- 資料校驗的基本原理
- <1> 資料校驗的必要性
- <2> 校驗的基本原理
- <3> 碼距的概念
- <4> 碼距與檢錯或糾錯能力的關系
- <5> 選擇碼距要考慮的因素
- 奇偶校驗
- CRC校驗及其實作
- 海明校驗
資料校驗的基本原理
<1> 資料校驗的必要性
- 受元器件的品質、電路故障或噪音幹擾等因素的影響，資料在被處理、傳輸、存儲的過程中可能出現錯誤
- 若能設計硬體層面的錯誤檢測機制，可以減少基于軟體檢錯的代價（系統觀）
<2> 校驗的基本原理
- 增加備援碼（校驗位）
- 有效資訊(k位) 校驗資訊(r位)
<3> 碼距的概念
- 同一編碼中，任意兩個合法編碼之間不同二進制位數的最小值
- 0011 與 0001 的碼距為1，一位錯誤時無法識别
- 0000、0011、0101、0110、1001、1010、1100、1111等編碼碼距為2。 任何一位發生變化，如0000變成1000就從有效編碼變成了無效編碼，容易檢測到這種錯誤
- 校驗碼中增加備援項的目的就是為了增大碼距
<4> 碼距與檢錯或糾錯能力的關系
- 碼距
- 碼距
- 碼距e+t+1 : 可糾正t個錯誤，同時檢測e個錯誤(e
<5> 選擇碼距要考慮的因素
- 碼距越大，抗幹擾能力越強，糾錯能力越強，資料備援越大，編碼效率低，編碼電路也相對負複雜
- 選擇碼距必須考慮資訊發生差錯的機率和系統能容許的最小差錯率
奇偶校驗
- 增加備援碼（檢驗位）
- 有效資訊(k位) 校驗資訊(r=1位)
- 編碼
- 根據有效資訊計算校驗資訊位，使校驗碼（資料+1位校驗資訊）中1的個數滿足奇/偶檢驗的要求
- 0001 -> 00011 (偶校驗) P1 = D1D2D3D4D5D6D…Dn
- 0001 -> 00010 (奇校驗) P2 =
- 特點
- 編碼與檢錯簡單
- 編碼效率高
- 不能檢測偶數位錯誤，無錯結論不可靠，是一種錯誤檢測碼
- 不能定位錯誤，是以不具備糾錯能力
- 奇偶校驗的碼距
- 碼距為 2
- 改進的奇/偶校驗
- 雙向奇偶校驗
- 可糾正1位錯誤
- 可檢測出某行/列上的奇數位
- 可檢測出一部分偶數位錯誤
- 不能檢測出錯碼分布在矩形4個頂點上的錯誤
- 方塊校驗
- 垂直水準校驗
- 奇/偶校驗應用
- 應用場景
- 記憶體條
- 工程上的應用
- 路由器配置
- 一般在同步傳輸中常用奇校驗
- 異步傳輸中常采用偶校驗
CRC校驗及其實作
- 原理
-
增加備援碼
有效資訊（k位）檢驗資訊（r位）
N = k + r <= 2r- 1
-
生成多項式G(x)
收發雙方約定的一個(r + 1)位二進制數，發送方利用G(X)對資訊多項式做模2除運算,生成校驗碼。接收方利用G(X)對收到的編碼多項式做模2除運算檢測差錯及錯誤定位
- G(x)應滿足的條件
- 最高位和最低位必須為1
- 當被傳送資訊（CRC碼）任何一位發生錯誤時，被生成多項式做除後應該使餘數不為0
- 不同位發生錯誤時，模2除運算後餘數不同
- 對不為0餘數繼續進行模2除運算應使餘數循環
- 常見生成多項式G(x)
- 模2除運算
- 模2運算規則
- 加/減運算（異或運算，加不進位，減不借位）
- 0±0＝0，0±1＝1，1±0＝1，1±1＝0
- 模2除法
- 按模2減，求部分餘數，不借位
- 上商原則
- 部分餘數首位為1時，商為1，減除數
- 部分餘數首位為0時，商為0，減0
- 當部分餘數的位數小于除數的位數時，該餘數即為最後餘數
- CRC編碼方法
-
根據待校驗資訊的長度k，按照 k+r ≤ 2r－1 确定校驗位r的位數
如對4位資訊 1100 進行CRC編碼，根據 4+r ≤ 2r－1
得 rmin= 3
- 根據r 和生成多項式的選擇原則，選擇位數為r +1的生成多項式G(X)= 1011
-
進行下列變化
有效資訊（k位） 檢驗資訊（r位）
1100 000
即：将待校驗的二進制資訊Q(X)邏輯左移 r 位,得到Q(X)’
- 對Q(X)’按模2運算法則除G(x)，求CRC編碼中的r位校驗資訊
-
用得到的餘數替換Q(X)’的最後r位即可得到對應的CRC編碼
1100 010
- CRC的檢錯與糾錯
- 接收方利用G(X)對收到的編碼多項式做模2除運算
餘數為0說明傳輸沒有錯誤
- 接收方利用G(X)對收到的有錯編碼多項式做模2除運算
餘數不為0說明傳輸有錯
- （7,4）編碼不同數位出錯對應的餘數
- 一位出錯情況下餘數的循環特性
- 利用出錯情況下餘數的循環特性就行糾錯
- 若餘數不為0，一邊對餘數補0繼續做模2除，同時讓被檢測的校驗碼循環左移，當餘數為101時，出錯位也移到A1位置。通過異運算糾正後繼續循環左移和執行餘數模2除法，直到修改後的出錯位回原位。不需對每一位提供糾正電路
- 當位數增多時，循環碼校驗能有效地降低硬體代價，這是它得以廣泛應用的主要原因 - CRC的應用
- 關于CRC的國際标準（部分）
海明校驗
- 原理
-
增加備援碼
有效資訊（k位）檢驗資訊（r位）
N = k + r <= 2r - 1
- 設k+r位海明碼從左到右依次為第1，2，3，……， k+r位，r位校驗位記為Pi（i=1，2，…，r)，分别位于k+r位海明編碼的第2i-1 （i=1，2，…，r)位上，其餘位依次放置被校驗的資料位
- (7，4)海明校驗碼中校驗位和被校驗資訊位的排列如下
-
海明碼位号 Hj1 2 3 4 5 6 7 8 9 10 11
P和b的分布 P1P2b1P3b2b3b4P4b5b6b7
- Hj 位的資料被編号小于j的若幹個海明位号之和等于j的校驗位所校驗 ,如:
設被傳送的資訊b1b2b3b5b5b6b7 = 1 0 1 1 0 0 0，采用偶校驗
則
- 特點
- 指錯字G4G3G2G1= 0000 不一定無錯（利用偶校驗的特點去判斷）
- 一位錯與兩位錯不能由指錯字差別
-
海明校驗的完善
G2G1= 0 0 0 0， 表明無錯！
- 特點
- 指錯字G4G3G2G1= 0000 不一定無錯（利用偶校驗的特點去判斷）
- 一位錯與兩位錯不能由指錯字差別
- 海明校驗的完善
- 在海明校驗的基礎上增加一位奇偶校驗位