（信号与信息处理专业论文）参数化viterbi译码器的fpga实现.pdf

哈尔滨工程大学硕士学位论文 摘要 维特比算法作为一种最大似然算法可以在网格图上找出最似然的状 态转移路径，已广泛应用在各种信号处理和数字通信领域。由于它的前 向纠错性能，维特比译码器广泛应用于各种数字通信系统如：卫星通信 系统、g s m ( g r o u ps p e c i a lm o b i l e ) 、3 g ( 第三代移动通信) 、d v b ( 欧 洲数字视频广播) 标准和a t s c ( 美国先进电视) 标准等。 本文以某型号接收机的应用为背景，主要论述了如何实现基于f p g a 的参数化的v i t e r b i 译码器的知识产权( i p ) 核。文中详细论述了译码器 的内部结构、v e r i l o g h d l ( 硬件描述语言) 实现、仿真测试等。这些可 变的参数包括：码型、a c s ( 加比选) 单元的数目、软判决比特数、回 溯深度等。用户可以根据自己的需要设置不同的参数由开发工具生成不 同的译码器用于不同的系统。 本文的创新之处在于：针对f p g a 的内部结构提出了一种新的累加 度量r a m 的组织形式，大大节省了嵌入式r a m 块；提出了一种新的 累加度量值的归一化办法：此外还给出了用m a t l a b 建模得到软判决信息 辅助仿真工具进行电路仿真的方法，大大提高了仿真的速度。 所设计的( 2 ，1 ，7 ) 连续型5 比特软判决译码器已经应用于某型号 接收机，经受了实际应用的考验产生了巨大的经济效益。 关键词：卷积码；维特比译码器：参数化； 软判决 哈尔滨工程大学硕士学位论文 a b s t r a c t t h ev i t e r b ia l g o r i t h mi su s e dt of i n dt h em o s t l i k e l ys t a t et r a n s i t i o n s e q u e n c ei nas t a t ed i a g r a m ，a n dh a sb e e nw i d e l yu s e di ns i g n a lp r o c e s s i n g a n dd i g i t a lc o m m u n i c a t i o n s p e c i f i c a l l yd u et ot h e i rf o r w a r de r r o rc o r r e c t i o n c a p a b i l i t y ，t h ev i t e r b id e c o d e r h a so f t e nb e e nu s e di nd i g i t a lc o m m u n i c a t i o n s y s t e ms 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 g ，d v ba n da t s c i n t h i sp a p e r ，ap a r a m e t e r i z e dv i t e r b id e c o d e rb a s e do nf p g ai s p r e s e n t e d t h es t r u c t u r eo ft h ed e c o d e r , t h er e a l i z a t i o no fv e r i l o gh d la n d t h es i m u l a t i o no ft h ed e s i g n e dd e c o d e ra r ed i s c u s s e dd e e p l y t h e s ea l t e r a b l e p a r a m e t e r si n c l u d eg e n e r a t i n gp o l y n o m i a l s ，t h en u m b e ro fa c s ，t h en u m b e r o fs o f td e c i s i o nb i t sp e rs y m b o l ，t r a c e b a c kl e n g t ha n ds oo n t h eu s e rc a ns e t t h ep a r a m e t e rw h i c hh en e e d s a st h en e wi nt h i sp a p e r ，an e wm e m o r y o r g a n i z a t i o n ，an e w n o r m a l i z a t i o nm e t h o da n d a w a y o f g e t t i n g s o f t d e c i s i o nb i t sh e l p e db ym a t l a ba r ep r e s e n t e d t h ed e s i g n e ds o f t d e c i s i o nv i t e r b id e c o d e rh a sb e e nu s e di n s o m e s 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 k e y w o r d ：c o n v o l u t i o n a lc o d e s ，v i t e r b id e c o d e r ，p a r a m e t e r i z e d s o f i d e c i s i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 日期：川厂年1 ，月讶日 堕玺鎏三翟盔兰鎏圭主售笙苎 1 一l _ _ _ _ _ l i l _ _ _ i i - l _ _ i - _ _ l l _ l - _ l _ _ _ _ _ l l _ _ l _ l 。- 一一 1 1 概述 第1 章绪论 在数字通信系统里为保证通信的可靠性往往要进行差错控制，常用 的办法就是进行信道编码，也就是在原始信息里通过某种规则加入冗余 信息来监督原始信息以达到差错控制的目的。 香农( s h a n n o n ) 信道编码定理指出：若有一离散、平稳、无记忆信 道，其容量为c ，只要待传送的实际信息率r c 时任何编码的p 必大于0 1 1 】。该定理的证明是建立在 随机编码的概念来完成的，仅给出了信道编码的理论极限性能和今后应 该努力的方向。这种理论上存在的随机性“好码”似乎可以随机选取， 但到底怎么选至今还没有找到有效的方法。 近5 0 年来，在信息技术发展和实际需要的不断推动下，人们一直在 寻求实现复杂度合理的更优秀的编译码方法，去逼近s h a n n o n 理论的理 想界限。令人鼓舞的是，在这个过程中已经取得了许多伟大的进展。从 早期的分组码、代数码，到r s 码，到后来的卷积码，以及今天的t u r b o 码、l d p c 码，所能达到的性能和s h a n n o n 限间的距离被不断缩小。现 在在实际应用中最常用的并已经成为许多行业标准的纠错编码有b c h 码、r s 码、卷积码和上世纪9 0 年代后发展起来的t u r b o 码。 卷积码最早在1 9 5 5 年由爱里斯( e l i a s ) 提出。自从1 9 6 7 年维特比 ( v i t e r b i ) 提出v i t e r b i 算法一一种最大似然译码算法以来，卷积码得到 了广泛的应用。算法的优良特性和集成电路产业的发展为v i t e r b i 译码器 的实用打下了坚实的基础。v i t e r b i 译码器已广泛应用于各种数字通信领 域如：数字卫星通信系统、g s m ( g r o u ps p e c i a lm o b i l e ) 、3 g ( 第三代 移动通信) 、d v b ( 欧洲数字视频广播) 、a t s c ( 美国先进电视1 等。 算法提出以来国外对如何实现v i t e r b i 译码器进行了大量研究，提出 了许多好的硬件组织办法和软件流程。例如：用回溯法代替传统的寄存 器迭代法获得译码信息；贝尔实验室最先提出了乒乓操作等等。同时随 哈尔滨工程大学硕士学位论文 着应用的深入，为在不影响性能的前提下减少硬件消耗和减小功耗还提 出了其他的一些改进译码算法，进而又推动了应用的发展。在国内，9 0 年代以前由于受制于集成电路产业的发展，大多数只是进行一些相关理 论研究和用通用计算机实现译码算法，市场上的硬件v i t e r b i 译码器几乎 都是国外a s i c ( 专用集成电路) 产品。9 0 年代以后随着国内集成电路产 业的发展和f p g a ( 现场可编程门阵列) 技术的发展，使得研究如何用 f p g a 和d s p ( 数字信号处理器) 实现v i t e r b i 译码器成为最近几年的热 点。用f p g a 实现t e r b i 译码器也常见报道，但是这些译码器都是针对 具体的应用，所设计的译码器的结构都已经确定。如何实现一个参数化 的译码器i p ( i n t e l l e c t u a lp r o p e r t y ，知识产权) 核，它可以在不同的开 发平台上实现各种各样结构的译码器，还未见报道。 v i t e r b i 译码器的实现不外乎两种：软件和硬件。随着电子技术特别 是半导体技术的发展，现在绝大多数的电子系统设计越来越多地使用 d s p ( 数字信号处理器) 、f p g a ( 现场可编程门阵列) 和a s i c ( 专用集 成电路) 。d s p 多用于复杂算法的部分( 如：多重i f - t h e n e l s e 结构) ，f p g a 和a s i c 则常用于前端处理( 如：f i r 滤波、信道均衡、伪码解扩、同 步、编译码等等) 。 用d s p 实现的v i t e r b i 译码器，主要用于速度较慢的场合，通用性和 灵活性受到限制；用a s i c 实现的v i t e r b i 译码器，它的速度虽然非常快 价格便宜，但它也只能实现某种特定的功能( 码型固定) ，设计完成后 不能对其进行改动，灵活性和通用性也受到限制：而f p g a 以其可编程 的灵活性广受小批量应用以及l c ( 集成电路) 功能验证的青睐。随着半 导体亚微米技术的发展，f p g a 的芯片密度已经达到了百万门级甚至千 万门级，它的设计越来越接近于a s i c 的设计，价格也越来越接近a s i c ， 因此f p g a 也被称为可编程的a s i c 。在某些应用领域己出现f p g a 取 代了a s i c 的趋势，它们之间的互相竞争也进步推动了半导体技术的 发展。 日益紧凑的系统要求设计人员尽可能在一片硅片上集成更多的功 能，也就是所谓的s o c ( s y s t e m o na c h i p ，单芯片系统) 。目前，d s p 、 m c u 、p c i 总线控制等复杂的功能都可由一片f p g a 完成。由于f p g a 芯片的密度不断增加和第四代e d a ( 电子设计自动化) 开发工具的使用， 利用f p g a 芯片实现s o c 已经成为可能，这项技术称之为s o p c ( s y s t e m o nap r o g r a m m a b l ec h i p ，可编程单芯片系统) 。s o p c 技术既具有基子 2 哈尔滨工程大学硕士学位论文 模板级设计的特征，又具有基于a s i c 的系统级芯片设计的特征。 一个复杂的数字电路系统( 可以认为是一个s o p c ) 可分为若干个模 快，其中包括些通用的模快如：f f t 、f i r 、i i r 、v i t e r b i 译码、r s 译 码、p c i 总线接口、调制解调、信道均衡等。设计者没有必要全部自己 设计这些模快，那样无疑会浪费宝贵的时间和人力。这时通用i p 模快就 应运而生了，设计师只要购买这些i p 模快和自己的其它核心单元连接起 来，利用e d a 工具完成系统集成、仿真和测试，从而大大缩短了设计 周期和上市时间。因此要使设计成功，就要更多的采用i p 模块。可以预 见随着i p 技术的发展，将来数字电路设计时，方案取定后便不再是向不 同的半导体公司购买所需的各种芯片，而是相应的i p 模快。 为更好的满足设计人员的需要和市场要求，各大f p g a 提供商给用 户提供了丰富的i p 核。这些核都是经过测试、验证和优化的。用户可以 先免费得到用于功能验证的i p 模快，当然这样的模快只能用于验证功能 而不能形成用于下载到f p g a 的配置文件，仿真测试通过以后由用户决 定要不要购买i p 核。以a l t e r a 公司为例，它和它的第三方合作伙伴 ( a m p p ，a l t e r am e g a f u n c t i o np a r t n e r sp r o g r a m ) 提供了1 0 0 多个i p 模 快，已涉及到数字信号处理、通信、总线接v i 和微处理器及其外围设备 等许多领域。 i p 设计需要一个很好的平台，h d l ( 硬件描述语言) 及其开发工具 就是这样一个平台。现在最常用的两种硬件描述语言是：v h d l ( v j r v h i g hs p e e di n t e r r a t e dc i r c u i th d l ) 和v e r i l o gh d l ，两者都已成为i e e e 的标准。v h d l 比较严谨难学适合大规模的系统级设计：v e r i l o gh i ) l 易学适合底层设计。美国东海岸和欧洲倾向于v h d l ，美国西海岸和亚 洲倾向于v e r i l o g h d le 随着i e e e - v e r i l o g h d l 一2 0 0 1 标准的出台v e r i l o g h d l 的系统级功能得到了增强，因此它已经成为众多电子工程师的首 选。 知识产权可以带来高附加值的产品，积极开发具有自主知识产权的 i p 块，在s o p c 领域占有一席之地，既符合我国国情，又具有重要意义。 半导体制造技术的两大发展趋势之一是深亚微米制造技术，另一个就是 i p 模快的设计。前者需要巨额资金投入和较长的生长周期，相比之下开 发具有自主知识产权的i p 模快是一条快捷方式。它可以充分发挥设计人 员的聪明才智，利用已有的高密度f p g a 器件和e d a 工具，在较短的 时间内开发出高质量的i p 模快和高性能的专用芯片，迅速占领市场。同 啥尔滨工程大学硕士学位论文 时a s i c 的前端设计一般也是利用f p g a 器件完成的，因此还可以以此 为契机，推动我国的a s i c 设计和制造水平。因而开发数字电路系统中 常用的各种i p 模快的意义就不言自明了。 通常设计一个成功的i p 模快，必须要有很好的设计思想和算法，先 进的开发工具，科学的设计流程，标准的接口方式，严格的测试验证手 段，完善的文档说明，以及良好的灵活性、易用性。 1 2 课题有关技术指标要求以及实现方法 经过最近几年的快速发展，国内自主开发的v i t e r b i 译码器已经占据 了一定的市场。但这些译码器往往都是各单位针对具体应用( 码型等参 数都以固定) 设计的，通用性、可移植性差。相比之下用h d l 语言开 发的参数可变的i p 功能模块的优势显而易见了。f p g a 提供商如a l t e r a 公司从1 9 9 9 年至今也经推出了3 个版本的v i t e r b i 译码器的i p 核，用户 只能当作黑匣子来使用而不知其h d l 源代码，且必须付出知识产权使 用费。 本课题以航天科技集团某研究所某型号接收机为背景，要求用a l t e r a 公司的f p g a 实现一个码型固定的工作在连续方式的v i t e r b i 译码器。具 体参数要求如下： ( 1 ) 码型：( 2 ，l ，7 ) 卷积码，生成多项式( 9 1 ，1 2 1 ) ： ( 2 ) 软判决比特数：s 比特( 3 2 电平) ； ( 3 ) 译码方式：连续译码； ( 4 ) 系统时钟：5 0 m h z ( 5 ) 译码速率：不低于3 5 0 k b p s ： ( 6 ) 所消耗的硬件资源，包括l e s ( 逻辑单元数目) 、嵌入式r a m 块数，以及最高工作频率要和a l t e r a 公司的i p 核的性能相当。 最后要在此基础上实现1 2 码率常用码型连续译码v i t e r b i 译码器i p 核。其参数可交，这些参数包括码型( 生成多项式) 、软判决量化比特 数、a c s ( 加比选) 单元数、回溯深度等等。用户可以根据自己的需要 选择不同的参数由开发工具自己生成不同结构的译码器。 考虑到应用背景，本设计采用了传统的v i t e r b i 算法。具体实现时， 先根据算法把整个译码器分为几大功能模块，分清各模块之间的接口关 哈尔浜工程大学硕士学位论文 系。然后用v e r i l o g h d l 分别实现各个模块，对各模块进行仿真测试。 当所有的模块完成以后，再把所有的模块按照接口关系连接起来进行逻 辑综合、布局布线和仿真测试。 设计所用到的工具有：a l t e r a 公司的f p g a 开发工具q u a r t u s i l 4 0 、 m o d e l 公司的仿真工具m o d e l s i m 5 7 s e 以及m a t l a b 6 5 。 值得一提的是：由于本设计仿真测试时，需要模拟信道真实情况， 输入的软判决信息必须是含有噪声的。为此对编码一调制一发射一解调 进行m a t l a b 建模，得到原始信息、含有噪声的软判决信息和信噪比参数， 然后用m a t l a b 对软判决信息数据文件做一定的处理转为q u a r t u s l l 4 0 的 激励波形去仿真，得到仿真后的文件，最后再用m a t l a b 对含有译码信息 的文件进行相关处理就能直观地得到译码信息。比较编译码前后的信息 就可以对译码器的性能做出初步判断，这是第一种方法。第二种方法也 是先用m a t l a b 进行编码一调制一发射一解调建模，得到原始信息、含有 噪声的软判决信息。将得到的软判决信息进行一定的格式转化后，在 m o d e l s i m 5 7 s e 环境下用v e r i l o gh d l 编写测试模块，从含有软判决信 息的文件里读出其值按照一定的节奏作为激励加到模块上看结果( 响 应) 。由于仿真工具先进，这种方法要比第一种方法节省2 1 3 的仿真时间。 当然后仿真通过后的设计还要下载到系统里，经实际系统的验证才 能作为接收机的译码器使用。 最后还要向用户提供详细的使用说明书。 1 3 本论文结构安排 第1 章，绪论：简述课题的相关背景、国内外动态以及目的和意义， 提出研究的主要内容及技术指标。 第2 章，卷积码的编译码原理：是理论知识，主要论述卷积码的编码 和译码原理。 第3 章，译码器的f p g a 实现：针对参数固定的译码器，根据算法 所划分的各功能模快分别详细讨论其f p g a 实现；然后论述如何对综合 后的电路进行仿真、测试。这一章是全文的重点。 第4 章，参数化i p 核的开发。 第5 章，总结。 堕j 鎏苫堡盔主翌圭耋垡鲨銮 第2 章卷积码的编译码 2 1 卷积码的编码及应用 2 1 1 卷积码的编码 对于一个信道，最不确定的因素就是噪声千挠，引起差错的往往也 是噪声。就噪声引发差错的统计规律而言可分为随机差错信道和突发差 错信道。对于随机差错信道，它的差错主要是由加性高斯自噪声 ( j 州g n ) 引起的。 根据编码信道的输出是二电平、多电平或是模拟量( 多电平数的极 限) 它可分为：二进制对称信道( b s c ) 、离散无记忆信道( d m c ) 、离 散输入连续输出信道。b s c 信道输入输出都是二进制的，也就是检测器 实行门限硬判决；d m c 信道的输入是二迸制输出是多进制的，也就是 检测器进行多电平量化，亦即所谓软判决t 离散输入连续输出信道是 d m c 的极限情况。 从香农( s h a n n o n ) 信道编码定理可以看出要降低误码率，通过某种 规则加入冗余信息( 编码) 是常用途径之一。常用的这些编码“规则” 有：分组编码、卷积编码等等。寻找好的编码方法直是信息论研究的 重点与核心。在相同误码率的条件下，编码比不编码可以节省几个d b 的信号功率，也就是说在同样的信噪比条件下编码以后可以降低发射和 接收功率。 卷积编码是在实际中应用极为广泛的一种编码方法，可以用( n ，k ， m ) 来表示。其编码器是一个由k 个输入端、n 个输出端且具有m l 级 移位寄存器所构成的有限状态的有记忆系统，m 称之为编码约束长度， 它表示编码码字的产生受m 个信息分组的制约；k n 表示编码效率。 卷积码至今尚未建立像线性分组码那样有严密而完整的数学分析体 系，分析它的方法也很多，但都有一定的局限性。描述卷积码的方法大 致可以分为解析表示法和图形表示法。解析法又分为生成矩阵法、码多 项式法等；图形表示法也可以分为状态图法、树图法、网格图法等。 6 晗尔滨工程大学硕士学位论文 下面结合( 2 ，1 ，3 ) 卷积码来说明常用的几种表示法：码多项式法、 状态图法和网格图法。图2 1 是( 2 ，l ，3 ) 卷积码编码器的结构图。从 图中可以看出，它是由k = l 即一个输入端，n = 2 即两个输出端，1 1 1 1 = 2 即两级移位寄存器组成的有限状态的有记忆系统，o 表示模2 和运算。 若以g l ( i _ o ，1 ，2 ) 表示各节点的值是否参加模2 和运算：卫，= 1 表示 参加运算；9 1 = o 表示不参加。此时上一路的生成多项式可以表示为： g = ( g o g l 9 2 ) = ( 1 0 1 ) = 1 + x 2 = 5 ( 2 1 ) 下一路的生成多项式可以表示为： g 2 = ( g o g l 9 2 ) = ( 1 1 1 ) = 1 + z + x 2 = 7( 2 2 ) 这样( 2 ，1 ，3 ) 卷积码的生成多项式就可以表示为g = ，g 。】= 5 ，7 。 如果输入的信息序列u = ( 1 0 1 1 1 ) = l + x 2 打3 协4 ，则相应的编码结果可以表 示为： 和 c 1 = ( 1 + 工2 + 工3 + 工4 ) ( 1 + 工2 ) = 1 + x 2 + z 3 + 工4 + z 2 + z 44 - x 5 十x 6 = 1 + 2 x 2 + x 3 + 2 x 4 + x 5 + x 6 = l + x 3 + x 5 + x 6 = ( 1 0 0 1 0 1 1 ) c 2 = ( 1 + z 2 + x 3 + x ) ( 1 + x + x 2 ) = 1 + x 2 + x 3 + x 4 + x + x 3 + x 4 + 工5 + x 2 + x 4 + x 5 + x 6 = 1 + x + 2 x 2 + 2 x 3 + 3 x 4 + 2 x 5 + x 6 = 1 十x + x 4 + x 6 = ( 1 1 0 0 1 0 1 ) 图2 1 ( 2 ，i ，3 ) 卷积码编码原理图 相应的编码信息组为( 1 1 ，o l ，0 0 ，1 0 ，o l ，1 0 ，i i ) 。除了上面的生 成多项式表示法以外，还可以用比较形象的的状态图、网格图来表示。 7 哈尔滨工程大学硕士学位论文 顾名思义，状态图法就是对编码寄存器做相应的状态标定，然后讨 论编码规则的方法。本文采用如下的状态标注法：寄存器的内容按照从 右向左的顺序所代表的二迸制数的大小作为状态标号的下标。由图2 2 可以看出寄存器总的状态数为2 k m = 2 2 = 4 种，其状态标号为s o = 0 0 ， s l = 1 0 ，s z = 0 1 ，s 3 = 1 1 。等式右边是寄存器内容，等式左边是状态标号。 由于每次的输入有两种可能：0 或者1 ，所以每次更新后的状态和编码 输出可能也只有两个。下面同样以输入信息序列为u = ( 1 0 1 1 1 0 0 ) 为例来 说明状态转移图： ( 1 ) 首先，移位寄存器复位，初始状态为s o ( 0 0 ) ： ( 2 )输入u = l ，输出c l = 1 0 0 = 1 ，c 2 = 1 0 0 0 0 = 1 ，编码码字为( c 1 c 2 ) = ( 1 1 ) ，移位寄存器状态改为1 0 ( s 1 ) ； ( 3 ) 输入u = o ，可算出c i = 0 ，c 2 = 1 ，编码输出码字为( 0 1 ) ，移位 寄存器状态改为0 l ( s 2 ) ： ( 4 ) 输入u = l ，可算出e l = o ，c 2 = 0 ，编码输出码字为( 0 0 ) ，移位 寄存器状态改为1 0 ( s i ) ： ( 5 ) 输入u = l ，可算出c l = l ，c 2 = 0 ，编码输出码字为( 1 0 ) ，移位 寄存器状态改为1 1 ( s 3 ) ； ( 6 ) 输入u = t ，可算出c l = o ，c 2 = l ，编码输出码字为( 0 1 ) ，移位 寄存器状态仍为1 1 ( s 3 ) ； ( 7 ) 输入u = 0 ，可算出c l = l ，c 2 = 0 ，编码输出码字为( 1 0 ) ，移位 寄存器状态改为0 1 ( s 2 ) ； ( 8 ) 输入u = o ，可算出c i = 1 ，c 2 = 1 ，编码输出码宇为( 1 1 ) ，移位 寄存器状态改为0 0 ( s o ) ； ( 9 ) 输入u = o ，可算出e l = o ，e 2 = o ，编码输出码字为( 0 0 ) ，移位 寄存器状态改为0 0 ( s o ) ； 可见经过最后输入两个0 ，编码寄存器又回到了初始状态s 。( 0 0 ) 。 得到的编码序列c = o i ，0 1 ，0 0 ，1 0 ，0 1 ，1 0 ，1 1 ，0 0 ) ，这和用生成多 项式法得到的编码序列是一样的。 按照上述步骤可以画出如图2 2 的状态转移图。四个圆圈内的分别表 示状态及对应的寄存器信息，状态之间的连线与箭头表示状态转移方 向，分支上的数字表示状态转移时相应的编码输出( 码字) ，而括号内 的数字则表示相应的输入信息。例如，假定初始状态为s o ( o o ) ，若输 入信息位为1 ，则输出码字为1 1 ，下一时刻的状态为s l ( 1 0 ) ；若输入 信息位为o ，贝【j 输出码字o o ，- f - - 时刻的状态仍旧是s o ( o o ) 。它实际上 哈尔滨工程大学硕士学位论文 就是一个有限状态机。 状态转移图虽然表现了各状态转移的去向，但不能记录状态转移随 时间的轨迹。另一种描述法一网格图法( 也称栅格图法) 可以弥补这一 缺陷。它可以将状态转移展开在时间轴上，使整个编码的全过程跃然纸 上。特别是在卷积码的概率译码中，它起着极其重要的作用。网格图以 状态为纵轴，以时间为横轴，将平面分割成格状就像网格一样。状态以 及状态转移的定义和状态转移图法一致，也是用箭头表示转移。箭头上 方标出的是状态转移时的输出码字( 输入信息) 。对于k = l 的情况还可 以用箭头的虚实来表示导致状态转移的输入是0 还是1 ，实线表示0 虚 线表示1 。上一次转移与下一次转移在图上首尾相连以体现时间的变化。 图2 _ 3 是( 2 ，1 ，3 ) 卷积码的网格图。 o o ( o ) 图2 2 ( 2 ，1 ，3 ) 卷积码的状态图 假设初始状态为s o 。输入的信息序列仍为u = ( 1 0 111 0 0 ) ，则在网格图 上状态转移轨迹为s o s i s t s l s 3 一s 3 一瓯一s o ，相应的编码输出为 ( 1 l ，0 1 ，0 0 ，1 0 ，0 1 ，1 0 ，1 1 ) 。对于不同的输入总能从网格图上找 到唯一的一条路径( 轨迹) 与之相对应。反过来，如果知道了状态转移 的路径也就知道对应的输入信息。因此如果事先知道了状态转移路径为 s o - - s 2 一s l s 2 一s 3 一s 3 一s 1 一s o ，则必然输入的信息序列为( 1 0 111 0 0 ) 。 这对于卷积码的v i t e r b i 译码中很重要，译码时就是根据最大似然准则找 到这条路径，找到了这条路径也就找到了相应的输入信息序列。 上述三种表示方法各有千秋，是理解卷积码编译码方法的基础。 9 哈尔滨工程大学硕士学位论文 s o ( 0 0 ) s l ( 1 0 ) s 2 ( 0 1 ) s 3 ( 1 1 ) 0 0 。0 0 。- 0 0 一 吵0 、1 罗飞t 少鼍t - i 矿妯1 | 一一1 丘一而一i 图2 3 ( 2 ，1 ，3 ) 卷积码的网格图 2 1 2 卷积码的应用 从信道编码定理看，卷积码是一种很有前途的能达到信道编码定理 所提出的码型，广泛应用于各种领域如：数字卫星通信系统、遥测外测 系统、g s m ( g r o u ps p e c i a l m o b i l e ) 、3 g ( 第三代移动通信) 、各种数 字电视标准等等。例如：绝大多数卫星通信采用的是( 2 ，1 ，7 ) 卷积 码：g s m 采用了( 2 ，1 ，5 ) 卷积码；c d m a 的i s 9 5 标准采用的是( 2 ， 1 ，9 ) 卷积码；3 g p p ( 第三代移动通信伙伴关系) 的w c d m a t 向信道采 用的是( 2 ，l ，9 ) 卷积码，反向信道采用的是( 3 ，l ，9 ) 卷积码；c c s d s ( 空 间数据系统咨询委员会) 也把卷积码作为实时要求较高业务的信息纠错 编码。此外卷积码还和r s 码作为一对黄金搭档常常级连使用，r s 码做 为外码卷积码作为内码用于d v b ( 欧洲数字视频广播) 标准和a t s c ( 美 国先进电视) 标准等等。t 不同结构的卷积码有不同的特性，卷积码也分成系统卷积码和非系 统卷积码等等，但这些不是本文研究的范畴。本文所选用的卷积码都是 经过计算机搜索验证的好码。 1 0 啥尔滨工程大学硕士学位论文 2 2 卷积码的译码 2 2 1 最大似然译码 卷积码的译码方法基本上可分为两大类：代数译码和概率译码。这 里重点介绍和本文有关的概率译码，它是实际应用中最常采用的译码方 法。 1 9 6 7 年，v i t e r b i ( 维特比) 引入了一种卷积码的译码算法，就是著 名的v i t e r b i 算法。后来o m u r a ( 小村) 证明v i t e r b i 算法等价于求通过 一个加权图的最短路径问题的动态规划解。最后f o r n e y ( 福尼) 指出它 事实上就是卷积码的最大似然译码算法。即译码器输出总是能给出对数 似然函数值为最大的码字。 设信息序列为u ，编码序列为c ，信道输出的r 是一个二( 或q ) 进 制的序列，译码器的任务就是根据一套译码规则，由接收序列r 给出与 发送信息序列u 最接近( 最好完全相似) 的估值序列u 。由于u 和c 有一一对应的关系，这等价于译码器根据r 产生一个c 的估值序列c 。 当接收序列r 给定时，译码器的条件译码错误概率定义为： p ( e r ) = p f c c g ) 所以译码器的错误译码概率为： 最= p ( e ，r ) p ( r ) 拧 p ( r ) 是接收r 的概率，与译码方式无关，所以译码错误概率最小的最佳 译码规则是使下式成立： m i n p = m i n p ( e r ) p ( r ) m i n ，( c c l i r ) m i n p ( c c r ) ；m a x p ( c 。= c r ) ( 2 3 ) r r 因此，如果译码器对输入的r ，能在码字中选择一个使概率最大的码字 c i 作为c 的估值序列，则这种译码规则一定使译码器输出的错误概率最 小。这是一种最大后验条件概率，一般来说信道模型并不使用后验条件 概率，而只表明转移概率。可以通过贝叶斯公式找到这两种概率之间的 关系： 哈尔滨工程大学硕士学位论文 p ( c ，r ) ：丝! ! 型! 曼上 ，【埘 可知，如发送端的每个码字的概率p ( c ) 均相同，且p ( r ) 与译码方式无 关，所以 m a x p ( c r ) jm a x p ( r c f ) ( 2 - - 4 ) 如果一个译码器的规则能在所有码字中选择菜一个c i 使( 2 4 ) 式最大， 则这样的译码规则称为最大似然译码。p ( r c ) 称为似然函数。 对于离散无记忆信道( d m c ) 有： m a x p ( r c = c ) = m a x 兀p ( _ c ，= c ，) f = 0 式中l 为码元的长度。把( 2 - 5 ) 式改写成对数形式： i = l lk - l m a x l o g 丌p ( _ c ，= c a = m a xy l o g p ( r , c ，= c ，) ( 2 5 ) ( 2 6 ) 我们把按公式( 2 - 5 ) 进行译码的算法称为最大似然算法，同时称求和项 为对数似然函数，有时就简称似然函数。 而对于对称二进制信道( b s c ) ，可以证明求最大似然函数值就等效 求晟小汉明距离即： - - 1h l - i m a x l o g p ( r t c ，= q ) = m i n d ( r ，c ) = r r f i n d ( m ，q ) ( 2 7 ) i oi = 0 其中d ( r ，c ) 表示求汉明距离，也就是求两个序列中对应位置比特不 同的个数。 2 2 2v i t e r b i 算法 前面说过，网格图是理解v i t e r b i 算法的核心。而v i t e r b i 算法的实质 就是根据接收的序列r 在网格图上找到一个和c 最相似的路径，知道了 这条路径，相应的u 也就知道了。其核心思想是依次在每个时刻对网格 图相应列的每个点( 对应于编码器该时刻的状态) ，按照最大似然准则 比较所有以它为终点的的路径，只保留一条具有最大似然值的路径，称 之为幸存路径，而将其他路径堵死弃之不用，故到了下一时刻只要对幸 存路径延伸出来的路径继续比较即可。即接收一段，计算、比较一段保 留下幸存路径，如此反复直到晟后。 算法的实际操作细化如下：首先要给每个状态节点分配幸存信息存 哈尔滨工程大学硕士学位论文 储器( p m ) 和累加度量值存储器( m m ) 。 ( 1 ) 卢o ，初始化。p m m m 清零，实际上p m 的值可以任意但为了工 程实现方便都是清零； ( 2 ) f = f + 1 ； ( 3 ) 接收新的一组数据，也就是该时刻接收的编码信息。对于每一个 状态： a 进行似然函数计算，也就是计算接收的信息和相应的编码信息的 似然函数值( 距离) ； b 从m m 寄存器里取出前时刻的路径度量值； c 进行累加一比较一选择( a c s ) 运算，得到新的幸存路径和路径度 量值； d 将新的幸存路径和度量值存入p m 和m m ： ( 4 ) 如果艇l ( l 为接收码元长度) ，回到步骤( 2 ) ，否则继续往下做： ( 5 ) 求m m 中最大元素( 最似然) 对应的路径从p m 中输出判决结果。 从中可以看出a c s 单元是整个译码器的核心，实现的译码器也因为 所用的a c s 数目的不同分为：全并行、全串行、部分并行或称之为时 分复用方式。这在后面的参数化实现部分会有论述。 下面以前一节的( 2 ，1 ，3 ) 卷积码为例来说明v i t e r b i 算法的译码 方法。假设输入的信息序列仍为u = ( 1 0 1 1 1 0 0 ) ，编码器输出c = ( 1 1 ， i o ，0 0 ，0 1 ，1 0 ，o l ，1 1 ) ，通过b s c 信道送入译码器的的序列r = ( 1 0 ， 1 0 ，0 0 ，0 1 ，1 1 ，0 1 ，1 1 ) 出现两个错误，现在利用v i t e r b i 算法来求u 的估值序列u 。 基于图2 3 的网格图，v i t e r b i 译码器接收序列r 的过程如图2 4 所示。 图中画出了各时刻进入每一状态的的留选路径和其度量值d ( 这里是最 小汉明距离) ，以及相应的译码估计信息序列u 。到了第七时刻，留选 路径就剩一条，相应的信息估值序列为u = ( 1 0 1 1 1 0 0 ) ，接收时的两个 错误得到纠正。 堕玺鎏三耋盔主鎏圭耋垡鲨銮 1 第一时刻接收子码r 0 ：1 0 5 第五时刻接收子码r 4 = 1 1 d u s o 1 ( 0 ) s li f 、l ( 1 ) 2 第二时刻接收于码r i = 1 0 du l ! 麓0 0 0 5 3 1 03 ( 0 1 1 、 4 第四时刻接收子码r 3 。o l du i 繇 s 3 、 ( 0 0 0 0 ) ( 0 0 0 1 ) ( 1 0 1 0 ) ( 1 0 1 1 ) 7 第七时刻接收子码r 6 = i i du 3 ( 1 0 l 1 0 0 ) 2 ( 1 0 1 1 1 0 ) 噱，。：矗：厉 i 、曩；s 3- v 图2 4 v i t e r b i 译码器接收序列r 的过程 2 2 3v i t e r b i 译码器的原理图 du 2 ( 1 0 1 n 0 0 ) 根据上面的算法，工程上实现v i t e r b i 译码器的原理图如图2 5 所示。 从图中可以看出整个译码器由度量计算( b m g ) 、加比选( a c s ) 、累加 度量r a m 、幸存信息r a m 、回溯判砍( t r a e e b a c k ) 以及控制单元组成。 译码器接收被噪声污染的编码序列后，先在路径度量计算( b m g ) 单元计算接收码元和各个编码期望码字的路径度量值送给加比选 ( a c s ) 单元。对于每一个状态，a c s 单元从累加度量r a m 读出转移 到该状态的前两个状态的累加度量值和相应的路径度量值进行加比选 运算，得到新的累加度量值存入到累加度量r a m ，同时得到l 比特的 幸存信息送入缓存器，等所有状态都运算完一起存入幸存信息r a m 。 达到回溯- 深度t b l ( t b l ，5 8 ( m - 1 ) ) 1 7 j 后，回溯判决单元根据最小的 累加度量值所对应的状态( 最小状态) 和幸存信息r a m 的幸存信息用 回溯的办法往前回溯t b l 步即可得到信息比特。各单元功能的简述如 下，后面将有详细讨论。 度量计算单元主要按照最大似然准则计算似然函数的值，也就是要 计算接收序列是各种期望码字的可能性大小。前面讲过对于硬判决( b s c ，唧m m um咖mm 哈尔滨工程大学硕士学位论文 信道) 就是计算汉明距离。对于实际应用中最多的软判决( d m c 信道) ， 工程上常常采用均匀量化。以1 6 电平量化为例，其量化电平值j ( o i 1 5 ) 近似地反映了码元似然函数的值1 2j ，这就方便了工程实现。 加比选单元每次对输入的两个前状态的累加度量值和两个对应度量 距离进行加比选运算得到新的累加度量值，同时得到l 比特的幸存信息。 这个幸存信息就是所选择状态标号的最高位，其原理图如图2 6 所示， 其中q ；2 ”2 。这样对于每接收一组软判决信息就能得到2 ”1 比特幸存信 息( 一个状态1 比特) 。 累加度量r a m 和幸存信息r a m 分别用来存储累加度量值和幸存信 息。控制单元负责控制整个译码器的工作。下面详细讨论回溯判决单元 如何用“回溯”法得到译码信息。 图2 5v i t e r b i 译码器的原理图 图2 6 状态转移图及加比选运算 前面的算法所说的得到译码信息的方法实际上是“寄存器传递法” x b j 哈尔滨工程大学硕士学位论文 它的实质是给每个状态分配一定长度的寄存器用来存储幸存信息。对于 每个状态，a c s 时把得到的l 比特的幸存信息和前一时刻的留存状态的 幸存信息进行移位拼接运算得到该状态新的幸存信息。这种办法虽然容 易理解，但实现起来相当复杂，旦要求高速译码其硬件开销大得惊人， 因而在实际应用中并不采用它，而是采用另一种所谓的“回溯”的办法 来实现。 回溯的实质可以这样描述：对于( 2 ，1 ，3 ) 卷积码如果t 时刻编码 寄存器的状态为$ 2 = 0 1 ，则t - 2 时刻输入的信息必然是l 。译码的时候 随着网格图往前进达到一定的深度( 大于编码约束长度) ，如果知道此 时的最小状态( 最小度量值所对应的状态) 和此前的所有幸存信息，就 能往前“回溯”推得以前的所有信息。 对于图2 4 的接收过程，其译码信息完全可以由回溯法得到，如图 2 7 所示。其中每一列的四个比特信息代表每个状态做加比选时所得到 的幸存信息比特，随着网格图往前推进达到回溯深度t b l 后开始回溯， 这样对译码器的性能的影响微乎其微【7 1 。受篇幅所限图中没有画出更长 的网格图。回溯开始后最小状态为s o = 0 0 ，从相应的四比特1 0 0 0 选出对 应的比特l ，然后把0 0 左移一位把选出的1 补在后面得到新状态s 2 = o l 称之为状态更新。再用$ 2 = 0 1 去选择前一组四比特0 0 1 0 得到l 。如此循 环下去，可以得到最后的译码信息为( 0 0 1 0 1 1 1 ) ，其中最开始的的两 比特0 0 是编码器的最初状态，后面的1 0 1 1 1 和原始