數(shù)據(jù)通訊與計算機網(wǎng)絡(luò)-差錯檢測與糾正

差錯檢測與糾正

差錯的分類

單比特錯

在一個數(shù)據(jù)單元中僅1個比特出現(xiàn)差錯。

突發(fā)差錯在一個數(shù)據(jù)單元中多于1個比特出現(xiàn)差錯。為檢測或糾正差錯，除數(shù)據(jù)之外，需提供額外的若干比特，連同原數(shù)據(jù)一并發(fā)送。

冗余編碼

差錯檢測與差錯糾正

前向差錯糾正vs.重發(fā)糾正

冗余編碼對模N運算，只使用0到N-1之間的N個整數(shù)。

模N運算模2運算=XOR模2加法=模2減法模2加結(jié)果中的“1”的個數(shù)是兩個碼字中對應(yīng)位不同的位數(shù)。

分組編碼:定長的比特組作為編碼單元原始的數(shù)據(jù)比特組稱為數(shù)據(jù)字（dataword）根據(jù)數(shù)據(jù)字，計算出r個的冗余比特，產(chǎn)生長度為n=k+r比特的碼字（codeword:C(n,k)。8B/10B分組碼：C(10，8)，即k=8，n=10。有2k=28=256個數(shù)據(jù)字，2n=210=1024個碼字。1024個碼字中的256個碼字用于表示原始數(shù)據(jù)字，其余768個碼字作為禁用碼字（及一些狀態(tài)字或控制字）。例10.1

差錯檢測

接收方知道哪些碼字是“準用碼字”;

接收方收到“禁用碼字”，丟棄。例10.2(奇偶校驗碼,d=2)sent011receive011OKgetdataword01fromitsent011receive111Errordiscardsent011receive000OK/Errorgetdataword00fromit

差錯糾正例10.3假設(shè)收到的碼字最多出現(xiàn)1比特錯，

發(fā)送01011收到01001發(fā)現(xiàn)有差錯：

01001+00000=010012bits不同

01001+01011=000101bit不同，

恢復(fù)為0101101001+10101=111003bits不同

01001+11110=101114bits不同(漢明碼,d=3)兩個碼字的漢明距離是對應(yīng)位上數(shù)字不同的位數(shù)。

漢明距離例10.4漢明距離d(10101,11110)＝3漢明距離d(000,011)＝21.2.最小漢明距離是一個碼字集中所有碼字間漢明距離的最小值。

最小漢明距離解：例10.5最小漢明距離dmin＝2。求前面例10.2的碼字集的最小漢碼距離。解：例10.6

檢測、糾錯能力同漢明距離的關(guān)系求前面例10.3的碼字集的最小漢碼距離。最小漢明距離dmin＝3。要保證能檢測出s位以內(nèi)的差錯，碼字集的最小漢明距離須滿足：dmin=s+1.設(shè)碼字x同碼字y的碼距為s+1。則碼字x出現(xiàn)1~s位的錯碼時，將不會錯成準用碼字y(即不會超出x為圓心，s為半徑的圓)，由此可檢測出差錯。（但不能糾錯，因無法判定錯碼是來自x還是來自y。）設(shè)碼字x同碼字y的碼距為2t+1,則碼字x或y出現(xiàn)1~t位的錯碼時,將不會超出各自碼字為圓心，t為半徑的圓，即不會由其它準用碼字所錯成,由此可判定差錯碼字應(yīng)恢復(fù)為哪一個準用碼字(糾正1~t位錯)。要保證能糾正t位以內(nèi)的差錯，碼字集的最小漢明距離須滿足：dmin=2t+1.為要糾正t位錯碼,并能檢測s位錯碼

(s>t)，碼字集的最小漢明距離須滿足：

d>=s+t+1tts1xy含義：若接收碼字中的差錯位數(shù)不大于t，可自行糾正；若大于t，但不大于s，可檢測出來（但不能糾正）分析：要能糾正t位錯碼，要求x～y的碼距d>=2t+1；

要能檢測s位錯碼，要求x至y的糾錯圓距離d’>=s+1(即x出現(xiàn)s位錯時，不落入y的糾錯圓內(nèi)，不被糾正為碼字y)

兩個要求合并為：要求碼距d>=s+t+1。某碼字集的最小漢明距離dmin=4。該碼字集的檢錯能力和糾錯能力各為多大?由d=s+1，s=d-1=4-1=3，該碼字集能檢測3比特以內(nèi)的差錯。

由d=2t+1，t=(d-1)/2=3/2=1.5，該碼字集能糾正1比特差錯。

由d=s+t+1,s>t，該碼字集能同時進行檢測和糾正：檢測2比特差錯，糾正1比特差錯。例10.9解：在線性分組碼的碼字集中，任何兩個準用碼字的“XOR”結(jié)果是該碼字集中的另一個準用碼字。對線性分組碼的碼字集，dmin

