漢明碼糾錯(cuò)的基本原理及優(yōu)化解決方案

引言

漢明碼是在原編碼的基礎(chǔ)上附加一部分代碼，使其滿足糾錯(cuò)碼的條件。它屬于線性分組碼，由于線性碼的編碼和譯碼容易實(shí)現(xiàn)，至今仍是應(yīng)用最廣泛的一類碼。漢明碼的抗干擾能力較強(qiáng)，但付出的代介也很大，比如8比特漢明碼有效信息只有總編碼長度的一半，可以糾正1個(gè)差錯(cuò)發(fā)現(xiàn)2個(gè)差錯(cuò)。在實(shí)際應(yīng)用中常常存在各種突發(fā)干擾，使連續(xù)多位數(shù)據(jù)發(fā)生差錯(cuò)。為了糾正3個(gè)以上的差錯(cuò)，就要加大碼距，使代碼冗余度大大增加，通信效率下降。本文所介紹的方法，就可以在不加大碼距的同時(shí)，提高漢明碼對(duì)突發(fā)干擾所產(chǎn)生差錯(cuò)的糾錯(cuò)能力，糾正多位連續(xù)的差錯(cuò)。

1 漢明碼糾錯(cuò)原理及設(shè)計(jì)

設(shè)原代碼的碼長為k比特，附加糾錯(cuò)編碼部分為r比特，則合成后的糾錯(cuò)碼為n=k+r比特。如果這種糾錯(cuò)碼的糾錯(cuò)能力為糾正1個(gè)差錯(cuò)，則應(yīng)滿足如下基本條件：

2r≥k+r+1

當(dāng)上式取等號(hào)時(shí)則稱漢明碼（Hamming Code）。干擾不僅使原代碼的每一位（k比特（可能出錯(cuò)，而且附加糾錯(cuò)位（r比特）也可能出錯(cuò)，故“一個(gè)差錯(cuò)”的情況共有k+r種，加上“正常”狀態(tài)共有k+r+1種狀態(tài)，而r比特的附加糾錯(cuò)位要能分辨這k+r+1種狀態(tài)。

漢明碼是線性分組碼，［n，k］線性分組碼的編碼設(shè)計(jì)就是在滿足給定條件（如碼距）下，如何從已知的k個(gè)信息元中求同r=n-k個(gè)校驗(yàn)元。要計(jì)算出校驗(yàn)元，就要先求出漢明碼校驗(yàn)矩陣。我們可以從線性空間的角度去分析，推出一致校驗(yàn)矩陣。這里給出構(gòu)造“糾正1個(gè)差錯(cuò)發(fā)現(xiàn)2個(gè)差錯(cuò)”漢明碼校驗(yàn)矩陣的簡便方法。以實(shí)際應(yīng)用中經(jīng)常使用的16位比特漢明碼為例來說明。

15比特漢明碼由11位信息位、4位校驗(yàn)位組成，因此，編碼長度為 n=k+r=11+4=15。我們把1，2，3，…，15化為二進(jìn)制數(shù)，然后把它們作為矩陣的縱列，可得到的矩陣為：

將包含單個(gè)1的4個(gè)縱列移到右邊，在最后加1列全0的縱列，在第1行上面加1行全1的橫行。這樣就得到了［16，11，4］可糾正1位錯(cuò)誤發(fā)現(xiàn)2位錯(cuò)誤的增廣漢明碼校驗(yàn)矩陣?？梢愿鶕?jù)編程要求組織信息位和校驗(yàn)位的位置，最后得到矩陣如下：

2 用漢明碼對(duì)連續(xù)多位差錯(cuò)糾正的實(shí)現(xiàn)

要想在不加大碼距的前提下，糾正連續(xù)多位差錯(cuò)，提高抵抗突發(fā)干擾的能力，可根據(jù)校驗(yàn)矩陣得出的漢明碼重新進(jìn)行組織排列。以16比特的漢明碼為例，把11個(gè)字節(jié)的數(shù)據(jù)編碼為16個(gè)字節(jié)的漢明碼后再按高低字節(jié)分成兩組。我們把每組字節(jié)8個(gè)漢明碼的第1位分別取出，組成第1個(gè)字節(jié)。然后，再把這8個(gè)字節(jié)漢明碼的第2位取出，組成第2個(gè)字節(jié)。依此類推，將這組8個(gè)字節(jié)漢明碼處理完畢，得到新的8個(gè)字節(jié)編碼，兩組一共16字節(jié)。我們可以看到這們排序后，每個(gè)字節(jié)包括原來8個(gè)漢明碼的其中1位。這樣，如果一次突發(fā)干擾使某一編碼字節(jié)連續(xù)8位都發(fā)生改變，實(shí)際是分別使原來8個(gè)漢明碼的其中1位發(fā)生了改變。只要在糾錯(cuò)前把受干擾的編碼恢復(fù)為原來正常的排列順序，就可通過計(jì)算校驗(yàn)碼完成差錯(cuò)的定位及糾錯(cuò)。

