（通信与信息系统专业论文）卷积码编码与维特比译码加速器设计.pdf

， 独创性( 或创新性) 声明 i i i i i iii l f li i i ii ii ji ii 17 5 9 3 4 0 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽 我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： l ! 掣潋一 日期：趁生! f ! 也 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有 关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学 位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论 文。( 保密的学位论文在解密后遵守此规定) 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：垒约型遨 日期： 之竺2 1 ：f ! ! 里 导师签名： ：弘：维匕 日期： 幽f 立! ! ：壁 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 卷积码编码与维特比译码加速器设计 摘要 通信的技术性能主要是从通信的数量与质量两方面来讨论的，一般数 量指标用有效性来度量，而质量指标用可靠性来度量。信道编码一直是通 信系统的研究热点，它的目的正是为了改善数字通信系统的传输质量。而 信道编码中卷积码则是近年来应用最为广泛的信道编码之一。卷积码广泛 应用于各种数字通信系统中，例如卫星通信系统、g s m 、3 g 等等。卷积码 的译码算法主要有概率译码和代数译码，而其中概率译码中的维特比译码 算法的应用最为广泛，它在许多移动通信终端的芯片中都需要实现。本论 文主要讨论卷积码编码与维特比译码算法。 本文主要论述了信道编码、卷积码的基本原理及表示方法以及维特比 译码算法的基本原理，同时也对截尾卷积码及其译码方法作了详细地分析 和研究。为了满足移动通信的终端芯片系统需求，本文在深入分析阐述维 特比译码规律和总结移动通信系统需求的基础上，提出了维特比译码的硬 件加速器设计，芯片利用寄存器控制加速器的运行。在加速器与芯片之间 的数据传输采用输入输出f i f o 的方法，提高传输效率和速度。而对于比较 长的译码序列采用滑动窗口来控制译码过程，以此节约芯片资源和提高译 码效率。再设计度量值和状态度量值存储方式及幸存路径存储方式，以提 高存储效率、译码效率以及节省芯片资源。在m i c r o s o f tv i s u a ls t u d i o2 0 0 5 开发环境下使用c 语言实现加速器的c m o d e l ，该c m o d e l 不仅实现了卷 积码编码、维特比译码算法，还验证了维特比译码算法的正确性。最后设 计加速器的测试用例，测试总结加速器的性能，得出可以满足g s m g p r s 系统译码需求的结论。 关键字：卷积码，维特比译码，加速器，g s m 邮电大学硕士学位论文 卷积码编码与维特比译码加速器设计 一 北京邮电大学硕士学位论文 c o n v o l u t i t h e r ea r cw a y sm a i n l yf r o mt w op e r s p e c t i v e st om o a s u r et h et e c h n i c a lp e r f o r m a n c eo f w i r e l e s sc o m m u n i c a t i o ns y s t e m t h eq u a n t i t yo fc o m m u n i c a t i o ns y s t e mi sj u d g e db yt h e v a l i d i t ya n dt h eq u a l i t yo fc o m m u n i c a t i o ns y s t e mi sj u d g e db yt h er e l i a b i l i t y t h ep u r p o s eo f c h a n n e lc o d i n gi st oi m p r o v et h et r a n s m i s s i o nq u a l i t yo fd i g i t a lc o m m u n i c a t i o ns y s t e m s ，a n d i ta l w a y si sar e s e a r c hh o t s p o ti nc o m m u n i c a t i o ns y s t e m s t h ec o n v o l u t i o n a lc o d e si su s e d w i d e l ya sc h a n n e lc o d i n g c o n v o l u t i o n a lc o d ew i d e l yu s e di nv a r i o u sd i 【g i t a lc o m m u n i c a t i o n s y s t e m s ，s u c ha ss a t e l l i t ec o m m u n i c a t i o ns y s t e m s ，g s m ，3 ga n ds oo n t h ed e c o d i n g a l g o r i t h m sf o rc o n v o l u t i o n a lc o d e sa l em a i n l yt h ep r o b a b i l i t yo fd e c o d i n ga n da l g e b r a i c d e c o d i n g v i t e r b id e c o d i n gi nt h ed e c o d i n ga l g o r i t h mi st h em o s tw i d e l yu s e dd e c o d i n g a l g o r i t h mf o rc o n v o l u t i o n a lc o d e s i nm a n yc h i p so fm o b i l ec o m m u n i c a t i o nt e r m i n a l sn e e dt o i m p l e m e n tv i t e r b id e c o d i n ga l g o r i t h m s ot h i sp a p e rf o c u s e so nc o n v o l u t i o n a lc o d ea n d v i t e r b id e c o d i n ga l g o r i t h m t h i sp a p e rd i s c u s s e st h ec h a n n e lc o d i n g , t h eb a s i c p r i n c i p l e sa n dm e t h o d so f c o n v o l u t i o n a lc o d ea n dt h eb a s i cp r i n c i p l e so fv i t e r b id e c o d i n ga l g o r i t h m ，w h i l et a i l - b i t i n g c o n v o l u t i o n a lc o d e sa n dd e c o d i n gm e t h o d sa l ea n a l y z e di nd e t a i l b a s e do nd e s c r i b i n gv i t e r b i d e c o d i n gi nd e t a i la n ds u m m a r i z i n gt h er e q u i r e m e n to fw i r e l e s sc o m m u n i c a t i o ns y s t e m s ， p r o p o s ev i t e r b id e c o d i n gh a r d w a r ea c c e l e r a t o r sa n dc o n t r o lt h eu s eo fa c c e l e r a t o r sb y r e g i s t e r st om e e tt h em o b i l ec o m m u n i c a t i o nt e r m i n a lc h i ps y s t e mr e q u i r e m e n t s t h ei n p u ta n d o u t p u tf i f ob e t w e e nt h ea c c e l e r a t o ra n dc h i pi su s e dt oi m p r o v et r a n s m i s s i o ne f f i c i e n c ya n d s p e e d s l i d i n gw i n d o wd e c o d i n gp r o c e s si su s e dt od e a lw i t hl o n gd e c o d i n gs e q u e n c e d e s i g n h o wt os a v eb r a n c hm e t r i c s ，s t a t em e t r i c sa n dt h es u r v i v i n gp a t hm e m o r yt oi m p r o v es t o r a g e e f f i c i e n c y , c o d i n ge f f i c i e n c ya n ds a v ec h i pr e s o u r c e s i m p l e m e n tt h ec - m o d e lo fv i t e r b i d e c o d i n ga c c e l e r a t o rw i t hcp r o g r a m m i n gl a n g u a g ei nm i c r o s o f tv i s u a ls t u d i o2 0 0 5 n o t o n l yi m p l e m e n tc o n v o l u t i o n a lc o d e sa n dv i t e r b id e c o d i n ga l g o r i t h m ，b u ta l s ov e n f st h e c o r r e c t n e s so fv i t e r b id e c o d i n ga l g o r i t h m a tl a s td e s i g nt e s tc a s et ov e r i f yt h ed e s i g no ft h i s a c c e l e r a t o r , s u m m a r ya c c e l e r a t o rp e r f o r m a n c ea n dm a k et h ec o n c l u s i o nt h a tt h ea c c e l e r a t o r 卷积码与编码维特比译码加速器设计 fg s m g p r ss y s t e m c o n v o l u t i o n a lc o d e ，v i t e r b id e c o d i n g , a c c e l e r a t o r ，g s m 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 目录 摘! 要! ； a b s t r a c t 7 第一章绪论l 1 1论文的研究背景。l 1 2 论文的主要工作及架构2 第二章卷积码。4 2 1 信道及信道编码。4 2 2 卷积码基本原理7 2 3 卷积码表示方法。9 2 3 1 解析式表示法。9 2 3 2 图形表示法9 2 3 2 1 状态图表示法9 2 3 2 2 树图表示法1 0 2 3 2 3 网格图表示法12 2 4 卷积码的距离特性1 3 2 5 截尾卷积码。1 4 2 6 本章小结1 4 第三章维特比译码原理15 3 1 卷积码译码方法1 5 3 2 最大似然译码15 3 3 维特比译码算法17 3 4 硬判决译码与软判决译码1 9 3 5 截尾卷积码译码19 3 5 1 循环维特比算法乙2 0 3 5 1 环绕维特比算法2 0 3 6 本章小结2 1 第四章g s m g p r s 卷积码编码、维特比译码加速器2 2 4 1 系统需求2 2 4 1 1g s m 系统中的卷积码2 2 4 1 2g p r s 中的卷积码2 3 4 1 3e g d e 系统中的卷积码。2 3 4 1 4t d s c d m a 中的卷积码2 4 4 1 5t d l t e 中的卷积码2 5 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 4 2 加速器总体设计2 5 4 3 输入输出f i f o 。2 6 4 4 译码算法规律及模块设计2 8 4 4 1 分支度量及加比选2 9 4 4 2 回溯3l 4 5 滑动窗口控制3 3 4 5 11 葡l e dt r a c e b a c km o d e 。3 3 4 5 2m i x e dt r a c e b a c km o d e 3 3 4 5 3c o n v e r g e n tt r a c e b a c km o d e 3 4 4 6 输入参数和输出参数设计3 5 4 7 本章小结3 6 第五章加速器c - m o d e l 实现与加速器测试报告3 7 5 1 加速器c - m o d e l 的实现3 7 5 1 1c - m o d e l 实现环境3 7 5 1 2c - m o d e l 算法部分。3 7 5 1 3c - m o d e l 测试部分。4 l 5 1 4c - m o d e l 测试结果4 2 5 2 加速器测试用例。4 3 5 3 加速器性能测试4 5 5 4 本章小结4 7 第六章总结与展望4 8 6 1 论文工作总结4 8 6 2 下一步工作4 9 参考文献5 0 附：爱! ；l 致谢。5 5 攻读学位期间发表的学术论文5 6 一 t k 鼍 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 1 1 论文的研究背景 第一章绪论 在现代通信中，信源和信道是组成通信系统的最基本单元。信源始产生信息的源， 信道则是传送载荷信息的信号所通过的通道，信源与信宿之间的通信是通过信道来实现 的。 度量通信的技术性能主要是从通信的数量与质量两方面来讨论的，一般数量指标用 有效性度量，而质量指标用可靠性度量。前者主要与信源统计特性有关，而后者则主要 决定于信道的统计特性。相应的，每个通信系统都进行信源编码和信道编码。信源编码 的目的是在分析信源统计特性的基础上，设法通过信源的压缩编码区掉这些统计多余成 分。信道编码的目的是为了改善数字通信系统的传输质量【。 为了减少数据在传输过程中产生的错误，提高通讯的可靠性，许多人在研究差错控制 信道编码的方法。在目前的数字通信系统中，前向纠错信道编码技术得到了广泛的应用。 这一技术的产生和发展源于通信系统本身的需求。在工程实践中并不存在理想的数字信 道，信号在各种媒体的传输过程中总会产生畸变和非等时时延，对数字信号来说就意味 着产生误码和抖动，而抖动的最终效果也反映在系统的误码上。为了在已知信噪比的情 况下达到一定的误比特率指标，首先应合理设计基带信号，选择调制、解调方式，采用频 域均衡或和时域均衡，使误比特率尽可能降低。但若误比特率仍然不能满足要求，则必 须采用信道编码，即纠错控制编码，将误比特率进一步降低，以满足指标要求瞳】。 前向纠错是指信号在被传输之前预先按一定的格式对其进行处理，在接收端则按规 定的算法进行解码以达到找出错码并纠错的目的。现代纠错码技术是由一些对通信系统 感兴趣的数学家们和对数学有着深厚功底的工程师们在近5 0 多年中发展起来的。1 9 4 8 年，信息论之父仙农( c l a u d ee l w o o ds h a n n o n ) 发表了现代信息理论奠基性的文章通 信系统数学理论，揭示了信源信息速率与信道容量的关系。自香农的论文发表以来， 人们经过持续不懈的努力已经找到多种好码，可以满足许多实用要求。汉明( h a m m i n g ) 于1 9 4 9 年提出了可纠正单个随机差错的汉明码【i 】，普朗基( p r a n g e ) 于1 9 5 7 年提出了循环 码的概念【l 】，h o c q u e g h e m 、b o s e 和c h a u d h u r i 于1 9 5 9 年发现了b c h 码【l 】，稍后，r e e d 和 s o l o m o n 提出了r e e d s o l o m o n ( r s ) 编码，这实际上是一种改进了的b c h 码，现代通信采用 在一个无线通信系统中，卷积码和相应的译码方法一维特比译码算法会频繁的调用， 并且如果传输码字比较长，运算量将很大。在无线通信终端芯片中，很多芯片都要嵌入 通信系统协议，比如g s m 协议、t d s c d m a 协议或者l t e 协议等等。芯片体积有限，并且频 繁调度需要大数据量的算法对系统的稳定性、实时性都有影响。为此，很多芯片公司生 产的嵌入移动通信协议的无线通信芯片都把一些调用率比较高、数据传输量比较大、成 熟稳定的软件算法设计成硬件加速器。 本文研究的卷积码编码及维特比译码算法硬件加速器设计是基于某电子公司移动通 信终端芯片为满足g s m 通信系统而开发设计的。本论文的主要工作和章节安排为： 第一章为绪论，简要介绍了信道编码纠错技术的应用和发展，对本课题研究的背景 和意义进行了阐述。 第二章首先介绍了信道及信道编码的基本概念和基本原理，然后详细介绍了卷积编 码的基本原理，表示方法。其中表示方法分为解析式表示法与图形表示法，对图形表示 2 i 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 法做了详细总结。 第三章主要介绍了维特比译码原理，着重介绍了维特比译码的步骤及硬判决、软判 决方法。同时研究总结了截尾卷积码的译码方法。 第四章根据系统需求，完成卷积码编码和译码硬件加速器的设计。加速器的设计与 一般的不同之处是有个输入输出缓冲。这种设置可以提高加速器与d s p 之间的传输速 度，同时可以把计算分支度量值的任务给加速器来完成。在算法处理模块，提炼出 b u t t c r f l y 结构，b u t t e r f l y 的使用，简化了实现的过程和步骤，使加比选的过程变得更加简 单。针对网格图及b u t t e r f l y 的特点，网格图的每一级每个状态选择的o 1 路径被保存下来， 这种方法既完整保留幸存路径，又方便回溯的操作。对可能的较长信息序列，用滑动窗 口来控制译码过程，最后根据系统需求及加速器的设计，设定了加速器的输入输出参数， 完成对算法的需求报告。 第五章实现了硬件加速器对应的c - m o d e l ，同时测试c - m o d e l ，保证c - m o d e l 的正确 性。使用m i c r o s o f tv i s u a ls t u d i o2 0 0 5 开发工具实现了加速器的c - m o d e l 程序。加速器 c - m o d e l 分为两个部分，一是算法实现部分，实现算法功能；二是测试验证部分，在算 法实现的基础上，验证算法的正确性。为了验证算法，本文采用的信道是加性高斯白噪 声信道，使用的调制方式是b p s k 调制。编码后的数据在加扰处理后，对其进行维特比 译码处理。最后将译码结果与编码前的序列进行对比，验证算法的正确性。同时设计了 加速器的测试用例，以验证硬件加速器。在对加速器的性能进行了大量测试之后，得出 加速器的译码性能参数，得出最后的结论：可以满足g s m g p r s 系统的译码需求。 第六章总结与展望及下一步可以改进的工作。 3 图2 - 1 数字通信系统的组成框图 信道是通信系统的重要组成部分，其特性对于通信系统的性能有很大影响。信道按 照其不同特征有不同的分类方法。按信道的组成可将其分为狭义信道与广义信道。信号 的传输媒质成为狭义信道。 除传输媒质外，还包括通信系统的某些设备，例如：收发信机、编译码器、调制解 调器，由他们所构成的系统称为广义信道。由调制器、传输媒质、解调器组成的广义信 道称为调制信道。按照信道输入输出端信号的类型可将其分为连续信道( 模拟信道) 和 4 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 离散信道( 数字信道) 。连续信道的输入输出信号为连续信号( 又成模拟信号) ，例如 广义信道中的调制信号属于连续信道。离散信道的输入输出信号为离散信号，又称数字 信号，广义信道中的编码信道即属于离散信道。如果输入为连续信号，输出为离散信号 或反之，则称为半连续或半离散信道。连续信道又可分为恒参信道和随参信道。恒参信 道的性质( 参数) 不随时间变化。如果实际信道的性质( 参数) 不随时间变化，或者基 本步随时间变化，或者变化极慢，则可以认为是恒参信道。随参信道的性质( 参数) 随 时间随机变化。一般的有限信道可看作是恒参信道；部分无线信道可看作是恒参信道， 另一部分是随参信道。 与有线通信通过光纤，同轴电缆等有形的介质传输信息不同，无线通信的信息传输 介质是无形的无线信道。在这里信道是对无线通信中发送端和接收端之间的通路的一种 形象比喻，对于无线电波而言，它从发送端传送到接收端，其间并没有一个有形的连接， 它的传播路径也有可能不只一条，但是我们为了形象地描述发送端与接收端之间的工作， 我们想象两者之间有一个看不见的道路衔接，把这条衔接通路称为信道。信道具有一定 的频率带宽，正如公路有一定的宽度一样。 无线信道中电波的传播不是单一路径，而是许多路径来的众多反射波的合成。由于 电波通过各个路径的距离不1 司，因而各个路径来的反射波到达时间不同，也就是各信 号的时延不同。当发送端发送一个极窄的脉冲信号时，移动台接收的信号由许多不同时 延的脉冲组成，我们称为时延扩展。同时由于各个路径来的反射波到达时间不同，相位 也就不同。不同相位的多个信号在接收端迭加，有时迭加而加强( 方向相同) ，有时迭加 而减弱( 方向相反) 。这样，接收信号的幅度将急剧变化，即产生了快衰落。这种衰落是 由多种路径引起的所以称为多径衰落。 此外，接收信号除瞬时值出现快衰落之外，场强中值( 平均值) 也会出现缓慢变化。主 要是由地区位置的改变以及气象条件变化造成的，以致电波的折射传播随时间变化而变 化，多径传播到达固定接收点的信号的时延随之变化。这种由阴影效应和气象原因引起 的信号变化，称为慢衰落。而且，由于移动通信中移动台的移动性，如前所说那样，无 线信道中还会有多普勒效应。在移动通信中，当移动台移向基站时，频率变高，远离基 站时，频率变低。我们在移动通信中要充分考虑“多普勒效应 。虽然，由于日常生活 中，我们移动速度的局限，不一可能会带来十分大的频率偏移，但是这也不可否认地会 给移动通信带来影响。 综上所述，无线信道包括了电波的多径传播，时延扩展，衰落特性以及多普勒效应， 这些因素使得无线信道的传输环境比有线信道要恶劣许多。因此，在移动通信中，我们 要充分考虑这些特性以及解决的方案。 5 纠错能力以内，就自动进行纠错。如果错误很多，超出了码的纠错能力，但能检测出来， 接收端通过反馈信道，要求发端重新发送有错的信息。这种方式在一定程度上避免tf e c 6 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 方式要求用复杂的译码设备和a q r 方式信息连贯性差的缺点，并能达到较低的误码率， 因而在实际的应用中也较广 4 1 。 2 2 卷积码基本原理 卷积码是e l i a s 在1 9 5 5 年提出的【l 】。在分组码中，把k 个信息比特序列编成n 个比 特的码组，每个码组中的( n - k ) 个校验位仅与本码组的k 个信息位有关，而与其它码 组无关。为了达到一定的纠错能力和编码效率，分组码的码组长度一般比较大。编译码 时必须把整个信息码组存储起来，由此产生的译码延迟会随着n 的增加而增加。和分组 码不同，卷积码前后各码组之间具有相关性，即卷积码编码后的n 个码元不仅与当前段 的k 个信息有关，而且还与前面( n 1 ) ( n 为编码约束度) 段的信息有关。在卷积码中， k 个信息比特也被编成n 个比特的码组，但k 和n 通常很小，并且可以通过串行或并行 的方式进行传输，而且时延很小。编码过程中互相关联的码元个数为n n 。 由于卷积码在编码过程中，充分地利用了各码组之间的相关性，且k 和n 都比较小， 因此，在与分组码同样的码率和设备复杂性条件下，从理论和实际两个方面，均已证明 卷积码的性能至少不比分组码差，且实现最佳和准最佳也较分组码容易【2 1 。但卷积码没 有分组码那样严密的数学分析手段，目前，好的卷积码大多是通过计算机进行搜索得到 的。 卷积码编码器如图2 - i 所示。 l2n 图2 - i 编码码率为k n ，编码约束度为n 的卷积码编码器 7 图2 - 2 ( 2 ，l ，3 ) 卷积码编码器 上图是( 2 ，l ，3 ) 卷积码的编码原理图，输入的信息元将经过两级移位寄存器，而两 编码结果将是其中某些寄存器内容和当前输入信息元的和。两路编码数据时分复用输 出，所以该( 2 ，1 ，3 ) 卷积码的码率为l 2 。 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 2 3 卷积码表示方法 卷积码的描述可以分为两大类型：解析法，它可以用数学公式直接表达，包括离散 卷积法、生成矩阵法、码生成多项式法；图形法，包括状态图( 最基本的图形表达形式) 、 树图及格图( 或称为篱笆图) 。下面以( 2 ，l ，3 ) 码为例来介绍状态图表示法和网格图表 示法。 2 3 1 解析式表示法 在解析法中，较为常用的主要是码生成多项式法。这种表示方法为编码器指定n 个 连接矢量集，每个矢量对应一个模2 加法器，每个矢量都是m 1 维，表示该模2 加法器 和编码移位寄存器之间的连接。矢量中第i 位上的l 表示移位寄存器相应级和模2 加法 器的连接，若是0 ，则表示相应级与模2 加法器之间无连接 6 1 。 图2 - 1 中编码器，用连接矢量9 1 代表上方连接，矿代表下方的连接，如下以( 2 ，1 ， 3 ) 卷积码为例，输入数据序列( 1 0 0 1 1 ) 及其对应的多项式为： u = ( 1 0 0 1 1 ) - - u ( x ) ：l + x 3 斗x 4( 2 1 ) g l = ( 1 11 ) - - g l ( x ) = 1 + x + 一( 2 2 ) 矿= ( 1 0 1 )- - 旷( x ) = 1 + 一( 2 - 3 ) 输出的码组多项式为： 2 3 2 图形表示法 2 3 2 1 状态图表示法 c 1 ( x ) = u ( x ) g l ( x ) = l + x + x 2 + x 3 + x 6 c 2 ( x ) = u ( x ) 幸g l ( x ) = i + x 2 + x 3 + x 4 + x 5 + x 6 ( 2 - 4 ) ( 2 5 ) 编码器的寄存器在任一时刻的所存储的内容称为编码器的一个状态。本例中，编码 存储m = 2 ，k = l ，编码器由两级移位寄存器构成，所以，移位寄存器所存储的内容只有 四种情况：0 0 、1 0 、o l 和1 1 ，以a ( o o ) ，b ( 1 0 ) ，c 0 1 ) ，d ( 11 ) 表示。随着信息序列不断送入， 编码器会不断地从一个状态转移到另一个状态。利用状态转移路径不但可以表示出该转 移过程中所对应的输出码段，同时还可以显示所对应的输入信息元。当输入序列为 ( 1 0 0 1 1 ) 时，( 2 ，l ，3 ) 卷积码的编码过程如下： 9 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 表2 - 1 输入序列( 1 0 0 1 1 ) 时编码过程 初始状态输入序列编码器新状态 编码后的序列( 第一个，第二个) alb 1 l bocl o c0al l - dlbl l al d0 1 p boco l coa l l doa0 0 c o d e w o r d l - - - - - - i v 0 0 j w 1 囤、1 暾二二! 坤一掣 。k 圆 i n p u tb i t o i n p u tb i t1 一，71 0 图2 - 3 ( 2 ，1 ，3 ) 卷积码转态转移图 一 虽然状态图能够表示卷积码编码器在不同输入的信息序列下，编码器各状态之间的 转移转移关系，但却不能描述随时间变化时系统状态转移的轨迹，为了解决这个问题， 可引入下面要介绍的网格图表示法。 2 3 2 2 树图表示法 图2 - 2 编码器的编码过程，也可以用图2 - 4 所示的码树来描述。图中每个节点对应 l o 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 于个输入码元。按照习惯，当输入为“0 时，走上分支：输入为“1 时，走下分支， 并将编码器的输出标在每个分支的上面。按此规则，就可以画出码树的路径。对于任一 个码元输入序列，编码器输出序列一定与码树中的一条特殊的路径相对应。因此，沿着 码元输入序列，就可以获得相应的输出码序列。例如，如果输入的信息序列为1 0 0 1 1 ， 输出编码序列为1 1 1 0 1 1 1 1 0 1 ，如图中虚线所示。由图2 1 可以看出，编码器的输出与 当前输入的码元m i 和先前输入的两个码元m j - 2 、m i i 的取值有关。我们将编码器中寄存 器内所存储的，先前输入的信息码元的可能取值称为编码器的状态。对应图2 2 的编码 器，m j - 2 1 i l j 1 ，可能的取值有四种：o o ，1 0 ，0 1 和1 l ，我们分别用毛b ，c ，d 表示，并将其 分别标注在码树的各节点上。( 2 ，1 ，3 ) 卷积码树图表示法如下图所示： t 1崆t 3l 毒荡 图2 - 4 ( 2 ，1 ，3 ) 卷积码树图表示法 在编码器的输入端输入一个新的信息码元后，编码器会从原来的状态转换成新的状 态。例如，若编码器原来的状态为c ，当输入码元为“l 时，编码器会从c 状态转换到 b 状态：当输入码元为“0 时，编码器会从c 状态转换到b 状态。从码树上还可以看到， l l 表状态之间的转移。若编码器从“0 0 ) 状态开始，并结束于a ( 0 0 ) 状态，则最先的m = 2 个 时间单位( 0 、1 ) ，相应于编码器由a 状态出发向各个状态转移，而最后m = 2 个时间单 1 2 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 位( t 6 、t 7 ) ，相应于编码器由各个状态返回s o 状态。 因而，在开始和最后的m 个时间单位，编码器不可能处于任意状态中，而只能处于 某些特定状态( 如( o o ) 、( 1 0 ) ) 之一，只是从第m ( 2 ) 到第l ( 5 ) 时间单位，编码器可以 处于任何状态之中( 即4 个状态a 、b 、c 、c 中的任意一个) 。编码器从全0 状态a 出发， 最后又回到a 状态时所输出的码序列成为结尾卷积码序列。所以，当送完l 段信息序列 后，还必须向编码器再输入m 段全0 序列，迫使编码器最终回到全0 状态a 。 网格图中的每一状态都有两个输入和两个输出分支。在某一时间单位( 节点) i ，离 开该状态的虚线分支，表示输入编码器中的信息码段为l ；而实线则表示输入至编码器 的信息码段为0 ；每个分支上的2 ( n ) 个数字，表示第i 时刻编码器输出的码段。网格图 中的每一条路径都对应不同输入的信息序列，如果所有可能输入的信息序列共有2 k l 那 么网格图中可能有的路径也有，相应于2 k l 个长为n - - - n ( h 1 1 1 ) 的不同序列。 2 4 卷积码的距离特性 在分组码中，常以最小距离作为纠错能力的度量。在卷积码中也同样有距离的概念， 经常使用的距离有两种：最小距离d 曲和自由距离d 妇( 简记为d f ) 。最小距离d 曲是 指卷积码中长度为n k ( k 为约束长度) 的编码序列之间的最小汉明距离。而自由距离d f 则是指任意长度卷积码编码序列之间的最小汉明距离。由于卷积码并不划分为一组组的 码字，而以自由距离作为纠错能力度量更为合理，它特别适合维特比算法。而最小距离 只是采用门限译码时，其译码处理长度仅限于n k 条件下适用。 卷积码的自由距离，是用来衡量所有可能码字序列对之间的距离的。其定义为：整个 编码码树上，所有半无限长序列之间的最小汉明距离。由于卷积码的自由距离直接决定 了它的纠错能力，所以寻找具有最大自由距离的卷积码是一项非常重要的工作。不过对 于卷积码的构造，目前除了计算机搜索外还没有其它更好的方法。下表是由奥登沃尔德 ( o d e n w a l d e r ，1 9 7 0 年) 和拉森( l a r s e n ，1 9 7 3 年) 采用计算机搜索方法得到的固定码率和 约束长度时具有最大自由距离的卷积码【j 7 1 。 表2 - 1 卷积码的自由距离与编码增益 约束长度k生成多项式( 八进制)自由距离编码增益( d b ) 3 ( 5 ，7 ) 54 2 6 4 ( 1 5 ，1 7 ) 65 2 3 5 ( 2 3 ，3 5 ) 76 0 2 6 ( 5 3 ，7 5 ) 8 6 3 7 7 ( 1 3 3 ，1 7 1 ) 1 06 9 9 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 8 ( 2 4 7 ，3 71 1 07 7 2 9 ( 6 1 ，7 5 3 ) 1 27 7 8 2 5 截尾卷积码 卷积码编码分为零截尾卷积码和截尾卷积码。零截尾卷积是指移位寄存器的初始状 态都为o 得到的编码结果。我们通常所说的卷积码一般是指零截尾卷积码，即卷积码编 码器的移位寄存器的初始值都为0 。 截尾卷积码也叫咬尾卷积码，则是把编码前数据的后k - 1 个数据作为编码器移位寄 存器的初始输入，这样卷积码编码器移位寄存器的初始状态和结束状态值都一样。 2 6 本章小结 本章介绍了信道编码原理及纠错码分类。详细介绍卷积码的基本原理，表示方法。 其中表示方法分为解析式表示法与图形表示法，尤其是网格图表示法，为进一步更好地 学习和应用卷积码打下了坚实的基础。另外还介绍截尾卷积编码，对卷积码编码有了更 深的了解和认识。 1 4 ( v i t e r b i ) 算法。维特比算法是基于码的网格图( t r e i l i s ) 基础上的一种最大似然译码算法， 是一种最佳的概率译码算法。后来o m u r a 证明维特比算法等价于求通过一个加权图的最 短路径问题的动态规划解。最后，f o m e y 指出它事实上就是卷积码的最大似然译码算法， 即译码器所选择的输出总是能给出对数似然函数值为最大的码字【l 】。 虽然代数译码所要求的设备简单，运算量小，但其译码性能( 误码) 要比概率译码 方法差许多。在码的约束度较小时，v i t e r b i 算法比序列译码算法效率更高、速度更快， 译码器也较简单。因而从v i t e r b i 算法提出以来，无论在理论上还是在实践上都得到了极 其迅速的发展，并广泛应用于各种数字传输系统，特别是移动通信系统中。 3 2 最大似然译码 因为v i t e r b i 算法是卷积码的最大似然译码算法，先介绍最大似然译码原理。信道编 码是为了提高可靠性的编码，而在数字通信中，通信可靠性的指标一般是采用平均误码 率p e 来表示的。平均误码率p e 是错判概率的数学期望， = 尸( c ) p ( e lc)(3-1) 北京邮电大学硕士学位论文 卷积码编码与维特比译码加速器设计 其中错判概率 胞lc ) = 币c l 国 ( 3 2 ) 式中c 为发送码字，c 为收端恢复的码字。 平均错判概率最小的最佳译码应符合最大后验概率准则( 即m a p 准则) 。接受端收 到y 后，最佳译码器的输出应该是 = a r g c cm a x p ( cl 少) )( 3 3 ) 式中的p ( c l y ) 是后验概率。 上式的含义是：在码字集合c 的所有可能码字中寻找出后验概率最大的一个码字昨 晚译码结果，也就是在该编码器的网格图中所有可能的路径集合中寻找出最大后验概率 的一条路径作为译码结果。 假设各可能的码字是先验等概的，即 p ( q ) = 尸( c 2 ) = = 素 ( 3 川 由b a y e s 公式，有 p ( c i 加掣铲 ( 3 - 5 ) 式中的p ( y j c ) 是似然函数。 在各码字先验概率等概条件下，后验概率最大者必然似然概率最大，故最佳m a p 译码即最大似然( m l ) 译码。 对于离散无记忆信道，设发送码序列长度为l 个符合，则 p ( y l c ) = 兀p ic ，) ( 3 - 6 ) l o g p ( y i c ) = l o g 兀p ( y zic f ) = l o g p ( y lic f ) ( 3 7 ) 于是最大似然( m l ) 译码可看作是对于给定接受序列弘求其对数似然函数的累加值为最 大的路径。称对数似然函数累加值为路径度量。 若该离散无记忆信道又是二进制对称信道( b s c ) ，则 差错概率p o l o ) = p ( 0 1 1 ) = p ； 正确概率p ( 1 i ) = p ( 0 1 0 ) = 1 - p ； 发送码序列( 长度为l 个符合) 经信道传输，发送d 个符合错误，则似然函数可写 为 1 6 北京邮电大学硕士学位论文卷积码编码与维特比译码加速器设计 对数似然函数 e ( y l c ) = n p ( 乃i q ) = ，一( 1 一尸) 纠，一 瑚 ( 3 8 ) p = ( 南) 以 ( 1 一 l o g p ( y i c ) = l o g 兀嘞i q ) = l o g p ( y t