是該碼字集中非全0的準用碼字中具有最少個“1”的準用碼字所含有“1”的位數(shù)。

線性分組碼的性質(zhì)前例10.2,例10.3：d=2d=3

一維奇偶校驗碼（simpleparity-checkcode）r0=∑ai(modulo-2)s0=(∑ai)+r0(modulo-2)r0取“0/1”值，使am-1am-2…a1a0r0中的“1”數(shù)目為偶數(shù)。偶校驗：示例：偶校驗碼C(5,4)一維奇偶校驗碼為c(n，n-1)，dmin=2，具有1比特的檢錯能力。（實際上，一維奇偶校驗碼能夠檢測任何奇數(shù)位差錯。）二維奇偶校驗碼

漢明糾錯編碼2m>=k+m+1(為糾1bit錯)檢測編碼的關(guān)鍵是確定差錯比特的位置。為能定位c(n,k)中單個差錯比特的位置，冗余碼必須能夠表示

n+1個狀態(tài)：在第j位的差錯，j=1,2,…,n；無差錯。對c(n,k)，n=k+m，則m比特的冗余碼需滿足：kmn=k+m123235336437549641074112m>=k+m+1(為糾1bit錯)r0=(∑ai)set/0r1=(∑ai)set/1

ri=(∑ai)set/i

rm-1=(∑ai)set/m-1

s0=r0+(∑ai)set/0s1=r1+(∑ai)set/1

si=ri+(∑ai)set/i

sm-1=rm-1+(∑ai)set/m-1

若僅1個ri

錯，監(jiān)督字“sm-1sm-2…s1s0”的值必為1,2,4,8,…。方案設(shè)計原則：選各Seti,使任1個“ai”錯時，產(chǎn)生的監(jiān)督字“sm-1sm-2…s1s0”的值相異，且不為1、2、4、8、…..。r3=a4r2=(a3

a2

a1)r1=(a3

a2

a0)r0=(a4

a3

a1a0)發(fā)送端校驗碼漢明糾錯編碼規(guī)則：由各個ak產(chǎn)生不同的監(jiān)督字S。接收端監(jiān)督碼a4a3a2a1a0rSvr3s3（8）vvvr2s2（4）Vvvr1s1（2）vvvvr0s0（1）S值：

97653

8421s3=r3

a4s2=r2

(a3

a2

a1)s1=r1

(a3

a2

a0)s0=r0(a4

a3

a1a0)對各ai

參與的運算集可有多種選擇，只須保證各自產(chǎn)生的S值不同。(某1bit錯，產(chǎn)生的S值)若接收無差錯，S3S2S1S0=00000若a0出錯，改變S1,S0S3S2S1S0=00113若a1出錯，改變S2,S0S3S2S1S0=01015若a2出錯，改變S2,S1S3S2S1S0=01106若a3出錯，改變S2,S1’S0S3S2S1S0=01117若a4出錯，改變S3,

S0S3S2S1S0=10019若r3出錯，改變S3

S3S2S1S0=10008若r2出錯，改變S2S3S2S1S0=01004若r1出錯，改變S1S3S2S1S0=00102若r0出錯，改變S0S3S2S1S0=00011r3=a4r2=(a3

a2

a1)r1=(a3

a2

a0)r0=(a4

a3

a1a0)s3=r3

a4s2=r2

(a3

a2

a1)s1=r1

(a3

a2

a0)s0=r0(a4

a3

a1a0)發(fā)送端校驗碼接收端監(jiān)督碼漢明糾錯編碼的譯碼器(基于前面的具體方案)：9

87654

3

2104-16譯碼器a4a3a2a1r3r2r0S2S3a0r1S0a4,a3,a1,a0S1a4a3a2a1a0s3=r3

a4s2=r2

(a3

a2

a1)s1=r1

(a3

a2

a0)s0=r0(a4

a3

a1a0)使用漢明編碼糾正多位差錯循環(huán)碼是線性分組碼，并具有性質(zhì)：在一個循環(huán)碼字集中，任何碼字的循環(huán)移位的結(jié)果是該碼字集中的另一個碼字。

示例：CRC碼字集C(7,4)(3個“1”,4個“1”,全“0”,全“1”)CRC編碼與解碼CRC編碼運算CRC解碼運算CRC除法運算的硬件構(gòu)成1/0CRC編碼器的除法運算過程CRC編碼器的移位寄存器實現(xiàn)若除數(shù)某位為0，則無該位對應(yīng)的異或門(及異或門上端紅色連線)。polynomials（多項式）多項式加法和減法多項式乘法和除法(x5+x3)+(x6+x5)=x6+x3加法=減法10011左移3bit:1001100010011右移3bit:10(x4+x+1)x3=x7+x4+x3(x4+x+1)/x3=xCRC的多項式除法InreceivedCRCcode,Ifs(x)≠0,error；Ifs(x)=0,