如果有163個(gè)字節(jié)的原始數(shù)據(jù)，經(jīng)編碼后為240個(gè)字節(jié)的漢明碼，那么如果把240個(gè)字節(jié)的漢明碼的每一位都取出，分別組成15個(gè)字節(jié)的編碼，這樣是不是可以連續(xù)糾正15個(gè)字節(jié)的差錯(cuò)了呢？在實(shí)際應(yīng)用中要分情況而定。通信中，一般可分為異步、同步兩種方式。在異步傳輸中起始位和停止位是由硬件電路產(chǎn)生的，如果干擾使起始位或停止位發(fā)生了改變，那么即使程序有跨字節(jié)糾錯(cuò)的能力也是無用的。對(duì)于同步方式則是可行的，因?yàn)樵诎l(fā)送接收雙方取得同步后，數(shù)據(jù)塊的每個(gè)字符間取消了起始位和停止位。常用的串口通信一般采用異步傳輸方式，能保證糾正連續(xù)1個(gè)字節(jié)的差錯(cuò)就可以了。

我們也要看到，這樣處理后提高了漢明碼對(duì)突發(fā)干擾差錯(cuò)的糾錯(cuò)能力，卻犧牲了對(duì)隨機(jī)干擾糾錯(cuò)能力。因?yàn)檫@樣對(duì)漢明碼重新排序后，原來1個(gè)漢明碼的各個(gè)位分布在不同位置的字節(jié)里，當(dāng)有多個(gè)隨機(jī)干擾出現(xiàn)時(shí)，可能使原來這個(gè)被拆開的1個(gè)漢明碼多位出現(xiàn)差錯(cuò)。因此采用多少位的漢明碼，如何對(duì)漢明碼重新組織排列，要根據(jù)信道的特點(diǎn)來決定。例如，一個(gè)數(shù)據(jù)通信信道經(jīng)常會(huì)受到多個(gè)隨機(jī)干擾的影響，那么我們就不必將漢明碼拆開。如果每次通信數(shù)據(jù)量不大，還可以縮短編碼長度，比如采用［8，4，3］8比特漢明碼。這樣雖然有效信息只是總編碼長度的50%，但比起出現(xiàn)多個(gè)差錯(cuò)后而要求發(fā)送方重發(fā)數(shù)據(jù)要好。

3 軟件實(shí)現(xiàn)

下面給出基于最常用的MCS-51單片機(jī)匯編語言的漢明碼測試程序。它的有效信息占到了總編碼長度的70%，測試程序中自動(dòng)生成11個(gè)字節(jié)的原始數(shù)據(jù)。

原始數(shù)據(jù)塊的長度、存放地址可根據(jù)實(shí)際情況由用戶自己確定，只要將本測試程序的漢明碼編碼、解碼子程序嵌入用戶應(yīng)用程序中，就可直接使用。

3.1 16位漢明碼編碼子程序

原始數(shù)據(jù)是11個(gè)字節(jié)，經(jīng)過編碼后是16個(gè)字節(jié)的漢明碼。圖1是漢明碼編碼子程序流程圖。

3.2 16位漢明碼解碼子程序

在解碼之前可以人為地加入差錯(cuò)。差錯(cuò)要控制在1個(gè)字節(jié)內(nèi)，否則出錯(cuò)標(biāo)志將置位，后續(xù)處理可根據(jù)實(shí)際應(yīng)用情況確定。圖2是漢明碼解碼子程序流程圖。

結(jié)語

本文針對(duì)漢明碼在實(shí)際應(yīng)用中對(duì)突發(fā)干擾所產(chǎn)生多位差錯(cuò)糾錯(cuò)能力低的缺點(diǎn)，提出了相應(yīng)的解決方案。此方法通過的實(shí)際使用，證明了這種方案是可行的尤其對(duì)于一些無線數(shù)傳設(shè)備，采用這種方案后可以有效糾正突發(fā)干擾所產(chǎn)生的差錯(cuò)。

責(zé)任編輯：gt