（计算机科学与技术专业论文）viterbi译码器vlsi设计关键技术的研究与实现.pdf

国防科学技术大学研究生院学位论文 摘要 卷积编码和v i t e r b i 译码是一种有效的前向纠错方法，广泛应用于数字通信领域，能较 大地提高信息传输的有效性和可靠性。本文深入研究了v i t e r b i 译码算法以及各种改进算 法，详细介绍了v i t e r b i 译码器v l s i 实现的关键技术及其性能特点。我们发现，当前大约 束长度的v i t e r b i 译码器的v l s i 实现中存在着设计参数和技术难以选择、所需存储空间和 译码延迟较大等问题。 基于此，我们首先设计了一个高度可配置的软件模拟器。对卷积编码、通信信道和 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 译码器的设计 过程中使用特殊算法对“加比选”单元进行了优化设计。通过对现有回溯算法的分析和回 溯过程的统计，我们提出了基于前向回溯算法的概率回溯算法，从而在减小回溯部件所需 存储空间的同时降低了译码器的译码延迟。 本文使用选定的参数、优化的“加比选”单元、提出的概率回溯算法实现了一个适用 于d r m 系统的( 4 ，1 ，6 ) v i t e r b i 译码器。最后还给出了该译码器的设计过程、模拟测试过程以 及性能评测。 关键词：( 概率) 回溯：v i t e r b ；v l s i 实现；v l t e r b i 软件模拟器；卷积编码；收缩卷积 码 a b s t r a c t c o n v o l u t i o n a lc o d ea n dv i t e r b ia l g o r i t h mi se x t e n s i v e l yu s e di nd i g i t a l e o m m u n i c a t i o na sa ne f f e c t i v ew a yo ff o r w a r dc o r r e c t i n g ，w h i c hc a nc o n s u m e d l y e n h a n c et h ev a l i d i t ya n dr e l i a b i l i t yo ft h ei n f o r m a t i o nt r a n s m i s s i o n i nt h i sp a p e r ， t h ev i t e r b ia l g o r i t h ma sw e l la si t sv a r i o u si m p r o v e m e n t si sp e n e t r a t e dw i t h ，a n d t h ek e yt e c h n o l o g i e st o g e t h e rw i t ht h ep e r f o r m a n c ec h a r a c t e ro fv i t e r b id e c o d e r s v l s ii m p l e m e n t a t i o na r ei n t r o d u c e d w ef i n dt h a tt h e r ea r es o m ed i f f i c u l t i e si n s e l e c t i n gd e s i g n i n gp a r a m e t e r sa n dt e c h n o l o g i e s ，d e d u c i n st h en e e d e dm e m o r ys p a c e a n dd e c o d i n gl a t e n c yi nt h ev i t e r b id e c o d e ru s i n gb i gc o n s t r a i n tl e n g t h i nt h i sp a p e r ，as o f t w a r es i m u l a t o rw h i c hc a nb eh i g h l yc o n f i g u r e di sd e s i g n e d t h ep r o c e s so fc o n v o l u t i o n a le n c o d i n g ，c o m m u n i c a t i n gc h a n n e la n dv it e r b id e c o d i n g w i l1b es i m u l a t e db yt h es o f t w a r es i m u l a t o r b yc o m p a r i n gt h ep e r f o r m a n c eo ft h e d e c o d e rw i t hd i f f e r e n tp a r a m e t e r sa n di m p l e m e n t i n gm e t h o d s ，w eo p t i m i z et h e s e l e c t i o no ft h e m i na d d i t i o n ，r o o t e di nf u r t h e rr e s e a r c hi nv i t e r b ia l g o r i t h ma n ds o m er e l a t e d t e c h n o l o g i e s w eo p t i m i z et h ed e s i g no f “a d d c o m p a r e s e l e c t ”u n i t as p e c i a l a l g o r i t h mn a m e d “p r o b a b i l i t yt r a c eb a c k ”i sd e v e l o p e db a s e do no u rr e s e a r c ho f t h ee x i s t e dt r a c eb a c ka l g o r i t h m sa n ds o m es t a t b yu s i n gi t ，t h ed e c o d i n gl a t e n c y a sw e l la st h em e m o r ys p a c ei nt h et r a c eb a c kc o m p o n e n ti sr e d u c e d t h i s p a p e ri m p l e m e n t sav i t e r b i d e c o d e rb yu s i n gt h es e l e c t e dp a r a m e t e r s ， o p t i m i z e d “a d d c o m d a r e s e l e c t ”u n i ta n dt h e “p r o b a b i l i t y t r a c eb a c k ” a l g o r i t h mw h i c hc a nb eu s e di nt h ed r m ( d i g i t a lr a d i o m o n d i a l e ) s y s t e m t h ep r o c e s so f i t sd e s i g n i n ga n dp e r f o r m a n c ee v a l u a t i n gi sg i v e ni nt h ee n d k e yw o r d s ：( p r o b a b i l i t y ) t r a c eb a c k , v i t e r b i ，v l s ii m p l e m e n t i n g ，s o f t w a r es i m u l a t i o no f v i t e r b id e c o d e r ，c o n v o l u t i o n a le n c o d i n g , p u n c t u r e dc o n v o l u t i e n a lc o d e 国防科学技术大学研究生院学位论文 图目录 图1 i 数字通信系统模型， 图l2d r m 系统结构 圈2l 一般卷积编码器结构 图2 ，2 ( 2 ，l ，2 ) 卷积编码器。 图2 3 ( 2 ，l ，2 ) 卷积码编码网格图 图2 4 ( 2 ，1 2 ) 卷积码编码过程。 图2 5 ( 2 ，1 ，2 ) 译码网格图 图2 6 寄存器交换法， 图2 73 指针偶算法的幸存路径更新， 图2 ，83 指针奇算法的幸存路径更新 图2 ，9 单指针算法的幸存路径更新 图2 1 0 偶混合算法的幸存路径更新， 图2 n3 指针前向回溯单端口存储器算法 图2 ，1 23 指针前向回溯双端口存储器算法 图21 3 蝶形计算部件， 图2 ，1 4 格子图分解过程 图2 ，1 5 串行“加比选”部件结构， 图3 1 v i t e r b i 译码器系统结构， 图32 数据处理流程， 图3 3 分支计算部件，。， 圈34“加比选”单元 图3 5 回稠部件结构， 图4 i 软件模拟器 ， 图42 译码器模块结构 图43 接收信号电压分布 。， 图44 噪音模拟程序 ， 訇4 5 莳向巴j 溯树型发散， 0 0 6 ， 0 加 地 m m 场 埔 h 抑 趴 盟 踮 拍 盯约 暑墨 国防科学技术大学研究生院学位论文 图46 概率回溯测试 圈47 概率阿溯误码统计 ， 图4 83 指针概率回溯算法， 图4 9 概率回溯结构 图4 1 0 三位量化输入输出关系 图41 1 v i t e r b i 译码器模拟性能 图5l 基于标准单元库的译码器设计流程 图5 2v i t e r b i 译码器i p 核的功能模块划分 图5 3 模块v i l ，j i u 与a h b 总线接口 图5 4v i t j i u 内模块问的信号简图 图5 5v t e r b i 译码器配置信息数据通路， 图5 6v i t e r b i 译码器译码数据通路 图5 7 信号解压缩， 图5 8 分支代价产生 图5 9“加比选”部件波形 图5 1 0 回溯部件波形 图5 儿所实现的译码器r | 生能 昭 明 虬 蛆 蛎 盯 的 眈 跎 弭 肼 跖 弱 卵 国防科学技术大学研究生院学位论文 表目录 表2 1 表22 表2 ，3 表2 4 表2 5 表3 1 表3 2 袁41 表4 2 表4 3 表5 1 表52 表5 3 表5 4 表5 5 表56 表5 7 模2 加法操作 ( 2 ，1 2 ) 卷积编码状态转换表 ( 2 ，1 ，2 ) 卷积编码输出信号表 各种回溯方法所需存储容量和延迟比较 r a d i x 一2 。速度复杂性比较 译码器实现参数 收缩模式 测试环境 各种回溯方法所需存储容量和延迟比较 测试环境变量 v i t e r b i 译码器i p 核的v e r i o g 描述 解压缩以及理论结果， 分支代价产生以及理论分支代价 “加比选”单元理论计算结果 译码器实现技术 三种v i t e r b i 译码器比较 回溯方法比较 6 ， ， 坩 虬 弘 蹰 盯 蛇 舛 肌 跖 f ； 骗 盯 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：! i ! ! ! i 叠璺墨! 竖! 遮盐羞毽拄盔鲍盈窒当塞趣 学位论文作者签名： 奎亟星日期：洳年，月。7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目 学位论文作者 作者指导教师 国防科学技术大学研究生院学位论文 第一章绪论 随着现代数字通信技术的迅猛发展，人们对信息传输的可靠性和有效性的要求也越来 越高。纠错码是提高信息传输可靠性的一种重要手段。卷积码作为一种有效的信道编码方 式已经得到广泛的应用，它与v i t e r b i 译码算法共同实现了前向纠错，从而改进了在多噪声 及衰落信道下译码的准确性，增强了数字通信系统的性能。 1 1 课题背景 现代数字通信、广播技术在发展的同时，也使得相关通信技术的研究成为通信领域的 研究热点。现代通信的强大魅力就在于它能为人们提供的灵活、机动、赢效的通信交流方 式，因而非常适合信息社会发展的需要。尤其是近几年来，随着数字调幅广播( d r m ) 、第 三代移动通信系统( 3 g ) 、数字电视( o r b ) 等一批与人们生活息息相关的数字系统的渐行 渐近，各国政府和开发商都为之投入了大量的人力物力。 但同时，这也使得现代数字通信系统的研究、开发和实现变得更复杂、更困难。实际 上，由于数字通信信道的恶劣和难以预测性，并且无线电波的传输不仅会随着传播距离的 增加而造成能量损耗，而且由于多径效应、多普勒频移和阴影效应等的影响，信号会快速 衰落，码间干扰和信号失真严重，因而通信质量受到了极大的影响。 为了解决这些问题，人们不断地研究和寻找着多种先进的通信技术以提高移动通信的 性能。特别是数字移动通信系统出现后，它促进了各种数字信号处理技术如多址技术、调 制技术、纠错编码、分集技术、智能天线等的发展。其中，纠错编码的应用成为数字通信 系统的一大优点。纠错编码主要有三种类型：前向纠错( f e c ) 、检错重发( a r q ) 和混合 纠错( h e c ) 。后两种类型的纠错编码用于双向通信系统中，而f e c 则应用于数字调幅广 播、软件无线电广播、第三代移动通信系统和数字电视等领域。 其中，信道编码技术被大量使用来纠正电波在信道传输中所产生的误码，而卷积码则 是当今通信领域、数字广播、磁盘容错和语音识别等领域中最常采用的信道编码方法。图 1 1 为数字通信系统的简单模型，图中标识出了信道编码、信道译码在数字通信系统中的 位置。 图1 1 数字通信系统模型 第1 页 国防科学技术大学研究生院学位论文 当今频率在3 0 m h z 以下的广播基本上使用模拟技术、广播质量不高，在长距离广播 中容易受到干扰。正因为模拟信号广播中存在上述的诸多缺点，数字调幅广播d r m ( d i g i t a l r a d i om o n d i a l e ) 协会于1 9 9 8 年成立。d r m 协会意在推广数字调幅广播系统在全球的应用。 d r m 系统如图1 2 所示，数字调幅广播系统是本文研究的应用环境。 数字调幅广播和模拟信号广播相比有如下特点： 衰减信道上的强纠错。在模拟调幅中，任何干扰如多径衰减、噪声和相邻信道干 扰都会影响信号的传输质量，而一个经过仔细设计的数字系统能更好地抑制这些 干扰； 较好的声音质量； 能传送与服务业务相关的数据； 在发射端能量的节约，在覆盖相同服务区域的情况下降低功率； 在任何可以相比的系统中有最高的频谱效率2 4 b i t h z ： 可以传输数据业务： 可以与模拟信号传送兼容： 可以充分利用现有中短波频谱资源。 正是因为d r m 系统的这些优点，数字调幅技术才逐渐的发展起来，它也是调幅广播 改变现状的唯一出路。 d r m 流程 a m： 。r 。m 调制 ： 纠错编码 ： a m o f d m 解调：纠错解码 图1 2d r m 系统结构 1 2 课题研究内容 本课题的目标为，根据d r m 协议标准以及d r m 组织提供的软件接收机，实现个 基于自主设计的通用微处理器芯片、具有较高性能的软硬件协同工作的d r m 接收机。我 们的工作将按照以下几个步骤进行： 深入分析了解d r m 协议，这是我们进一步工作的基础； 分析d r m 软件接收机。结合对d r m 协议的理解，分析软件接收机各个模块的功 能、模块接口的定义、数据结构的定义、整体结构和实现方法： 对d r m 接收系统进行测试。根据d r m 软件接收机和d r m 组织提供的i 受【试数据 第2 页 国防科学技术大学研究生院学位论文 进行测试，统计接收机各个功能模块的在整个接收过程中所消耗的处理机时间， 计算相对比重得到需要进行优化的功能模块和特殊运算； 确定d r m 接收系统的实现结构。首先确定需要优化的功能模块、特殊运算进行 硬件加速：然后对整个系统进行结构设计： 对需要硬件加速部分进行硬件设计与实现。根据算法和d r m 协议要求对需要加 速部分进行设计与实现，最后编写相应的驱动程序： 对使用c 语言实现的d r m 软件接收机进行代码移植。由于我们所要实现的接收 系统是基于自主设计的通用微处理器芯片，需要将代码进行移植； 对d r m 接收机迸行测试。在完成上述的工作之后便需要整合d r m 软硬件系统进 行功能和性能测试。 最后将测试通过接收系统进行生产。 1 3 本文主要工作 本文的主要工作是对数字调幅广播d r m a 】系统中的信道编码以及v i t e r b i 译码方法进 行分析与v l s i 实现。我所完成的主要工作将集中在以下几个方面： 对卷积编码和v i t e r b i 译码算法进行研究，总结对v i t e r b i 译码算法进行v l s i 设计 与实现的要求。主要基于算法本身的特性以及v l s i 设计的特性来展开分析。 优化v i t e r b i 译码器的v l s i 实现。这部分工作主要从译码器实现的系统结构、参 数配置以及实现技术等方面进行思考。首先，根据d r m 系统中对v i t c r b i 译码器 的性能要求和各种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 译码器的v l s i 实现进行模拟 测试和综合主要有以下几个目的和意义： 1 ) 验证v i t e r b i 译码器功能的正确性： 2 ) 验证我们在v i t e r b i 译码器的v l s i 实现中对结构、相关参数和技术的优化 选择的正确性： 3 ) 对译码器实现给出一个客观的评价。 本文着重从以上几点出发，对v i t e r b i 译码算法以及相关技术进行研究，对译码器进行 v l s i 设计与实现、模拟测试和逻辑综合。 第3 页 国防科学技术大学研究生院学位论文 1 4 本文结构 第一章，绪论。介绍当今通信技术的发展和通信基本模型，指出信道编码和译码在通 信系统中所占的重要位置；对我们实现的v i t e r b i 译码器的具体应用环境d r m 系统进行简 单说明；介绍本课题和本文中的主要工作和目标；阐明课题任务和工作，构建全文结构。 第二章，v i t e r b i 译码算法及相关技术研究。详细介绍v i t e r b i 译码算法和改进的译码算 法；对当今的回溯技术和“加比选”单元设计方法进行深入分析：研究当前的几种译码器 的系统结构。 第三章，v i t e r b i 译码器系统结构。给出了v i l e r b i 译码器体系结构的i p 核，并对其中 各个功能模块及其结构进行详细说明。 第四章，译码器设计与实现的关键技术。详细介绍本文中使用到的几个关键技术，包 括回溯技术和参数的选择，提出概率回溯算法。设计软件模拟器，并使用该模拟器对所选 参数对译码器性能的影响进行测试。 第五章，v i t e r b i 译码器的v l s i 实现及其评测。按照v l s i 的一般设计流程，阐述v i t e r b i 译码器的设计过程，随之对译码器进行功能模拟和验证。 第六章，结束语。对课题研究中取得的成绩以及不足进行客观的评价，对下一步的工 作进行展望。 国防科学技术大学研究生院学位论文 第二章 v it e r bi 译码算法及技术 卷积编码以及v i t e r b i 译码算法已经被广泛应用于各个领域。v i t e r b i 译码算法、译码器 系统结构设计以及译码器中功能模块的优化设计都有了很大的发展。本章将就当今v i t e r b i 译码的相关研究进行详细介绍。 2 1v i t e r b i 译码算法 卷积码是一种重要的实现差错控制的信道编码，其译码方式有三种：v i t e r b i 译码 2 1 、 序列译码和门限译码。其中，v i t e r b i 译码算法是最常用于卷积码的译码算法，它具有最佳 译码性能，但是其硬件实现复杂；门限译码性能最差，但硬件简单；序列译码在性能和硬 件复杂度方面介于v i t e r b i 译码和门限译码之间。 v i t e r b i 算法首先是由a n d r e w v i t e r b i 于1 9 6 7 年提出来的。该算法是一种极大似然序列 估计算法m l s e ( m a x i m u m l i k e l i h o o ds e q u e n c ee s t i m a t i o n ) ，其复杂度为o ( 2 x 一1 ) ( k 为卷 积码的约束长度) 。1 9 6 9 年，o m u r a 3 1 通过使用权重图将v i t e r b i 译码算法应用于动态可编 程技术来得到最短路径。之后，f o m e y 证明了v i t e r b i 译码算法是卷积码的最大似然译码算 法吼 2 1 1 卷积码编码方法 卷积码【4 】是一种对付突发错误的有效编码方法，通常记作( n ，k ，m ) 。它将k 比特信息编 码为n 比特数据，编码效率为r = k n 。k = m + l 为约束长度。编码后的卷积码中的n 个码 元不但与当前段的k 个输入信息有关，而且与前面m 段的信息有关，即连续的k 段输入 信息相互约束，编码输出的( r n + 1 ) n 个码元是相互关联的。其纠错能力随着k 的增加而增 强，而差错率随着k 的增加而指数下降。卷积编码器的结构如图2 1 所示。 l2 k 厂“、“v 、_ 九、 l2 k12 k12 k12 k 123 n 图2 1 一般卷积编码器结构 第5 页 一一旦堕型兰垫查查兰翌窒竺堕兰堡兰茎 ： = = = = = = ：= = = = = = = = = = ：= = = = = = = = = = = = = = = = = = = = = = ：= = = = = = = = = = = 一一 由图2 1 可知，卷积编码器包括两部分：一个由k 段组成的输入移位寄存器，每段有 k 位，总共( m ) k 位；n 个模2 和操作，其操作如表2 1 所示，图2 1 中n 个模2 和操作 的输入对应于编码器的n 个生成多项式，如公式2 1 所示。每输入k 比特数据，编码器输 出n 比特码元。 表2 1 模2 加法操作 输入a输入b输出( a 。b ) 0oo 011 l0l 1l0 一个( 2 ，1 ，2 ) 卷积编码器有1 个输入端z ，2 个输出端k 。誓。和2 级的移位寄存器。通 常将当前的输入数据直接用于运算产生输出序列，减少一级的移位寄存器。( 2 ，1 ，2 ) 卷积编 码器如图2 2 所示，编码效率r = 1 2 ，约束长度k = 3 。编码器对每位输入产生两位输 出y o 。和誓一其产生多项式为 f ，= 五e x , 一，o 五一： 1 _ 。= x 。工h 萝“每 q e = 2 e 电 卜一r 路 图2 2 ( 2 ，l ，2 ) 卷积编码器 公式2 1 我们可以从另一个更简单的角度来理解卷积编码问题，将编码器看成一个状态机，使 用移位寄存器的值来标识编码器的状态，这样对于上述的( 2 ，1 ，2 ) 的卷积编码器就有四个状 态。假设此处的移位寄存器进行右移操作，编码器的移位寄存器初始值为全0 状态。若输 入为数据为0 ，下一个状态仍为全0 ，否则编码器在下一个时钟沿变为1 0 ：。表2 2 给出了 编码器在不同输入数掘时，从当前状态到下一状态的转抉关系。 表2 2 称为状态转换表，同样，在当前输入数据和当| j 状态下，编码器输出数据如表 2 3 所示称为编码输 b 信号表。 国防科学技术大学研究生院学位论文 很明显表2 2 和表2 3 已经可以完全表示一个( 2 ，1 ，2 ) 卷积编码器的编码行为。 可知编码器总共2 一个状态，即表中有2 k - t 行、2 “列，其中k 为约束长度，k 为每个时 钟周期编码器的输入位数。 表2 2 ( 2 ，l ，2 ) 卷积编码状态转换表 下一状态 当前状态输入o ：输入l ： 0 00 0l o 0 l0 01 0 1 00 1 1 1 1 10 11 1 注：表中状态使用二进制表示 表2 3 ( 2 ，1 ，2 ) 卷积编码输出信号表 输出信号 当前状态输入0 ：输入l ： 0 00 01 1 0 11 10 0 1 0l o0 l l l0 11 0 通常使甩网格图表示卷积编码过程。图2 3 为上节中( 2 ，1 ，2 ) 孝积编码器的网格图d 下 图用于输入1 5 个数据的编码。 时序t 状态0 0 状态0 1 状态1 0 状态1 l 图2 3( 2 ，l ，2 ) 卷积码编码网格图 网格图中使用纵向的四个点来描述编码器可能的四个状态，对应于卷积编码的两个袁 中的状态。水平方向为时间轴，每一歹1 j 代表该时刻输入的数据。初始状态为全o 状态，其 中实线表示输入数据为l 的状态转换方向，虚线表示输入数据为0 的状念转换方向。对应 于上述【2 ，1 ，2 ) 卷积编码器，若输入序列x = 0 1 0 1 1 1 0 0 1 0 1 0 0 0 1 ，则对应的编码后的输出序 歹t jy = 0 0 h o o o 叭o 叭! ! ! ! ! ! ! ! ! ! ! ! 竺! ! ! ：一兰璺堡里竺璺! 兰垦量：竺堂! 型：望兰 而i 一一 “ 。 。 国防科学技术大学研究生院学位论文 织是按两个一组排列的，每组的第一个为码元为编码器的第一个模2 加法器的运算结果， 第二个码元为第二个模2 加法器运算结果。并且其输出的码值和状态转换关系对应于上述 的卷积编码输出信号表和卷积编码状态转换表。 时序t 状态0 0 状态0 l 状态1 0 状态l l 输a - - 0 1 o1 1 1oolo1o o o 1oo 输出0 0 “i o0 00 il oo li t ll l1 0o o 1 01 10 01 l1 01 1 图2 4 ( 2 ，1 ，2 ) 卷积码编码过程 从上面码率r = 1 2 、约束长度k = 3 的卷积编码过程中，我们可以看到，每一位( 组) 数据的输入都会对连续的三组输出信号产生影响。这也就是卷积码具备纠错能力的原因。 2 1 2 收缩( p u n c t u r e d ) 卷积编玛 卷积码具有较好的纠错能力，并且适合采用计算机搜索方法进行译码，但是也存在一 定的缺点： 卷积码的纠错能力除了受限于约束长发k ，另一个对其纠错能力影响很大的参数 就是编码效率r 。若码率较小表示编码结果中的冗余信息较多，则其纠错能力较 强，但是在信道带宽固定的情况下其可传输的有效信息也就比较少。若码率较大 的话又可能影响卷积码在数字通信中的纠错能力。 由于一个译码器的实现结构是和相应的卷积码结构相互对应的，所以，一个确定 实现的v i t e r b i 译码器的使用范围受到限制，不能很好的重用。因而收缩卷积码被 提出并被广泛使用。收缩卷积码是通过对普通卷积码进行特殊位的删除得到的一 种与原卷积码有相同结构特征的特殊卷积码。 d r m 协议【l l 中使用收缩卷积码6 j 进行信道编码，对于不同保护级别的数据采用不同 码率的卷积码进行信道编码，从而实现了在保证数据传输质量的同时充分利用了通信信道 的带宽。 收缩卷积码的编码器实现结构简单，只需在相应卷积码( 称为母码) 编码器的输出端加 上收缩电路即可完成收缩卷积码编码，收缩卷积编码器实现结构如图2 2 所示。收缩电路 将要根据不同的收缩模式周期性的删除码元，这样就得到了与母码有着不同码率却又有着 相同结构的收缩卷积码。正是由于不同码率的收缩卷积码来自相同的母码，有着相同的结 构和祷往，所以v i t e r b i 译码器可以在不改变结构的情况下，实现对多码率的收缩卷积码进 第8 页 国防科学技术大学研究生院学位论文 行译码的目的。 类似的，对于收缩卷积码也可以使用状态转换表和格子图完成编码，由于实现简单就 不再一一赘述。 2 1 3v i t e r b i 译码算法 若卷积编码器对长度为l e n 的序列s 进行编码得到序列t ，经过信道干扰，译码器接 收到的序列r = t + e ，e 为信道误码。v i t e r b i 译码就是根据r ，按最大似然规则找到编码 器所经过的状态序列。也就是计算最大似然函数4 够州l o p ( r 1 巧) ) 公式2 2 其中l o g a 为路径代价函数，p 为概率函数，r 为接收序列，r 为卷积编码器可能的发送序 列， 1 2 ，2 帆8 ”) 。 文献4 1 中证明了对于二进制输入e 进制输出的离散无记忆信道d m c 而言，计算最大 似然路径等价于计算与r 有最小汉明距离的路径，即 d ( r 1 ) d ( r i 一)公式2 3 其中，d 表示汉明距离函数，r 为接收序歹4 ，t r 为译码序列，为编码嚣任何可能的发送 序列， 1 , 2 ，2 ”“”) ，l e n 为序列长度，发送序列和接收序列都用q 迸制表示。即对于 某个状态序列s ，若它在公式2 2 有最大值，那么它也会在公式2 3 中有最小值。 因此，v i t e r b i 译码过程就是根据接收序列r 。从所有的可能的发送序列中搜索具有最 大概率的发送序列的过程。 由上面介绍的卷积编码过程可知，v i t e r b i 译码的每个候选发送序列对应网格图中的一 个状态序列。下面使用网格图介绍( 2 ，l ，2 ) 卷积码的v i t e r n 译码过程。 一个约束长度k = 3 的卷积码的v i t e r b i 译码网格图共有4 个状态节点。图中的每个分 支都被赋予一定的权重，也就是分支代价b m ，根据上述译码原理。权重应为咒和r 中对 应信号段的汉明距离，它是对接收序列与发送序列的相似程度和噪音干扰程度的一种度 量。因此二者越是相似，它们的汉明距离也越小。最后得到的有最小汉明距离的路径就是 对发送序列t 的最大似然估计序列l 。 v i t e r b i 算法首先搜索与r 有最小汉明距离的路径，其过程如下： 1 ) 在7 = f 时刻，对进入每个状态节点的2 条长度为 的部分路径，计算部分路 径代价。对4 个状态的每个状态挑选并存储有最小代价的部分路径和部分路 第9 页 国防科学技术大学研究生院学位论文 径代价，称作幸存路径。上述路径代价计算更新过程简称为“加比选”操作， 可以形式化表示为： m 川= m i n b m u + m 叫一i ，b m 。+ 孔，+ m ，+ 强卜【 公式2 4 其中：m 。为t 时刻到达i 状态的部分路径的路径代价，即沿着部分路径的 分支代价累加和；b m 。为从状态i 到状态j 分支代价，i ：