微機(jī) 錯(cuò)誤檢測(cè)和校正

MicrocomputerPrincipleandInterfacingTechniques

微機(jī)原理與接口技術(shù)微機(jī)原理課程組同濟(jì)大學(xué)電信學(xué)院控制科學(xué)與工程系Page22023/6/26TongjiUniversityMicrocomputerPrinciplesandInterfacing

Topic:ErrorDetection&Correction內(nèi)容基本問(wèn)題描述概念：檢錯(cuò)和糾錯(cuò)，碼距，數(shù)據(jù)校驗(yàn)碼，編碼和解碼，漏檢問(wèn)題奇偶校驗(yàn)碼海明碼循環(huán)冗余校驗(yàn)碼(CRC)三種編碼的比較

對(duì)每種編碼都應(yīng)重點(diǎn)理解其編碼原理，檢錯(cuò)原理和技術(shù)實(shí)現(xiàn)算法Page32023/6/26TongjiUniversity檢錯(cuò)和糾錯(cuò)問(wèn)題：數(shù)據(jù)在傳輸過(guò)程中不可避免的會(huì)發(fā)生各種錯(cuò)誤，那么數(shù)據(jù)的接收方如何判斷收到的數(shù)據(jù)是否有錯(cuò)(檢錯(cuò))？若出錯(cuò)能否自行修正(糾錯(cuò))？概念：檢錯(cuò)和糾錯(cuò)(Detection&Correction)相關(guān)概念：編碼和解碼(encoding&decoding)應(yīng)用：串行口數(shù)據(jù)傳輸：奇偶校驗(yàn)硬盤(pán)數(shù)據(jù)傳輸：CRC校驗(yàn)內(nèi)存數(shù)據(jù)檢錯(cuò)和傳輸：奇偶校驗(yàn)/海明校驗(yàn)無(wú)線(xiàn)數(shù)據(jù)傳輸：CRC校驗(yàn)/Turbo碼……磁盤(pán)陣列RAID技術(shù)Page42023/6/26TongjiUniversity數(shù)據(jù)校驗(yàn)碼概念：數(shù)據(jù)校驗(yàn)碼，編碼和解碼，漏檢問(wèn)題原理：檢錯(cuò)和糾錯(cuò)是建立在要對(duì)原始數(shù)據(jù)進(jìn)行編碼和解碼的基礎(chǔ)上的通過(guò)函數(shù)f

對(duì)數(shù)據(jù)進(jìn)行計(jì)算，以產(chǎn)生一種代碼，代碼和數(shù)據(jù)都被存儲(chǔ)和傳輸因此，若原始數(shù)據(jù)字長(zhǎng)為M位，校驗(yàn)碼長(zhǎng)為K位，則實(shí)際存儲(chǔ)的字長(zhǎng)應(yīng)該是M+K位。當(dāng)原先存儲(chǔ)的字讀出時(shí)，這個(gè)代碼用于檢錯(cuò)和糾錯(cuò)，在M位數(shù)據(jù)中產(chǎn)生一組新的K位代碼，與取出的代碼進(jìn)行比較：結(jié)果一致，無(wú)差錯(cuò)，取出的數(shù)據(jù)位傳送出去；檢測(cè)到差錯(cuò)，并可以糾正，數(shù)據(jù)位和糾錯(cuò)位一起送入糾正器，然后產(chǎn)生一組正確的M位數(shù)據(jù)位；檢測(cè)到差錯(cuò)，但無(wú)法糾正，報(bào)告出錯(cuò)Page52023/6/26TongjiUniversity奇偶校驗(yàn)碼編碼原理不管數(shù)據(jù)位長(zhǎng)度多少，校驗(yàn)位只有一位。若數(shù)據(jù)位和校驗(yàn)位一起包含奇數(shù)個(gè)“1”，則稱(chēng)為奇校驗(yàn)。若數(shù)據(jù)位和校驗(yàn)位一起包含偶數(shù)個(gè)“1”，則稱(chēng)為偶校驗(yàn)。例：數(shù)據(jù) 奇校驗(yàn)的編碼 偶校驗(yàn)的編碼

