矩阵理论在纠错编码中的应用

第!卷 第#期!年$月北京工商大学学报%自然科学版&()*+,-(./0 1 2 1+34 0 5 6+(-(3 7,+8/)9 1+0 9 9:+1;0*9 1 7%=,5 1 0+5 0?8 1 1(+&(-A!=(A#B,*A!文章编号C#D E#F#G#$%!&#F G H F I矩阵理论在纠错编码中的应用宋世敏%北京工商大学 数理部J北京#$E&摘要C利用矩阵理论解决通信中纠错编码问题J同时对卷积编码进行研究J有效地解决了无线数据通信中抗突发错误的问题J并用K语言进行编程L关键词C概率M矩阵M通信M差错M控制M码中图分类号CN#G#A!#MN!$D A!文献标识码CO收稿日期C!#P#H作者简介C宋世敏%#P D$Q&J女J北京人J讲师J主要从事经济数学研究L围绕无线数据通信中抗突发错误的问题J运用矩阵理论及概率论基础知识J设计了一种纠错编码方法L纠错编码对数据传输的可靠性是非常重要的R特别是在战争环境下J电子战异常激烈J电磁环境非常复杂J数据传输中的干扰将更加严重J可靠性将受到更大的威胁L在今后的通信和计算机系统设计中J纠错码会得到越来越广泛的应用LS卷积码的编码模型T#US A S V%W J S J S&码的编译码该码的编码器如图#所示L其约束度XY!JZY!JY#J Y#L若每一时间单位编码器输入一个新的信息元J且存储器内的数据往右移一位J则一方面直接输出至信道J另一方面与前两个单位时间送入的信息元 Q#Q!按图中线路所确定的规则进行运算J得到此时刻的两个校验元_ Q#_ Q!J跟随在后面组成一个子码Y%J_ Q#J _ Q!&J送入信道L显然J其监督方程为CaYb Q#易于导出监督矩阵为T#UCcY#R R#R R#R R R R#R R#R R 其码序列为C Y%d#d!d#d#!d!#d!ee&信道错误序列为Cf Y%g#g!g#g#!g!#g!ee&接 收序列为C hY%i#i!i#i#!i!#i!ee&J其伴随式为Cj Yh ckY%lf&ckYf ckY%j#j#j!#ee&根据矩阵运算结果J伴随式的相应各个分量如下Cm#Yg#bg!m#Yg#eeebg#bg#!m!#Yeeeeeeg#eeebg!#bg!nopeeee第分组的错误信息只在m#m#两个分量中出现J假定在约束长度内只发生一位错码J由于Z Y!J则当#&m#Y#J m#Y#时J可以判断g#Y#J即认为i#是错误的L!&m#Y#J而m#Y或m#Y J而m#Y#J可以判断g#Y J即认为i#无错L$&m#Y J m#Y J g#Y J即i#无错L可见J只要考察两个监督子%伴随式&分量J就可确定i#qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q是否发生错误!#$同样%由监督子分量&(%()可以确定接收序列中第(分组的信息数字*(是否正确$其他依次类推$由+(,&+-()(能够确定第+组信息元*+(是否正确$&%(%()卷积码的反馈译码器如图所示$图中%伴随式计算电路与编码电路一致$如果在译第.个接收信息数字*.(时%发现*.(错了%即/.(0(%算出.(0(和(0(%就利用.(,(的两个1(2使之通过一个与门电路给出一个1(2%这个1(2与*.(一起送入输出端的模加法器%使最后所译出的第.组的信息数字3.0*.(-(%从而得到正确的译码%即3.03.%此3.为原发端第.组信息数字$如果*.(没有错%即/.(0.%则.(,(只可能为&.%.)%&(%.)%&.%()这三种可能的任一种%与门给出的是1.2%译码输出为3.0*.(03.%也是正确的译码$这里需要指出的是%译*.(所需的两个监督子分量.(和(%都是由伴随式计算器的模加法器给出的%它们相差一个时间单元%因此需要一级移位寄存器来存放&4()%即在(移出时%.(则已进入4(中%此电路称为错误图样检测电路$根据.(,(的不同而分别给出.或(%以此来得到信息元的正确译码$在第.分组的信息元3.译出之后%就要顺次利用(,(对第(分组的信息元进行译码%也就是对*(进行判决$已知5(0/.(-/(-/(066/(66-/(-/在(中%包含了第.分组信息的错误图样/.($当/.(0(时%说明*.(有错%在(中反映了此信息$如果直接用(,(来判决*(%将要造成错判%所以在译*(之前就要消除/.(对(的影响$当/.(0(时%与门的输入是(7当/.(0.时%与门的输入是.%即与门的输出为/.($利用与门输出的/.(%经过反馈电路对监督子分量进行修正5 8(0(-/.(0/(-/(8(0(660/8(6-/8(-/8 利用 8(,8(来对*(译码%就和利用.(,(来对*.(译码完全一样了$这种每译一步就同时对监督子分量进行一次修正的办法称为监督子重调&或称监督子复位)$由于重调监督子用的是反馈电路%所以把这种译码方法叫做反馈译码法$这种译码器的具体译码步骤为5()第.分组的接收序列*.(,*.送入之前%上层寄存器4内为.%下层寄存器4(也为.$在*.(,*.送入后%得.(0*.(-*.0/.(-/.$)第(分组*(,*(送入后%*.(移入4%.(移入4(%此时计算出的(0*.(-*(-*(0/.(-/(-/($9)当/.(0(%原发信息码元为:.(03.%*.(03.-/.(%此时.(0(&假定在约束长度内仅(位错%即/.(0(%*.(有错%其他位均不错%/.0/(0/(0.)%(0($与门输出为1(2%输出3.0*.(-(03.-/.(-(03.-(-(03.即译码是正确的$同时与门所给出的1(2%经反馈电路后%修正了监督子 8(0(-(0/(-/($当/.(0.%即信息位无错%*.(03.($.(,(为.%或(.%或.($与门给出.%无须纠错%3.03.$;)一般%当要对第+分组信息位*+(进行译码时%该组接收信息元*+(已储入上层寄存器4%输入端为第&+-()组的*&+-()7下层寄存器4(已存入监督子&伴随式)分量 8+(0/+(-/+%新算出的监督子分量为&+-()(0/+(-/&+-()(-/&+-()$如果/+(0(%则+(0&+-()(0(%与门输出为1(2%输出为3+0*+(-(03+-/+(-(03+%同时反馈修正5 8&+-()(0&+-()(-(0/&+-()(-/&+-()$如果/+(0.%即*+(03+%则与门输出为1.2%不予纠正%3+0*+(03+$这样一组一组进行下去%直到译完为止$&?%)码的性能分析&9%(%)码的代数计算较好%编码实现电路比较容易%译码电路也相对容易%而且%由于它是每一位信息元伴随两个监督元%因此纠错能力比&%(%(%)码要强$但是%对于长突发错%它的纠错能力就不够了$&%(%()码在译码时假定在约束长度内只有一位错%而实际上有可能发生两位以上的错误%这样译码时就会产生误码$如果采用维特比&AB C D E F B)译码的话%就能降低误码率$采用&9%(%)码以上的编码方式%固然能提高纠错能力%但它们的算法,实现电路以及性能分析都复杂%处理速度慢%综合考虑GH第.卷 第(期宋世敏5矩阵理论在纠错编码中的应用是不合算的!故选用#$!%!%&码构造编码(模型的计算机算法()*采用按字节编码的+#(!*!*&码#$!%!%&码虽然是最简单的卷积码!纠错能力也最低!但至少可以达到,个码纠正%个!并不比其它码差很多在经过交织后可纠错%-,!完全可以满足大部分工程应用的需求!其编.解码显然比其它码要简单得多!易于实现!可靠性较高一般的卷积编码多用硬件实现!这使得在编.解码过程中往往按位处理#如图/所示&但是!如用软件实现纠错编.解码仍按位处理!就显得不尽合理现在无论是什么机型!在处理数据时都是八位以上按位编.解码不能充分利用计算机资源!并且必须将码元进行分组!使整个过程变复杂!因而效率很低而按字节编.解码则不存在分组问题!且能充分利用处理器资源!使整个过程简单化!因此大大提高了编.解码效率0/1由于采用了按字节编.解码的#$!%!%&码!编.解码的软件实现变得简单.高效!只需一段很短的程序#$!%!%&码可作为一个信道差错控制模块!插入到各所需数据传输的工程中!使其不必付出很大代价!便可大大提高数据传输的可靠性()(按字节的#(!*!*&码编.解码方法如图,所示!若每一时间单位编码器输入一个新的信息元23字节!且八位寄存器内的数据移出一个字节!则23一方面直接输出至信道!另一方面!与前一个单位时间送入的信息元23 4%!按图中线路所确定的规则进行运算!此时刻得到的一个校验元53 4%!跟随在23后面!组成一个子码637#23!53 4%&!送入信道显然!其监督方程为853723923 4%其码序列为86 7#6:%6:$6%6%$6$%6$;&信道错误序列为8 7#:%:$%$%7=?7#6 9&?7:%$%;&根据矩阵运算结果!伴随式的相应各个分量如下8A:%7:%9:$A%7:%;9%9%$A$%7;%;9$%9:%F:!%F:时!可以判断:%与%中同时不为:的位即为=:%的错误位$&:%F:!而%7:或:%7:!而%F:!可以判断:%7:!%7:!:%7:!即=:%无错可见!只要考察两个监督子#伴随式&分量!就可确定=:%中是否有某位发生错误译码时!无须译出监督元其译码也和按位的#$!%!%&码极为相似!不同之处在于每次送入的不是一位!而是一个字节!采用的寄存器均为G位!其具体过程不再重复H对编码模型实验的分析结合上面对其编码方法的分析!比较图/.图,!从中可以看出8按字节编码!虽不同于严格意义上的#$!%!%&卷积码!但在本质上是G组按位编码并行执行的结果因而!应具有与之相同的纠错能力!并且由于其一个字节内的各位互不相关!在不交织的情况下!显然比按位的#$!%!%&卷积码具有更强的抗长干扰能力例如!其至少可以纠正连续,个字节中的一个字节的错误#指该字节中没有一位是对的&!也可以纠正连续,个字节的错误!当然!其前提是在这,个连续字节中不能有相同位的错误这样的纠错能力!在不进行交织的情况下!用按位的#$!%!%&码:I北京工商大学学报#自然科学版&$:$年/月是难以达到的!部分程序如下#$%&()*+,-)$./0 12.$)34$%5 67,-4-$&0 4 8 4 9:;=,*%)-.9:;?.8 5$A$BC$DD67$?5$A 67 4 A;E;3;E;FG寄存器%;E;FG H寄存器.;E I;4 A;J;E;A KL M N:O M P:M O Q L 8 A,:-M R 8 F8;:(M R,2(PA F8;AS3T-T2 FU S为,5 M DA 6 A32 E SR%$?5 E;67 V 5&0 4 8 6 2 FV为输出%S F,H M AK*,*7 V 5&0 4 8 6 5 2TJ 6%STJ KV 4 A Q V 4 A V V V NA KK参考文献9 A 西安交通大学数学教研室/矩阵理论9 W/西安西安交通大学出版社=A X X;/9:王成名=余鑫晖/应用概率统计9 W/南宁广西师范大学出版社=A X X C/9 Y 王新梅=肖国镇/纠错码Z原理与方法9 W/西安西安电子科技大学出版社=A X X /_ a _ b cb de a f _ ga hi b f ja b b f f i a _ c ki f f b f b l i mn opqn 0$r 3$%5 st u v w x yt z x|v x t yv x!#v z$%&#!#=t!(!z)*t z +)&v z$,#!z t#-z!.t w#!x&=t!(!z)A;Y/=0 !z v 6 1 2 3 4 5 6 3 n.2*)-0*O(*,-$.%-.&.8 8*&-$%7*8 8.8&.)*,$%&.33(%$&4-$.%8 V-0*34-8$E-0*.8 V=W*4%-$3*=)$),.3*8*,*4 8&08 V3*4%,.?&.%2.(-$.%4&.)*,/9 0(,=*?$&$*%-V,.2*)-0*L 8.8 r*3-.8*,$,-$%7,()*%*8 8.8,$%S$8*,)4-4&.33(%$&4-$.%8 V3*4%,.?-0*L 8.7 8 4 33$%7.?:r 4%7(4 7*/;?4 2 L 8.8 4 8$-V 34-8$E&.33(%$&4-$.%*8 8.8&.%-8.&.)*5责任编辑李爱华6A第:;卷 第A期宋世敏矩阵理论在纠错编码中的应用