（信号与信息处理专业论文）迭代译码算法及在lascdma中的应用.pdf

摘要 最近，低密度极性校验码l d p c ( l o w d e n s i t yp a r i t y c h e c kc o d e s ) 、乘积码 t p c ( t u r b op r o d u c tc o d e s ) 及t u r b o 码代表了编码领域的重大突破。它们采用 的方式都是根据次优s i s o 迭代译码算法，采用受一定条件约束而又类似随机的 结构，比传统的前向纠错方式提供更多的编码增益。本论文主要研究迭代译码算 法在t p c 码和l d p c 码中的应用。分析了t p c 编译码算法在各种信道下的性能； t p c 码在l a s - c d m a 的自适应调制与编码中的应用，给出在l a s c d m a 系统中选 择m c s 级别的方案；同时还研究了l i ) p c 码的构造及其译码算法的实现以及规 则l d p c 在各种信道中的译码性能等。 【芙键词】软入软出：迭代译码；t u r b o 乘积码；低密度极性校验码：自适应调制与编码： l a s c d m a ；t u r b o 码；l s 码；并行级联卷积码；串行级联卷积码 a b s t r a c t l o w d e n s i t yp a r i t y - c h e c k ( l d p c ) c o d e s ，t o g e t h e rw i t ht u r b oc o n v o l u t i o n a lc o d e s ( t c c ) ，a n d t u r b op r o d u c tc o d e s ( t p c ) ，r e p r e s e n taf u n d a m e n t a l b r e a k t h r o u g hi nc o d i n gt h a th a se m e r g e d i n t h el a s td e c a d e t h en e wa p p r o a c h ，w h i c hi sb a s e do n s u b o p t i m a l s o f t i n s o f t o u ti t e r a f i v e d e c o d i n go fc o d e sc o n s t r u c t e du s i n gc o n s t r a i n e db u tr a n d o m - l i k es t r u c t u r e s ，o f f e r ss i g n i f i c a n t l y m o r ec o d i n gg a i nt h a nc o n v e n t i o n a lf e cm e t h o d s t h i st h e s i sm a i n l yf o c u s e so nt h ei t e r a r i v e d e c o d i n ga l g o r i t h m s u s e di nt p ca n dl d p c w ep r e s e n tt h et p ca l g o r i t h ma n di t s i m p l e m e n t a t i o n p e r f o r m a n c eu n d e rv a r i o u sc h a n n e le n v i r o n m e n t s ，a n dc o m p a r ei t w i t ht u r b o c o d e s i np a r t i c u l a r , an o v e ls c h e m et h a ta p p l i e st p ci na d a p t i v em o d u l a t i o n c o d i n g ( a m c ) i nl a s c d m as y s t e mi s p r o p o s e d ，a n d i ss h o w nt h a tc a n i m p r o v es y s t e mt h r o u g h p u t s i g n i f i c a n t l y t h e c h o i c eo fm o d u l a t i o nc o d i n gs c h e m e s ( m c s ) l e v e l si nl a s c d m as y s t e m u s i n gt p c - a m c i sd e t e r m i n e db ys i m u l a t i o n w ea l s os t u d yt h ep a r i t y c h e c km a t r i xc o n s t r u c t i o n s o fl d p ca n di t sd e c o d i n ga l g o r i t h m , a n dc o m p a r ei t sp e r f o r m a n c e i nv a r i o u ss c e n a r i o sw i t h t u r b oc o d e sa r es t u d i e d 【k e y w o r d s 】s i s o ，i t e r a t i v ed e c o d i n g ，t p c ，l d p c ，a m c ，l a s c d m a ，t u r b o c o n v o l u t i o n a lc o d e s ，l ss p r e a d i n gc o d e ，p c c c ，s c c c 北京邮j 乜人学颂i 学位论文 迭代弹e 马算法及谯l a s c d m a 中的应用 第一章绪论 数据业务是未来移动通信的一项基本要求。对良好的服务质量的要求，使得 信息传输的可靠性变得越来越重要。其中纠错编码技术是保证传输可靠性的一项 关键技术。纠错编码技术通过为信息添加冗余，来实现纠错。在数字移动通信、 数字卫星通信等应用中，传播环境较为恶劣，而纠错码技术是这些系统中用来维 持系统性能的一个重要手段。 纠错码可看作是从输入信息空间到码字空间的一个映射。映射的方法和相应 的译码方法决定了纠错码性能的优劣。信息和码字一般均由串符号构成，且每 个符号属于某个代数域，例如当代数域取g f ( 2 ) = 0 ，1 ( 此时，“加”运算定义为 模2 和 时，就对应了二元码。 在本章中，我们先介绍下纠错编码的发展情况，引入s h a n n o n 界的理论， 然后再介绍一下本论文重点分析的低密度极性校验码( l o wd e n s i t yp a r i t yc o d e ) 及t u r b o 乘积码( t u r b op r o d u c tc o d e ) ，最后给出论文的主要内容及论文结构。 1 1纠错编码的发展情况 分组码是最早应用的信道编码技术，在分组码每个码字中，监督元仅与本组 的信息元有关，而与别组的信息元无关。汉明码是h a m m i n g 在1 9 5 0 年提出的分 组码，这也是第一个纠错码。1 9 5 7 年p r a n g e 首先开始研究循环码，这是线性分 组码的一个重要子类，由于它具有循环特性和优良的代数结构，使得可用简单的 反馈移存器实现编码和伴随式计算，并可使用多种简单而有效的方法进行译码。 1 9 5 9 年h o c g e n 曲e m 与1 9 6 0 年b o s e 及c h a u d h u r i 分别提出了纠正多个随机 错误的循环码，称为b c h 码。这是一类纠错能力强，构造方便的好码。1 9 6 0 年 p e l e r s o n 找到了二元b c h 码的第一个有效算法，从而将b c h 码由理论研究推向 实际应用阶段。r e e d s d o m o n ( r s 码) 是多元b c h 码的一个特殊子类，是应用广 泛而有效的一类线性码。它是一类g f ( q ) ( q 2 ) 域上的码长为q - l 的循环码，它 既可以纠随机错误，也可以纠正突发错误，是m s d 码( 最大距离可分码) 中的纠 错能力最强的编码。定义在g f ( 2 9 ) 域上的非二元r s 码，通常用来傲二元内码的 外码。信息首先用r s 码编码，然后再用二进制码( 例如卷积码) 再次编码，这 钯3 砸 北隶邮i u 人学硕卜学位论文 选代详蹦算法及d ：l a s c d m a 中的应用 就是f o r n e y 的级联码。 卷积码是由麻省理工学院e 1 i a s 提出的，和分组码一样，卷积码也是将长度 为k 的输入信息组映射成长度为n 的输出编码组。所不同的是，输出码组不仅 和对应输入有关，还依赖以前的m 个输入信息。我们称k ( m + 1 ) 为该卷积码的约 束长度。在编码存储v 较大时，可以得到较低的译码错误概率。事实上，约束长 度为7 的卷积码一直是7 0 年代以来美国卫星通信的编码标准。在1 9 9 3 年t u r b o 码出现之前，白高斯信道性能最好的编码是f o r n e y 提出的用r e e d s o l o m o n 码做 外码，卷积码做内码的级联码。用移位寄存器可以很方便的实现卷积码，其译码 方法有两种：v i t e r b i 译码和序列译码。 卷积码理论的发展与译码的两个最主要的方法密切关连。这两个译码方法分 别为代数译码和概率译码。代数译码从码的代数结构出发，以一个约束长度的接 收序列为单位，对该接收序列的信息码组进行译码。这是基于码的代数结构的译 码方法。而概率译码不仅考虑码的结构，还考虑信道的统计特性，使译码的性能 更好。序列译码与v i t e r b i 最大似然译码都是概率译码。v i t e r b i 最大似然译码的 运算时间是固定的，其译码复杂性均与v 成指数增长。原则上说，随约束长度的 增加，卷积码可以接近s h a n n o n 限。但其最为人所知的译码算法v i t e r b i 译码 的算法复杂度按约束长度的指数增长。丽另一种译码方法序列译码，时延是 随机的，它与信道干扰情况有关，尽管译码复杂度与约束长度无关，但其纠错能 力有限。只有在速率小于某个低于信道容量c 的门限凡的条件下，序列译码才 能够有效纠错。在门限r o 点计算量将变得非常大。举例来说，b s c ( - - 二元对称信 道1 信道，码率1 ，2 的编码，要求噪声密度必须小于4 5 ，而此时的s h a n n o n 限 为1 1 。 在1 9 4 8 年，s h a n n o n 就提出了信道编码定理【1 】，晃定了纠错编码的性能。 但是在1 9 9 3 年以前，实际使用的编码方式在接近s h a n n o n 限之前，性能就开始急 剧下降，更别说达到了。b e r r o u 等在1 9 9 3 年提出的t u r b o 码，性能接近了s h a n n o n 限，这标志着信道编码理论进入了一个新的阶段，是近年来纠错编码领域的一个 突破。特别地，t u r b o 码采用的s i s 0 迭代译码技术能够在许多情况下相当接近于 s h a n n o n 极限，同时其复杂度远低于最大似然译码算法，因此迅速在实际系统中 得到了广泛的采用。 第4 页 北京邮l 也大学硕l 。学位论义 迭代译码算法发扯l a s c d m a 中的成用 迭代译码算法是g a l l a g e r 最初提出的，1 9 6 2 年他给出u ) p c 码的译码算法时就 应用了迭代思想。当时由于其实现特别是硬件实现复杂( 需要大量的乘除运算) ， 当时并不被人所关注。后来f o r n e y 在1 9 6 6 年提出一种多级编码结构即级联码，由 于其相应的译码算法采用的是硬判决，所以相应的迭代译码增益没有得到充分体 现。直到最近几年，在b e r r o u 等提出运用软入软出( s o f t i n s o f t o u t ) 的迭代 译码的t u r b o 码之后，迭代译码由于其强有力的纠错性能和较低的复杂度得到了 广泛应用。最近，低密度极性校验码( l o w d e n s i t yp a r i t y c h e c kc o d e s ) 、乘积码 ( t u r b op r o d u c tc o d e s ) 及t u r b o 码代表了编码领域的重大突破和研究方向。它们 采用的方式都是根据次优迭代译码算法，采用受一定条件约束而又类似随机的结 构，比传统前向纠错方式提供更多的编码增益，能够提供接近s h a n n o n 界的性能。 1 2s h a n n o n 界理论 在信道编码领域，学者们一直在寻找接近s h a n n o n 界的实用的编码。在这一 节中，我们将简单地回顾一下关于s h a n n o n 界的理论，引入s h a n n o n 界和作为底 线( b a s e l i n e ) 的无编码的m p a m 信号的误码率公式、有效编码增益等概念，作为 论文后面章节的理论基础。有关s h a n n o n 界理论的详细介绍，请参阅文献 2 1 。 在理想a w g n 信道中，令每维的平均输入符号能量为e s ，每信息比特的平 均能量为e b = e s r ，其中r 是用比特，每维( b d i m ) 表示的码率。由于p = e s t ， 1 ，2 t 。因此a w g n 信道的信噪比s n r = 南= 筹_ 2 畴。 信道容量c 是信道输入与输出之间的最大互信息，s h a n n o n 最著名的信道容 量( b i t s ) 公式为 c 帅1 = w l 0 9 2 ( 1 + s n r ) 等价地，信道容量( b i t d i m e n s i o n ) 为 c i m i = 去l 0 9 2 ( “s n r ) 。 ( 1 - 1 ) s h a n n o n 指出，在码率r c 时不可能。 调制符号所属的集合a 称为信号集或信号星座图。一个m p a m 星座圈包括m 个等距离的实信号，即a = d 。2 - m 十l ，m + 3 ，m 一1 ) ，其中d o 表示符号之间 第5 页 北京邮i u 人学硕i ? 学位论文迭代洋码算法及札l a s c d m a 中的心用 的最小距离。如果符号是等概率的，那么平均符号能量为e ，= ( m2 一1 ) d 。2 1 2 。 在一个未编码m p a m 系统中，r = l o g ：m 个信息比特独立编码为各个 m p a m 传输符号。在接收端，最优的译码准则是进行独立的符号判决。高斯噪 声变量w 。超过氐2 的概率( d o 为相邻m p a m 符号的距离) 为q ( d 。2 0 。) ，其 物加去脚( - y 2 1 2 y e x p ( - x 2 2 ) 信号集最外侧的两个点的每个符号的错误概率为只( i o u t e r ) = q ( d 。2 0 。) 而内侧的m 一2 个点的错误概率为只( e i i n n e r ) = 2 q ( d 。1 2 a 。) ，因此每个符合的平 均错误概率螈加半q ( d 0 2 0 - w ) = 半q ( 耥) ( 1 2 ) 式( 1 1 ) 的信道容量公式可以写成s n ( 2 ”1 ) = l 。定义一个标准化s n r 为 s n r = s n r l ( 2 2 8 - 1 ) ( 1 3 ) 其中r 是给定调制与编码方案时的实际数据速率。如果调制与编码方案可以达 到信道容量，则r = cj i s n r = 1 ( o d b ) 。如果r 1 ，对应的 是实际情况。这样| s _ 凇的值反映的是系统运作时距离s h a n n o n 界的距离a 对于无编码m p a m ，r = l o g ：m 以及式( i 3 ) ，可以得到 s n r ( m2 1 ) = s n r ( 2 ”- 1 ) = s n r 。 因此，无编码的m p a m 的每符号的平均错误概率可以写成 驰) = 半q ( j 拦即q ( 厕砭) ( m 较大时) 由f f - e 6 n 。= s n r l 2 r ，因此在给定码率r ( b i t d i m ) f l 寸，有 瓦e b 一2 2 2 8 r - 1 s n r 一 如果r ( 2 ”一1 ) 2 r 从中可以看出，在r 趋向于0 时，到达极限s h a n n o n 界： 毛，n 。 i n 2 ( 一1 5 9 d b ) 由于在r = i 时，e t , n o = - ；s n r ，因此未编码的2 - p a m 信号每符号( 或每比 特) 的错误概率为驰) - q ( 脚酝) - q ( j 鲁) 一个编码调制系统方案的“有效编码增益”是指达到一定的目标错误率所需 的。或s n r 与相应的使用作为底线( b a s e l i n e ) 的无编码方案的e 。n 。或 s n r 。比较所减少的数值。在低s n r 领域，底线为2 p a m ，在高s n r 领域， 底线为m p a m ( m 很大) 。 图1 1 描述的是无编码的2 p a m 的误码率p b ( e ) 作为e 。u 。和s n r 。的函数 的曲线。图中e 。n 。的轴相对与s n r 的轴偏移了3 2 ( 1 7 6 d b ) 。在己( ) = 1 0 。 时，无编码的二进制调制方案距离s h a n n o n 界1 2 ，5 d b 。因此，在这个误码率上， 如果带宽足够宽，从而可以使用强大的码率极低的二进制码( r kh 脯s nt 。蒜潮”掣鲫 + i j 9 d b 1 08 d h i m 8 图1 1 无编码的2 - p a m 的误比特率和无编码的m p a m 的误符号率与s h a n n o 页 k#霉-q甩f4 北京i t l l i i l l 人学硕j ：学位论文 迭代译码算法及谯l a s c d m a 中的应用 1 3 实用的接近s h a n n o n 界性能的编码 s h a n n o n 当时提出的信道编码定理“】是非构造性的，没有给出怎样实现。 近5 0 年来，在信息技术不断发展与实际需要的推动下，学者们一直在寻找实用的 更优秀的编码方式，去逼近理论上的s h a n n o n 界。下面我们将分别介绍上面1 1 节提到的三种接近s h a n n o n 界性能的编码：t u r b o 码，t u r b o 乘积码( t p c ) ，以及低 密度极性校验码( l d p c ) 。l d p c 码、t p c 码和t u r b o 码有一些共同特征：1 ) 他们 的构造中都有随机排列的参与；2 ) 它们的译码都采用了迭代译码：3 ) 其性能都 接近了s h a n n o n 限。在迭代译码过程中，译码器不仅输出信息比特的硬判值，还 要输出译码后的信息比特的可靠值。本论文重点对s i s o 迭代译码在低密度极性 校验码l d p c 、乘积码t p c 的应用进行研究。 1 3 1t u r b o 码 最初b e r r o u 提出的t u r b o 码是一静并行级联码，两路码率都是1 1 2 的卷积码 作为其分量码，两路输入之间用伪随机交织器进行随机重排。两路分量码都是系 统码：每一路输出的其中个分支是原输入序列。在输出时有一路分量码输出的 原输入序列被舍弃，成为码率i 3 的t u r b o 码。后来t u r b o 码的范围扩大到包括 并行级联卷积t u r b o 码( p a r a l l e lc o n c a t e n a t e dc o n v o l u t i o n a lc o d e ) 、串行级联卷积 t u r b o 码( s e r i a lc o n c a t e n a t e dc o n v o l u t i o n a lc o d e ) 、混合级联卷积码( h y b r i d c o n c a t e n a t e dc o n v o l u t i o n a lc o d e ) 、分组码卷积码串行级联码( s e r i a lc o n c a t e n a t e d c o n v o l u t i o n a la n db l o c kc o d e ) 、分组码t u r b o 码等等。其中对于卷积级联码中研 究的最多的是并行级联卷积t u r b o 码p c c c ，其次是串行级联卷积t u r b o 码 s c c c ；在分组码t u r b o 码中t u r b o 乘积码t p c 是研究较多的一种。t u r b o 码具有 非常优异的性能，w c d m a 和c d m a 2 0 0 0 都同时采用了卷积码和p c c c 作为纠错编码。 t u r b o 码主要用于对时延要求不高的高速数据业务。在c d m a 2 0 0 0 1 x h d r 中，s c c c 作为信道编码方案。l a s - c d m a 选用分组乘积t u r b o 码( t p c ) 作为数据业务的信 道编码方案。c b e r r o u 等最初提出的编码结构是由卷积码子编码器( 并加交织器) 级联得到的，而相应的迭代译码器是由多个软输入软输出( s i s o ) 子译码器构 成的，每个s i s o 子译码器以先验信息作为输入，并以外部信息作为输出；这里 第8 页 北京| | | f i u 人学硕1 学位论义 迭代详鹏算法及n l a s c d m a 中的戍用 外部信息为后验信息与先验信息的差值，将它与解调器的软输出信息进行合并 后，以先验信息的形式作为后级s i s o 子译码器的输入。目前t u r b o 码译码算法 有m a p 、l o g m a p 、m a x l o g 。m a p 、s o v a 算法等。 1 3 2t u r b o 乘积码 乘积码( p r o d u c tc o d i n g ) ，也即分组乘积t u r b o 码或称n 维乘积码，是e 1 i a s 于1 9 5 4 年提出的，是一类由n 个子码( 一般为较简单的分组码) 构成的特殊的 复合码，可以看作是对n 个n l 维乘积码再进行一维编码所获得的码字，其结构 见论文第二章的图2 7 。乘积码的最小距离是各子码最小距离的乘积；同时，其 码块长也为各子码码块长的乘积。在实际应用中，乘积码是一类能同时纠正随机 错误和突发错误、码构造简单的好码，特别适用于信道干扰复杂的差错控制系统。 系统可以通过合理地选取子码，以及对其进行适当地截短，获得比较灵活的码率。 它是香农信息理论提出后第一个在非零码率时可以实现无误码传输的纠错编码。 由于当时的硬件水平限制了它的应用，几十年来它的优越性能得不到有效应用。 后来t a n n e r 【2 1 】，“n c o s t e l l o 等人对乘积码的迭代译码算法进行了研究。随 着迭代译码算法的应用，乘积码由于它独特的优点再次得到关注。 乘积码可看作是一类将分组码进行串行级联、并采用分组交织器构成的级联 码。因此，乘积码是一种构造十分简单的纠错码结构，应用迭代译码方法，可发 挥该码的良好性能，并特别适合于高速硬件译码实现。它的各级s i s o 子译码器 以先验信息作为输入，并以外部信息作为输出；这里外部信息为后验信息与先验 信息的差值，将它与解调器的软输出信息进行合并后，以先验信息的形式作为后 级s i s o 子译码器的输入。t p c 码的s i s o 迭代译码算法可分为两类。一类是基 于t r e l l i s 结构的，如m a p 、l o g - - m a p 算法 2 4 1 等，另一类是非t r e l l i s 结构 的如c h a s e - p y n d i a h 算法【1 5 】、f b b a 算法 2 5 1 及p e s u d o m a x i m u m l i k e l i h o o d 算法【1 3 】。最近，有效的s i s o 译码算法大大推动t p c 码的商用化。a h a 公 司在1 9 9 8 年推出的a h a 4 5 0 1 编译码器设备1 2 2 使用的是t p c 技术。 1 3 3 低密度极性校验码 低密度极性校验码是由稀疏极性校验矩阵h 定义的二进制的线性纠错码。如 第9 负 北京1 | | 【f l 乜人学坝 与位论文 迭代详码算往及订- l a s c d m a 中的心用 果极陛校验矩阵h 有n 列m 行则所形成的码字序列v 是由满足m 个二进制 校验位的n 比特组成的，满足h v = o 。可以通过执行二进制高斯消元并对列进行 重排将h 阵变为系统阵形式h s y s = i 。ip 】，相应的生成矩阵为c s y s = p 7ii 。一。】， 就得到l d p c 码的系统阵形式的校验矩阵和生成矩阵。 1 9 6 2 年，g a l l a g e r 在自己的博士论文1 5 1 中提出一种基于稀疏校验矩阵的 线性分组码，也就是低密度校验码( l o wd e n s i t yp a r i t y - c h e c kc o d e ) ( 我们称 g a l l a g e r 当时构造的l d p c 码为g a l l a g e r 码) 。其监督矩阵具有以下特性：每列 包含很小的固定数目j = 3 的1 ，每行包含很小的固定数目k j 的l 。g a l l e g e r 不 但证明了l d p c 码的优良性能：1 ) 这些码字的典型最小距离随码长的增加线性 增加：2 ) b s c 信道下译码错误的典型概率随码长指数减小，而且提出了两种 迭代算法。但由于其实现特别是硬件实现复杂( 需要大量的乘除运算) ，当时并 不被人所关注。而当时人们的兴趣大都集中在有实现可能的编码方式上，例如级 联码等。直到最近几年，在b e r r o u 9 1 等提出t u r b o 码之后，m a c k a y 等人在 1 9 9 5 年发现：l d p c 码的性能足可以和t u r b o 码相比【3 】，而且在实现上更有优 势。m a c k a y 证明性能优异的l d p c 码的存在性1 4 1 ，并给出了构造l d p c 码 的一些思路。由于迭代译码算法的出现，使得l d p c 码的实用成为可能。l d p c 码采用的s i s o 迭代译码算法为消息传递算法，这将在第二章中进行详细介绍。 1 4目前完成的工作 目前完成的工作有： 根据文献【1 2 1 ，在c o s s a p 平台上实现了t p c 码编译码算法； 优化以扩展b c h 码为予码及以r s 码为子码的t p c 码的s i s o 迭代译码算法； 在l a s c d m a 系统中，结合高维调制，对以扩展h a m m i n g 码为子码及以扩 展b c h 码为子码的t p c 码在a w g n 信道和衰落信道下的性能进行仿真与分 析，并将t p c 码与t u r b o 码的性能进行了比较； 研究s i s o 迭代译码算码在l a s 系统中的应用，其中t p c 码在自适应调制 与编码( a m c ) 中的应用已申请专利( 专利申请号：p c t c n 0 2 0 0 0 7 2 ) ； 用m a r l a b 实现了规则l d p c 码校验矩阵和生成矩阵的构造，并在c o s s a p 平台上实现了l d p c 码的编译码算法； 钨1 0 页 ! 生塑堕坚查堂里生兰型塑坠一 垄! ! 堂坐塑! i 丝j ：! 垒! ：! 里竖垒! 塑查旦 通过仿真优化l d p c 译码算法的译码算法所用的各项参数： 优化l d p c 译码算法，使之可以与高维调制相结合： 对规则l d p c 码的性能进行多方面的仿真、验证与分析； 在l a s 系统中，在a w g n 信道和衰落信道下，结合高维调制，对规则l d p c 码与t u r b o 码的性能进行比较与分析。 1 5 论文结构 本论文分六章系统给出迭代译码算法及其在l a s c d m a 系统中的应用。 在第二章中给出s i s o 迭代译码算法的历史发展、算法原理以及它在p c c c 、 s c c c 、l d p c 、t p c 码中的应用，详细给出了t p c 码与l d p c 码所用的s i s o 迭代译码算法。 第三章给出了l d p c 码的发展情况、原理、分类，以及规则l d p c 码和不规 则l d p c 码的多种构造方式，其中包括我们在工作中已经用软件实现的几种 规则( 或类规则) l d p c 码校验矩阵的构造方式。 第四章给出了l d p c 码中s i s o 迭代译码算法的实现与性能分析，详细给出 了l d p c 码的s i s o 迭代译码算法的具体实现，将其与1 6 q a m 调制相结合， 对其在l a s 系统平台下的a w g n 和衰落信道下的性能与t u r b o 码的性能通 过仿真结果进行比较，并给出其复杂度分析、误码性能分析、以后的工作中 将其用于l a s 系统中的应用设想。 第五章给出t p c 码中s i s o 迭代译码算法的实现与性能分析，对以扩展 h a m m i n g 码为子码的二维t p c 码、以扩展b c h 码为子码的二维t p c 码分 别在l a s 系统平台中a w g n 和衰落信道下与t u r b o 码的性能进行仿真比较、 给出t p c 码的误码性能、抗突发错误性能、抗平台效应性能等方面的特点。 第六章给出了t p c 码在l a s 系统中的自适应调制与编码( a m c ) 技术中的应 用，分别给出了以扩展h a m m i n g 码为子码及以扩展b c h 码为子码的t p c 码用于a m c 的仿真曲线及所选的m c s ( m o d u l a t i o n c o d i n gs c h e m e ) 级 别，并对吞吐量进行仿真与分析。 总结与展望中总结了我们的工作并给出了有待于我们下一步研究的问题。 第1 1 页 北京f j l 乜人学颁j 学位论殳 选代译码算法驶拈l a s c d m a 中的戍用 第二章s i s o 迭代译码算法 在这一章中，我们给出s i s o ( s o f t i n s o f t o u t ) 迭代译码算法的原理并给出它在 并行级联卷积码p c c c 、串行级联卷积码s c c c 、t u r b o 乘积码t p c 、低密度极 性校验码l d p c 中的应用，重点介绍t p c 与l d p c 所用的s i s o 迭代译码算法。 最初的译码是采用硬判决译码，也就是解调器供给译码器作为译码用的每个 码元只取0 和1 ( 二进制情况) 两个值，这样的判决会损失掉接收信号中所包含 的有用信息。为了充分利用接收信号波形中的信息，使译码器能以更大的正确概 率判决所发送的码字，应该采用软判决译码，对解调器输出的抽样电压进行分层 或量化。通常译码器利用附加的软判决信息进行软译码时比硬译码能得到额外的 2 3 d b 的增益。在软判决译码中有两个最佳译码准则：使码字错误概率最小的软 判决译码( 以接收序列与发送码字的软判决距离为基础) 与使码元错误概率最低 的软判决译码( 以每个码元似然函数比为基础) 。使码元错误概率最小的软判决 译码方法中最重要的有：1 9 6 3 年由m a s s y 提出的a p p ( 后验概率译码) 算法、 h a r t m a n 与r u d o l p h 于1 9 7 6 年提出的诸位译码算法( h r 算法) 、1 9 7 1 年w e l d o n 提出的w e d 算法等。最早使码字错误概率最小的软判决译码算法是1 9 6 6 年 f o m e y 提出的广义最小距离译码g m d 算法，稍后c h a s e 于1 9 7 2 年提出c h a s e 算法实际上是g m d 译码的种实用算法。 迭代译码算法是g a l l a g e r 最初提出的。他在1 9 6 2 年给出l d p c 码的译码算 法时，就应用了迭代思想。当时由于其实现特别是硬件实现复杂( 需要大量的乘 除运算) ，当时并不被人所关注。f o m e y 在1 9 6 6 年提出的级联码，当时由于其相 应的译码算法采用的是硬判决，所以相应的迭代译码增益没有得到充分体现到 最近几年，在b e r r o u 等提出t u r b o 码之后，迭代译码由于其强有力的纠错性能 和较低的复杂度得到了广泛应用。b e r r o u 等最初提出的t u r b o 码编码结构是由卷 积码子编码器( 并加交织器) 级联得到的。并且，相应的迭代译码器是由多个软 输入软输出( s i s o ) 子译码器构成的，每个s i s o 子译码器以先验信息作为输入， 并以外部信息作为输出；这里外部信息为后验信息与先验信息的差值，将它与解 调器的软输出信息进行合并，以先验信息的形式作为后级s i s o 子译码器的输入。 s i s o 迭代译码算法融合了迭代思想和软判决的思想t 不但适用于卷积码领 第1 2 页 北京j | 】j f i u 人学碳l 学位论文迭代译码算法鼓拈l a s c d m a 中的应用 域岜适用于线性分组码领域。下面我们给出s i s o 迭代译码算法的原理。 2 1s i s o 迭代译码算法原理 迭代译码的基本思想是将一个的复杂的长的译码步骤分解为多个相对简单 的迭代译码步骤而且在迭代译码步骤之间信息概率的转移或者是软信息的传递 确保几乎没有信息损失。我们使用对数似然比函数介绍s i s o 的迭代译码算法。 设u 是g f ( 2 ) ： + 1 ，一1 ) 中的元素。二进制随机变量u 的对数似然比l 。( “) 定义为 “( “) = l 。g 鲁罢 岩，岛( “) 称为变量u 的软信息值。匕( “) 的符号是硬判决 口“) 值，v i i l u ( “) i 的幅度是该判决的可靠度。我们可以得到p = + 1 ) 2 舌i 丽。 根据关系 式 p ( u lo “2 = + i ) = p ( u = + 1 ) p ( u 2 = 十1 ) 十( 1 一p ( u l = + 1 ) ) ( 1 一p ( u 2 = + 1 ) ) 可以得到对于统计独立的随机变量u 。，u ： 地。) 1 。g 筹 ( 21 ) 设我们对软信息值为l ( u ) 的二进制值u 编码，得到码字x ，其软信息值为l ( x ) a 在经过b s c 信道或高斯衰落信道传输后，我们计算条件概率 地 y ) = l o g 篆端岫文篱蓦。删j 礼。而exp(-ne-毒so(y-a)：)仙s艄地址， 其中，l r = 4 n e ，n 。，称为信道的可靠值。对于衰落信道，a 表示衰落的 幅度，而对于高斯信道，令a = l 。 对于统计独立的传输来说，l ( x ly 。，y ：) = l c 。y 。+ l ，2 y 2 + l ( x ) ( 2 - 2 ) 我们考察二维的迭代译码。k i * k 2 信息比特u 用矩形排列。其相应校验比特 北京l | l l j i 乜大学硕l j 学位论义 迭代译码算法及拈l a s c d m a 中的应用 为p - , p 1 。匹配滤波器输出的接收值为y ，而在接收端所有码字的l c * y 均可以计 算出。图2 1 是一个简单的( 3 ，2 ，2 ) 单极性校验码作为成员码的示例。 幽2 1 ( 3 ，2 ，2 ) 迭代译码方粟不例 如图2 1 所示，接收信息中关于比特u 。的信息有两次：直接通过“。以及间 接通过“。2op i 。由于“i ：与p i 统计独立，根据式2 1 我们可以得到其软信息值 l ( u ：op i ) 。该“。的间接信息值称为外部信息值。同样我们也可以得到“，：的外 部信息值，将水平方向的这些外部信息值记为l - 。这样在开始竖直方向译码时， 我们使用这些t 作为竖直译码的先验信息。这样，在对“。竖直译码之后，我们 得到“。，可用的三个软信息值：接收到的直接信息值、水平译码得到的先验值l _ 以 及利用所有可用的“：。op ! 信息得到的竖直方向的外部信息值吐。如果我们在此 停止，在竖直译码后我们得到的软输出为 l ( u ) = t y + l - 4 - t ( 2 - 3 ) ( 2 3 ) 是从( 2 2 ) 得出的，这是因为到目前，( 2 3 ) 1 拒- - 项是统计独立的a 我们利用上面的s i s o 译码原理考察分组码作为成员码的情况。我们使用任 何系统分组码的组合对k i * k 2 信息比特在水平或竖直方向编码。对成员码的 s i s o 译码示意图参见图2 2 。 所有信息 的先验信 所有码 信道信 图2 2s i s o 译码器 所有信息比特 的外部信息值 所有信息比特 的后验信息值 第1 4 负 北京i h l l i u 人学硕卜学位论史 迭代详码算法及以- l a s c d m a 中的戍用 个最大后验概率( m a p ) 译码器的输出定义为一个后验对数似然比 y ) = l o g 黜。该译码器使用所有信息位u 的先验值l ( u ) 以及 所有码字的信道值l c * y 。对于系统码，信息比特u 的软输出为 l ( u ) = l ，y + l ( “) 十l 。( h ) ( 2 4 ) 这样，对于信息比特的对数似然比来说，有三个独立的估计量：信道值l c * y 、 先验值l ( u ) 以及利用编码限制得到的第三个独立估计量t ( “) 。对于等概率的信 息比特，在第一次迭代时没有先验信息，初始化l ( u ) = o 。使用对应信息部分的 l c + y 对水平方向的码c 一开始译码，根据( 2 4 ) ，水平方向码c 一的外部信息l - ( “) 为t ( “) = l - ( u ) 一t y ( 2 5 ) u 的这一独立估计现在用作对c 1 竖直译码的先验值，得到 吐( “) = l j ( u ) 一( l c y + ( “) ) ( 2 6 ) 此竖直外部信息值在下一次迭代时将用作码c 一译码的新的先验信息值。 需要说明的是，在第一个水平和竖直方向迭代时，软信息值是统计独立的， 但是之后他们将间接使用同一信息，它们的相关性将越来越强，最后通过迭代获 取的译码效果将变得很小。 对于最后一次迭代之后的软输出，我们将接收值与最后两个外部信息值合并 得到：( ：) ：t ) ，+ 乞( ：) + 吐( ：) 。整个过程如图2 3 所示。 甾2 3 等概率信息比特( “u ) o ) 的s i s o 迭代译码器的迭代译码过程 第1 5 负 苎堕型里：塑上堂丝堡兰 些垡塑坐塑鲨丝! ! ：! 箜：! 里翌! ! 塑些旦 在上面的分析中，我们介绍了分组码作为成员码可以使用s i s o 迭代译码算 法进行译码，同样，卷积码作为成员码也可以使用s i s o 迭代译码算法进行译码。 在此我们不再详细介绍，感兴趣的读者请参阅文献【2 4 】。 2 2 接近s h a n n o n 界的好码中的s i s o 迭代译码算法 在绪论中，我们介绍了s h a n n o n 界。近5 0 年来，在信息技术不断发展与实 际需要的推动下，学者们一直在寻找实用的更优秀的编码方式，去逼近理论上的 s h a n n o n 界。下面我们介绍几种实用的接近s h a n n o n 界的编码方式的译码结构 算法，它们的译码均应用s i s o 迭代译码算法，其中有属于卷积码范畴的研究较 多的p c c c 、s c c c ，以及属于分组码范畴的t p c 、l d p c 。其中p c c c 、s c c c 、 t p c 均为级联码形式，而l d p c 虽然是单独的分组码，但是其消息传递算法也 是一种s i s o 迭代译码算法。由于本论文主要是对t p c 、l d p c 码进行研究，因 此对p c c c 、s c c c 的迭代译码算法仅给出结构，具体算法请参阅相关文献。 2 2 1p c c c 与s c c c 的s i s o 迭代译码 c b e r r o u 等最初提出的t u r b o 码【9 】的编码结构是由卷积码子编码器( 并加 交织器) 级联得到的。并行级联卷积码p c c c 与串行级联卷积码s c c c 均属于 卷积级联码范畴的t u r b o 码。而相应的迭代译码器均是由多个软输入软输出 ( s i s o ) 子译码器构成的，每个s i s o 子译码器以先验信息作为输入，并以外部 信息作为输出；这里外部信息为后验信息与先验信息的差值，将它与解调器的软 输出信息进行合并后，以先验信息的形式作为后级s i s o 子译码器的输入。p c c c 与s c c c 的构造不同是级联方式不同，p c c c 为并行级联，s c c c 为串行级联， 相应的编译码结构也有所不同( 图2 4 ，图2 5 ，图2 6 ，图2 7 ) 。其中图2 7 中 x ( c ，i ) 、x ( u ，i ) 表示s i s o 译码器的软信息输入，它可以是对数似然比， ( c ，o ) 、 x ( u ，o ) 表示s i s o 译码器的软信息输出，它也可以是对数似然比。目前t u r b o 码 ( 包括p c c c 、s c c