ch2-4 數(shù)據(jù)校驗(yàn)碼

1、1 元件故障、噪聲干擾等各種因素常常導(dǎo)致計(jì)算機(jī)在處理信息元件故障、噪聲干擾等各種因素常常導(dǎo)致計(jì)算機(jī)在處理信息過(guò)程中出現(xiàn)錯(cuò)誤。為了防止錯(cuò)誤過(guò)程中出現(xiàn)錯(cuò)誤。為了防止錯(cuò)誤, , 可將信號(hào)采用專(zhuān)門(mén)的邏輯線(xiàn)可將信號(hào)采用專(zhuān)門(mén)的邏輯線(xiàn)路進(jìn)行編碼以檢測(cè)錯(cuò)誤路進(jìn)行編碼以檢測(cè)錯(cuò)誤, ,甚至校正錯(cuò)誤。甚至校正錯(cuò)誤。 通常的方法是：通常的方法是：在每個(gè)字上添加一些校驗(yàn)位在每個(gè)字上添加一些校驗(yàn)位, ,用來(lái)確定字中出用來(lái)確定字中出 現(xiàn)錯(cuò)誤的位置?，F(xiàn)錯(cuò)誤的位置。 常用方法：常用方法： 奇偶校驗(yàn)碼奇偶校驗(yàn)碼 ； 海明校驗(yàn)與糾錯(cuò)碼海明校驗(yàn)與糾錯(cuò)碼 ； 循環(huán)冗余校驗(yàn)碼循環(huán)冗余校驗(yàn)碼 。1.1.為什么設(shè)置校驗(yàn)碼為什么設(shè)置校驗(yàn)碼數(shù)據(jù)

2、校驗(yàn)碼數(shù)據(jù)校驗(yàn)碼21、碼字：、碼字：由若干位代碼組成，滿(mǎn)足某種編碼規(guī)由若干位代碼組成，滿(mǎn)足某種編碼規(guī)律的一個(gè)代碼字。律的一個(gè)代碼字。例：例：編碼規(guī)則編碼規(guī)則“代碼中代碼中1的個(gè)數(shù)為奇數(shù)的個(gè)數(shù)為奇數(shù)”則則 “01001001”合法合法 “11001001”不合法不合法2、數(shù)據(jù)校驗(yàn)的實(shí)現(xiàn)原理、數(shù)據(jù)校驗(yàn)的實(shí)現(xiàn)原理：數(shù)據(jù)校驗(yàn)碼是在合法：數(shù)據(jù)校驗(yàn)碼是在合法的數(shù)據(jù)編碼之間，加進(jìn)一些不允許出現(xiàn)的的數(shù)據(jù)編碼之間，加進(jìn)一些不允許出現(xiàn)的(非非法的法的)編碼，使合法的數(shù)據(jù)編碼出現(xiàn)錯(cuò)誤時(shí)成編碼，使合法的數(shù)據(jù)編碼出現(xiàn)錯(cuò)誤時(shí)成為非法編碼。這樣就可以通過(guò)檢測(cè)編碼的合為非法編碼。這樣就可以通過(guò)檢測(cè)編碼的合法性達(dá)到發(fā)現(xiàn)錯(cuò)誤的目

3、的。法性達(dá)到發(fā)現(xiàn)錯(cuò)誤的目的。數(shù)據(jù)校驗(yàn)碼原理32.2.奇偶校驗(yàn)奇偶校驗(yàn) 原理原理：在在 k 位數(shù)據(jù)碼之外增加位數(shù)據(jù)碼之外增加 1 位校驗(yàn)位，位校驗(yàn)位， 使使 k+1 位碼字中取值為位碼字中取值為 1 的位數(shù)的位數(shù)保持為保持為 偶數(shù)（偶校驗(yàn)偶數(shù)（偶校驗(yàn)）或）或 奇數(shù)奇數(shù)（奇校驗(yàn)奇校驗(yàn)）偶校驗(yàn)偶校驗(yàn)奇校驗(yàn)奇校驗(yàn)校驗(yàn)位校驗(yàn)位0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 1原有數(shù)據(jù)位原有數(shù)據(jù)位 兩個(gè)新的碼字兩個(gè)新的碼字例如：例如：奇偶校驗(yàn)碼（奇偶校驗(yàn)碼（N+1位）位）=N位有效信息位有效信息+1位校驗(yàn)位位校驗(yàn)位4同理同理, ,偶校驗(yàn)位偶校驗(yàn)位

