第15章輸入輸出接口設(shè)計(jì)(略)

第15章輸入輸出接口及設(shè)計(jì)天道酬勤主要內(nèi)容I/O系統(tǒng)概述I/O系統(tǒng)的性能I/O系統(tǒng)的功能I/O設(shè)備概述I/O設(shè)備的通用模型I/O接口的分類I/O控制器的結(jié)構(gòu)I/O端口的概念I(lǐng)/O設(shè)備的尋址I/O設(shè)備、I/O總線、I/O接口、I/O控制器的連接I/OSystem的性能兩個(gè)常用的性能指標(biāo)：Throughput:I/Obandwidth(吞吐率，即：I/O帶寬)單位時(shí)間內(nèi)從系統(tǒng)輸入/輸出多少數(shù)據(jù)？單位時(shí)間內(nèi)實(shí)現(xiàn)了多少次輸入/輸出操作？(服務(wù)器更關(guān)注)Responsetime:Latency(響應(yīng)時(shí)間，即：等待延遲)：在多長(zhǎng)時(shí)間內(nèi)完成請(qǐng)求的任務(wù)？(臺(tái)式機(jī)和嵌入式更關(guān)注)不同的任務(wù)對(duì)性能的要求不同：要求吞吐量高的場(chǎng)合：如：多媒體應(yīng)用（音/視頻的播放要流暢?。┮箜憫?yīng)時(shí)間短的場(chǎng)合：如：事務(wù)處理系統(tǒng)（存/取款的速度要快！）要求吞吐率高且響應(yīng)時(shí)間短的場(chǎng)合：如：ATM、文件服務(wù)器、Web服務(wù)器等I/OSystem的功能輸入/出系統(tǒng)的功能解決各種形式信息的輸入和輸出

即：用戶如何將所需的信息(文字、圖表、聲音、視頻等)通過(guò)不同的外設(shè)輸入到計(jì)算機(jī)中，以及計(jì)算機(jī)內(nèi)部處理的結(jié)果信息如何通過(guò)相應(yīng)的外設(shè)輸出給用戶要實(shí)現(xiàn)上述功能需解決以下一系列的問(wèn)題怎樣在CPU、主存和外設(shè)間建立一個(gè)信息傳輸“通路”怎樣將用戶的I/O請(qǐng)求轉(zhuǎn)換成設(shè)備的命令如何對(duì)外設(shè)進(jìn)行編址怎樣使CPU方便地尋找到要訪問(wèn)的外設(shè)I/O硬件和操作系統(tǒng)如何協(xié)調(diào)完成主機(jī)和外設(shè)之間的數(shù)據(jù)傳送，

等等15.1I/O接口概述I/O接口：I/O設(shè)備與I/O控制器之間的連接器包括：插頭/插座的形式、通訊規(guī)程和電器特性等分類：從數(shù)據(jù)傳輸方式來(lái)分：串行（一次只傳輸1位）并行（多位一起進(jìn)行傳輸）從是否能連接多個(gè)設(shè)備來(lái)分：總線式（可連接多個(gè)設(shè)備）獨(dú)占式（只能連接1個(gè)設(shè)備）從是否符合標(biāo)準(zhǔn)來(lái)分：標(biāo)準(zhǔn)接口（通用接口）專用接口（專用接口）按功能選擇的靈活性來(lái)分：可編程接口不可編程接口串行口并行口I/O設(shè)備接口串行口9針并行口VGA視頻口鍵盤接口雙絞線接口PS/2接口并行口25針同軸電纜網(wǎng)絡(luò)接口顯示器接口麥克風(fēng)音箱鍵盤接口并行口USB接口以太網(wǎng)雙絞線接口串行口鼠標(biāo)器接口(安裝在主板上的I/O設(shè)備接口)I/O總線,I/O控制器,I/O接口與I/O設(shè)備的關(guān)系I/O設(shè)備通常都是物理上相互獨(dú)立的設(shè)備，它們一般通過(guò)I/O接口與I/O控制器連接打印機(jī)掃描儀顯示器麥克風(fēng)網(wǎng)線I/O總線I/O接口硬盤光驅(qū)I/O設(shè)備CPU主板I/O設(shè)備I/O控制器（擴(kuò)充卡）機(jī)箱插座板卡插座I/O控制器PCI插槽內(nèi)存主板插槽機(jī)箱芯片組IDE接口機(jī)箱插座I/O設(shè)備鍵盤鼠標(biāo)器多數(shù)教材把I/O控制器和插座合起來(lái)稱為I/O接口。yALU寄存器組CPU總線接口R6CPU(前端)總線I/O總線主板擴(kuò)展槽PCI接口南橋芯片I/O總線磁盤控制器以太網(wǎng)卡USB控制器和接口鼠標(biāo)器鍵盤網(wǎng)線disk聲卡視頻卡光驅(qū)主存儲(chǔ)器0A北橋芯片y存儲(chǔ)器總線顯卡I/O總線,I/O控制器,I/O接口與I/O設(shè)備的關(guān)系I/O控制器通過(guò)擴(kuò)展卡或者南橋芯片與I/O總線連接I/O總線經(jīng)過(guò)北橋芯片與內(nèi)存、CPU連接I/O接口（I/O控制器）的職能數(shù)據(jù)緩沖

提供數(shù)據(jù)緩沖寄存器，以達(dá)到主機(jī)和外設(shè)工作速度的匹配錯(cuò)誤或狀態(tài)檢測(cè)

提供狀態(tài)寄存器，以保存各種錯(cuò)誤或狀態(tài)信息供CPU查用控制和定時(shí)

提供控制和定時(shí)邏輯，以接受從系統(tǒng)總線來(lái)的控制定時(shí)信號(hào)數(shù)據(jù)格式轉(zhuǎn)換

提供數(shù)據(jù)格式轉(zhuǎn)換部件使通過(guò)外部接口得到的數(shù)據(jù)轉(zhuǎn)換為內(nèi)部接口需要的格式，或在相反的方向進(jìn)行數(shù)據(jù)格式轉(zhuǎn)換與主機(jī)和設(shè)備通信