00000000 100000000 00000000001010100 001010100 101010100 01111111 001111111 101111111檢錯(cuò)(校驗(yàn))原理對(duì)采用奇校驗(yàn)的數(shù)據(jù)，如接收端收到是偶碼，則表示傳送傳輸有誤，采用偶校驗(yàn)的情形類(lèi)似。=>因此，奇偶校驗(yàn)可發(fā)現(xiàn)1位錯(cuò)，但無(wú)法定位錯(cuò)誤發(fā)生的位置Page62023/6/26TongjiUniversity奇偶校驗(yàn)碼實(shí)現(xiàn)無(wú)論編碼還是糾錯(cuò)，都可方便的采用異或運(yùn)算奇性=a0⊕a1⊕a2⊕…⊕an既可以方便的軟件實(shí)現(xiàn)，也可以方便的硬件實(shí)現(xiàn)Page72023/6/26TongjiUniversity1位糾錯(cuò)海明碼(原理)海明碼不僅能發(fā)現(xiàn)1位錯(cuò)，而且還能指出錯(cuò)誤位置，因此可支持糾錯(cuò)。原理/思路設(shè)有R位校驗(yàn)位，則共有0到2R-1個(gè)共2R個(gè)組合。若用0表示無(wú)差錯(cuò)，則剩余2R-1個(gè)值表示有差錯(cuò)，并指出錯(cuò)在第幾位。由于差錯(cuò)可能發(fā)生在K個(gè)數(shù)據(jù)位中或R個(gè)校驗(yàn)位中，因此必然有：

2R–1R+K

Page82023/6/26TongjiUniversity海明校驗(yàn)碼(校驗(yàn)位數(shù))海明碼需要幾位校驗(yàn)碼？k—數(shù)據(jù)位的位數(shù)

r—校驗(yàn)位的位數(shù)數(shù)據(jù)位k與校驗(yàn)位r的關(guān)系：2r

≥k+r+1數(shù)據(jù)位k校驗(yàn)位r總位數(shù)n1232~435~75~1149~1512~26517~3127~57633~6358~120765~127Page92023/6/26TongjiUniversity海明校驗(yàn)碼(校驗(yàn)位置)校驗(yàn)位和數(shù)據(jù)位是如何排列的校驗(yàn)位排列在2i–1(i=0,1,2,…)的位置上例：有一個(gè)BCD碼為D4D3D2D1,由此生成一個(gè)海明碼

7654321D4D3D2P3D1P2P1

22

2120

有一字節(jié)的信息需生成海明碼

D8D7D6D5P4D4D3D2P3D1P2P1

8421Page102023/6/26TongjiUniversity校驗(yàn)位取值公式(校驗(yàn)計(jì)算)海明碼的校驗(yàn)位Pi和數(shù)值位Di的關(guān)系 例：BCD碼為1011P3=D4⊕D3

⊕D2

0=

1⊕0⊕1P2=D4

⊕D3

⊕D1

0=

1⊕0⊕1P1=D4

⊕D2

⊕D1

1=

1⊕1⊕1

最后