4、定義為定義為 C C x0 x1 xn-1即即x中包含偶數(shù)個(gè)中包含偶數(shù)個(gè)1 1時(shí)時(shí), ,才使才使C C0 0。設(shè)設(shè)x( x0 x1xn-1 )是一個(gè)是一個(gè)n n位字位字, , 則則奇校驗(yàn)位奇校驗(yàn)位定義為定義為 C C x0 x1 xn-1式中式中代表按位加代表按位加, , 只有當(dāng)只有當(dāng)x中包含有奇數(shù)個(gè)中包含有奇數(shù)個(gè)1 1時(shí)時(shí), ,C C0 0。校驗(yàn)位形成校驗(yàn)位形成5例：例： 校驗(yàn)位的取值（校驗(yàn)位的取值（0或或1）將使整個(gè)校驗(yàn)）將使整個(gè)校驗(yàn)碼中碼中“1”的個(gè)數(shù)為奇數(shù)或偶數(shù)，所以有兩種的個(gè)數(shù)為奇數(shù)或偶數(shù)，所以有兩種可供選擇的校驗(yàn)規(guī)律：可供選擇的校驗(yàn)規(guī)律： 奇校驗(yàn)奇校驗(yàn)整個(gè)校驗(yàn)碼（有效信息位和校驗(yàn)位

5、）整個(gè)校驗(yàn)碼（有效信息位和校驗(yàn)位）中中“1”的個(gè)數(shù)為奇數(shù)的個(gè)數(shù)為奇數(shù)。 偶校驗(yàn)偶校驗(yàn)整個(gè)校驗(yàn)碼中整個(gè)校驗(yàn)碼中“1”的個(gè)數(shù)為偶數(shù)的個(gè)數(shù)為偶數(shù)。有有效效信信息息（8 8 位位）奇奇檢檢驗(yàn)驗(yàn)碼碼（9 9 位位）偶偶檢檢驗(yàn)驗(yàn)碼碼（9 9 位位）0 00 00 00 00 00 00 00 01 10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 10 01 10 00 00 01 10 00 01 10 01 10 00 00 01 11 10 01 10 01 10 00 00 01 10 01 11 11 11 11 11 11 10

6、00 01 11 11 11 11 11 11 11 10 01 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 10 01 11 11 11 11 11 11 11 16CPU奇偶奇偶校驗(yàn)校驗(yàn)電路電路主存主存加入校驗(yàn)碼后的計(jì)算機(jī)系統(tǒng)加入校驗(yàn)碼后的計(jì)算機(jī)系統(tǒng)8位位8位位9位位9位位0101010101010101101010101110101010101010101101010101101010111101010111有有4個(gè)個(gè)1有有5個(gè)個(gè)1正確正確出錯(cuò)出錯(cuò)有有6個(gè)個(gè)1中斷處理中斷處理7特點(diǎn)：特點(diǎn)： 奇偶

7、校驗(yàn)可提供單（奇偶校驗(yàn)可提供單（奇數(shù)奇數(shù)）個(gè)錯(cuò)誤檢測(cè)，）個(gè)錯(cuò)誤檢測(cè)， 但無(wú)法檢測(cè)多（但無(wú)法檢測(cè)多（偶偶數(shù)數(shù)）個(gè)錯(cuò)誤個(gè)錯(cuò)誤, 更無(wú)法識(shí)別錯(cuò)誤信息的位置及糾正錯(cuò)誤。更無(wú)法識(shí)別錯(cuò)誤信息的位置及糾正錯(cuò)誤。 發(fā)送：發(fā)送： x0 x1xn-1C （算出（算出C加到需發(fā)送字的后面）加到需發(fā)送字的后面） 接收：接收： x0 x1 xn-1 C 計(jì)算：計(jì)算：Fx0 x1 xn-1 C 結(jié)果：若結(jié)果：若F1，意味著收到的信息有錯(cuò)；，意味著收到的信息有錯(cuò)； 若若F0，表明，表明x字傳送正確。字傳送正確。校驗(yàn)方法：校驗(yàn)方法： (以偶校驗(yàn)為例以偶校驗(yàn)為例)奇偶校驗(yàn)碼常用于存儲(chǔ)器讀寫(xiě)檢查，或奇偶校驗(yàn)碼常用于存儲(chǔ)器讀寫(xiě)檢查