上述功能通過(guò)I/O接口與主機(jī)之間、I/O接口與設(shè)備之間的通信來(lái)完成I/O接口（I/O控制器）的結(jié)構(gòu)I/O控制器的一般結(jié)構(gòu)通過(guò)I/O控制寄存器發(fā)送命令字來(lái)向設(shè)備發(fā)送命令通過(guò)從狀態(tài)寄存器讀取狀態(tài)字來(lái)獲取外設(shè)或I/O控制器的狀態(tài)信息通過(guò)向I/O控制器發(fā)送或讀取數(shù)據(jù)來(lái)和外設(shè)進(jìn)行數(shù)據(jù)交換將I/O控制器中CPU能夠訪問(wèn)的各類寄存器稱為I/O端口對(duì)外設(shè)的訪問(wèn)通過(guò)向I/O端口發(fā)命令、讀狀態(tài)、讀/寫數(shù)據(jù)來(lái)進(jìn)行15.1.1I/O地址空間和I/O指令（1）統(tǒng)一編址方式（內(nèi)存映射方式）

與主存統(tǒng)一編址，將主存空間分出一部分地址給I/O端口進(jìn)行編號(hào)（因該方法是將I/O端口映射到主存空間的某區(qū)，故也被稱為“存儲(chǔ)器映射方式”）

例如，Motorola公司生產(chǎn)的處理器就采用該方案（2）獨(dú)立編址方式（特殊I/O指令方式）不和主存單元一起編號(hào)，單獨(dú)編號(hào)，成為一個(gè)獨(dú)立的I/O地址空間（因需專門I/O指令，故也稱為“特殊I/O指令方式”）

例如，Intel公司和Zilog公司的處理器就是獨(dú)立編址方式對(duì)I/O端口讀寫，就是向I/O設(shè)備送出命令或從設(shè)備取得狀態(tài)或讀/寫設(shè)備數(shù)據(jù)一個(gè)I/O控制器可能會(huì)占有多個(gè)端口地址I/O端口必須編號(hào)后，CPU才能訪問(wèn)I/O設(shè)備的尋址方式就是I/O端口的編號(hào)方式統(tǒng)一編址方式CPU不直接通過(guò)讀寫控制信號(hào)IOR#、IOW#對(duì)I/O端口讀寫，而是根據(jù)I/O端口在地址空間的位置，通過(guò)地址譯碼來(lái)實(shí)現(xiàn)地址線的高位參與片選控制邏輯無(wú)需設(shè)置專門I/O指令，只要用一般訪存指令就可存取I/O端口I/O模塊MemR#或MemW#命令由訪存指令發(fā)出，IOR#和IOW#命令怎樣呢？也是訪存指令，只是訪問(wèn)的地址范圍不同！統(tǒng)一編址方式優(yōu)點(diǎn)與訪存指令一致的存/取指令減少對(duì)專門I/O指令的設(shè)計(jì)利用豐富的訪存指令進(jìn)行I/O操作（不僅可對(duì)端口進(jìn)行數(shù)據(jù)傳送，而且還可直接對(duì)端口進(jìn)行移位、測(cè)試等）便于擴(kuò)大系統(tǒng)吞吐率外設(shè)或I/O寄存器數(shù)目幾乎不受限制，而只受總存儲(chǔ)容量的限制。在大型控制或數(shù)據(jù)通信系統(tǒng)等特殊場(chǎng)合很有用讀寫控制邏輯簡(jiǎn)單缺點(diǎn)主存空間減少。因?yàn)楸籌/O占用了存儲(chǔ)空間外設(shè)尋址時(shí)間長(zhǎng)。為了識(shí)別I/O端口,全部地址線都需參與地址譯碼，使譯碼電路復(fù)雜并需花很長(zhǎng)時(shí)間獨(dú)立編址方式通過(guò)不同的讀寫控制信號(hào)IOR#、IOW#和MEMR#、MEMW#來(lái)實(shí)現(xiàn)對(duì)I/O端口和存儲(chǔ)器的讀寫一般I/O端口比存儲(chǔ)器單元少，選擇I/O端口時(shí)，只需少量地址線指令系統(tǒng)必須設(shè)計(jì)專門的I/O指令是專門的I/O指令，指令中給的地址可能相同，但操作命令不同！MemR#或MemW#命令由訪存指令發(fā)出，IOR#和IOW#命令怎樣呢？獨(dú)立編址方式優(yōu)點(diǎn)I/O端口地址不占用存儲(chǔ)器地址空間，故主存空間不受I/O地址的影響I/O地址線較少，所以I/O端口譯碼簡(jiǎn)單，尋址速度快使用專用I/O指令，程序清晰，便于理解和檢查缺點(diǎn)專用I/O指令類型少，只提供簡(jiǎn)單的傳輸操作，故程序設(shè)計(jì)靈活性差要求處理器提供兩組讀寫命令(MEMR/MEMW、IOR/IOW)，增加了控制邏輯的復(fù)雜性和處理器引腳數(shù)15.1.2I/O查詢與中斷I/OPolling(輪詢，查詢):

最簡(jiǎn)單的I/O方式I/O設(shè)備（包括I/O接口）將自己的狀態(tài)放到一個(gè)狀態(tài)寄存器中OS階段性查詢狀態(tài)寄存器中的特定狀態(tài)，決定下一步的動(dòng)作OS主動(dòng)查詢，也稱為程序查詢方式或程序直接控制方式在傳送數(shù)據(jù)前，需要查詢了解外設(shè)的工作狀態(tài)。只有查詢的狀態(tài)滿足條件時(shí)，才執(zhí)行本次傳送。這種方式又稱之為條件傳送或狀態(tài)驅(qū)動(dòng)傳送方式。

