（通信与信息系统专业论文）可配置的viterbi译码器的fpga实现.pdf

摘要 卷积码作为一类重要的前向纠错码，同具有最大似然译码特性的v i t e r b i 译码 算法，广泛应用于各种数字通信系统。随着通信技术的持续发展，产生了许多新 技术和新标准。不羼的通信标准采用不同的卷积码，以往固定参数的v i t e r b i 译码 核已不能满足应用的需要。兼容不同通信标准，支持参数动态配置的v i t e r b i 译码 核的设计与实现，具有重要的研究价值。 本文以w i m a x 、l t e 和u m b 无线接入标准为背景，在分析了v i t e r b i 译码算 法的基础上，综合考虑资源使用和数据速率，给出了兼容三种标准、参数动态可 配置的v i t e r b i 译码核的f p g a 设计。可配置的参数包括协议类型、回溯深度以及 回溯的初始状态。这些参数与相应的输入数据同时送入译码器，在动态可配置情 况下完成可靠译码。创新的数据流控制机制提供了大流量数据的可靠译码。译码 器中合理使用的流水线结构保证了高速的数据速率。验证结果表明，译码功能正 常可靠，可配置性良好。w i m a x 配置情况下数据速率为1 0 0 m b p s ，l t e 和u m b 配置情况下数据速率为4 m b p s 。资源使用与相同配置的a l t e r a 译码核相当。 关键词：卷积码v i t e r b i 译码核动态可配置流水线 a b s t r a c t a sac l a s so fi m p o r t a n tf o r w a r de r r o rc o r r e c t i n gc o d e s ，t h ec o n v o l u t i o n a lc o d e i s a d o p t e de x t e n s i v e l yi nv a r i o u sc o m m u n i c a t i o nt e c h n i q u e sa n ds t a n d a r d s ( e g w i ， l t ea n du m s ) ，i nc o n j u n c t i o nw i t ht h em a x i m u m l i k e l i h o o dp e r f o r m a n c e # a c h i e v e d v i t e r b id e c o d i n ga l g o r i t h m 。i np a r t i c u l a r l y , t h ep a r a m e t e r so fc o n v o l u t i o n a lc o d e sa r e u s u a l l vd i 珏打e n ti nv a r i o u ss t a n d a r d s n o t et h a tt h ec o n v e n t i o n a lf i x e dv i t e r b id e c o d i n g c o r ei so n l yd e s i g n e d f o rs o m ef i x e dp a r a m e t e r s a n ds u i t a b l ef o rac 瞰a m e o l 翻嗽t l 越e a o 鞋s 锨d a 聪。t h e r e f o r e ，i ti si m p o r t a n ta n di n t e r e s t i n gt od e s i g na f l e x i b l e v i t e r b id e c o d i n gc o r ew h i c hi sc o m p a t i b l ew i t hv a r i o u ss t a n d a r d s ，e s p e c i a l l yf o r s u p p o r t i n gi n t e g r a t e ds e r v i c e s 孙髓st h e s i s ，w i t ht h ea p p l i c a t i o no ft h ec o n v o l u t i o n a lc o d em w i r e l e s sa c c e s s s t 鼢d 棚s ( e 。g ，w i m a x ，l t ea n dt y m b ) a n d t h ef u l lc o n s i d e r a t i o no f t r a d e 。o 纾b e 淅e e i l r e s o u c eu t i l i z a t i o na n dd a t ar a t e ，t h ed e s i g no fav i t e r b ic o r ei si n v e s t i g a t e db a s e d o n 也ea n a l y s i so ft h ev i t e r b ia l g o r i t h m ，w h i c hs u p p o r t st h e t h r e ew i r e l e s sa c c e s ss t 8 规a r d s a n dd y n a m i cp a r a m e t e r i z a t i o n t h ec o r t f i g u r a b l ep a r a m e t e r s i n c l u d es t a n d a r d 鲫e ， 衄c e - b a c kl e n g t ha n dt h ei n i t i a ls t a t ef o r t r a c e b a c k t h e s ep a r a m e t e r se n t e rt h ed e c o d c r , t o g e t h e rw i t ht h ec o r r e s p o n d i n gr e c e i v e dd a t a , a n dt h e nt h ed e c o d i n gc a nb e p c r f 0 1 m e d r e l i a b l y 豫d 嚣t h e c o n d i t i o no fd y n a m i cc o n f i g u r a t i o n t h e n o v e ld a t ac o n t r o l m e c h a 赫s mi si n 加d u c e di nt h ed e c o d e ra r c h i t e c t u r ef o rt h ep u r p o s eo ft h er e l i a b l e d e c o c l i n gf o rm a s s i v ed a t af l o w t h ep i p e l i n ea r c h i t e c t u r e ，w h i c h i sp r o p e r l yu s e dl nt h e w h o kd e c o d e 毛i m p r o v e sh i g hd a t ar a t eo b v i o u s l y i ti sv e r i f i e dt h a tt h e c o r r e c ta n d r e l i a b l 。d e c o d i n g ，a l o n gw i t ht h ec o n f i g u r a b i l i t yw o r k s w e l l d a t ar a t eo fl o o m b p sf o r w i m a xa n d4 m b p sf o rl t eo ru m bc a nb ea c h i e v e d r e s o u r c e u t i l i z a t i o ni s e q u i v a l e n tt ot h a to f a l t e r a c o r ew i t ht h es a m ep a r a m e t e r s k e y w o r d s ：c o n v o l u t i o n a lc o d e v i t r b ic o r e d y n a m i cc o n f i g u r a t i o n p i p e l i n e 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导 师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注 和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果； 也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：日期! ? ：兰! 多 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：主墨耋 导师签名：圭互么 日期， 日期j 雌 第一章绪论 第一章绪论 本章首先概述了作为课题背景的几种无线接入协议及特点，然后概述了v i t e r b i 译码器的发展现状和课题研究的意义。最后给出了本文的主要工作和后续章节的 行文安排。 1 1 课题研究的背景 在信息技术持续发展的环境下，用户自身的需求和新业务的相互推动，使得 市场的需求发生了变化：一方面，家庭或办公室等固定环境中的宽带业务已不能 满足传统的固定接入用户的需要，他们希望提供移动的宽带接入服务；另一方面， 传统的移动用户也不满足于简单的语音、短信等低速数据业务，希望使用更高数 据速率的多媒体业务。市场需求的变化促进了固定宽带服务和移动服务在技术上 和业务上的融合，并互相补充和促进。这就要求新的通信网络宽带化，而它的移 动性正体现在接入网中接入技术的使用。众多电信设备制造商、运营商和电信组 织参与制订的无线接入技术标准主要有w i m a x ，l t e 和u m b 。 w i m a x 全称为w o r l di n t e r o p e r a b i l i t ym i c r o w a v ea c c e s s ，即全球微波接入互操 作性。它是一项无线城域网( w m a n ) 技术，是针对微波和毫米波频段提出的一种 新的空中接口标准。目前业界所指的w i m a x 技术实际上就是i e e e 8 0 2 1 6 技术。 w i 的技术特点为： ( 1 ) 覆盖范围大，接入速度高 w i m a x 采用o f d m 技术，能有效对抗多径干扰；同时采用自适应编码调制 技术可实现覆盖范围和传输速率的折衷；此外，还利用自适应功率控制，可根据 信道状况动态调整发射功率。 ( 2 ) 提供灵活、优良的“最后一公里 接入服务 作为一种无线城域网技术，它支持无线局域网接入，也可作为有线接入方式 的无线扩展。w i m a x 不仅支持固定无线终端，也支持便携式和移动终端，能适应 各种地形环境。 ( 3 ) 提供广泛的多媒体通信服务 w i m a x 可提供面向连接的、具有完善q o s 保障的电信级服务。 ( 4 ) 具有较高的安全性 l t e 的全称是l o n gt e r me v o l u t i o n ，即3 g 系统的长期演进。该技术是3 g p p 主导的3 g 技术的升级演进。目前，基于w c d m a 无线接入技术的3 g 移动通信技 术已经成熟。为了进一步发展3 g 技术，3 g p p 引入了h s d p a ( 高速下行分组接入) 和e d g e ( 全球演迸的增强数据速率) 的3 g 增强技术，但由于成本过高，难以推广 使用。 可配置的v i t e r b i 译码器的f p g a 实现 w i m a x 宽带无线接入技术的出现，高速的接入速率给3 g 的无线接入技术带 来了巨大的压力。3 g 接入技术虽然在支持移动性和q o s 方面有较大优势，但接入 的空中接口和网络结构过于复杂，而且在成本上处于劣势。按照3 g p p 组织原先的 时间表，4 g 最早要在2 0 1 5 年才正式商用。市场的挑战以及降低成本、提高性能 的需求等因素共同推动了3 g p p 组织在4 g 出现之前加速制定新的空中接口和无线 接入网络标准。2 0 0 4 年，根据众多运营商、制造商以及研究机构的要求，3 g p p 通 过了关于“e v o l v e du t r aa n du t r a n ”，即“l t e ( 3 g 无线接入网长期演进) ”的立 项工作，并确定了该项目的总体计划。 l t e 的需求和目标是： ( 1 ) 性能方面的一个主要目标是提高吞吐量和频谱效率。 ( 2 ) 在部署和演进方面：首先应支持灵活的带宽和频谱，其次应支持与3 g 系统的 共存与互通。 ( 3 ) 在无线资源管理方面，e u t r a n 应支持增强的q o s 控带i j 机制，提供优化的上 层业务、应用和协议到无线资源的映射和匹配。 u m b 全称为u l t r am o b i l eb r o a d b a n d ，即超移动宽带技术。它是3 g p p 2 组织 主导的，c d m a 2 0 0 0 系列标准的升级和演进版本。它基于t c p i p ，下一代无线系 统上的互联技术，并作为3 g p p 2 下一代标准中的空中接口规范。u m b 技术在经济 地提供低速、低时延的语音业务同时有效地提供高速、非时延敏感的宽带数据通 信业务。为支持无缝接入，u m b 系统还支持与现有的c d m a 2 0 0 0 系统间进行跨 系统的无缝切换。 l i m b 系统的优势： ( 1 ) 移动环境下高速数据传输 ( 2 ) 低时延 ( 3 ) 覆盖范围广，能提供无线漫游的广域覆盖 ( 4 ) 增强的基于p 的语音系统容量，不会降低并发数据业务的吞吐量 卷积码在编码过程中充分利用了码组之间的相关性，信息比特长度和对应的 码字长度都很小，可以串行和并行方式传输，传输时延小。在编码器复杂性相同 时，卷积码的性能优于分组码。此外，最佳和准最佳译码的实现也比较容易。基 于以上优点，卷积码作为一种有效的信道编码方案，是当今无线数字通信技术的 重要组成部分，在实际中广泛应用。w i m a x 、l t e 和u m b 宽带无线接入技术均 采用卷积码作为物理层信道编码的基本备选方案之一。v i t e r b i 算法作为一种概率 译码算法，由于自身的最大似然译码的性能特点，成为卷积码在加性高斯白噪声 ( a w g n ) 信道下的最优译码算法。当卷积码的编码约束度不太大( 1 0 ) ，或者误码 率性能要求不太高( 1 0 巧) 时，v i t e r b i 算法的效率高，速度快，延时固定，译码器 结构简单。适合于硬件实现。 第一章绪论 l 。2v i t e 两i 译码器设计的现状相发展 1 9 5 5 年，e l i a s 提出了与分组码不同的卷积码【4 】1 5 】【椰。随后在1 9 6 7 年，a j v i t e r b i 提出了卷积码的v i t e r b i 译码算法【7 1 【8 】【9 】f l o 】，这是基于编码网格图的最大似然译码算 法。在卷积码的代数译码核概率译码方法中，v i t e r b i 算法以其自身麴优势成为卷 积码的一种最佳的概率译码算法。 1 9 7 3 年，g d f o m e y 发表了关于v i t e r b i 译码算法的综述性文章 1 0 】，结合网格 图的概念，文中指出v i t e r b i 译码算法实质上是最大似然译码算法，并且指出编码 网格图在结构上与蝶形运算结构有相似性。这弓| 发了v i t e r b i 译码器的算法和实现 结构方面大量的研究【1 6 】。随着集成电路工艺的发展，译码器从最早的集成块发展 为专用的集成芯片。随之出现了提高译码速率的高速译码结构和算法，例如1 9 8 9 年，g 。f e t t w e i s 等人发表了如何打破加比选运算单元瓶颈的文章驻，文中提出通过 网格合并使得网格图变得更加紧凑，但是对于大约束度的卷积码，蠢于状态数的 指数增加，电路规模将变得很大。为了在不显著增加电路规模的前提下，提高加 比选单元的运算速度，研究集中在加比选单元结构的进步改进上。通过单元结 构的重薪组织，加入并行结构降低加比选运算的反馈结构带来的延时。 以上这些结构都是在不改变v i t e r b i 译码算法基础上，对编码网格图或者运算 结构重新组织得到的。1 9 9 3 年，s h u ik u b o t a 等提出了s s t ( s c a r es t a t et r a n s i t i o n ) 算法【砼l ，罄的强减少译码器的状态跳转。s s t 算法使得译码器输入序列大部分时 间都处在0 状态，减少了状态跳转以及圈溯时最大状态的搜索，减少了译码器的 功耗。类似的算法还有很多，但都是牺牲性能来换取功耗的降低。 总的来看，从六十年代詹期开始研制v i t e r b i 译码器，到现今芯片集成制造王 艺快速发展的时代，国外对v i t e r b i 译码器的大量研究蛊在进行。特裁是高度集 成的f p g a 技术的产生和成熟，极大推动了高性能译码器设计的不断发展。目前， 囡内外一直都在开展基于f p g a 的译码性能可靠，高数据速率，低功耗译码器的 设计稆实现，数据速率从几十k b p s 至a 委m b p s l l 3 疆1 谨1 5 】1 2 毒褡】，状态数从1 6 至2 5 6 ， 设计的重点主要放在译码器功能模块的改进和优化上【2 3 1 1 2 7 1 2 8 】f 2 9 】【3 0 1 。从应用的需求 和设计趋势来看，v i t e r b i 译码器发展的方向是高数据速率，灵活的可配置，可熏 用，可移植性。 同时，各f p g a 厂商如a l t e r a 、x i l i n x 都推出了v i t e r b i 译码核，将其作为系统 设计中常用的功能核，提供全面的译码配置。系统设计人员可以将所需的功能模 块例化，在充分了解例化模块的外部时序后，就可以和其它模块配合，专注系统 级功熊的设计。f p g a 厂商提供的译码核霹以实现编码约束度、生成多项式、软输 入位宽、删余模式、加比选单元的个数以及回溯深度等参数的可配置，但是这些 参数在译码过程中是不能变化的【3 3 】【3 4 】。 4 可配置的v i t e r b i 译码器的f p g a 实现 1 3 课题研究的意义 现在大多数研究只针对某种码型的卷积码进行局部模块的性能优化，而很少 将译码器作为一个整体进行功能和性能优化。虽然f p g a 厂商提供的译码核功能 全面，支持多种参数配置，但是参数一经配置就是固定的。如果译码器的使用需 求或环境发生变化，整个译码核需要重新配置编译，译码核使用的灵活性很差。 译码核在某些应用情况下会产生异常，由于使用者无法确知译码核的内部结构， 给问题的定位和解决带来了极大的困难，也不利于译码核功能的扩展和改进。 随着通信技术的发展，各种通信标准相继出台。不同的协议根据应用需要， 采用不同的最优卷积码，而且对译码的算法性能和速率要求不同。因此，结合本 文卷积码应甩的三种无线接入协议，以及应用的可配置和灵活性的考虑，基于 f p g a 设计和实现一个v i t e r b i 译码核，提供灵活的参数配置，在大流量数据环境 下进行可靠译码，译码性能和速率满足应用需求，同时使用的资源尽可能少，不论 从研究角度还是应用角度，都是非常必要的，并具有一定的参考价值。 1 4 本文的研究内容和章节安排 本文的研究内容是在a l t e r af p g a 上实现支持w i m a x 、l t e 和u m b 协议中 使用的卷积码的译码，对不同长度的输入数据流都能正确完成译码功能。结合可 配置、资源和译码速率的要求，设计中对v i t e r b i 译码算法和算法中关键部分的实 现结构作了优化。采用自顶向下的设计方法，使用q u a r t u s i l 7 1 和m o d e l s i m 作为 综合和仿真工具，完成译码器的设计实现和验证。译码器主要的性能特点是： ( 1 ) 数据流控制功能； ( 2 ) 各种长度的连续或不连续输入数据帧的可靠译码； ( 3 ) 协议类型、回溯深度、回溯起始状态信息实现动态可配置。经过编译并正常工 作的译码器，只需当前数据帧完全输入译码器后，就可以输入新的配置信息； ( 4 ) w i m a x 协议配置下，译码速率不低于10 0 m b p s ，l t e u m b 协议配置下，译 码速率不低于4 m b p s ； ( 5 ) 逻辑资源和存储资源不超过相同配置条件下，a l t e r a 译码核的资源使用量。工 作频率不低于1 3 3 m h z 。 本文的章节安排如下： 第一章简要介绍了现今使用的w i m a x 、l t e 和u m b 宽带无线接入技术及技 术特点，阐述了所选课题的国内外进展，接着论述了所选课题的意义、内容和论 文的行文安排。 第二章介绍了卷积码的一般原理，对卷积码的编码，v i t e r b i 译码原理作了简 要介绍。对编码过程中使用的尾比特编码技术专门做了介绍。 第一章绪论 第三章根据设计的资源和速率要求，使用经过算法性能分析的参数，论述了 设计方案中主要模块的设计和优化。 第四章进行了译码器的测试验证。验证过程中，首先使用应用于三种无线接 入协议的卷积编码和v i t e r b i 译码算法，在高斯白噪声环境下，建立了信源信息的 编码、传输和译码的完整软件仿真模型，得到译码模块的输入和译码输出，然后 使用同样的译码器输入信息，得到硬件译码器的译码输出。将得到的两组译码输 出结果比较完成译码器功能的验证。最后利用q u a r t u s l l 7 1 和m o d e l s i m 进行译码 器资源使用和译码速率的验证。 第五章对全文作了总结，指出译码器设计可以改进的方向。 第二章卷积码的编码和v it e r b i 译码 第二章卷积码的编码和v i t e r b i 译码 本章首先介绍了卷积码的编码和模型表示，概述了现行普遍采用的尾比特编 码技术；接着黉点阐述了基于最大似然方法的v it e r b i 译码算法。最后给出了本 文涉及的无线接入协议中的卷积编码方案。 2 1 卷积码的编码 2 1 1 卷积码的概念 卷积码的基本思想在于，把信源输擞的信息序列，以k 比特分成一段，逶过 编码器输出，l 比特码组铆的，利用信息冗余进行纠错。与分组码不同，卷积编码 具有记忆性。 将发送信患序舞送入编码器可得到卷积码。编码器巍一组线性移位寄存器组 成。对应于每段k 比特的输入序列，输出以比特码组。为编码约束度，说明编码 过程中相互约束的码段个数。以个码元不仅与当前的k 个信息比特有关，还与前面 的一l 谤个信息有关。n = m + l ，掰为编码存储，它表示输入信息组在编码器中存 储的单位时间。n a = n n 为编码约束长度，说明编码过程中相互约束的码元个数。拂 或、a 是表示编码器复杂性的重要参数。卷积码的纠错能力随着的增加而增 强，误码率随着的增加丽呈指数下降，但同时编译码器的结构变得很复杂。 卷积码豢溺积，墨磁) 或何mk u ) 表示，有时也矮( 箨，教柳表示。尹一k 嚣为卷积码 的码率，它是衡量卷积码信息传输有效性的一个重要参数。本文对卷积码采用( 以，如 朋的表示方法，并采用m 级的串行编码器结构，包含一组7 z 个模2 加法器，以及 一个嚣位的串势转换器。如图2 。董所示。擞表示输入的信息，一l 箨) 表示卷 积码元，e 为卷积码序列。 圈2 1 卷积码通用编码器 2 1 2 卷积码的表示 描述卷积码的方法有两类，解析表示和图解表示。 可配置的v i t e r b i 译码器的f p g a 实现 卷积码的解析表示主要有延时算子多项式和半无限矩阵嚣种形式，主要用于 代数译码。 以( 2 ，1 ，3 ) 卷积码为例说明，编码器的结构如图2 2 所示。 c 图2 2 ( 2 , 1 ，3 ) 卷积码编码器 将输入序列表示为时延算子d 的多项式掰) ，输入序列表示为 m ( d ) 一m o 锄l d + m 2 d 2 + 其中，m o ，m l ，m 2 为输入信息序列的二进制表示，时延算子d 的幂次表示 相对于第一个输入信息比特的单位时延数鹭。 将编码器中各级移位寄存器和每个模2 加法器的连接关系表示为时延算子的 多项式g ) ，时延算子d 的幂次表示寄存器的级数。若某级寄存器和模2 加相连， 则多项式中对应项系数为l 。g ( d ) 称菇卷积码的生成多项式矩阵，每个元素赘为子 生成元。可知，( 2 ，l ，3 ) 卷积码的子生成元为g 1 一l 十辨扩，g 2 ( d ) = l 桫，生成 多项式为g ( d ) = 1 十d + 扩，l ，也可用八进制数值表示为g = 7 ，5 。 那么编码序列c p ) 一嬲p ) g ( d ) ，得到串行输擞的码序列。 图解表示有树匿、嚼格匿和状态转移图三种，主要雳于概率译码。 卷积码的树图表示是一种很形象的表示卷积码编译码过程的方法，常用在序 列译码中。 状态转移图方法，可以动态表示编鹨器状态的变化帮对应的编码输出。形象 的表示了编码器的工作过程。对照卷积编码器，随着信息序狲的不断输入，寄存 器内的值发生着变化，寄存器组表示的状态是确定、有限的，并在不断地跳转。 网格图表示实际上可器作状态图表示在时间轴上的展开。它以状态为纵轴， 时间为横轴，形象表示了卷积码的状态转移随时闻的变化关系，摇述编译码更加 方便。v i t e r b i 译码正是基于网格图的。网格图上，个节点代表某个时刻的个 状态，节点闻的连线代表状态的转移，实线表示状态转移的输入为l ，虚线为0 。 转移路径上标注了当前状态和输入所决定的编码输粥。网格銎的表示如图2 3 ( 球 所示。为了使编码器的初始和结束状态一致，需要在信息序列结尾送入额外的r n 个零比特。那么开始和结束的 n 个时间段，编码器只能处于某些特定的状态。中 闻时闻段，从第n = m + l 时刻开始，网格图开始重复，并且完全相同。当输入信息 序列为( 1 0 1 l ) ，由图中的状态转移路径来看，输入信息序列和网格图上的转移路 径是一一对应的。 第二章卷积码的编码和v i t e r b i 译码 对一个0 ，毛加卷积码而言，一共有2 拥个状态，若输入信息序列的长度为 锄) 七，则进入和离开每个状态的各有2 七个分支，格图上共有2 址条可能的路径， 相应于编码器输出的2 址个码序列。 t l如 ( 口) 岛 是 s s 0 0 ( 6 ) 岛 a 岛 s 图2 3 ( 2 ，1 ，3 ) 卷积码的网格图和蝶形图 在v i t e r b i 译码的应用设计中，常需要将状态分组，将转移路径相同的几个状 态提取出来，放到同一个网格中，如图2 3 ( 功所示，网格图的这种等价表示称为蝶 形图。通常都是按照蝶形图的方法进行硬件的设计实现。 2 1 3 尾比特编码技术 实现过程中，为了处理的方便，在编码过程中，将信息序列进行分组，每组 信息看成独立的信息帧。v i t c r b i 译码是从某个初始状态开始，根据当前状态存储 的路径信息向前回溯得到上一个状态，进而得到译码路径和译码输出的。为了得 到正确的回溯起始状态，最简单的作法就是在编码过程中，使得编码器的初始状 态，与全部信息序列进入后，编码器的最终状态保持一致。 常规的较简单的作法是归零编码。也就是每一帧信息进行编码前，编码器的 初始状态设置为0 ，在信息序列结尾送入归零比特，迫使编码器的最终状态为0 。 状态归零方法实现起来比较简单，但需要传输归零比特产生的额外编码序列， 降低了码率，增加了传输开销，当信息序列很长时，在一定的误码率要求下，这 种方法对发送功率的影响才能忽略。 尾比特编码技术是一种不影响编码码率的技术。归零编码可看作尾比特技术 的特例。尾比特技术采用的方法是，在一帧信息序列送入译码器时，用末尾比特 初始化编码器，这保证了本帧数据编码的起始和最终状态一致。译码器就可以通 过这个确定的状态进行回溯译码。这种编码方案简单，使用得较多f 4 】【1 7 】。 尾比特编码技术的优点是： ( 1 ) 对码率，或信息的传输效率的影响很小； ( 2 ) 卷积码的纠错性能不受影响。 同时它也有自身的缺点： ( 3 ) 尾比特编码的卷积码用通常的v i t e r b i 译码是无法得到可靠的结果的。需要对 翠器 可配鬣的v i t e r b i 译码器的f p g a 实现 接收序列进行训练，使得译码器从正确的初始状态回溯译码，会降低有效的吞吐 率； ( 4 ) 接收机的复杂度稍有增加。 实现过程中，需要优化结构，提高总体的吞吐率，来弥补加入的训练序列对 有效吞睦率的影响。 2 。2 。1 最大似然译码 2 2 卷积码的v i t e r b i 译码算法 在一个二进制编译码系统中，如图2 4 所示。输入信息序歹| 1 1 1 被编码为序列c ， 每个m 序列长度为k ，那么每个码字c 的个数应为2 七个。c 序列经过有噪声的无记 忆信道传送给译码器。译码器根据约定的译码规则，由接收序列r 给出与发送信 息序列m 最接近的估值序列赢。由于1 1 1 和码字c 之间存在一一对应关系，所以等 价于译码器根据r 产生c 的一个估值序列e 。当且仅当i 邑一c 时，r l a = m ，这时译码 器正确译码。如果译码器输出的8 c ，则译码器译码错误。 图2 4 简单的二进制编译码系统 如果译码器对接收序列r 来说，能在掌个码字 n # - - 个使p 0 = e | f ) 最大的玛序 列c ，= 1 , 2 ，2 勺，最大的码字c 作为c 的估值序列e ，则这种译码规则一定使译 码错误概率最小，称这种译码规则为最大后验概率译码。 由贝叶斯公式 讹| r ) = 掣 ) 可知，若所有发送的码字c l 先验等概，且由于以d 与译码方法无关，所以 m a x 觚知( e ，ir ) ： m a x 戡是。( r t c l 221 ，) ( 2 - 2 ) 抽w 。，、扣，2 。，2 # ” 、。 对于离散无记忆信道( d m c ) 而言 p ( r lc ，) = 1 7 尹积| 靠) ，l = 1 ，2 ，2 。 ( 2 3 ) 式中c 盯是码字e l 的第i 个分量，n 是r 的第z 个分量。按照式( 2 - 2 ) f f d ( 2 3 ) 的规则译 第二章卷积码的编码和v i t e r b i 译码 码，就是使译码错误概率最小的最佳译码规则。常称以rc ，) 为似然函数，这种译 码规则称为最大似然译码准则( m l d ) 【6 1 。由于1 0 9 b x 是z 的单调函数，所以式( 2 3 ) 写成 ，嚣冀。1 。g ap ( r fc t ) - ，器焉。善1 。g ap ( 巧ic t ，) ( 2 - 4 ) 称1 0 9 b x 为对数似然函数，对d m c 信道，要求发端码字的发送先验等概，这样， 才可将最大后验概率译码简化为m l d 准则，否则m l d 将不是最佳译码方法。由 于对数函数的单调性以及对乘法的加法变换，实际中常使用对数形式的m l d 准则。 可看出，对数化m l d 就是对接收序列找出对数似然值的累加和最大的那条路径。 在图2 4 中，信道环境为高斯白噪声( a w g n ) 信道，均值为0 方差口2 为n d 2 。接 收序列长度为，z ，由于噪声对每一码元( 或已调制符号) 的影响独立，因而在发送序 列c l = ( c l l ，e 1 2 ，c 如) ，= 1 , 2 ，2 露条件下，接收到序列r = ( r l ，2 ，h ) 的概率为 p ( r i c ，) _ 冉 ( 1 瓜) e x p ( 一譬) ) = 【1 厕re x p ( 一窆妈( 2 - 5 ) i = 1 y 0 由m l d 准则可知，选择使以r c ，) 最大的码字c ，作为译码结果，可等价表示为 m a x p ( rjc ，) 营m i n ( ，；一劬) 2 ，= 1 ，2 ，2 。( 2 - 6 ) 定义 噍= ( ，；一龟) 2 ( 2 7 ) 为接收序列r 与码字c ，间的欧氏距离，可作为r 与c ，相关性的一种度量。若r 与 c l 间的欧氏距离最小，则把r 译为c ，。可知，m l d 等价于最小欧氏距离译码。 在实际应用中，为了简化运算，便于实现，还可将最小欧氏距离作进一步简化。 将欧氏距离展开 d e - - e ( 巧一) 2 = 2 + 气2 2 i 气 ( 2 8 ) i = 1f 蕾jf = ii = 1 式中，对于z 个如来说，由于接收到的r 序列已知，那么第一项相同，在发送码 字等能量的条件下，第二项是相同的，可作等价简化 m i n d e m a x ，； ( 2 9 ) i = 1 可配置的v i t e r b i 译码器的f p g a 实现 这正是r 与戳的内积，可作为r 与e ，的相关度量。可知，在发送码字等能量的条 件下，最小欧氏距离准则等价于最大糯关准则。 对卷积码的最大似然译码，译码就是在网格图中选择一条路径，使相应的译 码序列与接收到的序列间的距离最小。 本节的内容用作硬件实现中分支度量计算的简化的理论依据。 2 2 2 v i t e r b i 译码 最大似然译码方法只是一种译码准则，它是考虑整个接收序列进行译码的。 宙前述的编码过程可看出，码序列的个数是很大的。举例来说，当信息序列长度 为l = 5 0 帧，归零序列长度为m = 5 帧，每帧信息长度为k = - 2 比特，每帧编码序列码 长为n = 3 比特，那么码序列个数为2 托一2 1 0 0 1 0 3 0 个。如果1 秒内送出的信息元为 1 0 0 眈特，那么信息速率只有l o o b p s ，这是撮低的，但即使在如戴低酶速率下，也 要求译码器在1 秒钟计算、比较至少l o 弼个似然函数( 或汉明距离、软距离) ，相当 于译码器计算1 个似然函数的时间要小于1 0 铷秒，这是根本无法实现的。更何况 使用情况下，输入信息序列经常是长时闻、大流量的连续数据流。因此，要寻找 最大似然译码有效的工程实现方法。 基于网格图搜索的译码是实现最大似然译码的重要方法和途径，v i t e r b i 译码 正是这样一种有效的实现算法。v i t e r b i 算法并不是在网格图上一次比较所有可能 豹2 跹条路径，丽是接收一段，比较一段，选一段最可能的分支，从丽达到整个码 序列是一个有最大似然函数的序列。 v i t e r b i 译码利用了网格图的重复性结构，计算网格图上在时刻t f 各状态到达的 路径和接收序列之闻的相似度，对最大似然算法简化得到的译码准则，利用不同 的度量值进行相似度的计算。v i t e r b i 译码的基本思想是，利用路径的汇聚消除网 格图中的冗余度，译码过程只需考虑那些使似然函数最大的路径。某个状态如果 发现某条路径已不可能获得最大的对数似然函数，就放弃这条路径，然后在剩下 的“幸存”路径孛重薪选择路径，壹刭发送码序列的结尾。宙予这种方法较翠的 丢弃了那些不可能的路径，从而减轻了译码的工作量，降低了译码的复杂度。 v i t e r b i 译码实现的步骤如下： ( 1 ) 从某一时闻单位翩开始，计算进入每一状态的所有长药歹段分支的部分路径 度量。对每一状态，从转移到其中的所有路径路径，挑选并存储一条有最大度量 值的部分路径和部分度量值，称此部分路径为相应状态下的留选路径或幸存路径。 ( 2 ) ，增加l ，把此时刻进入每一状态的所有分支度量，同与这些分支相连的前一 时翔幸存路径的度量楣加，得到了此时刻进入每一状态的部分路径度量值，选取 一个状态存储具有最大路径度量值的路径，并删去其它路径；若路径度量值都相 同，则任选条路径作为幸存路径。从而得到新的幸存路径，因此幸存路径延长 第二章卷积码的编码和v i t e r b i 译码 了一个分支。 ( 3 ) 若， n 聊，为输入信息序列帧数，则重复以上各步，否则停止。译码器得到 了具有最大路径度量的路径。 步骤( 2 ) 每进行一次，由于每个状态引出两条支路，因此以后各级中，路径延伸增 大一倍，但比较它们的似然函数累加值后，丢弃一半，结果留存下来的路径总数 保持常数。直到归零比特发送完毕，整个网格图中只有唯一的幸存路径被留存。 可以看到，在已知接收序列的情况下，这条译码路径和编码路径是最为相似的。 2 3 卷积码在无线宽带接入技术中的应用 目前在w i m a x 、l t e 和u m b 无线宽带接入技术中，都将卷积码作为物理层 信道编码的一种方案。 在i e e es t d8 0 2 1 6 2 0 0 4 ( r e v i s i o no f i e e es t d8 0 2 1 6 2 0 0 1 ) 标准中，采用的卷 积码编码约束度为7 ，码率为1 2 。生成函数为 1 7 1 ，1 3 3 。，并且采用了尾比特编 码的方式【。如图2 5 所示。 碰们g o = 1 7 1 瞅 dg l = 1 3 3 瞅 图2 5w i m a x 协议中的卷积编码器 在3 g p p t s3 6 2 1 2v 8 1 0 标准中，采用的卷积码编码约束度为7 ，码率为1 3 。 生成函数为 1 3 3 ，1 7 1 ，1 6 5 o c t ，同样采用了尾比特编码的方式【2 1 。如图2 6 所示。 一l jl j l一l ji 1u 厂 歹了 1 一 r v 一w 1r 1r 1r1r 、l ，、 、 一、 ， 一、， 一v r 1 r1r1r1r ，、，、，、 一， 、- l 卵g o = 1 3 3 嘲 dg l = 1 7 1 砥 2 g 2 = 1 6 5 。吐 图2 6l t e 协议中的卷积编码器 在3 g p p 2c s 0 0 8 4 0 0 1 0 标准中，采用的卷积码编码约束度为9 ，码率为1 3 。 生成函数为【5 5 7 ，6 6 3 ，7 1 1 。，采用了类似的尾比特编码方式【3 1 。如图2 7 所示。 ：jl j i7 l j t 1 ：厂，1 ：丌_ = 丌1 ：兀_ ：i f + + 烹烹 一烹 一w一w vw rv 1r 1r 1r1 r1r ， 、 一， ，、l ，、 r 、， 一一 r 1r 1r1 r1 r 一， 、l ， 一，、一 图2 7u m b 协议中的卷积编码器 碰o o = 5 5 7 。 卵g l = 6 6 3 。 d 2 g 2 = 7 11 喊 可配置的v i t e r b i 译码器的f p g a 实现 2 4小结 本章首先对卷积码的基本概念和编码过程做了阐述，考虑到三种无线接入标 准中使用的是尾比特卷积码，将尾比特卷积编码技术做了介绍。然后描述了卷积 码的译码，本文采用的v i t e r b i 译码算法是对最大似然译码作了简化，首先介绍了 最大似然译码，考虑到降低算法的实现复杂度，将最大似然译码作了各种简化以 便介绍v i t e r b i 译码的一般原理。最后将三种接入协议中使用的卷积码作了简单的 介绍。 第三章可配置v it e r b i 译码器的结构设计1 5 第三章可配置v i t e r b i 译码器的结构设计 本章给出了可配置v i t e r b i 译码器的实现。依据译码器工作参数的仿真选择， 充分考虑算法及运算结构的优化，详细论述了各主要功能模块的设计和实现方案 的选择。着重论述了动态可配置功能的实现以及数据流控靠4 机制的荸l 入。 3 。l 译码器总体实现结构 本章针对w i m a x 、l t e 和u m b 协议中使用的卷积码，给出了兼容不同协议 的可配置v i t e r b i 译码器的设计与实现。协议与系统标识一对应。译码器具备系 统标识、回溯初始状态和回溯深度等参数动态可配置的功能，结合流量控制的整 体设计结构，在大流量持续输入的情况下，可以正常、可靠、高速地完成卷积码 的译码。译码器包括分支度量计算、路径度量管理和幸存路径管理等主要模块。 图3 。1 译码器的总体设诗结构 译码器的总体设计结构如图3 1 所示。在接收端，经过前端处理的数据送入译 码器。其中，f i n 、f b m u 和f o u r 是f i f o 。到达译码器的数据经过输入数据缓 存模块i n p u t 和f i n 后，进入分支度量缓存模块b m u 秘f b m u 。所有分支度量 的计算结果送入路径度量管理模块a c st o p 。对于每个状态的两条到达支路，路 径度量管理模块将上级路径度量与本级分支度量累加，比较运算结果并更新本级 路径度量，同时选择幸存路径。将幸存路径标志信息存入循环存储模块中。 r a mc t r 和r a m 0 - - 一r a m 3 构成循环存储模块。r a mc t r 根据路径度量管理 单元和幸存路径管理单元产生的当前r a m 的读写控制信号，将r a m 允许读写的 状态信息进行反馈，使得循环存储模块可以按照预先设计的流水线方式正常高效 1 6 可配置的v i t e r b i 译码器的f p g a 实现 地工作。幸存路径管理单元读出所需的幸存路径标志信息，采用回溯结构完成译 码