8、，或ASCII字符傳送過(guò)程字符傳送過(guò)程中的檢查。中的檢查。8編譯碼電路編譯碼電路D7D6D5D4D3D2D1D0D校奇形成偶校驗(yàn)出錯(cuò)奇校驗(yàn)出錯(cuò)偶形成AB=1=1=1=1=1=1=1=1119交叉奇偶校驗(yàn) 計(jì)算機(jī)在進(jìn)行大量字節(jié)（數(shù)據(jù)塊）傳計(jì)算機(jī)在進(jìn)行大量字節(jié)（數(shù)據(jù)塊）傳送時(shí)，不僅每一個(gè)字節(jié)有一個(gè)奇偶校驗(yàn)位送時(shí)，不僅每一個(gè)字節(jié)有一個(gè)奇偶校驗(yàn)位做橫向校驗(yàn)，而且全部字節(jié)的同一位也設(shè)做橫向校驗(yàn)，而且全部字節(jié)的同一位也設(shè)置一個(gè)奇偶校驗(yàn)位做縱向校驗(yàn)，這種橫向、置一個(gè)奇偶校驗(yàn)位做縱向校驗(yàn)，這種橫向、縱向同時(shí)校驗(yàn)的方法稱(chēng)為交叉校驗(yàn)?？v向同時(shí)校驗(yàn)的方法稱(chēng)為交叉校驗(yàn)。 第第1字節(jié)字節(jié) 1 1 0 0 1 0 1 1

9、 1 第第2字節(jié)字節(jié) 0 1 0 1 1 1 0 0 0 第第3字節(jié)字節(jié) 1 0 0 1 1 0 1 0 0 第第4字節(jié)字節(jié) 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 010交叉奇偶校驗(yàn) 交叉校驗(yàn)可以發(fā)現(xiàn)兩位同時(shí)出錯(cuò)的情交叉校驗(yàn)可以發(fā)現(xiàn)兩位同時(shí)出錯(cuò)的情況，假設(shè)第況，假設(shè)第2字節(jié)的字節(jié)的a6、a4兩位均出錯(cuò)，橫兩位均出錯(cuò)，橫向校驗(yàn)位無(wú)法檢出錯(cuò)誤，但是第向校驗(yàn)位無(wú)法檢出錯(cuò)誤，但是第a6、a4位位所在列的縱向校驗(yàn)位會(huì)顯示出錯(cuò)，這與前所在列的縱向校驗(yàn)位會(huì)顯示出錯(cuò)，這與前述的簡(jiǎn)單奇偶校驗(yàn)相比要保險(xiǎn)多了。述的簡(jiǎn)單奇偶校驗(yàn)相比要保險(xiǎn)多了。 11幾個(gè)基本概念1、多項(xiàng)式與二進(jìn)制數(shù)碼、多項(xiàng)式

10、與二進(jìn)制數(shù)碼 n多項(xiàng)式包括生成多項(xiàng)式多項(xiàng)式包括生成多項(xiàng)式G(x)和信息多項(xiàng)式和信息多項(xiàng)式C(x)。 n如生成多項(xiàng)式為如生成多項(xiàng)式為G(x)=x4+x3+x+1， 可轉(zhuǎn)可轉(zhuǎn)換為二進(jìn)制數(shù)碼換為二進(jìn)制數(shù)碼11011。 n而發(fā)送信息位而發(fā)送信息位 1111，可轉(zhuǎn)換為數(shù)據(jù)多項(xiàng)式，可轉(zhuǎn)換為數(shù)據(jù)多項(xiàng)式為為C(x)=x3+x2+x+1。 n最高次冪R=4122 2模模2 2運(yùn)算：運(yùn)算：不考慮借位和進(jìn)位不考慮借位和進(jìn)位（1 1）模）模2 2加減：加減：可用異或門(mén)實(shí)現(xiàn)，即：可用異或門(mén)實(shí)現(xiàn)，即：0+0=00+0=0；0+1=10+1=1；1+0=11+0=1；1+1=01+1=0；0-0=00-0=0；0-1=10

11、-1=1；1-0=11-0=1；1-1=01-1=0；（2 2）模）模2 2乘法：乘法：用模用模2 2加求部分積之和加求部分積之和例如：例如： 1011 x 11 1011 + 1011 1110113 （3） 模模2除法：除法：按模按模2減求部分余數(shù)，每上一位商，部分余減求部分余數(shù)，每上一位商，部分余數(shù)要減少一位，數(shù)要減少一位，上商規(guī)則是上商規(guī)則是：只要余數(shù)最高位為：只要余數(shù)最高位為1，則商，則商1，否則為否則為0。當(dāng)部分余數(shù)的位數(shù)小于除數(shù)時(shí)，該余數(shù)為最后余數(shù)。當(dāng)部分余數(shù)的位數(shù)小于除數(shù)時(shí)，該余數(shù)為最后余數(shù)。例如：例如： 111.商11（除數(shù)） 1000（被除數(shù)） 11 10 11 10 11

