（通信与信息系统专业论文）基于fpga的卷积编码和维特比译码的研究与实现.pdf

摘要 在数字通信中，采用差错控制技术( 纠错码) 是提高信号传输可 靠性的有效手段，并发挥着越来越重要的作用。纠错码主要有分组码 和卷积码两种。在码率和编码器复杂程度相同的情况下，卷积码的性 能优于分组码。 卷积码的译码方法主要有代数译码和概率译码。代数译码是基于 码的代数结构；而概率译码不仅基于码的代数结构，还利用了信道的 统计特性，能充分发挥卷积码的特点，使译码错误概率达到很小。 卷积码译码器的设计是由高性能的复杂译码器开始的，对于概率 译码最初的序列译码，随着译码约束长度的增加，其译码错误概率可达 到非常小。后来慢慢地向低性能的简单译码器演化，对不太长的约束长 度，维特比( v i t e r b i ) 算法是非常实用的。维特比算法是一种最大似然 的译码方法。当编码约束度不太大( 小于等于1 0 ) 或者误码率要求不太 高( 约1 0 。5 ) 时，v i t e r b i 译码算法效率很高，速度很快，译码器也较简 单。 目前，卷积码在数传系统，尤其是在卫星通信、移动通信等领域 已被广泛应用。 本论文对卷积码编码和v i t e r b i 译码的设计原理及其f p g a 实现方 案进行了研究。同时，将交织和解交织技术应用于编码和解码的过程 中。 首先，简要介绍了卷积码的基础知识和维特比译码算法的基本原 理，并对硬判决译码和软判决译码方法进行了比较。其次，讨论了交 织和解交织技术及其在纠错码中的应用。然后，介绍了f p g a 硬件资源 和软件开发环境q u a r t u si i ，包括数字系统的设计方法和设计规则。 再有，对基于f p g a 的维特比译码器各个模块和相应算法实现、优化进 行了研究。最后，在q u a r t u si i 平台上对硬判决译码和软判决译码以 及有无交织等不同情况进行了仿真，并根据仿真结果分析了维特比译 码器的性能。 分析结果表明，系统的误码率达到了设计要求，从而验证了译码 器设计的可靠性，所设计基于f p g a 的并行v i t e r b i 译码器适用于高速 数据传输的场合。 关键词：数字通信，卷积码，维特比算法，交织和解交织，现场 可编程门阵列 a b s t r a c t i nt h e d i g i t a lc o m m u n i c a t i o n ，e r r o r c o n t r o l c o d i n g ( e r r o r c o r r e c t i n gc o d i n g ) i sa ne f f e c t i v em e t h o dt oi m p r o v er e l i a b i l i t yo fs i g n a l t r a n s m i t t i n g ，a n di t sa c t i o ni sm o r ea n dm o r ei m p o r t a n t e r r o rc o r r e c t i n g c o d e m a i n l y i n c l u d e sb l o c kc o d ea n dc o n v o l u t i o n a lc o d e t h e p e r f o r m a n c eo fc o n v o l u t i o n a lc o d ei ss u p e r i o rt ob l o c kc o d ei ft h e i r c o r r e s p o n d i n ge n c o d e r sa r et h es a m ec o m p l i c a t e dd e g r e e a l g e b r a i cd e c o d i n ga n dp r o b a b i l i s t i cd e c o d i n ga r ec h i e f l ym e t h o d f o rc o n v o l u t i o n a l d e c o d i n g ，a l g e b r a i cd e c o d i n g i sb a s e do nt h e a l g e b r a i cs t r u c t u r eo fc o n v o l u t i o n a lc o d e ，b u tp r o b a b i l i s t i cd e c o d i n gi s b a s e do nn o to n l yt h ea l g e b r a i cs t r u c t u r eo fc o n v o l u t i o n a lc o d e ，b u ta l s o t h es t a t i s t i c sc h a r a c t e r i s t i c so fs i g n a lc h a n n e l ，i t ss p e c i a l l yc h a r a c t e r i s t i sd r a w no u t ，s oe r r o rp r o b a b i l i t yf o rd e c o d i n gi sv e r yl o w t h ed e s i g no fc o n v o l u t i o n a lc o d ed e c o d e rb e g a nf r o mh i g h p e r f o r m a n c ea n dc o m p l i c a t e dd e c o d e r ，f o rt h ef i r s ts e q u e n c ed e c o d i n g ， i t se r r o rp r o b a b i l i t yf o rd e c o d i n gw o u l db ev e r yl o ww h e nc o n s t r a i n t l e n g t hi si n c r e a s e d l a t e r ，t h ed e c o d ed e v e l o p e ds l o w l yt o w a r d st ol o w p e r f o r m a n c ea n ds i m p l ed e c o d e r ，v i t e r b ia l g o r i t h mi sv e r yu t i l i t yf o r s h o r tc o n s t r a i n t l e n g t h v i t e r b ia l g o r i t h m i sam a x i m u n l i k e h o o d d e c o d i n g m e t h o d w h e nc o n s t r a i n t l e n g t h i sn o t l o n g ( 10 ) o r r e q u i r e m e n tf o rb i te r r o rr a t e i sn o th i g h ( a b o u t10o ) ，a l g o r i t h mf o r v i t e r b id e c o d i n gi s h i g he f f i c i e n c ya n df a s ts p e e d ，a n dt h ed e c o d e ri s a l s os i m p l e d e s i g nf o re n c o d e ra n dd e c o d e ro fc o n v o l u t i o n a lc o d e si si n t r o d u c e d i n t h i s p a p e r a tt h es a m et i m e ，r e a l i z a b l e s c h e m ew i t hf p g ai s r e s e a r c h e d t e c h n o l o g yo fi n t e r l e a v ea n dd e i n t e r l e a v ei sa p p l i e di nt h e p r o c e d u r eo fc o d i n ga n dd e c o d i n g i nt h ef i s tp l a c e ，t h ea b co fc o n v o l u t i o n a lc o d e sa n dt h eb a s i c p r i n c i p i u mo fa l g o r i t h mf o rv i t e r b id e c o d i n gi sb r i e f l yi n t r o d u c e d ，a n d t h ed i f f e r e n c eb e t w e e nh a r d - d e c i s i o na n ds o f t - d e c i s i o ni sa n a l y z e d t h e n e x ti no r d e r ，t e c h n o l o g yo fi n t e r l e a v ea n dd e i n t e r l e a v e ，i n c l u d i n gi t s a p p l i c a t i o ni ne r r o rc o n t r o lc o d i n g 。t h e3 t h ，a p p l i c a t i o nf p g a ，t h e h a r d w a r er e s o u r c e ，a n dq u a r t u si i ，t h es o f to fd e v e l o p m e n t e n v i r o n m e n ta r ei n t r o d u c e d ，i n c l u d i n gt h ed e s i g n i n gm e t h o da n dt h e d e s i g n i n gr u l eo fd i g i t a ls y s t e m t h e4 t h ，e n e o d e ra n de a c hm o d u l eo f v i t e r b id e c o d e ri s d e s i g n e da n dc o r r e s p o n d i n gd e c o d i n ga l g o r i t h mi s a p p l i e d ，t h ea l g o r i t h m i sr e a l i z e dw i t hf p g a a tl a s t ，e n c o d e r ， h a r d d e c i s i o nd e c o d i n ga n ds o f t - d e c i s i o nd e c o d i n g ，t h eu s a g eo f i n t e r l e a v e a n dd e i n t e r l e a v ea r es i m u l a t e di nq u a r t u si i ，t h e nt h e f u n c t i o no fv i t e r b ie n c o d e ri sa n a l y z e da c c o r d i n gt ot h er e s u l to f s i m u l a t i o n t h er e s u l to fa n a l y s i sd e n o m i n a t et h a tb i te r r o rr a t eo fs y s t e mh a s a c h i e v et h er e q u i r e m e n to fd e s i g n ，a n dt h ei m p l e m e n t a t i o no fd e s i g nf o r d e c o d e ri sv e r i f i e d ，p a r a l l e lv i t e r b id e c o d e rd e s i g n e dw i t hf p g ai sf i t t e d f o rh i g hs p e e dd a t at r a n s m i s s i o n k e y w o r d s ：d i g i t a lc o m m u n i c a t i o n ，c o n v o l u t i o n a lc o d e s ，v i t e r b i a l g o r i t h m ，i n t e r l e a v ea n dd e i n t e r l e a v e ，f p g a 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得叁鲞盘 里l 或其他教育机构的学位或证书而使用过的材料。与我一同2 1 2 作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 繇施一期：一产，日 学位论文版权使用授权书 本学位论文作者完全了解墨叠盘堂有关保留、使用学位论文 的规定。特授权苤鲞盘堂可以将学位论文的全部或部分内容编入有 关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编 以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件 和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 文作：魂啼弘新繇列前臂 擀醐：1 “肌日解聃一净j l 曰 e j ? 嘉e 第一章绪论 1 1 引言 第一章绪论 随着现代通信技术的发展，高速传输和高可靠性成为信息传输的 两个主要方面，而可靠性尤为重要。信息在实际信道中传输时，信道 特性的不理想、加性噪声和人为干扰等因素的影响，都会使系统接收 的信息不可避免地出现差错。为降低误码率，实现可靠性通信，通常 采用的途径有两种：一种是通过选择高质量的传输线路、改善信道的 传输特性、增加发送信号的功率、选择有较强抗干扰能力的调制解调 方式等，来降低信道本身引起的误码；另一种是通过信道编码对信道 差错进行控制。许多情况下，前者常常会受条件的限制，不是所有情 况都能采用，而信道差错控制编码则可以弥补前者的不足【l 】。 纠错编码的基本实现方法是在发送端将被传输的信息附上一些监 督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联 ( 约束) 。接收端则根据既定的规则校验信息码元与监督码元之间的关 系。一旦传输发生差错，则信息码元与监督码元的关系就受到破坏， 从而在接收端可以发现错误乃至纠正错误。 1 2 纠错码的应用和发展 在实际传输信息时，如果由于信道传输特性、加性噪声和人为干 扰等因素的影响而使接收到的信息出现差错，那么为了使系统能够达 到一定的误比特率，可以通过合理设计基带信号，选择调制、解调方 式，采用频域均衡或时域均衡等手段，使误比特率尽可能降低。但如 果误比特率仍达不到要求，那么必须通过信道编码即纠错编码来进一 步降低误比特率。由于信道编码可以使传输质量提高1 2 个数量级或 更多，所以在现代通信系统中，信道编码已经成为系统重要的组成部 分，对提高整个系统的传输性能起着重要的作用。 1 9 4 8 年，香农( s h a n n o n ) 在他的开创性论文“通信的数学理论 中， 首次阐明了在有扰信道中实现可靠通信的方法，提出了著名的有扰信 道编码定理：对于一个给定的有扰信道，若信道容量为c ，只要发送端 以低于c 的速率r 发送信息，则一定存在一种编码方法，使译码错误概 第一章绪论 率p 。随着码长玎的增加，按指数下降到任意小的值【2 】，可表示为： 只e 嵋( 置) ( 1 1 ) 式中：e ( r ) 为误差指数，其大小与胄和c 有关。 有扰信道编码定理奠定了纠错码的基石。近几十年发展起来的差 错控制技术都是基于这一定理而产生的。 目前，各种纠错码如循环码、b c h 码、r s 码、l d p c 码以及调制 与纠错码相结合的t c m 码等都得到很好的研究、发展和应用，可以说 纠错码已渗透到很多领域。在移动通信中，纠错码被广泛用于模拟体 制的信令传输及数字体制的整个传输，以提高传输的可靠性和节省宝 贵的频谱资源；在卫星通信中，纠错码技术已成为降低对高功放的要 求和减少地球站天线孔径尺寸的经济且可靠的方法；在电话网上的数 据传输中，纠错码技术己成为将高速数据传输变成现实的关键技术； 在计算机存贮和运算系统中，也广泛应用了纠错码技术。此外，在超 大规模集成电路设计中采用纠错码技术后，大大提高了集成电路芯片 的成品率，同时又降低了芯片成本。 由信道编码理论可知，随着码长刀的增加，译码错误概率按指数方 式趋近于零。因此为提高纠错码有效性，就必须使用长码。但码长增 加，码率会相应下降，译码设备复杂性与计算量也相应增加，以致难 以实现。要解决这一矛盾，可采用级联码的方法。级联码一般由内码 和外码两级组成。内码既可以用作纯纠错，也可以用做纠错与检错。 但一般情况下，级联码被用在组合信道中，内码中出现的错误往往超 过了内码的纠错能力。所以，内码通常仅用来纠正少量错误，其主要 能力用来检错，指出错误位置；纠错任务则由外码译码器完成。这样 两级译码的结果，得到了好的纠错效果，还使得内外译码器均较简单， 内译码器是检错译码器，外译码器是纠错译码器【3 j 。 t u r b o 码是由c b e r r o n 等人在1 9 9 3 年提出的接近香农极限的一种 并行级联码，是在综合几十年来级联码、乘积码、最大后验概率译码 及迭代译码等理论基础上的一种创新。其基本原理是通过编码器的巧 妙构造，即多个子码通过交织器进行并行或串行级联( p c c s c c ) ，然 后进行迭代译码，从而获得卓越的纠错性能。t u r b o 码不但在抑制加性 高斯噪声方面性能优越，而且还具有很强的抗衰落、抗干扰能力。在 低于香农极限0 7 d b 的情况下，可以得到1 0 5 的误码率。正是由于t u r b o 码超乎寻常的性能，使得它的一经出现就立即引起编码学界的极大轰 动，围绕t u r b o 码的研究也成了通信系统中的个热点【2 1 。 第一章绪论 随着近年来电子技术和集成电路技术的发展，纠错编码技术不但 早已应用于实际的通信设备之中，而且不断的有更高性能、更低功耗 的译码器出现。正是这种实际应用与纠错码理论研究的相互促进，使 得纠错编码技术不断呈现出蓬勃向上的活力。 1 3 本课题的研究意义 进行信道编码时，可采用多种纠错码。其中卷积码和分组码是纠 错码的两种主要形式，在码率和编码器复杂程度相同的情况下，卷积 码的性能要优于分组码，而且更易于实现最佳译码和准最佳译码。由 于卷积码的优异性能，使得它在很多方面都得到了应用。 由于卷积码各码组之间的相互关联，在对卷积码的分析时，至今 未找到像分组码那样严密的数学分析手段，因此对卷积码的性能分析 比较困难，e t 前大多是通过计算机进行好码的搜索。卷积码的译码也 较分组码容易，可有两大类译码方法：代数译码和概率译码。在概率 译码中，维特比译码算法是一种最大似然算法，在码的约束度较小时， 其效率比序列译码算法更高、速度更快，译码器也较之更为简单。所 以，自维特比译码算法提出以来，在理论和实践方面都得到了极其迅 速的发展，被广泛地应用于各种数传系统【2 j 。 在现代通信系统中，通信技术的发展使图像、语音、数据、视频 等多种业务的复用成为可能，但这对数据的传输速率和系统的处理速 度要求会越来越高，为了实现数据的实时传输，就必须有高速处理信 息的能力。通常，数字信号处理芯片是一种软件工作方式，很难满足 高速处理的要求，因此必须通过硬件方式才能实现。微电子技术的发 展，使系统设计可以根据需要来设计专用集成电路( a s i c ) 芯片，为了 使a s i c 的设计周期缩短，人们希望最好在实验室就能设计出合适的 a s i c 芯片，并且立即投入到实际应用中。现场可编程逻辑器件( f p g a ) 的出现使这一设想成为可能。1 9 8 5 年，自x i l i n x 公司推出f p g a 至今， 已经历了十几年的发展历史，占据了巨大的市场，部分替代了a s i c 。 其原因在于f p g a 不仅解决了电路系统小型化、低功耗、高可靠性等问 题，而且其开发周期短、开发软件投入少、芯片价格不断降低，特别 是对小批量、多品种的产品需求，使f p g a 成为首选【4 】。随着现代e d a 技术的发展，借助高性能e d a 软件的辅助设计，可以使设计人员更能 集中精力进行电路设计，快速将产品推向市场。 第一章绪论 本文中，v i t e r b i 译码器的设计采用了基于f p g a 的现代e d a 技 术，使设计出来的v it e r b i 译码器有更高的可靠性。有了高性能的硬 件资源，还要配置优化的译码算法，无论译码器可靠性，还是其工作 的效率，或是硬件资源的利用率，都与译码算法有很大的关系。本文 采用的是一种并行的v i t e r b i 译码算法，通过截尾译码、寄存器交换 等技术来降低系统开销，减小时延时间，提高资源利用率，再加以交 织和解交织技术来提高y i t e r b i 译码器的纠正突发错误的能力。 1 4 本论文的章节安排 第一章简要介绍纠错编码的应用和发展，对本课题研究的现实意 义进行了简要阐述。 第二章首先介绍了与卷积码有关的基本概念，同时对与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 i t e r b i 译码的性能要优于硬判决译码，对 此也进行了介绍和比较。 第四章简要介绍交织和解交织技术，重点介绍了行列交织器和解交 织器的原理及应用。 第五章首先对可编程逻辑器件和e d a 技术设计数字系统的方法与 规则进行了介绍，包括硬件描述语言及其软件开发平台q u a r t u si i ； 然后介绍了利用f p g a 实现卷积码编码器；最后，重点介绍了构成硬判 决和软判决v i t e r b i 译码器的各功能模块的设计与实现，并分析了在实 现v i t e r b i 译码器过程中存在的问题。 第六章通过对硬判决和软判决v i t e r b i 译码器的仿真，分析了各自 的性能特点，并在此基础上对硬判决译码和软判决译码的性能进行了 比较。 1 5 本章小结 本章首先介绍了纠错码的应用和发展情况以及对本课题研究的意 义，然后介绍了本论文的主要工作和基本框架。 第二章卷积码的基础知识 第二章卷积码的基础知识 卷积码是e l i a s 在l9 5 5 年提出的。在分组码中，把k 个信息比特 序列编成行个比特的码组，每个码组中的( 刀七) 个校验位仅与本码组 的k 个信息位有关，而与其它码组无关。为了达到一定的纠错能力和 编码效率，分组码的码组长度一般比较大。编译码时必须把整个信息 码组存储起来，由此产生的译码延迟会随着刀的增加而增加。和分组 码不同，卷积码前后各码组之间具有相关性，即卷积码编码后的刀个 码元不仅与当前段的k 个信息有关，而且还与前面( n 1 ) ( 为编码 约束度) 段的信息有关。在卷积码中，k 个信息比特也被编成力个比特 的码组，但k 和刀通常很小，并且可以通过串行或并行的方式进行传 输，而且时延很小。编码过程中互相关联的码元个数为n n 。 由于卷积码在编码过程中，充分地利用了各码组之间的相关性， 且k 和以都比较小，因此，在与分组码同样的码率和设备复杂性条件下， 从理论和实际两个方面，均已证明卷积码的性能至少不比分组码差， 且实现最佳和准最佳也较分组码容易【2 】。但卷积码没有分组码那样严 密的数学分析手段，目前，好的卷积码大多是通过计算机进行搜索得 到的。 2 1 卷积码的基本概念 卷积码编码器如图2 1 所示。 图2 - 1码率为k n ，编码约束度为n 的卷积码编码器 图2 1 主要包括：一个输入移位寄存器( 分为段，每段k 位) ；刀 个模2 加法器；一个输出数据选择器( 刀选一) 。某一时刻，输入到编 码器的k 个信息元组成一个信息组，相应的输出序列是由刀个码元组 第二章卷积码的基础知识 成的码段。这里，称为编码约束度，说明编码过程中互相约束的码 段个数。令n = m + l ，则m 称为编码存储，它表示输入信息组在编码器 中需存储的单位时间( 有时为了简化，编码器中只用m 段的输入移位 寄存器) 。称n n 为编码约束长度，说明编码过程中互相约束的码元个 数，如m = 2 ，n = 2 ，则n n = 6 。所以m 或以及n n 都是表示卷积码编 码器复杂性的重要参数。 同样，在卷积码译码过程中，不仅要根据此时刻输入到译码器的码 元，而且还要根据以后很长一段时间如m j ( 通常m ，m ) 段单位时间 内收到的码元，才能译出一个信息元。称所d + 1 = d 为译码约束度，称 n n d 为译码约束长度，它们分别表示译码过程中互相约束的码段或码元 个数。总之，在卷积码的各码段之间，不论是编码还是译码都不是每 段各自处理，而是与前m 或m d 段有关。所以，卷积码通常用( r t ，k ，m ) 或( n n ，踟表示。令r = k n ，则称尺为卷积码的码率，码率是衡量卷积 码传输信息有效性的一个重要参数。 2 2 卷积码的表示方法 卷积码的表示方法主要有多项式矩阵表示法、状态图表示法和网格 图表示法。其中，多项式矩阵表示法主要用于代数译码，而v i t e r b i 译 码算法主要采用后面两种方法来表示。下面以( 2 ，1 ，2 ) 码为例来介 绍状态图表示法和网格图表示法。 设( 2 ，l ，2 ) 码的两个子生成元为： g ( 1 ，1 ( d ) = l + d + d 2 ( 2 1 ) g ( d ) = 1 + d 2 ( 2 - 2 ) 所以，该码的生成多项式矩阵为： g ( d ) = 【l + d + d 2 ，l + d 2 】 ( 2 - 3 ) 根据g ( d ) 可得如图2 2 所示的编码电路。 图2 - 2 ( 2 ，l ，2 ) 卷积码编辑器 第二章卷积码的基础知识 2 2 1 状态图表示法 图2 3 为图2 2 所示卷积码编码器的状态图。编码器的寄存器在任 一时刻的所存储的内容称为编码器的一个状态，以s ，表示。本例中，编 码存储m = 2 ，k = - i ，编码器由两级移位 寄存器构成，所以，移位寄存器所存 储的内容只有四种情况：0 0 、1 0 、0 1 和11 ，这就是说本例中的编码器共有 四种状态：s ”s 1 、s 2 和s 3 。随着信息 序列不断送入，编码器会不断地从一 个状态转移到另一个状态。利用状态 转移路径不但可以表示出该转移过程 中所对应的输出码段，同时还可以显 示所对应的输入信息元。 虽然状态图能够表示卷积码编码 器在不同输入的信息序列下，编码器 各状态之间的转移转移关系，但却不 图2 - 3( 2 ，1 ，2 ) 卷积码编码器状态图 能描述随时间变化时系统状态转移的轨迹，为了解决这个问题，可引 入下面要介绍的网格图表示法。 2 2 2 网格图表示法 、麓 图2 - 4( 2 ，1 ，2 ) 码l = 5 时的网格图 图2 2 所示的卷积码编码器在l - - 5 ( 信息元的长度) 时的网格图如 图2 - 4 所示。在网格图中，一个节点代表着某个时间点上的状态，节 点之间的连线( 分支) 则代表状态之间的转移。图2 4 中共有l + m + l 第二章卷积码的基础知识 个时间单位( 节点) ，用0 到三+ 坍予以标号。 若编码器从5 0 ( 0 0 ) 状态开始，并结束于j o 状态，则最先的m = 2 个时间单位( 0 、1 ) ，相应于编码器由s o 状态出发向各个状态转移，而 最后m - - 2 个时间单位( 6 、7 ) ，相应子编码器由各个状态返回s o 状态。 因而，在开始和最后的m 个时间单位，编码器不可能处于任意状态中， 而只能处于某些特定状态( 如s o 、s 1 ) 之一，只是从第m ( 2 ) 到第l ( 5 ) 时间单位，编码器可以处于任何状态之中( 即4 个状态s o 、s l 、s 2 、 j 3 中的任意一个) 。 编码器从全0 状态s o 出发，最后又回到s o 状态时所输出的码序列成 为结尾卷积码序列。所以，当送完l 段信息序列后，还必须向编码器再 输入m 段全0 序列，迫使编码器最终回到s o 状态。 网格图中的每一状态都有两个输入和两个输出分支。在某一时间 单位( 节点) i ，离开该状态的虚线分支，表示输入编码器中的信息码 段为l ；而实线则表示输入至编码器的信息码段为0 ；每个分支上的2 ( 以) 个数字，表示第i 时刻编码器输出的码段。网格图中的每一条路 径都对应不同输入的信息序列，如果所有可能输入的信息序列共有2 址， 那么网格图中可能有的路径也有2 址，相应于2 虹个长为- ( l + m ) n 的 不同序列。 从第m ( 2 ) 时间单位开始，某一时间单位f 的状态都是在前一时间 单位f 1 两个状态的基础上，输入相同信息码段来得到的。前一时间单 位f 1 的两个状态可以通过将澄f 问单位的状态s ，左移一位后得到，或左 移一位后加2 扣1 得到。以图2 4 所示的网格图为例，图中的状态s 2 、s 3 就是由前一时间单位的状态s1 和j 1 7 在输入信息元“0 和“1 后得到 的。将s1 、s 17 与s 2 、s 3 的关系可表示为图2 5 所示。 图2 - 5 状态j2 、53 的碟形图 图2 5 被称之为碟形图，它不但能够反映出某一状态和前一单位 时间的两个状态之间的关系，同时还能显示在状态转换过程中输入信 第二章卷积码的基础知识 息元( 码段) 及相应的输出码段。碟形图对于构造维特比译码器起着 关键的作用。 2 3 本章小结 本章通过介绍卷积码的一些基本概念，为进一步更好地学习和应 用卷积码打下了基础。另外，还介绍与概率译码相关的卷积码的表示 方法，尤其是网格图表示法，对维特比译码器的设计与实现有很好的 帮助。 第三章维特比译码算法 第三章维特比译码算法 卷积码译码可分为代数译码和概率译码两大类。代数译码方法完 全依赖于卷积码的代数结构，主要的方法是大数逻辑译码。而概率译 码不仅利用了码的代数结构，而且还利用了信道的统计特性。1 9 6 1 年 乌层格莱夫( w o z e n e r a f t ) 提出的序列译码是最早的具有实用价值的卷 积码的概率译码方法。1 9 6 3 年费诺( f a n o ) 对序列译码进行改进后又 提出了f a n o 算法。推动了序列码的实际应用。1 9 6 7 年维特比( v t e r b i ) 又提出了另一种概率译码算法一v i t e r b i 算法，v i t e r b i 算法是利用码的网 格( t r e l l i s ) 图而进行的一种最大似然译码算法，也是一种最佳的概率译 码方法。它在卷积码的约束长度较小时，比序列译码方法效率更高， 速度更快，译码器也比较简单，是一种非常有效的译码方法i s 。目前， 维特比译码方法己广泛的应用在各种数字通信系统中，本文使用的译 码方法就是维特比译码。 3 1 最大似然译码 由于v i t e r b i 算法是一种最大似然译码算法，因此这里先介绍最大 似然译码的原理。 图3 1 所示为卷积码编、译码系统模型。其中，长度为k 的二进 制( 或巧进制，这里以二进制为例) 序列信息序列肘经过卷积码编码 器后变成长度为玎的发送序列c ，然后发送序列c 被送入有噪声的离 散无记忆信道( d m c ) 。在接收端，译码器根据一套译码规则，由接收 序列r 给出与发送 的信息序列m 最 接近( 或相同) 的 估值序列厨。由于 m 与码字c 之间存 在一一对应关系， 所以就这等价于译 图3 1卷积码编、译码系统模型 码器根据r 产生一个c 的估值序列仑。当且仅当d = c 时，译码器正确 译码。如果译码器输出的e c ，则说明译码器产生了错误译码。 当给定接收序列r 时，译码器的条件译码错误概率定义为， 第三章维特比译码算法 所以译码器的错误译码概率： p f e r ) = p c * c l r ) ( 3 1 ) 足= p ( 尺) 尸( 申) ( 3 2 ) 胄 式中户俾) 是接收序列r 的概率，它与译码算法无关。所以使译码错误 概率最小的最佳译码规则是 面n 最= m i n p ( r ) p ( e i r ) ( 3 3 ) r 这等价于对所有的r 均有 m i n 最- - m ；m p ( q r ) = m j m p c * c l r ) 又 m i n ? c , c l r ) = m a x p c = c l r ) ( 3 4 ) ( 3 5 ) 因此，对于译码器输入的尺，如果能在2 个码字中选择一个使 p ( e f = c r ) 最大nn ng , c j ( f = l ，2 ，3 ，2 毒) 作为c s j 估值序列e ，则 这种译码规则一定使译码器输出错误概率最小。采用这种译码规则的 译码为最大后验概率译码。 由贝叶斯公式 酬舻警 可知，如果发端发送每个码字的概率p ( c ) 均相同， 方法无关，那么 m a x p ( c i r ) ：，m a x p ( r l c i ) 对于d m c ，有 ( 3 6 ) 且由于p ( r ) 与译码 ( 3 7 ) 尸( 尺i c i ) = 兀尸( ，；b ) ( 3 8 ) j = i 式中c 耖是码字c ，的第j 个分量，r i 是r 的第f 个分量。如果按照译码 器的译码规则能在2 个码字c 中选择出一个使式( 3 - 7 ) 最大c ，那么 这种译码规则称为最大似然译码( m l d ) ，称p ( rlc ) n 似然函数，相 第三章维特比译码算法 应的译码器称为最大似然译码器。 由于l o g b x 是x 的单调函数，所以上式可写成 j l ，曼冀1 0 9 ap ( r i c , ) = ，爨跫；1 0 9 。p ( r , l c , j ) ( 3 - 9 ) 式中l o g b p ( rc ) 为对数似然函数或似然函数。对于d m c 信道，m l d 是使译码错误概率最小的一种最佳译码准则或方法。通常用对数似然 函数比较方便，这是因为对数函数是非降函数，取对数前后所得结果 的大小趋势不变，且对数似然函数对所收到的符号具有相加性，因此， 最大似然译码可看成是对所给定的接收序列求其对数似然函数的累加 值为最大的路径。 综上所述，m l d 就是根据接收到的尺，在2 七个码字集中寻找与尺之 间距离最小的码字c ，并将其作为最可能发送的码字而接收。通常把 可能的译码序列与接收序列之间的距离称为度量值。 3 2 维特比算法的基本原理 ( 甩，k ，历) 卷积码编码器共有2 翩个状态，若输入的信息序列的长度 是三七十i n k ( 后m k 个码元全为o ) ，则进入和离开每一状态各有2 条分 支，在网格图上共有2 肛条不同的路径，相应于编码器输出的2 虹个码序 列。 编码器送出的信息码序列c ，在经过d m c 传输后被送入译码器的 是序列r = c + e ，其中e 是信道错误序列。译码器根据接收序列尺，按 最大似然译码准则力图寻找编码器在网格图上所走过的路径，这个过 程就是译码计算、寻找最大似然函数 m a x l 0 9 6 p ( r i c j )产1 ，2 ，3 ，2 t 匝 ( 3 1 0 ) 的过程，或者说译码器计算、寻找有最大“度量 的路径过程，即寻 找 峄m ( r b ) 产1 ，2 3 ，2 乜 ( 3 1 1 ) 的过程。式中，m a x m 1 0 3 0 个码序列( 或网格图上的路径) ；若m = 5 ，则( + 渐) = 5 5 。 如果在一秒钟内送出这k l = l0 0 个信息元，则信息传输率只有1 0 0 b i t s 。 但即使是在如此低的信息速率下，也要求译码器在一秒钟内计算、比 较1 0 3 0 个似然函数( 或汉明距离、软距离) ，也就是要求译码器计算每 个似然函数的时间应小于l0 3 0 s ，很显然这是无法实现的。更何况通常 情况下三不是几十，而是成百上千。因此，必须寻找新的最大似然译码 算法。 v i t e r b i 算法就是在解决上述困难中而引入的一种最大似然译码算 法。这种算法并不是在网格图上一次比较所有可能的2 址条路径( 序列) ， 而是接收一段，计算、比较一段，选择一段最可能的码段( 分支) ，从而 达到整个码序列是一个有最大似然函数的序列。v i t e r b i 算法的步骤如 下： 1 从某一时间单位j = m 开始，对进入每一状态的所有长为，段分 支的部分路径计算其相应的度量。对每一状态，挑选并存储一条有最 大度量的部分路径及其部分度量值，称此部分路径为幸存路径。 2 ，增加l ，把此时刻进入每一状态的所有分支度量，和与这些分 支相连的前一时刻的幸存路径的度量相加，即可得到此时刻进入每一 状态的幸存路径，对幸存路径及其度量值加以储存后，幸存路径就又 延长了一个分支。 3 若j l + m ，则重复以上各步，否则停止，译码器可得到有最大 路径度量的路径。 从时间单位m 直至l ，网格图中2 加个状态中的每一个状态都有一 条幸存路径，共有2 h 条。但在三时间单位( 节点) 后，网格图上的状 第三章维特比译码算法 态数目逐渐减少，幸存路径也相应减少。最后到第l + m 单位时间，网 格图归到全为0 的状态，因此仅剩下一条幸存路径。这条路径就是要 找的具有最大似然函数的路径，也就是译码器输出的估值序列e 。由 此可知，在网格图上用v i t e r b i 译码算法得到的路径一定是一条最大似 然路径，因而这种方法是最佳的。 一 3 3 硬判决译码和软判决译码 所谓硬判决是指解调器根据其判决门限对接收到的信号波形直接 进行判决后输出0 或1 。换句话说，就是解调器供给译码器作为译码用 的每个码元只取0 或l 两个值。而软判决则是指解调器不进行判决， 而是直接输出模拟量，或是将解调器输出波形进行多电平量化( 不是 简单的0 、1 两电平量化) ，然后送往译码器。即编码信道的输出是没 有经过判决的“软信息。 与硬判决算法相比，软判决译码算法的路径度量采用“软距离 而不是汉明距离。最常采用的是欧几里德距离，也就是接收波形与可 能的发送波形之间的几何距离。在采用软距离的情况下，路径度量的 值是模拟量，需要经过一些处理以便于相加和比较。因此，使计算复 杂度有所提高。除了路径度量以外，软判决算法与硬判决算法在结构 和过程上完全相同。一般而言，由于硬判决译码的判决过程损失了信 道信息，软判决译码比硬判决译码性能上要好约2 d b 【5 j 。 下面在硬判决和软判决概念的基础上，介绍有关硬判决和软判决 的基本原理。 设在数字通信系统中采用b p s k 的调制方式，即用 而( f ) = 4 2 e c o s ( 6 t + z r 2 ) ( 3 - 1 4 ) ( 3 。15 ) 来传送0 、1 两个码元，式中e ，为信号能量，t = i f o 为发送信号周期， 信号通过均值为o 、方差为盯2 = o 2 的加性高斯白噪声( a w g n ) 信道后 到达接收端解调器的输入端。由于采用相干解调，因此解调器匹配滤 波器输出的抽样电压是一均值为虿、方差为盯2 = n o 2 的高斯随机变 量。所以，输出电压，；的概率密度函数为 第三章维特比译码算法 砌) - 韭铲( 3 - 1 6 ) p ( 巾) - 堕铲( 3 - 1 7 ) 在硬判决解调器中，最佳判决门限为0 。当匹配滤波器输出的电压 为负，则输出为1 ( 相当于0 或l 码元) ；若为正，则输出为+ 1 ( 相当于1 或0 码元) 。此时，系统的误码率为 或= g ( 2 互n o ) 2 】 ( 3 1 8 ) 式中 ) = f 去出 ( 3 - 1 9 ) 在数字通信系统中，与硬判决解调器相应的译码器就是硬判决译 码器，即硬判决译码器利用解调器送来的己经过硬判决的0 、1 信息来 进行译码，这样的判决方式我们称之为硬判决译码。而硬判决译码的 结果会损失掉接收信号中所包含的有用的信息。为了充分利用接收信 号波形中的有用信息，使译码器能够以更大的正确概率判决所发的码 字，就把解调器输出的抽样电压进行量化。这样，解调器输出至译码 器的值就不止两个，而有q ( 通常q = 2 册) 个。另一方面，如果译码器直接 利用解调器的未量化的模拟电压进行译码，则称为模拟译码。无论译 码器是利用q 进制序列译码，还是利用模拟量的模拟译码，统称为软判 决译码。 在应用纠错码进行差错控制时，对信道的质量都会有一定的要求。 信道质量越好，利用纠错码所获得的效果就越明显；而如果信道原始 误码率很高如为1 0 一。则利用纠错码后不但没有好处，有时反而变得 更坏。但软判决译码不同，在误码率为1 0 。2 10 0 范围内，能提供几乎 最佳的性能。 在硬判决译码器中，通常利用汉明距离d i l 来度量码的纠错能力。 而在软判决译码中，与软判决译码器相应的解调器的输出是q ( = 2 用) 进制值，或介于1 之间的实数值。与此相应的，必须定义两个露长序 列或码字之间的软判决距离，下面主要针对欧几里德距离进行介绍。 当码字序列在均值为0 、方差为仃2 - - n o 2 的高斯白噪声信道中传输 时，它会受到噪声的干扰。设接收序列尺长度为刀，则由于噪声对每一 第三章维特比译码算法 码元( 或符号) 的影响是独立的，因而发送序列为g = ( 白l ，“，) ，接收序 列为局= ( ，i , - - - , r , ) 的概率p ( r