海明碼為1010101Page112023/6/26TongjiUniversity765432122D4D3D2P321D4D3D1P220D4D2D1P11位糾錯(cuò)海明碼的實(shí)現(xiàn)把M+K=m個(gè)數(shù)據(jù)=>HmHm-1...H2H1(海明碼）,每個(gè)校驗(yàn)位Pi在海明碼中被分配在2i-1位置上。Hi由多個(gè)校驗(yàn)位校驗(yàn)(多重校驗(yàn)思想)每個(gè)海明碼的位號(hào)要等于參與校驗(yàn)它的幾個(gè)檢驗(yàn)位的位號(hào)之和。目的：盡量增大合法碼的碼距。舉例：M=8，K=4，則海明碼為：H12H11H10H9H8H7H6H5H4H3H2H1P4,P3,P2,P1根據(jù)規(guī)則，分別對(duì)應(yīng)于：H8,,H4,,

H2,,

H1這樣，P1=M1M2M4M5M7P2=M1M3M4M6M7P3=M2M3M4M8P4=M5M6M7M8Page122023/6/26TongjiUniversity1位糾錯(cuò)海明碼的實(shí)現(xiàn)(續(xù))

P1=M1M2M4M5M7P2=M1M3M4M6M7P3=M2M3M4M8P4=M5M6M7M8Page132023/6/26TongjiUniversity12111098765432120M7M5M4M2M1P121M7M6M4M3M1P222M8M4M3M2P323M8M7M6M5P4基于海明碼的糾錯(cuò)海明碼的接收端的公式:S3=P3⊕D4⊕D3

⊕D2

S2=

P2⊕D4

⊕D3

⊕D1

S1=P1⊕D4

⊕D2

⊕D1假定海明碼1010101在傳送中變成了1000101S3=P3⊕D4⊕D3

⊕D2=0⊕1⊕0⊕0=1

S2=

P2⊕D4

⊕D3

⊕D1=0⊕1⊕0

⊕1=0S1=P1⊕D4

⊕D2

⊕D1=1⊕1⊕0

⊕1=1

因此,由S3S2S1=101,指出第5位錯(cuò),應(yīng)由0變1Page142023/6/26TongjiUniversity校驗(yàn)位用文氏圖計(jì)算舉例Page152023/6/26TongjiUniversity3D17D45D26D3A即S1B即S2C即S31P12P24P3用文氏圖計(jì)算舉例7654321D4D3D2P3D1P2P1海明碼的糾錯(cuò)原理(文氏圖)4位海明糾錯(cuò)碼的糾錯(cuò)原理（文氏圖）Page162023/6/26TongjiUniversity1110ABC......….1100ABC1110ABC1偶校驗(yàn)結(jié)果00100傳送后1位錯(cuò)1110ABC1糾正后的結(jié)果003756ABC..1241位糾錯(cuò)2位海明碼的實(shí)現(xiàn)如出現(xiàn)兩位錯(cuò),必須再增加一位奇偶校驗(yàn)位Page172023/6/26TongjiUniversity0110ABC0110ABC0100010ABC1100011ABC1100010ABC110111110011ABC1101010110100101001001110010011101100111位糾錯(cuò)2位海明碼的實(shí)現(xiàn)上述這種碼稱(chēng)為單糾錯(cuò)碼（SEC）。通常半導(dǎo)體存儲(chǔ)器采用SEC-DED（單糾錯(cuò)-雙檢錯(cuò)碼）。雙檢錯(cuò)碼與SEC相比需要增加1個(gè)附加位。實(shí)例在IBM3000系列中，主存64位數(shù)據(jù)采用8位SEC-DED碼進(jìn)行校驗(yàn)，占了12%的系統(tǒng)開(kāi)銷(xiāo)；VAX計(jì)算機(jī)中32位字長(zhǎng)機(jī)器，采用7位SED-DED碼，占了22%的系統(tǒng)開(kāi)銷(xiāo)Page182023/6/26TongjiUniversity循環(huán)冗余校驗(yàn)(CRC)碼循環(huán)冗余校驗(yàn)碼基本原理CRC碼是將一串二進(jìn)制看成是系數(shù)為0或1的多項(xiàng)式，一個(gè)有k位組成的幀可以看成從xk-1到x0的k次多項(xiàng)式的系數(shù)序列，這個(gè)多項(xiàng)式的階數(shù)為k-1。最高位是xk-1項(xiàng)的系數(shù)，次高位是xk-2的系數(shù)，且多項(xiàng)式以2為模運(yùn)算。校驗(yàn)和的計(jì)算思路 (1)設(shè)G(x)為r階，在幀的末尾附加r個(gè)零，使幀具有m+r位數(shù)據(jù)，相應(yīng)的多項(xiàng)式可以表示為xrM(x)。 (2)按照模2除法，用xrM(x)除以對(duì)應(yīng)的生成多項(xiàng)式G(x)。 (3)由上面的步驟得到一個(gè)商Q(x)和一個(gè)余數(shù)R(x)，將其中的余數(shù)R(x)作為校驗(yàn)和。Page192023/6/26TongjiUniversity循環(huán)冗余校驗(yàn)(CRC)碼CRC碼的編碼方法模2加減:異或邏輯—0⊕0=0;

0⊕1=1;

1⊕0=1;1⊕1=0.模2乘:模2除:

1010101/10000

×10110110100100000000101010010001010101Page202023/6/26TongjiUniversity101循環(huán)冗余校驗(yàn)(CRC)碼例:M(x)=x3+x2=1100M(x)·x3=x6+x5=1100000

G(x)=x3+x+1=1011M(x)·x31100000010G(x)10111011

M(x)·x3+R(x)=1100000+010=1100010

編好的循環(huán)校驗(yàn)碼稱(chēng)為(7,4)碼,即n=7,k=4Page212023/6/26TongjiUniversity==1110+循環(huán)冗余校驗(yàn)(CRC)碼A1A2A3A4A5A6A7余數(shù)正確1100010000A7錯(cuò)1100011001A6錯(cuò)1100000010A5錯(cuò)1100110100A4錯(cuò)1101010011A3錯(cuò)1110010110A2錯(cuò)1000010111A1錯(cuò)0100010101Page22將收到的CRC碼用約定的生成多項(xiàng)式G(x)去除,如果碼字無(wú)誤則余數(shù)應(yīng)位0,如果有某一位出錯(cuò),則余數(shù)不為0,不同位數(shù)出錯(cuò)余數(shù)不同.如果對(duì)余數(shù)補(bǔ)個(gè)0繼續(xù)除下去,我們將發(fā)現(xiàn)一個(gè)現(xiàn)象:各次余數(shù)將按上表順序循環(huán).2023/6/26TongjiUniversityCRC的譯碼與糾錯(cuò)CRC碼的糾錯(cuò)方法根據(jù)不同的余數(shù)來(lái)糾正不同的出錯(cuò)位循環(huán)除法:余數(shù)添0繼續(xù)除法,同時(shí)信息部分進(jìn)行循環(huán)移位.當(dāng)最高位變成101時(shí),則最高位取反,糾錯(cuò).繼續(xù)余數(shù)除法,直至循環(huán)一遍,余數(shù)變成第一次的余數(shù).例A5出錯(cuò)

11001101000101100101繼續(xù)循環(huán)

1001101011101100000100110111100110001010