奇偶校驗碼

是一種增加二進制傳輸系統最小距離的簡單和廣泛採用的方法。例如，單個的奇偶校驗將使碼的最小距離由一增加到二 ^[1]  。

一個二進制碼字，如果它的碼元有奇數個1，就稱為具有奇性。例如，碼字“10110101”有五個1，因此，這個碼字具有奇性。同樣，偶性碼字具有偶數個1。注意奇性檢測等效於所有碼元的模二加，並能夠由所有碼元的異或運算來確定。對於一個n位字，奇性由下式給出：奇性=a0⊕a1⊕a2⊕…⊕an

奇偶校驗可描述為：給每一個碼字加一個校驗位，用它來構成奇性或偶性校驗。可以看出，附加碼元d2，是簡單地用來使每個字成為偶性的。因此，若有一個碼元是錯的，就可以分辨得出，因為奇偶校驗將成為奇性。奇偶校驗編碼通過增加一位校驗位來使編碼中1個個數為奇數（奇校驗）或者為偶數（偶校驗），從而使碼距變為2。因為其利用的是編碼中1的個數的奇偶性作為依據，所以不能發現偶數位錯誤。

^[1]  一個編碼系統中任意兩個合法編碼（碼字）之間不同的二進數位（bit）數叫這兩個碼字的碼距，而整個編碼系統中任意兩個碼字的的最小距離就是該編碼系統的碼距。

為了使一個系統能檢查和糾正一個差錯，碼間最小距離必須至少是“3”。最小距離為3時，或能糾正一個錯，或能檢二個錯，但不能同時糾一個錯和檢二個錯。編碼信息糾錯和檢錯能力的進一步提高需要進一步增加碼字間的最小距離。

碼距越大，糾錯能力越強，但數據冗餘也越大，即編碼效率低了。所以，選擇碼距要取決於特定系統的參數。數字系統的設計者必須考慮信息發生差錯的概率和該系統能容許的最小差 ^[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.20所示,編碼規則為

若每個信息段就是一個字符的話,這裏的q就是發送的信息塊中的字符數。

水平奇偶校驗的編碼效率為R=q/(q+1)。

水平奇偶校驗不但可以檢測出各段同一位上的奇數位錯,而且還能檢測出突發長度≦p的所有突發錯誤，因為按發送順序從圖2.20中可見，突發長度≦p的突發錯誤必然分佈在不同的行中，且每行一位，所以可以檢查出差錯，他的漏檢率比垂直奇偶校驗方法低。但是實現水平奇偶校驗碼時，不論是採用硬件還是軟件方法，都不能在發送過程中產生奇偶校驗冗餘位邊插入發送,而必須等待要發送的全部信息塊到齊後,才能計算冗餘位,也就是一定.要使用數據緩衝器,因此它的編碼和檢測實現起來都要複雜一些。

同時進行水平奇偶校驗和垂直奇偶校驗就構成水平垂直奇偶校驗,也稱為縱橫奇偶校實驗,如圖2.21所示。若水平垂直都採用偶校驗,則

水平垂直奇偶校驗的編碼效率為R=pq/[(p+1)(q+1)]。.

水平垂直奇偶校驗能檢測出所有3位或3位以下的錯誤(因為此時至少在某一行或某一'列上有一位錯)、奇數位錯、突發長度<=p+1的突發錯以及很大一部分偶數位錯。測量表.明,這種方式的編碼可使誤碼率降至原誤碼率的百分之一到萬分之一。

水平垂直奇偶校驗不僅可檢錯,還可用來糾正部分差錯。例如數據塊中僅存在1位錯'時,便能確定錯碼的位置就在某行和某列的交叉處,從而可以糾正它。

奇偶校驗碼是 ^[2]  奇校驗碼和偶校驗碼的統稱，是一種最基本的檢錯碼。它是由n-1位信息元和1位校驗元組成，可以表示成為（n，n-1）。如果是奇校驗碼，在附加上一個校驗元以後，碼長為n的碼字中“1”的個數為奇數個；如果是偶校驗碼，在附加上一個校驗元以後，碼長為n的碼字中“1”的個數為偶數個。設：如果一個偶校驗碼的碼字用A=[an-1,an-2,…，a1,a0]表示，則：（1） ^[2]  式中 為校驗元，“+”為模二和（以後也這樣表示，請注意）。式（1）通常被稱為校驗方程。利用式（1），由信息元即可求出校驗元。另外，如果發生單個（或奇數個）錯誤，就會破壞這個關係式，因此通過該式能檢測碼字中是否發生了單個或奇數個錯誤。