单片机实现海明码纠错原理的研究

张福军 宋铁军 刘 坤

(黑龙江八一农垦大学信息技术学院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.