程序程序查詢方式舉例：用程序直接控制方式控制打印輸出開(kāi)始讀接口狀態(tài)輸出一個(gè)字符就緒否讀打印機(jī)狀態(tài)忙否啟動(dòng)打印讀打印機(jī)狀態(tài)完成否結(jié)束出錯(cuò)處理NYNY出錯(cuò)否YNNY……問(wèn)題：這里“就緒”的含義是什么？打印控制器的數(shù)據(jù)緩沖中內(nèi)容已被取走打印，現(xiàn)在為“空”，可以接收新打印字符程序控制I/O（程序查詢I/O）特點(diǎn)簡(jiǎn)單、易控制、外圍接口控制邏輯少CPU與外設(shè)串行工作，效率低、速度慢，適于慢速設(shè)備查詢開(kāi)銷極大(CPU完全在等待“外設(shè)完成”)工作方式：完全串行工作方式或部分串行僅用于CPU速度不高、外設(shè)配備不多的情況外設(shè)CPU啟動(dòng)探詢完成啟動(dòng)探詢完成“踏步”現(xiàn)象工作工作“探詢”期間，可以一直不斷查詢(原地“踏步”)，也可以定時(shí)查詢(但要保證數(shù)據(jù)不丟失！)。I/O中斷I/OInterrupt(中斷I/O):

絕大多數(shù)系統(tǒng)都支持的中斷I/O方式若一個(gè)I/O設(shè)備需要CPU干預(yù)，它就通過(guò)中斷請(qǐng)求通知CPUCPU中止當(dāng)前程序的執(zhí)行，調(diào)出OS（中斷處理程序）來(lái)執(zhí)行處理結(jié)束后，再返回到被中止的程序繼續(xù)執(zhí)行OS被動(dòng)調(diào)出，也稱為中斷驅(qū)動(dòng)I/O方式中斷I/O方式基本思想：

當(dāng)外設(shè)準(zhǔn)備好時(shí)，便向CPU發(fā)中斷請(qǐng)求，CPU響應(yīng)后，中止現(xiàn)行程序的執(zhí)行，轉(zhuǎn)入一個(gè)“中斷服務(wù)程序”進(jìn)行輸入/出操作，實(shí)現(xiàn)主機(jī)和外設(shè)接口之間的數(shù)據(jù)傳送，并啟動(dòng)外設(shè)工作?！爸袛喾?wù)程序”執(zhí)行完后，返回原被中止的程序斷點(diǎn)處繼續(xù)執(zhí)行。此時(shí)，外設(shè)和CPU并行工作。外設(shè)CPU啟動(dòng)完成啟動(dòng)完成工作工作工作請(qǐng)求響應(yīng)啟動(dòng)請(qǐng)求響應(yīng)中斷服務(wù)程序返回15.1.3DMA輸入/出方式DMA的全稱直接存儲(chǔ)器存取(DirectMemoryAccess)為什么要引入DMA方式？程序直接控制方式受“踏步”現(xiàn)象的限制，效率低下，不適合高速設(shè)備和主機(jī)間的數(shù)據(jù)傳送中斷控制方式雖比程序直接控制方式有效，CPU和外設(shè)有一定的并行度，但由于下列原因也不適合高速設(shè)備和主機(jī)間的數(shù)據(jù)傳送對(duì)I/O請(qǐng)求響應(yīng)慢。每傳送一個(gè)數(shù)據(jù)都要等待外設(shè)的中斷請(qǐng)求，并增加許多中斷響應(yīng)和中斷處理前、后的附加開(kāi)銷(保護(hù)斷點(diǎn)、現(xiàn)場(chǎng)等)，不能及時(shí)響應(yīng)I/O請(qǐng)求。因單位數(shù)據(jù)之間的間隔短，甚至無(wú)法再利用，必須讓一批數(shù)據(jù)交換完，這樣交換數(shù)據(jù)便完全占用主機(jī)，又回到完全串行工作狀態(tài)數(shù)據(jù)傳送速度慢。數(shù)據(jù)傳送由軟件完成(由CPU執(zhí)行相應(yīng)的中斷服務(wù)程序來(lái)完成)，速度慢，由于單位數(shù)據(jù)不斷完成交換的準(zhǔn)備，便可能沖掉信息而造成數(shù)據(jù)丟失DMA概述DMA方式的基本思想在高速外設(shè)和主存之間直接傳送數(shù)據(jù)由專門硬件(即：DMA接口)控制總線進(jìn)行傳輸DMA方式適用場(chǎng)合高速設(shè)備(如：磁盤、光盤等)成批數(shù)據(jù)交換，且單位數(shù)據(jù)間的時(shí)間間隔較短采用“請(qǐng)求－響應(yīng)”方式每當(dāng)高速設(shè)備準(zhǔn)備好數(shù)據(jù)，就進(jìn)行一次“DMA請(qǐng)求”，DMA控制器接受到DMA請(qǐng)求后，申請(qǐng)總線使用權(quán)DMA控制器的總線使用優(yōu)先級(jí)比CPU高，為什么？與中斷控制方式結(jié)合使用DMA傳送前，“尋道”“旋轉(zhuǎn)”等操作結(jié)束時(shí)，通過(guò)“中斷”告知CPUDMA控制器控制總線傳送數(shù)據(jù)時(shí)，CPU執(zhí)行其他程序DMA傳送結(jié)束時(shí)，要通過(guò)“DMA結(jié)束中斷”告知CPU與中斷控制方式結(jié)合使用舉例：用于磁盤和主存間數(shù)據(jù)交換時(shí)尋道旋轉(zhuǎn)連續(xù)讀寫結(jié)束、校驗(yàn)中斷方式中斷方式DMA方式中斷方式DMA和程序中斷兩種方式的數(shù)據(jù)通路DMA概述CPU主存AC

中斷接口DMA接口I/O

設(shè)備中斷方式數(shù)據(jù)傳送通路輸入指令輸出指令DMA方式數(shù)據(jù)傳送通路DMA傳送是以主存為中心，它在外設(shè)主存間開(kāi)辟了直接數(shù)據(jù)傳輸通路，且該通路是完全用硬件實(shí)現(xiàn)的。主存啟動(dòng)地址的確定、傳輸長(zhǎng)度的計(jì)數(shù)與控制、主存與外設(shè)間的數(shù)據(jù)傳送等均由DMA接口的邏輯電路完成。

