單片機實現海明碼糾錯原理的研究

張福軍 宋鐵軍 劉 坤

(黑龍江八一農墾大學信息技術學院1，黑龍江 大慶 163319;中國鐵通大慶分公司2，黑龍江 大慶 163453)

0 引言

在微機系統的數字信號傳輸過程中，信息不可避免地受到各種干擾的影響，使信號波形發生變化，由此而產生錯誤信息。因此，如何及時發現錯誤并糾正錯誤信息，在數字通信中顯得尤為重要［1］。在實際應用中，通常利用單片機的串行雙工通信方式完成信息的傳輸，以保證單片機之間的通信準確，降低誤碼率。

一般采用的串行雙工通信方式有兩種，一是提高信道通信質量，降低由于信道本身引起的誤碼;二是在信道本身誤碼率無法改變的情況下，采用差錯控制技術，在數據發送端對信息進行抗干擾編碼，在數據接收端對信息進行譯碼，從而發現錯誤碼字或自動糾正錯誤碼字，提高數據傳輸的準確度。對于確定的系統而言，通常采用第二種方法，具體思想為在發送端的數據序列中增加一些數位，稱為監督位，這些監督位和數據位之間有一定的關系。接收端利用這種關系，還原真實數據并進行錯誤判斷。這種方法需要在線路收發端加裝編譯碼控制電路，利用硬件完成糾錯編碼功能。在實時性允許的現場情況下，可以利用軟件來完成硬件功能，從而降低成本、簡化電路，并根據實際情況，靈活地選擇適當的編碼碼制［2］。

海明碼是目前比較成熟和具有一定糾錯能力的碼制，本文就是利用單片機實現海明碼軟件編碼和譯碼的過程。

1 海明碼的編碼原理

1.1 海明碼的基本原理

人們從不同的角度和思路出發，創造了多種差錯控制編碼，海明碼就是其中之一。海明碼是1950年由Hamming R提出的、可以糾正一位差錯的分組碼。它利用在m個信息位上，增加k個校驗位，構成一個n=(m+k)位的碼字，然后利用k個校驗關系式產生的k個校正因子來區分是否有錯和確定在碼字中的n個不同位置的一位差錯。為了能夠糾正單個錯誤，必須滿足下列Hamming不等式:

對于式(1)，可以理解為假設n位信息中有一位出錯，必然產生n種不正確的代碼，而n位信息中含有k個校驗位，所以在2k個狀態中，用(2k－1)個狀態來分別代表出現一位錯碼的n種狀態，而剩下的一個表示正確的代碼。這樣可以知道出錯的碼位并進行糾正。

根據Hamming不等式可以得出對應不同校驗位的編碼長度，如表1所示。

表1 校驗位對應的編碼長度Tab.1 Encoding lengths vs.checking bit

由表1可以看出，當數據位較少時，需要附加的校驗位較多，但隨著數據位數的增加，所附加的校驗位就相對較少。

1.2 海明碼的編譯碼過程

利用單片機軟件實現海明碼的發送與接收，必須首先了解海明碼的編碼規則。海明碼編碼規則如下。

①校驗位與數據位之和為n，每個校驗位ki被分配在海明碼的第2i－1的位置上，其他位是數據位，并且按照從低位向高位依次排列的關系分配數據位。

②海明碼的每一位碼(包括校驗位和數據位)是由多個校驗位進行校驗的，被校驗的每一位位置號等于校驗它的各校驗位的位置號之和。只有這樣安排，才能從校驗的結果中反映出錯位的位置號［3］。

假設待發送的數據信息為一個字節，由表1可知，需要4位校驗位，這樣16種狀態可以包含12位數據中的每一位，其中包括8位數據位和4位校驗位。

待發送的 12 位數據為:M1、M2、M3、M4、M5、M6、M7、M8，校驗位為 K1、K2、K3、K4。根據海明碼編碼規則①，海明碼為 K1、K2、M1、K3、M2、M3、M4、K4、M5、M6、M7、M8。所有數據均為左邊為低位、右邊為高位。根據海明碼編碼規則②，生成的海明碼校驗位如表2所示。

表2 海明碼校驗位Tab.2 Hamming code checking bit

根據表1可以得出校驗位與需要校驗位之間的關系。K1校驗位對應的需校驗位的位編號最低位都為“1”，同理K2校驗位對應的需校驗位的位編號的倒數第二位都為“1”。依次類推它們與相應位的關系，可以得到校驗方程組為:

在數據的接收端需要對信息進行解碼，也就是譯碼，在譯碼過程中最重要的操作是獲得狀態碼。這里狀態碼用 S1、S2、S3、S4表示，狀態碼通過校驗方程得到。每個方程產生一個相應的值，把這些值組合起來就可以判斷出是否有錯誤以及錯誤的位置。檢驗方程如式(3)所示。

狀態碼與錯誤信息位的對應關系如表3所示［4－5］，若沒有錯誤，狀態碼為 0000。

表3 狀態碼與錯誤信息位的對應關系Tab.3 Status codes vs.error information bit

根據表3的狀態碼對應關系，在接收端只要得到狀態碼即可糾正錯誤的信息位，實現糾錯的功能。

2 單片機海明碼糾錯原理

