矩阵分析在汉明码中的应用.DOC

1、矩阵分析在汉明码中的应用摘要：数字信号在传输过程中，由于受到干扰的影响，码元波形将变坏。接收端收到后可能发生错误判决。由于乘性干扰引起的码间串扰，可以采用均衡的办法来纠正。而加性干扰的影响则需要用其他办法解决。在设计数字通信系统时，应该首先从合理选择调制制度，解调方法以及发送功率等方面考虑，使加性干扰不足以影响到误码率要求。在仍不能满足要求时，就要考虑采用差错控制措施了，本文在基于矩阵分析的基础上对汉明编码进行介绍，效率高，提高抗突发干扰的能力。关键词：矩阵分析 汉明码引言矩阵如今在各个领域都有广泛的应用，例如在生活中，在经济中，在通信领域，数字图像领域中等各个方面应用很广泛。在生活中的魔方也

2、是根据矩阵分析，在 excel 表格中，我们可以根据矩阵很简单的计算出各行各列的和，在数字图像处理中，我们将图像用矩阵表示，像素来表示，一个像素代表一点，有很多像素组成一幅数字图像，再对矩阵进行各种变换从而实现数字图像处理，在通信领域中我们也经常用到矩阵，例如编码，我们下面将对矩阵分析在汉明编码中的应用进行具体分析1.汉明码编码Hamming码中文称作汉明码。汉明码是由汉明于1950年提出的，具有纠正一位错误能力的线性分组码 它的突出特点是：编译码电路简单，易于硬件实现；用软件实现编译码算法时，软件效率高；而且性能比较好.1.1 汉明码的定义：若一致监督矩阵H 的列是由不全为0且互不相同的所有

3、二进制m(m2的正整数)重组成，则由此H矩阵得到的线性分组码称为2 m-1,2m-1-m，3汉明码。1.2 汉明码的构造特点：1)绐定一个m，我们由二进制m 重组成线性分组码的监督矩阵H，由二进制m重来标定一个发生错误的位置。由此可知，二进制m 重共有2 种位组合，去掉一个全为0的位组合，则余下共有2 m-1种位组合。故汉明码的最大码长n=2 m-1。2)由上面分析，我们可以知道：m 即是汉明码监督位的位数。故一个汉明码中，信息位的位数k=nm=2 m-1-m3)汉明码的距离为 3，因此可以纠正 1 位错误，检出 2 位错误。1.3 汉明码编码的主要算法汉明码的编码就是如何根据信息位数k，求出

4、纠正一个错误的监督矩阵H，然后根据H求出信息位所对应的码字。构造汉明码监督矩阵H的方法很多，这里仅介绍一种。1)根据已知的信息位数k，从汉明不等式中求出校验位数m=n-k；2)在每个码字C：(C 1，C 2， ，C 2m -1)中，用c 02 ，c 12 ，c n-12作为监督位，剩下的位作为信息位；3)用二进制数字表示2 m-1 列，得到2 m-1列和m行监督矩阵H；4)用3步的H形成HC T =0，从而得出m个监督方程；5)将已知的信息代入方程组，然后求出满足上述方程组的监督位c (i=0，1， ，m一1)。例如，用以上方法，很容易求出7，4，3汉明码的监督矩阵：1 1 1 0 1 0 0

5、 H= 1 1 0 1 0 1 0 1 0 1 1 0 0 1及编码所对应的码字为C=011001。对于码组长度为 n、信息码元为 k 位、监督码元为 rnk 位的分组码，常记作（n，k）码，如果满足 2r1n，则有可能构造出纠正一位或一位以上错误的线性码。下面我们通过（7，4）汉明码的例子来说明如何具体构造这种码。设分组码（n，k）中，k = 4，为能纠正一位误码，要求r3。现取r3，则nkr7。我们用a 0ala2a3a4a5a6表示这7个码元，用S 1、S 2、S 3表示由三个监督方程式计算得到的校正子，并假设三位S 1、S 2、S 3校正子码组与误码位置的对应关系如表1所示。S1S2S

6、3 错码位置 S1S2S3 错码位置001 a0 101 a4010 al 110 a5100 a2 111 a6011 a3 000 无错码表1 校正子和错码位置关系由表可知，当误码位置在a 2、a 4、a 5、a 6时，校正子S 11；否则S 10。因此有S1a 6a 5a 4a 2，同理有S 2a 6a 5a 3a 1和S 3a 6a 4a 3a 0。在编码时a6、a 5、a 4、a 3为信息码元，a 2、a 1、a 0为监督码元。则监督码元可由以下监督方程唯一确定a6a 5a 4a 2 = 0a6a 5a 3a 1 = 0 (1.1.1)a6a 4a 3a 0 = 0也即a2a 6a

