工業(yè)大學(xué)計算機(jī)網(wǎng)絡(luò)(第五版)海明碼教學(xué)課件.ppt

1、1、差錯編碼理論,目的：,確保幀可靠地交付接收方,基本方法：,發(fā)送方必須在數(shù)據(jù)塊中加入一些冗余信息，使數(shù)據(jù)塊中的各個比特之間建立某種形式的關(guān)聯(lián)，接收端通過驗證這種關(guān)聯(lián)關(guān)系是否存在，來判斷數(shù)據(jù)傳輸過程是否出錯,差錯編碼,兩種差錯編碼策略：,糾錯碼,檢錯碼,差錯檢測 海明距離：兩個碼字中對應(yīng)不同位的個數(shù) 例如： A：10001001 B：10110001 則碼字A與B的海明距離為3,碼字A必須錯3個比特才能變成碼字B,編碼集的海明距離：,在一個有效的編碼集中，任意兩個碼字的海明距離的最小值 稱為該編碼集的海明距離,推論1：,如果要能檢測出d個錯誤，則編碼集的海明距離至少應(yīng)為d+1,差錯糾正,例如：

2、 某編碼集只有4個有效碼字 碼字A：000000 碼字B：000111 碼字C：111000 碼字D：111111 在接收端受到碼字為010111 分析： 海明距離為3 A：錯4比特 B：錯1比特 C：錯5比特 D：錯2比特 可知：由B出錯的概率最大 因此：接收端恢復(fù)為000111,糾錯是將無效碼字恢復(fù)成距離它最近的有效碼字，并非100%正確,推論2,如果要糾正d個錯誤，則編碼集的海明距離至少應(yīng)為2d+1,總結(jié)：,檢/糾錯碼的檢/糾錯能力與編碼集的海明距離有關(guān)， 海明距離越大，檢/糾錯能力就越強(qiáng)， 但所需的冗余信息就越多，編碼效率就越低,2、差錯控制的策略,前向糾錯,自動重發(fā)請求,糾錯碼，用于

3、沒有反饋信道的單工通信,檢錯碼,3、海明碼,基本思想：,n(碼字）=k(信息比特）+r（校驗比特）,沒有出錯的話，這r個校正因子都為0；如果有一個錯誤，這r個校正 因子不會全為0，根據(jù)校正因子的不同取值，可以知道錯誤發(fā)生在碼字 的哪一個位置上。,每個校驗比特與某幾個特定的信息比特構(gòu)成偶校驗的關(guān)系。,接收端對這r個奇偶關(guān)系進(jìn)行校驗，得到校正因子,將每個校驗比特和與它關(guān)聯(lián)的信息比特進(jìn)行相加的結(jié)果稱為校正因子,海明碼只能糾正1比特的錯,糾正單比特錯至少滿足的條件： n+1=3,以7-4海明碼為例：,步驟一：,信息比特和校驗比特的位置關(guān)系,I4 I3 I2 r2 I1 r1 r0 7 6 5 4 3

4、2 1,2k位置為校驗比特,步驟二：,每個信息比特的位置寫成2的冪次之和的形式,7=22+21+20 6=22+21 5=22+20 3=21+20,步驟三：,r2 = I4+I3+I2 r1 = I4+I3 +I1 r0 =I4+I2+I1,計算校驗比特,步驟四：,計算校正因子,S2=r2+ I4+I3+I2 S1=r1 + I4+I3 +I1 S0=r0 +I4+I2+I1,結(jié)論：,如果沒有錯，校正因子都為0 如果校正因子不全為0，則有錯，錯誤的位置 在S=S2S1S0處，將該比特取反的正確數(shù)據(jù),海明碼舉例1： 已知信息I=1001，采用7-4海明碼，則發(fā)送的碼字為什么？ 解：,I4 I3

5、 I2 r2 I1 r1 r0 6 5 4 3 2 1 1 0 0 1 信息比特,r2 = I4+I3+I2 =1+0+0=1 r1 = I4+I3 +I1=1+0+1=0 r0 =I4+I2+I1=1+0+1=0 冗余信息,發(fā)送的碼字信息為：1001100,海明碼舉例2： 某接收端收到的碼字為1011011，問收到的信息是否正確？ 解：,I4 I3 I2 r2 I1 r1 r0 6 5 4 3 2 1 0 1 0 信息比特 1 1 1 冗余比特,S2=r2+ I4+I3+I2= 1+1+0+1=1 S1=r1 + I4+I3 +I1=1+1+0+0=0 S0=r0 +I4+I2+I1=1+1

6、+1+0=1,三個矯正因子不全為0，說明碼字有錯，錯誤的位置：S=S2S1S0 即將第5個比特位置上的1變?yōu)?,Error-Correcting Codes,Use of a Hamming code to correct burst errors.,編碼思想：將位串看成系數(shù)為0或1的多項式 舉例： 二進(jìn)制比特流：1011001 對應(yīng)的多項式：X6+X4+X3+1 推論： 1）以k個信息比特為系數(shù)構(gòu)成的多項式稱為信息多項式K（X），最高次冪為K-1 2）以r個冗余比特為系數(shù)構(gòu)成的多項式為冗余多項式R（X），其最高冪次為r-1 3）在K個信息比特后加上r個冗余比特構(gòu)成的碼字所對應(yīng)的多項式P(X)

7、稱為碼多項式： P（X）=Xr*K（X）+R（X）,4、CRC（循環(huán)冗余碼/多項式編碼）,檢錯思想：收發(fā)雙方約定一個生成多項式G(x)（其最高階和最低階系數(shù)必須為1），發(fā)送方在幀的末尾加上校驗和，使帶校驗和的幀的多項式能被G(x)整除；接收方收到后，用G(x)除多項式，若有余數(shù)，則傳輸有錯。 校驗和計算算法 步驟一： 若G(x)為r階，原幀為m位，其多項式為M(x)，則在原幀后面添加r個0，幀成為n+r位，相應(yīng)多項式xr M(x) 步驟二： 按模2除法用對應(yīng)于G(x)的位串去除對應(yīng)于xr M(x) 的位串,步驟三： 按模2減法從對應(yīng)于Xr M(X) 的位串中減去余數(shù)，結(jié)果就是要傳送的帶校驗和的

8、幀的多項式T(X) T(X) = Xr M(x) + Xr M(X) MOD2 G(X) ,Calculation of the polynomial code checksum,CRC編碼方法舉例： G（X）=X4+X+1，欲發(fā)送的信息為10110011，問在線路上傳輸?shù)拇a字為什么？,所加的冗余為的個數(shù)r=生成多項式的最高次冪,模2運算,當(dāng)出現(xiàn)差錯的碼的多項式能被G（X）整除時， 錯誤就檢測不出來， CRC不能保證檢測出所有的錯誤,Building Blocks For CRC,Exclusive or,Shift registor a shows status before shift b shows status after shift Output same as top bit,Example Of CRC Hardware,Computes 16-bit CRC Registers initialized to zero Bits of message shifted in CRC found in re