2。3 差錯檢測
資料傳輸過程中會由於噪聲或者其他因素而出現
差錯
。差錯分為
位錯
與
幀錯
兩大類。
位錯：二進位制數字出錯，如00000000變成00000001
幀錯：包括
丟失
、
重複
、
失序
三種。如傳送編號順序為1、2、3的三個幀，如果接收方收到的是13，就是發生了
丟失
，2號幀丟失；如果接收方收到的是1223，就是發生了重複，2號幀
重複
；如果接收方收到的是132，就是發生了
失序
，2 、3號幀失序。
為了保證資料傳輸的可靠性，必須採取一些措施來檢測差錯。差錯控制既可以檢測差錯然後
重傳
，也可以檢測差錯後直接
糾錯
。前者使用檢測編碼，後者使用糾錯編碼。
注：這裡的編碼是資料鏈層的編碼，針對的是
一組位元
。而物理層的編碼是針對
單個位元
，如歸零編碼、曼徹斯特編碼。
2。3。1 檢測編碼
檢測編碼有
奇偶校驗碼
和
CRC迴圈冗餘碼
兩種。
2。3。1。1 奇偶校驗碼
奇偶校驗碼分為
奇校驗
和
偶校驗
。n位的奇偶校驗碼中有n-1位資訊元和1位校驗元。在編碼時，先看資訊元中的“1”的個數是奇數還是偶數，對於奇校驗，如果資訊元中“1”的個數為奇數，則校驗位設定為0，如果為偶數，則校驗元設定為1，總之奇校驗就是透過設定校驗元時
校驗碼中“1”的個數為奇數
。而偶校驗就是透過設定校驗元時
校驗碼中“1”的個數為偶數
。
接收方收到資料後會檢查“1”的個數，對於奇校驗，如果“1”的個數為奇數，則認為沒有出錯，如果為偶數，則判定出錯，要求傳送方重傳。偶校驗同理。從工作過程中我們可以發現，如果判定出錯，則肯定發生了錯誤；但是如果
判定未出錯，卻不一定傳輸正確。
比如傳送奇校驗碼為000000001 ，如果接收方收到的是000000111，此時會判定正確，但實際出現了錯誤。奇偶校驗碼
只能檢測出奇數個位元的錯誤
。
2。3。1。2 CRC迴圈冗餘碼
CRC迴圈冗餘碼比較複雜，用一個例子來說明。比如要傳送資料1101 0110 11，首先發送方與接收方會商定一個
生成多項式
，如10011，生成多項式可以換一種形式G（x）=x4+x+1。事實上G（x）=1*x4+0*x3+0*x2+1*x1+1*x0，，取各項係數就得到了10011，然後
確定生成多項式的階
，生成多項式的階為x的最高次數，此生成多項式x的最高次數為4，故階為4。接下來在要傳送的資料後面加上4（階數）個0，得到1101 0100 11
0000
，然後進行模2除法（相同取0，不同取1，見下圖）。
最後得到的餘數1110即為冗餘碼，故最終傳送的資料為1101 0110 11
1110。
接收方收到資料後除以生成多項式10011，如果得到的餘數為0，則判定沒有錯誤並
接收
；否則判定未出錯並
丟棄
。
值得注意的是，使用CRC迴圈冗餘校驗也不一定保證接收就沒有出錯，只是出錯機率低，一般生成多項式越高階，出錯機率越低。
2。3。2 檢錯編碼
檢錯編碼這裡介紹海明碼。海明碼工作流程：
確定校驗碼位數r→確定校驗碼和資料的位置→求出校驗碼的值→檢錯並糾錯
①確定校驗碼位數：如果資料有m位，設校驗碼為r位，則校驗碼一共有2r種取值，減去1種全對的情況，則2r-1種取值方式表示有1位出錯，而編碼後一共有m+r位，故r應滿足：
2r-1≥m+r（海明不等式）
例如傳送資料1100，m=4，代入不等式可得最小的r=3，海明碼有m+r=7位。
②確定校驗碼和資料的位置：校驗碼放在序號為2n（1，2，4，8…）的位置上，按序填上。
③求出校驗碼的值：
4號校驗碼，4對應的二進位制為100，則其負責1**的校驗，即1
00
、1
01
、1
10
、1
11
，再轉換為十進位制，也就是4，5，6，7。1、2號校驗碼同理。
偶校驗說明：4對於x4，5對應0，6、7均對應1，則x4取0，這樣有偶數（也就是2）個“1”。
④檢錯並糾錯：
假設接收方收到的資料：
我們很容易發現5號位出錯了，但是接收方並不能直接識別，需要採用一定的方法進行判斷。
x4負責的4、5、6、7：0、1、1、1，由於是偶校驗，而這裡是奇數個1，故判定出錯。
x2負責的2、3、6、7：0、0、1、1，偶數個1，判定正確
x1負責的1、3、5、7：1、0、1、1，奇數個1，判定錯誤
據此可得出資料傳輸出錯。接下來判定出錯的位數：
法一：
合起來就得到了101，轉換為十進位制就是5，也就是5號位出錯。
法二：
先作圖，如圖所示。最外面三個部分是1、2、4，然後交叉的部分寫其和，3=1+2，5=1+4，6=2+4，7=1+2+4。根據前面的判斷4、5、6、7和1、3、5、7中有錯，取4、5、6、7的圓與1、3、5、7
相交
的部分，可得到錯誤在5、7中，又根據2、3、6、7正確，可以
排除
7，這樣就可以確定5號位出錯。
