（通信与信息系统专业论文）turbo编码技术及其在移动通信中的应用研究.pdf

摘要 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 编码( s t t u c ) 技术。 关键字：t u r b o 码m a p 算法软输出v i t e r b i 算法分集空时t u r b o 码 a b s t r a c t a n i m p o r t a n tb r e a k t h r o u g hi nt h eh i s t o r yo f c h a n n e lc o d i n gw a st h ed i s c o v e r yo f t u r b oc o d e s ，w h i c hl e a d st oz e a l o u sr e s e a r c h so nt u r b o c o d i n gt e c h n i q u e i nt h e c o m m u n i c a t i o ns y s t e m t h i sp a p e ri sc l o s e l yf o c u so i lt u r b oc o d i n g t e c h n i q u e f i r s t l y , w ei n t r o d u c et h ep r i n c i p l e so ft u r b oc o d e sa n dp r e s e n tt h es i m u l a t i o nr e s u l t sa n d p e r f o r m a n c ea n a l y s i s s e c o n d l y ，c o n s i d e r i n g s o m ef a c t o r so nw h i c h p e r f o r m a n c e d e p e n d s ，w eg i v es o m ed e s i g nc r i t e f i a so ft u r b oc o d e s f i n a l l y ，i nc o n s i d e r a t i o no f c h a r a c t e r i s t i c so fm o b i l ec h a n n e l ，w ei n v e s t i g a t et h ec o m b i n a t i o no ft u r b oc o d i n g t e c h n i q u ea n ds p a c ed i v e r s i t yt e c h n i q u e ，n a m e l y ，s p a c et i m et u r b oc o d i n g ( s t t u c ) t e c h n i q u e k e y w o r d s ：t u r b oc o d e s m a ps o v a d i v e r s i t y s t t u c 创新性声明 y5 8 3 8 3 1 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表过或撰写过的研究成果：也不包含为获得西安电子科技大 学或其他教育机构的学位或证书而使用过的材料，与我一同工作过的同志对本研 究所作的任何贡献均已在论文中作了明确说明并表示了谢意。 本人签名篮瓶墨日期压西趑 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校 有权保留送交的论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采硝影印、缩印或其他的复制手段保存论文。 本人签名 导师签名 耋域圭! 笠些 日期_ 竺竺至 圈塑 日期： 第一章绪论 第一章绪论 实现可靠性通信，主要有两种途径：一种是增加发送信号的功率，提高接收 端的信号噪声比：另种是采用编码的方法对信道差错进行控制。前者常常受条 件限制，不是所有情况都能采用；后者是建立在香农( c 1 a u d e e s h a n n o n ) i n 论1 1 基础上的，在他的论文中，曾划编码的效能加以阐明。他证明：如果数据源的速 率低于信道容量之值时，则可采用适当的编码与译码方法，以任意小的差错概率 在噪声信道上进行通信。近几十年发展起来差错控制编码技术就是基于这一思想 而产生的，编码技术和提高信号发送功率都能在接收端有效地抑制噪声信号，而 有效地在噪声中恢复出有用信g - ，因此从这个意义上说，差错控制编码中的编码 技术和提高发送信号功率是等效的。 在实际的应用中，使通信速率受到限制的并不只是信道容量，而更多的是实 现编码方案所花的费用，费用的限制使通信速率远远低于通信容量。近年来，在 寻求用于各类噪声信道上有效与实用的编码方案方面进行了大量研究，并在寻求 实用方案方而已取得很大的进展，使得在许多应用中，编码都能对性能提供重大 的改善。在通信系统中引入差错控制编码所能获得的两个显而易见的好处就是： 一个是在所发送的数据中加入冗余，对实际的通信过程中不可避免的差错进行检 测或纠正，以满足可靠性通信；另个就是编码的利用，使得信号发射功率减少， 从而使通信设备的体积、重量及复杂度大为下降。随着纠错编码进一步的发展， 以及固态电子器件在体积与价格方面迅速下降，使编码的实用性大大增加。因此， 纠错编码已不再单纯是一个理论上讨论的课题了，而更多的成为门标准技术而 被广泛采用。本文所要介绍的t u r b o 码正是这样一类重要的纠错码技术。 1 1 纠错编码的历史与发展概况 在香农( c l a u d e e s h m m o n ) 于1 9 4 8 年所发表的经典论文“通信的数学理论” 中 1 ，明确地指出了一个编码通信系统可取得的性能，从而奠定了信息论的基础。 信息论的基本定理不仅指出通信的有效性界限，也明确指出了在得到这些界限时， 编码所起的作用。因此，从通信的观点来看，越能设计出接近信道容量的编码当 然越好，但s h a n n o n 的文章中并没有明确指出如何将拟传输的消息进行纠错编码， 也没有提出这种具有纠错能力的传输系统的具体实现方法。而且，即使存在这样 的编码，如何进行有效的编码和译码同样是一个重要的问题，所以纠错编码所研 究的问题不仅是设计出接近信道容量的“好码”，而且更重要的是要设计出类能 进行有效编译码的“好码”。 由于纠错编码能提高通信的可靠性，故日益受到科技人员的重视。受香农理 q 、u r b o 编码技术及其社移动通信r 1 1 的应j 4 j 研究 论的鼓舞，此后汉明( h a m m i n g ) 、斯列宾( s l e p i a n ) 、普兰奇( p r a n g e ) 等人相继投入这 一领域进行研究。在5 0 年代初，根据s h a n n o n 的思想，给出了一系列设计好码和 有效译码的方法：之后，纠错编码受到了越来越多的通信和数学工作者，特别是 代数学家的重视，尤其在6 0 年代至7 0 年代初，这方面的研究活动十分活跃，使 纠错编码的理论研究达到了顶峰，为以后的实际应用打f 理论基础；到7 0 年代初 至8 0 年代，大规模集成电路和微机的迅速发展，为纠错编码的应用打下了坚实的 物质基础，因而与应用相关的各种技术及有关问题得到了极大的关注，并在实际 中取得了巨大成功，这为纠错编码在各类通信系统中的广泛应用丌辟了新的篇章， 至此，纠错编码的实现和设计作为通信系统的一部分而受到通信工作者更广泛的 关注，从而进一步推动纠错编码技术的发展。 到f f 前为i j ：! = ，纠错码技术已经在实际应用中取得了越来越不可忽视的作用： 利用纠错编码降低各类数字通信系统以及计算机存贮和运算系统的误码率，提高 通信质量，延长计算机无故障运行时间等；在超大规模集成电路设计中采用纠错 码技术来提高芯片的成品率，降低芯片成本；纠错码与调制技术相结合所产生的 t c m 技术，使得在频率资源日趋紧张的今天能获得更大的带宽效率；纠错码与密 码技术相结合，可以构造出一类既能加密、签名，又具有纠、检错功能的密码系 统；纠错码与信源编码相结合的结果，使得通信系统更为有效与可靠；不仅如此， 纠错码中的编译码思想和方法，也被一些研究领域( 如：神经网络) 所借鉴，用来解 决这些领域中的一些问题。因此，我们有理由相信，随着科学的进步和实际的需 要，纠错码理论必将进一步发展，同时，随着超大规模集器件成本的进一步下降， 它的应用范围必将进一步扩大。 1 2 研究背景 移动通信从一进入市场就获得了极大的成功，并最示出了强大的生命力。同 时，移动通信技术也面临一个最主要问题，就是如何在时变的衰落信道进行可靠 的数据传输，这也是它和光纤、铜线通信等相比面临的一个重要挑战，同时随着 各种数字多媒体业务的迅猛发展，移动通信还必须解决的一个问题就如何在无线 信道中实现高速数据通信。在衰落环境下降低误码率相当困难：在加性高斯白噪 声信道( a w g n ) 下，用典型的调制和编码方式，把比特错误率( b e r ) 从1 0 降到 1 0 ，信噪比需要增加1 - 2d b ；而在多径环境下要获得同样的性能改善，信噪比需 要增加1 0 d b ；同时能够利用的带宽资源也十分有限。因而通过在发射端采用更高 的功率进行发射或者采用额外的带宽来改善系统性能，在下- 一代通信系统中都不 合适，与下一代通信系统的要求相违背。因此，关键是要在不需要额外的功率和 第一章绪沦 不牺牲带宽的情况下，有效的减少多径衰落对基站和移动台的影响。 理论上，抵抗信道衰落的最好方法是进行功率控制，也就是说如果发射端预 先知道信道条件，那么在发射的时候预先将信号变形来抵消衰落带来的影响。运 用这种方法有两个基本问题：最主要的问题是这种方法需要发射端有较大的动态 范围。这是因为为了克服定的信道衰落，发射端必须将发射信号功率提高到一 定程度。由于放大器的体积和成本的限制，这在大多数情况下是不实际的，而在 前面已经提到，纠错编码技术在某种意义上，可以认为是和提高发送信号功率等 效的，因此可以作为一种替代方法来采用；第二个问题是，发射端并不知道相对 于接收端的信道条件，除非在上行( 移动台到基站) 链路和下行( 基站到移动台) 链路 中使用相同的发射频段的系统中，因此必须将信道信息从接收端反馈给发射端， 但是这显然是不可取的，为了获得可靠的反馈信息，发射端又必须将发射端的信 道信息反馈给接收端，以使接收端能根据此信息进行功率控制将反馈信息发出， 所以进行功率控制的办法并不可行。 抗衰落技术的另一种有效措施就是采用分集技术，分集技术依目的可以为宏 观分集( m a c r o s c o p i c ) 和微观( m i c r o s c o p i c ) 分集。宏观分集是以克服氏期衰落为目的 的；按信号的传输方式可以分为显分集和隐分集两种。显分集指的是构成明显分 集信号的传输方式，多指利用多副天线进行接收和发射信号的分集；隐分集的分 集作用含在传输信号中的方式，在接收端利用信号处理技术实现分集，它包括交 织编码技术，跳频技术等。隐分集一般用在数字移动通信中，通常采用交织编码 技术将分集作用隐藏在传输信号之中，使得码字中的码元在传输过程中所遭受的 衰落互不相关，也可以获得抗衰落的效果。接收机可以用信道编码来检测或纠正 由于在无线信道中传输而引入的部分或全部的误码。由于解码是在接收机进行 解调之后执行的，所以编码被看作一种后检测技术。 既然编码和提高发送信号功率是等效的，而交织编码技术同时又可视为一种 隐分集技术，因此交织编码技术的研究对于移动通信极为重要。交织本质上还是 一种编码技术，而在纠错码技术的研究中，即使不是明确提到，交织也已经作为 一种提高编码增盏的手段面广泛采用，因此纠错码技术的研究事实上已经包括了 交织技术，这在t u r b o 编码技术中尤为明显，以后我们将会看到，t u r b o 码中的交 织技术对t u r b o 码性能的影响是举足轻重的。 纠错编码技术也可以和天线分集技术相结合来进一步改善无线信道的性能， 近年来兴起的空时编码技术就是这样一种技术。1 9 9 6 年，贝尔( b e l l ) 实验室提出了 空时编码授术的概念，将发射分集技术和接收分集技术结合起来，在各阵元的发 射信号之间引入时域和空域的相关，并且将信号处理技术与编码技术结合起来进 行处理，这样做巧妙地将纠错码技术和天线分集技术有机地结合在一起，既可以 有效的补偿信道衰减、增加系统的容量、抑制噪声和干扰，同时又可以获得很高 4t u r b o 编码技术及其在移动通信中的府用研究 的分集增益和编码增益，从而获得优异的性能。 1 3 本文主要工作 本文讨论t u r b o 编码技术，主要围绕并行级连卷积码( p c c c ) 进行，包括以下 方面： 1 主要对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 码性能的改善情况。 3 结合移动通信的实际考虑，将天线分集技术与t u r b o 编码技术相结合，分 析并讨论了空时t u r b o 码( s t t u c ) 的性能。 论文共分为五部分： 第二章主要对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 码( s t t u c ) 的设计和译码算法进行了详细分析，同时给出相应的仿 真结果。 第二章t u r b o 码的基本原理 第二章t u r b o 码的基本原理 t u r b o 码是由b e “o u ，g l a v i e u x 和t h i t i m a j a s h i m a 5 在i c c 9 3 会议上提出的， 在他们的文章中指出，采用大小为6 5 5 3 5 的随机交织器，并迭代1 8 次，码率为1 2 的t u r b o 码在a w g n 信道匕当e b n o o 7 d b 时的误比特率( b e r ) 1 0 一，达到了近 s h a n n o n 限的性能( 1 2 码率的s h a n n o n 限为0 d b ) 。t f 是由于t u r b o 码超乎寻常的 性能，使得它的出现立即引起了编码学界的极大轰动，围绕t u r b o 码的研究也成了 通信系统中的一个热点。对t u r b o 码的开拓性研究主要有以下几个方面：降低译 码器及译码算法复杂度方面的研究主要有r o b e r t s o n 6 ，b e r r o u 【7 等人：为了获 得更有效的带宽而进行编码和调制结合的研究主要有g o 趣8 】，w a e h s m a n n 9 ， r o b e r t s o n 1 0 等人；对于t u r b o 码性能的更深入的研究主要有b e n e d e t t o 11 ，1 2 1 及p e r e z 1 3 等人；h a g e n a u e r 1 4 ，p y n d i a h 【1 5 】将t u r b o 的概念扩展到了并行级连 分组码( p a r a l l e lc o n c a t e n a t e db l o c kc o d e s ) 上；j u n g 16 诗口n a s s h a n 研究了在短帧长 的情况下的编码性能，将其应用到语音系统中，并和b l a n z 1 7 合作将t u r b o 码推 广到c d m a 系统中：对于交织器的研究最初见于b a r b u l e s c u 1 8 1 等人的文章中。 下面我们将对t u r b o 码进行介绍，首先介绍t u r b o 码的编码原理，然后介绍译 码原理及一些常见的译码算法；接着给出t u r b o 码在加性白高斯信道下的性能分 析。 2 1t u r b o 编码原理 一个常见的t u r b o 编码器如图2 1 所示，两个分量编码器利用相同的输入信息 进行编码，但是在它们之间有一个交织器以保证输出的信息尽量不相关。我们以 分量码为递归系统卷积( r s c ) g 5 的情况进行讲解，用此方法构成的t u r b o 码即为传 统意义上的t u r b o 码，虽然更进一步的研究表明：用别的分量码( 如分组码) 1 9 2 2 1 也可以得到很好的性能，并且分量码也可以不仅局限为两个( 如三个或更多) 。但在 本章中我们只讨论这一类标准的t u r b o 码，r s c 编码器如图2 2 b 所示，这是一个 编码约束度k = 3 的r s c 编码器，生成多项式分别为( 1 1 1 ，1 0 1 ) ，写成八进制的形式即 是( 7 ，5 ) 。 一个码率为1 2 ，生成多项式为( g l ，c 2 ) 的r s c 码，总可以找到一个生成多项 式为( g 1 ，g 2 ) 的非系统卷积码( n s c ) 和它对应，反之也一样。对于一个约束长度为足 记忆长度为m = k - 1 的二进制n s c 编码器，设它的生成多项式为( g h g 2 ) n 己 g 1 = g l ， ，g 2 = 9 2 。) ) ，当k 时刻的输入比特为u k 时，输出的码字“是一个二进制比 特对( x ：，x ：) ，且它们可以由( 2 1 ) 式确定： t u r b o 编码技术及其在移动通信中的应州研究 r l x ：= g l ，一， m o d 2 9 1 - = 0 或1 i = 0 ( 2 - 1 a ) k 一1 x ：= 9 2 ，“ r o o d 2 9 2 i 2 0 或1( 2 - 1 b ) f - o 1 r 删 j余 上 i 交织器 复 fij 用+ 1 分量编码器2 卜一一- 图21t u r b o 编码器原理削 幽2 2 an s c 编码器图2 2 br s c 编码器 l 2 码率的递归系统卷积码( r s c ) 编码器是由对应的n s c 通过反馈连接并使其 中的一个输出等于输z t k 特u k 构成的，这是信息比特，记为x ：，另一路输出为检 验比特，记为“p 。此时移位寄存器的输入不再是输入比特讯，而是输ll l 特楸和 反馈连接模2 加后的结果卿，因此可得： 毋卸或1( 2 - 2 ) 将a k 代入( 2 1 b ) 中就可以得到校验比特工f ，图2 2 分别给出了约束长度k = 3 ， 生成多项式为( 7 ，5 ) 的n s c 和r s c 编码器结构图，通常信息比特序列只需要从任 何一个分量编码器中选取即可，考虑到实现问题，显然选取不经过交织的那一路 比特序列要方便得多。另外，为了能够提高编码速率，两个分量编码器的校验比 特序列经删余和复用后输出，信息比特序列一般不进行删余处理。 2dom 一女 g n + i “ l l i d 第：章t u r b o 码的基本原理 2 2t u r b o 码的译码原理 - 一一个常见的t u r b o 迭代译码结构如图2 _ 3 所示，分量译码器输出的外信息还将 作为另一个译码器的先验信息再次利用，同时为了使分量译码器输出的外信息与 另一个分量译码器接收到的信道软信息对应，两个译码器之间有一个交织器或者 解交织器相连。 劁2 3t u r b o 译码棘理 如图2 3 所示，在开始迭代时，分量译码器1 获得信道输出的软信息，计算出 软输出信息作为每个译码比特的估计值，同时这一部分软输出信息又作为分量译 码器2 的先验信息输入，同理，分量译码器2 利用此部分先验信息及信道输出的 软信息，计算出相应的软输出信息；在下一次的迭代中，此部分信息便可作为分 量泽码器1 的先验信息，如此反复即可进行迭代。显然，每增加一次迭代，都能 提高系统的性能获得更低的误码率，但是迭代次数的增加会增加系统的复杂度和 延迟，而且迭代次数越往上增加，所获得的改善越有眼，在以后的仿真将指出这 一点。 由于编码器中利用了交织，所以每个分量译码器的输出的外信息必须正确的 进行交织和解交织，以使它和另一个译码器接收到的信道软信息相对应，见图2 3 。 并且由于译码过程是一个迭代过程，因此每次迭代不只是利用最初的信道软信息 而且也利用了迭代更新后的信息。 当然，t u r b o 译码也不只局限于迭代译码的办法，事实上，m b r e i l i n g 2 3 ，2 4 1 等人就提出过非迭代方法的译码，而且经过仿真发现该类算法并不比一些常见的 迭代译码算法差，甚至比一些常见的迭代译码算法要好。但是在本文中只介绍基 于迭代译码原理的算法，非迭代的译码原理请参考文献 2 3 ，2 4 。 r1 1 u r b o 编码技术及其在移动通信巾的应用研究 _ _ 一一一一一 2 2 1 对数似然比 由于对数似然比( l l r ) 的概念极为重要，在此特意对它单独进行介绍，为了更 清楚的描述两个译码器之问交换的信息，r 0 b e r t s o n 2 5 引入了对数似然比( l l r ) 的 概念，他认为，两个译码器之间交换的信息其实可以简化为对数似然比的形式， 一个信息比特坼的l l r 可记为l ( u 女) ，l ( u p ) 以对数形式表征了可能取值的概率 比，l ( u 。) 定义为： m 渺倦蓦， ( 2 3 ) 本文中，蜥的可能取值为+ 1 和一1 ，而不是+ 1 和0 ，这并没有什么区别，在本 文中采用式( 2 3 ) 的形式定义l l r 。图2 4 给出了l ( u 。) 随取+ 1 的概率时的变化 情况。由图可见，当l ( u 。) 大于0 时，取+ 1 的概率更大；反之，则取一1 的概率 更大；而在三( ) = 0 的情况下，取十1 或者l 并不影响整个判决情况，所以利用 l ( u 。) 的符号就可以对进行判决。 萋0 一一 一 一 ， f 图2 4 l ( u 。) 随取十1 时的概率的变化情况 考虑到p ( u 。= 一1 ) = 1 一p ( u 。= + 1 ) ，( 2 - 3 ) 式可以写成： p m 1 ：坚要( 2 - 4 ) 1 一p ( u k = + 1 ) ( 2 5 ) 丽 去 = ：枷 百 i i 陧 第二章t u r b o 码的基本原理 问理： p ( u k = - 1 ，= 品= 嵩 ( 2 _ s ) ( 2 - 5 ) 式和( 2 6 ) 式可以写成。个统一的形式： 脚。圳，( 鲁筹p ”川2 p ， 注意到式( 2 7 ) q h 括号中的部分和求p ( ) 无关，因此它是个公共项，通常可 视为常数。前面定义的对数似然比只是基于非条件概率得到的，但是我们所获得 的信息通常是通过接收到的信道输出序列而得到的条件概率，因此假定接收到的 序列为y ，定义条件l l r ： 地出必爱蔷器) ( 2 - s ) 条件概率e ( u 。= 1 歹) 是关于译码比特的一个后验概率，这就是软输入软 输出分量译码器所希望获得的信息。同样，我们再定义另外一种条件l l r ，即发送 比特x 。为+ 1 或者一1 时，接收到y 。的条件似然比： 地小渺( 簧糍蓦) ( 2 - 。) 需要注意的是，式( 2 8 ) 和( 2 9 ) 的定义在形式上很相似，但是在概念上并不相 同。虽然这样定义会引起很大的混淆，但是由于它们在大量关于纠错码的文献中 已经被广泛的使用，因此我们依然沿用这种定义形式。 假定被编码后的符号比特矗采用b p s k 调制，并经过高斯信道或者衰落信道 传送，因此我们可得到在接收端接收为y 。的概率： m * i x e = 1 ) = 丽1e x p ( _ 参( y k - t - a ) 2 ) ( 2 _ 1 0 ) 其中，e 。为每个传输比特的能量，盯2 为噪声方差，口为信道的衰落幅度f 对于 无衰落的a w g n 信道，。= 1 ) ，于是利用( 2 1 0 ) 式，式( 2 9 ) 可以重新写成下面的形 式： t u r b o 编码技术及其在移动通信中的应用研究 l ( y 女 其中， l ，、 一们exp(-2(yk 卜沪1 唧c 一知丽 e x p ( 一三专一( y 女+ d ) 2 ) 。a “嘉 ) = 参4 叫。= 够( 2 - 1 1 ) ( 2 1 2 ) 上式中，t 被定义为信道可信度量值( c h a n n e lr e l i a b i l i t yv a l u e ) ，这是一个仅依 赖于s n r 和信道衰落幅度的量。因此，对于高斯信道下的b p s k 系统，信道的软 输出l ( y 。i ) 可以简单地由y 。和信道度量值t 相乘而得到。 在介绍过对数似然比之后，我们进一步介绍分量译码器的译码算法。 2 2 2 分量译码器的译码算法 为了能使分量译码器中的信息能被另一个译码器所利用，t u r b o 码通常采用迭 代译码的原则进行译码，因此分量译码器必须选择一类特殊的泽码器软输入 软输出( s i s o ) 译码器，这一类译码器的译码算法通称为s i s o 算法，通常有两大类： 一类是m a p 算法以及基于m a p 算法的一些改进算法；另一类则是基于v i t e r b i 算 法的软输出v i t e r b i 算法( s o v a ) 以及它的一些改进算法。下面我们将对这些算法进 行介绍。 2 2 2 1m a p 算法 本小节我们将介绍m a p 算法理论，如不做特别申明，以后的推导通常都是指 二进制形式。m a p 算法最初由b a h l ，c o c k e ，j e l i n e k 和r a v i v 等在1 9 7 4 年提出的， 为了纪念它的提出者，该算法也叫b c j r 算法 2 6 1 。由于m a p 算法实现起来比较 复杂，因此在t u r b o 码的出现之前并没有得到广泛应用。 对于给定的比特序列y ，m a p 算法需要给出译码比特巩为+ l 或者一1 的概率， 出2 2 1 节可知，这等价于求条件l l r l ( u 。jy ) ，其中： 坳加) _ l n ( 糍) ( 2 1 3 ) 运用贝叶斯公式，上式可写成： 上c “t i 歹) = n c ；i i ；i 端，= n c 鬻，c ：一。， 图2 2 所示的k = 3 的r s c 编码器，它的状态转移如图2 5 所示。对于k = 3 的 情况一共有4 个状态，而且每一个状态有两个转移状态，分别对应输入为+ 1f 实线 第二章t u r b o 码的基本原理 所示) 或者一1 ( 虚线所示) 的情况。由图2 5 可见，如果前一状态s k 1 和当前状态 已知，则蜥也完全可以知道。因此，= + 1 的概率等于输入比特= + 1 时所引起 的前一状态1 到当前状态s k 的转移概率，这是= + 】时对应的四个转移分支中 的一个( 如实线所示) ，而所有的转移分支之问是互斥的，因此，任意。个分支转移 的概率等于所有分支转移概率之和，所以，式( 2 1 4 ) 可以写成： 旧幽黔 = s t a s t = s “歹) = s r a s 女= s a 罗) ( 2 1 5 ) 幽2 5k = 3 的r s c 码的转移概率 ( 2 1 5 ) 式中，( s ，s ) 坼= + 1 表示当输入比特机= + 1 时，所对应的状态由 s k 一，= s 到s k = s 的所有分支转移，( j ，j ) j = 一1 类推，在以后的篇幅中将 p ( s 。= s t a s 女= s a 歹) 简记为p ( s ”s “歹) 。考虑到接收序列萝r i f 以分成三部分：在 当前转移接收到的码字只= ( y 2 ，y f ) ( 其中蚝表示接收到的信息比特，表示接收 到的校验比特) ，当前转移之前接收到的码字序列歹。，以及在当前转移之后接收 到的码字序列夕。因此，p ( s ”s “歹) 可以写成： p ( s ”j “萝) = p ( s s “乃。t “兄“职月)( 2 1 6 ) 假定信道是无记忆信道，而且当前转移之后接收到的序列歹。只和k 时刻的状 态s 有关，而和k 时刻之前的状态一无关，由l # n t n t y 式，可得： 1 2t u r b o 编码技术及其在移动通信巾的应| j 研究 p ( s “s “歹) = p ( y ，tl 一“j “只。t “歹t ) ) p 0 “s “只。t “歹t ) = e ( y 脚ij ) p ( s ”s “乃。 “或) = p ( 只，t | s ) p ( y k “j ) l 歹，。tl 一 ) ，p ( 乃。t “s ) ( 2 1 7 ) = p ( y 似15 ) p ( y k “s ) h ) p ( 歹心“s ) = 展( j ) “( s ，s ) 吼一( s ) 其中， k - i ( ，) = 尸( 只。t “s ) 为前向递推，p a s ) = p ( f j ，。fs ) 为后向递推， y k ( s ，s ) = p ( 或“s 1s 1 ) 是状态转移概率，为了更进一步说明它们之间的关系，将图 2 5 拓展成图2 6 。对所有通过网格图的状态s ，m a p 算法分别计算( s ) ，p a s ) ， 及y k ( s ，s ) ( k 2 0 1 ，n 一1 ) ，求出p ( s “s “刃，带入式( 2 1 5 ) 则可以求出l ( u 。l 夕) 。 y j 吼一i ( s 1 )“( s ，s )鼠( s ) 图2 6k = 3 时的m a p 算法译码网格图 因此，在给定接收序列兄的情况下，的条件l l r 为 l ( u + | 夕) = ( s ) y i ( 一，s ) a ( s ) ( 2 1 8 ) 这就是m a p 译码器所要求出的条件l l r l ( u 。l 罗) ，下面进一步介绍吼( s ) 屈( s ) ，及儿( j ，s ) 的计算过程。 一、前向递推( s ) 的计算 首先来看前项递推( s ) 的递推过程，由式( 2 17 ) t i j 得 彦豪 弟一草t u r b o 码f 一基本原理1 3 _ - 一 吒( s ) = r ( s t2 s a 夕+ ，) = p ( s “y j k a 死“s ) = 尸田，。f 厩“s “， ) p ( 溉“圳s ) ( 2 2 2 ) = 鼠( s ) n ( s 。，s ) 因此，可以通过( 2 2 2 ) 式由l ( s ) 后向递推出羼一。( s ) 的值，图2 7 中也同样给出 了如何由屈+ ( j ) 和y 。( 0 ，s ) 求出屈( 0 ) 的一个例子。 但是风( 5 ) 的初始化却不如a o ( s ) 嬲, q t ，因为由式( 2 。1 7 ) 可见，p a s ) 是 在给定当前状态s 后，将来接收到序列只，。的概率，因此当网格图在七= n 时，接 收序列已经终l e ，无法确定风( j ) ，它的初始化一般有下面三种建议 1 b e r r o u 等人 5 】建议将编码过程进行结尾处理( t r e l l i st e r m i n a t i o n ) ，使其 在n 时刻回到全零状态，此刻显然有： ? n ( 0 ) = 1 ，风( s o ) o 2 r o b e r t s o n 在文献 2 5 中建议对不进行结尾处理情况下初始化为： 风( s ) = 口( s ) ，g s ； 3 b r e i l i n g 在文献 2 7 】则认为，考虑到式( 2 1 7 ) ，有： 风一( 5 ) = p ( y ”= p 帆“j = h ( s 。，s ) 5 5 再来看式( 2 - 2 2 ) ，由它的递推关系，有： 风一。( j ) = 风( s ) y 。( s ，s ) 因此，比较( 2 - 2 3 ) 和( 2 - 2 4 ) 式，显然有： 风( s ) = 1 ，v s 。 ( 2 2 3 ) ( 2 - 2 4 ) 虽然b r e i l l n g 在理论上证明了对于所有状态s ，风( s ) 应该设为1 ，但是由( 2 2 4 ) 式可见，由于采用了递推过程，所以在网格接近结束阶段时的约束长度范围以内 的几步转移中，九( s ，s ) 的值必须严格设定，即必须将那些不可能的状态转移概率 设为0 ，这就使得计算过程变得复杂，因为此刻y e ( s ，s ) 不能利用统一的计算公式 求出。因此，一般采用b e r r o u 等人 5 】的建议也可以得到相同的结果，将编码网格 进行结尾处理( t e h n i n “o n ) ，将风( o ) 设为1 ，风( s o ) 设为0 ，并用相同方法对所 望l 堂堂壁 望 有转移状态下的扎( j 1 ，j ) 进行计算，该方法在实现上相对简单，在实际应用中较为 常见。 三、分支转移概率儿( s ，s ) 的计算 由分支转移概率儿( s 。，j ) 的定义，利用贝叶斯公式，可得： 7 k ( s p 5 ) 2 以溉“5 淞) 2 地拶“5 ) ，p ( s l ，) = p ( 或附“s 淞( ) ( 2 2 5 ) 其中是能够引起状态瓯一= ，到状态瓯= s 转移的编码输入比特，p ( ) 是 该输入比特的先验概率，由( 2 7 ) 式： r - j t ) 1 2 、 p ( 2 【南= 面胪。“”“= 哦尸m “( 2 - 2 6 ) 其中q = i e - i l ( u 葡) 2 是个依赖于三( ) ，而和坼无关的量。在式( 2 2 5 ) 中， p ( 夕e l “s ) 可以等价为p ( 死1 瓦) ，其中夏是引起状态瓯。：到状态：j 转移 的发送码字，因此对于无记忆信道，有： 尸( 兄 “j ) ) = j d ( 或f 瓦) = i 竺i p ( y 。f ) ( 2 - 2 7 ) y 一。，是接收码字瓦和发送码字瓦中的单一比特， 是每个码字中所包含 的二迸制比特数。假定发送的比特是在高斯信道中利用b p s k 方式发送的，则 发送的符号为十l 或者一1 ，于是p ( y 。，ix ) 可以写成： 以乩卜“卜志馘p ( - 2 e 盯b 2 ( 蝴咱2 )( 2 其中毛为每个发送比特的能量，盯2 为噪声方差，以为信道的衰落幅度( 在无衰 落的a w g n 信道下为1 ) ，将( 2 2 8 ) 式带入( 2 2 7 ) 中，有： 尸( 只j ) 2 兀熹e x p ( 一鲁( y 。吨彬) 1 = 1 吖z 厅盯2 0 - “。 。丽裔“旦2 0 2 善( 蚝2 枷2 2 2 圳( 2 - 2 9 ) 钉即p ( 参2 a 翮n ) t u r b o 编码技术及其在移动通信中的应_ l j 研究 其中，c 譬= 瓦厨1 e x p ( 一旦2 0 2 y t 2 ，j 疋i z l 一个并s n r 和接收序列歹有关的 量，而q ：= e x p ( 参喀瑚一卧嘉如2 ) 是一个只 h s n r 和衰落9 菖度有 关的量。因此几( ，s ) 可以写成 m s ) = c 趿严“，2 ) - c 譬e x p ( 参2 口善砀儿) = c e ( u k l ( u d 2 ) e x p ( 冬窆x k t y k l ) r 2 3 0 ) 三。由式( 2 1 2 ) 定义，c = q ) c c 娑与或者瓦无关，n 止l w 见n - - + n n _ 。 对于编码速率为1 2 的二进制的r s c 码，式( 2 3 0 ) 还可以进一步写成： 删一- c 一) ，2 ) e x p ( 等( 小硝朋 ( 2 - 3 1 ) 综上所述，m a p 算法的一些关键过程如图2 8 所示。 图2 8m a p 算法示意图 四、归一化处理 考唐到( 2 3 0 ) 式是由连续随机变量的概率密度计算得到的，y 。( s ，s ) 的值有可 能大于1 ，这会使得递推( ，j ) 和屈( 一，5 ) 时可能会引起溢出，因此有必要对 吐女( 5 ) 、p 。( s ) 进行归一化处理。 令： 碘) 2 器 弘) 2 蔬 ( 2 - 3 2 a ) ( 2 3 2 b ) 第章t u r b o 码的基本原理 注意到： 所以： 夕( 乃。) = p ( 妥= 驴只。) = ( s ) 将( 2 2 0 ) 式代入上式，并且分子分母同除毗p ( y 。) ，我们得到 蕊一；( ，) y k ( s ，s ) 酗曲。袁甄丽 f 2 3 3 ) 考虑划： p ( 只，| 只“) = 尹( 乃，“y j k ) p ( y ，“) = p ( 只| 乃。m ) p ( 只。壶+ ) p ( y j 。 ) 予 是有： g ( s ) y k ( s 1 ，s ) 鼠2 两习东j 酒瓦赢i 鼠( s ) 九( s , ，。- 脯 y j k + 1 ) 略( s ) p ( l 。) 厦( s ) y 。s ) 曩i 两s t 系再f 谚瓦- - 了 sj ，- - 。、s ) 扎( s ，s ) 。夏s 藏万瓣两( 2 - 3 4 ) 将( 2 3 2 ) 式代入( 2 1 8 ) 式，有： l ( u 女| 刃= 瓦一，( s 。) p ( y j 。) r k ( s + ，s ) 厦( s ) j p ( 歹mf 只。) ( 5 ，p 靠o + | ( j ，s ) ； u l 啄，( s ) n ( s 。，s ) 厦( s ) f j ) j 墨二：! 哌一，弧s 溉( s ) f j ) j “j = 一i 0 3 5 ) 这样，就完成了m a p 译码算法的推导过程，由瓦( s ) 、磊的定义可知，它 一篷吼 = p 一礴 ，lj；lll，l，jq，0l ! ! ! ! 虫! 垄塑垫查墨篓垄翌垫塑堕! 塑壁塑竺墨 们的初始化完全和a 。( j ) 、1 3 , ( s ) 相同。 2 2 2 2 改进静m a p 算法 2 2 。2 1 节介绍的m a p 算法比v i t e r b i 算法复杂德多两且硬判决输出的结果在 性能上几乎和v i t e r b i 算法一样。因此在它被发现之后的近2 0 年中几乎被忽略了， 然而在t u r b o 码的应用中又重新燃起了人们对它的研究兴趣，而且也可以进行改 进，健褥在几乎不降低性髓的情况下而降低复杂度。m a x l o g 。m a p 算法最初由 k o c h 2 8 和e r f a n i a n 2 9 等人提池，该鳟法将递摧过程转换到对数域内避行，然后 将结果作近儆处理，从而显著降低了复杂度，由于是一个近似过程，所以和m a p 算法相比，它的性能是次优的( s u b o p t i m a l ) 。不过，r o b e n s o n 等人【6 在t 9 9 5 年提 出蛇l o g m a p 算法，对m a x - l o g - m a p 算法中的近似怒理逶行了校正，所以可以 获得和m a p 算法相同的性能，但是复杂度比m a x l o g 。m a p 算法稍有提高。本节 将介绍这两静算法，它们都是m a p 算法的一稀改逮。 一、m a x - l o g - m a p 算法 在m a p 算法中和厢式( 2 - 1 7 ) 计算条件l l r l ( u 。iy ) 时，必须先计算下面三部 分酶络莱( 绉一诧后的l 妻程与茈粪似) ：1 ) 蓠向邋推嚷一，) ；2 ) 后向递捺孱( s ) ；3 ) 分支转移概率投( 一，s ) em a x l o g d v i a p 霉法将这些运算变换到对数域两，然嚣利 用下面的近似公