程序中斷傳送的數(shù)據(jù)傳送必須通過(guò)CPU寄存器和使用CPU的指令，是以CPU為中心的。DMA方式的特點(diǎn)外圍設(shè)備訪問(wèn)請(qǐng)求直接發(fā)往主存儲(chǔ)器不需要CPU做保存現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)等工作DMA控制器中，需要設(shè)置數(shù)據(jù)寄存器、設(shè)備狀態(tài)或控制寄存器、主存地址寄存器、設(shè)備地址寄存器和數(shù)據(jù)交換個(gè)數(shù)計(jì)數(shù)器DMA開(kāi)始和結(jié)束時(shí)，需要處理機(jī)進(jìn)行管理在DMA方式開(kāi)始前，對(duì)DMA控制器進(jìn)行初始化。傳送主存緩沖區(qū)首地址、設(shè)備地址、數(shù)據(jù)塊的長(zhǎng)度等，并啟動(dòng)設(shè)備開(kāi)始工作在DMA方式結(jié)束后，向CPU申請(qǐng)中斷，對(duì)數(shù)據(jù)緩沖區(qū)進(jìn)行后處理DMA執(zhí)行中，數(shù)據(jù)傳送過(guò)程不需要CPU干預(yù)DMA概述

直接存儲(chǔ)器訪問(wèn)DMACPU DMA控制器 (DMAC)c存儲(chǔ)器硬盤控制器硬盤直接傳輸數(shù)據(jù)請(qǐng)求使用總線允許使用總線DMA控制器的操作步驟DMA操作步驟(1)DMA控制器的預(yù)置(初始化)—軟件實(shí)現(xiàn)準(zhǔn)備內(nèi)存設(shè)置參數(shù)啟動(dòng)外設(shè)

(2)DMA數(shù)據(jù)傳送—硬件實(shí)現(xiàn)DMA請(qǐng)求：選通→DMA請(qǐng)求→總線請(qǐng)求DMA響應(yīng)：總線響應(yīng)(CPU讓出總線)→DMA響應(yīng)DMA傳送：DMA控制總線進(jìn)行數(shù)據(jù)傳送(3)DMA結(jié)束處理—軟件實(shí)現(xiàn)根據(jù)計(jì)數(shù)值為“0”，發(fā)出DMA結(jié)束信號(hào)去接口控制產(chǎn)生DMA中斷請(qǐng)求信號(hào)，轉(zhuǎn)入中斷服務(wù)程序，做一些數(shù)據(jù)校驗(yàn)等后處理工作。I/O設(shè)備與主機(jī)進(jìn)行數(shù)據(jù)交換的三種基本方式I/OPolling(輪詢，查詢):I/OInterrupt(中斷I/O):DirectMemoryAccess(DMA方式):

磁盤等高速外設(shè)特有的I/O方式磁盤等高速外設(shè)成批地直接和主存進(jìn)行數(shù)據(jù)交換需要專門的DMA控制器控制總線，完成數(shù)據(jù)傳送當(dāng)外設(shè)準(zhǔn)備好數(shù)據(jù)后，向DMA控制器發(fā)DMA請(qǐng)求信號(hào)，DMA控制器再向CPU發(fā)總線請(qǐng)求，CPU讓出總線后，由DMA控制器控制總線進(jìn)行傳輸，無(wú)需CPU干涉小結(jié)

DMA方式與程序中斷方式的比較(1)數(shù)據(jù)傳送(2)響應(yīng)時(shí)間(3)處理異常情況(4)中斷請(qǐng)求(5)優(yōu)先級(jí)中斷方式DMA方式程序硬件指令執(zhí)行結(jié)束存取周期結(jié)束能不能低高傳送數(shù)據(jù)結(jié)束處理小結(jié)三種I/O方式的CPU工作效率比較存取周期結(jié)束CPU執(zhí)行現(xiàn)行程序CPU執(zhí)行現(xiàn)行程序DMA請(qǐng)求啟動(dòng)I/OI/O準(zhǔn)備I/O準(zhǔn)備一個(gè)存取周期實(shí)現(xiàn)I/O與主存之間的傳送CPU

執(zhí)行現(xiàn)行程序CPU查詢等待并傳輸I/O數(shù)據(jù)CPU執(zhí)行現(xiàn)行程序啟動(dòng)I/OI/O準(zhǔn)備及傳送指令執(zhí)行周期結(jié)束CPU執(zhí)行現(xiàn)行程序CPU執(zhí)行現(xiàn)行程序啟動(dòng)I/O中斷請(qǐng)求I/O準(zhǔn)備I/O準(zhǔn)備CPU處理中斷服務(wù)程序?qū)崿F(xiàn)I/O與主機(jī)之間的傳送間斷啟動(dòng)I/O啟動(dòng)I/OI/O準(zhǔn)備中斷請(qǐng)求啟動(dòng)I/OI/O準(zhǔn)備一個(gè)存取周期DMA請(qǐng)求程序查詢方式程序中斷方式DMA方式I/O準(zhǔn)備及傳送CLKDATAR/W (a)同步傳送DATAR/WRDY (b)異步傳送c15.1.4總線和總線的同步方式在同步通信方式下，通信雙方由統(tǒng)一的時(shí)鐘控制數(shù)據(jù)傳送，該時(shí)鐘通常是由CPU發(fā)出的，并傳送到總線上的所有部件。由于采用了公共時(shí)鐘，各個(gè)功能部件何時(shí)發(fā)送或接收信息都由統(tǒng)一時(shí)鐘規(guī)定，因此同步通信具有較高的數(shù)據(jù)傳輸率。異步通信方式是指利用數(shù)據(jù)發(fā)送部件和接收部件之間的相互“握手”信號(hào)(非統(tǒng)一時(shí)鐘)來(lái)實(shí)現(xiàn)總線數(shù)據(jù)傳送的方式。異步通信方式優(yōu)點(diǎn)：總線周期長(zhǎng)度可變，便于實(shí)現(xiàn)不同速度部件之間的數(shù)據(jù)傳送。缺點(diǎn)：會(huì)增加總線的復(fù)雜性和成本。15.2數(shù)據(jù)錯(cuò)誤檢測(cè)及校正三種常用的檢錯(cuò)糾錯(cuò)碼：奇偶檢錯(cuò)碼，用于并行數(shù)據(jù)傳送中海明檢錯(cuò)與糾錯(cuò)碼，用于并行數(shù)據(jù)傳送中循環(huán)冗余碼，用于串行數(shù)據(jù)傳送中編碼過(guò)程譯碼過(guò)程傳送原始數(shù)據(jù)碼字結(jié)果數(shù)據(jù)形成校驗(yàn)位的值，加進(jìn)特征檢查接送的碼字，發(fā)現(xiàn)/改正錯(cuò)誤能檢驗(yàn)奇數(shù)位錯(cuò)誤糾錯(cuò)碼，能糾正1位錯(cuò)誤校驗(yàn)碼概述定義：是一種具有發(fā)現(xiàn)某些錯(cuò)誤或自動(dòng)改正錯(cuò)誤能力的一種數(shù)據(jù)編碼方法。目的：用于檢查或糾正在存取、讀寫和傳送數(shù)據(jù)過(guò)程中可能出現(xiàn)的錯(cuò)誤。基本思想：“冗余校驗(yàn)”，即通過(guò)在有效信息代碼的基礎(chǔ)上，添加一些冗余位來(lái)構(gòu)成整個(gè)校驗(yàn)碼。構(gòu)成：有效信息＋校驗(yàn)位概念過(guò)程有效信息校驗(yàn)碼編碼器校驗(yàn)碼校驗(yàn)位校驗(yàn)碼發(fā)送/寫/存接收/讀/取有效信息校驗(yàn)位有效信息校驗(yàn)位校驗(yàn)碼譯碼器正確錯(cuò)誤輸出校驗(yàn)碼概述概念形成校驗(yàn)位的值，加進(jìn)特征檢查接收的碼字，發(fā)現(xiàn)/改正錯(cuò)誤15.2.1奇偶校驗(yàn)偶校驗(yàn)奇校驗(yàn)校驗(yàn)位用于并行碼檢錯(cuò)原理：在n位數(shù)據(jù)碼之外增加1位校驗(yàn)位，使n+1位碼字中取值為1的位數(shù)總保持為偶數(shù)（偶校驗(yàn)）或奇數(shù)（奇校驗(yàn)）。例如：