12、 1141 1CRCCRC的編碼方法的編碼方法循環(huán)冗余校驗(yàn)碼循環(huán)冗余校驗(yàn)碼（循環(huán)冗余校驗(yàn)碼（CRC）的基本原理是：）的基本原理是：在在K位信息碼后再拼位信息碼后再拼接接R位的校驗(yàn)碼，整個(gè)編碼長(zhǎng)度為位的校驗(yàn)碼，整個(gè)編碼長(zhǎng)度為N位，因此，這種編碼又叫位，因此，這種編碼又叫（N，K）碼。對(duì)于一個(gè)給定的（）碼。對(duì)于一個(gè)給定的（N，K）碼，可以證明存在一）碼，可以證明存在一個(gè)最高次冪為個(gè)最高次冪為N-K=R的多項(xiàng)式的多項(xiàng)式G(x)。根據(jù)。根據(jù)G(x)可以生成可以生成K位信位信息的校驗(yàn)碼，而息的校驗(yàn)碼，而G(x)叫做這個(gè)叫做這個(gè)CRC碼的碼的生成多項(xiàng)式生成多項(xiàng)式。 校驗(yàn)碼的具體生成過(guò)程為：假設(shè)發(fā)送信息用信

13、息多項(xiàng)式校驗(yàn)碼的具體生成過(guò)程為：假設(shè)發(fā)送信息用信息多項(xiàng)式C(X)表示，將表示，將C(x)左移左移R位，則可表示成位，則可表示成C(x)*2R ，這樣，這樣C(x)的右邊的右邊就會(huì)空出就會(huì)空出R位，這就是校驗(yàn)碼的位置。通過(guò)位，這就是校驗(yàn)碼的位置。通過(guò)C(x)* 2R除以生成除以生成多項(xiàng)式多項(xiàng)式G(x)得到的余數(shù)就是校驗(yàn)碼。得到的余數(shù)就是校驗(yàn)碼。 15CRC碼的生成（一）n多項(xiàng)式除法n1、將碼多項(xiàng)式C(x)乘以xrn2、用G(x)除C(x)*xr，得余式R(x)n3、 C(x)*xr+ R(x)及編碼后的多項(xiàng)式例: G(x)=x4+x3+x+1，C(x)=x3+x2+x+1，R=4nC(x)*x4

14、/G(x) = x2+1n校驗(yàn)碼：校驗(yàn)碼：0101n完整編碼：完整編碼：1111010116CRC碼的生成（二）n1、將x的最高冪次為R的生成多項(xiàng)式G(x)轉(zhuǎn)換成對(duì)應(yīng)的R+1位二進(jìn)制數(shù)。 n2、將信息碼左移R位，相當(dāng)與對(duì)應(yīng)的信息多項(xiàng)式C(x)*2R n3、用生成多項(xiàng)式（二進(jìn)制數(shù)）對(duì)信息碼做模2除，得到R位的余數(shù)。 n4、將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC碼。 17 例例 設(shè)四位有效信息位是設(shè)四位有效信息位是11001100，選用生成多項(xiàng)式，選用生成多項(xiàng)式 G(X)=G(X)=1 1011011，試求有效信息位試求有效信息位11001100的的CRCCRC編碼。編碼。 解：解：

15、(1)(1)將有效信息位將有效信息位11001100表示為多項(xiàng)式表示為多項(xiàng)式M(x)M(x) M(X) = X M(X) = X3 3 + X+ X2 2 = 1100= 1100 (2) (2)M(X)M(X)左移左移r=3r=3位，得位，得M(x)M(x)* *X X3 3 M(x)M(x)* *X X3 3 = X= X6 6 + X+ X5 5 = 1100000= 1100000 (3) (3)用用r+1r+1位的生成多項(xiàng)式位的生成多項(xiàng)式 G(X)G(X)，對(duì)，對(duì)M(x)M(x)* *X Xr r作作“模模2 2除除” 1100000/1011 = 1110 + 010/101111

16、00000/1011 = 1110 + 010/1011 (4) (4)M(x)M(x)* *X X3 3 與與r r位余數(shù)位余數(shù)R(X) R(X) 作作“模模2 2加加”，即可求得它，即可求得它的的CRCCRC編碼編碼 M(x)M(x)* *X X3 3 + R(X) = 1100000 + + R(X) = 1100000 + 010010 = 1100010 = 1100010 ( (模模2 2加加) ) 因?yàn)橐驗(yàn)閗=7k=7、n=4n=4，所以編好的，所以編好的CRCCRC碼又稱(chēng)為碼又稱(chēng)為(7(7，4)4)碼。碼。183CRC的譯碼及糾錯(cuò) CRC CRC碼傳送到目標(biāo)部件，用約定的多項(xiàng)式

