（信号与信息处理专业论文）turbo码的sova译码算法在fpga中的实现.pdf

【摘要】 t u r b o 码以其接近s h a n n o n 理论极限的优异性能在无线通信中起了举足轻重 的作用，受到了人们的广泛关注。本论文讨论了t u r b o 码的译码原理，分析了 t u r b o 译码的几种常用算法并比较了它们的优缺点，着重分析了s o v a 译码原理 以及在f p g a 上的硬件设计方案。我们设计的采用后验度量算法的双滑动窗 s o v a 译码方案，支持3 g p p t s2 5 2 1 2 协议中规定的最大信息速率( 2 m b i t s ) ， 而硬件资源仅约为一般维特比译码器的两倍。 苤毽逦w c d m a ，t u r b o c o d e s ，s o v a ，f p g a a b s t r a c t t u r b o - c o d e s ，w i t ht h ep e r f e c tp e r f o r m a n c en e a rs h a n n o nl i m i t , p l a y sa l l i m p o r t a n tr o l ei nw i r e l e s sc o m m u n i c a t i o n sa n di st h ef o c u so fs c i e n t i s t s a n d e n g i n e e r s r e s e a r c h i n g i nt h i sp a p e r , w ed i s c u s st h ep r i n c i p l eo ft u r b o - c o d e d e c o d i n g ，a n a l y z es e v e r a lo r d i n a r ya l g o r i t h m s o nt u r b o c o d ed e c o d i n g ，a n d c o m p a r et h e r ep e r f o r m a n c e s w i t ha ne m p h a s i s ，w ea n a l y z et h es o v aa l g o r i t h ma n d d e t a i lan e wa r c h i t e c t u r ew h i c hl e a d st oar e a l - t i m ec i r c u i t a sa na p p l i c a t i o n ，w e i m p l e m e n tt h i sa r c h i t e c t u r en a m e d “d o u b l e s l i d e w i n d o ws o v a w i t hap o s t e r i o r i w e i g h t i n ga l g o r i t h m ，w h i c hs u p p o r t st h em a xt r a f f i ci r i t e n s i t yd e s c r i b e di n3 g p p t s 2 5 2 1 2p r o t o c o la n dt h es i z ei sr o u g h l yt w i c et h es i z eo f t h ec l a s s i c a lv i t e r b id e c o d e l k e y w o r d s w c d m a ，t u r b o - c o d e s ，s o v a ，f p g a t u r b o 码的s o v a 译码算法在f p g a 中的实现 绪论 第一节第三代移动通信系统 ( 一) 下一代移动通信系统的特征 在上个世纪8 0 年代末，以频分多址为特征的第一代移动通信系统已经进入 大规模发展的时期，而以时分多址为特征的第二代系统暂露头角。第一代系统实 现了人们对移动通话的要求，第二代系统则提高了系统容量，并支持区域内漫游， 但是，这些还都只是初步的实现了人们对“移动通信”的理想而己。 这时，有线通信领域由于光传输技术的突飞猛进，使因特网蓬勃发展，并且 为用户提供了多种业务和崭新的生活方式。自然而然的，人们期待无线通信领域 能够有一次革命，通过支持全球覆盖以及更宽、更灵活的业务，使得因特网不再 是有线领域的概念。具体而言，这种系统应达到以下要求。 ( 1 ) 在服务质量方面。对话音业务，具有更好的通话质量和尽可能小的延迟， 对于数据业务，提高现有的传输带宽，减少误码率；此外，系统还应获得 最大的频谱利用率，支持更多的用户； ( 2 ) 提供新的业务种类和服务类别。下一代系统应克服二代系统在数据业务上 的落后局面，能够实现从自u 所不能实现的新话音和数据业务，并支持一定 的q o s 措施如按要求分配带宽等； ( 3 )在系统升级的时保证平滑过渡，保护已有的巨大投资； ( 4 ) 系统的运行具有相当的灵活性，支持多模式、多频段和多环境，多模式和 多频段允许用户的“漫游”需求，灵活性体现在业务的适应性上如多媒体 业务： ( 二) i m t - 2 0 0 0 ：第三代移动通信系统 t u r b o 码的s o v a 译码算法在f p g a 中的实现 针对上述要求，国际电联( i t u ) 提出了f p l m t s ( 未来公共陆地移动通信 系统) ，并预期该系统在2 0 0 2 年左右投入商用，又由于该系统的一期主频段位于 2 g h z 附近，i t u 正式将其更名为i m t - 2 0 0 0 ，也就是第三代移动通信系统。 不同于第一、二代系统的多址方式，由于c d m a 方式能够有效的提高时机 系统的容量，并实施各种新技术，进而满足人们对下一代系统的核心要求即大容 量、多业务，因此成为第三代移动通信系统的核心技术。 在第三代系统的概念提出后，各种厂商与地区的标准化组织便纷纷行动起 来，展开系统设计与标准化的活动，目的是占领技术上的领导地位，争取市场先 机。截至到1 9 9 8 年6 月3 0 日，提交到i t u 的地面第三代移动通信无线传输技 术( r t t ) 共有1 0 种。其中f d d 方式8 个，t d d 方式5 个。此后，经过众多 标准化组织如3 g p p 、3 g p p 2 等不懈的努力，众多厂商及运营商就商业系统技术 规范的意见已经基本趋于一致。2 0 0 0 年5 月举行的i t u r 2 0 0 0 年全会上最终批 准通过了i m t - 2 0 0 0 无线接口技术规范。宽带c d m a 技术作为主流技术类别包括 3 g p p 组织提交的w c d m a 、3 g p p 2 组织提交的c d m a 2 0 0 0 和中国提交的 t d s c d m a 。其中前两种为f d d 方式而后一种为t d d 方式。 在i m t - 2 0 0 0 中，出于克服无线传播中的各种衰落和系统多址干扰的目的， 各种标准均有针对性的采用了相应的新技术予以消除，主要包括： ( 1 )为减小系统的多址干扰，采用功率控制技术，包括开环功控、闭环功控和 外环功控；另外还可使用智能天线技术，一是对来自移动台的信号进行到 达角估计，作空域滤波，是对基站发射信号作波束成型，从而降低功率， 减小对其他用户的干扰，从某种程度上讲，该技术应属于一类多址技术 ( s d m a ) ，归结到底提高了系统的容量： ( 2 ) 为克服时间选择性衰落( 多普勒频移) 而采用信道交织技术，但交织区间 定要大于相关时间，这样便将有记忆的突发信道改造为无记忆的随机独 立差错信道，有利于纠错码的应用； ( 3 ) 为克服空间选择性衰落，借助于发射与接收空问分集技术，前提是保证天 线间隔大于荇干个波长； ( 4 ) 为克服频率选择性衰落，进行初始同步与r a k e 接收处理，这是由于扩 频系统的信号，其带宽较宽，码片时间一般均小f 城市繁华区多径时延值 t u r b o 码的s o v a 译码算法在f p g a 中的实现 5 u s ，所以在获取同步的前提下，便可以进行多重路径的分辨和处理 第二节信道编码技术 在通信系统的设计和评估中，我们非常注重三个指标，那就是有效性、可靠 性、安全性。所谓有效性就是指占用尽可能少的信道资源( 如频段、时隙、和功 率) ，一般通过信源编码来实现：所谓可靠性，主要是指在传输中抵抗各类客观 自然干扰和人为干扰的能力，一般通过信道编码、合理运用调制技术来实现：所 谓安全性，主要是指在传输中的安全保密性能，可以通过扩频或者密码来实现。 这里我们主要讨论用来实现可靠传输的信道编码技术。 信道编码技术的种类很多，我们经常使用的包括线性分组码、卷积码、交织 编码、级联码、t u r b o 码等等。其中，线性分组码包括h a m m i n g 码、c r c 码、 b c h 码、r s 码、f i r e 码等等；交织编码有块交织和卷积交织俩种：卷积码是 最常见的一种非分组码，它构造简单，功能也比较强大，一般采用维特比算法进 行译码；级联码是一种利用短码构造长码的手段，由内码和外码级联而成，原则 上讲，内码和外码都可以采用分组码和卷积码，但最常见和有效的组合方式是内 码采用软判决的维特比译码的短约束长度卷积码，外码采用高性能的非二进制的 r s 码：t u r b o 码其实也是一种级联码，但是它也融合了交织编码，卷积编码， 性能非常优异。 下面，简要说说数字移动通信系统中的信道编码技术。移动通信信道是衰落 信道，其大致的差错率通常是l o 1 0 ，信道上符号错误类型包括随枫独立错 误和突发序列错误。在信道编码的差错控制方案中，有前向差错控制( f e c ) 和 自动重复请求( a r q ) 两种，或两者的联合使用。3 g 以前的移动通信系统主要 针对话音业务，采用简单的f e c 差错控制就能满足误码率要求，而且系统的时 延较小。在第三代移动通信中，由于首次。| 入高速数据业务，且存在多种数据业 务，这类业务对误信率要求更高，我们司以采用更高性能的f e c 编码，而且必 要时也可以在物理层或网络层上结合a r q 方案，以适应不同的业务要求。 对f 语音业务，一般要求信息在解码晤误码率率为l o ”或更低。为此，f _ l 乎 t u r b o 杩的s o v a 译码算法在f p g a 中的实现 所有的蜂窝系统一致地采用了卷积码。如g s m 系统中使用分组循环码检错，使 用1 2 和1 3 ( 凿孔) 卷积码进行纠错控制；i s 9 5 之中则采用了( 2 ，1 ，8 ) 卷积码 + 块交织方式进行差错控制；在w c d m a 和c d m a 2 0 0 0 等3 g 系统中也都采用 ( 2 ，1 ，9 ) 或( 3 ，1 ，9 ) 的卷积码。 对于数据业务，i m t - 2 0 0 0 只提出了要达到1 0 。或更低的差错率，但并未规 定具体编码方案。在标准制定过程中曾使用r e e d s o l o m o n ( r s ) 码+ 卷积码级 联编码方式，但是最终，w c d m a 和c d m a 2 0 0 0 中都引入t u r b o 码作为数据业 务差错控制的主要方式。这是因为与r s + c v 方式相比，它可多获得l c l b 的增益， 虽然在译码复杂度上要大于前者。此外，信道编码中还使用了c r c 检错机制和 块交织技术，以在系统中进行f e r 测量和对抗快衰落突发错误。 第三节论文内容 本实验室多年来跟踪c d m a 通信技术，对宽带c d m a 通信中多项关键 技术都有深入研究。并在c o s s a p 平台上建立了完整的w c d m a 仿真环境。在 此基础上，开始研发w c d m a 硬件实验平台，为将来的进一步的研究奠定基础。 本人有机会参加了w c d m a 移动系统硬件平台的开发。在此过程中，主要实现 信道编译码器。主要工作： 分析3 g p p 协议中有关信道编码和映射的规范，主要是数据业务部分： 设计信道编码器，包括卷积码和t u r b o 码： 在f p g a 上设计实现基于s o v a 算法的t u r b o 码译码器； 设计f p g a 与d s p 的交互接口，与王刚强同学设计的d s p 共同完成 3 g p pt s2 5 2 1 2 协议中规定的信道编译码、速率匹配、信道复用等。 论文第一章详细阐述了i t u r b o 码的编码原理，译码过程和性能分析，着重 分析了s o v a 算法的硬件实现方案。第二章介绍了w c d m a 硬件平台的结构以 及信道复用信道编码部分的f p g a 和d s p 的接口设计思想、实现细节。第三章 就交织器和双滑动窗s o v a 算法在f p g a 中的实现进行了详细的况明。第四章 总结设计过程中的一些收获。 4 t u r b o 码的s o v a 译码算法在f p g a 中的实现 第一章t u r b o 编、译码原理及性能分析 在无线通信迅速发展的同时，我们不要忘记，支撑它发展的是一系列先进技 术，信道编码技术是其中之一。在无线通信中，信道编码起着举足轻重的作用。 这是因为，无线通信的环境常常是恶劣的，信道的信嗓比很低，多径衰落和 d o p p o l e r 频移等等的影响，因此，寻求种在极低信噪比情况下的强大纠错工具 就成了急待解决的课题。终于，在1 9 9 3 年瑞士日内瓦召开的国际通信会议上， c b e r r o u 等人找到了种所谓的t u r b o 码编码技术。 所提出的t u r b o 码与以往其它类型的码相比，它的性能更接近s h a n n o n 的理 论限( 离此极限不到l d b ) 。更重要的是，t u r b o 码的性能在低( 至中) 信噪比s n r 的条件下仍可以接近于s h a n n o n 限。1 9 9 6 年，c b e r r o u 等人将他们的发现进 步整理总结，将文章发表在i e e e 通信汇刊上。该文在1 9 9 7 年获得i e e e 关于信 息论论文奖。t u r b o 码是编码界的一个里程碑。 t u r b o 码一经c b e r r o u 等人提出，立即受到了世界范围内信息和编码理论界 的关注，并成为该领域近几年来研究的热点。i e e e 等一些重大的国际性学术会 议和著名学术期刊均发表了大量有关t u r b o 码的研究成果，有关t u r b o 码的专题 研讨会也不时在些国家举行( 如i e e ej o u m a l o ns e l e c t e da r e a s i n c o m m u n i c a t i o n s ) ) 在2 0 0 0 第2 期出版关于m b o 码研究的专辑) 。目前对t l 曲o 码研究主要集中在以下几个方面： 1 t u r b o 码的工作机理t u r b o 码的产生是实践的结果，没有确定的设计准 则，这对t u r b o 码的设计和优化产生了定的困难。因此，有必要对t u r b o 码的编 码机理进行研究，以便为好码的构成提供指导。要完成t u r b o 码编码机理的研究， 有待于对t u r b o 码的正确建模，这是极其吸引人的却又非常困难的问题。 2 t u r b o 玛交织方法的选择t u r b o 码中的交织器对t u r b o 码的性能有很大 的影响，选择恰当的交织器，将使t u r b o 码的性能得到充分发挥。什么是最佳的 交织方法，一宜没有定论，这是研究n 而o 码必颁解决的一个关键闯题。 3 t u r b o 码的译码算法 对m a p ( m a x i m u ma p o s t e r i o r i ) 算法和s o v a ( s o f t o u t p u tv i t e r b ia l g o r i t h m ) 算法正在开展广泛的研究，主要围绕译码性能、时延和 实现复杂性进行研究。 t u r b o 码的s o v a 译码算法在f p g a 中的实现 4 t u r b o 码的思想方法延拓面向分组的t u r b o 码的构造、译码及其性能的 研究正在开展；采用串行级联方法进行编码的t u r b o 码的研究也在进行。 5 t u r b o 码的应用由于t u r b o 码性能优越，有望出现在各种通信系统中， 如移动通信、个人通信、深空通信、卫星通信等：t u r b o 码在移动通信和个人通 信环境下的应用是当今最令人关注的问题。 6 t u r b o 码和其它通信技术的结合 这方面人们进行了广泛的研究，如 t u r b o 码与调制技术( q a m ，t c m ) 的结合，t u r b o 码与均衡的结合，t u r b o 编码与 信源编码的结合，t u r b o 译码与接收检测的结合等等。对于以上几方面，人们研 究均很活跃，取得了不少成果，但是总的看来，研究均处于初级阶段。此外，值 得一提的是，欧洲数字广播标准中已确定采用o f d m 和t u r b o 码，1 9 9 6 年完成 了系统模拟，现在瑞典等国正在进行a s i c 的设计和验证。在硬件实现方面，t u r b o 码的试验芯片己经开发出来，法国、澳大利亚、美国的3 家公司均宣称开发出了 相应的产品。 下 所示。它是由两个递归卷积编码器( r s c ) 以也称为并行级联卷积码( p c c c ) 。 + 输出x 2 图1 1t u r b o 编码器 t u r b o 编码器输出时依次输出系统比特x ，校验比特y 1 ，校验比特y 2 。两 个递归卷积编码器结构可以相同，也可以不相同。在大多数的应用情况下，为了 6 t u r b o 码的s o v a 译码算法在f p g a 中的实现 简化译码器结构，一般使用相同的r s c 。每个卷积编码器称为t u r b o 码的成员码 ( c o n s t i t u e n tc o d e ) 。 7+一。一xk 图1 2 递归卷积编码器 递归卷积编码器的一般结构如图1 2 所示。如图卷积编码器中系数g l i ，g o j ， i 0 ，1 , 2 ，3 ，分别是校验比特乘积多项式和反馈多项式系数。 在此，对如图的r s c 编码器进行一个简单的分析，在这个r s c 编码器中， 记忆单元v = 3 ，约束长度为k - - v + l = 4 ，在k 时刻，输入比特d k ，输出编码比特 c k = ( x k ，y k ) 。设记忆单元输入比特变量为a k ，则 吼= d + g 胡 ( 1 ) i = 1 9 1 。，g o i ，a k ，取值空间为( o ，1 ) 。上式又可以改写为： d = g 。，口 ( 2 ) 则r s c 系统卷积码输出可表示为： x k = d k k = g l 口 ( 3 ) ( 4 ) 在以往的卷积码纠错编码应用中，多使用非系统卷积码( n s c ) 和系统卷积 码两种。已有的研究结果表明，相同记忆单元长度，n s c 的误码率特性在高信 澡l l ( s n r ) 的情况下优于系统卷积码，而在低s n r 的情况下，则要较系统码差。 t u r b o 码的s o v a 译码算法在f p g a 中的实现 这也是一般纠错编码的普遍特性，从编码序列方面来看，这是因为n s c 的自由 距d f 要较系统码大。递归系统卷积码r s c 结合了n s c 和系统码的特性，在码率 r ，2 3 时，在任何s n r 下都优于n s c 码，虽然在r 2 3 时，在大的s n r 时仍 较n s c 码差。 交织器的作用在于随机置乱两个成员码生成的校验比特位置。从自由距的角 度看，t u r b o 码的自由距，主要取决于交织器，而并不仅由其成员码的自由距决 定。从码重量谱的角度去看，主要目的是将导致第一个编码器输出为低重量码字 的输入序列经过交织器后，可以使第二个编码器的输出为高重量码字，从而使整 个编码后的输出达到高重量，以便提高t u r b o 性能。交织器分为规则和非规则交 织器两类。在多数t u r b o 码性能分析中使用的是规则交织器，如块交织器，螺旋 交织器，多级交织器等。而非规则交织器会提供更好的性能，如随机交织器， m o d k 交织器等。但是，到目前为止，还没有一个最优化的交织器设计准则。 t u r b o 编码器采用分块编码的方式，即将信息码流按一定的长度分隔为编码 块，编码交织、译码均以块为单位。这种方式会引入一定的时延，设信息传输速 率为r b ，编码块长为k ，则编码和译码引入的固有延时至少是2 k r b 。对于实 时业务，例如语音业务，这是。个需要考虑的重要因素。 t u r b o 码的码率可以通过凿孔( p u n c t u r i n g ) 来提高，如通过如下的凿孔矩阵 可实现将每个1 2 码率的成员码提升到2 3 码率，矩阵中“0 ”表示对应比特删除， 矩阵列数对应两个成员码个数，矩阵右乘实现对各成员校验码序列的凿孑l 。也即 两个成员码交替输出校验比特，总的t u r b o 码码率为l ，2 。 肚闲 t u r b o 总的码率可由下式计算： 到：土+ 上一1( 6 ) 胄 r lr 2 r l 和r 2 分别为两个成员码码率，为达到更好的性能，应满足r l r 2 。且这 种凿孔操作一般只在校验比特上进行。 t u r b o 码的s o v a 译码算法在f p g a 中的实现 第二节t u r b o 码迭代译码原理及译码算法介绍 1 2 1t u r b o 码迭代译码原理 t u r b o 码的编码部分由两个子编码器组成，在其译码部分也就相应有两个子 译码器。t u r b o 码译码器在一种级联反馈结构上完成迭代译码的过程。译码器l 提供的判决符号的软输出值或外信息量作为译码器2 的输入先验信息，译码器2 产生的外信息量作为先验信息反馈给译码器1 。采用这种迭代译码器的好处是， 每个译码器不仅能利用本译码器的信息比特和校验比特，还能利用前一译码器提 供的信息进行译码，从概率论的角度进行分析，在保证形成负反馈的前提下，每 次迭代的结果均进一步趋近真实值。这样的过程理论上可以重复多次，直到增加 迭代次数无法显著改善性能为止。两级子译码器之间通过交织器或解交织器隔 离。交织器和解交织器的存在主要有两个作用：( 1 ) 打散译码器的软输出序列， 使突发错误的长度变短。 ( 2 ) 尽量减小先验信息序列与编码符号序列之间的相 关性。当交织长度足够大时，可以近似认为先验信息序列与符号序列互不相关， 这时二者联合提供的信息量达到最大。 图1 3t u r b o 码译码器的逻辑模型 图1 3 展示的是t u r b o 码译码器的逻辑模型，反映出先验信息、外信息、可 靠忾信息在译码器中流动的基本方式。不同的t u r b o 码译码器对这三种信息量有 各自的处理方式，包括信息量的提取、传递和加工。这就是我们下面将要介绍的 t u r b o 码常用译码算法。 t u r b o 码的s o v a 译码算法在f p g a 中的实现 1 2 2t u r b o 码常用译码算法 通常t u r b o 码译码比较常用的算法就是最大后验概率( m a p ：m a x i m u ma p o s t e r i o r i ) 算法和软输出维特比算法( s o v a ：s o f to u t p u tv i t e r b ia l g o r i t h m ) 。由于 m a p 算法中包含乘法运算，计算复杂、速度慢、不利于硬件实现，所以将其运 用到对数域就有了l o g m a p 、m a x - l o g - m a p 等算法。 下面分别介绍一下m a p 、l o g m a p 、m a x l o g m a p 、s o v a 等算法。 1 m a p 算法 c h a n g 和h a n c o c k 最早提出m a p 算法，当时只是用来减小有码闻串扰信道 的错误符号( 比特) 比率。但几乎同时，b a h le ta 1 和m c a d a me ta 1 就将m a p 算法用到了编码信道上。 下面，我们就给出加性自高斯噪声信道( a w g n ) 中系统卷积码m a p 译码 算法的完整推导。 r 对于一个有v 个寄存器单元的编码器，我们定义其k 时刻的状态为s ，s 是 一个v 维向量，仅与每个存储单元的输出有关。k 时刻的输入信息比特为d 。，此 时编码器的状态由墨转变到s ，同时，我们假定信息比特序列( d 。) 由n v 个 独立的比特d 。组成，它分别以先验概率器、矗取值0 和1 ，这里器+ 爿= 1 。我 们令译码器的初始状态值s ，= o ，最后的v 个信息比特( d 。+ ，到d 。) 是追零比 特，可以让寄存器的状态在n + 1 时刻归零( 也就是说又+ 。= o ) 。 假设用的是码率为1 2 的带反馈的系统卷积码编码器，它在k 时刻的输出有 两个，一个是未经编码的比特，另一个是经过编码的比特q ，编码输出经b p s k 或者q p s k 调制后送到a w g n 信道。在接收端，我们定义接收到的比特序列为： r ，= ( r r ”r ) ( 7 ) 这里，r 。= ( k ，儿) 是k 时刻接收的符号。h 、y 。的定义如下： 毛= ( 2 d 女一1 ) + 见 ( 8 ) y = ( 2 c 一1 ) + g 。 ( 9 ) t u r b o 码的s o v a 译码算法在f p g a 中的实现 p 。、q 。是俩个独立的、方差为占2 的正态随机变量。我们定义跟每个待译码 比特d 。相关的似然比以为： 。一p r ( 巩= 0j 月，) 一丙瓦丽 ( 1 0 ) 这里p r ( d 。= i 群) ( i = 0 1 ) 是数据比特疵的最大后验概率( a p o p ) 。反 的后验概率可以由下式定义的联合概率密度推导出来， 砧= p r ( d = i ，s k = m l r ，) ( 1 1 ) 这样，d 。的后验概率就可以写成 p r ( d 。= i i r ，) = 以” ( 1 2 ) 这里的i = 0 ，1 ，求和运算在全部2 ”个状态上进行累加。联合( 1 0 ) 式和( 1 2 ) 式，跟以相关的似然比以可以写成 通过比较五和门限值1 ，译码器就可以作出如下判决： ( 1 3 ) 磊= 侄矧 ， 用b a y e s 准则，( 1 1 ) 式中的联合概率密度表达式可以写为： 前”= p r ( d = i ，s i = m ，r ，) p r ( r ( ) = p r ( r i d , = i ，墨= m ，掣) + p r ( 碟l i 破= i ，s k = m ，b ) p r ( 吐= i r s = m ，乓) p “r ，)( 1 5 ) 我们假设墨= m 表示k 时刻前的事件不会受到k 时刻后事件的影响，且定 义口? 为k 时刻m 状态时的前向状态度量，那么 p r ( 足1 1 d ：1 s = m ，r f ) = p r ( 月? i s 。= m ) = f 1 6 ) 类似地，我们僻到 矿矿 生。 = 以 t u r b o 码的s o v a 译码算法在f p g a 中的实现 p r ( r l i d , = i ，s k = i 珥r ! ) = p r ( r 盘l i 瓯+ i = f ( i ，所) ) = g 川 ( 1 7 ) 这里的j ( i ，胁) 表示状态为m 时输入为i 后的状态值，芦f 为k 时刻状态为m 时的反向状态度量。我们定义分支度量如下： = p r ( 哝= i ，s t 一- - n - m ，r k ) ( 1 8 ) 将( 1 3 ) 一( 1 5 ) 式代入( 1 2 ) ，得到 丸f = a ：6 r ip 3 9 1 p r ( r ，) ( 、9 ) 再将( 1 6 ) 式代入( 1 0 ) 则 口i 1 矿彪p 2 参丽 q 上式的求和运算是在全部2 个状态上进行累加，且分子和分母上各有一次 累加运算。 ( 1 6 ) 式可以通过递归进行计算。过程如下： 口? = p r ( r j * i s k = m ) = p r ( d = 歹，s r m 7 ，r s = m ) m 。j = o 1 ：p 胄? i d , 。= ，最= m ，一，= 脚，墨一。) “ ( 2 1 ) + p r ( d k l = ，s l = m ，凡一。i 瓯= m ) = p r ( 钟- 2i s 一，= b ( j ，m ) ) + p r ( d k 一= ，& 。= b ( j ，m ) ，见一。) ，= o l = 口等川础u 川 ，m o 上式中，第一重累加运算变量研从0 到2 一l ，6 ( j ，m ) 表示当前状态为r n 上一时刻输入为j 时，所对应的前一个状态。利用同样的方法，我们可以从芦昱，递 归推导出所。必须注意的是，只有在整个数据块全部接收完毕后，才能进行反 向度量的计算。这样，( 1 7 ) 市以写成： t u r b o 码的s o v a 译码算法在f p g a 中的实现 群= p “r ：i s k = m ) = p r ( d , 一。= j ，是+ 。= 脚，犬墨= 掰) m 。j o = p r ( 碟，i d 。= _ ，s = m ，s + = 所7 ，风) “一 ( 2 2 ) + p r ( d i = ，s k + l = m ，r i s = 嘲 = p r ( r 晶i 墨+ 。= f ( j ，m ) ) + p r ( d k = ，& = m ，r 。) j - o 1 = p 盘删6 j - o 图2 4 给出了计算和芦f 的示意图，它同维特比算法的结构非常相似。不 同的是，在维特比算法中，我们将分支度量和状态度量相加，而在m a p 算法中 却将二者相乘：在维特比算法中，我们寻找最小路径度量，而在m a p 算法中却 将路径度量相加。也就是说，维特比算法中的加一比一选( a c s ) 运算在m a p 算法中变成了乘一加( m a ) 运算。 k lk 口b 一( o l ，m ) so 矗二，j 2 0 c ，1 口? 8 _ 1 , b t l , ) j ：1 口衙b ( i 州 kk + 1 8 | ：孓”1 一，万- 3 = 0 8 ：一。 y 、j = 1 占：，”。 1 引冀。 图1 4 前向状态度量和后向状态度量示意图 m a p 算法的 。作原理是：先正向计算前向状态度量值钟并存储结果，然后 反向计算反向度量值芦，。观察后发现，( 2 2 ) 式中的群4 麟”项在( 2 0 ) 式对五 的计算式中也出现r 。所以，在计算彤的同时就可以利用耐”艄项：_ 讨算五， 这样就可以减少运倬次数。如果编码器的起始状态为0 ，我们可以这样初始化： 口? = 1 且口? = o ( m o ) 。如果编码器编码结束对被迫零，则麒。可以向样初始 化；如果编码器编弼结束状态未定( 没有迫零时发生) ，则对于任何1 t i 郡有芦 = 1 。 t u r b o 码的s o v a 译码算法在f p g a 中的实现 分支度量酬4 。由离散无记忆信道( d m c ) 的转移概率和先验概率( a p r p ) 确定。利用b a y e s 准则，( 1 8 ) 变为： 6 7 = p r ( dk = i ，s k = m ，r k 、 = p r ( r tl 吃= i ，s k = m ) + p r ( & = 坼 d 女= i ) p r ( d = i ) ( 2 3 ) = p r ( x , i 以= f ，& = m ) + p r ( y i d i = f ，瓯= 加) “2 ” 既然p 。、q 。是相互独立的，那么当前状态就与当前输入无关，可能是2 ”种 状态中的任何一种。定义六= p r ( d = i ) ，对于均值为0 ，方差为占2 的a w g n 信道，( 2 3 ) 式变成： ，j1 掣。莉嘉。x p ( 一寺k 一( 2 i - 1 ) 2 ) 吼 + 丽1e x p ( 一寺【y t 一( 2 c ”一1 ) 】2 ) d y 女 ( 2 4 ) = k 女最c x p l , ( 椎i + y c “) 】 上式中蚝是个常数，出 、砒是、y 。的差分值，l 。= 2 6 2 ，c l m 是在s = m ，d k = i 时编码生成的校验比特。因为( 2 4 ) 式中的墨对( 2 0 ) 式中的丸没 有什么影响，所以我们可以忽略它。实际上，在我们计算前向和反向状态度量的 时候，我们都令丘等于前一状态度量值中最大值的相反数。这样就归一化了新 的状态度量值，确保状态度量值不会为负或者溢出。 将( 2 4 ) 式代入( 2 0 ) 式，我们得到： ，。口，e x p ( l , y 女c “州户凹川 2 嚣e x p ( 硌萎甄砭瓣( 2 5 ) = 厶e x p ( - l c x ) “ 这里氕= 嚣一是输入先验概率的比值，六是输出的外信息。我们可以将 六看成输入信息的修正值，它可以减小译码后的错误概率。在t u r b o 译码过程 中，外信息是非常重要的，因为它让修正值从一级译码器送到下一级译码器。 2 l o g - m a p 算法 为了降低译码复杂度，我们要设法减少m a p 算法中乘法运算的次数。这司 t u r b o 码的s o v a 译码算法在f p g a 中的实现 以通过对该算法取对数( 或者负对数) 来实现。同样，这种技术最初也是运用在 码间串扰信道上，而后才用到编码信道上。 如果取负对数，m a p 算法中的乘法运算就转化为加法运算，但加法器要比 乘法器好实现的多。不过，加法运算就转化为e 运算，其定义如下： 盘e 6 = 一l 。g r ( 占一“+ 占一6 ) 。 ( 2 6 ) = m i n ( a ，6 ) 一i o g 。( 1 + 占一”“) 函数m i n ( a ，b ) 和l a - b i 可以通过减法器和选择器实现。但是，函数 f ( z ) = l o g 。( 1 + 占。：) = c l n ( 1 + e 。”) ( 2 7 ) 就很难实现，这里c = i l n e = j o g 。e 。图1 ，5 是c = l 时，( z ) 的曲线。由图 我们可以看到：函数，( 。) 很快就衰减到0 ，在z o 时其最大值为c l n 2o 6 9 3 c 。 这样，f ( z ) 就可以用一个小的查找表实现。对于不同的c 值，可以用一系列查 找表。 l i 、 令l k = 一l o g 。矗 a ：= 一l o g ，a ： b ：= 一l o g 。p ： 磷= 一l o ge 6 ： 图1 5c = l 时的厂( z ) 与z 关系图 ( 2 8 a ) ( 2 8 b ) ( 2 8 c ) ( 2 8 d ) t u r b o 码的s o v a 译码算法在f p g a 中的实现 那么m a p 算法变成： 2 一12 一1 厶= e ( 掣+ 硝“+ 醐p ) 一e ( 群+ 谚”+ 磁y ) ( 2 9 ) m = 0m = 0 = e ( a b ( j 川5 - d j b ”) j = o l b f , = e ( 占嚣f ”1 + 驯) j = o ，一l 这里，e 口。= 口o e a le e 口“，分支度量 ，卸 ( 3 0 ) d ：”= 一l o g 。k k l o g ；“一a ( x k i + y k c ”) = 一l o g 。一l o g 。嚣一l o g 。( 爿嚣) 一a ( x k i + y k c ”) ( 3 2 ) = 一e 一( 毛+ a x k ) i a y c 这里，k 是一个常数，a = 2 8 2 1 0 9 。e = 上。c ，z k = 一l o 玉是对数先验概 率。为了再度归一化，我们令托等于前一状态度量值的最小值。我们可以将a 看成是经过解调和量化后的无噪信号的幅度。注意，我们可以通过随意改变a 和。的值去确定c 值，这时，( 2 7 ) 式查找表的值也得跟着改变。反过来，如果 给定三。和一个c 值对应的查找表，我们就知道了a 值。( 2 5 ) 式可以改写成 l k = z k + a x k + = j 上式中z ：= - l o g 。“是译码器引入的外信息的对数表示。 3 i v i a x - l o g - m a p 算法 如果我们令f ( z ) = o ，那么( 2 9 ) 一( 3 1 ) 式就变成： 厶= 母( + 磁”+ 碟) 一哪n ( 卅+ 磁一+ r f ( 1 ) = m i n i ( ，b ( o ，州+ 磁紫”弧霹r 1 + 叫挚呐) 】 鲜= m i n i ( 磁+ d , o ”) ，( 硝y + 叫) 】 月， ( 3 4 ) 【3 5 ) l3 6 ) 这种次优算法有一个优点，就是与噪声方差占2 独立。和m a p 算法一样 t u r b o 码的s o v a 译码算法在f p g a 中的实现 这种算法最先也是应用在码间干扰信道中。跟维特比算法类似，它的硬判决性能 也不错。但要提请注意的是：m a x - l o g m a p 中前向状态度量的计算跟维特比 算法中的状态度量( s m ) 完全一致。但不同的是，m a x - l o g m a p 中状态度量 ( s m ) 在反方向上也得计算，因为只有这样才能确定似然比。 4 s o v a 算法 s o v a 算法的全称是：软输出维特比算法( s o f t - o u t p u tv i r t e b ia l g o r i t h m ) 。 维特比算法( v a ) 在通信接收器中已经成为一个工具，在解调、译码、均衡中 都有广泛的应用。在q a m ( 正交振幅调制) 和c p m ( 连续相位调制) 等系统中， v a 的级联得到了应用。在这些系统中，v i r t i b i 接收器代替了传统的调制机制。 然而在v i r t e b i 级联系统中存在着以下缺点：内v a 调制会产生突发错误，而外 v a 调制又非常敏感；内v a 产生硬判决限制了外v a 运用接收软判决的能力。 在实际应用中，这两个缺点越发明显，于是引入了s o v a 算法，它采用软( 硬) _ 判决计算度量值，且输出相应判决比特和可靠行信息。 s o v a 算法是h a g e n a u e r 于1 9 8 9 年提出来的。它是v i t e r b i 算法的改进类型。 v i t e r b i 算法是一种最大似然译码算法，通俗的讲，它的译码过程是在接收序列r 的控制下，在码的篱笆图上走编码器走过的路径。 图1 6 所示的是3 g p pt s2 5 2 1 2 协议中规定的t u r b o 码分量码( g ( d ) = 【1 + d + 3 ，l + d 2 + d 3 】) 的篱笆图。它表示编码状态转移与时间的关系。v a 就是在 篱笆图上寻找一条具有最大“度量”的路径。 ， i _ 。 一生：一二l - 一：1 ”一 ! 一 t | 、j ! 1 io i ， 。| e- | |。| - ；t j | - !。 -， 7 厂7 r7 !。i? i0 70 i0o 。! j 。| 二i 二；。 i； j ，t ，一， 一j 一， 一t j i 图1 6g ( d ) = 【1 + d + j ，i + d 2 + d 3 】的r s c 码的篱笆图 y， ，： 、 7 _ 。_ 一 o一澎jj t b t t t 、 t u r b o 码的s o v a 译码算法在f p g a 中的实现 图1 7 表不的是一个s o v a 算法的例子。为了简化起见，我们考虑篱笆图上 的每一个节点有两个分支，状态数为2 ”，v 为编码器移位寄存器的长度。它以6 为时延进行比特译码，假设6 足够大，使得2 ”条幸存路径以足够大的概率汇聚 予一点。如图1 7 所示，在k 时刻，v a 选择了对应于状态s 。( o s 。s = 2 ”一1 ) 的一条幸存路径，同时还对应着一条待选路径( 竞争路径) ，这两条路径的度 量值为 f n m 。= 争( 一堙) 2 ， m = l ，2( 3 7 ) j v0j = 一占h ；i 其中，甥表示j 时刻第m 条路径的n 个比特中的第n 个比特，表示和堙 在对应位置的接收值，e ，0 是信噪比( s n r ) 。由上式可得 p r o b p a t hm p 一，m = l ，2 ( 3 8 ) 设度量值较小的路径为m = l ，即m ，m ：，这说明v a 选择的幸存路径是路 径1 。那么选择错误的幸存路径的概率为 一者= 南高= 击， ， p “2 硒。再鬲2 百 引 式中，a = m 2 一m ，0 ，p 。代表了传输的不可信度。假设路径l ( 幸存路 径) 与路径2 ( 竞争路径) 的信息比特不相等的位置有e 个， “；”“只 j = ，。，_ ，。， ( 4 0 ) 而“= “j 2 的位置对幸存路径的判决不会产生决定性的影响。假设已存储的 路径1