|
引言 漢明碼是在原編碼的基礎上附加一部分代碼，使其滿足糾錯碼的條件。它屬于線性分組碼，由于線性碼的編碼和譯碼容易實現，至今仍是應用最廣泛的一類碼。漢明碼的抗干擾能力較強，但付出的代介也很大，比如8比特漢明碼有效信息只有總編碼長度的一半，可以糾正1個差錯發現2個差錯。在實際應用中常常存在各種突發干擾，使連續多位數據發生差錯。為了糾正3個以上的差錯，就要加大碼距，使代碼冗余度大大增加，通信效率下降。本文所介紹的方法，就可以在不加大碼距的同時，提高漢明碼對突發干擾所產生差錯的糾錯能力，糾正多位連續的差錯。 1 漢明碼糾錯原理及設計 設原代碼的碼長為k比特，附加糾錯編碼部分為r比特，則合成后的糾錯碼為n=k+r比特。如果這種糾錯碼的糾錯能力為糾正1個差錯，則應滿足如下基本條件： 2r≥k+r+1 當上式取等號時則稱漢明碼（Hamming Code）。干擾不僅使原代碼的每一位（k比特（可能出錯，而且附加糾錯位（r比特）也可能出錯，故“一個差錯”的情況共有k+r種，加上“正常”狀態共有k+r+1種狀態，而r比特的附加糾錯位要能分辨這k+r+1種狀態。 漢明碼是線性分組碼，[n,k]線性分組碼的編碼設計就是在滿足給定條件（如碼距）下，如何從已知的k個信息元中求同r=n-k個校驗元。要計算出校驗元，就要先求出漢明碼校驗矩陣。我們可以從線性空間的角度去分析，推出一致校驗矩陣。這里給出構造“糾正1個差錯發現2個差錯”漢明碼校驗矩陣的簡便方法。以實際應用中經常使用的16位比特漢明碼為例來說明。 15比特漢明碼由11位信息位、4位校驗位組成，因此，編碼長度為 n=k+r=11+4=15。我們把1，2，3，…，15化為二進制數，然后把它們作為矩陣的縱列，可得到的矩陣為： 
將包含單個1的4個縱列移到右邊，在最后加1列全0的縱列，在第1行上面加1行全1的橫行。這樣就得到了[16,11,4]可糾正1位錯誤發現2位錯誤的增廣漢明碼校驗矩陣。可以根據編程要求組織信息位和校驗位的位置，最后得到矩陣如下：
D1、D2、D4、D8是校驗位，D16是全字節偶校驗位，其余11位是信息位。校驗碼分別是C0=0AB61H，C1=0CDA2H，C2=0F1C4H，C3=0FE08H，C4=0FFFFH。 2 用漢明碼對連續多位差錯糾正的實現 要想在不加大碼距的前提下，糾正連續多位差錯，提高抵抗突發干擾的能力，可根據校驗矩陣得出的漢明碼重新進行組織排列。以16比特的漢明碼為例，把11個字節的數據編碼為16個字節的漢明碼后再按高低字節分成兩組。我們把每組字節8個漢明碼的第1位分別取出，組成第1個字節。然后，再把這8個字節漢明碼的第2位取出，組成第2個字節。依此類推，將這組8個字節漢明碼處理完畢，得到新的8個字節編碼，兩組一共16字節。我們可以看到這們排序后，每個字節包括原來8個漢明碼的其中1位。這樣，如果一次突發干擾使某一編碼字節連續8位都發生改變，實際是分別使原來8個漢明碼的其中1位發生了改變。只要在糾錯前把受干擾的編碼恢復為原來正常的排列順序，就可通過計算校驗碼完成差錯的定位及糾錯。 如果有163個字節的原始數據，經編碼后為240個字節的漢明碼，那么如果把240個字節的漢明碼的每一位都取出，分別組成15個字節的編碼，這樣是不是可以連續糾正15個字節的差錯了呢？在實際應用中要分情況而定。通信中，一般可分為異步、同步兩種方式。在異步傳輸中起始位和停止位是由硬件電路產生的，如果干擾使起始位或停止位發生了改變，那么即使程序有跨字節糾錯的能力也是無用的。對于同步方式則是可行的，因為在發送接收雙方取得同步后，數據塊的每個字符間取消了起始位和停止位。常用的串口通信一般采用異步傳輸方式，能保證糾正連續1個字節的差錯就可以了。 我們也要看到，這樣處理后提高了漢明碼對突發干擾差錯的糾錯能力，卻犧牲了對隨機干擾糾錯能力。因為這樣對漢明碼重新排序后，原來1個漢明碼的各個位分布在不同位置的字節里，當有多個隨機干擾出現時，可能使原來這個被拆開的1個漢明碼多位出現差錯。因此采用多少位的漢明碼，如何對漢明碼重新組織排列，要根據信道的特點來決定。例如，一個數據通信信道經常會受到多個隨機干擾的影響，那么我們就不必將漢明碼拆開。如果每次通信數據量不大，還可以縮短編碼長度，比如采用[8,4,3]8比特漢明碼。這樣雖然有效信息只是總編碼長度的50%，但比起出現多個差錯后而要求發送方重發數據要好。 3 軟件實現 下面給出基于最常用的MCS-51單片機匯編語言的漢明碼測試程序。它的有效信息占到了總編碼長度的70%，測試程序中自動生成11個字節的原始數據。 原始數據塊的長度、存放地址可根據實際情況由用戶自己確定，只要將本測試程序的漢明碼編碼、解碼子程序嵌入用戶應用程序中，就可直接使用。源程序清單請見網絡補充版（http://www.dpj.com.cn）。 3.1 16位漢明碼編碼子程序 原始數據是11個字節，經過編碼后是16個字節的漢明碼。圖1是漢明碼編碼子程序流程圖。
3.2 16位漢明碼解碼子程序 在解碼之前可以人為地加入差錯。差錯要控制在1個字節內，否則出錯標志將置位，后續處理可根據實際應用情況確定。圖2是漢明碼解碼子程序流程圖。
結語 本文針對漢明碼在實際應用中對突發干擾所產生多位差錯糾錯能力低的缺點，提出了相應的解決方案。此方法通過筆者的實際使用，證明了這種方案是可行的尤其對于一些無線數傳設備，采用這種方案后可以有效糾正突發干擾所產生的差錯。 參考文獻 1. 周航慈.饒運濤 單片機程序設計基礎 1997 2. 周航慈.孫麗華.王仁波 信息技術基礎 2002 3. 周航慈 單片機應用程序設計技術 2002 作 者：東華理工學院 趙建武 周航慈 來 源：單片機與嵌入式系統應用2004（1） |
