提高汉明码对突发干扰的纠错能力 - 软件编程/OS - 电子工程

2dmin

<strong>引言</strong>

汉明码是在原编码的基础上附加一部分代码，使其满足纠错码的条件。它属于线性分组码，由于线性码的编码和译码容易实现，至今仍是应用最广泛的一类码。汉明码的抗干扰能力较强，但付出的代介也很大，比如8比特汉明码有效信息只有总编码长度的一半，可以纠正1个差错发现2个差错。在实际应用中常常存在各种突发干扰，使连续多位数据发生差错。为了纠正3个以上的差错，就要加大码距，使代码冗余度大大增加，通信效率下降。本文所介绍的方法，就可以在不加大码距的同时，提高汉明码对突发干扰所产生差错的纠错能力，纠正多位连续的差错。

<strong>1 汉明码纠错原理及设计</strong>

设原代码的码长为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化为二进制数，然后把它们作为矩阵的纵列，可得到的矩阵为：


<ignore_js_op>





2010-4-13 09:33:26 上传
<strong>下载附件</strong> (10.12 KB)




</ignore_js_op>


将包含单个1的4个纵列移到右边，在最后加1列全0的纵列，在第1行上面加1行全1的横行。这样就得到了[16,11,4]可纠正1位错误发现2位错误的增广汉明码校验矩阵。可以根据编程要求组织信息位和校验位的位置，最后得到矩阵如下：


<ignore_js_op>





2010-4-13 09:33:26 上传
<strong>下载附件</strong> (13.99 KB)




</ignore_js_op>


D1、D2、D4、D8是校验位，D16是全字节偶校验位，其余11位是信息位。校验码分别是C0=0AB61H，C1=0CDA2H，C2=0F1C4H，C3=0FE08H，C4=0FFFFH。

<strong>2 用汉明码对连续多位差错纠正的实现</strong>

要想在不加大码距的前提下，纠正连续多位差错，提高抵抗突发干扰的能力，可根据校验矩阵得出的汉明码重新进行组织排列。以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%，但比起出现多个差错后而要求发送方重发数据要好。

<strong>3 软件实现</strong>

下面给出基于最常用的MCS-51单片机汇编语言的汉明码测试程序。它的有效信息占到了总编码长度的70%，测试程序中自动生成11个字节的原始数据。

原始数据块的长度、存放地址可根据实际情况由用户自己确定，只要将本测试程序的汉明码编码、解码子程序嵌入用户应用程序中，就可直接使用。源程序清单请见网络补充版（http://www.dpj.com.cn）。

3.1 16位汉明码编码子程序

原始数据是11个字节，经过编码后是16个字节的汉明码。图1是汉明码编码子程序流程图。


<ignore_js_op>





2010-4-13 09:33:26 上传
<strong>下载附件</strong> (22.83 KB)




</ignore_js_op>


3.2 16位汉明码解码子程序

在解码之前可以人为地加入差错。差错要控制在1个字节内，否则出错标志将置位，后续处理可根据实际应用情况确定。图2是汉明码解码子程序流程图。


<ignore_js_op>





2010-4-13 09:33:26 上传
<strong>下载附件</strong> (34.64 KB)




</ignore_js_op>


<strong>结语</strong>

本文针对汉明码在实际应用中对突发干扰所产生多位差错纠错能力低的缺点，提出了相应的解决方案。此方法通过笔者的实际使用，证明了这种方案是可行的尤其对于一些无线数传设备，采用这种方案后可以有效纠正突发干扰所产生的差错。

<strong>参考文献</strong>

1. 周航慈.饶运涛 单片机程序设计基础 1997
2. 周航慈.孙丽华.王仁波 信息技术基础 2002
3. 周航慈 单片机应用程序设计技术 2002

作 者：东华理工学院 赵建武 周航慈
来 源：单片机与嵌入式系统应用2004（1）