（微电子学与固体电子学专业论文）高速、低功耗维特比解码器算法研究与电路实现.pdf

摘要 摘要 随着无线通信技术的发展，各种应用标准相继出现，人们对无线通信系统的 要求在不断的提高，希望其提供更高的数据传输速率，同时成本更低，功耗更小。 纠错编解码模块作为无线通信系统的重要组成部分，其硬件实现的复杂度对整个 系统的速度、功耗等都有重要影响。同时，无线信道本身的复杂性也对纠错编解 码性能提出了极高的要求。卷积码和维特比解码算法作为信道纠错编解码方案非 常适用于无线通信衰落信道，广泛应用于各种无线通信系统，如无线局域网 ( w l a n ) ，数字视频广播( d v b ) ，多波段正交频分复用超宽带( - o f d m i ，w b ) 等等。这些高速无线传输系统对维特比解码器的设计提出了挑战，如何 能够以更少的硬件开销和更低的功耗实现符合系统编码增益和速度要求的维特 比解码器一直是研究热点。本文的讨论即围绕着高速无线通信系统这一应用环 境，重点以m o f d m 标准适用的维特比解码器为例，分析如何通过算法和结 构的优化突破维特比解码器的速度瓶颈。 本文介绍了数字通信系统和信道编解码的基本概念，论述了卷积码和维特比 解码的原理，讨论了各种高速维特比解码器的设计方案。针对- o f d mu w b 无线通信系统，本文具体应用了这些设计方法，给出了设计实例，阐述如何根据 系统要求确定维特比解码器的电路结构和重要参数，并最终实现了满足性能指标 的维特比解码器，给出了其测试结果。最后讨论了维特比解码器进一步改进的方 法，包括进一步提高速度，降低功耗的技术。 关键词：前向纠错编码，维特比解码，多波段正交频分复用超宽带 中图分类号：t n 4 9 2 a b s t 髓c t a b s t r a c t w i t i lt i l e i e v e l o p m e n to fw i r e l e s sc o m m u n i c a t i o nt e c h n 0 1 0 9 ya n de m e 鸦e n c eo f v a r i o u sw i r e l e s sa p p i i c a t i o n 咖d a i 出，m ed e m a n df o r 佻t l o w - c o s t 锄dl o w p o w e r 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 si se v e ri n c r e a s i n g a sav i t a lp a r ti nt 1 1 ew i r e l e s s s y s t e m s ，e n d r - c o r r e c t i o nc o d ep l a y sak e yr o l e i ni m p r o v i n gt h es y s t e m so v e r a l l p e r f o m a n c e ，s u c ha ss p e e d ，p o w e r 粕dh 鲫d w a r ec o m p l e x i 妙m o r e o v e r ，m e 眦i q u e c h a r a c t e r i s t i co fw i r e l e s sc h 锄e lp o s e ss 仃i n g e n tr e q u i r e m e n t0 nt h ep 刊b 肋觚c eo f e r r o r - c o r r e c t i o nc o d e c o i l v o l u t i o n a lc o d e s ( c c ) 锄d t e r b ia l g o r i t h m ( v a ) t o g e t h e r a r ev e r ) rs u i t a b l ef o rw i r e l e s sf i a d i n gc h 锄e i sd u et 0t 1 1 e i rh i 曲c o d m g - g a i n 锄d m o i l e r a t eh a r d w a r eo v e r h e a d ，a n da r ew i d e l yu s e di nc o n t e m p o r a d ，w i l - e l e s ss y s t e m s ， s u c ha sw l a n ，d v b ，m b o f d mu w b ，e t c h o w e v e r ，t 1 1 0 s eh i 曲一s p e e dw l e s s c o m 瑚u n i c a t i o ns y s t e m sm a k et h er e a l i z a t i o no fv i t e r b id e c o d e r ( v d ) ac h a l l e n g e s i n c el o wc o m p l e x i 吼l o wp o w e r ，h i 曲c o d i n g - g a ma n dh i 曲s p e e da r er e q u i r e d n i s 廿l e s i sd i s c u s s e st h eo p t i m i z a t i o no fa l g o r i t h r n 锄da r c h i t e c t u r eo fv dt 0 b r e a kt h es p e e db o t t l e n e c k 锄da c h i e v er a q u i r e m e n tp o s e db yt h o s ew i r e l e s s c o 删m u n i c a t i o ns y s t e m s m b o f d mu w bs y s t e m sa r ep a m c u l a r l yd i s c u s s e d 淞锄 e x 锄p l e t h et 1 1 e s i s f i r s ti n 仃0 d u c e sm eb a s i cc o n c c p to fd 垮t a lc o m m u l l i c a t i o n s y s t i m sa n dc h a n n e lc o d e s ，a n dt h e nd i s c u s s e sp r i n c i p i e so fc ca n d1 、7 r a s e v e r a l t e c h n i q u e su s e dt 0r e a l 讫eh i g h s p e e dv d a r cd i s c u s s e di i ld e t a i l a sa ne x 锄p l e ，m e t i l e s i sa p p l i e st h o s et c c h n i q u e st 0 也em b o f d m sv da n ds h o w sh o wt 0c h 0 0 s e s p e c i f i ca r c h i t e c t u r e 锄dp a r a 【r 1 1 e t e r s f i n a l l y ，p o t e n t i a lt e c h n i q u e sw h i c hc 锄b e u s e d t 0m r 吐l e ri m p r o v et t l ev da r ed i s c u s db r i e f l y k e y w o r d ：f o n a r de n 0 rc o n e c t i o n ，t e r b id e c o d e r ，m b o f d m u w b 第1 章引言 第1 章引言 1 1 论文工作的背景 随着无线通信技术的发展，各种无线通信系统相继出现，人们对无线通信系 统的要求在不断提高，希望其提供更高的数据传输速率，成本更低，功耗更小。 不论是在个人应用还是在军事应用中，无线高速数据传输重要性日益凸现；用无 线方式代替传统有线连接，使系统更加方便灵活成为现阶段研究热点。 相比有线信道，无线衰落信道更为复杂，需要更强大的纠错编解码保证系统 能够正常工作。前向纠错编码( f o n a r de n 0 rc o 盯e c t i o n ，f e c ) 是一类能够提高信 道可靠性的码，它通过在发送的数据中增加冗余达到纠错目的。卷积码是f e c 中的一种，配合维特比解码算法( t e r b ia l g o r i t h m ，v 久) ，这一编解码系统非常 适合加性高斯白噪声( a d d i t i v ew h bg a u s s i 锄n o i s e ，a w g n ) 信道，广泛应用于 各种无线通信系统，如无线局域网( w l a n ) ，数字视频广播( d v b ) ，多波段 正交频分复用超宽带( m b o f d mu w b ) 等等。对于m b o f d mu w b 技术， 由于其具有传输速率高、抗多径能力强、功耗低、成本低、穿透能力强、低截获 概率、与现有其他无线通信系统共享频谱等特点，已经成为无线个人域网 ( w 撑烈) 的首选技术。其标准由w i m e d i a 联盟与欧洲计算机制造联盟( e c m a ) 联合制定【l 】。这些高速无线传输系统对维特比解码器的设计提出了挑战，如何 能够以尽可能小的硬件开销和更低的功耗实现符合系统纠错要求的维特比解码 器一直是研究热点。本文的讨论即围绕着高速无线通信系统这一应用环境，重点 以m o f d m 标准适用的维特比解码器为例进行分析。 1 2 论文内容和结构 本文介绍了数字通信系统和信道编码、信道解码的基本概念，论述了卷积编 码和维特比解码的原理，讨论了各种高速维特比解码器的设计方案，并且针对 m o f d mu w b 无线通信系统给出了设计实例，阐述如何确定维特比码器的电 路结构和参数，并最终硬件实现了可以满足性能指标的维特比解码器。 第l 章引言 本文第1 章为引言：第2 章介绍了纠错编码基本原理，包括其分类，在数字 通信系统中的作用和性能评估方法等；第3 章具体介绍了卷积码和维特比解码算 法，证明了维特比算法是卷积码的最大似然解码算法，并讨论了算法在实际硬件 实现时如何优化的问题，之后以一o f d mu w b 通信系统为例，介绍了实际应 用中的卷积码和它的衍生种类凿孔卷积码：第4 章探讨了如何设计一个高速 的维特比解码器，在简要介绍了解码器的基本结构之后，给出了三种适用于高速 解码的结构，并比较了它们的优缺点；第5 章以m b o f d mu w b 通信系统的维 特比解码器为设计目标，阐述了如何根据系统具体要求选择维特比解码器结构， 确定参数，讨论了实现时的一些具体细节问题，给出了其中一种方案的f p g a 实 现结果；第6 章总结了全文，并对将来如何进一步改进维特比解码器，使之速度 更快、功耗更低进行了讨论。 2 第2 章纠错编码基本原理 第2 章纠错编码基本原理 在现实的非理想信道上传输数字化数据时，传输信号将不可避免的受到信道 带来的各种损害，如噪声、干扰和衰落等，严重影响通信系统的性能和可靠性。 为了使发送的数据能够在接收端可靠的恢复，需要使用纠错编码控制通信系统的 误码率。 1 9 4 8 年，克劳德香农( c l a u d es h a 衄o n ) 在其里程碑式的论文【2 】中证明只 要信息传输速率低于信道容量，通过对信息适当进行编码，可以在这一信息传输 速率的情况下，将有噪信道引入的差错减至任意小的程度。自从香农的这一著作 发表以来，人们为了在噪声环境下控制差错而在设计纠错编解码方法方面做了大 量的努力。纠错编码广泛应用在现代通信系统和数字存储系统中，已经成为其不 可分割的一部分。 本章介绍了纠错编码的基本原理，结合数字通信系统讨论了纠错编码的分类 和应用环境，数字通信相关的基本概念，纠错编码解码的准则等，最后讨论了纠 错编码性能的评估和香农给出的性能上界一香农限。 2 1 纠错编码概述及分类 图2 1 是一个基本的数字传输系统框图，目的是将信息从信元传送到信宿。 信源编码器将信源的输出转换为二进制数字信息序列；信道编码器将信息序列 口变换成编码序列_ i ，称为码字( c o d e w o r d ) 。调制器将信道编码器的输出转换 为适合在信道上传输的波形。在典型的无线信道中，波形会受到噪声、多径效应、 多普勒效应和衰落等各种干扰影响，在接收端经解调器处理产生接收序列r 。信 道解码器将接收序列，变换为二进制序列五，作为对发送端信息序列口的估计序 列。这一解码策略基于信道编码规则和信道的传输特性而定。尽管非理想的信道 环境会导致某些解码错误，但在一定的条件下，五将是信息序列的重现。本论 文的主题维特比解码器所采用的维特比算法即为一种解码策略，3 2 1 节将指出 在一定条件下，算法产生的五是接收序列，的最优估计。一般而言，信道解码器 设计的基本要求是( 1 ) 信息在信道解码器的输出端能够可靠的再现；( 2 ) 将编 3 第2 章纠错编码基本原理 图2 - 1 数据传输系统框图 码器和解码器实现的硬件代价降低到可接受的范围内。 信道编码一般分为两大类，即分组码( b i o c kc o d 鹤) 和卷积码( c 佃v o l u t i o n a l d e s ) 。分组码的编码器将信息序列划分成每组含七个信息比特或符号的消息分 组，用二进制七维向量比= 。，坞，“) 表示，总共有2 种可能的不同消 息。信道编码器进而将每个消息距变换成刀维离散符号向量 l ，= ( ，h ，吃，k 。) ，称为码字。消息和码字一一对应，即对于2 种不同消 息，编码器的输出端有2 种可能的不同码字。这2 个长度为，z 的码字的集合即 称为( 刀，七) 分组码。比值r = 七以称为码率。由于栉符号输出码字只取决于对应 的七比特或符号组成的消息分组，即每个消息编码过程是独立的，故编码器是无 记忆的，可用组合逻辑电路直接实现。对于二进制码，码字l ，也是二进制的，应 有七聆，也即码率r l 。则对每个码字而言，刀一七个冗余比特使得该码有纠错 能力。如何选择这些冗余比特以实现非理想信道上的可靠信息传输是设计分组码 类的纠错码的主要问题。 卷积码编码器同样接收后比特分组的消息序列“，并产生咒符号分组的编码 序列 ，。对于二进制编码，则为刀比特分组的编码序列 ，。但与分组码不同的是， 每个编码分组不仅取决于当前单位时间对应的七比特消息，而且与前所个消息组 也有关。参数坍称为编码器的存储级数( m e m o 巧o r d e r ) 。比值r = 七力称为码率。 由于编码器含有存储单元，因而必须用时序逻辑电路实现。图2 - 2 给出了一个 七= l ，刀= 2 ，聊= 2 的二进制前馈卷积码编码器的例子，可以看到其中包含了时 序逻辑元件d 触发器。对卷积码的详细讨论参见3 1 节。 4 第2 章纠错编码基本原理 n 口 固j 日一 。、 图2 2 卷积码编码器实例 a b 2 2 调制与编码 2 2 1 数字带通调制与解调 在图2 1 所示的通信系统中，编码器输出的符号传给调制器，并由调制器选 定一个适于传输的、持续时间为r 的波形，也即带通信号，在发送到信道上进行 传输。如果符号是二进制的0 或l ，则调制器的信号集只需两个信号，即对应于 符号“1 ”的丑( f ) 和对应于符号“0 ”的岛o ) 。选择 删2 謦渤席邝佟2 佟， 删= 序c o s ( 2 确韧) - _ 停c 0 s 2 嗍邝坯丁 其中五为载波信号频率，是基带信号频率l r 的整数倍；b 是每个信号的能量。 则载波的相位随着编码器输出的变化而取0 或万。这种调制称为二进制相移键控 ( b i n a r yp h a s es h i f tk e y i n g ，b p s k ) 。 如果将二进制编码器的输出序列以，比特为一组进行分段，每组为一个符号， 则相应的调制器的信号集需要m = 2 7 个信号，这样就构成了m 进制调制。m 进 制调制的一个例子是m 进制相移键控( m a r yp h a s e s h i f tk e y i n g ，m s k ) ，其信 号集由能量均为乓，相位为m 种等间隔的不同相位的正弦信号构成： 厅 岛) = 、= 孑c o s ( 2 万五f + 磊) ， o f r ( 2 - 2 ) y 上 其中谚= 2 万( f 1 ) m ，l f m 。可见b p s k 是m s k 当m = 2 时的特例。m = 4 时调制通常称为q p s k ( q u a t n t u r ep h a s es h i f tk e y i n g ) 。 由调制器产生的信道信号组成了发送信号s ( f ) ，则接收信号为 ，( f ) = s ( f ) + ，z o ) ( 2 3 ) 第2 章纠错编码基本原理 式中，l ( f ) 代表加性高斯白噪声a w g n ，这种噪声广泛存在于各种通信系统中， 其单边功率谱密度为o 。 图2 1 中解调器处理接收信号，1 0 ) 时须每隔丁秒产生一个符号输出。最优解 调器通常包含一个匹配滤波器或者相干检测器，后面再加一个采样开关，每隔r 秒对滤波器或相干检测器的输出进行采样。如对于式( 2 1 ) 所示的b p s k 调制，其 采样输出为： y = r r ( f ) 等c 。s 2 万五f 出 ( 2 _ 4 ) 一般这一输出为实数值。经量化后成为有限的q 个离散值中的一个，再送入信道 解码器进行处理。 2 2 2 信道模型 如果在给定时间间隔丁内检测器的输出仅和该间隔内传输的信号有关，而与 以前传输的信号无关，则称此信道是无记忆( m e m o 搿l e s s ) 的。这样，m 进制 输入的调制器、物理信道和q 进制输出的解调器三者组合在一起，构成的信道模 型成为离散无记忆信道( 曲c r e t em e m o r y l e 豁c h 粕n e l ，d m c ) 。如图2 3 ( a ) 所示， d m c 可以用一组转移概率尸( 川f ) ( o f m 一1 ，0 ，q 1 ) 完全描述，其中f 代 表调制器输入的符号，代表解调器输出的符号，尸( if ) 是发送为f ，接收为_ ，的 概率。对于m = 2 ，q = 2 ，且噪声的幅值分布对称的情况( 此时 p ( 1o ) = p ( oi1 ) = p ) ，可以得到一种重要的信道模型，即二进制对称信道( b i n a 叮 科m m e t r i cc h a n n e i ，b s c ) ，如图2 3 ( b ) 所示。对于b s c ，转移概率p 一个参数即 可完全描述这个信道。 o 弋s 面 。；：薹 lk 惫补 尸( 9 l l l 卜 2 ，称为软判决( s o f t d e c i s i o n ) 。这样，解码 器必须能够处理多电平的输入，也即相比硬判决，软判决解码器需要处理更多的 信息。软判决为解码器提供了更多的信息用于解码，有助于解码器纠错性能的提 高，但同时解码器的硬件开销也会大大增加。软判决和硬判决在维特比算法和维 特比解码器中的讨论见3 2 2 节。 2 3 最大似然解码 综合以上的讨论，可以给出一个在a w g n 信道上采用d m c 模型的编码系统 框图，如图2 - 4 所示【6 】。由于信源编解码不属于本论文考虑范围，故在图2 3 中 信源和信源编码器合并后整体视为数字信源；信宿和信源解码器合并后整体视为 数字信宿。解调器按最优解调器模型分解为匹配滤波检测器、采样开关和q 电平 量化器。由于，是q 电平量化器的输出，故信道解码器内部首先要根据，选择一 个估计的码字，再根据码字和信息序列一一对应的关系产生对信息序列的估 值蠡。显然，由于信息序列口和码字y 之间一一对应关系，当且仅当参= ，时， 蠡：以，反之若移 ，则会出现解码错误。故选定最优的解码策略使得对每个可能 的接收序列，选择最佳的码字估值移是解码的重要任务。若给定r ，定义解码器 7 警 年 等等 抒茅 第2 章纠错编码基本原理 离散记忆信道 图2 4a w g n 信遭上的通信系统 的条件误码率( c o n d i t i o n a le n o rp r o b a b i l 时) 为： 尸( e i ，) 全尸( 痧 ，ir ) ( 2 - 7 ) 则解码器的误码率为： p ( e ) = p ( e l ，) p ( ，) 7 ( 2 8 ) 其中p ( ，) 为接收序列为，的概率。显然，尸( ，) 与解码策略无关，故使尸( e ) 最小 为目的的最佳解码策略必须使尸( e i ，) = p ( 移 ，i ，) 对所有，为最小。由于 p ( 争yi ，) 最小等价于使p ( p = ，i ，) 最大，因此对于给定的，根据贝叶斯公式， 有 即2 等笋 ， 为最大的参作为码字 ，可使尸( e i ，) 最小，也即在给定，的情况下，要选择最大似 然码字作为参。若所有码字等概出现，则( 2 9 ) 式等价于使户( ，j l ，) 最大。函数 p ( ，i ，) 称为发送码字l ，的似然函数。对于d m c ，其接收向量，中的每个接收符 号只与相应的传输符号有关，则 p ( ，i ，) = 兀p ( i _ ) ( 2 - 1 0 ) 以( 2 1 0 ) 式达到最大作为解码标准的解码器称为最大似然解码器( m a x i m u m i i k e i i h o o dd e c o d e r ) 。在( 2 一l0 ) 式两边取对数，则解码标准等价于最大化对数似然 8 第2 章纠错编码基本原理 函数： l o g 尸( ，ii ，) = l o g 盹l 哆) ( 2 - 1 1 ) 由于乘法转为加法，在硬件实现时采用对数似然函数能够降低硬件复杂度。 b s c 作为d m c 的一个特例，可以进一步讨论如下：此时q = 2 ，是一个二 进制序列，由于信道噪声的影响，会出现v 的情况，其概率为尸( iv ) = p ； 而，；= _ 的概率为尸也lv ，) = 1 一p 。令d ( ，l ，) 表示，和y 之间的汉明距离 ( h a m m i n gd i s t 觚c e ) 。对于长度为玎的分组码( 即汉明距离最大为疗) ，( 2 - 1 1 ) 式 变为 l o g p ( ，ll ，) = d ( ，l ，) l o g p + 【刀一d ( ， ，) 】l o g ( 1 一p ) ：d ( ， ，) l o g 了兰i - + 刀l o g ( 1 一p ) 卜p ( 2 1 2 ) 上式中，刀l o g ( 1 一p ) 是一个常数，p l 2 时，l o g ，l o ，故b s c 下的最 l p 大似然译码原则就是选择使d ( ，l ，) 为最小的参作为码字 ，。因此b s c 下的最大 似然译码器又称为最小距离解码器( m i n i m u md i s t a n c ed e c o d e r ) 。 2 4 有噪信道编码定理 本章开始曾提到香农在论文【2 仲证明了在噪声信道中可靠的传输信息是可 能的。这一结论具体而言是有噪信道编码定理，它指出每个信道都有一个信道容 量c ，对任意满足r c 的速率尺，都存在传输速率为尺的码，用最大似然解码 可以达到任意小的解码误码率尸( e ) 。 对于卷积码，如果其分组长度为门，存储级数m 足够大，则存在这样的卷积 码，使得： 尸( e ) 2 一加1 幢m ( 2 13 ) 对于r c ，e ( r ) 为r 的正函数，且完全由信道特性决定。式( 2 一1 3 ) 说明若r c ， 卷积编码可以通过增加存储级数m 来获得任意低的误码率，也可以通过增大分 组长度力的方式减小码率来获得任意低的误码率。 有噪信道编码定理仅保证了满足式( 2 1 3 ) 的卷积码的存在性，但并没有指出 如何去构造他们。而对于卷积码的解码算法如维特比算法来讲，存储级数小的 9 第2 章纠错编码基本原理 增加将使算法的复杂度以相应的指数级增长，故依靠增加存储级数聊来获得低 误码率是不切实际的。所以在设计纠错编解码系统的同时，既要注意构造出性能 好的码使得式( 2 一1 3 ) 的下界能尽量接近，同时也要注意控制算法的复杂度和相应 的硬件复杂度。对于分组码，也有类似的结论，此处不再讨论。 2 5 纠错编码性能的评估 2 5 1 误码率与编码增益 编码通信系统的性能可以用误码率和编码增益来衡量。 误码率即解码错误的概率。一般使用比特误码率，也即误比特率( b i t e 丌o rr a t e ， b e r ) 来衡量。在一个码率为r = 七丹的编码通信系统中，为传输每个信息比特 所需要传输符号的数目为l r 。若每个传输符号的能量为e 。，则每个信息比特 对应的能量e 为 磊= e r ( 2 1 4 ) 假设信道为单边功率谱密度为o 的a w g n 信道，e 为接收端输入的单位信 息比特能量，则比值毛o 定义为信噪比( s i g l l a l - t 0 - n o i s er a t i o ，s n r ) 。该比值通 常以( 1 b 为单位。b e r - 卧浓曲线图是描述在一定条件下纠错码性能最常见和直 观的方式。 编码增益的定义是指为获得一个特定的误码率，编码系统所需的e 0 比非 编码系统的减少值。在b p s k 调制删g n 信道下，非编码系统的最0 可由式 ( 2 5 ) 计算得到。获得额外的编码增益的代价是更高的解码复杂度。解码器硬件复 杂度的提高所带来的编码增益能使系统其它部分开销相应得到减小，在通信系统 的设计中，两者的权衡十分重要。 2 5 2 香农限 在为差错控制而设计编码通信系统时，总是希望获得特定误码率所需的s n r 值尽量小，也就是使编码系统相对于使用相同调制信号集的非编码系统获得尽可 能大的编码增益。根据香农的有噪信道编码定理，可以推导出一个码率为r 的 编码通信系统达到无误码传输状态所必须的最小s n r 的理论极限。这个理论极 限称为香农限( s h a n n o ni i m i t ) ，它说明对一个码率为尺的编码通信系统，只有 当娜己超过这个极限值时才可能获得无误码传输。只要洲t 高于这个极限值， 无误码传输的编码通信系统必然存在，尽管这个系统可能相当复杂。图2 5 给出 了b p s k 调制和a w g n 信道下码率r 和信噪比e 0 的关系。随着对数字传输 l o 第2 章纠错编码基本原理 可靠性要求的提高和信道纠错编码的不断发展，已经出现了十分逼近香农限的纠 错编解码方案，如t u f b 0 码和低密度奇偶校验( l d p c ) 码等【6 】【8 】。 香农限毛，o ( d b ) 图2 5 码率，香农限的关系 第3 章卷积码和维特比解码算法 第3 章卷积码和维特比解码算法 卷积码( c o n v o l u t i o n “c o d e s ) 和维特比解码器( t c r b id e c 0 d e r ) 作为经典的 信道纠错编解码方案，广泛应用于无线通信系统、深空通信系统、磁存储系统等， 能够提供强大的纠错能力以对抗信道干扰，并具有一定的硬件实现经济性。 o f d m 超宽带无线通信系统选择卷积码作为其信道编码，并通过凿孔 ( p _ u i l c t u r c ) 定义了多种不同码率的凿孔卷积码以适应系统不同速率和编码增益 的要求【l 】。 本章介绍了卷积码和维特比解码算法。3 1 节介绍了卷积码的定义、表示方 法、影响性能的参数等；3 2 节讨论了维特比算法，证明了在一定条件下该算法 是卷积码的最大似然解码方法，并以一个例子说明了该算法的工作步骤，对于影 响性能的一些参数结合仿真结果着重进行了讨论；3 3 节介绍了凿孔卷积码。 3 1 卷积码概述 3 1 1 卷积码的定义 卷积码属于前向纠错( f o r w a r de r r o rc o r r e c t i o n ，f e c ) 信道编码。所谓前向 纠错码是指接收端利用纠错码自身的信息自动纠正检出的错误而不依赖其他信 息。这一纠错策略和自动请求重传( a u t o m a t i cr e p c a tr e q u e s t ，a r q ) 策略相对应。 在2 1 节中已经指出卷积码的编码器有记忆，故在任意时间单元内，编码器 的输出不仅取决于该时刻的输入，也依赖于一定数量的以前的输入。一个存储级 数为脚的卷积码编码器就存储了前所个时间单元的输入信息。对于码率为 r = 七甩的卷积码编码器，信息序列被分成长度为七的分组输入，码字被分成长 为刀的分组输出，如图3 1 所示【1 0 】。 卷积码分为两大类，即前馈卷积码和反馈卷积码。每大类中又可分为系统编 码或非系统编码。图3 1 所示即为一种前馈非系统的卷积码编码器。在实际工程 应用中，七= 1 的前馈非系统卷积码编码器应用十分广泛，此时信息序列不必分 段而可以连续处理。图3 2 所示的卷积码编码器j = 1 ，栉= 2 就是这样的一个例 1 2 第3 章卷积码和维特比解码算法 储存深度所q 址级 ( 分组长度为d 图3 _ 1 前馈非系统卷积码编码器 子。本文以下的内容除非声明，讨论的都是这种特殊的卷积码。对于这一类型的 卷积码，一个重要的参数是约束长度k = 聊+ 1 ，其中朋为存储深度。如图3 2 的卷积码约束长度k 即为3 。 3 1 2 卷积码的表示 卷积码有多种图示方法以利于分析，如连接表示、状态图表示、树图表示和 网格图表示等。 n 。 口 【 d 一7 d 一厂、 a b 图3 - 2k = 3 ，r = k ，n = 1 ：2 的卷积码编码器 1 连接表示 连接表示可直接映射到电路实现，如图3 2 所示。电路由移位寄存器、异或 门组成。这一连接可以用生成多项式( g e n e r a t o rp o l y n o m i a l ) 描述，每个多项式 对应连接图上的一个异或门。多项式有尺项，每个抽头在多项式中占有一项， 其系数是否为o 取决于移位寄存器和异或门之间的连接是否存在。仍以图3 2 为 例，该卷积码的生成多项式为： & ( x ) = l + x + x 2 岛( x ) = l + x 2 ( 3 1 ) 第3 章卷积码和维特比解码算法 另也可以将多项式精简为只保留系数的形式，并在习惯上用8 进制表示。如 = 1 11 2 = 7 l ，= 1 0 1 2 = 5 s 。 2 状态图表示 卷积码编码器是一种带记忆特性的编码器，其输出取决于输入和编码器的状 态，因此可以用分析有限状态机( f i n i t e s t a ：t em a c h i n e ，f s m ) 的状态图来表示编 码器。如图3 3 所示，即为图3 2 所示的卷积码编码器状态图。其具体分析方法 与f s m 的一般分析方法完全一样。 n 【、n 1 l o 图3 3 卷积编码器的状态图表示 3 网格图表示 网格图( 魄l l i sd i a 鼾a m ) 对维特比解码的理解十分重要。网格图纵向代表卷 积码编码器所有可能出现的状态，横向代表时间，可将其视为状态图在时间轴上 的展开( t i m e i n d e x e dv e r s i o no ft h es t a ：t ed i a g r a m ) 。不同时间的状态之间的连线 代表可能出现的状态转移( 也是允许出现的状态转移) 。输入序列进入编码器后 的编码过程在网格图上对应一条确定的状态转移路径( p a t l l ) 。如图3 4 所示为图 3 2 的卷积码编码器对应的网格图。图中状态数为4 ，实线对应编码器输入“0 ” 时可能发生的状态转移，虚线对应编码器输入“l 时可能发生的状态转移。输 入序列1 0 l l o 所产生的输出序列为1 l l o0 00 l0 1 ，对应的路径在图3 4 中用粗箭 头表示。 1 4 第3 章卷积码和维特比解码算法 图3 _ 4 卷积码编码器的网格图表示 3 1 3 卷积码的性能 卷积码的性能取决于自由距离参关于自由距离的相关内容可以参考【6 】 8 】。 卷积码的距离特性和纠错性能需要通过传输函数( n 肌s f e r 龟n c t i o n ) 获得。具体 的方法可以参考【8 】和【1 1 】。基本原则是通过分析卷积码的状态图可以获得传输函 数丁( d ，刀，并可进一步得到在b p s k 调制和a w g n 信道下误比特率的上界。 卷积码的码率r 越低，香农限也越低，可能达到的性能也就越好。在相同的 码率r = 后栉和约束长度足的情况下，卷积码的性能和生成多项式密切相关。好 的卷积码通常通过计算机搜索得到。在 7 】和 8 中可以查到不同码率和约束长度 下最优卷积码的生成多项式。 3 2 维特比算法 3 2 1 卷积码的最大似然解码 1 9 6 7 年，安德鲁维特比( a n d r e w t e 小i ) 提出了一种卷积码的解码算法 【3 【4 】，并被g 福尼( gd f o m e y ) 证明这一算法在一定条件下实际上是卷积 码的最大似然解码算法 5 】，即解码器选择的输出是使接收序列条件概率最大的 码字。该算法从此被称为维特比算法( t e r b ia l g o r i t l l l n ) 。由于该算法相对来说 易于硬件实现，很快成为在实际应用中的卷积码解码首选方案。 在以下假设情况下，可以证明维特比算法是一种最大似然( m a x i m u m l i k e l i h o o d ) 解码算法【6 】： 1 ) 假设传输信道是无记忆信道 2 ) 假设所有可能的码字等概出现 第3 章卷积码和维特比解码算法 3 ) 假设差错概率与发送序列无关 下面给出这一结论的具体说明： 假设一个二进制输入、q 进制输出、信道为d m c 的信道模型，长度为 的 信息序列口= ( ，“) 经码率为l 力的卷积码编码器编码，生成长度为 = 舸( 办+ 朋) 的码字 ，= ( ，一，+ m 。) = ( v 0 ，v l ，v - 。) 。其中的m 为寄存器 存储深度，代表附加在信息序列口之后的，1 个0 ，以使编码器结束编码时回到零 状态。由于编码器一般在开始编码时清零，即在网格图上的路径从零状态开始， 这样以零状态结束，既便于下一次的编码操作，也使解码时能确定码字结束时网 格图上路径的状态。这样，最终码字长度为= ”( 办+ 肌) ，接收到的q 进制序列 为，= 瓴，+ 臃j ) = 瓴，i ，一。) 。正如在2 3 节中讨论的，解码器必须根 据接收序列，产生码字v 的估计痧，d m c 上的最大似然解码器就是选择最大化对 数似然函数l o g 尸( ，ly ) 的痧作为码字。对于d m c ，有 + 册一l一l l o g 尸( ，i ，) = l o g 尸( i 吩) = 1 0 9 尸( 乃l m ) ( 3 - 2 ) ，神，l o 其中p ( 巧l m ) 是信道转移概率。 式中第一项对数似然函数l o g 尸( ，l ，) 称为路径( 码字) ，的路径度量( p a t h m e 埘c ) ，并以m ( ，i ，) 表示。式中第二项1 0 9 尸( i 咋) 称为分支度量( b r a c h m e t r i c ) ，并以m ( l 屹) 表示。式中第三项l o g 尸( 巧lv ，) 为比特度量( b i t m e t r i c ) ， 并以m l b ) 表示。则路径度量m ( ，f v ) 可表示成： ( 3 3 ) 维特比算法即是根据从d m c 接收到的序列，找到通过网格图具有最大度量 的路径，根据式( 3 2 ) 和( 3 3 ) ，这条路径即为所求的最大似然路径。 实际实现该算法时，采用迭代的方式处理接收序列，。在每个时间单元，将2 个分支度量加到它们对应的在前一个时间单元生成并存储的路径度量上( “加” 操作) ，比较进入每一状态的所有2 个路径的度量( “比”操作) ，选择具有最大 度量的路径( “选”操作) ，这些路径称为幸存路径( s u n ，i v o rp a t h ) 。以上三个 操作合称为加比选( a d d 。c o m p a r e s e i e c t ，a c s ) 操作。每个状态对应的幸存路径 被存储下来，因为其对应的码字可能就是解码后的消息序列估计值五。各状态的 路径度量也保存下来以备下一时间单元的操作，前一时间单元的路径度量则可以 抛弃。迭代操作的步骤如下： 1 )时间f - j 时开始解码操作，计算进入每一状态的单个路径的分支度 1 6 崎0 m m m = 咋 ，l m 一枷 = 力p m 第3 章卷积码和维特比解码算法 量并储存。所有路径状态和幸存路径存储器复位清零。 2 )f 增加1 。将进入每个状态的分支度量与前一时间单元该状态的幸存 路径的度量相加，之后对每一状态，比较进入该状态的所有2 路径的度量，选 择具有最大度量的路径成为更新后的幸存路径( 加比选操作) 。存储该路径及其 度量。 3 )如果f 而+ 朋则重复步骤2 ，否则停止。 注意在进行第2 步的操作时，存储的可以是对应于幸存路径的信息序列，这 样当算法结束时，可直接获得估计信息序列詹；也可以是幸存路径每次更新时所 选择的前一时间的状态值，则算法结束时根据这些状态信息可以逆向推出幸存路 径经过的所有状态，称为回溯( t r a c e b a c k ) ，从而得到估计信息序列五。不管哪 种方法，解码算法都是直接得到恢复的估计信息序列五而无需再通过估计的码字 序列移获得。 当迭代进行至时间单元厅后，此时编码器将要回到全零状态，故在网格图上 幸存路径逐渐变少，至时间单元办+ m 时，只有唯一的以零状态为结尾的幸存路 径。显然，这条路径就是最大似然路径，维特比算法总是找到通过网格图的最大 似然路径。在这一意义上它是卷积码的一种最优解码算法。 3 2 2 硬判决和软判决解码 在转移概率p 1 2 的二进制对称信道( b s c ) 的情况下，接收序列，是二进 制的( q = 2 ) ，此时解码器为硬判决解码。( 3 2 ) 式的对数似然函数简化为： l o g 尸( ，iy ) = d ( 厂，y ) l o g _ 卫+ l o g ( 1 一p ) ( 3 4 ) i p 其中d ( ，y ) 为，和y 之间的汉明距离。由于对于所有，l o g l 0 ，故最大似然等价于最大化，l ，也即维特比算法找 到网格中和接收序列相关最大的路径。 从( 3 7 ) 式中间的推导过程也可以看到，若把实数接收序列，和码字v 表示成 n 维欧式空间中的向量，则对于连续输出的a w g n 信道，最大化对数似然函数 等价于找到码字y 使它的欧式距离离接收序列，最近。这也就意味着若采用软判 决将接收序列，量化，则用欧式距离计算分支度量，维特比算法其他部分不变， 就能将算法应用于连续输出的a w g n 信道。在前面我们已经知道，软判决比硬 判决性能上更好，并且理论上可以证明，软判决比硬判决有3 d b 的渐进编码增 益。量化的精度越高，相对硬判决所获得的编码增益也就越高，但硬件的复杂度 也很快增长。图3 5 是约束长度k = 4 ，码率尺= 1 2 的码在不同量化精度下的 性能仿真结果，所用的信道模型为b p s k 调制，a w g n 信道。同时给出了未编 1 8 第3 章卷积码和维特比解码算法 码系统相应的结果，由( 2 5 ) 式给出。可以看到解调器量化为q = 8 级，也即将接 收序列，中的符号量化为3 b i t 时，解码器获得的编码增益与采用不量化的解调器 所获得的编码增益差距在0 2 5 d b 之内；更高的量化级数只能带来很小的性能改 善。故一般软判决维特比解码器采用的量化精度为3 b i t 。 配 b o ( d b ) 图3 - 5 不同量化精度下卷积码性能仿真结果 3 2 3 维特比算法实例 本节以图3 2 所示卷积码编码器生成的卷积码为例，详细讲解维特比算法的 过程。假设输入编码器的序列为0 1 0 1 1 1 0 0 1 0 1 0 0 0 l ，则编码器的输出符号序列为： 0 0l l1 00 00 1 1 00 l1 l 1 1l o0 0l ol l0 0l l1 01 l 其中包括了附加在该序列之后的两个0 以使编码器复位。这一编码过程，可由 3 1 2 中讲到的网格图中的一条路径来表示，如图3 6 所示。 时间o12 345678 状态0 0 状态0 1 状态1 0 状态1 1 编码器输入 编码器输出 o10 111oo1o10oo 1oo 1 1 1 0 们1 00 1”1 0 1 0 1 1”1 01 1 图3 6 对应确定输入序列的网格图中的路径 1 9 第3 章卷积码和维特比解码算法 现在假设由于信道中噪声的影响，解码器接收到的序列为： 0 0l lj jo o0 11 00 11 1 l l1 0o o 口口1 l0 01 11 01 1 其中有2 个符号出现错误，如上面的斜体所示。下面可以看到维特比解码算 法是如何正确地得到输入编码器的原始发送序列。为简单起见，我们使用硬判决 维特比解码，并认为卷积编码器的初始状态为0 0 。 每接收到一个符号，即计算该符号与编码器当时状态下可能出现的符号之间 的汉明距离，即分支度量。比如从t = o 到t = 1 只有两个可能出现的符号：“0 0 ” 或“1 1 。这是因为卷积编码器被初始化到状态o o ，当输入o 或l 时，只有两种 后续状态和对应的两种输出。 在t = 1 时刻，解码器收到的符号为“0