數(shù)字通訊的錯(cuò)誤檢測(cè)與糾正課件

錯(cuò)誤檢測(cè)與糾正1錯(cuò)誤類(lèi)型 錯(cuò)誤多比特錯(cuò)誤突發(fā)錯(cuò)誤單比特錯(cuò)誤1.1單比特錯(cuò)誤

單比特錯(cuò)誤是指在給定數(shù)據(jù)單元（例如一個(gè)字節(jié)，一個(gè)字符，數(shù)據(jù)單元，或是數(shù)據(jù)包）中只有一個(gè)比特被從0變?yōu)?或是從1變?yōu)?。0變到1發(fā)送接收00000100000011001.3突發(fā)錯(cuò)誤突發(fā)錯(cuò)誤指數(shù)據(jù)單元中兩個(gè)或兩個(gè)以上連續(xù)的比特從0變?yōu)?或是從1變?yōu)?。01000010010001010101110101000101突發(fā)錯(cuò)誤發(fā)送接收2錯(cuò)誤檢測(cè)2.1冗余

在數(shù)據(jù)通信中采用四種類(lèi)型的冗余校驗(yàn)技術(shù)：垂直冗余校驗(yàn)（VRC）（也稱(chēng)為奇偶校驗(yàn)），縱向冗余校驗(yàn)（LRC），和循環(huán)冗余校驗(yàn)（CRC），是在物理層實(shí)現(xiàn)而在數(shù)據(jù)鏈路層被使用的。而第四種技術(shù)，校驗(yàn)和技術(shù)，主要由網(wǎng)絡(luò)層，包括國(guó)際互連網(wǎng)，所使用，而在傳輸層實(shí)現(xiàn)的。校驗(yàn)方法檢驗(yàn)和循環(huán)冗余校驗(yàn)縱向冗余校驗(yàn)垂直冗余校驗(yàn)2.2垂直冗余碼校驗(yàn)

在錯(cuò)誤檢測(cè)中最常用和費(fèi)用最低的方法是垂直冗余校驗(yàn)（VRC），又常稱(chēng)作奇偶校驗(yàn)。在垂直冗余校驗(yàn)（VRC）中，在每一個(gè)數(shù)據(jù)單元上都增加一個(gè)校驗(yàn)位，從而使得1的總數(shù)（包括校驗(yàn)位）對(duì)于偶校驗(yàn)來(lái)說(shuō)是偶數(shù)，或?qū)τ谄嫘ｒ?yàn)來(lái)說(shuō)是奇數(shù)。偶校驗(yàn)生成1校驗(yàn)函數(shù)1的總數(shù)是偶數(shù)嗎？1數(shù)據(jù)VRC接收方可靠性：

垂直冗余校驗(yàn)（VRC）可以檢測(cè)所有單位比特錯(cuò)誤。只要發(fā)生錯(cuò)誤的比特?cái)?shù)是奇數(shù)（1，3，5等等），該技術(shù)也可以檢測(cè)出多比特錯(cuò)誤和突發(fā)錯(cuò)誤。缺點(diǎn)：但當(dāng)發(fā)生錯(cuò)誤的個(gè)數(shù)是偶數(shù)時(shí)，它就不能檢測(cè)出多比特和突發(fā)錯(cuò)誤?？煽啃?/p>

LRC技術(shù)極大地提高了發(fā)現(xiàn)多比特錯(cuò)誤和突發(fā)錯(cuò)誤的可能性。但是，有一種類(lèi)型的錯(cuò)誤仍然會(huì)被遺漏。如果在某個(gè)數(shù)據(jù)單元中的兩個(gè)比特被破壞，同時(shí)在另一個(gè)數(shù)據(jù)單元中正好相同位置的兩個(gè)比特也被破壞，那么LRC校驗(yàn)器就檢測(cè)不出這種錯(cuò)誤。2.4循環(huán)冗余碼校驗(yàn)第三種也是最有效的一種冗余校驗(yàn)技術(shù)就是循環(huán)冗余校驗(yàn)（CRC）。和基于加法的VRC及LRC技術(shù)不同，循環(huán)冗余校驗(yàn)（CRC）是基于二進(jìn)制除法的。00…0數(shù)據(jù)除數(shù)nbitn+1bit余數(shù)nbit循環(huán)冗余碼數(shù)據(jù)除數(shù)余數(shù)0，接收非0，拒絕數(shù)據(jù)發(fā)送方接收方

