扩展汉明码的交织重排算法研究及其实现

文章编号: 1001 9081( 2012) S1 0085 03扩展汉明码的交织重排算法研究及其实现梁红玉* ，陈冬梅( 桂林电子科技大学 信息与通信学院，广西 桂林 541004)( * 通信作者电子邮箱 lruby guet edu cn)摘 要: 从信道纠错编码的基本思想出发，讨论了汉明码、扩展汉明码以及交织的纠错检错能力，提出了对扩展 汉明码进行交织重排的算法。然后采用 C 语言对该算法进行程序设计，验证了该算法的可行性。结果表明: 此种算 法具有较强的抗干扰能力，提高了传输数据的可靠性。关键词: 扩展汉明码; 交织重排; 信道编码中图分类号:文献标志码: ATN915 01Research and realization of interlace and rebuild algorithm of extended Hamming codeLIANG Hong-yu* ， CHEN Dong-mei( School of Information and Communication， Guilin University of Electronic Technology， Guilin Guangxi 541004， China)Abstract: On the basic principle of channel error-control coding theory， the ability of detecting and correcting errors wasdiscussed between Hamming code and extended Hamming code， then the principle of interlace and rebuild of extended Hamming code was introduced Programs were written in C language to demonstrate and prove the algorithm The results prove that the algorithm of interlace and rebuild of extended Hamming code has robust ability of anti-disturbing to enhance the reliability of data transmissionKey words: extended Hamming code; interlace and rebuild; channel coding在信道编码中，汉明码是目前运用的一种高效的线性分组码。由于其编码和译码容易实现，至今仍是应用最广泛的 一类码1 5。在汉明码的基础上按规则增加一位奇偶校验码 构成扩展汉明码，可增加检错纠错的能力6 12。然而在实际 通信系统中常常存在各种突发干扰，使连续多位数据发生差 错。重新设计一种更有效的纠错编码，将几种编码有效地结 合起来提高纠错能力，这些都是设计实际系统时所必须考虑 的重要问题。本文在分析汉明码编译码基础上，提出了对汉明码进行 扩展并且交织的算法，同时用 C 语言在 VC 环境下实现了扩 展汉明码交织算法，进一步验证该方法的可行性。发来构造一个新的线性分组码，使得某些参数能符合实际的需要，扩展码就是一种。假设 是一个 ( n，k) 线性分组码，其中某些码重为奇数。若对每个码组 c = ( c ，c ，c)增加一个奇偶验位 c 使0 1n 10得满足 c0 + c0 + c1 + + cn 1= 0。这样的码 经全校验位扩展后得到一个 ( n + 1，n) 线性码 c0 。若 的最小重量为 d 是奇数，则 0 的最小重量是偶 数 d + 1，汉明码距也增加了一位，变为 dmin = 4。若原来的 的校验矩阵为 H，则 c0 的校验矩阵为:11 1= 0( 1)H0 0 H1汉明码线性分组码是信道编码中重要的一类编码方式，其表示2 1 2 译码原理设发送码组 A过 程 中 可 能方式为 ( n，k) 其中 k 为位信息码元个数，n 为编码后总位数，r = n k 位监督位。其原理是在发送端编码采用 r 位监督码 元与 k 位信息码元之间建立一定的校验关系，在发送端利用 该校验关系对收到的 n 位码元进行检错纠错。在线性码中，= an ， an 1 ， ， a1 ， a0 ，在传输发 生 误 码。 接 收 码 组 B=bn ， bn 1 ， ， b1 ， b0 ，则收发码组之差定义为错误图 样 E，也称为误差矢量，即其中 E = en ， en 1 ， ， e1 ， e0 ，且1 6最小码距 dmin 决定了检错纠错的能力 。通常把最小码距= 3 ，码长 n 与监督位个数 r 满足关系式 n = 2 1 的线rdmin0， bi = ai1， bi ai性码就成为汉明码2，4，6。汉明码是一种高效的完备码，编译 码容易实现，只能纠正 1 位错，但不能检错2 5。e =iS 称为伴随式或校正子，计算公式如下:扩展汉明码及其交织原理2S = BHT = ( A + E) H = AH + EH = EH0000TTTT( 2)02 1 扩展汉明码编译码原理6 10扩展汉明码的出现弥补了汉明码原有的不足，它增加了1 位校验位，最小汉明距增加到 4，增加了检 2 位错位能力。接收端收到每个码组后，可以根据编码规则倒推回去。可以根据式( 2) 来求出一个校正子组，若为 0 则表示无误，否则表示有误码。把得到的校正子依次与监督矩阵按列比较，编码原理找到与校正子相同的那列监督位以及接收码中的误码位，对其取反即可。2 1 1在信道编码中，通常从一个已知的 ( n，k) 线性分组码出收稿日期: 2011-12-31; 修回日期: 2012-02-10。作者简介: 梁红玉( 1974 ) ，男，山西文水人，讲师，硕士，主要研究方向: 通信信号分析处理、无线通信;陈冬梅( 1976 ) ，女，湖北荆门 人，讲师，硕士，主要研究方向: 移动通信、通信网络、无线传感器网络。突发错误则无能为力。但是如果结合交织与重排原理，突发错误就可以转变为随机错误来解决。交织是把经过扩展汉明 编码的码字顺序重新排列，不加冗余比特所以交织前后码距 不变2，10，12。原理如图 1 所示。infora = 000001 0 0 101 1对应的扩展汉明码为:inforb = 01 1 00000111010111011 100 0图 1 扩展汉明码交织器原理交织器和解交织器( 以一个 3 8 交织器为例) 的实现步 骤如下:对于传输过程中可能出现的各种干扰分下面 3情况来讨论。1) 输入 信 号 经汉明码编码器后生成发送序列 X1x1 x2 x3 x24 。2) 发送端交织器将数据序列存储为一个行列交织矩阵A1 ，它按行写入，按列读出。= x1x2x10x18x3x11x19x4x12x2x5x13x21x6x14x22x7x8 A1 = x9 x17x15x16 x23x24 交织器输出后送入信道的数据序列为 X2x2 x10 x18 ，x8 x16 x24 。= x1 x9 x17 ，3) 假设在突发信道中，由于信道衰落和噪声干扰的影 响，使传输的信号发生误码，第一个突发错误出现在 x1 x9 x17 ， 第二个突发错误出现在 x8 x16 x24 ，则经突发信道后的输出信号 序列为 X3= x1 x9 x17 ，x2 x10 x18 ，x8 x16 x24 在接收端，信号经解交织器，解交织器也是一个行列矩阵存储器，它按列写入，按行读出，与交织器规律相反，即: x1x8x2x10x18x3x11x19x4x12x2x5x13x21x6x14x22x7x15x23 x16A2 = x9 x17x24图 2 算法实现流程1) 无误传输，tt = 0。在传输过程中不引入误码，对接 码计算校正子矩阵得: 经解交织器后输出信号为 X4 = x1 x2 x3 x4 x5 x6 x7 x8 x9 通过以上分析，增加交织器和解交织器x10 x15 x16x17x18 x24后，原来信道中的连续差错变成了随机错误。S = 000000 0 0 0程序设计与验证用 C 语言在 VC 环境下编程实现汉明码、扩展汉明码和 扩展汉明码的交织重排。程序分析交织深度为 3 的交织 ( 8，4) 扩展系统汉明码，进行数据传输或存储，并引入各种误码 情况，讨论该算法的检错纠错能力。300 0全 0 校正子矩阵证明了信息传输无误，在图 3 中得以体现编程设计流程在信道传输前先将待传输的 3 组数据编码为扩展汉明 码，编程思想按照图 2 流程来编写。3 1程序实现与验证选用四位监督位的扩展汉明码 ( 8，4) 码。矩阵多项式 系数同样输入 h1 = 7，6，5，4，3，2，1，即表示监督矩阵多项 式为 H1 = 7a6 ，6a5 ，5a4 ，4a3 ，3a2 ，2a1 ，1a0为 ( 7，4) 汉明码 的监督矩阵，对于扩展汉明码还必须在其基础上增加一个全0 的末列一个全 1 的头行，这样运行程序构造监督矩阵为:3 2 1 1 1 11110110110111100101010011 0 0 0 H0 =图 3 无误码传输( 去掉了底色)2) 3 位误码传输，tt = 3。交织深度为 3，这里 h1 选用三在程序运行中选择交织深度为 c = 3，即同时对 3 组扩展连续误码，起始位为第 1 位。由程序运行可见，接收码子错在第 1 位、第 2 位和第 3 位。程序运行如图 4，计算得校正子矩 阵为:了交织深度，译码就会出错。这里选择突发错误为 4 位，程序运行如图 5 所示。校正子为:S = 100111 1 1 0S = 1111171 1 1 111 17SS = 1 71SS =71 17最终的译码结果表明，第 1 位是错误译码，第 2 位和第 3位是正确译码。倘若连续误码再多，或者说误码位数超出交 织深度得更大，超出几位也就会错误译码几位。最终译码结果与理论上是一致的。可见扩展汉明码结合交织重排，可以将突发错误转变为随机错误来纠错译码。结语扩展汉明码是早期的一种纠错编码，是在汉明码基础上 增加了一个奇偶校验位，最小汉明距增加到 4 位，所以能纠错1 位和检错 2 位误码2，4，11 12。但是扩展汉明码本身只能解 决随机错误，如果结合其他编码，如交织码，就可以将突发错 误转化为随机错误，其能力取决于交织器器的交织度，交织度 越深，抗突发错误能力越强。参考文献:4王新梅，肖国镇 纠错码: 原理与方法M 西安: 西安电子科技大学出版社，1991: 52 79曹志刚， 钱亚生 现代通信原理M 北京: 清华大学出版社，1992: 331 338常同 信息理论基础M 北京: 清华大学出版社，2004: 156 158甘家宝 汉明码校验原理解析J 微型电脑应用，2007，23 ( 1 ) :58 60阎华， 范宇 差错控制编码技术应用研究J 航空兵器，2005 ( 4) : 30 34王爱珍 扩展汉明码的编解码器的设计及其 FPGA 实现J 现代电子技术，2008，31( 19) : 187 191盛蒙刚 汉明码编译码的 FPGA 设计与实现J 山西电子技术，2007( 6) : 43 47余莹，吴国芳，邓家梅，等 并行级联扩展汉明码的研究J 无线 电工程，2000，30( 1) : 41 42，62方国涛 基于 FPGA 的汉明码编译码系统J 信息技术，2010 ( 7) : 79 81123 图 4 三位误码传输 ( 去掉了底色)456789 10 王刚，高宏亮 基于 FPGA 交织编码的设计与实现J 哈尔滨理工大学学报，2009，14( 1) : 63 6611 章学静，薛琳等 汉明码及其编译码算法的研究与实现J 北京 联合大学学报，2008，22( 1) : 46 4912 KUMAR U K， UMASHANKAR B S Improved Hamming code for error detection and correctionC / / 2nd International Symposium on Wireless Pervasive Computing S l : IEEE，2007: 498 500图 5四位误码( 去掉了底色)3 ) 有3 位以上误码传输，7 t t 3 。只要误码位数超出( 上接第 84 页)参考文献:C / / 14th International Conference on Field-Programmable Logicand Applications Antwerp: Springer，2004: 852 856HUANG D， KAHNG A Partitioning-based standard-cell global placement with an exact objective C / / Association for Computing Machinery Symposium on Physical Design New York: Kluwer Aca- demic Publishers， 1997: 18 25SIGL G， DOLL K， JOHANNES F Analytical placement: a linear or a quadratic objective function C / / 28th ACM / IEEE Design Automation Conference New York: ACM Press， 1991: 427 432 McMURCHIE L， EBELING C PathFinder: a negotiation-based performance-driven router for FPGAsC / / Proceedings of Associa- tion for Computing Machinery International Symposium on Field-Pro-grammable Gate Array New York: ACM Press， 1995: 111 1171BETZ V， ROSE J VPR: a new packing， placement and routingtool for FPGA research C / / Proceedings of the 7th International Workshop on Field Programmable Logic and Application London: Springer， 1997: 213 222LEE S-J， RAAHEMIFAR K FPGA placement optimization method- ology survey C / / Canadian Conference on Electrical and Comput- er Engineering 2008 Vancouver: CCECE， 2008: 1981 1986 VORWERK K， KENNINGS A， GREENE J W Improving simulated annealing-based FPGA placement with directed moves J IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2009， 28( 2) : 179 192DANILIN A， SAWITZKI S Optimizing the performance of the sim-ulated annealing based placement algorithms for island-style FPGAs526374