17、碼傳送到目標(biāo)部件，用約定的多項(xiàng)式G(x)G(x)對(duì)收到的對(duì)收到的CRCCRC碼進(jìn)行碼進(jìn)行“模模2 2除除”，若余數(shù)為若余數(shù)為0 0，則表明該，則表明該CRCCRC校驗(yàn)碼正確；校驗(yàn)碼正確；否則表明有錯(cuò)，不同的出錯(cuò)位，其余數(shù)是不同的。由余數(shù)否則表明有錯(cuò)，不同的出錯(cuò)位，其余數(shù)是不同的。由余數(shù)具體指出是哪一位出了錯(cuò)，然后加以糾正。具體指出是哪一位出了錯(cuò)，然后加以糾正。 不同的出錯(cuò)位，其余數(shù)也是不同的。不同的出錯(cuò)位，其余數(shù)也是不同的?？梢宰C明：更換不同的有效信息位，余數(shù)與出錯(cuò)位的可以證明：更換不同的有效信息位，余數(shù)與出錯(cuò)位的對(duì)應(yīng)關(guān)系不會(huì)發(fā)生變化，只與碼制和生成多項(xiàng)式對(duì)應(yīng)關(guān)系不會(huì)發(fā)生變化，只與碼制和生成多

18、項(xiàng)式G(X)G(X)有關(guān)。有關(guān)。19(7,4)碼的出錯(cuò)模式碼的出錯(cuò)模式(G=1011)20不是任何一個(gè)不是任何一個(gè)(k+1)(k+1)位多項(xiàng)式都能作為生成多項(xiàng)式，從檢位多項(xiàng)式都能作為生成多項(xiàng)式，從檢錯(cuò)、糾錯(cuò)的要求來(lái)看，生成多項(xiàng)式應(yīng)滿(mǎn)足下列要求：錯(cuò)、糾錯(cuò)的要求來(lái)看，生成多項(xiàng)式應(yīng)滿(mǎn)足下列要求：(1)(1)任何一位發(fā)生錯(cuò)誤，都應(yīng)使余數(shù)不為零；任何一位發(fā)生錯(cuò)誤，都應(yīng)使余數(shù)不為零；(2)(2)不同位發(fā)生錯(cuò)誤，都應(yīng)使余數(shù)不同；不同位發(fā)生錯(cuò)誤，都應(yīng)使余數(shù)不同；(3)(3)用余數(shù)補(bǔ)零，繼續(xù)作用余數(shù)補(bǔ)零，繼續(xù)作“模模2 2除除”，應(yīng)使余數(shù)循環(huán)。，應(yīng)使余數(shù)循環(huán)。常用的常用的CRCCRC生成多項(xiàng)式：生成多項(xiàng)式：CR

19、C-12 12CRC-12 12位位 x x1212+x+x1111+x+x3 3+x+x2 2+1 +1 CRC-16 16CRC-16 16位位 x x1616+x+x1515+x+x2 2+1 +1 （IBM)IBM)CRC-16 16CRC-16 16位位 x x1616+x+x1212+x+x5 5+1 +1 （CCITT)CCITT)CRC-32 32CRC-32 32位位 x x3232+x+x2626+x+x2323+x+x1616+x+x1111+x+x1010+x+x8 8+x+x7 7+x+x5 5+x+x4 4+x+x2 2+x+1 +x+1 5 5、CRCCRC產(chǎn)生電

20、路產(chǎn)生電路 CRCCRC校驗(yàn)碼不僅檢錯(cuò)率高，而且硬件實(shí)現(xiàn)簡(jiǎn)單，因而到校驗(yàn)碼不僅檢錯(cuò)率高，而且硬件實(shí)現(xiàn)簡(jiǎn)單，因而到底廣泛應(yīng)用。底廣泛應(yīng)用。4 4關(guān)于生成多項(xiàng)式關(guān)于生成多項(xiàng)式211原理原理海明校驗(yàn)碼的實(shí)現(xiàn)原理是：在數(shù)據(jù)位中加入海明校驗(yàn)碼的實(shí)現(xiàn)原理是：在數(shù)據(jù)位中加入幾個(gè)校驗(yàn)位，將數(shù)據(jù)代碼的碼距均勻地拉大，幾個(gè)校驗(yàn)位，將數(shù)據(jù)代碼的碼距均勻地拉大，并把數(shù)據(jù)的每個(gè)二進(jìn)制位分配在幾個(gè)奇偶校并把數(shù)據(jù)的每個(gè)二進(jìn)制位分配在幾個(gè)奇偶校驗(yàn)組中。當(dāng)某一位出錯(cuò)后，就會(huì)引起有關(guān)的驗(yàn)組中。當(dāng)某一位出錯(cuò)后，就會(huì)引起有關(guān)的幾個(gè)校驗(yàn)位的值發(fā)生變化，這不但可以發(fā)現(xiàn)幾個(gè)校驗(yàn)位的值發(fā)生變化，這不但可以發(fā)現(xiàn)錯(cuò)誤，還能指出是哪一位出錯(cuò)，為進(jìn)

