VITERBI改进算法研究

电脑编程技巧与维护 Viterbi改进算法研究 毛淑华。李丽华 f东华理工大学，抚州 3~000) 摘 要： Viterbi译码算法是最大似然译码。 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 所研究的改进 Viterbi算法，不但保持 了原有 Viterbi算法的特性， 而且在减少译码路径的情况下，能较好地解决突发错误信道中，原 Viterbi译码算法则性能急剧下降的问题。通过在 编码信道模型上的仿真表明，已知正确的约束位越多，分布的越密，则提高的性能越明显。 关键词：信道编码；维特比译码；通信 Study on the Improvement of Viterbi Algorithm MA0 Shuhua,LI Lihua (East China Institute of Technology，Fuzhou 344000) 【Abstract】Viterbi algorithm decoding is a kind of maximum likelihood decoding。In this paper，the improvement of Viterbi algorithm is produced，experiment results show that it can overcome the drawback of the decoding performance greatly degraded．when burst eiTors occur， and reduce the decoding complexity while keeping the good characteristic of conventional Viterbi algorithm．Simulations over coding channel show that the more correct bits we know the better the perform ance is． 【Keywords】channel coding；Viterbi algorithm；communication l 引言 卷积码广泛应用于各种数字通信系统中，其中卫星通信 中信道部分也大量采用卷积码。描述卷积编码的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 很多， 如卷积码的矩阵描述 、生成多项式描述、树图 (网格 图)描 述、有限状态图描述等 ，并且卷积码的描述方法与它所采用 的译码方法密切相关。目前研究 比较成熟的方法有卷积码的 生成多项式矩阵描述和网格图描述。卷积码的网格图描述是 一 种形象的表示卷积码编译码过程的方法 ，Viterbi基于网格 图提出著名的 Viterbi译码算法成为目前解决卷积码译码的最 有效的算法。卷积码的概率译码不仅利用码自身的代数结构， 而且还考虑了信道的统计特性，因而能充分发挥卷积码的特 点，使译码错误概率达到最小。 2 卷积码原理 卷积码是把 k个信息比特的输入经编码后，形成 n个比 特的输出，通常k和n很小，特别适宜于以串行形式传输信 息 ，延时小。与分组码不同，卷积码中编码后的 n个码元不 但与当前段的k个信息有关，而且与前面 fN一1)段的信息有 关，因此称 N为约束长度。编码过程中相互关联的码元为 Nk 个。卷积码的纠错能力随着 N的增加而增大 ，而差错率随着 N的增加而指数下降。在编码器复杂性相同的情况下，卷积码 的性能优于分组码。 ’ 卷积码的译码方法可分为两大类。一类是代数译码，利 用编码本身的代数结构进行译码，不考虑信道本身的统计特 性。该方法的硬件实现简单，但性能较差，其中具有典型意 义的是门限译码；另一类是概率译码，这种译码通常建立在 最大似然准则的基础上。由于计算是用到了信道的统计特性 ， 因而提高了译码性能，但这种性能的提高是以增加硬件的复 杂度为代价的。常用的概率译码方法有维特比译码和序列译 本文收稿日期：2008年9月 8日 一 2 一 码。卷积码概率译码的基本思路是：以断续的接收码流为基 础 ，逐个计算它与其他所有可能出现的、连续的网格图路径 的距离，选出其中可能性 (概率)最大的一条作为译码估值输 出。概率最大在大多数场合可解释为距离最小，这种最小距 离译码体现的正是最大似然的准则。 3 硬判决Viterbi译码算法原理 Viterbi算法是一种最大似然译码算法。它并不是在网格 图上一次比较所有可能的 2枕条路径 (序列)，而是接收一段， 计算 比较一段 ，选择一段最有可能的码段 (分支)，从而达到 整个码序列是一个有最大似然函数的序列。 Viterbi算法的基本思路是 ：以断续的接收码流为基础， 逐个计算它与其他所有可能出现的连续的格状图路径的距离， 选出其中可能性 (概率)最大的一条作为译码估值输出。 从时间单位 m至 L，网格图中2 个状态中的每一个有一 条幸存路径，共有 2 条。但在 L时间单位后，网格上的状态 数目减少，幸存路径也相应减少。最后到第L十m单位时间， 网格图上的状态数目减少，因此仅剩下一条幸存路径。这条路 径就是要找的具有最大似然函数的路径，也就是译码器输出的 估值序列。由此可知，在网格图上用维特比算法得到的路经一 定是一条最大似然路径，因此这种方法是最佳的。 4 改进 Viterbi译码算法原理 在 Viterbi译码中，对于长度为 L的二进制序列的最佳译 码 ，需要对有可能发送的 2 个不同序列的 2 条路径的似然函 数累加值 (即路径量度)进行 比较，选取其中最大的一条。 当该二进制序列的某位数据已经确定为正确的时 ，那么，所 有不符合该正确数据的路径认为是错误的，这样 ，可以使候 选路径减半，即为2 。所以每确定一位，就可以使候选路径 减半，当确定了m位后候选路径数量变为2 ；当一个位被 确定为正确后，其不仅自身译码正确，同时可以影响其附近 的位。 S0FrWARE DEVELOPMENT AND DESIGN 软件开发与 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 设编码器含有 N个状态，其从 0状态开始 ，当经过 M时 刻后，返回0状态，其译码的网格图见图1。在J时刻的接收 的数据，与从 J一1时刻，第 i个状态，到 J时刻，第 k个状态 输出的数据的汉明距离记为 C (i,k) (i状态与 k状态之间不 存在连接的话 ，那么 C．(i,k)=。。)。从 0时刻，0状态 ，到达 第J时刻，k状态的所有路径中，其中一条路径具有最小汉明 距离 ‘pi(k)，该路径在每个时刻经过的状态记录在 ￡，(k)中， 那么最终 ￡ (0)就是译码的最优路径。 图 1网格图 5 两种 Viterbi译码算法性能的比较 在仿真中，令数据大小为 250比特，信息位由随机数产 生，加 6位的状态归零码。共 256比特。仿真的参数记录在 表 1中。 表 1仿真参数 原始数据大小 250 插入状态归零码长度 6 编码后数据包大小 256×2 编码 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 习 信道 BSCt~道 仿真次数 1O0O 在仿真中，编码后的数据包的格式如图 2所示。每个数 据包被分为n个段 SI-S ，每段内含有 m个比特，B。一B 。每段 (最后一段 Sn除外)的第 m一1个 比特为我们所知道的正确的 约束位 f图中黑色部分)。这样共有 f256／m)一1个正确的约束 位，且呈均匀分布。仿真中，m取 2、4、8、16进行仿真， 分别测试了译码后的误码率与误包率。采用两种算法进行译 码，以进行比较，一种是采用改进算法进行译码 ；一种是未 进行改进算法，仅在译码后将已知正确的比特填充进译码结 果中，对此两种算法进行比较，结果见图3，图4。 图 2包结构 6 结论 卷积码己经广泛应用于卫星通信和移动通信等无线通信 系统中，其编译码技术研究不断有新的进展 ，信道编码技术 已经成为一门 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 技术而被广泛地应用于各种通信系统中。 本文研究的 Viterbi算法对卷积码的译码是一种改进。纠错编 码技术处于不断的发展之 中，新的编码在实际中的应用 ，会 给编码分析人员提出新的课题，这就要求我们不断研究新方 法，去解决实际工作中出现的新问题。 R 图 3误包率性能曲线 图 4误码率性能曲线 参考文献 [1】王新梅 ，肖国镇．纠错码——原理与方法 fM】．西安：西 安电子科技大学出版社，2001． 【2】张宗橙．纠错编码原理与应用 【MJ．北京：电子工业出版 社，2003；83—86． 【3]游余新，王进祥，来逢昌，叶以正．高速低功耗维特比译 码器的设计与实现 fJj．计算机研究与发展．2003；40(2)： 360— 3651． 【4]Lei Cao，Chang Wen Chen A Novel Product Coding and Re- currentAhernate Decoding Scheme for Image Transmission Over Noisy Channels[J】IEEE TRANSACTIONS ON COM- MUNICATIONS，SEm MBER 2003 VOL．5 1，NO．9． 『51温学东．卷积码编码及其 Vietbri译码算法的 FPGA实现 [J]．信息与电子工程，2005；3(9)：176— 179． [6]6 曹志刚，钱亚生．现代通信原理 [M】．北京：清华大学出 版社，1992． 【7】杨留清，张闽申，徐菊英．数字移动通信系统 【M】．北京： 人民邮电出版社，1998． 【8】Lin S，Costello DJ．差错控制编码基础和应用 [M]．北京： 人民邮电出版社，1981． 作者简介 毛淑华，女 (1979一)，汉族，助教，计算机应用技术在职研 究生，主要研究方向：通信领域。 一 3 一