约束维特比译码算法的性能研究

约束维特比译码算法的性能研究 约束维特比译码算法的性能研究 14福建电脑2006年第8期 约束维特比译码算法的性能研究 陈东侠,余轮,许明,周霆 (福州大学物理与信息学院福建福州350002) 【摘要】:维特比译码是一种最大似然译码,在数字通信系统中得到广泛的应用. 约束维特比算法是利用已知的正确信 息.对维特比算法进行改进.本文针对约束维特比算法进行了探讨,并对其性能进 行了仿真实验.仿真结果证明,在二进制均 衡信道中当采用约束维特比算法时.性能得到了较大的提高. 【关键词】:维特比算法约束二进制均衡信道 1.引言 卷积码f11在数字通信系统『21中得到了广泛的应用.卷积码 不是把信息序列分组后再进行单独的编码.而是由连续输入的 信息序列得到连续输出的已编码序列.卷积码通常用2个参数 来描述:码率(Coderate)k/n,和约束长度(Constrainlength)K, k/n是在一个编码周期内进入卷积编码器的位数k与卷积编码 器输出的码元数的比值:则示了编码器的长度.即:多少个 比特位的段可供输入组合逻辑.以产生输出码元.通常把卷积码 记作,. 解卷积码的技术有许多种.包括序列译码,堆栈算法,反馈 译码等等,而其中最重要的是维特比(Viterbi)算法【1】.Viterbi译 码采用最大似然算法.能够达到最佳的误码率.特别适用于随机 错误进行前向纠错.运算量的大小也完全能够被接受.Viterbi算 法的出现使卷积码立即流行了起来 约束Viterbi算法『31,是当已知某些位置的数据是正确地情 况下.可以限制Viterbi算法格状路径必须通过该点.在这种约 束之下.Viterbi算法地性能能得到大幅提高.约束Viterbi算法 的关键在于如何确定某一位正确,在文献『31中采用了乘积码行 列交替约束的方法.以达到确定约束位的作用. 本文第二部分将讨论约束Viterbi算法的原理.在第三部分 将讨论其实现.第四部分将对其在BSC信道上进行仿真的结果 进行讨论. 2.约束Vi【erbi算法原理 在Viterbi译码中.对于长度为L的二进制序列的最佳译 码.需要对有可能发送的个不同序列的2'条路径的似然函数 累加值(即路径量度)进行比较.选取其中最大的一条.当该二进 制序列的某位数据已经确定为正确的时.那么.所有不符合该正 确数据的路径认为是错误的,这样.可以使候选路径减半,即为 2.所以我们每确定一位,就可以使候选路径减半.当确定了m 位后候选路径数量变为2t,-.. 当一个位被确定为正确后. 其不仅自身译码正确.同时可以 影响其附近的位.例如采用图1 所示的递归系统卷积码(RSC: tlecursiveSystematicConvolution. alCode).从零状态开始,到零状 态结束图1递归系统薯积码(2,l,2) 对输入长度为8的序列fO11OOO11进行编码,其编码 结果为 {ooll1OooO1O1l1) 经过信道后,由于噪声干扰,接收段收到的序列中,有3位 数据发生错误(加框的数据) {oollO1oo11Oll1) 如果按照一般的Viterbi译码(图2a中粗线表示的路径), 基金项目:中国国家自然科学基金资助课题(60372O7O) 其得到的结果将是 fool1Ol1O1OOl11) 错误由原来的3个变为5个.如果我们已知某位正确.例如 第7位O正确f]划线的数据) {ooll01oollO1l1) 那么在解码时.在的时刻,所有的该位为1的路径被删除 (图2b中打叉的路径),如此经过解码后,我们有会得到正确的 译码(图2b中粗线表示的路径). FII=-1r-3H#5两FfFIr-2H两 图2a无约束时的错误译码图2b有约束时的正确译码 3.约束Viterbi算法的实现 设编码器含有N个状态.其从O状态开始.当经过M时刻 后,返回O状态,其译码的网格图(Trellis)见图3.在J时刻的接 收的数据,与从J一1时刻,第i个状态,到J时刻,第k个状态输 出的数据的汉明距离记为C",纠(i状态与k状态之间不存在连 接的话,那么c/i,k)=oO).从O时刻,O状态,到达第J时刻,k状 态的所有路径中.其中一条路径具有最小汉明距离;),该路径 在每个时刻经过的状态在;)中,那么最终就是译码 的最优路径. 采用约束Viterbi算法中,假设已知i时刻的输入为正确,那 么令符合该输入的路径上的C,O其中O?i?^JO?? J7,,一J不符合该输入的路径上的,纠=o.其中O??^JO? k?N—l 这样.只有在该时刻符合已知正确输入的路径才会在累加 后成为最小值并保留下来.译码时,初始化)==ci(O,i)(D=0 ??^LJ之后.进行累加并选取最小值 (f)+一(f,划@=ar鼬0+ O?k?^L 由于在i一1时刻符合约束的G一,.而不符合约束的为 oo,所以),)只会保留符合约束的路径. 最终 氟=翘?+1)J(1)=arjI(f)+q(j 经过回溯得到各个时刻的状态 {D,ia…J)其中i7-*,I(01)O??Jlf—J 2006年第8期福建电脑15 4.仿真实验 参考文献[3】中的仿真,在仿真中,令数据大小为216比特, 信息位由随机数产生,加6位的状态归零码.共222比特.编码 器为(2,1,6)递归系统卷积码,编码效率为0,488.仿真的参数记 录在表格1中. 原始数据大小216 插入状态目零码长度6 蝙码后数据包大小222×2 编丹 眦 s 【0x79J 信遒BSc信道 仿真次数l000 表1仿真参数 在仿真中.编码后的数据包(Packet)的格式如图4所示.每 个数据包被分为n个段(Segment).S1一Sn.每段内含有m个比 特.B1一Bm.每段(最后一段Sn除外)的第m一1个比特为我们所 知道的正确的约束位(图中黑色部分).这样共有(222/m)一1个正 确的约束位,且呈均匀分布.仿真中,m取16进行仿真,分别测 试了译码后的误码率(BER:BitErrorRate)与误包率(PER: PacketErrorRate).采用两种算法进行译码.以进行比较.一种 是采用约束算法进行译码:一种是未进行约束算法.仅在译码后 将已知正确的比特填充进译码结果中.对此两种算法进行比较. 结果见图5a,b. I二l jqC,~n.1)J 图3N状态M时刻网格图图4包结构 图5aPER性能曲线图5bBER性能曲线 图5的结果说明,在加入约束进行计算后.性能得到了较大的提 升,尤其在信道性能较差,即经过信道后误码率较高的情况下. 经过解码后的数据.无论是PER还是BER都提高的更多 5.结论与展望 本文探讨了约束VITERBI算法的实现与性能.并进行了仿 真,其结果表明,在进行约束后,性能得到了提升.约束VITERBI 算法关键的问题在于如何获得可靠的约束,文献f31提供了一种 可行的方法,但其编码效率较低.下一步思考的问题是如何不变 码率或有较低下降的情况下,得到可靠的约束. 参考文献: 1.LinS.CostelloDJ.差错控制编码基础和应用.【MJ北京:人民邮电出 版社.1981 2.曹志刚.钱亚生.现代通信原理.J北京:清华大学出版社,1992 3.LeiCao.ChangWenChenANovelProductCodingandRecurrer( AlternateDecodingSchemeforImageTransmissionOverNoisyC~meb ?】IEEETRANSACTIONS0Nc0MMuNIcAT10NS.VOL.51. NO.9.SEP,rEMBER2003 4.N.Seshadri.C.一E.W.Sundberg.ListVi~rbidecoding~Igorithms出 apphcafiom.田IEEETram.Commun..vo1.42.PP.313—323.Feb.一Apr. 1994. (上接第ll页) 高计算机应用水平的教师具有专业背景优势.在计算机应用的 课程上组织教学针对性强.可以考虑纳入到计算机基础教学的 队伍中来.这样能很好地解决计算机师资队伍在专业上的互补 性.形成一支高素质,复合型的计算机基础教学师资队伍. 4.5培养计划以及学分制管理 在原来全校统一的计算机公共课的教学模式中.教学管理 比较简单.根据新形势下计算机基础教育的目标和要求.简单地 统一增加课程和教学时数显然是行不通的原因是各专业学生 在学期间的总教学时数是由本科生培养计划规定.不能随意增 加.即使增加,根据各个专业的性质,对计算机的知识和能力有 不同的要求.如果再考虑学生本身的兴趣,所开设课程的内容, 学时和学分管理等问题,应由承担计算机教学的部门,各系部和 教学管理部门统一协调和管理. 4.6完善课程体系方案. 在实施的过程中应不断地完善课程体系方案.形成与所设 课程配套的教学计划,教学大纲,教学方法,教学内容,实验内 容,考试大纲和考核方式以及教学管理方法等.在新形势下.结 合本院校学生的实际情况精选或编写教材,精选内容,加强实践 教学.在原有的基础与验证型实验的基础上再增加综合与开发 型实验,以强化学生上机动手能力,解决问题的能力,知识综合 运用能力等.促进学生更好地学习计算机课程.提高学生素质和 能力. 5.结束语 计算机基础教学的改革从提出到成熟还有一个过程.需要 在实践中发现问题,解决问题,经验,不断完善改进.通过课 程改革,教学方法的改进,考核的进一步完善,合理等.提高 学生的学习积极性.使得非计算机专业学生通过学习能真正地 掌握计算机的知识.提高信息技术素养及信息处理和利用的能 力.为将来应用计算机知识和技术解决与专业相关的实际问题 打下良好的基础.增加农业高校毕业生的社会适应性和竞争力. 从而较好地解决毕业生的就业出路.为社会各领域培养更多的 应用型,复合型人才. 参考文献: 1.教育部.关于进一步加强高校计算机基础教学的几点意见.2004. 2.谭浩强.高等学校计算机基础教育改革的新阶段田.计算机教育.2003 (12).