（通信与信息系统专业论文）rs码软判决译码的研究.pdf

摘要 r e e d s o l o m o n ( r s ) 码是最优秀的纠错编码之一。它的编码构造和硬判译码算法被视 为代数理论与工程实现的完美结合。然而r s 码缺少简单有效的软判译码算法，这将严 重影响r s 码在未来通信系统中的应用。鉴于r s 码有着广泛的应用，研究r s 码软判 决译码算法具有重要的理论意义及应用价值。 本文主要致力于r s 码软判决译码算法的研究，系统地介绍了目前国际上主流的一 些软判决译码算法，如k o e t t e r 和v a r d y 提出的代数软判决( a s d ) 译码算法，j i n gj i a n g 和n a r a y a n a n 提出的自适应置信度传播译码( a b p ) 算法以及m o s t a f a 和m c e l i e c e 提出的 级联型译码算法。 在此基础上，为了提高r s 码的纠错性能，本文提出了一种基于c h a s e 的代数软判 决译码算法，称为c h a s e a s d 。该算法充分利用了接收比特的可信度信息，但运算复杂 度较高。针对该算法运算复杂度高的问题，我们进一步给出了简化的c h a s e a s d 算法。 仿真结果表明，提出的c h a s e a s d 和简化的c h a s e a s d 算法均可比原a s d 算法提供更 多的译码增益。 另外，本文还考察了a b p 算法与其它软输入硬输出算法级联的性能，比如硬判决 译码算法，a s d 算法，o r d e r e ds t a t i s t i c sd e c o d i n g ( o s d ) 算法及b o xa n dm a t c h d e c o d i n g ( b m a ) 算法等。结合自适应置信度传播译码算法软输入软输出( s i s o ) 的特点， 我们将累积对数似然比的级联方式和多重偏置引入到级联型译码算法，有效地降低了级 联型算法的平均迭代次数。通过大量仿真分析，我们可以看到这些改进有效的增强了级 联型算法性能。 最后，在基于同样仿真软件平台的条件下，我们对具有同码长同码率的r s 码与短 l d p c 码的译码性能进行了比较。仿真结果表明，采用不同的译码算法，译码性能的差 异会有所不同。 关键词：r s 码；软判决译码；代数软判决译码算法；自适应置信度传播；级联译码算 法 a b s t r a c t r e e d s o l o m o n ( r s ) c o d e sf i r ea m o n gt h em o s tc e l e b r a t e de r r o rc o r r e c t i n gc o d e s t h e i r a r c h i t e c t u r ea n dh a r dd e c i s i o nd e c o d i n g ( h d d ) a l g o r i t h m sa r ec o n s i d e r e da sp e r f e c tm a r r i a g e b e t w e e na l g e b r a i ct h e o r ya n de n g i n e e r i n ga p p l i c a t i o n h o w e v e r , t h el a c ko fa ne f f e c t i v es o f t d e c i s i o nd e c o d i n ga lg o r i t h mw i l lc e r t a i n l yb a f f l et h e i ra p p l i c a t i o n si nf u t u r ec o m m u n i c a t i o n s y s t e m s s i n c et h er sc o d e sh a v eb e e nu s e di naw i d ev a r i e t yo fa p p l i c a t i o n s ，r e s e a r c h e so n s o f td e c i s i o nd e c o d i n go fr sc o d e sd oh a v eg r e a tv a l u en o to n l yi nt h e o r y , b u ta l s oi n e n g a n e e n n g t h i st h e s i si sm a i n l yo nt h es o f td e c i s i o nd e c o d i n go fr sc o d e s f i r s t l y , w es y s t e m i c a l l y i n t r o d u c er e c e n ts o f td e c i s i o nd e c o d i n ga l g o r i t h m s ，s u c ha sa l g e b r a i cs o f td e c i s i o nd e c o d i n g ( a s d ) a l g o r i t h mp r o p o s e db yk o e t t e ra n dv a r d y , a d a p t i v eb e l i e fp r o p a g a t i o n ( a b p ) a l g o r i t h mp r o p o s e db yj i n gj i a n ga n dn a r a y a n a na n dc o n c a t e n a t e da l g o r i t h mp r o p o s e db y m o s t a f aa n dm c e l i e c e t h e n ，t oi m p r o v et h ee r r o r - c o r r e c t i n gp e r f o r m a n c e ，a l la l g e b r a i cs o f td e c i s i o nd e c o d i n g a l g o r i t h mo fr e e d s o l o m o nc o d e s b a s e do nc h a s ea l g o r i t h mi sp r o p o s e d ，c a l l e dc h a s e a s d ， w h i c hc a nm a k ef u l lu s eo ft h er e l i a b i l i t i e so ft h er e c e i v e db i t sw i t hh i g h e rc o m p u t a t i o n c o m p l e x i t i e s t or e d u c et h ec o m p u t a t i o nc o m p l e x i t i e so ft h ep r o p o s e da l g o r i t h m ，as i m p l i f i e d c h a s e a s da l g o r i t h mi st h e np r e s e n t e d s i m u l a t i o nr e s u l t ss h o wt h a tb o t hc h a s e a s da n d s i m p l i f i e dc h a s e - a s d c a np r o v i d em o r ed e c o d i n gg a i n so v e rt h eo r i g i n a la s da l g o r i t h m m o r e o v e r , c o n c a t e n a t e da l g o r i t h m s ，s u c ha sa b p b ma l g o r i t h m ，a b p a s da l g o r i t h m ， a b p - o s d ( o r d e r e ds t a t i s t i c sd e c o d i n g ) a l g o r i t h ma n da b p b m a ( b o xa n dm a t c h d e c o d i n g ) a l g o r i t h ma r ed i s c u s s e d a c c o r d i n gt ot h ef a c tt h a ta b pa l g o r i t h mi sa na l g o r i t h m w i t ht h ec h a r a c t e r i s t i co fs o f t - i n s o f t o u t ( s i s o ) ，t h ec o n c a t e n a t e dm e t h o do fa c c u m u l a t e d l o g - l i k e l i h o o dr a t i o ( a l l r ) a n dm u l t i p l eb i a s e sa r ei n t r o d u c e dt oc o n c a t e n a t e da l g o r i t h m s ， e f f e c t i v e l yr e d u c i n gt h en u m b e r so fa v e r a g ei t e r a t i o n f r o mam a s so fs i m u l a t i o n ，w ec a ns e e t h a tt h e s ei m p r o v e m e n t se f f i c i e n t l ye n h a n c et h ep e r f o r m a n c eo fc o n c a t e n a t e da l g o r i t h m s f i n a l l y , p e r f o r m a n c ec o m p a r i s i o n so fr sc o d e sa n ds h o r tl d p cc o d e sw i t ht h es a m e c o d el e n g t ha n dr a t ea r ed o n eo nt h es a m es o f t w a r ep l a t f o r m s i m u l a t i o nr e s u l t ss h o wt h a t ， t h ep e r f o r m a n c ed i f f e r e n c ev a r i e sw i t hd i f f e r e n td e c o d i n g a l g o r i t h m s k e yw o r d s ：r e e d s o l o m o n ( r s ) c o d e s ；s o f td e c i s i o nd e c o d i n g ( s d d ) ；a l g e b r a i c s o f t d e c i s i o nd e c o d i n g ( a s d ) a l g o r i t h m ；a d a p t i v eb e l i e fp r o p a g a t i o n ( a b p ) ； c o n c a t e n a t i o nd e c o d i n ga l g o r i t h m a b p a l l r a s d a w g n b c h b e r b g m d b m b m a b p f e r g m d g s h d d i i s i r k v l d p c o s d s d d r s s e r s i h o s i s 0 s n r w e r 缩略语词汇 l i s to fa b b r e v i a t l o n s a d a p t i v eb e l i e fp r o p a g a t i o n自适应置信度传播算法 a c c u m u l a t e dl o g l i k e l i h o o dr a t i o 累积对数似然比 a g e b r a i cs o f td e c i s i o nd e c o d i n g代数软判决译码 a d d e dw h i t eg a u s s i a nn o i s ec h a n n e l 加性高斯白噪声信道 b o s e ，c h a u d h u r i & h o c q u e n g h e l nt y p e o f 博斯- 乔赫里一霍克文黑姆码 c o d e b i te r r o rr a t i o误比特率 b i t l e v e l g m d比特级的g m d 译码算法 b e r l e k a m p m a s s e y b m 译码算法 b o xa n dm a t c hd e c o d i n g 盒匹配译码算法 b e l i e fp r o p a g a t i o n 置信度传播 f r a m ee r r o rr a t e误帧率 g e n e r a lm i n i m u md i s t a n c ed e c o d i n g广义最小距离译码 g u r u s w a m i s u d a n g s 译码算法 h a r dd e c i s i o nd e c o d i n g硬判决译码 i t e r a t i v ei n f o r m a t i o ns e tr e d u c t i o n迭代信息集缩减 k o e t t e r - v a r d yk v 译码算法 l o wd e n s i t yp a r i t yc h e c kc o d e低密度校验码 o r d e r e ds t a t i s t i c sd e c o d i n g分阶统计译码 s o f td e c i s i o nd e c o d i n g 软判决译码 r e e d s o l o m o n 里德一所罗门 s y m b o le r r o rr a t e 误符率 s o f t i n p u th a r d o u t p u t 软输入硬输出 s o f t i n p u ts o f t - o u t p u t 软输入软输出 s i g n a ln o i s er a t i o 信噪比 w o r de r r o rr a t e码字错误概率 i v 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 研究生签名：与兰垒乳日期：土丛争牡 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。本文电子文档 的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅， 可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权南京邮电 大学研究生部办理。 研究生签名： 奎蝼 导师签名： r 期0 哟= 华，害 南京邮i u 人学硕i j 研究生学位论义第一章绪论 第一章绪论 随着科学技术的发展和社会的进步，通信特别是移动通信已成为人类生活不可或缺 的一个重要组成部分。于是，通信传输的有效性与可靠性也就成为当前研究的热点。而 可靠性主要是指信息传输的“质量”问题，因此差错控制编码的研究就成为通信研究的 分支之一。 1 1 纠错码的发展及现状 各种干扰以及噪声的存在使可靠性通信实现变得比较困难。为了实现信息的可靠性 传输，人们提出了信道编码的方法，来纠正通信中各种干扰以及噪声带来的错误。信道 编码是二十世纪4 0 年代术提出、6 0 年代发展起来的一门提高数据传输可靠性的理论与 技术，经过5 0 多年的发展，已经形成了一整套的信道编码理论。随着数字通信的发展， 数据网的飞速发展，对数据传输的可靠性提出了越来越高的要求，因此，如何提高数据 传输的可靠性已成为一个迫切需要解决的问题。 由于干扰和衰落，在信号传输过程中将出现差错，故对数字信号必须采用纠、检错 技术，即纠、检错编码技术，以增强数据在信道中传输时抵御各种干扰的能力，提高系 统的可靠性。要对信道中传送的数字信号进行的纠、检错编码就是信道编码。 信道编码的实质就是在信息码中增加一定数量的码元，使它们满足一定的约束关 系，这样由信息码元和监督码元共同组成一个由信道传输的码字，在传输的过程中如果 受到干扰，某位码元发生了变化，就破坏了他们之间的约束关系，收方通过检验这种约 束关系就可把错误识别出来，或者进一步判定错误的位置并加以纠正，从而保证通信的 可靠性。代数理论为信道编码提供了理论基础，大规模集成电路和微型计算机的发展为 信道编码技术的应用开拓了广阔的前景。如果不进行信道编码，直接把信息代码送入信 道，收到的信息就没有“可靠性”，只有“可能性”。 1 9 4 8 年仙农创立了信息谢，首次指明了信道编码的发展方向和研究目标。仙农指 出，任意一个信道都存在一个确定的信道容量c ，当通信速率r 小于信道容量c 时， 总存在一种编码方法，当码长充分时，若采用最大似然算法进行译码，则信息错误率可 以达到任意小。这就是著名的有噪信道编码定理。该定理没有给出构造纠错码的方法， 仅是一个编码的存在性定理，但是开辟了信道编码理论这一富有活力的研究领域。 南京邮i 【1 人学顾i ：研究生学位论义第一章绪论 从仙农信道编码定理可知，随着码长的增加，系统可以获得更好的编码增益。但是， 当码长较大时实现最大似然译码比较困难。因此构造实现简单实用的编码方案以及寻找 有效的译码算法成了信道编码理论与技术研究的中心任务。 在2 0 世纪4 0 年代，r h a m m i n g 和m g o l a y 率先提出了一个实用的信道编码方案， 这极大地推动了编码理论的发展。此后，m g o l a y 提出了纠错能力更强的二元g o l a y 码 以及三元g o l a y 码。在g o l a y 码之后，m u l l e r 在1 9 5 4 年提出了一种分组码，r e e d 在 m u l l e r 提出的分组码的基础上又提出了一种新的分组码，叫做r e e d m u l l e r ，简称r m 码。相对于汉明码以及g o l a y 码，r m 码在纠错能力以及码字长度方面具有更好的适应 性。在r m 码之后，人们又提出了循环码的概念。循环码也属于线性分组码，但它的码 字具有循环移位特性，循环码的这种特性大大简化了编译码结构。h o c q u e n g h e m 在1 9 5 9 年，b o s e 和r a y - c h a u d h u r i 研究组在1 9 6 0 年分别独立提出了b c h 码；1 9 6 0 年r e e d 和 s o l o m o n 将b c h 码推广到非二元域上得到了r s 码。b c h 码和r s 码是目前应用非常 广泛的纠错码。但是直到1 9 6 7 年b e r l e k a m p 给出了r s 码的一个非常有效的译码算法之 后，r s 码才被广泛地应用于某些通信系统。在一般通信系统中，r s 码与其他性能优异 的纠错码相结合，大大提高了系统的可靠性。 虽然上述分组码在数学上已经非常成熟，并且在实际通信系统中得到了广泛的应 用。但是分组码存在一些固有的缺陷。首先分组码是面向分组块的，因此必须在接收完 整码字之后才能开始译码，当数据块比较大时，产生很大的译码时延。另一缺点是大多 数基于代数的分组码的译码都是硬判决译码，因此性能损失较大。虽然可实现码的软判 决译码，但是通常译码的复杂度都比较大，基本上是随着码长的增加呈指数增加。1 9 5 4 年e l i a s 等人提出了一种没有线性分组码上述缺点的卷积码。在编码时，卷积码引入了 寄存器，增加了码元之间的相关性，可边输入数据边进行编码。并且，在接收了部分码 元之后，就可以进行译码。特别是1 9 6 7 年维特比译码算法的出现，使卷积码在通信系 统中得到了极为广泛的应用。 2 0 世纪8 0 年代，信道编码进入了另一研究高潮。以前传统的编码技术都是增加系 统的带宽来换取编码增益，因此不适合对带宽要求较高的系统。1 9 8 2 年u n g e r b o e c k 提 出的网格编码调$ 1 j ( t c m ) 的概念，解决了带宽和纠错这对矛盾。 到9 0 年代初，编码领域进入了一个崭新的阶段。1 9 9 3 年，t u r b o 码【2 】作为一种新型 信道编码方案被提出。由于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 码迭代译码 2 塑室! ! ! ! ! ! 坚叁兰塑! 型! 壅竺兰垡笙茎兰二童竺笙 【3 j 的思想也为众多通信系统提供了一种解决问题的方案。迭代译码思想在通信中的应用 的研究也在不断的深入。最初t u r b o 码的编码是利用两个卷积编码器作为分量编码器， 外加一个交织器构成。在研究前人工作的基础上，人们发现了被遗漏的重大成果，即一 种能利用随机编码的思想以及实现迭代译码【“】的线性分组码，这就是目前编码领域中 新的研究热点低密度奇偶校验码( l o wd e n s i t yp a r i t yc h e c kc o d e ) ，简称l d p c 码【7 1 。 目前l d p c 码以其优异的性能和较低的译码复杂度，获得了人们的青睐。l d p c 码已经 成为第四代移动通信技术中的关键技术之一，并有相关的提案被提交。从此，它成为了 通信系统纠错编码中的有力竞争者。 1 2r s 码的提出及发展 19 5 9 年1 月21 日，i r v i n gr e e d 和g u ss o l o m o n 向“j o u r n a lo ft h es o c i e t yf o ri n d u s t r i a l a n d a p p l i e dm a t h e m a t i c s ”提交了只有五页纸的论文“p o l y n o m i a lc o d e so v e rc e r t a i nf i n i t e f i e l d s ”【8 1 。他们在论文中谨慎地提出了构造一类新型纠错编码的方法。然而在随后的 四十多年旱，这种叫r e e d s o l o m o n ( r s ) 坌q 错编码在c d 播放、广播电视、磁体存储、无 线通信以及深空通信等等无数个系统中大放异彩。事实上，r s 码已经成为了2 0 世纪电 信革命密不可分的一部分。 r s 码的技术发展可以大致分为以下阶段： 1 9 5 9 年r e e d 和s o l o m o n 利用有限域中的多项式第一次构造出了r s 码； 1 9 6 1 年g o r e n s t e i n 和z i e r l e r 9 】发现了r s 码是多元域本原b c h 码的一种子码，给 出了r s 码时域编码，并且给出了b c h 码以及r s 码的译码算法。紧接着c h i e n t l 0 】和 f o m e y 1 1 1 进一步改进了算法。但是这些译码算法在可纠错误个数较多时仍然不够有效； 1 9 6 7 年b e r l e k a m p 1 2 1 突破性地构造了一种有效译码算法，使得r s 码能够强大有效 地纠正大量的错误； 1 9 6 8 年m a s s e y 1 3 1 证明了b e r l e k a m p 算法等于一种基于快速的线性反馈移位寄存器 的算法，进一步提高了译码的效率； 1 9 7 5 年s u g i y a m a ，k a s a h a r a ，h i r a s a w a 和n a m e k a w a 【1 4 1 证明e u c l i d 算法能有效地 对b c h 码和r s 码译码； 1 9 9 1 年由于意外事故，发射至木星的g a l i l e o 号飞船的高增益天线损毁，只能使 用低增益天线，引发准软判决算法研究大热，从此为各类通信系统设计的r s 码准软判 算法层出不列1 5 】【1 6 】； 雨尿邮il 1 人学坝i ： o f e 生字位论义 第一币矫论 1 9 9 9 年g u r u s w a m i 和s u d a n ( g s ) 【1 7 】提出了一种能够超越r s 码硬判译码半径的代 数列表译码，r s 码的软判译码隐现曙光； 2 0 0 4 年k o e t t e r 和v a r d y ( k v ) 0 8 在g s 算法的基础上提出了一种基于多项式的低复 杂度代数软判决译码( a s d ) 算法，该算法与硬判决算法( h d d ) 有着明显的增益，宣告了 r s 码软判决译码时期的到来；从此，g a u s s 算法 19 1 ，c h e m o f f 算法【2 0 1 ，a b p 算法【2 l 】， 分解译码【2 2 】【2 3 1 以及各种级联型算法接踵而至。虽然软判决译码算法的性能越来越好， 但复杂度也水涨船高，可以说至今没有能够在实际中被应用的r s 码软判决算法。 2 0 0 5 年r s 码最大似然译码( m l d ) h i 题被g u r u s w a m i 和v a r d y 2 5 】证明是n p h a r d 问题。因此，寻找逼近m l d 性能且低复杂度的r s 码译码算法成为了纠错码领域的一 个炙手可热的问题。 1 3 课题意义 r s 码由于具有诸如对随机错误、突发错误纠错和纠删的能力，获得了广泛的应用。 当今世界，每年有数十亿美元的资金投入到编解码产品研发与生产中，并且每分钟译出 的数以百万的码字中，毫不夸张的讲，至少有四分之三是与r s 码相关的。 每个使用计算机的人实际上是在和r s 码打交道。这几十年来，r s 码广泛应用于 硬盘等电磁存储设备。如果信道编码方面没有诸如t u r b o 码【2 1 的发明和l d p c 码【7 】的复 活等其它突破，没有人会怀疑r s 码的垄断地位会受到动摇。然而这些码也不是十全十 美的，存在一个错误平底问题有待解决，因此，在实际应用中，r s 码常常作为级联的 外码用来纠正它们的错误平底问题。其它的存储设备如c d 和d v d ，将r s 码和r s 乘 积码级联作为它们纠错码的标准。值得一提的是，这些数字存储设备正在我们的日常生 活中扮演着越来越重要的角色，例如：手机，个人数字助理( p d a s ) ，数码相机和高清电 视等等。 没有r s 码，深空探索也许只是一个梦。“旅行者”把探测到的图像数字化经r s 码编码后发送给我们。r s 码在现有的各种探测操作中被广泛的使用，并且在将来的探 测任务中将再现光芒，例如，r s 码以及r s 码的级联码被用于深空通信和卫星通信的 视频播送。 r s 码在第三代( 3 g ) 无线标准和c d m a 2 0 0 0 高速广播包数据的空中接口中被用作外 码，并有望在第四代无线通信系统中作为级联的外码使用。a d s l 接入网的h a r q 差 错控制系统采用分组交织的r s 码来维持较高的吞吐量和可信度。此外，交织r s 码也 4 堕塞! ! ! ! ! ! 坚叁兰堡：! ：型! 壅竺兰竺堡苎笙二翌笪笙 是1 0 g b p s 高速光纤网络传输的标准用码。 从上文分析可知，r s 码与我们的生活息息相关。然而在实际应用中r s 码的译码 算法往往采用的是硬判决译码算法，未能充分利用信道的软信息，于是寻找一种低复杂 度的、高效的软判决译码算法就成为当今编解码理论界的热点。 1 4 本文的主要工作及章节安排 本文主要研究了r e e d s o l o m o n 的各种软判决译码算法，内容包括r s 码的代数软 判决译码的改进译码算法c h a s e a s d 及其简化算法s i m p l i f i e dc h a s e a s d 、r s 码自适 应置信度传播的改进算法m a b p 、基于自适应置信度传播( a b p ) 算法利用累积对数似然 t i , ( a l l r ) 或者多重偏置( m u l t i p l eb i a s e s ) 进行级联的可信度迭代级联软译码算法、 a w g n 信道下同码长同码率的r s 码与短l d p c 码之间的译码性能比较及分析。主要 成果如下： l 、为了充分利用接收比特的可信度信息，将c h a s e 算法用于a s d 算法的前端，形 成了a s d 的改进算法c h a s e a s d 算法。针对c h a s e a s d 译码复杂度高的情形，我们将 统计平均的思想引入到对a s d 前端重度矩阵的处理中，形成了低复杂度的s i m p l i f e d c h a s e a s d 译码算法，并将它们的译码性能进行了比较； 2 、a b p 软判决译码的思想是由b p 算法演进而来，而r s 码的校验矩阵中的环4 较多，属于h d p c ( h i g hd e n s i t yp a r i t yc h e c k ) 码，得通过高斯消去处理化成近似l d p c 的码字处理。高斯消去的计算复杂度很高，我们可以通过增加a b p 内部b p 迭代的次 数来减少外部迭代的次数，即减少高斯消去的次数，从而降低译码的复杂度；此外，结 合修改外部校验矩阵迭代的随机移位步长，形成r s 码的m a b p 软判决译码算法； 3 、将累积对数似然l 匕( a l l r ) 或者多重偏置( m u l t i p l eb i a s e s ) 弓 入到基于a b p 的级 联译码算法中，改变了传统的级联译码算法的级联结构，形成新的改进的级联软译码算 法，并比较了其与传统级联算法的性能： 4 、将同码长同码率的r s 码和短l d p c 码在a w g n 信道下，采用不同的软判决译 码算法进行了译码性能的比较和分析。 本文的章节做如下安排： 第一章为绪论，简要介绍了纠错码的发展与现状、r s 码的发展和主要工作。 第二章给出了信道编码的基本理论、线性分组码的概念以及传统的译码算法。 第三章介绍了r s 码相关的基础知识及其代数硬判决译码算法。 南京邮i 【1 人学硕1 ：研究生学位论文第一章绪论 第四章在研究了k v 算法以及简化的k v 算法之后，给出了c h e m o f f 算法和b g m d 算法详细的译码步骤，考虑到b g m d 算法没有充分软信息，于是在b g m d 算法思想的 启发下，提出了一种充分利用比特可信度信息的代数软判决译码( a s d ) 算法的改进算法 c h a s e a s d ，分析了算法的译码复杂度，针对c h a s e a s d 算法复杂度较高的情形，又给 出了简化的c h a s e a s d 算法，并通过仿真与其他算法进行了性能比较。 第五章在分析自适应置信度传播( a b p ) 算法和级联算法结构的基础上，将累积对数 似然k l , ( a l l r ) 级联方式引入到a b p 的级联算法中，提出了a l l r a b p o s d 以及 a l l r a b p b m a 算法；然后，将多重偏置引入到级联算法中，形成a b p b i a s o s d 和a b p b i a s b m a 算法，最后通过仿真，考察了其译码性能。在仿真的过程中，对于 同码长同码率的r s 码与短l d p c 码的性能比较也进行了相应的探讨。 第六章对全文工作进行了总结，并对下一步工作进行了展望。 6 南京i i i i ie t j , 人学硕：l j 研究生学位论文第_ 二章信道编码 第二章信道编码 2 1 数字通信系统的组成 图2 1 显示了一个基本的数字通信系统的功能性框图和基本组成部分【1 1 【2 6 l 。 图2 1 数字通信系统的基本模型 信源的功能是将载有信息的消息传送出去，其输出可以是模拟信号，如音频或视频 信号；也可以是数字信号，如电传机的输出，该信号在时间上是离散的，并且具有有限 个输出字符。有信源产生的消息经信源编码器变换成二进制数字序列。理论上，应当用 尽可能少的二进制数字表示信源输出，换句话说，我们要寻求一种信源输出的有效表示 方法，使其很少产生或不产生冗余。将模拟或数字信源的输出有效地变换成二进制数字 序列的处理过程称为信源编码或数据压缩。由信源编码器输出的二进制数字序列称为信 息序列，它被传送到信道编码器。 众所周知，信道中各种噪声和干扰是造成数字通信系统接收机误码的主要原因。与 信源编码器的解相关作用相反，信道编码器则是对信源编码器输出的离散信息序列适当 地添加冗余度( 或相关性) ，使接收机译码器具有自动t q 检错能力，以降低比特( 或 符号) 误码率。信道编码的最终目的就是在发射信号功率，传输系统所占用的信道带宽 和译码算法复杂度等因素的共同制约下提高信息传输的可靠性。 信道编码器输出的数字信号通常不适合直接在信道中传输，而调制器的作用就是将 该数字信号转化成易于在信道中传输的模拟信号。调制器产生有一定时间宽度的，适合 于传输媒质传输的时间有限信号，所有有限信号组成信道符号集。因此信道编码器的输 出被转换成该集合中相应的信号波形。 信道的功能是承载和存储信息。它包括从调制器输入至解调器输出的所有硬件设 备，传输媒质和存储媒质。硬件设备中存在热噪声和各种非线性失真，而传输媒质会引 入各种自然和人为的干扰，存储媒质则容易受到损伤。如移动通信中的多径传播和信号 7 塑塞! ! ! ! ! ! 坚叁兰堡：! 型! 丛竺兰竺丝兰兰三皇堡望笙塑 衰落，光缆中的信号色散，暴露在存储媒质表面的细小硬颗粒和读写设备不佳对存储媒 质所造成的物理损伤等。由于上述种种因素使得到达接收端的信号不可避免地产生失 真，从而使解调器的输出出现错误。有时为分析方便，我们亦把导致接收信号失真的各 种干扰，噪声和失真从信道中分离出来等效为一个如图2 1 所示的独立噪声源。 在接收端，解调器通常输出q 进制( q 2 ) 或模拟信号作为对受到噪声和干扰损伤 的接收信号的估计，随后信道译码器依据编码准则，信道特征和解调器的输出共同估计 发射端所传送的信息。如果将解调器的输出量化成两个电平，那么我们称之为硬判决解 调，相应的译码过程为硬判决译码。反之，如果将解调器的输出量化成q 个( q 2 ) 电 平，我们则称之为软判决解调。作为软判决解调的一个极端情况，q = 0 0 意味着无穷量 化或直接对解调器输出的模拟信号进行采样。与软判决解调相应的译码过程为软判决译 码。由于硬判决解调通常会造成信息不可逆转的损失，因此对性能要求较高的通信系统 一般均采用软判决解调。 同样信源译码器依据信源编码准则和信道译码器的输出共同估计发射端信源的输 出，最终将此估计输出传递给信宿( 用户) 。 2 2 差错控制系统与纠错码分类 在数字通信系统中，利用纠错码或检错码进行差错控制的方式大致可分为三种 【l 】【2 6 】【2 7 】： ( 1 ) 检错重发法：接收端在收到的信码中检测出( 发现) 错码时，即设法通知发送 端重发，直到正确接收为止。所谓检测出错码，是指在若干接收码元中知道一个或一些 是错的，但不一定知道该错码的准确位景。采取这种差错控制方法需要具备双向信道。 ( 2 ) 前向纠错法：接收端不仅能在收到的信码中发现有错码，还能够纠正错码。对 于二进制系统，如果能够确定错码的准确位置，就能够纠正它。这种方法不需要反向信 道( 传递重发指令) 也不存在由于反复重发而延迟时间，实时性好。但是纠错设备要比 检错设备复杂。 ( 3 ) 反馈校验法：接收端将收到的信码原封不动地转发回发送端，并与原发送信码 相比较。如果发现错误，则发送端再进行重发。这种方法原理和设备都较简单，但需要 有双向通道。因为每一信码都相当于至少传送了两次，所以传输效率较低。 信道纠错码中的码分类： 南京邮l u 人学硕i ：g d z 生学位论文第二二章信道编码 信道编码中用到的码类有很多种，为了清楚起见，我们用图2 2 表示。 2 3 信道模型和信道容量 图2 2 纠错码分类 在有扰信道中进行可靠信息传输的基石是s h a n n o n 于1 9 4 8 年提出的有扰信道随机 编码定理，简称为s h a n n o n 定理【1 1 。它明确地指出任何一个有扰信道均存在一个确定的 信道容量c ，对于小于此信道容量的信息传输速率，存在一种编码方式，当采用最大似 然译码且码长趋于无穷大条件下，其译码错误概率亦趋近于零。 2 3 1 二进制对称信道 o 1 - p 0 l 。p 图2 3 二进制对称信道( b s c ) 的转移概率 一个加性噪声信道，把调制器，信道，噪声源和解调器等效视为一个如图2 1 所示 的等效信道，如果调制器采用二进制波形，解调器实行硬判决，这就构成了如图2 3 所 示的信道，它具有离散时间的二进制输入序列和离散时间的二进制输出序列，这样一个 合成信道的特点是它有一个可能输入值与输出值的集合均取自 0 ，1 ) ，以及一组表示可 o 南京邮i u 人学顾 ：研究生学位论文 第二章信道编码 能输入与可能输出之间关系的条件概率，如果信道噪声和其他干扰导致传输的二进制序 列发生统计独立的差错，那么平均差错概率p 是 p ( y = 0x = 1 ) = p ( y = 1lx = 0 ) = p p ( y = 1lx = 1 ) = p ( y = 0ix = 0 ) = 1 一p ( 2 1 a ) ( 2 1 b ) 这种对称的二进制输入、二进制输出信道简称为二进制对称信道( b s c ) 。由于这种 信道的每个输出比特仅与对应的一个输入比特有关，所以说该信道是无记忆的。 2 3 2 离散无记忆信道 离散无记忆信道b s c 可视为一种更广义的离散输入，离散输出信道的特例。一般 的情况即m 进制( m 2 ) 输入q 进制( q m ) 输出离散无记忆信道( d m c ) 。 如图2 1 所示，由信道编码器输出至d m c 的m 进制符号集为x = x 0 ，x l ，x m 一。) ， d m c 输出q 符号集为y = 秒o ，y 。，y q _ i ) ，该信道的转移概率为p ( y ，ix i ) 。信道输入x 和输出】，的平均互信息定义为 2 】 脚) = 姜芝x j ) l 。g i = o i = o等 ，( x ；y ) = ，io 等 1 、l f ， 由上式可知，输出y 与自身的平均互信息i ( y ；y ) 为 d l 咿；聊= 地) l o g 而l i = o1 、f ， ( 2 2 ) ( 2 3 ) ，( 只】，) 亦称作为输出】，的( 无条件) 熵，通常用( n 表示。在输kx 被观察到情 况下输出l ，的条件熵h ( yix ) 定义为 m l0 - 1 1 胛2 荟i = o 嘶小g 赢斋i ，= o1 fi “， 因此由( 2 2 ) 式所定义的互信息i ( x ；y ) 亦可以表示为 ，( x ；】，) = h ( 】，) 一h ( yx ) ( 2 4 ) ( 2 5 a ) 它表示输出j ，y 由于输入0 x 被观察到后所减少的熵( 不确定性) 。易证 ，( x ；y ) 也可以表示为输入x 由于输出】，被观察到后所减少的熵，即 l o 南京邮l u 大学硕l ：g f 究生学位论文 第二章信道编码 ，( x ；y ) = h ( x ) 一h ( xly ) 对于一般d m c ，s h a n n o n 定义它的信道容量c 为l 】 ( 2 5 b ) c = m 驯a x i ( x ；y ) h 1 胁l ( 2 6 ) 如果对数以2 为底，c 的单位为比特( b i t s ) 信道符号，即每个在d m c 中传输的符号 所包含的最大平均比特数。如果采用自然对数e 为底，c 的单位为奈特( n a t s ) 信道符号。 对于如图2 3 所示的二进制对称信道( b s c ) ，它的信道容量可由( 2 6 ) 和( 2 5 a ) 计算， 即 c = m a x h ( y ) 一h ( y iz ) ) i 。o 1( 2 7 ) 厂i 工 令p ( x = 0 ) = p o ，则p ( x = 1 ) = 1 一p o 。由( 2 4 ) 式可得条件熵h ( yix ) 为 1l h ( yix ) = 一p ( x j ，y f ) l o g p ( y ，lx j ) j = oi = o = 一 p o ( 1 一p ) l l o g ( 1 一p ) 一p o p l o g p 一 ( 1 一p o ) p l l o g p 一 ( 1 一p o ) ( 1 一p ) l o g ( 1 一p ) = 一p l o g p 一( 1 一p ) l o g ( 1 一p ) = 日( p )(