1.1.4校驗碼
1.校驗碼用來檢測傳送的資料是否出錯。
2.将資料出現的編碼分為兩類：合法編碼：用于傳輸資料
錯誤編碼：不允許在資料中出現的編碼
3.奇偶校驗碼：是一種通過增加備援位使得碼字中"1"的個數恒為奇數或偶數的編碼方法,它是一種檢錯碼。
在實際使用時又可分為垂直奇偶校驗、水準奇偶校驗和水準垂直奇偶校驗等幾種。
拓展：1.垂直奇偶校驗
垂直奇偶校驗又稱為縱向奇偶校驗,它是将要發送的整個資訊塊分為定長p位的若幹段(比如說q段),每段後面按"1"的個數為奇數或偶數的規律加上一位奇偶位,如圖2.19所示。問位資訊(I11,I21,…,Ipl,I12,…,Ipq)中,每p位構成一段(即圖中的一列),共有q段(即共有q列〉。每段加上一位奇偶校驗備援位,即圖中的rio編碼規則為
注意:此間的"+"指的是模二加,也即異或運算。
圖中箭頭給出了串行發送的順序,即逐位先後次序為I11,I21,…,Ip1,r1,I12,…,Ipa,r2,…,兒,…,I間,rq。在編碼和校驗過程中,用硬體方法或軟體方法很容易實作上述連續半加運算,而且可以邊發送邊産生備援位;同樣,在接收端也可邊接收邊進行校驗後去掉校驗位。
垂直奇偶校驗方法的編碼效率為R=p/(p+1)。通常,取一個字元的代碼為一個資訊段,這種垂直奇偶校驗有時也稱為字元奇偶校驗。例如,在8位字元代碼(即用8位二進制數位表示一個字元)中,p=8,編碼效率便為8/9。
垂直奇偶校驗方法能檢測出每列中的所有奇數位錯,但檢測不出偶數位的錯。對于突發錯誤來說,奇數位錯與偶數位錯的發生機率接近于相等,因而對差錯的漏檢率接近于1/2。
2.水準奇偶校驗
為了降低對突發錯誤的漏檢率,可以采用水準奇偶校驗方法。水準奇偶校驗又稱為橫向奇偶校驗,它是對各個資訊段的相應位橫向進行編碼,産生一個奇偶校驗備援位,如圖2.20所示,編碼規則為
若每個資訊段就是一個字元的話,這裡的q就是發送的資訊塊中的字元數。
水準奇偶校驗的編碼效率為R=q/(q+1)。
水準奇偶校驗不但可以檢測出各段同一位上的奇數位錯,而且還能檢測出突發長度≦p的所有突發錯誤，因為按發送順序從圖2.20中可見，突發長度≦p的突發錯誤必然分布在不同的行中，且每行一位，是以可以檢查出差錯，他的漏檢率比垂直奇偶校驗方法低。但是實作水準奇偶校驗碼時，不論是采用硬體還是軟體方法，都不能在發送過程中産生奇偶校驗備援位邊插入發送,而必須等待要發送的全部資訊塊到齊後,才能計算備援位,也就是一定.要使用資料緩沖器,是以它的編碼和檢測實作起來都要複雜一些。
3.水準垂直奇偶校驗
同時進行水準奇偶校驗和垂直奇偶校驗就構成水準垂直奇偶校驗,也稱為縱橫奇偶校實驗,如圖2.21所示。若水準垂直都采用偶校驗,則水準垂直奇偶校驗的編碼效率為R=pq/[(p+1)(q+1)]。.
水準垂直奇偶校驗能檢測出所有3位或3位以下的錯誤(因為此時至少在某一行或某一'列上有一位錯)、奇數位錯、突發長度<=p+1的突發錯以及很大一部分偶數位錯。測量表.明,這種方式的編碼可使誤碼率降至原誤碼率的百分之一到萬分之一。
水準垂直奇偶校驗不僅可檢錯,還可用來糾正部分差錯。例如資料塊中僅存在1位錯'時,便能确定錯碼的位置就在某行和某列的交叉處,進而可以糾正它
4.海明碼：
海明碼是一種可以糾正一位差錯的編碼。它是利用在資訊位為k位，增加r位備援位，構成一個n=k+r位的碼字，然後用r個監督關系式産生的r個校正因子來區分無錯和在碼字中的n個不同位置的一位錯。它必需滿足以下關系式： 2r ≥ k+r+1 或 2r ≥ n+1 海明碼的編碼效率為： R=k/(k+r) 式中 k為資訊位位數 r為增加備援位位數。
編碼步驟 (1)根據資訊位數，确定校驗位數，2^r >= k+r+1，其中，k為資訊位數，r為校驗位數。求出滿足不等式的最小r，即為校驗位數。
(2)計算機校驗位公式。
表1-3其實可以當成一個公式來套用，如有已經編碼的資料 1100 1001 0111。我們隻需把這些資料填充到校驗公式，即可得到資訊位與校驗位。
填充的方法是這樣的，首先看資料的最低位(即右邊第1位)，最低位為1，把1填充在公式表的r0位置，接着取出資料的次低位資料(即右邊第2位)，
把它填充到r1位置，把右邊第3位數填充到I1位置。依此類推，我們可以得到表1-4。
表中第2行資料為1100 001 1，這就是資料1100 1001 0111的編碼資訊，而表格第3行是1 011，這便是校驗位。
注意： n 校驗位rn 所在位數為2^n，其餘由資訊位填充; n 資訊位下标從1開始，而校驗位下标從0開始。
例如：I8 對應的第十二位12=2^3+2^2，I7對應的第十一位11=2^3+2^1+2^0，I6 對應的第十位10=2^3+2^1，I5 對應的第九位9=2^3+2^0，
一直寫到I1對應的第三位。
校驗位rn 由前面位數寫成2的幂之和中包含2^n 的位數對應的資訊位之和構成
例如： r3=I8+I7+I6+I5 （+表示異或）
(3)求校驗位。根據上面我們所說的計算公式可以求出校驗位。
(4)求海明碼。根據上面的表格填充後，寫出海明碼。
5.循環備援校驗碼（CRC）：是資料通信領域中最常用的一種差錯校驗碼，其特征是資訊字段和校驗字段的長度可以任意標明。
（1）生成CRC碼的基本原理：任意一個由二進制位串組成的代碼都可以和一個系數僅為‘0’和‘1’取值的多項式一一對應。例如：代碼1010111對應的多項式為x6+x4+x2+x+1，而多項式為x5+x3+x2+x+1對應的代碼101111。
（2）CRC碼集選擇的原則：若設碼字長度為N，資訊字段為K位，校驗字段為R位(N=K+R)，則對于CRC碼集中的任一碼字，存在且僅存在一個R次多項式g(x)，使得
V(x)=A(x)g(x)=xRm(x)+r(x);
其中: m(x)為K次資訊多項式， r(x)為R-1次校驗多項式，g(x)稱為生成多項式：
g(x)=g0+g1x+g2x2+...+g(R-1)x(R-1)+gRxR
發送方通過指定的g(x)産生CRC碼字，接收方則通過該g(x)來驗證收到的CRC碼字。
（3）CRC校驗碼軟體生成方法：借助于多項式除法，其餘數為校驗字段。
（海明碼部分引用網易部落格上的資料及表格）
轉載于:https://www.cnblogs.com/nuanningan-292684880/archive/2013/02/02/2890382.html