數(shù)據(jù)鏈路層(錯誤檢測與糾正)

數(shù)據(jù)鏈路層(錯誤檢測與糾正)第一頁，共23頁。奇偶校驗碼

奇偶校驗碼是一種通過增加冗余位使得碼字中“１”的個數(shù)為奇數(shù)或偶數(shù)的編碼方法，它是一種檢錯碼。一個二進制碼字，如果它的碼元有奇數(shù)個1，就稱之為具有奇性。對于一個n位字，奇性=a0⊕a1⊕a2⊕…⊕an。很明顯，用同樣的方式，也能夠根據(jù)每一個碼字的零的個數(shù)來構(gòu)成奇偶校驗。單個的奇偶校驗碼可描述為：給每一個碼字加一個校驗位，用它來構(gòu)成奇性或偶性校驗。因此，若有一個碼元是錯的，就可以分辨得出。在一個傳輸系統(tǒng)里，傳輸以前，由奇偶發(fā)生器把奇偶校驗位加到每個字中。原有信息中的數(shù)字在接收機中被檢測，如果沒有出現(xiàn)正確的奇、偶性，這個信息標(biāo)定為錯誤的，這個系統(tǒng)將把錯誤的字拋掉或者請求重發(fā)。注意，用單個的奇偶校驗碼僅能檢出奇數(shù)個碼元的錯誤。奇偶校驗可以用在數(shù)字系統(tǒng)的主要接口設(shè)備中，由于在每個信息中增加了冗余度，僅當(dāng)出現(xiàn)錯誤的概率和錯誤的危害足夠大時，才采用奇偶校驗碼。在實際的應(yīng)用中，按碼字的形成方向可以分為垂直奇偶校驗、水平奇偶校驗和垂直水平奇偶校驗三種奇偶校驗方式。第二頁，共23頁。垂直奇偶校驗

垂直奇偶校驗又稱縱向奇偶校驗，它能檢測出每列中所有奇數(shù)個錯，但檢測不出偶數(shù)個的錯，如圖2-23所示，因而對差錯的漏檢率接近1/2。位\數(shù)字0123456789C10101010101C20011001100C30000111100C40000000011C51111111111C61111111111C70000000000偶C00110100110奇1001011001圖2-23垂直奇偶校驗方式第三頁，共23頁。水平奇偶校驗

水平奇偶校驗又稱橫向奇偶校驗，它不但能檢測出各段同一位上的奇數(shù)個錯，而且還能檢測出突發(fā)長度<=p的所有突發(fā)錯誤，如圖2-24所示。其漏檢率要比垂直奇偶校驗方法低，但實現(xiàn)水平奇偶校驗時，一定要使用數(shù)據(jù)緩沖器。位\數(shù)字0123456789偶校驗C101010101011C200110011000C300001111000C400000000110C511111111111C611111111111C700000000000圖2-24水平奇偶校驗方式第四頁，共23頁。水平垂直校驗

水平垂直校驗(LRC)又叫報文校驗、方塊校驗。這種方法是在奇偶校驗的基礎(chǔ)上，為了提高奇偶校驗碼對突發(fā)錯誤的檢測能力，將若干奇偶校驗碼排成若干行，然后對每列進行奇偶校驗，放在最后一行，該檢驗字符的編碼方法是使每一位縱向代碼中1的個數(shù)成為奇數(shù)(或偶數(shù))。傳輸時按照列順序進行傳輸，在一批字符傳送之后，另外增加一個檢驗字符，在接收端又按照行的順序檢驗是否存在差錯。由于突發(fā)錯誤是成串發(fā)生的，經(jīng)過這樣的傳輸后錯誤被分散了。它能檢測出所有3位或3位以下的錯誤、奇數(shù)個錯、大部分偶數(shù)個錯以及突發(fā)長度<=p+1的突發(fā)錯，如圖2-25所示。可使誤碼率降至原誤碼率的百分之一到萬分之一，還可以用來糾正部分差錯，有部分偶數(shù)個錯不能測出。它適用于中、低速傳輸系統(tǒng)和反饋重傳系統(tǒng)。圖2-25水平垂直奇偶校驗方式第五頁，共23頁。恒比碼

碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼?！昂惚却a”僅是單個奇偶校驗的推廣。五中取三的恒比碼常常用于傳輸二進形式的十進數(shù)。如我國郵電部門使用的五單位數(shù)字保護電報碼，就是一種五中取三的恒比碼，編碼方式見圖2-26所示。在這種表示方法中采用8-4-2-1的權(quán)數(shù)來表示十進數(shù)，然后選擇所增加的恒比位使每個字恰好有兩個0和三個1。當(dāng)接收到的任何信息其1的個數(shù)少于三或多于三，就可以知道這個信息是錯誤的。恒比碼能夠檢測出全部的單一錯誤和40%的兩個錯誤。數(shù)字編碼數(shù)字編碼101011610101211001711100310110801110411010910011500111001101圖2-26五中取三恒比碼第六頁，共23頁。循環(huán)冗余檢驗的原理在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循環(huán)冗余檢驗CRC的檢錯技術(shù)。假設(shè)待傳送的數(shù)據(jù)M=1010001101（共kbit）。我們在M的后面再添加供差錯檢測用的nbit冗余碼一起發(fā)送。第七頁，共23頁。冗余碼的計算用二進制的模

2