00011000100001

01010010110101

原有數(shù)字位兩個(gè)新的碼字

數(shù)據(jù)編碼、傳送及檢錯(cuò)過(guò)程：設(shè)原始數(shù)據(jù)為d6d5d4d3d2d1d0，增加1個(gè)偶校驗(yàn)位d7，構(gòu)成8位偶校驗(yàn)編碼。d7=d6⊕d5⊕d4⊕d3⊕d2⊕d1⊕d0式中⊕為異或運(yùn)算。發(fā)送方把8位的偶校驗(yàn)碼d7d6d5d4d3d2d1d0

發(fā)送出去。接收方收到8位偶校驗(yàn)碼d7d6d5d4d3d2d1d0

。校驗(yàn)電路用來(lái)檢查8位數(shù)據(jù)中取值1的個(gè)數(shù)是否為偶數(shù)。若是，則沒(méi)有出錯(cuò)，否則，出現(xiàn)了錯(cuò)誤。check=d7⊕d6⊕d5⊕d4⊕d3⊕d2⊕d1⊕d0奇校驗(yàn)位形成偶校驗(yàn)位出錯(cuò)奇校驗(yàn)位出錯(cuò)偶校驗(yàn)位形成XYG8G7G6G5G4G3G2G1G校奇偶校驗(yàn)碼奇偶校驗(yàn)位的形成及校驗(yàn)電路奇偶校驗(yàn)又分為垂直校驗(yàn)水平校驗(yàn)水平垂直校驗(yàn)1、垂直(縱向)奇偶校驗(yàn)以七單位碼數(shù)字0--9為例說(shuō)明垂直奇偶校驗(yàn)碼表1七單位數(shù)字的垂直奇偶校驗(yàn)碼(偶校驗(yàn)）0123456789B70000000000B61111111111B51111111111B40000000011B30000111100B20011001100B10101010101校驗(yàn)01101001102、水平(橫向)奇偶校驗(yàn)對(duì)一組信息內(nèi)各字符的同一位進(jìn)行奇偶校驗(yàn)時(shí)，稱為水平奇偶校驗(yàn)。仍以七單位碼為例并用表2-2來(lái)說(shuō)明。傳送時(shí)是按列傳送字符。表2水平奇偶校驗(yàn)（偶校驗(yàn)）0123456789校驗(yàn)B700000000000B611111111110B511111111110B400000000110B300001111000B200110011000B1010101010113、水平垂直奇偶校驗(yàn)同時(shí)進(jìn)行水平和垂直奇偶校驗(yàn)的方式稱為水平垂直奇偶校驗(yàn)。仍以七單位碼為例來(lái)說(shuō)明，如表3。0123456789校驗(yàn)B700000000000B611111111110B511111111110B400000000110B300001111000B200110011000B101010101011校驗(yàn)01101001101表3水平垂直奇偶校驗(yàn)水平校驗(yàn)碼和垂直校驗(yàn)碼只能發(fā)現(xiàn)奇數(shù)個(gè)錯(cuò)，不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)。水平垂直校驗(yàn)碼具有較強(qiáng)的檢錯(cuò)能力，它不但能發(fā)現(xiàn)所有一位、二位和三位錯(cuò)誤，而且能改正一位錯(cuò)誤。練習(xí)題1.設(shè)有8位信息為11000001，奇校驗(yàn)碼是何值?偶校驗(yàn)碼又是何值?要求寫出計(jì)算的過(guò)程，并分析檢錯(cuò)與糾錯(cuò)能力。15.2.2錯(cuò)誤糾正碼ECC

海明碼海明校驗(yàn)碼的原理是在數(shù)據(jù)中加入幾個(gè)校驗(yàn)位，并把數(shù)據(jù)的每一個(gè)二進(jìn)制位分配在幾個(gè)奇偶校驗(yàn)組中。當(dāng)某一位出錯(cuò)后，就會(huì)引起有關(guān)幾個(gè)校驗(yàn)位的值發(fā)生變化，這不但可以發(fā)現(xiàn)錯(cuò)誤，還能指出是哪一位出錯(cuò)。在此介紹糾正一位錯(cuò)誤的編碼。n位信息k位校驗(yàn)碼海明校驗(yàn)碼構(gòu)成m位k=?校驗(yàn)位的狀態(tài)應(yīng)當(dāng)有m+1種(含無(wú)錯(cuò))，以便能指出m位中的任何一位有錯(cuò)或無(wú)錯(cuò)。所以增添的奇偶校驗(yàn)位數(shù)k應(yīng)滿足：

2k≥m+1=n+k+1不同位數(shù)的數(shù)據(jù)編成海明碼所需的最小校驗(yàn)位數(shù)，如表4。表4不同位數(shù)的數(shù)據(jù)所需海明碼的最小校驗(yàn)位數(shù)nk1~33

4~104

11~255

27~576

58~1207若要求發(fā)現(xiàn)2位錯(cuò)誤，則校驗(yàn)碼應(yīng)當(dāng)在前述基礎(chǔ)上再增加1位校驗(yàn)位。即用(k-1)代替上式中的k。若海明碼的最高位號(hào)為m，最低位號(hào)為1。DmDm-1······D2D1海明碼的編碼規(guī)則：(1)、校驗(yàn)位位數(shù)與數(shù)據(jù)位位數(shù)之和為m，每個(gè)校驗(yàn)位Ｐi在海明碼中被分在位號(hào)2i-1的位置，其余各位為數(shù)據(jù)位，從低位向高位依次排列。(2)、海明碼的每一位Di(包括數(shù)據(jù)位和校驗(yàn)位本身)由多個(gè)校驗(yàn)位校驗(yàn)，其關(guān)系:

被校驗(yàn)的每一位位號(hào)＝∑2i-1(i=1…)(3)、在增大合法碼的碼距時(shí)，使所有碼的碼距盡量均勻地增大，以保證對(duì)所有碼的檢錯(cuò)能力平衡提高。D13D12D11D10D9D8D7D6D5D4D3D2D1P0A8A7A6A5P8A4A3A2P4A1P2P1例如對(duì)一個(gè)字節(jié)進(jìn)行海明編碼。每個(gè)字節(jié)由8個(gè)二進(jìn)制位組成(n=8)，根據(jù)表4可知k=4，再加上一位對(duì)整個(gè)信息的校驗(yàn)位(分清是兩位出錯(cuò)還是一位出錯(cuò))，故海明碼的位數(shù)為13，表示：由編碼規(guī)則(2)，得出如表5。表5海明碼位號(hào)與校驗(yàn)位的位號(hào)關(guān)系海明碼位號(hào)數(shù)據(jù)位/校驗(yàn)位參與校驗(yàn)的校驗(yàn)位位號(hào)海明碼位號(hào)=位號(hào)之和D1P111=1D2P222=2D3A11,23=1+2D4P444=4D5A21,45=1+4D6A32,46=2+4D７A41,2,47=1+2+4D8P888=8D9A51,89=1+8D10A62,810=2+8D11A71,2,811=1+2+8D12A84,812=4+8D13

P01313=13從表5求出Pi值的偶校驗(yàn)的結(jié)果：P1=A1⊕A2⊕A4⊕A5⊕A7P2=A1⊕A3⊕A4⊕A6⊕A7P4=A2⊕A3⊕A4⊕A8P8=A5⊕A6⊕A7⊕A8P0=A1⊕A2⊕A3⊕A4⊕A5⊕A6⊕A7⊕A8⊕P1⊕P2⊕P4⊕P8對(duì)接收到的海明碼形成新的校驗(yàn)位Ci，對(duì)按配偶(或奇)原則配置的海明碼，若各Ci均為0(或1)，則傳送過(guò)程正確；否則根據(jù)各Ci形成的值可指出錯(cuò)誤的位置。Ci的形成過(guò)程C1=P1⊕A1⊕A2⊕A4⊕A5⊕A7C2=P2⊕A1⊕A3⊕A4⊕A6⊕A7C4=P3⊕A2⊕A3⊕A4⊕A8

C8=P4⊕A5⊕A6⊕A7⊕A8C0=P0⊕P8⊕P4⊕P2⊕P1⊕A1⊕A2⊕A3⊕A4⊕A5⊕A6⊕A7⊕A8海明碼海明碼的糾錯(cuò)例如對(duì)字符C(8位)進(jìn)行海明校驗(yàn)，其海明碼如下:從上述公式可知P1=A1⊕A2⊕A4⊕A5⊕A7=1

⊕1

⊕0

⊕0

⊕1=1P2=A1⊕A3⊕A4⊕A6⊕A7=1

⊕0

⊕0

⊕0

⊕1=0P4=A2⊕A3⊕A4⊕A8=1

⊕0

⊕0

⊕0=1P8=A5⊕A6⊕A7⊕A8=0

⊕0

⊕1

⊕0=1P0=0海明碼為：0010010011101D13D12D11D10D9D8D7D6D5D4D3D2D1P50100P8001P41P2P1設(shè)其中一位出錯(cuò)，如第八位接收到的編碼為：D13D12D11D10D9D8D7D6D5D4D3D2D10010000011101校驗(yàn)結(jié)果：C1=P1⊕A1⊕A2⊕A4⊕A5⊕A7=0C2=P2⊕A1⊕A3⊕A4⊕A6⊕A7=0C4=P4⊕A2⊕A3⊕A4⊕A8=0C8=P8⊕A5⊕A6⊕A7⊕A8=1C0=1由于C8C4C2C1不為0000，所以有錯(cuò)，錯(cuò)誤位在C8C4C2C1=1000處。至于其它情況，可以類推。(12，8)分組碼海明校驗(yàn)線路=1A8D12

11000111=1A4D7=1A3D60110=1A2D50101=1A1D30011=1A5D91001=1A6D101010=1A7D1110110000無(wú)錯(cuò)有錯(cuò)4~16譯碼器D12D11D10D9D8D12D7D6D5D4D11D10D7D6D3D2D11D9D7D5D3D1奇偶形成線路C8奇偶形成線路C4奇偶形成線路C2奇偶形成線路C1C8C4C2C1海明碼設(shè)要傳送的數(shù)據(jù)A4A3A2A1=0101，則需增添檢測(cè)位k=3，其位置安排為A4A3A2P3A1P2P1。按配偶原則得各校驗(yàn)位：P1=A4⊕A2⊕A1=0⊕0⊕1=1P2=A4⊕A3⊕A1=0⊕1⊕1=0P4=A4⊕A3⊕A2=0⊕1⊕0=1故0101的海明碼應(yīng)為：A4A3A2P4A1P2P1=0101101海明碼例題若接收到的海明碼為0101111，其糾錯(cuò)過(guò)程如下：新的檢測(cè)位為：C4

