單片機(jī)實(shí)現(xiàn)海明碼糾錯(cuò)原理的研究

張福軍 宋鐵軍 劉 坤

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

0 引言

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

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

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

1 海明碼的編碼原理

1.1 海明碼的基本原理

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

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

根據(jù)Hamming不等式可以得出對(duì)應(yīng)不同校驗(yàn)位的編碼長(zhǎng)度，如表1所示。

表1 校驗(yàn)位對(duì)應(yīng)的編碼長(zhǎng)度Tab.1 Encoding lengths vs.checking bit

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

1.2 海明碼的編譯碼過(guò)程

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

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

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

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

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

表2 海明碼校驗(yàn)位Tab.2 Hamming code checking bit

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

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

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

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

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

2 單片機(jī)海明碼糾錯(cuò)原理

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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

［1］趙軍軍.海明碼在微機(jī)信息傳輸中的糾錯(cuò)原理與應(yīng)用［J］.寶雞文理學(xué)院學(xué)報(bào)，1997(1):54－57.

［2］梁紅，王英煥.軟件差錯(cuò)控制在單片機(jī)通信中的應(yīng)用［J］.鞍山鋼鐵學(xué)院學(xué)報(bào)，1998，21(4):31 －33.

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

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

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

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

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

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

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

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