21、一步自錯(cuò)誤，還能指出是哪一位出錯(cuò)，為進(jìn)一步自動(dòng)糾錯(cuò)提供了依據(jù)。動(dòng)糾錯(cuò)提供了依據(jù)。3、海明校驗(yàn)碼222、編碼規(guī)則 若海明碼的最高位號(hào)為若海明碼的最高位號(hào)為m，最低位號(hào)為，最低位號(hào)為1，即，即mm-121，則，則海明碼的編碼規(guī)則是：海明碼的編碼規(guī)則是：（1）校驗(yàn)位與數(shù)據(jù)位之和為）校驗(yàn)位與數(shù)據(jù)位之和為m，每個(gè)校驗(yàn)位，每個(gè)校驗(yàn)位Pi在在海明碼中被分在位號(hào)海明碼中被分在位號(hào)2i-1的位置上，其余各位為的位置上，其余各位為數(shù)據(jù)位，并按從低向高逐位依次排列的關(guān)系分配數(shù)據(jù)位，并按從低向高逐位依次排列的關(guān)系分配各數(shù)據(jù)位。各數(shù)據(jù)位。（2）海明碼的每一位位碼）海明碼的每一位位碼Hi（包括數(shù)據(jù)位和校驗(yàn)（包括數(shù)據(jù)位和校

22、驗(yàn)位）由多個(gè)校驗(yàn)位校驗(yàn)，其關(guān)系是被校驗(yàn)的每一位）由多個(gè)校驗(yàn)位校驗(yàn)，其關(guān)系是被校驗(yàn)的每一位位號(hào)要等于校驗(yàn)它的各校驗(yàn)位的位號(hào)之和。位位號(hào)要等于校驗(yàn)它的各校驗(yàn)位的位號(hào)之和。（3）在增大碼距時(shí)，應(yīng)使所有的編碼的碼距盡量）在增大碼距時(shí)，應(yīng)使所有的編碼的碼距盡量均勻地增大，以保證對(duì)所有編碼的檢測(cè)能力平衡均勻地增大，以保證對(duì)所有編碼的檢測(cè)能力平衡地提高。地提高。23 假設(shè)欲檢測(cè)的有效信息為假設(shè)欲檢測(cè)的有效信息為n位，需增加的校驗(yàn)位為位，需增加的校驗(yàn)位為k位，則校位，則校驗(yàn)碼的長(zhǎng)度為驗(yàn)碼的長(zhǎng)度為n+k位。校驗(yàn)位的狀態(tài)組合，應(yīng)當(dāng)具有指出位。校驗(yàn)位的狀態(tài)組合，應(yīng)當(dāng)具有指出n+k位中任一位有錯(cuò)或無(wú)錯(cuò)的能力，即需要區(qū)

23、別出位中任一位有錯(cuò)或無(wú)錯(cuò)的能力，即需要區(qū)別出n+k+1種種狀態(tài)。應(yīng)滿(mǎn)足以下關(guān)系式：狀態(tài)。應(yīng)滿(mǎn)足以下關(guān)系式：2k-1n+k+1 這個(gè)關(guān)系式稱(chēng)為這個(gè)關(guān)系式稱(chēng)為海明不等式海明不等式，若信息位長(zhǎng)度，若信息位長(zhǎng)度n確定后，由此可確定后，由此可得到校驗(yàn)位得到校驗(yàn)位k的最短長(zhǎng)度。的最短長(zhǎng)度。 確定校驗(yàn)位后，就可以與信息位組成海明校驗(yàn)位。假設(shè)數(shù)據(jù)確定校驗(yàn)位后，就可以與信息位組成海明校驗(yàn)位。假設(shè)數(shù)據(jù)位是位是7位二進(jìn)制編碼，據(jù)上所述，位二進(jìn)制編碼，據(jù)上所述，校驗(yàn)位的位數(shù)校驗(yàn)位的位數(shù)k為為4,故海明故海明碼的總位數(shù)為碼的總位數(shù)為11。它們的排列關(guān)系可表示為：。它們的排列關(guān)系可表示為： 海明碼位號(hào)：海明碼位號(hào)： H1

