檢錯碼

檢錯碼是一種編碼，指在傳輸過程中發生錯誤後,在接收端能自動檢查並發現錯誤的編碼。常用的檢錯碼有奇偶校驗碼、恆比碼等。

基本介紹

• 中文名：檢錯碼
• 目的：提高信息傳輸的有效性和可靠性
• 簡介：一種編碼
• 類別：奇偶校驗編碼和循環冗餘編碼

原理

為提高信息傳輸的有效性和可靠性,根據香農信息理論,必須對信源訊息實施信源編碼和信道編碼。經過Shannon,Fano或Huff man等3種形式的信源編碼後所形成的信息位若不實施信道編碼而直接藉助信道傳輸,由於信道干擾的存在必將使得接收端收到的信息出現不可補救的失真,因此必須對這些信息位實施添加某些校驗位的信道糾錯編碼。

類別

檢錯碼的兩大類別：奇偶校驗編碼和循環冗餘編碼。奇偶校驗碼是在原信息碼元後面附加一個監督元，使碼組中1或0的個數為奇數或偶數，為奇數者稱為奇數校驗碼；為偶數者稱為偶數校驗碼。奇數校驗碼可以發現奇數個錯誤。恆比碼是碼組中0和1的比例相同的編碼。它能檢查並發現偶數個錯誤。循環校驗碼（CRC碼），是數據通信領域中最常用的一種差錯校驗碼，其特徵是信息欄位和校驗欄位的長度可以任意選定。

奇偶校驗編碼

奇偶校驗是常用的檢錯方法。其原理是在7單位的ASCII代碼後增加一位，使碼中“1”的個數成奇數（奇校驗）或偶數（偶校驗）。經過傳輸後，如果其中一位（包括奇數個位）出錯，則接收端按同樣的規則就能發現錯誤。這種方法簡單實用，但只能對付少量的隨機性錯誤。

為了能檢測突發性的位串出錯，可以使用檢查和的方法。這種方法把數據塊中的每個位元組當做一個二進制整數，在傳送過程中按模256相加。數據塊傳送完後，把得到的和作為校驗位元組傳送出去。接收端在接收過程中進行同樣的加法，數據塊加完後用自己得到的校驗和與接收到的校驗和比較，從而發現是否出錯。實現時可以用更簡單的方法，例如在校驗位元組傳送前，對累加器中的數取2的補碼。這樣，如果不出錯的話，接收端在加完整個數據塊以及校驗和後累加器中是0.這種方法的好處是，由於進位的關係，一個錯誤可以影響到更高的位，從而使出錯位對校驗位元組的影響擴大了。可以粗略地認為，隨機的突發性錯誤對校驗和的影響也是隨機的。出現突然錯誤而得到正確的校驗位元組的機率是1/256。 於是我們就有255：1的機會能檢查出任何錯誤。

二維奇偶校驗碼

二維奇偶校驗碼是在奇偶校驗碼的基礎上生成的，又可分為垂直奇偶校驗、水平奇偶校驗和水平垂直奇偶校驗三種。

（1）垂直奇偶校驗

垂直奇偶校驗又稱為縱向奇偶校驗，它是把要傳送的信息碼元按定長 m 位分為若干段（如分為 n 段），然後按每段的縱向排列，對每列的信息元進行奇偶校驗，得到的校驗元附在每列後面。傳輸時按列的次序傳輸：第 1 列、第 2 列……第 n 列。以傳送序列1110111 1101111 1110010 1101100 1100100 為例，圖1表明了垂直奇偶校驗的基本原理。

由圖1可見，垂直奇偶校驗的編碼效率為 R = m/(m+1)，通常 m 取值為 8 ，即一個字元的長度 ， 所以垂直奇偶校驗有時也稱為字元奇偶校驗 。這種檢驗碼只能檢驗出垂直列上的奇數位差錯 ，而不能檢驗出偶數位差錯 。 但由於突發錯出現奇數位錯誤碼元與出現偶數位錯誤碼元的機率各半 ，因此垂直奇偶校驗只能查出 50% 突發性錯誤 。

（2）水平奇偶校驗

水平奇偶校驗又稱為橫向奇偶校驗 ，它也是把要傳送的信息碼元按定長 m 位分為若干段（如分為 n段），然後每段縱向排列 ，對每行的信息元進行奇偶校驗 ，得到的校驗元附在每行後面 。 傳輸時同樣按列的次序傳輸 ：第 1 列 、第 2 列 … … 第 n +1 列 。 仍以傳送序列1110111 1101111 1110010 1101100 1100100 為例 ， 圖2表明了水平奇偶校驗的基本原理 。

由圖2可見 ， 水平奇偶校驗的編碼效率為 R = n/（n+ 1）。這種檢驗的優勢是檢錯能力強 ， 不僅能檢驗出水平方向上每行的奇數位錯 ， 而且還能檢測出突髮長度 ≤ m 位的所有突發錯 。 但它的缺點是傳送端必須等待上層的信息都到全後才能開始計算冗餘位 ， 接收端也必須等待全部信息都接收後才能開始進行校驗 ， 所以傳送方和接收方都必須設定緩衝區 ， 並且產生檢驗碼 、檢查檢驗碼的邏輯也比較複雜 。
（3）水平垂直奇偶校驗
將水平和垂直兩個方向的奇偶校驗結合起來就構成了水平垂直奇偶校驗 ，又稱縱橫奇偶檢驗和方陣奇偶校驗 。 仍以傳送序列 1110111 1101111 1110010 1101100 1100100 ，圖3表明了水平垂直奇偶校驗的基本原理。水平垂直奇偶校驗的編碼效率為 R =mn/[(m+1)(n+1)]。

水平垂直奇偶校驗可以檢測出所有 3 位或 3位以下的錯誤 、水平或垂直方向上的奇數個錯誤 、突髮長度 < m 的突發性錯誤以及部分偶數位錯誤 。 換言之 ，它可以檢測出除了互相補償的偶數位錯以外的所有差錯（這裡所謂互相補償的偶數個數是指有錯的各行 、各列中出錯位數都為偶數的情況） 。另外 ， 水平垂直奇偶校驗不僅能檢錯 ， 還可以糾正部分差錯 。 例如 ，數據碼元中僅存在一位錯誤時 ， 就能確定錯碼的位置（在某行和某列的交叉處）,從而糾正它 。

循環冗餘編碼

工作原理如下：

收發雙方依所協定的規定使用一個CRC生成多項式G(x)。常用的多項式有：

CRC-12：G(x)=x12+x11+x3+x2+x+1

CRC-16：G(x)=x16+x15+x2+1

CRC-CCITT：G(x)=x16+x12+x5+1

CRC-32：G(x)=x32+x26+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1

計算方法為：最高次方決定二進制數字序列，凡有x的位置為1，其它位置為0。

根據二進行制數字序列的位數n，在要傳送的數據後面補n-1個0;

將得到的新的數據除以二進制數字序列(使用異或算法，不借位)，得到一個n-1位數的餘數m

將原來要傳送的數據序列與餘數m構成一個新的數字序列進行傳送。

接收方接到傳送方發來的數據後，將收到的數據依然用規定的二進制序列來除，如果得到的餘數為0，則數據正確，否則重發。