（通信与信息系统专业论文）低密度校验码的性能分析及最小和算法.pdfVIP

摘要 1 1 11 11 11 11 11 1 11 11 11iii y 19 5 8 5 3 5 低密度校验码( l d p c ) 是一种渐近逼近s h a n n o n 容量限的好码，其长码性能甚 至比t u r b o 码还要好很多。由于具有译码复杂度低、错误平层低等优点，低密度 校验码在信息可靠传输中的良好应用前景已经引起学术界和i t 业界的高度重视， 成为当今信道编码领域最受瞩目的研究热点之一，低密度校验码的应用也已经被 广泛关注。 作者在对l d p c 码基本编译码理论的理解基础上，对影响l d p c 码性能的因素 做了深入的分析；并研究了采用最小和算法l d p c 码的量化译码设计。本文研究了 l d p c 码的量化译码，提出了一种基于密度进化理论优化设计低密度校验码最小和 量化译码器的算法，此种算法能够大大降低译码复杂度，同时译码性能损失也很 小。 l d p c 码的实用化道路还是很漫长的，虽然l d p c 码的性能优越，但是编码问题 一直很难解决。因此，对l d p c 码的编码方面还需要做进一步地研究，如码的构造 及线性编码问题。量化译码也是l d p c 码实用化过程中的关键问题。作者仅对l d p c 码量化译码做了粗浅的研究，如何设计一个复杂度低但性能好的量化译码器是值 得深入研究的。 关键词：低密度校验码最小和算法量化译码 a b s tr 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 sa r eac l a s so fc a p a c i t y a p p r o a c h i n g e r r o r - c o r r e c t i n gc o d e s f o rl o n gc o d el e n g t h s ，l d p cc o d e sc a l le v e no u t p e r f o r mt u r b o c o d e s d u et ot h ea d v a n t a g e so fl d p cc o d e s ，s u c ha sl o w e rc o m p l e x i t yo f d e c o d i n g a n dl o w e re l t o rf l o o r , t h e i ra p p l i c a t i o n si nr e l i a b l ec o m m u n i c a t i o n sh a v er e c e i v e d g r e a t i n t e r e s t sa n dh a v eb e c o m eo n eo fm o s ta t t r a c t i v ef i e l di nc h a n n e lc o d i n gc o m m u n i t y n o w , t h ea p p l i c a t i o no fl d p ch a sb e e np u to nt h ea g e n d a t h i st h e s i s i n v e s t i g a t e s s o m ea s p e c t so fl d p cc o d e sw i t h e m p h a s i s o n p e r f o r m a n c ea n a l y s i sa n dq u a n t i z a t i o nd e c o d i n gs c h e m e so fl d p c c o d e s q u a n t i z a t i o n d e c o d i n go fl d p cc o d e si ss t u d i e d a ne f f i c i e n tq u a n t i z a t i o n - d e c o d i n gs c h e m ei s p r o p o s e dw h i c hc a ng r e a t l yr 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 hal i t t l ep e r f o r m a n c e l o s s a l t h o u g hl o n gl d p cc o d e sa l eg o o d ，t h ee n c o d i n gp r o b l e mi sh a r dt os o l v e s o t h es t u d yo f e n c o d i n ga n dq u a n t i z a t i o nd e c o d i n ga l g o r i t h mi se s s e n t i a lt ot h ep r a c t i c a l u s e k e y w o r d s ：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 sm i n i m u m s u m a l g o r i t h mq u a n t i z a t i o nd e c o d i n g 第一章绪论 第一章绪论 本章简要介绍了数字通信与信道编码的关系，回顾了信道编码理论与技术的 发展历程；给出了常见的几种信道模型及其容量计算；概述了l d p c 码的历史和 现状；最后总结了作者在攻读硕士期间所做的主要工作并给出了本文内容安排。 1 1 数字通信与信道编码 通信系统旨在将信息由信源高效、可靠、有时还需安全地传送到信宿。有扰 通信信道的噪声会对传输信息产生干扰，从而可能降低通信可靠性。所以，通信 系统设计的中心问题是在随机噪声干扰下如何有效而可靠地传输信息。在数字通 信系统中可靠与快速往往是一对矛盾。若要求快速，必然使每个数据码元所占用 的时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误的可能性增加， 传送信息的可靠性减低。若要求可靠，则使得传送消息的速率变慢。因此，如何 较合理地解决可靠性与速度这一对矛盾，是正确设计一个通信系统的关键问题之 一。 数字通信系统的可靠性用错误比特率( 8 e r ) 衡量，有效性用传输速率衡量。早 期的人们普遍认为：通信系统的可靠性与有效性是一对不可调和的矛盾，在有扰 通信信道上实现任意小错误概率的信息传输的唯一途径就是把传输速率降低至零 i l l 。s h a n n o n 信息和编码理论的奠基性论文“通信的数学理论 2 1 ”- 于1 9 4 8 年发表之后， 改变了这一观念。他首次阐明了在有扰信道中实现可靠通信的方法，指出实现有 效而可靠地传输信息的途径是编码。在这篇论文中s h a n n o n 证明了数据压缩和传输 的基本定律从而奠定了信息理论的基石，s h a n n o n 也因此被称为“信息论之父”。根 据s h a n n o n 的信息理论，数字通信系统的基本组成如图1 1 所示1 3 j 。一般的通信系统 均可以用图1 1 来表示。如图上所示，发送端包含四个模块：信源、信源编码、信 道编码和数字调制器。 信源编码就是用二进制( 或多进制) 序列来表示信源输出的过程，其目的是 除去信源的冗余以减少通信负担，因而也称为数据压缩。任何信源都有一个被称 为信源熵的量，它表征了信源的平均不确定程度。信源编码定理【4 】指出信源熵是数 据压缩的下界；信道编码与信源编码正相反，它通过在信息序列中引入冗余来实 现通信的可靠性，任何信道都存在一个被称为信道容量的值，它表征了信道的传 输能力；数字调制就是将信息序列映射成适合信道传输的信号的过程。对应地在 接收端也有相应的四个模块用于实现相反的过程。 综上所述，信道编码是解决通信有效性和可靠性这对矛盾的关键，也是实现 通信系统经济性所必需的。但是，s h a n n o n 在“通信的数学理论”中关于信道编码定 2 低密度校验码的性能分析及最小和算法 理的证明是存在性的，因而如何在实际系统中实现信道编码仍然是一个难题。 编码信道 图1 1 数字通信系统的模型 1 2 信道编码定理和s h a n n o n 限 1 2 1 信道编码定理【5 1 信道编码定理和信源编码定理、率失真理论一起构成了s h a n n o n _ 三大编码定 理。s h a n n o n 在证明上述信道编码定理时的三个条件： 1 ) 编码采用了随机编码思想； 2 ) 让码长趋于无穷； 3 ) 译码采用了最大似然译码。 1 ) 、2 ) 使得码本身具有卓越的纠错性能，而3 ) 中的最大似然译码使得码的纠错 性能得以从分发挥。但是，采用随机编码，使码长趋于无穷大并且采用最大似然 译码将会使系统的复杂度和延时变得太大，因而无法在实际中使用。 每个信道具有确定的信道容量c ，对任何小于c 的码率r ，存在有速率为r 码长 为n 的分组码及( n o ，k o ，m ) 卷积码，若用最大似然译码，则随着码长的增加其 译码错误概率p 可任意小1 6 j ，即 p 4 p 一”删 ( 1 1 ) p 4 p 侧州r = 4 p 一幔m ) 式中，4 和4 为大于0 的系数，乓( r ) 和e ( r ) 为正实函数，称为误差指数。 通过增加信道容量c ，从而使e ( r ) 增加；在r 一定的情况下，增加分组码长n ； 这两种方法都可以使p 指数下降。 任意离散输入无记忆平稳有噪信道都有一个被称为信道容量的值c ，它标志 第一章绪论3 着信道传输能力的上限，只要信息传输速率r c ，就存在一种编码方式，当平均 码长足够大时，译码错误概率可以做到任意小；反之，则无论采用何种编码方式 也不可能保证错误概率任意小。 1 2 2s h a n n o n 限 1 9 4 8 年s h a n n o n 在“通信的数学理论”中推导了波形信道在加性高斯白噪声下的 信道容量： 。刖o g z 1 + 最1 ( 1 3 ) 式中是信道带宽，e 是信号的平均功率，o 是噪声的单边功率谱密度，c 是信道容量( 单位为b i t s ) 。在数字通信系统中，e 是每信息比特需要的传输能量。 面c l 0 9 2 叶导宰静 e h 磐烨一1 n qc | w 每= 瓣斋- - - l n 2 - - 1 6 招 m 4 ， 昂o 一1 6 d b 就可以实现高斯白噪声信道下的无误传输。这是带宽无限高 斯白噪声信道的极限传输能力，称s h a n n o n 。 1 3 低密度校验码的历史和发展现状 早在1 9 6 2 年g a l l l a g e r 已经提出正则低密度校验码( r e g u l a rl o wd e n s i t yp a r i t y c h e c kc o d e s ) 和迭代译码( i t e r a t i v ed e c o d i n g ) 的概念【刀，然而直到上世纪9 0 年代中期 l d p c 码被s p i e l m a n 、m a c k a v 和n e a l 等学者【8 ，9 】重新发现后，它才重新引起人们的广 泛关注。为什么性能如此杰出的码会沉寂几十年才被人们认识呢? g a l l a g e r 曾说过 这是因为在l d p c 码提出不久，f o m e y 提出了级联码的思想，而当时大多数人都认 为级联码更有可能取得好的性能。当然，还有一个原因就是当时的硬件水平尚未 成熟，实现那么长的l d p c 码( l d p c 码的短、中码的码长已经达到几百、几千的量 级) 非常困难，致使l d p c 码几十年来一直无人问津，只有寥寥几篇文章。其中有一 篇是1 9 8 1 年t a n n e r 发表的获奖文章“ar e c u r s i v ea p p r o a c ht ol o wc o m p l e x i t yc o d e s ” b o ，当然这篇文章获奖已经是低密度校验码重新被人们认识后的事了。通过这篇 文章，t a n n e r 为基于图模型的码奠定了基石。文中引入了l d p c 码的二部图模型 ( b i p a r t i t eg r a p h i c a lm o d e l ，现在称为t a n n e r 图) ：图1 2 给出了一般l d p c 码的t a n n e r 4 低密度校验码的性能分析及最小和算法 图表示。图1 2 中黑色圆圈表示码字中的符号，方框表示局部约束关系。t a n n e r 将 l d p c 码中的局部约束关系推广到一般的线性码中，并发现上述模型包含了乘积码 以及由简单码递归构造的码类。同时，t a n n e r 还提出了现在所说的“最小和”算法( 或 者称为“最大积”算法) 。t a n n e r 对基于图模型码类的贡献使我们认识到：如果对相 对简单的码进行迭代译码，那么译码器可以采用并行结构，符合当今大规模集成 电路技术的要求；因为译码器可以有效地使用软判决信息，并且采用了并行结构， 此外译码复杂度也很低，所以即使对长码进行译码，速度也很快。 蓼 慕 图1 2l d p c 码的t 锄e r 图 图1 3 因子图 l d p c 码的复兴和t u r b o 码的出现紧密相关。1 9 9 3 年，c b e r r o u ，a g l a v i e u x ，a n d et h i t i m a j s h i m a 提出令人震惊的t u r b o 码【1 1 l 一离b i a w g n 信道s h a n n o n 容量限只有 0 5 d b1 1 b 0 码成为继u n g e r b o e c k 提出t c m 【1 2 j 之后信道编码的又一里程碑。t u r b o 码给人们带来了一个重要启示：迭代译码可以获得接近最大似然译码的性能。于 是，迭代译码思想成为信道编码理论界的研究热点，也被用在通信的各个方面， 如信道均衡。经过j h a g e n a u e r 等人的总结，迭代译码思想上升为现在我们所熟知 的t u r b o 原理( t u r b op r i n c i p l e ) 。与此同时，各种t u r b o 1 i k e 码也纷纷涌现：b e n e d e t t o 的串行级联t u r b o 码、s i p s e r 和s p i l m a n 的扩展码、t o m a d o 码、重复累积( r a ) 码和李 坪的c t 码等等。当然这其中也有同样采用迭代译码的低密度校验码。( 所有的 t u r b o 1 i k e 码都由结构简单、译码复杂度低的分量码和伪随机置换矩阵组成，并且 t u r b o 1 i k e 码有两个共同点：可以采用图模型表示、构造；采用迭代译码思想。) l d p c 码研究的兴起，除了t u r b o 码的研究热潮为它提供了契机，还有两方面 原因【l3 】：一方面是由于s p i e l m a n 、m a c k a y 等几位学者独立研究了低密度校验码， 发现l d p c 码有杰出的纠错能力；而另一方面是由于w i b e r g 在他的关于基于图模型 码的论文中作了拓荒性的研究工作 1 4 , 1 5 】。s p i e l m a n 在他的论文中基于扩展图 ( e x p a n d e rg r a p h s ) ，基于l d p c 码设计了一种具有渐进好纠错性能的码类，称为扩 展码。这种码可以线性时间编、译码。此后不久，a l o n 和l u b y 把这些结果应用到 i n t e m e t 丢包的问题中，设计t t o m a d o 码【l6 。t o r n a d o 码是第一个商用化的l d p c 码。 在删除信道中，线性码的译码问题等价于解线性线性方程组，通常求解一般线性 方程组的时间复杂度不是线性的，但是如果方程组中的每个方程都只有一个未知 数( 或者通过迭代等效于每个方程只有一个未知数) 的话，那么译码将变得非常 第一章绪论 5 简单。此后，l u b y 研究发现使用非规则图并优化度分布序列可以使码的性能逼近 删除信道的容量限，即当传输速率接近1 一p 时( p 为删除概率) 可以取得非常小 的误比特率。 f i t s t p a r i t y b i t s d a t a -广- 卜 -u- n - 1 卜_ 广- -uo - -厂 l - l l w 盯：h- 十一1r-* 至 l 一厂 一 1 广一 - 口一 ：hz 几一 ：ih - h - iu-t 1 广一 t r e l l 缸 s e c o n d p a r i t y b i t s 图1 4t u r b o 码的因子图模型图1 5l d p c 码的因子图模型 w i b e r g 的最大贡献在于他把t a n n e r 图进行了扩展，引入了状态节点。扩展后 的图仍然是二部图，称为因子图( f a c t o rg r a p h ) ，因子图模型如图1 3 所示。图1 4 和图1 5 分别为t u r b o 码和l d p c 码的因子图模型。因子图中的符号节点与t a n n e r 图中的符号节点含义一致，是可以观测得到的；而状态节点是内部的，不能由外 部观测得到，它是由设计者添加用以简化码的图模型表示。引入状态节点使得图 码和网格码得到了统一，图1 6 为通常网格码的因子图模型。图中4 为符号节点， s 为状态节点，而g 是约束关系，它决定了允许的状态转移和输出( & ，a k ，8 k + 1 ) ( t r e l l i ss e c t i o n ) 。 最g 图1 6 网格码的因子图模型 图1 7r a 码的因子图模型 除了对码的图模型表示作出了杰出贡献之外，w i b e r g 对译码也作了深入的研 究。他明确地给出了最小和算法( r a i n - s u ma l g o r i t h m ) 及和积算法( s u m - p r o d u c t a l g o r i t h m ) 的特征，并且指出如果用“求最小值”( m i n ) 运算代替“求和”( s u m ) 运算，用 “求和”( s u m ) 运算代替“求积”( p r o d u c t ) 运算，那么这两种算法在本质上是一样的，更 进一步他给出了“半环 ( s e m i r i n g ) 扩展。此外，w i b e r g 还证明了无环图上这两种算 法分别对应着最大似然译码和最大后验概率译码。特别地，在网格图上分别退化 成v i t e r b i 算法和b c j r 算法。这些结果促使研究工作者将这两种算法应用到有环图 6低密度校验码的性能分析及最小和算法 中，也取得了令人非常满意的结果。 此后，经过众多学者的研究，l d p c 码的理论研究得到了蓬勃发展。t o r n a d o 码的理论分析技术被r i c h a r d s o n 、u r b a n k e 等学者的发展之后，可以应用到a w g n 信道中非规贝j j l d p c 码的长码设计当中以满足各种不同应用目的。给定一个具有任 意度分布的二元l d p c 码，这几位学者指出【r 7 】在对称信道中采用和积译码算法时概 率密度的进化可以精确计算出来。此外，他们还证明了当码长足够大、迭代次数 足够多时，存在一个门限值，如果噪声低于这个门限就可以实现无误传输。而这 个门限值可以通过选择度分布序列进行优化。仿真结果表明用这种方法设计的码， 当码长达到1 0 5 时其性能要优于t u r b o 码。c h u n g 等人设计了l 2 码率的l d p c 码，其 门限值离s h a n n o n 限在0 0 0 4 5 d b 之内l l 引。 d i v s a l 8 2 、m c e l i e c e 等人提出的重复累积码( r ac o d e s ，r e p e a t - a c c u m u l a t ec o d e s ) 1 1 9 j 是一种构造非常简单的t u r b o 1 i k e 码，然而其性能却比t u r b o 码出现之前的任何码 都好，离s h a n n o n 限在1 5 d b 之内。r a 码的分量码是( n ，1 ，n ) 的重复码和2 状态、码率 为1 的卷积码( 其生成多项式为g ( d ) = 1 ( 1 + d ) ) ，分量码之间通过伪随机交织器连接， 如图1 7 所示。其他一些学者也提出一些简单码类，其性能与r a 码相当，有的甚至 更好。香港城市大学李坪博士所提出的c t 码( c o n c a t e n a t e dt r e ec o d e s ) 【2 0 j 就是一例。 c t 码由m 个2 状态网格码通过交织器交错连接在一起。c t 码可以看成是一种l d p c 码，其译码复杂度很低，但是性能却和同样码长的t u r b o 码相当。这样看来，简单 的码通过大的伪随机交织器连接在一起并且采用和积算法( s u m p r o d u c ta l g o r i t h m ) 译码将会获得接近s h a n n o n 容量限的纠错性能。 近年来，l d p c 码的理论研究已经取得了相当丰硕的成果。研究表明l d p c 码 具有如下一些优点：1 ) 长码时，l d p c 码的性能优于t u r b o 码。在二元输入加性白 高斯噪声信道( b i a w g n c ) 下，c h u n g 等人所优化设计的非规贝i j l d p c 码离s h a n n o n 容量限只有0 0 0 4 5 d b ；2 ) l d p c 码具有一套线性复杂度的译码算法，即消息传递 算法，相l 匕t u r b o 码的译码算法要简单得多，而且可以实现并行处理，因此其译码 延时短，更适用于大吞吐量的应用场合；3 ) 相对t u r b o 码而言，l d p c 码具有更低 的错误平层，并且多数译码错误都是可以检测的；4 ) 由于l d p c 码完全由其校验 矩阵决定，因此可以灵活设计各种参数的l d p c 码。正是因为这些原因，l d p c 码 已经被d v b s 2 等一些国际标准所采纳。 正是由于l d p c 码具有上述诸多优点，它在通信领域的许多方面都有很好的应 用前景，如网络数据传输、光纤通信、深空通信、图像传输、下一代无线通信系 统、磁记录、用户数据线( d s l ) 、数字图像水印等。l d p c 码已经为几个国际标 准所采纳，国内外一些单位和公司已经研制开发出相应的l d p c 码编译码器。2 0 0 4 年1 月正式颁布的d v b s 2 标准采用了l d p c 码和b c h 码级联的方式来实现纠错功 第一章绪论 7 能。f l a r i o n 公司已经开发出名为v c c t o r _ l d p c 的l d p c 码编译码器【5 4 1 。 1 4 本文的主要研究工作和内容安排 本文首先回顾了信道编码理论与技术的发展历程，其次介绍了低密度校验码 编译码原理，分析了影响低密度校验码性能的因素，介绍和仿真了相关优化算法； 介绍了低密度校验码的量化译码，最后对一种优化设计最小和量化译码器算法进 行了研究，该算法可以大大降低译码复杂性并且译码性能损失不大。 8 低密度校验码的性能分析及最小和算法 第二章l d p c 码的编译码原理 9 第二章l d p c 码的编译码原理 2 1l d p c 码的因子图表示 因子图是一个表示因式分解结构的二部医 ( b i p a r t i t e ) ，图中每一个变量节点对 应一个变量，每一个因子节点对应一个局部函数，当且仅当变量是局部函数的自 变量时，相应的变量节点和函数节点之间存在一条连接边1 2 1 1 。 因子图是一个通用模型，它归纳了目前所有的图模型定义，认为图模型本质 上是要表达一个全局函数到一组局部函数乘积的有效分解。在码表示应用中，因 子图把编码过程中产生的码字约束分解为基于码元子集的局部约束，或者基于全 概率公式把译码过程中码字的后验概率( a p p ) 测度分解为码的先验约束和信道转 移概率的乘积，实现基于局部函数的迭代边界计算，最后渐进地逼近最佳译码。 2 1 1 码结构表示 一个码长为、信息位数为k 的线性码由一个生成矩阵g 。定义，信息序列分 组墨。通过g 被映射到码字x = s t ；。线性码可以由一致校验矩阵日m 。等效描述， 所有码字均满足h x r = 0 。校验矩阵的每一行表示一个校验约束z ，其中所有非零 元素对应的码元变量x ，构成一个校验集，由一个校验方程表示。校验矩阵的每一 列表示一个码元符号参与的校验约束。码元变量与校验方程之间的关系称为结构。 下面，我们主要对二元l d p c 码进行讨论。 l d p c 码是一类线性码，由其校验矩阵具有的稀疏特点而命名，即口中的元素 几乎全部是o ，只有极少量的非零元素。g a l l a g e r 最早定义的二元( ，以，以) l d p c 码是码字长度为、设计码率为r 。三l 一矾以的线性码，其校验矩阵日的每一列 都包含正好吐，个“1 ”、每一行都包含正好以个“1 ”。由于满足这个结构条件的校验 矩阵并不唯一，所以具有参数( n ，d ，d 。) 的l d p c 码构成了一个码集合。 一般，日可以依上述结构条件随机生成，但所给码的性能差异较大。如果日 矩阵各行线性独立，则实际码率r = r 。；否则，实际码率r = ( 一m ) n r o ， 其中m 7 是日行空间的维数。 10 l0 ol o1 1o 0l 1o o1 10 o1 01 1o 10 o l 10 o1 ( a ) 校验矩阵和方程组 0 0 0 0 i l i | = = 所鲰勋鲰 + + + + 以舴戥 + + + + 扔以胁缸 + + + + 崩而免毙 l o低密度校验码的性能分析及最小和算法 ( b ) 因子图表示 图2 1 ( 8 , 2 ，4 ) l d p c 码的校验系统及因子图表示 设一个( ，d ，d c ) 码c 具有校验矩阵h = ( ) m 。，其因子图模型可以表示为 一个二部图。码字向量x = ( 而，x 2 ，x ) 表示为一组变量节点缸，：= 1 ，) ，校 验约束表示为一组校验节点k ：扛1 ，m ) 。仅当h i i = 1 时，节点x ，和z 。之间由一 条边连接，节点x ，和z ，互称相邻节点，其间连接边称为这两个节点的相邻边。因 子图上每个变量节点具有盔，条入射边，即度数为d ，；每个校验节点具有d 。条入射 边，即度数为以，共有e = n d ，= m d c 条边。令集合m ( ) = f ：h o = 1 ) 表示变量x ， 的受限范围；令 ，( j ) = ，：办，= 1 ) 表示校验z 。的约束范围。 m 2 1 ( a ) 是一个( 8 ，2 ，4 ) 短码的校验矩阵及校验方程组，图2 1 ( b ) 是相应的因子 图表示。该图表示了校验约束结构码的全局函数f ( x l ，黾) ，也称码特征函数。每 个校验节点乙表示一个局部约束函数z ( 缸，：( 讲) 。全局函数因式分解为 厂( x l ，x 8 ) = 石( x l ，x 3 ，x 5 ，x 7 ) ( x l ，吒，x 8 ) 六( x 2 ，而，x 7 ) 厶( x 2 ，确，x 5 ，黾) ( 2 1 ) 定义指示函数为一个把布尔逻辑命题p 映射至w j g f ( 2 ) _ h 的二值函数： c p ，= 三：；：= n t r 嬲u e e ( 2 - 2 ) 式( 2 1 ) 中的各个函数均为指示函数，其中全局函数的逻辑命题为“x 是一个码 字”，每个局部函数的逻辑命题为图2 1 ( a ) 中的校验方程。式( 2 1 ) 又写作为 b c 】= 【五+ 墨+ x 5 + x 7 = 0 】 而+ x 4 + + = 0 】 x 2 + 屯+ k + x 7 = o 】 x 2 + 墨+ x 5 + x g = o 】( 2 3 ) 图2 1 ( b ) 的因子图实际上是一个有环r r t l l l c r 。注意到矩阵的第三列和第七列 中，1 出现在第一行和第三行两个两行位置上，对应在因子图中，依照无向边连接 关系，存在一个长度为4 的循环路径( x 3 ，z 1 ) 、( z i ，x 7 ) 、( x 79 2 3 ) 、( z 3x 3 ) 。类似地， 图中还存在另一个长度为4 的循环路径( x 。，z 2 ) 、( z 2 ，x 8 ) 、( x 8 ，z 4 ) 、( z 。，x 。) 。采用 迭代置信传播算法译码时，这种短环路将极大地影响码性能。码的最小汉明 第二章l d p c 码的编译码原理 ( h a m m i n g ) 距离及距离谱直接取决于环路的分布情况。因此构造码时，应该尽量消 除短环路【8 3 0 ，6 7 1 。 l d p c 码的因子图表示中，e 条边对校验节点的入射关系和对变量节点的入射 关系可以看作是相互置换，所以一个特定的码集合实际是满足特定条件的随机置 换函数集合。如果不限制变量节点和校验节点度数，那么随机置换函数有可能导 致变量节点和校验节点各自的度数不再恒定，这时入射边分布表示为一对度数分 布序列a = ( ，a 以) 和p = ( p l ，一，p a , ) 2 2 1 ，其中九，和p 。分别表示度数j 变量节 点的入射边比例和度数f 校验节点的入射边比例，西和d ，分别是最大变量节点度数 和最大校验节点度数。或用多项式兄( x ) = 克。a x j - i 和j d ( 功= 乌p i 石卜1 表示，这 时设计码率r ，p ) = 1 一j ：j d ) 出j ：a ) d x = 1 一篷譬：p ，f ) 侄名：t ) 。 当度数分布多项式退化为a ( x ) = x 几1 和j d 0 ) = x 肛1 时，变量节点和校验节点的 度数分别恒定为，和k ，相应的码就称为( ，j ，k ) 规贝j j ( r e g u l a r ) l d p c 码，反之称 为非规贝1 ( i r r e g u l a r ) l d p c 码。规则l d p c 码通常也称为g a l l a g e r 码。具有优化度数分 布a ( x ) 和p ( 功的非规则l d p c 码一般要好于规则l d p c 码，而且非规则l d p c 码的 性能已经超过了最好的m r b o 码t 2 3 1 。 2 1 2 后验概率分布表示 考虑时间离散信道上的一个分组码c ，设传输码字为x = ( ，x ：，x ) ，接收 码字为y = ( y l ，y 2 ，y ) 。根据全概率公式，信道输入和输出向量的联合概率( 密 度) 函数f ( x ，y ) = p ( x ) f ( yl 力，其中p ( x ) 是发送码字x 的先验概率，八少i 戈) 是发 送码字x 时接收j ，的条件概率( 密度) 函数或似然函数。基于给定的信道观察y ，对 码字集合c 的后验概率( a p p ) i 9 i 度p ( xij ，) 与联合概率函数f ( x ，j ，) 成比例，即 p ( xjj ，) = f ( x ，y ) f ( y ) o cf ( x ，y ) ( 2 4 ) 对于时间离散的平稳无记忆信道，似然函数具有如下的乘积形式 f ( ylx ) = f o l ，j ，2 ，y ，ix 1 ，x 2 ，h ) = 兀厂 ，ix ，) ( 2 - 5 ) 其中f ( y ix ，) ，j = 1 ，n ，是平稳信道的标量转移概率密度函数。 码字x 允许服从任何分布。如果假定所有码字被等概选取，即先验概率p ( x ) 为 一个常数，结合形如式( 2 1 ) 的码特征函数，可以表示为【2 l 】 1 p ( x l ，x 2 ，h ) = 斋f ( x l ，x 2 ，h ) ( 2 - 6 ) 1 2 低密度校验码的性能分析及最小和算法 图2 2l d p c 码的后验概率测度因子图 因此，联合概率函数f ( x ，y ) 可以比例表示为 mj v f ( x t ，x z ，x ；y 。，y ：，y ) 芘兀z ( ke ( ，) ) ) 兀f ( y ix j ) ( 2 - 7 ) f = l j = l 代入式( 2 - 4 ) 得到后验概率测度，即给定信道观察j ，时，x c 的后验概率为 m p ( xj ，) = a 兀z ( “：ke ( 1 - i f ( y ，ix j ) ( 2 8 ) i = 1 i = 1 其中口是使工。c p ( x j ，) = 1 的归一化因子。 在表示l d p c 码校验约束的因子图上，增加接收变量节点 夕j 及信道转移函数 书d a f ( y ，i 一) ) ，得到如图2 2 所示的表示码字后验概率分布p 伍ij ，) 的因子图。图 中，黑圆点表示局部校验函数，等同于图2 1 中的校验节点；黑方块表示转移函数 节点；圆圈表示发送变量和接收变量节点。 2 2 基于网格图的l d p c 码译码方法 对于l d p c 码校验矩阵的每一行可以看作一个单校验码，每行的译码就是为 了得到每个b i t 的外信息。从而可知每个单校验码都可以使用两状态的网格图来表 示。下面针对不同的测度方法对单校验码的译码进行说明，并给出各种方法之间 的关系。 2 2 1 置信传输的因子图表示及几种概率测度 l d p c 码可以根据校验矩阵构造t a n n e r l n ，并在t a n n e r 图的基础上进行译码。如 图2 3 所示的置信传输译码的因子图。 第二章l d p c 码的编译码原理 z tz 2z m 、 彤 q 、 、 ： k ； 髓 ； 图2 3 置信传播译码网格的因子图 图2 3 中所有变量节点为父亲节点，其邻节点为孩子节点。分析可以得到基本 传递消息的过程。蟛是毛节点向t 节点传递的校验消息，鳝是节点向刁节点传 递的变量消息，碍和研是外信息。用贝叶斯网络术语，劈表示刁根据其他父亲 毪：k 六k ( f ) 当前状态向宣称的“= 口使乞满足的的可信度，研表示 根据其他孩子包括z 和 & ：七f ，k m ( _ ，) ) 向z f 宣称的“= 口”的可信度。按照 t u r b o 原理，每个局部约束刁视为一个子码，这时群也称为子码毛产生的外信息。 对于二元输入信道中，对码符号甜 0 , i 和信道输入符号甜 + 1 ，一1 的讨论是 等价的，因此我们在下文中不致混淆时。设一个二元随机变量的概率分布率由 ( n 。，n 。) 或( 风，a ) 等价表示，下面式子定义了似然比( l r ) 、对数似然比( l l r ) 和概 率差三种量度 2 4 1 ，毫n l p _ 1( 2 - 9 ) m 曼l o g ( p + l p _ 1 ) ( 2 1 0 ) 肇= n l n l ( 2 - 1 1 ) 可以得到如下的转换公式： v ：肄 ( 2 1 2 ) 1 ，= i z 1 一助 、 卸：掣 1 3 ) ( 2 - 1 3 卸2 而 所：l o g 肄 ( 2 1 4 ) 1 一助 、 卸：尝：t a n h _ - m ( 2 1 5 )。 e ”+ 12 、 其中t a n h 三= ( p 。一1 ) ( e 。+ 1 ) 1 4低密度校验码的性能分析及最小和算法 2 2 2 基于概率测度的和积算法 根据2 2 1 中的表示，在概率测度下，变量消息和校验消息分别定义为 鳞- - p ( x j = 口l 儿，瓴：后m ( _ ) 0 ) 和巧- p ( z 。i _ = 口) 圆。对两者进行如下的推 导： q ；= p ( x j = z k k 删f ) ) = 罴笔卷铲 p ( x = a y ，) p ( ：k m ( ，) f ) l y ，x = 口) 一1 瓦瓦面不瓦厂 尸( x ：叫y 沙( 七m ( 州叫x j ：口) 尸( x j2 口 y j ) 删h 肼p ， )p ( z ：k ，( ) f ) ) = a 扩彤兀r 昌 ( 2 - 1 6 ) r ；= 尸( z ，l = 口) = p ( z ，xix = 口) = p ( z jfx ，= 口，x ) p ( xl 工= 口) = 尸( 乙ix ) 尸( xix ，= 口) = p ( z ，ix ) 兀p ( x 。) 苴2 玑 x ：- 。4 ， 6 ，( 7 ) 、j = 尸( z ，ix ) 兀璐 x ：x j = a ，t e , v ( o j ( 2 1 7 ) 其中式( 2 - 1 6 ) e f t ，为归一化常数，群是从上一次迭代中传递来的函数消息， 首次迭代时为初始值。式( 2 - 1 7 ) 中，p ( x k ) 是指特定求和组合x 中各分量矗取相应 值的概率，显然，群是一个似然概率。用于逐符号判决的最终变量消息为 彰= a 彤ii 筋a ( 2 - 1 8 ) 其中，口为归一化因子。相应的判锲准则是 曼，= a r g m a x q 口 ( 2 一1 9 ) 状态0 l q = ( s j _ l ，s j )j l j 图2 4 检验约束的状态图 第二章l d p c 码的编译码原理 若码字均匀分布，式( 2 1 7 ) 中p 瓴lx ) 替换为局部指示函数z ( ：j ( 讲) ， 表示校验约束毛只对码字x 局部进行约束。 若码字非均匀分布，假设码字概率分布为尸( x ) ，其中x c ，一般地尸瓴lx ) 计 算如下 尸( 乏ix ) = z ( _ ：j ( f ) ) 妒( x ) ( 2 - 2 0 ) i e c 上述各式中，我们限定五= 0 ，表示满足校验约束；( f ) 歹表示从( f ) 中去 掉后的子集，m ( ) 、f 从m ( y ) 中去掉f 后的子集。消息修正公式是基于无环有向 树结构推导的，即变量节点之间相互统计独立，函数节点之间也相互统计独立。 为实施有效计算，下面基于状态图对式( 2 9 ) 进行简化。设一个度数为的校 验节点z 具有父亲变量节点集 西，劫 ，考虑节点z 向节点妇传递消息。校验约 束关系可以用一个如图2 4 所示的有限状态机( f s m ) 描述。这是一个状态空间为 g f ( 2 ) 的一阶马尔可夫( m a r k o v ) 源，初始和终止状态均为零状态，g f ( 2 ) 上的部分 校验和为转移状态勺= 勺一。+ = ：；，晚。 用3 重组= ( s j _ l ，) 弓对转移分支进行标识，显然= s j + s j - l ，且有 l 哆l - 4 。分支概率 p ( 6 f ) = p ，ls ，1 产p o ，= j ，一s ，一1 ) 对状态屯，我们有 尸( & = o ) = p ( x l = o ) p ( 而= o ) + p ( x n = 1 ) 尸( 而= 1 ) 尸( 是= 1 ) = p ( 而= 0 ) p ( 而= 1 ) + p ( x n = 1 ) p ( x 2 = 0 ) 其概率差为 p ( s 2 = 0 ) - p ( s 2 = 1 ) = ( 尸( 毛= 0 ) 一尸( 五= 1 ) ) ( p ( 砭= o ) 一p ( 屯= 1 ) ) 经过有限归纳，对任意时刻后( 1 ，2 ，吃- z ，得凹( & ) = 兀：。凹( ) 不同时刻的一对状态& 和s ，( 七 ，) 之间一条路径的路径值为其所含分支概率 测度值的乘积。满足局部校验约束z 的任意一组配置 而，劫 ，必然对应图上一 条有效路径；且应该有魄= 电一。式( 2 - 17 ) 则表示所有堍= 0 的有效路径值之和或 者所有= l 的有效路径值之和。根据以上推导，得 p ) 2 p 魄一。) = 兀：1 廿( _ ) 所以，令 式( 2 9 ) 重新写为 ( 2 2 1 ) ( 2 - 2 2 ) 1 6 低密度校验码的性能分析及最小和算法 嵋= 兀级 k c n ( t ) u 为了满足式( 2 - 1 6 ) 的计算要求，需要做中间变换谫= ( 1 + 峨) 2 和 砖= l 一碍。 2 2 3 基于似然比度量的和积算法 ( 2 - 2 3 ) f 面给出似然比度量： 乃- n s ) = e x p 2 y x a 2 ( 2 2 4 ) 毫r m r = ( 1 + 屿) ( 1 - 饯) ( 2 2 5 ) b 兰骘踢= y ，兀 ( 2 2 6 ) k c m ( j ) 、j 为保证式( 2 - 2 3 ) 的计算，需要做中间变换g = o v - 1 ) ( r ，+ 1 ) 。最终消息定 义为： o 毫g o 场1 = y j 兀如 r a m ( j ) 2 2 4 基于对数似然比度量的和积算法 ( 2 2 7 ) 对数似然比量度的初始消息、校验消息和变量消息分别定义为甜三l o g ( y ) 、 三l o g ( ) 、兰l o g ( r ) 。根据以上定义，的初始值为o ，判决规则为 毛2 哆o 】。 t l j = 2 y j | t q 2 8 ) 吻= u j + ( 2 2 9 ) 讪降 = 。飘鼬降) 。， 吻三l 。g ( r u ) = l 。g ( 霹砖) = l 。g ( 7 1 + - a 堕& ) 蝇= 篙j 删、，瓯=