24、1 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1 海明碼：海明碼： D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1 可知：可知： 每個(gè)校驗(yàn)位由其本身校驗(yàn)；每個(gè)校驗(yàn)位由其本身校驗(yàn)； 每個(gè)數(shù)據(jù)位由若干校驗(yàn)位校驗(yàn)每個(gè)數(shù)據(jù)位由若干校驗(yàn)位校驗(yàn)。3增添校驗(yàn)位24根據(jù)海明碼的編碼規(guī)則，每一位海明碼都有多個(gè)校驗(yàn)位根據(jù)海明碼的編碼規(guī)則，每一位海明碼都有多個(gè)校驗(yàn)位校驗(yàn)，且校驗(yàn)，且被校驗(yàn)的每一位的位號(hào)等于參與校驗(yàn)它的幾個(gè)校驗(yàn)被校驗(yàn)的每一位的位號(hào)等于參與校驗(yàn)它的幾個(gè)校驗(yàn)位的位號(hào)之和位的位號(hào)之和。 占據(jù)各權(quán)位上的校驗(yàn)位按權(quán)組成的占據(jù)各權(quán)位上的校驗(yàn)位按權(quán)組成的8421碼碼，正好等于，正好

25、等于海明碼的位號(hào)，即海明碼的位號(hào)海明碼的位號(hào)，即海明碼的位號(hào)Hi正好等于要校驗(yàn)它的校驗(yàn)正好等于要校驗(yàn)它的校驗(yàn)位所占權(quán)位權(quán)值之和。位所占權(quán)位權(quán)值之和。例如：例如：H11P423P221P120這說(shuō)明了這說(shuō)明了H11位將由位將由 P4、P2、P1進(jìn)行校驗(yàn)。進(jìn)行校驗(yàn)。校驗(yàn)位校驗(yàn)位P1可以校驗(yàn)：可以校驗(yàn)：H1 、H3、H5 、H7 、H9、H11、H13、H15校驗(yàn)位校驗(yàn)位P2可以校驗(yàn)：可以校驗(yàn)：H2 、H3、 H6、H7 、H10、H11、H14 、H15校驗(yàn)位校驗(yàn)位P3可以校驗(yàn)：可以校驗(yàn)：H4 、H5、 H6、 H7 、H12、H13、H14 、H15校驗(yàn)位校驗(yàn)位P4可以校驗(yàn)：可以校驗(yàn)：H8、H9

26、、 H10、H11、H12、H13、H14 、H15根據(jù)校驗(yàn)時(shí)根據(jù)校驗(yàn)時(shí)偶校驗(yàn)偶校驗(yàn)，可以寫(xiě)出相應(yīng)的校驗(yàn)方程。，可以寫(xiě)出相應(yīng)的校驗(yàn)方程。4校驗(yàn)位校驗(yàn)任務(wù)的分配25 方法方法：將錯(cuò)了的碼字重新代入校驗(yàn)方程校驗(yàn)一次即可。假設(shè)：將錯(cuò)了的碼字重新代入校驗(yàn)方程校驗(yàn)一次即可。假設(shè)上面例子中的海明碼上面例子中的海明碼01100000100傳送后，若傳送后，若H6位發(fā)生了位發(fā)生了錯(cuò)誤，變成了錯(cuò)誤，變成了01100100100，這時(shí)把它們代入上面的偶校，這時(shí)把它們代入上面的偶校驗(yàn)校驗(yàn)方程，如下：驗(yàn)校驗(yàn)方程，如下： H1 H3 H5 H7 H9 H110 1 0 0 1 0 = 0 = E1 H2 H3 H6 H

27、7 H10 H110 1 1 0 1 0= 1 = E2 H4 H5 H6 H70 0 1 0 = 1 = E3 H8 H9 H10 H110 1 1 0 = 0 = E4可以把可以把E4E3E2E1= 0110看成一個(gè)看成一個(gè)“錯(cuò)誤字錯(cuò)誤字”，因?yàn)槠涠驗(yàn)槠涠M(jìn)制碼為進(jìn)制碼為0110，說(shuō)明，說(shuō)明H6出了錯(cuò)，是出了錯(cuò)，是H6錯(cuò)成了錯(cuò)成了1，所以要糾錯(cuò)，所以要糾錯(cuò)，糾錯(cuò)時(shí)將糾錯(cuò)時(shí)將H6位取反值，即讓它恢復(fù)到正確值位取反值，即讓它恢復(fù)到正確值0。這樣糾錯(cuò)后。這樣糾錯(cuò)后即可得到正確的海明碼即可得到正確的海明碼01100000100。5檢錯(cuò)與糾錯(cuò)檢錯(cuò)與糾錯(cuò)26對(duì)字節(jié)的海明編碼和校驗(yàn)對(duì)字節(jié)的海明編碼和

