（通信与信息系统专业论文）turbo编解码的软件实现和应用.pdf

摘要 t u lb o 码是一种儿乎接近香农理论极限的前向纠错编码( f e c ) ，义司称作丌：行级联卷积码 j 五j ij 】低信啖比缄功率受限的条什r ，级联、迭代、软判决是其一i 个m 要概念。本论文洋细 搬述j t t l l b e 码的编译码原删：包括递门系统卷捌码( r s c ) 的结构阿个f 码的级联，交织 器的改n 蜮人衍验概率( m a p ) 算法，迭代洋码的思想和软输判决等。 往软俐实脱力l 乩本论文j hm a t l a b 编写r 通_ 【4 = | 的编码模块平针剥单个洚码器的基于m a p 钾江n o i ￥蚂摸块。n ：此基础上，j jc + + 州州上述基本模块，3 ：) 3 1 1 入j 7 高斯i t i 啭卢及对编泽码 输入数据的处理如交纵、解交织等，对编译码过稃进行仿真。其中，反馈泽码部分则是结合 j 成员阵m ，牡个从反馈迭代泽码的绱 = ：| 来实现的。本论文还将t ur b o 码廊川丁跳频短波数据 投刺系统，川d s p ( t m s 3 2 0 c 5 4 x ) 实现编码j ) j 能。 戈犍。 t m 确弼? a s j x 交织器? r s c 最大后验概率算法， a b s t r a c t t u r b oc o d e sa r eac l a s so ff o r w a r de r r o rc o r r e c t i o n ( f e c ) c o d e st h a t a p p r o x i m a t e l yr e a c h t h el i m i t sp r e d i c t e d b y s h a m l o ni n f o r m a t i o nt h e o r y t u r b o c o d e st h a ta r ea l s oc a l l e d p a r a l l e l c o n c a t i n a t e dc o d e sc a nb ea p p l i e di nl o w s i g n a l t o n o i s ee n v i r o n r n e n t t h et h r e eb a s i cc o l l c e p t so ft h a ta r e ：c o n c a t i n a t i o n ， i t c r a t i o n ，a n ds o f td e c i s i o n t h i sd i s s e r t a t i o ns p e c i f i c a l l yd e s c r i b e st h ep r i c i p l e o f e n c o d i l l g a n d d e c o d i n g o ft u r b oc o d e sw h i c hi n c l u d et h es t r u c t u r eo f r e c u l s i v e s y s t e m a t i cc o n v o l u t i o n a l ( r s c ) c o d e s ，t h e c o n c a t i n a t i o no ft w o c o n s t i t u e n te n c o d e r ，t h e d e s i g no fi n t e r l e a v e r ，m a x i m u map o s t e r i o r i ( m a p ) a l g o l i t h m ，t i l et h o u g h t o fi t e r a t i v ed e c o d i n ga n ds o f td e c i s i o n f r o mt h ev i e wo f i m p l e m e t a t i o n ，t h i s d i s s e r t a t i o nf u l f i l l st h e g e n e r a l e n c o d i n gm o d u l e a n dd e c o d i n gm o d u l ew h i c hi sb a s e do nt h em a p a l g o r i t h m f o rs i n g l ed e c o d e r b y m a t l a bp r o g r a m m i n g t h e nt h es i m u l a t i o no ft h ep r o c e s s o fe n c o d i n ga n dd e c o d i n gi sa c c o m p l i s h e d b yc + + p r o g r a m s t h a tu s et h ea b o v e m o d u l e sa n da d ds 0 1 t t en o i s es i m u l a t i o na n ds o f o et r a n s a c t i o no ft h ed a t a w h a t sm o r e ，t h i sd i s s e r t a t i o na p p l i e dt u r b oc o d e st of r e q u e n c y - h o p p i n gd a t a t r a n s m i s s i o ns y s t e ma n da d o p t sd s p ( t m s 3 2 0 c 5 4 x ) t op e r f o r mt h ef u n c t i o no f e n c o d i n g k e y w o r d s ：丁u r b oc o d e s ，c o n c a t i n a t i o n ，i n t e r l e a v e r , r s c , m a p 南开大学顶士论文 绪言 在当今的信息时代，通信技术得到了迅速的发展，无线通信成为目i ； 研究的 重要领域。在无线通信中，信道编码起着举足轻重的作用；这是因为无线通信的 环境常常是恶劣的，例如信道的信噪比很低，受多径衰落和多普勒频移等的影响。 所以寻求一种在极低信噪比隋况下的强大纠错工具就成了急待解决的课题。而 t u r b o 编码是近年来用差错控制提高误码率的有效手段之一，其超乎寻常的优异 译码性能使其已经被确定为第三代移动通信系统i m t - 2 0 0 0 的核心技术之一，作 为传输高速数据的信道编码标准。 t u r b o 编码器是出两个或两个以上的成员编码器并行级联形成的，其中的成 员编码器是一种递归系统卷积码( r s c ) ，两个编码器通过交织器( i n t e r l e a v e r ) 分 隔开，分别对输入的数据并行处理。其译码的思想是：将整个译码问题分成更小 的问题对其中的每个子码进行译码，获得局部最优解，并以迭代( i t e r a t i v e ) 的方式共享信息。译码器用后验比特概率的形式产生软输出信息，具体的译码方 法有最大后验概率算法( m a p ) 、l o g m a p 算法、m a x 1 0 9 m a p 算法、软输入软 输出维特比译码算法( s o v a ) 等多种，根据实际情况可选择最佳的译码方法。 目前，关于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 码在d s - s sc d m a 系统中的应用以及t u r b 0 编译码系统的实现等 等。 本文尝试将t u r b o 编码应用于无线跳频( f h ) 短波数据通信系统中，本文参 考了大量国内外的文献，对影响t u r b o 码性能的几个方面包括成员码的选择交 织器的设计，各种译码算法的优缺点进行了整理和比较。成员码编码器选择约束 长度n = 5 的递归系统卷积码，校验位经过删余( p u n c t u r e d ) ，得到i 2 码率的编 码结果；译码方案采用最大后验概率算法( m a p ) 迭代译码6 次。在具体实现 上，用m a t la b 完成了单独的编译码模块，整个编译码系统用c + + 编程实现并进 行仿真验证。其中，编码部分还用t i 公司的定点d s p 系列t m s 3 2 0 c 5 4 x 软件实 现，嵌入到跳频发射系统中。本文还对交织器的设计进行探讨，将保奇偶性融入 交织器的设计中，实现对所有信息比特的等差错保护，从而提高译码性能。 南开人学坝i j 论立 本论文结构共分四章。第一章介绍有关t u r b o 码的基本概念。第二章描述了 t u r b o 编码器的结构，交织器的设计及软件实现。第三章涉及t u r b o 译码器反馈 迭代的原理和几种译码方法的比较。第四章详细讨论了m a p 算法，设计了基于 此算法的译铲5 模块，并从穆休卜仿真了编译码过穰。 由于本人水平有限，论文中难免会存在着错误和不足之处，望各位老师批评 指i f 。 - 2 南开人学坝j ：论文 第一章t u r b o 码的基本概念 1 1t u r b o 码的提出和国内外的研究现状 在1 9 9 3 年的国际通信会议( i c c 9 3 ) 上，两位任教于法国不列颇通信大学 的教授c b e r r o u 和a g l a v i e u x 首次提出了种新的信道编码方案一t u r b o c o d e 码，它由于很好地应用了s h a n n o n 信道编码定理中的随机性编、译码条件，从 而获得了几乎接近香农理论极限的译码性能。其结构为：子码采用约束长度为5 ， 生成式为( 3 7 ，2 1 ) 的递归系统卷积码，交织器采用的是2 5 6 2 5 6 的伪随机交 织。通过修正b a h l 译码算法【2 1 仿真，在a w g n 信道下，l 2 码率的t u r b o c o d e 经1 8 次迭代译码后可得到：在e b n 0 = 0 7 d b 时，比特误差概率为1 0 一。 自t u r b o - c o d e 提出以后。由于其优异的性能，立刻在编码领域引起了极大的 兴趣，人们对它作了许多方面的研究。h a g e n a u e r 对s o v a 进行研究f 3 1 ，认为在 a w g n 信道下s o v a 应用于迭代译码可获得与修正b a h l 算法相近的性能；成 功地将s o v a 应用于t u r b o c o d e 的迭代译码。 p j u n g 等首先研究了在a w g n 信道下短帧传输( 1 9 2 比特) 的b e r 和f e r ， 提出了一种短交织长度的伪随机交织器的设计方法。子码为( 2 3 ，3 5 ) 的 t u r b o c o d e 在最佳交织器下，采用m a p 算法( 修正b a h l 算法) 经1 0 次迭代 后其性能为：当e b n 0 = 2 0 d b 时，b e r = i 2 x1 0 ，f e r j 2 5 1 0 d 。 目前国外对于t u r b o c o d e 的研究已不仅限于理论上和计算机仿真，已经着手 进行实用化研制。最早的实验产品是采用两个约束长度为3 的八状态卷积码作予 码，交织长度为3 2 3 2 的t u r b o c o d e 。采用两次半迭代译码，( 总运算量为每 个子码最大似然维特比译码运算量的9 倍) 当e b n 0 = 2 0 d b 时，测得比特误差概 率为9 0 1 0 。另外美军已成功地在一块o s p 上，实时地实现了交织长度为2 3 7 2 的t u r b o c o d e 编码的线性调频调制解调器。测量出在a w g n 信道下，误码率为 1 0 一1 0 5 时，其编码增益比采用卷积时要高1 3 d b ，且在短波信道下有更高的编 码增益，在误码率为1 0 。4 时，其编码增益比采用卷积时要高2 5 d b 。 t u r b o 码目前已经应用在i n m a r s a t 移动卫星通信系统中；c d m a 多用户 检测中：第三代移动通信i m t - 2 0 0 0 还将t u r b o 码作为其传输高速数据的信道编 码标准。但目前还没有将t u r b o 码应用于跳频方面的研究，本论文在依据经典的 t u r b o 编码理论，结合跳频中的实际应用，采用短帧的形式将t u r b o 码作为跳频 南开人学吲l j 论立 前端的信道编码，并通过实验进行了软件仿真。 1 。2 并行级联卷积码( t u r b o 码) 在信道编码中，一般说来“好码”意味着以下几点：1 ) 编码结果有良好的码 距特性：2 ) 译码器等价于或逼近于最大似然( m l ) 译码；3 ) 能以合理的运算 量构造编码器及译码器。当信噪比比较高时，噪声引起的空间位置偏移d 。较小， 此时译码的性能主要由最小汉明距d 。决定，最小汉明距越大则译错的可能性 越小，这是我们熟知的情况：但当信噪比较低时，噪声引起的空间位置偏移很大， 此时译错为最小汉明距处的码的概率还不如译错为其他码的概率大，故在低信噪 比条件下应用时，码距分布比最小码距对码的性能更具有决定性。此时好码的特 征是，错误概率不可忽略的码的总个数少即码距分布的尾部较小。 无论从信息论还是从编码理论看，要想尽量提高编码的性能，就必须加大编 码中具有约束关系的序列长度。但是直接提高分组码编码长度或卷积码约束长度 都使得系统的复杂性急剧上升，在这种情况下，级联码既可以减少译码的复杂性， 同时又能够得到等效长码的性能，所谓级联码就是以多个短码来构造长码。级联 码方面的大量研究最终结出了t u r b o 码这样一个硕果。t u r b o c o d e 在吸取传统级 联码优点的基础上，采用了“并行级联”结构的全新思想。典型的t u r b o c o d e 的结构如图1 1 所示。 k r 删 d k 。e i 截 趣蕃 和 复 用 图1 1 t u r b o c o d e 编码器结构 它通常由两个结构相同的递归系统卷积( 通常称为子码) 编码构成，r s c t 直接对进入的信息序列进行编码，得校验序列；同时，将信息序列以通过交织 4 南开人学硕l 论文 器交织后的序列一送往r s c 2 进行编码，得到校验位如，t u r b o c o d e 码字就是 由信息序列后接两路校验序列构成。成员编码器所产生的校验位( y y ：。) 可 经不同删截矩阵删除后得到不同码率的t u r b o 码。 1 3 迭代译码 传统的级联码的结构是串行结构，其性能完全取决于内码输出的误码率和外 码的纠错能力，内外码之间最多只是单向( 由内码送至外码) 传递判决比特可靠 性的软信息，没有真正意义上的信息相互交换。于是人们考虑将外码也进行软输 出译码，并将其软输出信息反馈到内码译码来提高整体性能。显然传统的串行级 联码结构是难以实现这种反馈的，因为它的编码关系为： c l = y ( x ) ，外码 c 2 = g ( c ) ，内码 因此外码译码输出的关于符号x 的信息不能直接提供给内码译码器，为了能 够得到反馈结构，需要内外码均为系统码。在后面我们将会看到，并行级联系统 码能很好地满足这个要求( 当然串行结构也是可行的) 。它是对输入信息序列及 其交织后的罱换序列分别进行系统编码，这样两个子译码嚣之间就可循环交换信 息，实现反馈迭代译码。译码器的工作像t u r b oe n g i n e 一样，故称为t u r b o 码。 在对传统串行级联码做了上述结构和算法上的修正后，就引出了性能优异的 并行级联码t u r b o c o d e 。 1 4 软输出译码 传统的译码方法是解调器直接对接收信号进行硬判后送至译码器，即解调器 送给译码器的只有0 和1 两个值，而没有给出0 和1 判决的可靠性信息，我们称 之为硬判决译码。但是如果解调器将接收检测样本直接( 或量化后) 送入译码器， 译码器利用样本中的额外信息进行译码，则获得的性能要比硬判决译码好，这种 译码方式称软判决译码。在理论上，软判决译码比硬判决译码要好大约2 d b ，对 只有单个编码的传输系统来说，软判决译码是最佳的方法。 南开人学顺卜论义 由于一般的译码方法只能提供硬判决输出，最早的级联码外码译码均为硬判 决译码，为了提高译码性能，使外码译码也有可利用的软信息，人们提出了软输 出( s o f t o u t p u t ) 算法，软输出是对每个译码判决输出比特可靠性的度量，它是 一个连续的实值估计。级联码中采用软输出的内码译码器不仅改变了错误图样的 分布，同时它还相当于一个噪声抑制滤波器，有效地改善了接收信号的信噪比。 后面我们将看到在迭代译码中软输出信息对下级译码起着非常重要的作用。 目前获取软输出信息的算法主要有两种，第一种是最大后验概率( m a p ) 算 法，又叫b c j r 算法，对于在离散无记忆信道下具有有限状态马尔可夫特性的编 码，它是一种提供了逐符号或逐比特似然值的最优算法。对于线性码，m a p 算 法是获得最小符号误差概率的最佳译码方法。第二种是软输出维特比算法 ( s o v a ) ，该算法的复杂度要比m a p 算法小，仅为标准维特比算法运算量的两 倍多，它只能获得最小差错事件概率，但因其计算量小，比较适合于在工程上应 用。 1 5t u r b o 码的实际应用 1 5 1 在第三代移动通信系统中的应用 第三代移动通信系统i m t - 2 0 0 0 的目标是提供覆盖全球的多种高层次综合业 务、多种系统和多种运营环境的大容量、高速率、高质置、高灵活性、功能强大 的移动通信系统，其特点是多媒体化和智能化，要求能够为用户提供多元传输速 率、高性能、高质量的服务。为支持大数据量的多媒体业务，必须在有限带宽信 道上高速传输数据。由于无线信道传输媒质的不稳定性和噪声的不确定性，一般 的纠错码很难达到较高要求的业务质量( q o s ) ( 一般要求误比特率b e r o = 辛c i 。= 1 ，l ( c i i ) ( o = 寺( 女= 0 ( 3 1 9 ) 由此可见，对联合概率砧的求解是最大后验概率译码的关键，为此，我们 对磁进行分解，这种分解具有实际的物理意义( 具体的m a p 算法见第四章) 。 定义出一，口? 和卢捃”三个量度： 口? ；p ( r ? 一d k = f ，s = ，l ，r ，) = p ( r s k = m ) ( 3 2 1 ) 彪p = p ( r l d k = f ，瓯= 删，也) = j p ( 碟慨+ = ( f ，小) ) ( 3 2 2 ) 则掣= 篙 z 。， 簖舻硝川 最终“引刊0 9 l 豪雨萨l 。2 4 3 3 2m a x l o g m a p 算法 m a p 算法的计算量主要集中在对4 ，口? 和卢四川的求解上。将式( 3 2 0 ) 中的r k 分成x k 和y k 两部分，在m a x 1 0 9 m a p 算法中。考虑到对a w g n 信道， 有 m t 乇s 圳。击侧一击b t 吲2 ) 2 5 ) 其中，n d 2 是a w g n 信道噪声的功率谱。c k ；( x k ，y k ) 和r = ( x k ，y k ) 分别为编 码码字和接收码字。利用下式作简化 l o g ( 8 而+ a + p 氏) m f i a l 川x d ( 3 2 6 ) 从而对数似然比可以表示成： l ( d ) zm a x ( 1 0 9 ( 6 2 ”) + l o g ( 口? ) + l o g ( 尸瑞”) 一m a x ( 1 0 9 ( d o ”) + l o g ( 口? ) + l o g ( j 口锻”1 ) f 3 2 7 、 2 8 南开人学坝士论文 3 3 3l o g - - m a p 算法 在m a ) ( 一l o g m a p 算法中的近似取值使得译码性能下降 如何精确计算l o g ( e 4 + 人+ e 吒) 的值。山j a c o b i a n 对数算法 l o g ( p 4 + e d 2 ) = m a x ( 8 1 ，岛) + l o g ( 1 + p i 点一以1 ) 若记a = 8 5 - + a + p 瓯- = e 6 则可通过递归计算得到l o g ( e 4 + 人+ e 以) ， 从而问题归结于 ( 3 2 8 ) r 3 2 9 ) l o g ( e 4 + 人+ e 矗) = l o g ( a + p “) = m a x ( 1 0 9 a ，占。) + l 0 9 0 + e - i l 。8 6 一晶i ) = m a x ( 彩n ) + l 0 9 0 + e - l , s - , 1 )( 3 3 0 ) 然后再按m a p 算法来计算每个信息比特的对数似然比。 3 3 4s o v a 算法 在卷积码的译码中采用维特比译码算法可使误码率减至最小并且译码速度 较快。但对每一个译码比特来说，标准维特比算法无法给出该比特的后验概率 ( a p p ) 等软输出信息。因此在t u r b o 码译码中要对维特比算法进行修正，就是 在每一次删除似然路径时保留一些必要的信息( 即外部信息) ，把这一信息作为 维特比译码的软输出，这就是软判决维特比译码( s o v a ) 算法的核心思想。在工 程应用中，由于s o v a 算法的运算量较小，而且可以采用滑窗法，从而可以大大 减小时延，因此更适合于工程应用。 我们在此对该算法作一个简单的介绍，对于a w g n 信道，定义从状念到状 态的路径度量函数为： l o g y k ( r k , m , m ) = 学+ 学+ j 1 岷d k + k ( 3 ，- ) 若设译码深度为6 ，在k + 6 时刻，选择出一条路径度最大的路径，相应得到 k 时刻的硬判决d k 。最大路径上共有8 + 1 个状态节点，每个节点有一条幸存路径 和一条被丢弃的路径，两条路径的度量值之差记为。 1 0 ( i = 0 ，l ，6 ) 。所 以，最后软判决输出为 l ( d ) = d m i 缺a + = 4 x t c 5 。+ + m ( 3 3 2 ) 根据上述描述，s o v a 算法可以分为以下几个步骤完成： 2 9 南开人学嘲小论史 ( 1 )计算路径度量与度量差： ( 2 )更新可靠性度量： ( 3 )减去内信息，得到下一步所需的外信息值。 本节中提到的三种简化算法各有优缺点，在工程上针对不同的系统要求， 可以选择使用。 3 3 5 各种算法的比较 在译码性能方面，m a p 算法和l o g - - m a p 算法的效果最好。最差的是s o v a 算法，它与m a p 算法相差o 5 - - l d b 左右，并且随着信噪比的增大差距没有降 低的趋势。m a x l o g m a p 算法的性能介于两者之间。 造成上述译码算法性能上的差距的主要原因是对判决路径的选取方式，对于 k 时刻的软判决输出，可以把到达最终状态的所有路径分成两大类，即d k = o 的 路径集u o 和d k = 1 的路径集u i 。m a p 算法和l o g - - m a p 算法都是分别计算u o 和u i 中所有路径的后验概率之和，并以两者的比值作为d k 的软判决输出。因此 在理论上，两者应具有相似的、较优的译码性能。 而对于s o v a 算法和m a ) ( 一l o g m a p 算法，可以证明，它们的硬判决输出 是相同的。两者性能差别的来源在于不同的软判决信息获取方法。不失一般性， 假设最大路径是属于u 0 的全零路径，m a x l o g m a p 算法是从u i 中选择出 条度量值最大的路径，然后将该路径与全零路径度量值之差作为k 时刻的软判决 输出。也即m a x - - l o g - - m a p 算法以选取u o 和u l 路径集中最大值路径来代替l o g m a p 算法中求u o 和u i 中所有路径之和的操作。随着信噪比的提高，u o 和u 1 中都会有一条路径的度量值远远大于其他路径的度量值。这时，m a ) 【一l o g m a p 算法中所用的近似会变得很准确。而对于s o v a 算法，它仅仅是沿着最大度量路 径( 此处为全零路径) 回溯，寻找u i 路径集中与全零路径上的状态节点相交的 度量值最大的一条路径，并认为这就是u l 路径集中具有最大度量值的一条，然 后用于软判决输出。而实际上，u l 中度量值最大的一条路径并不一定与全零路 径相交，即使在信噪比增加的情况下也不一定，这就造成了软判决信息中的误差， 最终影响译码性能。 虽然这些次最优算法在t u r b o 码的译码过程中会使性能有所下降，但其运算 量却大大减少了，使实际的译码器硬件电路的设计实现成为可能。 3 0 南开大学倾士论文 第四章基于m a p 算法的反馈译码器 4 1m a p 算法 前面已经提到t u r b o 码的译码过程开始于每个数据比特后验概率( a p p ) 的 形成，接着足选择对应于最大后验概率的数据比特。随着受干扰的编码比特序列 的接收，后验概率判决过程使得m a p 算法可以确定每个比特时间内最可能传输 的信息比特。这不同于维特比算法( 、，a ) ，在那里每个数据比特的后验概率不存 在，维特比算法寻找的最可能传输的序列。当译码误比特率p b 很小时，m a p 和 前文提到的软输出维特比算法( s o v a ) 之间的性能差异几乎没有；但在高误比 特率p b 的情况下，m a p 性能比s o v a 要优予o 5 d b 或更多。 实际上，m a p 算法的实现有些类似于编码比特分组上的双向维特比算法。 只要这个双向计算得到分组的状态和分支量度，分组中每个数据比特的a p p 和 m a p 便可得到。我们在这里描述的a w g n 信道模型下系统卷积码的m a p 译码 算法的推导思想源自p i e t r o b o n 的著作【6 】。首先求出a p p 的比率，称为似然比a ( d k ) ，或其对数形式l ( d k ) ，称为对数似然比( l l r ) ，如前面式( 3 1 8 ) 所示： 埘沪崦冈 ( 4 1 ) 其中，露是二进制序列月1 ( 从时刻k = l 至某个时刻n 的观测值) 的条件 下。数据d k = i 和状态s k = m 的联合概率，正如式( 3 1 6 ) 提到的： 砧= 尸( 矾= f ，& = m r i ”) ( 4 ，2 ) 上式中，吖表示通过信道传输、解调，以软判决的形式输入译码器的受干 扰编码比特序列，其下标表示开始比特的序号，上标表示结束比特的序号。实际 上，m a p 算法要求解调后的输出序列每次以n 比特的数据分组送入译码器。理 解了科的意义后，我们可以将r ，分成三部分，写成如下的形式： r = 尺，r ，r 。)( 4 3 ) 在上一章中简单介绍m a p 算法时提到要将联合概率置分解成三个度量 a ? ，p 删w 和咧”，通过分别求这三者来得到联合概率。其实，这种分解是根据 南开人学颂l + 论义 贝叶斯准则而来的，为了方便应用该准则，将式( 4 2 ) 分割为a ，b ，c ，d 四部 分。这样，式( 4 2 ) 可写成如下的形式： 嚣= p ( d 。= f ，s = m l r - , r 。，r 。, v ) = 1 , ( , 4 1 a ，c ，d ) ( 4 4 ) 我们再凹坝f 贝叶斯准m 0 ： 刖i s , c , d ) = 鬻 ：曼! 纠笪：! ：竺! ! ! 兰：! ! 呈! = e ( a l a , c 1 , d 试) e ( 石d i a 矿, q p ( a , c ) ( 4 ，5 ) j p ( 露，c ，d ) 、 4 将该准则应用到式( 4 4 ) ，在这里使用贝叶斯准则实质上是将求后验概率转化 成求先验概率和其他的条件概率。 戤= 尸( r ? 一i d 。= ，s = m ，r f ) p ( r l 。i d 。= f ，s 女= m ，r 。) j d ( 以= f ，咒= 卅，峨) 尸( r )( 4 6 ) 其中，尺= r 。，r 。在后面的讨论中，羽1 , t f l 将逐个给出式( 4 6 ) 右端的三 个分子的定义和推导，分别称为前向状态量度、后向状态量度和1 分支量度。 4 2 状态量度和分支量度的定义 首先我们定义式( 4 6 ) 右端的第一个分子为时刻k 和状态m 下的前向状态 量度，并对其进行化减，表示为： j p ( 月? t d 。= f ，瓯= 肌，月) = p ( j r ? 一i 乳= 川) = 口? ( 4 7 ) 上式化减的依据是d k = i 和则与r i k 。1 是非相关的，这是由于假定s k = m 表示 时刻k 时的状态，时刻k 以酶的事件则不受时刻k 以后的观察所影响。换句话说， 过去的不会被以后的影响，所以，p ( r i k 1 ) 与d k = i 和序列r k “是相互独立的。但 是由于编码器具有记忆性，编码器状态s k = m 是建立在过去的基础之上，所以这 一项是相关的，在表达式中必须保留下来。式( 4 7 ) 表示了时刻k 的前向状态 量度a ：( 作为过去序列的概率) ，只取决于此序列引起的当前状态，而与其他无 关。 类似地，式( 4 6 ) 右端的第二个分子可以理解为时刻k 和状态m 下的反向状各 3 2 商开入学硕1 ：论义 量度甜m 出剥其进行化减如式( 4 8 ) 所示 j d ( r 。nd 。= f ，s = 删，r ) = p ( r 2 + 。b + i = f ( i ，m ) ) = 础? ( 4 8 ) 其中，f ( i ，m ) 表示对给定输入d k = i 和状态s k = m 的情况下的下个状态， 也就是s k m 卢0 j ，为时刻k + l 和状念s k + l = f ( i ，m ) 卜的反向状态量度。式( 4 8 ) 将下一个时刻k + l 的反向状态量度，表示为将来序列的概率，此将来序列依赖于 将来时刻k + l 的状态，而这状态又是输入比特和当前时刻k 的状态的函数，这就 是有限状态机的基本定义。 最后，我们来看式( 4 6 ) 右端的第三个分子，定义其为时刻k 和状态m 下的分 支量度，表示为咧一。因此，有 尸( d k = i ，瓯= 用，r ) = ” ( 4 9 ) 下面，我们将式( 4 7 ) ，( 4 8 ) 和( 4 9 ) 式代入式( 4 6 ) ，就得到有关联合概率更简 洁的表示，即 ”= 篙 。 将联合概率的标到式( 4 1 0 ) 代入似然比公式即式( 4 1 ) ，有 口? 舻觥” 懈卜长丽 煅“矾卜1 0 氛丽萨 f 吖剧1 f ”。l l ”1j ( 4 1 1 a 、 ( 4 1 1 b ) r ( d 。) 是我们蜮终得到的笫k 个数搬比特的l l r ，将其川一j i 判决，t ! l j - i i 褂至0 译码的结果，这罩对数的底数通常取为e 。 4 3 状态量度和分支量度的计算 4 3 1 前向状态量度的计算 我们从前向状态量度的定义式( 4 7 ) 开始求解d 厶它可表示为从时刻k - 1 起所 有可能的转移概率之和，如下式： - 3 3 南开人学倾i j 论立 口卜p ( d 。= ，瓯l = m 。，月i s , = 珊) ( 4 1 2 ) ，= 0 将r i 。1 改写成 r l “2 ，rk _ j m q 形式，再次利用贝叶斯准则，得 尸( 月h 墨= m ，d 。= 工s k l = 肌，r 。 = 0 ，( ，l = ，n i i = ，j ? 。，凡 一l f s = ”2 ) ( 4 13 a ) 口? 7 = 户( 月? - 2 l 瓯一，= 6 ( ，州) ) ，( 以一。= ，s k 一= 6 ( ，m ) ，r ) ( 4 13 b ) j = 0 上式t 扎b ( j ，m ) 表示通过对应。- j 二输入j 的前一个分支，出状态m 后i 甸返吲 的前一个状态。式( 4 。1 3 b ) 可以替代式( 4 ，1 3 a ) ，因为已知时刻k 。1 的状态1 2 1 和输入 j ，可以完全定义到达状态s k = m 的路径。仔细观察式( 4 1 3 b ) 中的右边第一项， 正符合式( 4 7 ) 的形式，只不过是对应于k 1 时刻的前向状态量度a 出”：同理， 右边第二项符合式( 4 。9 ) 的形式，表示k l 时刻的分支量度。利用式( 4 r 7 ) 和( 4 9 ) 来 简化式f 4 1 3 ) ，【；】j 得： 口甜”占i , b “” ( 4 1 4 ) 式( 4 ，1 4 ) 表明，时刻k 和状态m 下的新的前向状态量度可通过从时刻k - 1 的 两个加权状态量度相加得到。这个权值包括对应于数据比特0 和1 的转移的分支 量度，如图4 1 a 所示。 k - ik kk + i d f ( a ) 前向状态培度 口：= 口川b ( o 川0 一, b l 旧川+ d 心川酬0 “m j = o p 紫 ( b ) 后向状态龄度 p ；= p 冀4 6 ；4 + 母i i 4 7 6 ：8 剐4 1 年f 1 成? f ”，计掉的豳】0 ) = 甚之示 卜图中，矧4 1 a 所示为参数口的两种不同的表示。用口盘表示时k - 1 的d u 。3 4 - 南开人学硕i j 论文 向状态量度此州有两种i 可能的潜在状态( 取决fj = o 或i ) 。用。? 表示时刻k 的前向状态量度，前一时刻的两种可能转移在时刻k 终止于相同的状态m 。 4 3 2 后向状态量度的计算 类似j in 州q 状态量度，我们根据式( 4 8 ) 来推导后向状念量度的递摊关系，其 中卢搿”l _ e ( r l l l s = f ( i ，) ) ，则有： 历= j d ( 尺，k = ) = p ( r 。，r i | 只= 州)( 4 1 5 ) 可以将群1 表示为到时刻k + l 的所有可能转移概率的总和，如( 4 1 6 ) n 示： 彤= p ( d k = 工最+ ，= 搠，& ，陵= 磁) ( 4 1 6 ) j = 0 根据贝l 】圻准则 雕= 尸( r 。i s , = 珊，以= ，s 。= 朋。，r 。) p ( 矾= 工s 。= m ，r 。i s , = ) l ，= 0 ( 4 i 7 ) 由式( 4 1 7 ) 右边第一项中的s k = m 和d k = j 就可完全定义到达s k + l = f ( i ，m ) 的路 径，即给定输入j 和状态m 下到达下一状态的路径。因而在这些条件下，允许将 式( 4 ，1 7 ) 第二项中的s k + i = m 替换为s k = m ，得 所= p ( r ，i s 。+= f ( j ，m ) ) 尸( 以= ，s 。= m ，r 。) = 鄙”卢搿川 ( 4 18 ) ) - o 式( 4 18 ) 表明| 卜j 刻k 和状态m 下的新的反向状态量度，可以通过由时刻k + l 的两个加权状态量度相加得到，这个加权包括对应于数据比特0 和l 的转移分支 量度。图4 1 b 所示为参数b 的两种不同表示。用彪，肿表示时刻k + l 的反向状态 量度，此时有两种可能的潜在状态( 取决于j = 0 或1 ) 。用卢r 表示时刻k 的反向 状态量度，这t - ，n , - t 亥0k + l 的两种可能的转移来自相同的状态m 和时刻k 。图 4 1 中计算前向和反向状态量度的图解与实际编码的路径网格图一致。 m a p 译码算法的实现与维特比译码算法有一些相似之处。在维特比算法中， 我们将分支量度与状态量度相加，然后进行比较并选择最小距离( 最大似然值) 以获得下一个状态量度。这个过程称为相加一比较选择。在m a p 算法中，将 南开人学坝t i j 论文 分支量度与状态量度相乘( 对数形式的十h 1 j i i ) ，然后将它们相加f f l j - , l ：是比较从而 得到下一个前向或反向状态量度，如图4 1 所示。通过维特比算法寻找最可能的 序列；所以，为了找到最好的路径，必须持续进行比较和选择。而通过m a p 算 法，得到一个软数据( 对数似然值) ；所以，这个过程利用了一个时问间隔中所 有可能的转移景度，以获得该时间问隔内虽好的数据比特整体统计值。 4 3 3 分支量度和后验似然比的计算 最后，我们来考察分支量度的计算，对式( 4 9 ) 展丌，展成( 4 1 9 ) 所式的形式： 瓯”= p ( d 。= ，瓯= m ，r ) = p ( r 女l 以= f ，墨= m ) p ( s k = 埘p 女= i ) p ( d = j ) ( 4 1 9 ) 在上式中，r k 表示接收序列 x k ，y k ，x k 是含噪声的接收数据比特，y k 为相 应的含噪声的接收监督比特。由于噪声对数据比特和监督比特的影响是独立的， 当前状态与当前输入也是相独立的，所以当前状态可以是2 。个状态中的任意一 个。u 是卷积码系统记忆元素的数目，即移位寄存器的个数。这个编码的约束长 度k 等于u + 1 。表示成公式的形式： p ( s k ：m | 矾：f ) ：百1 ( 4 2 0 ) 以及 一= j d ( “l 以= f ，瓯= m ) p ( y 。i d 。= f ，瓯= m ) 鲁 ( 4 2 1 ) 其中，一定义为p ( d k = i ) ，是d k 的先验概率。 根据相关的概率论我们知道，随机变量x k 取值x k 时的概率p ( x k = x k ) 与概率 密度函数p 。( h ) 有关，即 e ( x = h ) = p 。( x k ) 呶( 4 2 2 ) 为了表达方便，取值为的x k 随机变量x k 通常记为x k ，与式( 4 2 1 ) 5 b 的x k 和 y k 具有相同的意义。这样，对于a w g n 信道，其噪声均值为0 方差为o2 ，利用 式( 4 2 2 ) ，将式( 4 2 1 ) e ? 的概率部分替换为其相应的概率密度函数形式，可得到式 r 4 2 3 ) ： - 3 6 - 南开大学预j 。论文 弘矗刊一圭c 孚十击e x 帕丝笋巾：， 、乃。、荨簖e x p ( 等i , m ) 硝 似巩卜以姒瞰幕每 矿a ? e x p ( 掣) 觥 哪一p ( 等) 群 ( 4 2 5 ) 对式( 4 2 5 ) q j 自 ja ( d ) 取对数得到式( 4 2 6 ) ，由此可见，最终软数据( 0 。) 由三个 - 3 7 南开人学坝 j 论文 的系统卷积码编码器，约束长度k = 3 ，编码效率为1 2 。输入序列为d 一 l ，o ， 0 ) ，对应于时刻k = l ，2 ，3 。连续地从序列u = l ，0 ，0 中取出一比特，然后再 从校验比特序列v = 1 ，0 ，】) 中取j n 。一比特就得到系统形式的输f ：f 编码比特序列。 在每种情况下，最左边的比特都是最早的比特，所以输出序列为1 1 0 0 0 ，双 极性形式为+ 1 + 1 1 1 1 + 1 。 例42 m a p 译码举例 南开人学坝l + 论立 图4 2 表明某个假设的噪声矢量n 。和n 。对序列u 和v 造成干扰，所以可以表 示为x = u + n 。和y = v + m 。如图4 ，2 b 所示，时刻k = l ，2 ，3 到达译码器的值分别为 1 5 ，0 8 ，o 5 ，0 2 ，一0 6 ，1 2 。图中分别用l 和“o 表示对应数据比特1 和o 的 先验概率，并假设对于所有时刻数据都是等概出现的，即n 。= no = 0 5 。在这个例 子中，所有的信息都可用于计算分支量度和状态量度并将它们的值送入图4 2 c 所示的译码器网格图。在这个网格图中，时刻k 和k + l 之间的转移对应于数据比 特d 。，在时刻k ，编码器处于某个状态m ，时刻k + l 则转移到下个新的状态。 在图中，每个网格转移的码字比特u k ，”k 标在各个转移线上( 仅对k = 1 ) 。 已知x k 和y k ，就可以利用我们上文描述的最大后验概率算法来进行译码，网 格图中共有4 个状念，用a = 0 0 ，b = l o ，c = 0 1 ，d = l l 表示。在这个例子中，具体 的译码步骤如下： ( 1 ) 计算8 个分支量度：这里假设a k = l 且。2 = 1 ，简化公式( 4 2 4 ) 为下式。 一= o 5 e x p ( x k u ；+ 儿以”) ( 2 ) 计算状态量度：对于前向状态量度，因为编码器是从全零状态丌始编码， 所以起始条件为i = 1 o f n 学一- - 庐k = l 。= 磁宇= o ，利用公式( 4 1 4 ) 迭 代计算3 次。对于后向状态量度，本例中时刻k = 4 的最终状态也为a = 0 0 ， 所以起始条件为嚣= 1 0 和普= 届嚣= 詈= 0 ，利用公式 ( 4 1 8 ) 迭代计算3