=P4⊕A4⊕A3⊕A2=1⊕0⊕1⊕0=0C2=P2⊕A4⊕A3⊕A1=1⊕0⊕1⊕1=1C1=P1⊕A4⊕A2⊕A1=1⊕1⊕0⊕1=0其中C2不為0，出了錯(cuò)，出錯(cuò)位置在C4C2C1=010,即第2位，計(jì)算機(jī)自動(dòng)將“1”改為“0”。海明碼一般用在能糾錯(cuò)1位的場(chǎng)合。對(duì)任意n位信息，先求出需增加的檢測(cè)位數(shù)k，再確定Pi的位置，按奇或偶原則來(lái)配置Pi各位的值即可。海明碼例題15.2.3循環(huán)冗余校驗(yàn)(CRC碼)循環(huán)冗余校驗(yàn)碼主要用于傳輸純二進(jìn)制串行信息的情況。循環(huán)冗余校驗(yàn)碼由信息位(n位)加上校驗(yàn)位(k位)構(gòu)成。即n位信息位k位校驗(yàn)位應(yīng)用CRC碼的關(guān)鍵是如何從n位信息得到k位校驗(yàn)位，以及如何從n+k位信息碼判斷是否出錯(cuò)。n+k位1、模2四則運(yùn)算模2運(yùn)算是指按位模2相加為基礎(chǔ)的四則運(yùn)算，運(yùn)算時(shí)不考慮進(jìn)位和借位。(1)模2加減法

0+0=0

0+1=1

1+0=1

1+1=0

0-0=0

0-1=1

1-0=1

1-1=0結(jié)論：減去一個(gè)數(shù)等于加上該數(shù)。加、減法都是異或。(2)模2乘法——按模2加求部分積。例1011

110

————————

0000

1011

1011

——————————

111010(3)模2除法——按模2減求余數(shù)。例101

|——————

101｜10000

101

——————

010

000

——————

100

101

——————

01

···余數(shù)循環(huán)冗余校驗(yàn)碼①

模2加減的結(jié)果相同：即按位加，可用異或邏輯實(shí)現(xiàn)0±0=0、0±1=1、1±0=1、1±1=0②

模2乘：按模2加求部分積之和③模2除：按模2減求部分余數(shù)。

101……

商每求一位商應(yīng)使部分余數(shù)減少一

10110000位，上商的原則是：當(dāng)部分余數(shù)

101的首位為1時(shí)，商取1；當(dāng)部分

010余數(shù)的位數(shù)少于除數(shù)的位數(shù)時(shí)，

000該余數(shù)即為最后余數(shù)。

100101

01…余數(shù)模2運(yùn)算設(shè)待編碼的信息為Dn-1Dn-2···D1D0。將待編碼的n位有效信息位組表示為多項(xiàng)式M(x)；

