（通信与信息系统专业论文）turbo码编译码方法的研究与实现.pdf

摘要摘要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 极限的低信噪比下仍然能够获得较低的误码率，所以在近几年己成为编码理论界研究的热门领域，在第三代移动通信系统的开发中，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 码原理和结构进行介绍，并对不同参数对t u r b o码性能的影响进行仿真，得到了一些结论。仿真过程中，采用了一些方法来改善t u r b o码的误比特率性能：编码器部分利用交织与删余的综合设计，使每个信息位都有对应的校验位输入信道，起到了等保护的作用；译码部分采用线性近似与门限近似相结合的方法对l o g m a p 算法进行改善，在对性能影响不大的情况下，显著降低复杂性；s o v a算法中采用帧尾加长处理的方法充分利用了每帧最后j 位信息。为了加速t u r b o 码译码的实现，对m a p 类算法采用了分段译码的方法减小了译码等待延时，同时采用了一种基于外信息统计值的停止准则，以降低迭代次数为条件减小了译码迭代延时。最后，利用v h d l 语言在可编程逻辑器件上完成了t u r b o 码编码器的设计。然而，到目前为止，对t u r b o 码的研究还不算很完善，尤其是在实际应用中还有很多问题有待解决。但是t u r b o 码的优异性能是不能否定的，它有非常广阔的应用前景。关键词t u r b o 码；m a p 算法；s o v a 算法；v h d la b s t r a c tt u r b oc o d ew e r ef i r s ti n t r o d u c e di n1 9 9 3b yc b e r r o ue t c ，t h e ya r es h o r t e n e df r o mp a r a i l e lc o n c a t e n a t i o nr e c u r s i v es y s t e m a t i cc o n v o l u t i o n a lc o d e sw h o s ee n c o d e rc o n s i s t so fap a r a l l e lc o n c a t e n a t i o no ft w oo rm o r ec o n v o l u t i o n a lc o d e s ，a n di t sd e c o d e ru s e sas o f a - i n p u t s o f t o u t p u tf e e d b a c kd e c o d i n gr u l e t h i sk i n do fc o d eh a sg i v e nr i s et oal a r g ei n t e r e s ti nt h ec o d i n gt h e o r yb e c a u s eo ft h e yc a ns t i l la c h i e v es m a l lb i te r r o rr a t ea tl o ws n rc l o s et ot h es h a n n o nc a p a c i t yl i m i t s i nt h ed e v e l o p m e n to ft h et h i r dg e n e r a t i o nm o b i l ec o m m u n i c a t i o ns y s t e m s ，i ti sw e l lk n o w nt h a tt u r b oc o d e sa r et h ew a yo f c o r r e c tc o d i n go fh i g h s p e e d i n gd a t ac h a n n e l t h er e s e a r c ho ft u r b oc o d e si n c l u d e st h ed e s i g no ft h ee n c o d e r ，t h ei n t e r l e a v e ra n ds o f l - o u t s o f t - i ni t e r a t i v ed e c o d i n ga l g o r i t h m t h eg o a lo f t h i sp a p e ri st os t u d yt h ek e yi s s u e sb o t hi ne n c o d i n ga n dd e c o d i n gb l o c ka n dt or e a l i z et h ee n c o d i n gb l o c kb yh a r d w a r e f i r s t l y , t h eb a c k g r o u n do fi t sb i r c ha n dd e v e l o p m e n tt r e n da r ei n t r o d u c e d s e c o n d l ns o m ef u n d a m e n t a lt h e o r ya n db a s i cs t r u c t u r eo ft u r b o c o d e sa r ed e s c r i b e d a c c o r d i n gt ot h i s ，a n a l y s e so fd i f f e r e n tp a r a m e t e r sf o rt h ep e r f o r m a n c eo ft u r b oc o d e sa r ep r e s e n t e da n dg o ts o m ec o n c l u s i o n s d u r i n gt h ep r o c e s so fs i m u l a t i o n ，s o m em e t h o d sa r ep r o p o s e dt oi m p r o v et h ep e r f o r m a n c eo fb e r ：u s e dt h ec o m b i n e dd e s i g no fi n t e r l e a v e ra n dp u n c t u r ei ne n c o d i n gp a r t ，s o ，e a c hi n f o r m a t i o nb i th a sc o r r e s p o n d i n gp a r i t yb i tw h i c hh a v ee q u a lp r o t e c t i o n ；p u tf o r w a r dl i n e a ra p p r o x i m a t ea n df i x e da p p r o x i m a t et or e d u c et h ed e c o d i n gc o m p l e x i t yw i t h o u tn o t a b l ee f f e c to nt h ep e r f o r m a n c eo fl o g - m a pa l g o r i t h m ；m a k eu s eo fa d d i t i o n a lb i t sa tt h ee n do fe a c hf r a m eo fs o v a i no r d e rt oa c c e l e r a t ed e c o d i n g ，b l o c kd e c o d i n ga r eu s e dt os h o r t e nw a i t i n gt i m ea n dan e ws t o pc r i t e r i o nb a s e do ne x t e m a li n f o r m a t i o na r ep r o p o s e dt oi m p r o v ed e c o d i n gt i m e l a s t ，r e a l i z e dt h ew h o l et u r b oe n c o d e ru s ev h d ll a n g u a g eb a s e do np r o g r a m m a b l ed e v i c e k e yw o r d st u r b oc o d e s ；m a pa l g o r i t h m ；s o v aa l g o r i t h m ；v h d l河北大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特1 1 1 1 1 以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了致谢。作者签名：旦盟垂日期：j ! 堕年尘月止日学位论文使用授权声明本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。本学位论文属于1 、保密口，在年月日解密后适用本授权声明。2 、不保密。( 请在以上相应方格内打“”)作者签名：导师签名：囡疏羲2 至塑日期：塑喳年上月址日日期：堕年上月j 生日第1 章绪论第1 章绪论提高信息传输的可靠性和有效性，始终是通信工作所追求的目标。纠错码是提高信息传输可靠性的一种重要手段。它经历了5 0 年的历史，在此期间有了很大的进展。伴随着信息时代的到来以及微电子技术的飞速发展，今天的纠错码已不再单纯是一个理论上探讨得问题，它己成为现代通信领域中不可或缺的一项标准技术。近年来，随着无线数字通信的发展及各种高速率、突发性强的新业务的出现，研究并利用好的纠错码技术就越来越显得非常必要。尤其是在些频带或功率受到限制的系统中，这种必要性更为突出。1 1t u r b o 码的产生纠错码的中心任务就是要针对不同干扰特性的各种信道设计出编码效率高、抗干扰性能好，而且编译码设备又较简单的检、纠错码。对于数字通信系统设计者来说，能够按照用户所需的信息传输速率与精确度提出一个经济合算的系统是其根本任务。为了满足用户对信息传输精确度的要求，可以采用两种方法来施行：一是增加单位信息的信号能量；二是采用信道编码。但是，就目前来说，大部分系统对功率的要求非常严格，例如在c d m a 等数字蜂窝移动通信系统中，为了提高系统容量就必须使信噪比( s n r ，s i g n a ln o i s er a t i o ) 减小，因此通常只能选择信道编码方式。1 9 4 8 年，s h a n n o n 在他的开创性论文通信的数学理论阻m a t h e m a t i c a lt h e o r yo fc o m m u i l i c a t i o n ) 中指出【1 ：任何一个通信信道都有确定的信道容量c ，如果通信系统所要求的传输速率r c ，则存在一种编码方法，当码长y t 充分大并应用最大似然译码( m l d ，m a x i m u ml i k e l i h o o dd e c o d i n g ) 时，信息的错误概率可以达到任意小。这就是著名的有噪信道编码定理，奠定了纠错编码理论的基石。然而s h a n n o n 的信道编码定理并未给出构造有效码的实用方法，而且当要求的差错概率很低时，将迫使系统采用非常长的编码，从而导致使用非常复杂的译码算法，甚至不可能实现译码。从五十年代到六十年代初，纠错码的研究主要集中在线性分组码理论上，相继出现了汉明码1 2 j ，循环码，b c h 码及r s 码等好码。五十年代还提出了另外一类纠错码一一卷积码pj 。河北大学工学硕士学位论文卷积码在编码过程中引入了寄存器，从而增加了码元间的相关性，但同时也给其分析和设计带来困难。在六十年代，随着对卷积码的深入研究，出现了几种与卷积码相适应的译码算法，促进了对卷积码的研究和应用，它曾被认为是一种非常有前途的能达到信道编码定理所指出的理论极限的码类。另外，在实际应用中，为了优化性能，人们还往往利用级联码或乘积码的形式。但无论是分组码、卷积码还是级联码、乘积码，相对于未编码情况，尽管一定程度上提高纠错性能，但还远未达到理论的极限。在1 9 9 3 年于瑞士日内瓦召开的国际通信会议( i c c ，i n t e r n a t i o n a lc o n f e r e n c eo nc o m m u n i c a t i o n s ) 上，法国的c b e r r o u 等人首次提出一种称为t u r b o 码州的全新的编码方案。由于它很好地应用了s h a n n o n 信道编码定理中的随机性编、译码条件，从而获得了几乎接近s h a n n o n 理论极限的译码性能。仿真结果表明，在采用长度为6 5 5 3 6 的随机交织器并译码迭代1 8 次的情况下，在信噪比厶0 o 7 d b 并采用二元相移键控p s k )调制时，码率为l 2 的t u r b o 码在加性高斯白噪声 a w g n ) 信道上的误比特率( b e r ，b i te r r o r m 啦) 1 0 ，仅比香农限毛0 = 0 d b 多了o 7 d b 这一超乎寻常的优异性能立即引起了编码界的强烈反响，t u r b o 码很快成为纠错编码领域的一个热点。t u r b o 码的提出，标志着信道编码理论与技术研究进入了一个崭新的阶段，它结束了长期将信道截止速率作为实际容量的历史；它改变了人们构造好码的传统观念，现存人们更喜欢基于概率的软判决泽码方法，而不是早期基于代数的构造与译码方法：而且人们对编码方案的比较方法也发生了变化，从以前的相互比较过渡到现在的均与s h a n n o n 限进行比较；同时t u r b o 码迭代的思想也为解决不同通信领域的问题提供了新的思路。1 2t 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 码的研究进展，主要集中在以下几个方面：主要集中在以下几个方面：第1 章绪论1 2 1t 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 码的核心，在目前已经成熟的纠错码中有许多可以选作分量码，如分组码和卷积码。在各种性能测试中，卷积码的性能一般要好于分组码，目前分量码的选择基本上是卷积码，对分量码选择分组码的研究较少。s b e n e d e a o 5 。7 1 分析了分别采用递归与非递归卷积码作为分量码时t u r b o 码的性能，说明分量码应采用递归结构；j h o k f e i t 提出了迭代译码适应性( i d s ，i t e r a t i v ed e c o d i n gs u i t a b i l i t y ) 的概念，同时提出分量码的反馈多项式应该选为本原多项式；d d i v s a l a r 等人分别研究了高码率和低码率条件下t u r b o 码分量码设计的一般性原则。另外一个通过码字设计提高性能的方法是采用多维码作为分量码，许多文献也专门对此进行讨论。交织器的设计直接影响t u r b o 码的距离谱和性能，其主要作用是提高低重序列的输出码重和减小译码输出之间的相关性。t u r b o 码中常用的交织器有分组交织器与随机交织器两大类，其基本类型又可分为行列式分组交织、螺旋式分组交织、线性转换式随机交织和读表式随机交织等。k a n d r e w s 对交织器的数学理论进行了研究，解释了影响交织器性能和实现的因素；文 8 】、【9 也以仿真为手段研究了不同的交织对性能的影响；j y u a i l 【l o 就交织器与分量码两者的联合优化会对t u r b o 码的性能有所改进方面进行了有益的尝试。有关交织器设计的方法已有很多，但到目前为止尚没有通用的交织器设计方法出现。另外，有关交织器的硬件实现问题也有讨论。1 2 2 软输出迭代译码算法t u r b o 码的编码过程实际上是一个利用强约束短码构造伪随机长码的过程。对于传统编码方法来说，当码字达到一定长度以后，m l d 是不可能实现的。而软判决迭代译码很好的解决了这个问题。因此，软输入软输出( s i s o ，s o f t i n p u t s o f t o u t p u t )的译码算法是t u r b o 码译码的必须算法。自t u r b o 码出现以来这方面的研究也引起河北大学工学硕士学位论文了有关学者的关注。h a g e n a u e r 等1 1 1 利用对数似然比对存在的软输入软输出算法进行分析。这些方法包括逐符号最大后验概率译码( m a p ，m a x i m u m a p o s t e r i o r i ) 算法或称b c j r 算法；软输出v i t e r b i ( s o v a ，s o f t o u t p u t v i t e r b i a l g o r i t h m ) 及相应的次最优算法。m a p 算法是一种基于码元的最大后验概率译码算法，对于线性块编码的卷积码，它能使比特错误率最小，也是最早应用于t u r b o 码中的译码算法 1 2 1 。但是采用此算法计算量大，译码复杂度高，在实际中应用起来比较困难。因此，如何消除m a p 算法中的指数和乘法运算成为简化的首要任务。而最为有效的方法就是利用对数函数的单调性，对算法中的变量统一取对数，将其中的乘法运算化为加法运算并消除部分指数运算。t u r b o 码译码算法的复杂度还表现在前向和后向迭代运算中，由于减少迭代次数可以有效的减少前向和后向迭代运算，也就会降低译码复杂度。因此如何减少迭代次数或对信息符号及早判决成为人们研究的热点，针对这种情况，人们提出了各种改进的算法f 1 3 。1 5 】。相比之下，t u r b o 码译码中，软输出维特比译码( s o v a ) 算法计算简单，存储量小，易于硬件实现的优点，受到目前人们广泛的关注 1 6 - 1 7 。但由于它的输出不是对m a p 算法结果的一个近似，因此是次最优算法，它在性能上与m a p 算法相差l d b左右。综上所述，t u r b o 码的译码算法主要采取m a p 算法和s o v a 算法，而算法的简化、复杂度的降低、内存的减少一般是以信噪比为代价换取的。因此，如何寻找一种译码算法与m a p 算法性能一致而又比较简单的算法一直是人们研究的热点。1 2 3t u r b o 码的应用由于t u r b o 码具有接近s h a n n o n 理论极限的性能，尤其是低信噪比下的优异性能使t u r b o 码在许多通信系统中都有非常大的应用潜力。除了在深空通信、卫星通信以及多媒体通信等领域的应用以外，t u r b o 码在无线移动通信系统中的应用是目前的研究热点。目前，t u r b o 码已经成为第三代移动通信系统的标准之一【1 8 】，有关其关键技术的标准化也已经出现。此外，t u r b o 码在文本传输和数据存储等方面也有应用。d 第1 章绪论t u r b o 码的出现，不仅提供了一个性能优越的编码方法，同时迭代的思想也为众多通信问题提供了解决方案。有关t u r b o 迭代思想在通信系统中应用的研究也在不断深入。这主要包括：迭代信道估计和同步、多用户检测、t u r b o 均衡。此外，t u r b o 码在联合信源一信道编码以及实现a r q 技术上也有应用。虽然t u r b o 码的研究已经从简单的仿真发展到应用于实际的通信系统，但t u r b o码的理论解释、关键技术改进以及在相关领域应用的具体化仍然是非常重要的课题。纵观t u r b o 码的研究现状，我们认为需要进步研究的课题有：( 1 ) 最优分量码与交织器的联合设计。( 2 ) 低复杂性译码算法。( 3 ) 译码迭代过程的优化、收敛性以及迭代停止准则的设计。( 4 ) 联合信道估计多用户检测均衡和译码算法。( 5 ) t u r b o 码与高阶调制技术的结合。( 6 ) t u r b o 编译码器的硬件实现。( 7 ) t u r b o 码在无线通信、移动通信以及多媒体通信中的应用，特别是在移动网络、i m t - 2 0 0 0 及加密系统中的应用等。1 3 本文主要工作及内容安排t u r b o 码被看作是1 9 8 2 年t c m ( t r e l l i sc o d e dm o d u l a t i o n ) 技术问世以来，信道编码理论语技术研究上所取得的最伟大的技术成就，具有里程碑的意义。其优异的性能吸引越来越多人投入到t u r b o 码的研究工作中来。本文对t u r b o 码编译码过程中的关键问题进行了分析，并对不同设计参数对t u r b o 码性能的影响进行了计算机仿真，同时用v h d l语言实现了t u r b o 码编码器的设计。具体内容安排如下：( 1 ) 第1 章介绍了t u r b o 码的产生背景、研究现状和发展趋势。( 2 ) 第2 章介绍了差错控制编码的基本知识及常用的纠错码分组码、卷积码，并由级联码存在问题及解决方案引出t u r b o 码的产生。( 3 ) 第3 章介绍了t u r b o 码编、译码器的基本结构，并对编码过程中的关键问题进行了详细研究。采用了交织与删余的综合设计，保证交织器对于两个分量编码器具有等保护作用，提高了误比特率性能。5 河北大学工学硕士学位论文( 4 ) 第4 章详细推导了t u r b o 码的m a p 、l o g m a p 和s o v a 译码算法，并对几种算法的性能和复杂性进行了比较。采用了几种方法从存储空间和误比特率性能方面对t u r b o 码性能进行改善。( 5 ) 第5 章通过性能仿真分析了分量码、信息序列长度、码率、译码方法等因素对t u r b o 码性能的影响。采用分段译码和停止准则相结合的方法提高t u r b o 码的译码时延特性。( 6 ) 第6 章介绍t u r b o 码编码器的v h d l 硬件实现，并给出了不同部分m a x p l u si i的时序仿真波形，做到了输入连续信息序列得到同步的、连续的输出序列。( 7 ) 第7 章对本文工作进行总结。总之，t u r b o 码编译码算法的研究与实现是目前研究的热点，对其作深入研究将有助于t u r b o 码在实时通信系统中的应用。第2 章差错控制编码基础第2 章差错控制编码基础现代信息和编码理论的奠基人c e s h a n n o n 在1 9 4 8 年提出了著名的有噪信道编码定理，在定理中s h a n n o n 给出了在数字通信系统中实现可靠通信的方法以及在特定信道上实现可靠通信的信息传输速率上限。同时，该定理还给出了有效差错控制编码的存在性证明，从而促进了信道编码领域研究的快速发展。自此以后，人们一直致力于寻找纠错能力强，译码复杂性小和硬件实现简单的纠错编码方法。从纠错码的发展历程看，主要可以分成两类：分组码和卷积码，为进一步提高码字的纠错性能和带宽效率，又相继提出了级联码以及格型编码调制等方法。本章将主要介绍与本文相关的信道编码理论以及分组码、卷积码和级联码的概念、编码方法，从而了解t u r b o 的产生过程和背景。2 1 信道编码理论随着对高效、高可靠性数字通信系统需求的迅猛增长，大规模高速宽带网络的发展使语音、图像和其他多媒体信息的传输成为可能。通信系统设计人员最关心的是如何在数据源功率和传输带宽有限，系统复杂性和设备造价尽可能小的条件下实现尽可能准确的信息传输，即使信息传输的误码率最小化。信道编码是消除或降低信息传输错误概率的有效手段之一。根据s h a n n o n 信息理论，通用数字通信的组成结构如图2 1 所示1 9 1 。；蓁i等效离散信源ii 信ll 干li 区卜匹三h 三困 三一一i等教离散信宿l等效离散信道图2 1 数字通信系统框图f i g 2 1b l o c kd i a g r a mo f d i g i t a lc o m m u n i c a t i o ns y s t e m在数字通信系统中，发送器的任务是将信源生成的信息转换为能够抵抗信道噪声和失真以及有利于在传输媒质上进行传输的形式，它包括信源和信源编码器。信源中通常包含冗余信息，这主要是因为在信源中相邻符号之间存在一定的相关性，而且每个符号- 7 一河北大学工学硕士学位论文出现的概率是相同的。为提高传输带宽利用率和信息传输效率，在信息传输之前先利用信源编码器来消除这些冗余，可以利用最少的码元来代表要传输的信息。信源输出经过信源编码器编码后得到的数字序列称为信息序列。传输信道存在一定的噪声和衰落，必然会对其上传输的信息引入失真和信号判决错误，因此需要采用差错控制编码来检测和纠正这些比特错误。信道编码器的作用就是按一定规则在信息序列m 中嵌入冗余码元，使不具规律性的信息序列m 变成具有某种规律的新序列s ( 又称为码序列) 。与原始信息序列中的冗余码元不同，经过信道编码添加的冗余码元的作用是减小传输中发生的信号和码元错误，提高系统的可靠性。在接收端，信道译码器根据这种预知的编码规则来译码，检测接收的数字序列胄是否符合预知的规则，从而发现或纠正接收序列r 中的错码。信道编码是在发送器和接收机之间实现信号可靠传输的必要手段之一。通常信息序列m 是以k 个码元为一组来传输的，我们称这k 个码元组成的码组为信息码组，信道编码器按一定规则对每个信息码组附加”一k 个冗余的码元( 称为该码组的监督码元或监督元) ，构成了行个码元的码组( 又称码字) ，这v 个码元之间是相关的。确切地说，附加的”一k 个冗余码元为何种符号序列与待编码的信息码组有关。从信息传输的角度来说，监督元不载有任何信息，所以是多余的，但这种多余度使码字具有一定的纠错和检错的能力，提高了传输的可靠性，降低了误码率。比特形式的信息是不适合在物理信道上传输的，因此需要利用数字调制器将这些编码信息比特转换成适合于在信道上传输的连续波形信号。同时调制器还可以在相同的物理信道上同时传输多个信息比特，从而提高信息传输速率。调制器的基本思想是将编码的数字序列映射成适合在信道上传输的模拟连续信号。信号经过信道传输后到达接收端。在接收机中，数字解调器的作用是通过对接收到的调制信号序列或传输码字进行最优估计，然后输出数字编码序列到信道译码器。信道译码器对接收序列进行估计和判决，估计准则是根据编码准则和信道特性而确定的，目的是使信道噪声所造成的信号判决错误最小化。如果接收序列是二元序列，则相应的信道译码器的译码称为硬判决译码，硬判决译码会损失接收序列中的有用信息。为充分利用接收信号波形中的信息，可以把解调器输出的抽样电压量化，因而由解调器送给译码器的值就有q 个；或者译码器就直接利用解调器输出的未量化模拟电压进行译第2 章差错控制编码基础码。如果接收序列是非二元的量化序列或连续未量化的序列，相应信道译码器的译码称作是软判决译码。理论上，软判决比硬判决译码至多可有3 d b 增益。最后信源译码器根据信源编码准则将得到的信道译码器输出的编码信息序列经过相应的信源译码后，得到对原始信源序列的估计并传递给用户( 信宿) 。衡量信道编译码有两个指标，误码率g ( e ) 和信息传输速率r 。如果确定一个可容忍的误码率，希望传输速率r 尽可能高；或者给定五，希望得到最小的误码率。在有扰信道中，对于第一种情况，且能做到多高；对于第二种情况，误码率能否做到任意小?信道编码定理回答了这些问题。信道容量是指信道能无错误的传送信息的最大信息率。编码定理是用来解决达到这个最大值的可能性和超过这个最大值时传输问题的方法。s h a n n o n 信道编码定理指出：对于一个给定的有扰信道，若信道容量为c ，信道中信息传输率为r ，如果r c ，必定不存在有这种编码方法，当趋于无限大时，差错概率将接近1 。因此，信道容量是一个界限，在此界限之内，几乎可以无错误地传输信息，反之，在此界限外，就不可能做到无错误地传输。g a l l a g e r 等人已经证明，对于离散输入无记忆信道，存在码率为r 的包含个符号的码字，在采用最大似然译码时其码字错误概率的上限为【2 0 1只( p ) f )由上可知，一个0 ，_ j ) 线性分组码有两个最重要的参数：一个是它的最小距d 。，另一个是码率r = k n 。d 。反映出码的纠错能力，d 。越大，码的纠错或检错能力就越强。r 表示信息位在码组中所占的比重，r 越大，说明信息位占的比重越高，故码的有效性越高。显然，我们总希望构造一个r 既高d 。又大的码，但实际上这二者是矛盾的，编码的主要任务就是如何找到一种方法，在满足一定r 下，使d 。尽可能大。对于一个0 ，后) 线性分组码，若将其任意个码字( c 。，c ，c 0 ) 的码元向右或向左循环移一位，所得的( c 0 ，c n + c 2q ) 或也。，c 。，吒，巳一。) 仍然是码字，则称该码为循环1 4 第2 章差错控制编码基础码。循环码是一类非常重要的线性码，它的特点是编译码器可以很容易地利用移位寄存器构造乘法电路和除法电路来实现，而且由于循环码具有很好的代数结构，因此译码方法相对简单。循环码由于实现简单而在众多通信系统中得到了广泛的应用。2 4 卷积码分组码都是将序列切割成分组后独立地进行编译码，分组与分组之间没有任何联系。从信息论的角度看，这样做忽略了各信息分组之间的联系，必然丧失一部分相关信息，且信息序列切割得越碎( 码字越短) ，丧失的信息越多。但若使分量码码长n 尽量大，译码复杂度将随着胛指数上升。这些问题导致卷积码的产生。卷积码是1 9 5 5 年由埃利斯( e l i a s ) 提出的，它是一个有记忆系统，它将信息序列切割成长度为_ j 的一个个分组。与一般分组码的不同之处在于：当某一分组码进行编码时，不仅根据本时刻的分组，而且根据本时刻以前的 n 个分组共同来决定输出码字，m 称为编码存储，它表示输入信息组在编码器中需存储的单位时间。由于码字的产生一共受到n = m + 1 个信息分组的制约，因此称n = m + 1 为编码约束度，说明编码过程中互相约束的码段数。常用瓴，k 0 ，聊) 来表示某一卷积码，该码的码长为n 。，信息位长度为岛，编码约束度是n = m + 1 。称。= n n 。为编码约束长度，说明编码过程中互相制约的码元数。称r = k o n 为编码速率，简称码率。码率是衡量卷积码编码效率的重要参数。图2 - 3 给出t - - 进制( 2 ，1 ，2 ) 卷积码的编码框图。图中d ( f = l ，2 ) 为移位寄存器。图2 3 ( 2 ，1 ，2 ) 卷积码的编码框图f i g 2 3e n c o d i n gb l o c kd i a g r a mf o rt h e ( 2 ，1 ，2 ) c o n v o l u t i o n a lc o d e编码时，在某一时刻_ j 送入编码器一个信息比特m 。，同时移位寄存器中的数据( d 1 和d 2 中存储的数据分别是| 一1 时刻和k 一2 时刻的输入m 和m h ) 右移一位，编码器根据移位寄存器的输出m 。、m 。和编码器的输入按照编码器中所确定的规则进行运算，1s 河北大学工学硕士学位论文生成该时刻的两个输出码元c 和毋。由图2 _ 3 的编码器结构可知，这个( 2 ，1 ，2 ) e f 6 ：溺的编码规则为c 1 1 ) = m to m h( 2 7 a )c 竽= 埘io m o m n 2( 2 7 b )输出码字为以= 雠) ，c p l )( 2 8 )可见，任一时刻的编码输出气不仅与当前时刻的输入m 。有关，同时还与孟一t 时刻和k 一2 时刻的输入。和m 有关，同时，k 时刻的输入信息元还影响接下来k + 1时刻和k + 2 时刻的编码输出气+ 。和吒+ 2 。和分组码一样，卷积码也可以用矩阵和多项式来表示，但这些表示方法并不能揭示卷积码的内在特性。在这一点上，状态图和网格图提供了很好的描述工具。通常卷积码的编码电路可以看作一个有限状态的线性电路，因此可以利用状态图来描述编码过程。编码器寄存器在任一时刻所存储的数据取值称为编码器的一个状态，以s 表示。对于图2 ，3 所示的二进制( 2 ，1 ，2 ) 卷积码，编码器中包含两个寄存器，因此，共有2 2 = 4 种可能的状态，相应的取值和标记如表2 1 所示。表2 1 约束度为3 的编码寄存器状态表t a b 2 1s t a t et a b l ef o rt h ee n c o d i n gr e g i s t e rw i t hr e s t r i c t e dl e n g t ho f 3状态sd l d 2s 10 0s 20 1s 31 0s 41 1随着信息序列的输入，编码器中寄存器的状态在上述4 个状态之间转移，并输出相应的码序列。将编码器随输入而发生状态转移地过程用流程图的形式来表示，即得到卷积码的状态图。( 2 ，1 ，2 ) 卷积码状态图及相应的输入码元和输出码元的关系如图2 4 所示。在图2 4 每一条转移路径上的标记中，斜线前的是输入码元，后面是相应的输出码- 1 6 第2 章差错控制编码基础元。编码器的编码过程就是在状态图上状态转移的过程。例如，对于信息序列m = ( 1 0 1 1 1 0 0 ) ，若卷积码的初始状态为& ，则在对m 编码时状态转移为s o 斗s l js 2 一s i 斗s 3 斗s 3 js 2 呻s o相应的编码输出为( 1 1 , 1 0 ，0 0 ，0 1 ，1 0 ，0 1 ，1 1 ) 。将状态图按照时间的顺序展开，即得到卷积码的格图表示。例如，考察长度为上= 5 的输入信息序列，为使编码器在编码完成后回到初始r 状态，需要在信息序列的尾端补充与编码器寄存器个数相等的l 1 0图2 4 ( 2 ，1 ，2 ) 卷积码编码器状态图f i g 2 4e n c o d i n gs t a t ed i a g r a mf o rt h e( 2 1 ，2 ) c o n v o l u t i o n a lc o d e零比特。由此，相应的格图表示如图2 5 所示。其中每条路径转移分支对应的输入输出码元与图2 4 给出的状态图中的一致。图中粗线所对应的输入信息序列为m = ( 1 0 1 1 1 0 0 ) ，相应的编码输出为0 1 ，1 0 ，0 0 ，0 1 ，1 0 ，0 1 ，1 1 ) 。0 00 l1 01 1t = 0l234567图2 5d ，1 , 2 ) 卷积码l = 5 格图描述f i g 2 5t r e l l i sd i a g r a mf o rt h e ( 2 ，1 ，2 ) c o n v o l u t i o n a lc o d ew i t hl = 5卷积码的译码可分为代数译码和概率译码。代数译码一般仅用于简单的卷积码。其优点是译码电路简单，延时小，适合于高速译码。其不足之处在于：适合代数译码的卷积码的编码增益一般都不大，且仅适合于硬判决译码。卷积码概率译码的基本思想是：以断续的接收码流为基础，逐个计算它与其他所有可能出现的、连续的网格图路径的距离，选出其中可能性f 概率) 最大的一条作为译码估值输出。概率最大在大多数场合可解释为距离最小，这种最小距离译码体现的正是最大似然的准则。当前最流行、最实用的卷积码译码算法是a j v i t e r b i 于1 9 6 7 年提出 2 3 的维特比算法，它分为硬判决v i t e r b i 译码和软判决v i t e r b i 译码两种译码方式。由于最优的特性和河北大学工学硕士学位论文相对适中的复杂度，维特比算法在三1 0 的卷积码译码中已成为首选的、最普遍采用的算法。2 5 级联码与t u r b o 码香农1 9 4 8 年提出的信道编码定理虽然仅是一个存在性定理，但却指出了纠错码的研究方向。最近几十年，纠错编码理论和实践的发展正是沿着信道编码定理的两条主线，即构造码长n 哼o o 的渐进好码，以及在可接受的译码复杂度范围内实现最大似然译码这两个方向展开的。从理论上讲，只要增加码长以加大随机化，几乎所有的码都可以是渐进好码，这一点从编码角度上讲也是可以实现的。从工程角度看，真正的障碍还在译码上。因为译码复杂度和码长成指数关系，对长码实现晟佳译码几乎是不可能的。由于无限长码的译码事实上是不可实现的，于是人们被迫去寻找各种替代的、可实现的方法，其中之一受信号分级放大、火箭分级推进的启发，“纠错是否可能分级? ”，这就导致了级联编码方案的出现。1 9 6 6 年，f o m e y 提出了一种构造长码的有效方法 2 4 1 ，就是利用两个短码的串接构成一个长码，其编、译码器结构分别如图2 6 、2 7 所示，叫做串行级联码。图2 6 串行级联编码器框图f i g 2 6b l o c ko f s e r i a lc o n c a t e n a t e de n c o d e r图2 7 串行级联译码器框图f i g 2 7b l o c ko f s e r i a lc o n c a t e n a t e dd e c o d e r该码在发送端是两级编码，在接收端是两级译码，属于两级纠错。连接信息源的叫做外编( 译) 码器，连通信道的叫做内编( 译) 码器。若外码是码率为r 的( 彤) 分组码，内码是码率为r l 的0 ，尼) 分组码，则两者合起来相当于码长为n n 、信息位为麟、码率为r = r o r l 的分组长码。一1 8 一第2 章差错控制编码基础由于软判决特比最大似然译码算法适合于约束度较小的卷积码，因此级联码的内码常用卷积码，外码则采用分组码。以卷积码为内码的级联码适用于高斯白噪声信道，原因是卷积码本质上属于纠随机差错码而不是纠突发差错码。针对维特比译码产生突发差错的特点，如果在卷积内码和分组外码之间插入一个交织器，其作用在于数据顺序的随机化，则交织器不仅使差错随机化，也使数据随机化，起增加码长的功能。对于串行结构的级联码，其总体纠错能力是内码纠错能力和外码纠错能力之和，尽管不像系统工程有“综合大于个别之和”的能力，但分别提高内、外码的纠错能力都能有效地提高总体纠错能力。由于软判决译码比硬判决译码从理论上要优秀3 d b ，因此适合使用维特比软判决译码的卷积码成为首选的内码。但是，通常的维特比译码只能提供硬判决输出，导致级联其后的外码无法再采用软判决译码，这必然造成信息的损失。为了使外码译码也能利用软信息，要求内码译码具有软输入、软输出。为此，人们提出了各种软输出算法，其中以m a p 算法口5 】和s o v a 算法 2 6 j 最有代表性，应用也最广。进一步的思考使人们提出这样一个问题：信号可以通过反馈取得优良的性能，那么信息是否能通过反馈而得到某种好处呢? 具体到级联码，既然s i s o 算法允许将内码的软输出提供给外码作为软判决输入，那么外码是否也能执行软输出译码并将译码软信息反馈到内码的输入端而提高其性能昵? 沿着这条思路的进一步研究发现，传统级联码结构之所以难以实现信息反馈，主要的障碍存在于两个方面【2 7 l ：编码过程在数学上是一种映射，可以用函数关系来描述。外码编码g = ( x ) ，译码x = f 。1 ( a )内码编码c 2 = g ( c 1 ) ，译码c 1 = g - l ( c 2 )反馈到内码的软信息表示为：石一厂1 k 。( c 2 ) )级联码各级编、译码器只知道本级的函数关系，对于反馈到内码输入端的信息x ，= 。k 。( c 2 ) ) ，能被内码译码器识别的信息函数g 1 ( c 2 ) 被未知函数厂- 1 ( ) 保藏阻隔而无法利用。反馈既可能是有用信息的反馈( 良性) ，也可能是无用甚至差错信息的反馈( 恶性) ，作为一种稳定的译码算法，如何才能保证信息反馈是良性的? 另外，反馈必然导河北大学工学硕士学位论文致循环迭代，在算法设计上如何保证能收敛到正确的位置，以及如何来判段迭代的收敛与否?为了解决第一个问题，希望信息位工能和内码的g 建立直接的关系。为此，要求内、外两层码均采用系统码，这样，信息位x 可直通穿越信道和各级编译码器而与编译码的函数关系无关，反馈信息x 也可直接被利用。至于第二个问题，要求内码译码在本次循环所用的反馈软信息中不包含上次循环时曾用过的信息，因为不是同一信息的循环，也就不存在正反馈还是负反馈的问题。从严格意义上看，这种要求是不可实现的。但当两次译码之间经过交织处理后，用于本次译码的反馈信息由于交织器的随机化处理而变得与上次不同。此时，只有从反馈符号似然信息中除去己用过的关于该符号本身的部分，就可以基本清除正反馈，实现迭代译码。对传统级联码做了上述结构和算法上的修正后，性能优异的t u r b o 码就诞生了。t u r b o 码，又称并行级联卷积码( p c c c ，p a r a l l e lc a s c a d ec o n v o l u t i o n a lc o d e ) ，是由c ，b e r r o u 等在i c c 9 3 会议上提出的。它巧妙地将卷积码和随机交织器结合在一起，实现了随机编码的思想；同时，采用软输出迭代译码来逼近最大似然译码，具有非常优异的