eithernoerrororerror,butfailedtodetect.CRC編碼分析數(shù)據(jù)字d(x)CRC碼字c(x)除式g(x)編碼余數(shù)r(x)差錯模式e(x)解碼余數(shù)s(x)能被g(x)整除的e(x)所對應(yīng)的差錯模式被漏檢。c(x)/g(x)=[xn-kd(x)+r(x)+e(x)]/g(x)=[xn-kd(x)]/g(x)+r(x)/g(x)+e(x)/g(x)=[q(x)+r(x)/g(x)]+r(x)/g(x)+e(x)/g(x)=q(x)+e(x)/g(x)設(shè)計g(x)，使盡可能多的e(x)不能被g(x)整除。數(shù)據(jù)字d(x)CRC碼字c(x)除式g(x)編碼余數(shù)r(x)差錯模式e(x)解碼余數(shù)s(x)如果g(x)多于1項，且x0系數(shù)為1，則所有的單比特差錯均能被檢測出來。1.單比特差錯討論下述g(x)對單比特差錯的檢測能力。a.x+

1

b.x3

c.1a.單比特差錯模式為e(x)=xi。任何xi不能被x+1整除，所以x+1可檢測任何單比特差錯。b.如果“i”大于或等于,xi能被x3整除。所有在位置0～2的單比特差錯能被檢測出來。c.任何xi

能被1整除。該g(x)不能作為除數(shù)。解:例10.152.兩個單獨比特差錯如果g(x)不能整除xt+1(t∈1~n–1)，則任何兩比特差錯均能被檢測。差錯模式e(x)=xj+xi=xi(xj-i+1)=xi(xt+1),(t∈1~n–1)討論下述g(x)對兩個單獨比特差錯的檢測能力。

a.x+1b.x4+1c.x7+x6+1d.x15+x14+1a.任何相鄰的兩個比特差錯e(x)=xj+xj-1均能被x+1整除，故該類差錯不能被該g(x)檢測出來。b.任何相鄰4個比特位置的兩比特差錯不能被該g(x)檢測。c.類同于d。d.該除數(shù)g(x)的最高次項為x15。若e(x)=xt+1的最高次t<=15，則e(x)不能被該g(x)整除。一個碼字中的兩個差錯比特只要間隔不大于15位即能被該g(x)檢測出來。例10.16解：含因子x+1的g(x)能夠檢測所有奇數(shù)位差錯。3.奇數(shù)個比特差錯分析：(x+1)與任何多項式的乘積為偶數(shù)項多項式。(x+1)(x3+x+1)=x4+x3+x2+x+x+1=x4+x3+x2+1(x+1)(x3+x)=x4+x3+x2+x(x+1)(x2+x)=x3+x2+x2+x=x3+xK項多項式被x+1乘后為2k項（偶數(shù)項）。若其中有j對同類項，合并后減少2j項（偶數(shù)）。所有差錯長度L≤r的突發(fā)差錯能被檢測。所有差錯長度L=r+1的突發(fā)差錯能以概率1–(1/2)r–1被檢測。所有差錯長度L>r+1的突發(fā)差錯能以概率1–(1/2)r被檢測。4.突發(fā)差錯e(x)=xj+…..+xi=xi(xj-i+…+1)=xi(xL-1+…+1)其中L=差錯長度

取

g(x)=xr+…..+1分析下列g(shù)(x)對不同差錯長度的突發(fā)性差錯的檢測能力。a.x6+1b.x18+x7+x+1c.x32+x23+x7+1a.能夠檢測所有差錯長度L<=6的突發(fā)差錯；檢測差錯長度L=7的突發(fā)差錯的漏檢概率為3%；檢測差錯長度L>=8的突發(fā)差錯的漏檢概率為1.6%解：例10.17b.能夠檢測所有差錯長度L<=18的突發(fā)差錯；檢測差錯長度L=19的突發(fā)差錯的漏檢概率為8×10-6

；檢測差錯長度L>=20的突發(fā)差錯的漏檢概率為4×10-6

。c.能夠檢測所有差錯長度L<=32的突發(fā)差錯；檢測差錯長度L=33的突發(fā)差錯的漏檢概率為5×10-9

；檢測差錯長度L>=34的突發(fā)差錯的漏檢概率為3×10-9

。對高性能g(x)的要求：1.x0

的系數(shù)為1；

2.至少包含三項xr+xk+1；3.包含因子x+1。g(x)多項式標準sender:data={7,11,12,0,6},makesum1=∑{7,11,12,0,6}=36send{7,11,12,0,6,36}

receiver:received{7,11,12,0,6,36}makesum2=∑{7,11,12,0,6}=36comparesthesum2withthesum1

ifthetwoarethesame,noerror;otherwise,error,thedatadiscarded.

校驗和的概念例10.18sender: