工作原理
一個二進碼字,如果它的碼元有奇數個1,就稱為具有奇性。例如,碼字“1011010111”有七個1,因此,這個碼字具有奇性。同樣,偶性碼字具有偶數個1。注意奇性檢測等效於所有碼元的模二加,並能夠由所有碼元的異或運算來確定。對於一個n位字,奇性由式(8-1)給出:
奇性=a0⊕a1⊕a2⊕…⊕an (8-1)
很明顯,用同樣的方式,我們也能夠根據每一個碼字的零的個數來構成奇偶監督。
單個的奇偶監督碼可描述為:給每一個碼字加一個監督位,用它來構成奇性或偶性監督。例如,在圖8-2中,對於二進碼就是這樣做的。可以看出,附加碼元d2,是簡單地選來使每個字成為偶性的。因此,若有一個碼元是錯的,就可以分辨得出,因為奇偶監督將成為奇性。
在一個典型系統里,在傳輸以前,由奇偶發生器把奇偶監督位加到每個字中。原有信息中的數字在接收機中被檢測, 如果沒有出現正確的奇、偶性,這個信息標定為錯誤的,這個系統將把錯誤的字拋掉或者請求重發。注意,用單個的奇偶監督碼僅能檢出奇數個碼元的錯誤。
例如考慮圖8-4里的奇性監督碼。把奇、偶監督位加到一個 8-4-2-1 BCD碼,使之能夠進行奇監督(將所有監督位反過來將產生偶監督碼)。可以看到,如果將任何碼字里的奇數個碼元反過來,那么將成為偶性碼,因而,無效的字是可以分辨出來的。然而,如果有兩個或四個碼元反過來,那末奇偶監督將仍然是奇性碼,並且這個字被認為是正確的。只當一個給定的字里同時出現兩個錯誤的機率被忽略不計時,單個的奇偶監督才是有效的,實際上,奇監督碼比偶監督碼可取,因為它排除了傳輸全0的情況。
十進數字 4 比特直接二進碼 奇性監督位
n 8 4 2 1
0 0 0 0 0 1
1 0 0 0 1 0
2 0 0 1 0 0
3 0 0 1 1 1
4 0 1 0 0 0
5 0 1 0 1 1
6 0 1 1 0 1
7 0 1 1 1 0
8 1 0 0 0 0
9 1 0 0 1 1
圖8-4 附加奇性監督位的BCD碼
簡單的說,不帶奇偶校驗的記憶體每個位元組只有8位,如果其某一位存儲了錯誤的值,就會導致其存儲的相應數據發生變化,進而導致應用程式發生錯誤。而奇偶校驗就是在每一位元組(8位)之外又增加了一位作為錯誤檢測位。在某位元組中存儲數據之後,在其8個位上存儲的數據是固定的,因為位只能有兩種狀態1或0,假設存儲的數據用位標示為1、1、1、0、0、1、0、1,那么把每個位相加(1+1+1+0+0+1+0+1=5),結果是奇數,那么在校驗位定義為1,反之為0。當CPU讀取存儲的數據時,它會再次把前8位中存儲的數據相加,計算結果是否與校驗位相一致,從而一定程度上能檢測出記憶體錯誤。奇偶校驗分兩種,一種是奇校驗和偶校驗,例:奇校驗中,將原來用7位表示的最低位上加1,如果最終的二進制數中,1的個數是奇數的話就不用加1,反之,加1。
實際套用
奇偶監督可以用在數字系統的主要接口設備中。由於在每個信息中加了多餘度,僅當出現錯誤的機率和錯誤的危害足夠大時,才採用奇偶監督碼。
假設以400比特/秒的速率傳輸四碼位信息(100字/秒)。設由試驗數據或適當的計算確定了任何單個碼位出現錯誤的機率為3.1×10-5。因為,每個字包含四個碼位,接收到錯字的機率大約為1.25×l0-4,即在100字/秒的傳輸速率下,平均每80秒錯一個字。
加一個奇偶監督位後,每個字需要五個碼位,從而,將傳輸速率降低到80字/秒,能夠檢測一個錯誤,並且能指令傳送機重發錯了的信息以校正信息。出現兩個錯誤的機率計算如下:如果五個碼位是A、B、C、D、E,那么兩個錯誤可能以下述10種組合出現。即
AB、AC、AD、AE
BC、BD、BE
CD、CE
DE
出現任何一對的機率是(3.1×10-5)2,或9.6×10-10,因此,在單個字里出現兩個錯誤的機率等於10× 9.6×10-10,或9.6×10-9。以80字/秒的新的傳輸速率, 可能以每1.3×10-6秒, 即平均每15天,出現一個未被檢出的錯誤。因為三個錯誤能被檢測出,四個碼位錯誤的機率與兩個錯誤相比可以忽略不計,因此,我們在這裡不考慮任何更多的錯誤。
局限
奇偶校驗只能檢測出錯誤而無法對其進行修正,同時雖然雙位同時發生錯誤的機率相當低,但奇偶校驗卻無法檢測出雙位錯誤。