可靠性：除了正好數(shù)據(jù)塊的比特值是按除數(shù)值變化的錯(cuò)誤外，循環(huán)冗余校驗(yàn)（CRC）將檢測(cè)出其他所有錯(cuò)誤。甚至對(duì)于上面所提到的四比特錯(cuò)誤，這種情況發(fā)生的可能性仍然是很小的。而且，常用的CRC除數(shù)通常有13，17，或是33個(gè)比特，使得不可檢測(cè)的錯(cuò)誤可能降低到幾乎近于零。3錯(cuò)誤糾正

錯(cuò)誤糾正可以通過(guò)兩種方式進(jìn)行。一種方式是當(dāng)發(fā)現(xiàn)錯(cuò)誤時(shí)，接收方可以讓發(fā)送方重新發(fā)送整個(gè)數(shù)據(jù)單元。另一種方法是可以采用錯(cuò)誤糾正碼，自動(dòng)糾正一些錯(cuò)誤。理論上，可以自動(dòng)糾正任何一種二進(jìn)制編碼錯(cuò)誤。但是錯(cuò)誤糾正碼比錯(cuò)誤檢測(cè)碼要復(fù)雜得多，并且需要占據(jù)更多的冗余比特位。糾正多比特錯(cuò)誤和突發(fā)錯(cuò)誤所需要的比特位數(shù)是如此巨大，因此在大多數(shù)情況下這樣做是十分低效的。因此，大多數(shù)錯(cuò)誤糾正技術(shù)都局限于一個(gè)，兩個(gè)，或是三個(gè)比特錯(cuò)誤。3.1單比特錯(cuò)誤糾正實(shí)現(xiàn)錯(cuò)誤糾正，必須知道錯(cuò)誤的比特位。所以，錯(cuò)誤糾正的訣竅在于對(duì)非法比特或比特組的定位。3.2海明碼1.為冗余比特定位一個(gè)七位的ASCⅡ碼需要在數(shù)據(jù)單元末尾附加或者在原始數(shù)據(jù)中間插入四個(gè)冗余比特。在圖9-18中，這些比特放在位置1，2，4和8上（這些都是在11比特位中的2的指數(shù)序數(shù)）。為清楚表明下面的例子，我們將它們稱(chēng)為r1,r2,r4,以及r8。ddrdrddrdrd1110987654321冗余bit圖9-18在海明碼中冗余比特的位置

R2與這些bit有關(guān)dddddddR8R1R4R2R4與這些bit有關(guān)

7564dddddddR8R1R4R2

0111010101100100R8與這些bit有關(guān)11910

8dddddddR8R1R4R2101110011010

10001193762101110100011011101100010

數(shù)據(jù)：10011011191037568142數(shù)據(jù)加入r1加入r2加入r4加入r81001101110011011100110110011011191037568142119103756814211910375681421191037568142編碼：10011100101000001113.錯(cuò)誤檢測(cè)與糾正現(xiàn)在假設(shè)在上述傳輸被接收時(shí)，第7位從1變成了0

接收方接收該傳輸并采用與發(fā)送方計(jì)算每個(gè)冗余比特時(shí)相同的比特組合來(lái)重新為每一個(gè)組計(jì)算新的VRC校驗(yàn)位。然后將新的校驗(yàn)位置按照冗余比特位置（r8,r4,r2,

r1)排列成一個(gè)二進(jìn)制數(shù)。在本例中。這一步就得出結(jié)果