各種校驗碼校驗算法分析講解

2024年3月31日發(fā)(作者：郭沫若天上的街市)

各種校驗碼校驗算法分析 二進制數(shù)據(jù)經(jīng)過傳送、存取等環(huán)節(jié)會發(fā)生誤碼1變成0或0

變成1這就有如何發(fā)現(xiàn)及糾正誤碼的問題。所有解決此類問題的方法就是在原始數(shù)據(jù)數(shù)碼

位基礎(chǔ)上增加幾位校驗冗余位。 一、碼距 一個編碼系統(tǒng)中任意兩個合法編碼碼字之間不

同的二進數(shù)位bit數(shù)叫這兩個碼字的碼距而整個編碼系統(tǒng)中任意兩個碼字的的最小距離就

是該編碼系統(tǒng)的碼距。 如圖1所示的一個編碼系統(tǒng)用三個bit來表示八個不同信息中。在

這個系統(tǒng)中兩個碼字之間不同的bit數(shù)從1到3不等但最小值為1故這個系統(tǒng)的碼距為1。

如果任何碼字中一位或多位被顛倒了結(jié)果這個碼字就不能與其它有效信息區(qū)分開。例如如

果傳送信息001而被誤收為011因011仍是表中的合法碼字接收機仍將認為011是正確

的信息。 然而如果用四個二進數(shù)字來編8個碼字那么在碼字間的最小距離可以增加到2

如圖2的表中所示。 信息序號 二進碼字 a2 a1 a0 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0

0 5 1 0 1 6 1 1 0 7 1 1 1 圖 1 信息序號 二進碼字 a3 a2 a1 a0 0 0 0 0 0 1 1 0 0 1 2 1

0 1 0 3 0 0 1 1 4 1 1 0 0 5 0 1 0 1 6 0 1 1 0 7 1 1 1 1 圖 2 注意圖8-2的8個碼字相

互間最少有兩bit的差異。因此如果任何信息的一個數(shù)位被顛倒就成為一個不用的碼字接

收機能檢查出來。例如信息是1001誤收為1011接收機知道發(fā)生了一個差錯因為1011不

是一個碼字表中沒有。然而差錯不能被糾正。假定只有一個數(shù)位是錯的正確碼字可以是

1或1010。接收者不能確定原來到底是這4個碼字中的那一個。也可看到 在

這個系統(tǒng)中偶數(shù)個2或4差錯也無法發(fā)現(xiàn)。 為了使一個系統(tǒng)能檢查和糾正一個差錯碼間

最小距離必須至少是“3”。最小距離為3時或能糾正一個錯或能檢二個錯但不能同時糾

一個錯和檢二個錯。編碼信息糾錯和檢錯能力的進一步提高需要進一步增加碼字間的最小

距離。 圖8-3的表概括了最小距離為1至7的碼的糾錯和檢錯能力。 碼距 碼 能 力 檢

錯 糾錯 1 2 3 4 5 6 7 0 0 1 0 2 或 1 2 加 1 2 加 2 3 加 2 3 加 3 圖3 碼距越大糾錯

能力越強但數(shù)據(jù)冗余也越大即編碼效率低了。所以選擇碼距要取決于特定系統(tǒng)的參數(shù)。數(shù)

字系統(tǒng)的設(shè)計者必須考慮信息發(fā)生差錯的概率和該系統(tǒng)能容許的最小差錯率等因素。要有

專門的研究來解決這些問題。 二、奇偶校驗 奇偶校驗碼是一種增加二進制傳輸系統(tǒng)最小

距離的簡單和廣泛采用的方法。例如單個的奇偶校驗將使碼的最小距離由一增加到二。 一

個二進制碼字如果它的碼元有奇數(shù)個1就稱為具有奇性。例如碼字“10110101”有五個1

因此這個碼字具有奇性。同樣偶性碼字具有偶數(shù)個1。注意奇性檢測等效于所有碼元的模

二加并能夠由所有碼元的異或運算來確定。對于一個n位字奇性由下式給出 奇性a0⊕a1

⊕a2⊕…⊕an 奇偶校驗可描述為給每一個碼字加一個校驗位用它來構(gòu)成奇性或偶性校驗。

例如在圖8-2中就是這樣做的。可以看出附加碼元d2是簡單地用來使每個字成為偶性的。

因此若有一個碼元是錯的就可以分辨得出因為奇偶校驗將成為奇性。奇偶校驗編碼通過增

加一位校驗位來使編碼中1個個數(shù)為奇數(shù)奇校驗或者為偶數(shù)偶校驗從而使碼距變?yōu)?。因

為其利用的是編碼中1的個數(shù)的奇偶性作為依據(jù)所以不能發(fā)現(xiàn)偶數(shù)位錯誤。 再以數(shù)字0

的七位ASCII碼0110000為例如果傳送后右邊第一位出錯0變成1。接收端還認為是一個

合法的代碼0110001數(shù)字1的ASCII碼。若在最左邊加一位奇校驗位編碼變?yōu)?0110000

如果傳送后右邊第一位出錯則變成101100011的個數(shù)變成偶數(shù)就不是合法的奇校驗碼了。

但若有兩位假設(shè)是第1、2位出錯就變成101100111的個數(shù)為5還是奇數(shù)。接收端還認為

是一個合法的代碼數(shù)字3的ASCII碼。所以奇偶校驗不能發(fā)現(xiàn)。 奇偶校驗位可由硬件電路

異或門或軟件產(chǎn)生 偶校驗位 an a0⊕a1⊕a2⊕…⊕an-1 奇校驗位 an NOTa0⊕a1⊕a2⊕…

⊕an-1。 在一個典型系統(tǒng)里在傳輸以前由奇偶發(fā)生器把奇偶校驗位加到每個字中。原有信

息中的數(shù)字在接收機中被檢測 如果沒有出現(xiàn)正確的奇、偶性這個信息標(biāo)定為錯誤的這個系

統(tǒng)將把錯誤的字拋掉或者請求重發(fā)。 在實際工作中還經(jīng)常采用縱橫都加校驗奇偶校驗位的

編碼系統(tǒng)--分組奇偶校驗碼。 現(xiàn)在考慮一個系統(tǒng) 它傳輸若干個長度為m位的信息。如果

把這些信息都編成每組n個信息的分組則在這些不同的信息間也如對單個信息一樣能夠作

奇偶校驗。圖4中n個信息的一個分組排列成矩形式樣并以橫向奇偶HP及縱向奇偶VP

的形式編出奇偶校驗位。 m位數(shù)字 橫向奇偶位 n 個 碼 字 a1 a2 … am-1 am HP1 b1

b2 … bm-1 bm HP2 c1 c2 … cm-1 cm HP3 … … … … … … n1 n2 … nm-1 nm HPn VP1

VP2 … VPm-1 VPm HPn1 縱向奇偶位 圖 4 用綜橫奇偶校驗的分組奇偶校驗碼 研究圖

4可知分組奇偶校驗碼不僅能檢測許多形式的錯誤。并且在給定的行或列中產(chǎn)生孤立的錯

誤時還可對該錯誤進行糾正。 在初級程序員試題中早期也出現(xiàn)在程序員試題中經(jīng)常有綜橫