M(x)=Dn-1xk-1+Dn-2xk-2+···+D1x+D0由于CRC碼(M位）是由信息位(n位)加上校驗(yàn)位(k位)構(gòu)成，故相當(dāng)于將M(x)左移了k位，即M(x)*xk，這樣就可以空出k位來(lái)拼接k位校驗(yàn)位。2、CRC碼編碼方法00……0Dn-1Dn-2···D1D0k位首先將有效信息位M(x)左移k位形成M(x)·xk，右邊空出的k位用于拼接校驗(yàn)位，然后用多項(xiàng)式M(x)·xk除以生成多項(xiàng)式G(x),得到一個(gè)商和一個(gè)余數(shù)(校驗(yàn)位),把余數(shù)緊跟在數(shù)據(jù)位之后發(fā)送。

M(x)·xk+R(x)=[Q(x)·G(x)+R(x)]+R(x)=[Q(x)·G(x)]+[R(x)+R(x)]按模2加，得CRC碼

=Q(x)·G(x)當(dāng)接收端收到信息時(shí)，用同樣的方法也除出一個(gè)余數(shù)。若余數(shù)為0，則傳送正確；若余數(shù)不為0，由該余數(shù)可指出哪一位出錯(cuò)，并糾正。注意:除法為模2除法。

CRC碼的校驗(yàn)位生成方法例：對(duì)四位有效信息(1100)，求CRC碼，生成多項(xiàng)式為1011。M(x)*x3=(x3+x2)*x3=x6+x5=1100000111|————————1011|11000001011——————————11101011——————————10101011—————————010CRC碼=M(x)*x3+010=1100010大家可除以G(x)看余數(shù)是否為0。上述CRC碼稱為(7，4)碼，M=7，n=43、CRC的譯碼與糾錯(cuò)通過(guò)上例求出一位出錯(cuò)模式如表6表6

(7,4)循環(huán)碼的出錯(cuò)模式(生成多項(xiàng)式G(x)=1011)a1

a2

a3

a4

a5

a6

a7余數(shù)出錯(cuò)位正確1

100010000無(wú)錯(cuò)誤11000110017110000001061100110100511010100114111001011031000010111201000101011如果循環(huán)碼有一位出錯(cuò)，用G(x)做模2除將得到一個(gè)不為0的余數(shù)。如果對(duì)該余數(shù)補(bǔ)0繼續(xù)除下去，將會(huì)發(fā)現(xiàn)一個(gè)有趣的結(jié)果：各次余數(shù)將按表6順序循環(huán)。這就是“循環(huán)碼”名稱的由來(lái)。并不是任何一個(gè)（r+1）位多項(xiàng)式都可以作為生成多項(xiàng)式。從檢錯(cuò)及糾錯(cuò)的要求出發(fā)，生成多項(xiàng)式應(yīng)能滿足下列要求：①任何位發(fā)生錯(cuò)誤都應(yīng)使余數(shù)不為0。②不同位發(fā)生錯(cuò)誤應(yīng)當(dāng)使余數(shù)不同。③對(duì)余數(shù)繼續(xù)作模2除，應(yīng)使余數(shù)循環(huán)。循環(huán)冗余校驗(yàn)碼關(guān)于生成多項(xiàng)式4、實(shí)現(xiàn)模2除法的線路循環(huán)碼校驗(yàn)的邏輯線路核心是模2除法線路。模2除的分解步驟歸納為兩種類型：如果余數(shù)(包括被除數(shù))最高位為0，則將余數(shù)左移一位；如果余數(shù)最高位為1，則對(duì)生成多項(xiàng)式G(x)作模2加法(異或)，然后余數(shù)左移一位。電路如圖2所示。圖2模2除邏輯圖圖2實(shí)現(xiàn)Ｇ(X)=1011的(7,4)碼模2除線路圖由于G(x)固定不變，故G2可省去；只求其余三位，故G3和T0也失去意義?？珊?jiǎn)化為圖3(a)。判斷題1、使用檢錯(cuò)/糾錯(cuò)碼會(huì)增加硬件成本，因而只適用于發(fā)生故障概率比較高的地方2、奇偶校驗(yàn)碼只能發(fā)現(xiàn)錯(cuò)誤，不能糾錯(cuò)3、海明碼只能發(fā)現(xiàn)錯(cuò)誤，不能糾錯(cuò)4、CRC碼只能發(fā)現(xiàn)錯(cuò)誤，不能糾錯(cuò)錯(cuò)對(duì)錯(cuò)錯(cuò)補(bǔ)充題1.有一個(gè)（8，4）碼，生成多項(xiàng)式為G（X）=X4+X3+X2+1，寫出代碼1011的CRC校驗(yàn)碼，要求寫出計(jì)算的過(guò)程。2.設(shè)有16位信息為1100001101101101，海明碼是何值?說(shuō)明編碼方法，寫出計(jì)算的過(guò)程，并分析所選方案具有怎樣的檢錯(cuò)與糾錯(cuò)能力。3.設(shè)有8位信息為11000001，奇校驗(yàn)碼是何值?偶校驗(yàn)碼又是何值?要求寫出計(jì)算的過(guò)程，并分析檢錯(cuò)與糾錯(cuò)能力。15.4PS/2接口startd0d1d2d3d4d5d6d7paritystopps2_dataps2_clkPS/2鍵盤送數(shù)據(jù)給主機(jī)的時(shí)序圖管腳說(shuō)明：只需接4根線，VCC要+5V，時(shí)鐘和數(shù)據(jù)線要用雙向口線，F(xiàn)PGA可以不用外接上拉電阻。另外，USB鍵盤也可以用，只要用一個(gè)轉(zhuǎn)接頭轉(zhuǎn)成PS2即可。15.4.1PS/2鍵盤例如，按下“L”鍵再放開(kāi)，則送出4BF04B（掃描碼是4B）又如，按下 “Delete”鍵再放開(kāi)，則送出E071E0F071（E0：擴(kuò)展鍵；71：掃描碼）。

如果長(zhǎng)時(shí)間按下“L”鍵再放開(kāi)，則送出4B4B...4BF04B多個(gè)鍵可以同時(shí)被按下，比如先按左“Shift”(掃描碼為12）,按下“L”鍵再放開(kāi)“L”鍵,再放開(kāi)“Shift”鍵，則送出124BF04BF012c當(dāng)你按下一個(gè)一般的鍵，鍵盤側(cè)送出相應(yīng)的掃描碼；松開(kāi)時(shí)，送出F0接著又是掃描碼。前者稱為MakeCode（通碼），后者稱為BreakCode（斷碼）。擴(kuò)展鍵，在二者最前面又加上E0。PS/2鍵盤掃描碼掃描碼有兩種不同類型的通碼和斷碼當(dāng)一個(gè)鍵被按下或按住，就發(fā)送通碼（一個(gè)字節(jié)，但擴(kuò)展按鍵的通碼是兩字節(jié)或四字節(jié)寬，這類的通碼第一個(gè)字節(jié)總是為E0H。）；當(dāng)一個(gè)鍵被釋放，就發(fā)送斷碼（兩字節(jié)長(zhǎng)，第一個(gè)字節(jié)是F0H）。No.KEY通碼斷碼1"A"1CF01C2"5"2EF02E3"F10"09F0094RightALTE0

11E0F0115Right"Ctrl"E014E0F014第二套掃描碼基本按鍵斷碼，鍵盤會(huì)發(fā)送“F0”+“通碼”

擴(kuò)展按鍵斷碼，則發(fā)送“E0”+“F0”+“通碼”

PS/2發(fā)送數(shù)據(jù)到PC的時(shí)序在時(shí)鐘的下降沿讀取數(shù)據(jù)。(a)鍵盤發(fā)送時(shí)序 (b)鍵盤接收時(shí)序數(shù)據(jù)格式如果數(shù)據(jù)位中１的個(gè)數(shù)為偶數(shù)，校驗(yàn)位就為１；如果數(shù)據(jù)位中１的個(gè)數(shù)為奇數(shù)，校驗(yàn)位就為０；總之，數(shù)據(jù)位中１的個(gè)數(shù)加上校驗(yàn)位中１的個(gè)數(shù)總為奇數(shù)，因此總進(jìn)行奇校驗(yàn)。1個(gè)起始位總是邏輯08個(gè)數(shù)據(jù)位（LSB）低位在前1個(gè)奇偶校驗(yàn)位奇校驗(yàn)1個(gè)停止位總是邏輯11個(gè)應(yīng)答位僅用在主機(jī)對(duì)設(shè)備的通訊中ps2_keyboard.v

moduleps2_keyboard(clk,clrn,ps2_clk,ps2_data, rdn,data,ready,overflow,count); inputclk,clrn,ps2_clk,ps2_data; inputrdn; output[7:0]data; outputready; outputoverflow; output[3:0]count;//internalsignal,fortest regoverflow;//fifooverflow reg[3:0]count;//countps2_databits reg[9:0]buffer;//ps2_databits reg[7:0]fifo[7:0];//dataf