運算進行2n乘M的運算，這相當(dāng)于在M后面添加n個0。得到的(k+n)bit的數(shù)除以事先選定好的長度為(n+1)bit的數(shù)P，得出商是Q而余數(shù)是R，余數(shù)R比除數(shù)P至少要少1個比特。第八頁，共23頁。冗余碼的計算舉例設(shè)n=5,P=110101，模2運算的結(jié)果是：商Q=1101010110，余數(shù)R=01110。將余數(shù)R作為冗余碼添加在數(shù)據(jù)M的后面發(fā)送出去，即發(fā)送的數(shù)據(jù)是1110，或2nM+R。第九頁，共23頁。

1101010110

←

Q

商

除數(shù)

P→

1101011000

←

2nM被除數(shù)

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余數(shù)循環(huán)冗余檢驗的原理說明第十頁，共23頁。幀檢驗序列FCS在數(shù)據(jù)后面添加上的冗余碼稱為幀檢驗序列FCS(FrameCheckSequence)。循環(huán)冗余檢驗CRC和幀檢驗序列FCS并不等同。CRC是一種常用的檢錯方法，而FCS是添加在數(shù)據(jù)后面的冗余碼。FCS可以用CRC這種方法得出，但CRC并非用來獲得FCS的惟一方法。

第十一頁，共23頁。檢測出差錯只要得出的余數(shù)R不為0，就表示檢測到了差錯。但這種檢測方法并不能確定究竟是哪一個或哪幾個比特出現(xiàn)了差錯。一旦檢測出差錯，就丟棄這個出現(xiàn)差錯的幀。只要經(jīng)過嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù)P，那么出現(xiàn)檢測不到的差錯的概率就很小很小。第十二頁，共23頁。應(yīng)當(dāng)注意僅用循環(huán)冗余檢驗CRC差錯檢測技術(shù)只能做到無差錯接受(accept)?！盁o差錯接受”是指：“凡是接受的幀（即不包括丟棄的幀），我們都能以非常接近于

1

的概率認(rèn)為這些幀在傳輸過程中沒有產(chǎn)生差錯”。也就是說：“凡是接受的幀都沒有傳輸差錯”（有差錯的幀就丟棄而不接受）。要做到“可靠傳輸”（即發(fā)送什么就收到什么）就必須再加上確認(rèn)和重傳機制。第十三頁，共23頁。海明碼的實現(xiàn)和特點海明碼：海明碼是一種可以糾正一位差錯的編碼。它是利用在信息位為k位，增加r位冗余位，構(gòu)成一個n=k+r位的碼字，然后用r個監(jiān)督關(guān)系式產(chǎn)生的r個校正因子來區(qū)分無錯和在碼字中的n個不同位置的一位錯。它必需滿足以下關(guān)系式：

２r>=n+1

或

2r>=k+r+1

海明碼的編碼效率為：

R=k/(k+r)

式中k為信息位位數(shù)，r為增加冗余位位數(shù)

第十四頁，共23頁。UseofaHammingcodetocorrectbursterrors第十五頁，共23頁。已知：信息碼為："0010"。海明碼的監(jiān)督關(guān)系式為：

S2=a2+a4+a5+a6

S1=a1+a3+a5+a6

S0=a0+a3+a4+a6

求：海明碼碼字。

1)由監(jiān)督關(guān)系式知冗余碼為a2a1a0。

2)冗余碼與信息碼合成的海明碼是："0010a2a1a0"。

設(shè)S2=S1=S0=0,由監(jiān)督關(guān)系式得：

a2=a4+a5+a6=1

a1=a3+a5+a6=0

a0=a3+a4+a6=1

因此，海明碼碼字為："0010101"第十六頁，共23頁。已知：海明碼的監(jiān)督關(guān)系式為：

S2=a2+a4+a5+a6

S1=a1+a3+a5+a6

S0=a0+a3+a4+a6

接收碼字為：“0011101”(n=7)

求：發(fā)送端的信息碼。

1)由海明碼的監(jiān)督關(guān)系式計算得S2S1S0=011。

2)由監(jiān)督關(guān)系式可構(gòu)造出下面錯碼位置關(guān)系表：3)由S2S1S0=011查表得知錯碼位置是a3。

4)糾錯--對碼字的a3位取反得正確碼字："0010101"

5)把冗余碼a2a1a0刪除得發(fā)送端的信息碼："0010"

第十七頁，共23頁。已知：信息碼為：“11001100”

(k=8)

求：海明碼碼字。1)把冗余碼A、B、C、…，順序插入信息碼中，得海明碼

碼字:“AB1C100D11

0

0”

碼位:

123456789101112

其中A,B,C,D分別插于2k位(k=0,1,2,3)。碼位分別為1,2,4,8。2)冗余碼A,B,C,D的線性碼位是：(相當(dāng)于監(jiān)督關(guān)系式)

A->1,3,5,7,9,11；

B->2,3,6,7,10,11；

C->4,5,6,7,12；(注5=4+1；6=4+2；7=4+2+1；12=8+4)

D->8,9,10,11,12。

第十八頁，共23頁。3)把線性碼位的值的偶校驗作為冗余碼的值(設(shè)冗余碼初值為0)：

A=∑(0,1,1,0,1,0)=1

B=∑(0,1,0,0,1,0)=0

C=∑(0,1,0,0,0)

=1

D=∑(0,1,1,0,0)

=0

4)海明碼為:"101110001100"第十九頁，共23頁。已知：接收的碼字為：“100110001100”(k=8)

求：發(fā)送端的信息碼。

1)設(shè)錯誤累加器(err)初值=0

2)求出冗余碼的偶校驗和，并按碼位累加到err中：

A=∑(1,0,1,0,1,0)=1err=err+20=1

B=∑(0,0,0,0,1,0)=1err=err+21=3

C=∑(1,1,0,0,0)=0err=err+0=3

D=∑(0,1,1,0,0)=0er