7、5a 4a1a 6a 5a 3 （ 1.1.2）a0 = a6a 4a 3由上面方程可得到表 2 所示的 16 个许用码组。在接收端收到每个码组后，计算出 S1、S 2、S 3，如果不全为 0，则表示存在错误，可以由表 1 确定错误位置并予以纠正。举个例子，假设收到码组为 0000011，可算出 S1S2S3=011,由表 1 可知在 a3上有一误码。通过观察可以看出，上述（7，4）码的最小码距为 dmin3，纠正一个误码或检测两个误码。如果超出纠错能力则反而会因“乱纠”出现新的误码.信息位 监督位 信息位 监督位a6a5a4a3 a2a1a0 a6a5a4a3 a2a1a0000000010

8、0100011010000001110111011010001001101010111100111100010001001010101100111101011000110111101111010100111表2 （7,4）汉明码的许用码组2.监督矩阵上面有提到过，线性码是指信息位和监督位满足一组线性代数方程的码，式(1.1.1)就是这样的例子，现在将它改写成1*a61*a 51*a 40*a 31*a 20*a 10*a 0=01*a61*a 50*a 41*a 30*a 21*a 10*a 0=0 (1.1.3)1*a60*a 51*a 41*a 30*a 20*a 11*a 0=0 我们可

9、以将式（1.1.3）表示成如下的矩阵形式a6a51 1 1 0 1 0 0 a4 01 1 0 1 0 1 0 a3 = 0 （1.1.4）1 0 1 1 0 0 1 a2 0 a1a0式（1.1.4）还可以简记为 H*A T=0T 或 A*H T=0 （1.1.5） 其中1 1 1 0 1 0 0 H= 1 1 0 1 0 1 0 A= a6a5a4a3a2a1a0 0= 0001 0 1 1 0 0 1上角“T”表示将矩阵转置。例如H T是H的转置，即H T的第一行为H的第一列，第二行为第二列。我们将H称为监督矩阵(paritycheck matrix).只要监督矩阵H给定，编码时监督位和

10、信息位的关系就完全确定了。由（1.1.4）和(1.1.5)都可以看出，H的行数就是监督关系式的数目r，H的每一行中的“1”的位置表示相应码元之间存在的监督关系。式（1.1.4）中的H矩阵可以分为两部分。1 1 1 0 1 0 0H= 1 1 0 1 0 1 0 = PIr (1.1.6)1 0 1 1 0 0 1式中：P为r*k阶矩阵；I r为r*r阶单位方阵。3. 生成矩阵由代数理论可知，H矩阵的的各行应该是线性无关的，否则将得不到r个线性无关的监督关系式，从而也得不到r个独立的监督位。若一矩阵可以写成PI r的矩阵形式，则其各行一定是线性无关的。因为容易验证I r的各行是线性无关的，故PI

11、 r的各行也是线性无关的。类似于（1.1.1）改成（1.1.4）那样， （1.1.2）可以改写成a6a2 1 1 1 0 a5a1 = 1 1 0 1 a4 （1.1.7）a0 1 0 1 1 a3或者1 1 1a2a1a0 = a6a5a4a3 1 1 0 = a6a5a4a3 Q (1.1.8)1 0 10 1 1其中，Q为一个k*r阶矩阵，它为P的转置，即Q=PT式（1.1.8）表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位。我们将Q的左边加上一个k*k阶单位方阵，就构成一个矩阵G1 0 0 0 1 1 1G= IKQ = 0 1 0 0 1 1 0 (1.1.9)0 0

12、1 0 1 0 10 0 0 1 0 1 1G称为生成矩阵（generator matrix） ，因为由它可产生整个码组，即有a6a5a4a3a2a1a0 = a6a5a4a3 G= A (2.2.0)4.(7,4)汉明码的编码思路(7,4)汉明码的编码就是将输入的四位信息码编成七位的汉明码，即加入三位监督位。根据式(2.2.0）A = a 6 a5 a4 a3 G 可知，信息码与生成矩阵 G的乘积就是编好以后的(7,4)汉明码，而生成矩阵 G 又是已知的，由式(1.1.9)得1 0 0 0 1 1 1G = 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1所

13、以，可以得出如下方程组a6 = a6a5 = a5a4 = a4a3 = a3 (2.2.1) a2 = a6 + a5 + a4a1 = a6 + a5 + a3a0 = a6 + a4 + a3参考文献1 史荣昌，魏丰；矩阵分析；北京理工大学出版社；2 雷章富;汉明码的串行检测法J;桂林电子工业学院学报 ;1983 年 02 期；3 饶世麟; 第九讲 信道编码浅说 J;遥测遥控;1984 年 02 期；4 王可; 数字通信中的密码技术和差错控制技术(一 )J;中国空间科学技术;1985年 01 期；5 朱江;宋利民 ;陈俊;李奎; CPLDFPGA 在数字通信系统的应用 一种(7,4)汉明码的硬件实现A; 中国航海学会通信导航专业委员会 2006 年学术年会论文集C;2006 年；6 陈丽萍;基于纠错码的水印技术研究D; 福建师范大学;2005 年。