28、校驗(yàn) (1)編碼編碼 一個(gè)字節(jié)由一個(gè)字節(jié)由8位二進(jìn)制位組成，此時(shí)位二進(jìn)制位組成，此時(shí)N=8，K=5，故海明碼的總位數(shù)為，故海明碼的總位數(shù)為13位，可表示為：位，可表示為： H13 H12 H2 H1 五個(gè)校驗(yàn)位五個(gè)校驗(yàn)位P5P1對(duì)應(yīng)的海明碼位號(hào)應(yīng)對(duì)應(yīng)的海明碼位號(hào)應(yīng)分別為：分別為：H13 、H8 、H4 、H2 、H1 ，除，除P5 外，外，其余四位都滿(mǎn)足其余四位都滿(mǎn)足Pi的位號(hào)等于的位號(hào)等于2i-1的關(guān)系，而的關(guān)系，而P5只能放在只能放在H13上，因?yàn)樗呀?jīng)是海明碼的最上，因?yàn)樗呀?jīng)是海明碼的最高位了。因此，有如下排列關(guān)系：高位了。因此，有如下排列關(guān)系： P5 D8 D7 D6 D5 P4 D

29、4 D3 D2 P3 D1 P2 P1 27對(duì)字節(jié)的海明編碼和校驗(yàn)對(duì)字節(jié)的海明編碼和校驗(yàn) 各個(gè)信息位形成各個(gè)信息位形成Pi 值的偶校驗(yàn)的結(jié)果：值的偶校驗(yàn)的結(jié)果： P1=D1 D2 D4 D5 D7 P2=D1 D3 D4 D6 D7 P3=D2 D3 D4 D8 P4=D5 D6 D7 D8 依據(jù)各信息位形成依據(jù)各信息位形成Pi（i=14）值時(shí)，不同信）值時(shí)，不同信息位出現(xiàn)在息位出現(xiàn)在Pi項(xiàng)中的次數(shù)是不一樣的，其中項(xiàng)中的次數(shù)是不一樣的，其中D4和和D7都出現(xiàn)三次，而都出現(xiàn)三次，而D1、D2、D3、D5、D6、D8僅出現(xiàn)僅出現(xiàn)兩次，為此，還要補(bǔ)充一位兩次，為此，還要補(bǔ)充一位P5校驗(yàn)位，使：校驗(yàn)位

30、，使： P5=D1 D2 D3 D5 D6 D828對(duì)字節(jié)的海明編碼和校驗(yàn)對(duì)字節(jié)的海明編碼和校驗(yàn) (2)校驗(yàn)校驗(yàn) 將接收到的海明碼按如下關(guān)系進(jìn)行偶將接收到的海明碼按如下關(guān)系進(jìn)行偶校驗(yàn)：校驗(yàn)： S1=P1 D1 D2 D4 D5 D7 S2=P2 D1 D3 D4 D6 D7 S3=P3 D2 D3 D4 D8 S4=P4 D5 D6 D7 D8 S5=P5 D1 D2 D3 D5 D6 D8 校驗(yàn)得到的結(jié)果值校驗(yàn)得到的結(jié)果值S5S1（指誤字），（指誤字），它能反映它能反映13位海明碼的出錯(cuò)情況：位海明碼的出錯(cuò)情況：29對(duì)字節(jié)的海明編碼和校驗(yàn)對(duì)字節(jié)的海明編碼和校驗(yàn) 當(dāng)當(dāng)S5S1為為00000時(shí)，

31、表明無(wú)錯(cuò)時(shí)，表明無(wú)錯(cuò)。 當(dāng)當(dāng)S5S1中僅有一位不為中僅有一位不為0，表明是某一校驗(yàn)位，表明是某一校驗(yàn)位出錯(cuò)或三位海明碼（包括信息位和校驗(yàn)位）同時(shí)出錯(cuò)或三位海明碼（包括信息位和校驗(yàn)位）同時(shí)出錯(cuò)。出錯(cuò)。 當(dāng)當(dāng)S5S1中有兩位不為中有兩位不為0，表明是兩位海明碼同，表明是兩位海明碼同時(shí)出錯(cuò)，此時(shí)只能發(fā)現(xiàn)錯(cuò)誤，而無(wú)法確定出錯(cuò)的時(shí)出錯(cuò)，此時(shí)只能發(fā)現(xiàn)錯(cuò)誤，而無(wú)法確定出錯(cuò)的位置。位置。 當(dāng)當(dāng)S5S1中中有三位不為有三位不為0，表明是一位信息位出，表明是一位信息位出錯(cuò)或三位校驗(yàn)位同時(shí)出錯(cuò)，出錯(cuò)位的位號(hào)由錯(cuò)或三位校驗(yàn)位同時(shí)出錯(cuò)，出錯(cuò)位的位號(hào)由S4S1四位編碼值指明四位編碼值指明，此時(shí)不僅能檢查出一位錯(cuò)，而，此時(shí)不僅能檢查出一位錯(cuò)，而且能準(zhǔn)確地定位，因此可以糾正