張福軍 宋鐵軍 劉 坤

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

0 引言

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

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

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

1 海明碼的編碼原理

1.1 海明碼的基本原理

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

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

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

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

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

1.2 海明碼的編譯碼過程

利用單片機軟件實現(xiàn)海明碼的發(fā)送與接收，必須首先了解海明碼的編碼規(guī)則。海明碼編碼規(guī)則如下。

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

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

假設待發(fā)送的數(shù)據(jù)信息為一個字節(jié)，由表1可知，需要4位校驗位，這樣16種狀態(tài)可以包含12位數(shù)據(jù)中的每一位，其中包括8位數(shù)據(jù)位和4位校驗位。

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

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

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

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

狀態(tài)碼與錯誤信息位的對應關(guān)系如表3所示［4－5］，若沒有錯誤，狀態(tài)碼為 0000。

表3 狀態(tài)碼與錯誤信息位的對應關(guān)系Tab.3 Status codes vs.error information bit

根據(jù)表3的狀態(tài)碼對應關(guān)系，在接收端只要得到狀態(tài)碼即可糾正錯誤的信息位，實現(xiàn)糾錯的功能。

2 單片機海明碼糾錯原理

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

2.1 單片機軟件實現(xiàn)海明碼的發(fā)送

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

圖1 發(fā)送程序流程圖Fig.1 Flowchart of sending program

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

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

2.2 單片機軟件實現(xiàn)海明碼的接收

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

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

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

3 結(jié)束語

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

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

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

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

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

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

［6］邸德家.海明碼的編碼解碼程序?qū)崿F(xiàn)［J］.內(nèi)蒙古石油化工，2007(2):115－117.

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

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

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

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