上述海明碼編譯碼的運算思想，可以用單片機軟硬件實現，它們各有優缺點。利用單片機配合數字邏輯部件實現，可大大提高數據的可靠性，串行數據傳輸具有編譯碼速度快等特點，但需要一定的硬件電路支持，這無疑增加了數據傳輸系統的成本和復雜性。下面介紹一下用單片機軟件實現編譯碼的過程。

2.1 單片機軟件實現海明碼的發送

海明碼編碼、發送的基本思想是在數據存儲器的M1區中每個單位存放1個8位數據，首先按照式(1)計算出相應的校驗位，然后根據海明碼編碼規則進行排列，并存放在存儲器的M2區中，兩個相鄰的存儲單元存放的是一幀數據，發送時將M2區中的內容一次性發往接收端。單片機采用比較常用的MCS-51單片機，發送機發送程序流程圖如圖1所示。

圖1 發送程序流程圖Fig.1 Flowchart of sending program

初始化程序包括定時器T1、串行口、M1和M2區地址指針、海明碼長度、累加和R等的初始化。發送機首先發送海明碼數據塊長度和累加和，若接收機不能夠正確接收，回答有錯(FFH)，則發送機重新發送，直至接收機回答正確(00H)，發送機開始發送海明碼數據信息，直到全部數據信息發送完畢［6］。MCS-51系列單片機內部具有位尋址功能的布爾處理器，位地址為20H～2FH，還具有位尋址的寄存器和累加器以及位操作指令。使用布爾處理器可以很容易地完成海明碼的編碼和譯碼計算，這些計算包括數據發送端校驗位的計算和數據接收端狀態碼的計算［7］。海明碼發送機軟件編碼的程序流程圖如圖2所示。

圖2 軟件編碼程序流程圖Fig.2 Flowchart of software encoding procedures

2.2 單片機軟件實現海明碼的接收

接收機的程序與發送機相對應。接收機首先接收數據塊長度和累加和，對接收的數據進行校驗。如果校驗有錯，則向發送機回送出錯字符(FFH)，并重新接收數據塊長度和累加和;若校驗正確，則向發送機回送字符(00H)，開始接收數據信息，并存入接收機的M2區。然后對M2區數據進行解碼，完成數據位錯碼的檢測和糾正。最后將正確的數據按發送格式存于接收機的M1區［8］。接收機接收程序流程圖與發送機發送程序流程圖類似，這里不再敘述。接收機海明碼軟件譯碼程序流程圖如圖3所示。

圖3 軟件解碼程序流程圖Fig.3 Flowchart of software decoding procedures

在接收端，當計算得到狀態碼后，還要根據狀態碼判斷接收數據是否有錯，若有錯，要找出出錯位置并予以糾正。為了便于操作，可以將表3的狀態碼對應錯誤位置，按照一定的順序存放在單片機程序存儲器中，其首地址為TAB，單元存放的內容為錯碼對應的位置，用“1”表示。當發現接收數據有錯時，只需將對應的地址單元內容與相應的數據單元內容相異或，即可完成錯碼的糾正。最后將海明碼還原出數據信息，存儲到接收機數據存儲器的M1區，從而完成數據接收與校驗的過程［9］。

3 結束語

由上述海明碼原理及校驗位和狀態碼關系式的具體構造過程和方法來看，海明碼可以發現并自動糾正一位差錯，能夠把差錯限制在盡可能小的范圍內且不需要發送機重新發送，有效節約了通信網絡中的信息流量。利用單片機軟件實現糾錯編解碼，不僅可以節約硬件資源，且比較容易實現，只要在發送機、接收機中分別加入數據編碼和解碼子程序即可。利用匯編語言或者C語言都很容易實現這一過程［10］。在實際應用中，錯碼的位置與狀態碼的對應關系可以不同，有多種組合，這由程序編寫人員確定。對應關系不同，則所得到的校驗位和狀態碼關系式也不相同，可見，海明碼的構造是很靈活的。

［1］趙軍軍.海明碼在微機信息傳輸中的糾錯原理與應用［J］.寶雞文理學院學報，1997(1):54－57.

［2］梁紅，王英煥.軟件差錯控制在單片機通信中的應用［J］.鞍山鋼鐵學院學報，1998，21(4):31 －33.

［3］須文波，姚紫陽.擴展海明碼在嵌入式系統通信中的應用［J］.微處理機，2006(6):110 －113.

［4］于海雯.海明碼的原理及其構造方法［J］.計算機與現代化，2001，72(2):148 －150.

［5］錢華明，李仲玉，馬吉臣，等.海明碼在提高導航數據傳輸可靠性中的應用［J］.微計算機信息，2008，24(12):225 －227.

［6］邸德家.海明碼的編碼解碼程序實現［J］.內蒙古石油化工，2007(2):115－117.

［7］陳雪麗.單片機原理及接口技術［M］.北京:化學工業出版社，2008:13－17.

［8］張濤，王金崗.單片機原理與接口技術［M］.北京:冶金工業出版社，2007:168－171.

［9］張玲，李磊民，劉剛.海明碼糾錯在無線遙控中的應用［J］.通信技術，2007，40(11):17 －19.

［10］呂菲，劉大偉.糾錯碼在通信系統中的應用［J］.軟件導刊，2008，7(4):17 －18.