一、差錯檢測和糾錯技術簡單介紹

本篇講的差錯檢測和糾錯技術主要是針對比特錯誤。
對一個節點發送到一個相鄰節點的幀，檢測是否出現比特差錯，并糾正。相關技術有很多，下圖為差錯檢測和糾正的過程。

在發送節點，數據D附加若干差錯檢測和糾錯位EDC，一起發送到鏈路。數據D包括網絡層傳來的數據報，以及鏈路級尋址信息、序列號和其他字段。保護范圍包括數據D的所有字段。
接收節點接收比特序列D’和EDC’。接收方利用收到的D’按照規則來計算差錯校驗位EDC，看計算的EDC是否與收到的EDC’相同，相同則無錯誤，不相同則有錯誤。
這里需要說明一下差錯檢測技術和糾正技術不能保證接收方檢測到所有的比特差錯，即可能出現未檢測到的比特差錯，而接收方并未發現。所有我們需要選擇一個合適的差錯檢測方案使未檢測到的情況發生的概率很小即可。
差錯檢測和糾錯技術越好，越復雜，開銷更大。

二、三種主要的差錯檢測技術

（1）奇偶校驗：最基本的方法。
（2）檢查和方法：常用于運輸層。
（3）循環冗余檢測：常用于鏈路層。

1、奇偶校驗

1.1、一比特奇偶校驗

（1）發送方：
在要發送的信息D（d位）后面附加一個奇偶校驗位，發送數據中1的個數是奇數則位奇校驗，否則是偶校驗。

如上圖所示，假設發送數據進行偶校驗，則需要在校驗位補充1以湊成偶數個1。 然后將d+1位數據一起傳輸發送。
（2）接收方：檢測收到的信息（d+1位）中“1”的個數。
若是使用偶校驗：當發現奇數個1時表示至少有一個比特發生差錯（奇數個比特差錯）。
若是使用奇校驗：當發現偶數個1時表示至少有一個比特發生差錯。
我們可以看到不管是奇校驗還是偶校驗都只能查出任意奇數個錯誤，不能發現偶數個錯誤。
若比特差錯概率很小，差錯獨立發生，一比特奇偶校驗可滿足要求。 若差錯集中在一起“突發”，一幀中未檢測到的差錯的概率達到50%。

1.2、二維奇偶校驗

基本思想：
首先將要傳的信息D（d比特）劃分為i行j列，即i個組，每組j位。其次，對每行和每列分別計算奇偶校驗值。最后結果的i+j+1個奇偶比特構成了幀的差錯檢測比特。

如上圖，假設需要發送的數據是10101 11110 01110共15比特。劃分為3組，每組5個比特。分別進行、列偶校驗，校驗碼如上圖。假設在傳輸過程中有一個比特錯誤，例如第二行第二列的1變為0。在接收方進行校驗時會發現第二行和第二列的校驗碼不對，這樣就會發現是第二行第二列的數據發生了錯誤。
因此二維奇偶校驗可以檢測并糾正單個比特差錯，可以檢測但不能糾正分組中任意兩個比特的差錯。

2、檢查和方法

2.1、過程

（1）發送方：首先在發送方將數據的每兩個字節當作一個16位的整數，可分成若干整數。然后將所有16位的整數求和，對得到的和逐位取反，作為檢查和，放在報文段首部，一起發送。
（2）接收方：對接收到的信息（包括檢查和）按與發送方相同的方法求和。若結果全1則表示收到的數據無差錯，若結果中有0表示收到的數據出現差錯。
注意：當數字作加法時，最高位的進位要回加到結果中。
如下例子：

2.2、檢查和特點

（1）分組開銷小：檢查和位數比較少。
（2）差錯檢測能力弱。
（3）適用于運輸層，因為差錯檢測用軟件實現，檢查方法簡單、快速。
（4）鏈路層的差錯檢測由適配器中專用的硬件實現，采用更強的循環冗余檢測方法。

3、循環冗余檢測（CRC）

3.1、檢測過程

這種檢測方法在計算機網絡中廣泛采用。
循環冗余檢測編碼：即多項式編碼，把要發送的比特串看作為系數是0或1的一個多項式，對比特串的操作看作為多項式運算。
例如10111可看作x${}^4$+x${}^2$+x+1。
（1）發送方：首先在發送方計算出一個r位附加比特R，添加到D的后面產生DR（d+r）比特。DR能被生成多項式G模2運算整除，一起發送。

（2）接收方：用生成多項式G去除接收到的DR（d+r）比特。若余數非0則表明傳輸發生差錯；若余數為0表示傳輸正確，去掉尾部r位，得所需數據D。

3.2、模2計算

模2計算：
加法不進位，減法不借位，即操作數的按位異或（XOR）。
乘法和除法與二進制運算類似，其中加法或減法沒有進位或錯位。例如乘以2${}^r$，即比特模式左移r個位置。

3.3、R的計算

計算R的步驟如下：
將數據D后面添加r個0，除以給定的生成多項式G，所得余數即為R（r位），r表示CRC編碼的位數。
設D=101110，d=6，G（生成多項式）=1001，CRC編碼是3比特即生成多項式位數減1。r=3。計算過程為：

最后算出的余數是011，即R。
因此實際傳輸的數據形式是：101110011

3.4、循環冗余碼CRC的特點

生成多項式G的選擇：有8、12、16和32比特生成多項式G。其中8比特的CRC用于保護ATM信元首部；32比特的標準CRC-32用于鏈路級協議。
CRC能檢測小于r+1位的突發差錯、以及任意個奇數個差錯。

總結

以上是生活随笔為你收集整理的差错检测和纠错技术的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。