（通信与信息系统专业论文）低密度生在矩阵码的研究.pdf

摘要 删j i f f l | 川i i i 舢 y 19 5 8 5 2 6 。 稀疏图码( s p a r s eg r a p hc o d e s ) 在信道纠错和信源压缩方面都有突出的表现。 在信道纠错方面，应用稀疏图码可以在较低的编译码复杂度下获得逼近信道容量 性能。由于信道编码和信源编码( 有失真数据压缩) 存在对偶性，将稀疏图码应 用于信源编码时也能提供优越的性能，这一点引起了广泛关注。 本文介绍了低密度生成矩阵( l d g m ) 码在信道及信源编码中的应用。论文的主 要内容如下： 介绍了l d g m 码作为信道码时的译码算法一和积算法。分别研究了单个 l d g m 码，以及以l d g m 为分量码的串行级联方案，并给出了相应的仿真结果。 结果表明，串行级联方案克服了单个l d g m 码具有较高错误平层的缺点，在较低 的编译码复杂度下获取了逼近容量限的性能。 介绍了率失真的基本概念，研究了基于l d g m 码的二进制对称信源量化算法。 其中，真实度传播算法和修正的真实度传播算法具有较低的编码复杂度，适用于 短码长的规则l d g m 码；偏置传播算法基于一个足够简单的框架，在支持高速率 的同时能达到很好的率失真性能；而测度传播启发式抽取算法通过信息在因子图 上的传递，以及传递过程中适当的加权和抽取处理，最后收敛到l d g m 码字上。 仿真结果表明，这几种算法都可以提供优良的率失真性能。 实数域上的信源量化技术研究具有重大的应用价值，因此我们将二进制的信 源量化算法推广至实数域信源。我们研究了基于均方失真( m s e ) 准则的偏置传 播算法，与网格编码量化( t c q ) 相比，其实现复杂度更低，但损失一定的性能。 关键词：低密度生成矩阵稀疏图码信道编码信源编码量化 a b s t r a c t s p a r s eg r a p hc o d e sh a v ea c h i e v e do u t s t a n d i n gp e r f o r m a n c ei nb o t hc h a n n e lc o d i n g a n ds o u r c ec o d i n gf i e l d s s p a r s eg r a p hc o d e sa sc h a n n e lc o d e sc a ny i e l de x c e l l e n t e r r o r - c o r r e c t i n gp e r f o r m a n c ew i t hl o we n c o d i n ga n dd e c o d i n gc o m p l e x i t y s i n c et h e d u a lo fag o o de r r o r - c o r r e c t i n gc o d ei sa ne f f i c i e n tc o d ef o rl o s s ys o u r c ec o m p r e s s i o n , s p a r s eg r a p hc o d e sw h i c hc a l la l s op r o v i d eo u t s t a n d i n gp e r f o r m a n c ei ns o u r c ec o d i n g a t t r a c tw i d ea t t e n t i o n t h em a i nb o o yo ft h et h e s i sc o n c e r n st h ep e r f o r m a n c eo fl d g mc o d e sf o rc h a n n e l c o d i n ga n ds o u r c ec o d i n g t os u m m a r i z e ，t h ep o s i t i v er e s u l t so b t a i n e di nt h et h e s i sa r e a sf o l l o w s ： w ed i s c u s st h ed e c o d i n ga l g o r i t h mo fl d g m c o d e s s i n g l el d g m c o d e a n ds e r i a l c o n c a t e n a t i o no fl d g mc o d e sa r eb o t hi n v e s t i g a t e d t h e n , p e r f o r m a n c ec o m p a r i s o n a n da n a l y s i sw i mt h et w os c h e m e sa r ec o n d u c t e d t h e 锄rf l o o rr e s u l t i n gf r o mt h e p o o r d i s t a n c ep r o p e r t i e so fl d g mc o d e sc a nb ei m p r o v e dw i t hp r o p e rc o n c a t e n a t i o no f t w oc o d e s ，w h i l em a i n t a i n i n gt h ea d v a n t a g e so fl o wc o m p l e x i t y w ei n t r o d u c eb a s i ck n o w l e d g eo fr a t ed i s t o r t i o na n dl d g mc o d e s s o m e l d g m - b a s e da l g o r i t h m sf o rb i n a r ys y m m e t r i cs o u r c ea r ei n v e s t i g a t e d t m t h i n e s s p r o p a g a t i o na n dm o d i f i e dt r u t h i n e s sp r o p a g a t i o na r ee x c e l l e n ta l g o r i t h m sf o rs o u r c e c o d i n ge m p l o y i n gs h o r t - l e n g t hr e g u l a rl d g mc o d e sw i t hl o wc o m p l e x i t y b i a s p r o p a g a t i o n a c h i e v e st h es a m e n e a r - o p t i m a l r a t e - d i s t o r t i o np e r f o r m a n c ew i t ha s u b s t a n t i a l l ys i m p l e rf r a m e w o r ka n dm a k e sf a s ti m p l e m e n t a t i o nf e a s i b l e a n ds u r v e y p r o p a g a t i o ni n s p i r e dd e c i m a t i o na l s ot r a n s f e ri n f o r m a t i o no nt h e f a c t o rg r a p ha n d w e i g h tt h eu p d a t ei n f o r m a t i o n s i m u l a t i o nr e s u l t ss h o w t h a tq u a n t i z a t i o na l g o r i t h m sc a n a c h i e v eo p t i m a lr a t e - d i s t o r t i o np e r f o r m a n c e q u a n t i z a t i o na l g o r i t h m sf o rr e a l n u m b e rf i e l da r ev e r yi m p o r t a n t w ee x t e n d q u a n t i z a t i o na l g o r i t h mf r o mb i n a r ys y m m e t r i cs o u r c et or e a l n u m b e rf i e l d w ed e v e l o p m e a n s q u a r ee l l o r ( m s e ) - b a s e d b i a s p r o p a g a t i o na l g o r i t h m c o m p a r e d 谢也 t r e l l i s - c o d e dq u a n t i z a t i o n ( t c q ) ，t h ec o m p l e x i t yo ft h ea l g o r i t h mi sm u c hl o w e r 、) l ，i m p e r f o r m a n c ed e g r a d a t i o ni n c u r r e d k e yw o r d s ：l d g ms p a r s eg r a p hc o d e s c h a n n e lc o d i n g s o u r c e c o d i n gq u a n t i z a f i o n 第一章绪论 第一章绪论 本章首先介绍了低密度生成矩阵( l d g m ) 码分别用于信道码和信源编码的研究 概况，总结了现有的几种量化算法；而后又简单介绍了信道和信源编码原理；最 后给出了本文的主要工作和各章节的行文安排 1 1l d o m 码用于信道编码的研究进展 低密度生成矩阵( l o wd e n s i t yg e n e r a t i o nm a t r i x , l d g m ) 码是低密度校验 ( l o w - d e n s i t yp a r i t y - c h e c ll d p c ) 码的对偶码。在早期，由于规则l d g m 码的错 误平层独立于码长，因此它们被认为是渐进的坏码川。然而，仿真结果表吲3 】【4 】： 使用系统l d g m 码的信道编码方案可以得到接近于l d p c 码和t u r b o 码的纠错性 能。m a c k a y 、c h e n g 以及w i c k e r 等分析了l d g m 码相对于l d p c 码和t u r b o 码 在编译码复杂度上的优势【2 】【6 】【7 1 。 2 0 0 3 年，f r i a s 和z h o n g 通过串行级联两个l d g m 码降低了规则l d g m 码 的错误平层【3 】。与t u r b o 码和l d p c 码相比，串行级联l d g m ( s e r i a l c o n c a t e n a t e d l d g m ，s c l d g m ) 码具有更低的编译码复杂度。2 0 0 5 年，f r i a s 和z h o n g 又基 于规则l d g m 码提出了并行级联方案【5 】。在不提高译码收敛阈值的前提下，并行 级联l d g m 编码方案可以有效地降低错误平层，且其纠错性能接近于串行级联 l d g m 码i s 。2 0 0 7 年，l o p e z 等应用外信息转移( e x t r i n s i ci n f o r m a t i o nt r a n s f e r ，e x i t ) 函数来优化设计s c l d g m 码以逼近容量限【8 1 。仿真结果表明：相对于非规则累积 码和基于传统方法设计的s c l d g m 码，基于e t 函数设计出的规则及非规则 s c - l d g m 码具有更低的译码收敛阈值和错误平层，提供更好的纠错性能。 1 2l d g m 码用于有失真信源量化的研究进展 现有的信源量化技术中，量化码大多采用u n g e r b o e c k 的网格码【9 , 1 1 】或网格编码 量化( t r e l l i sc o d e dq u a n t i z a t i o n , t c q ) 码【1 0 , 1 5 , 1 8 】。此类基于网格图的量化技术基 于v i t e r b i 算法【1 9 】操作，但为了达到率失真界，需要设计相当复杂的网格图，进而 导致很高的编译码复杂度。此外，部分学者还研究了l d p c 码用于信源编码时的 性能。众所周知，l d p c 码是一类能够逼近香农限的好的信道码，已有研究【2 0 2 1 表明l d p c 码可以成功地用于无失真的分布式信源编码，此种情形下的信源编码 可以等效为无噪声信道译码问题。当用于有失真信源编码时，也有研究结果【2 2 j 指 出使用l d p c 码可以逼近二进制率失真界，但信源限定为二进制独立同分布的 2 低密度生成矩阵码的研究 b e r n o u l l i 信源( i r x = l = p r x = 0 ) = o 5 ) 且l d p c 码的列重必须为d ( 刀) ( 以为码 长) 。当我们将这类码用于实际量化时，仍然存在一些问题，诸如使用现有的b p 算法译码无法收敛或者不能译出可靠的信息【2 2 2 3 1 。因此，针对上述存在的问题， 一种解决方案是从码构造的角度提出一种新的图码结构，另一种方案是从译码角 度对现有b p 算法进行有效的改进。此外，研究新的有失真编码算法也是一种有效 的途径。 由于信道编码可以视为率失真理论中失真信源编码的对偶，因此一个性能好的 信道纠错码的对偶码可以用作高效的失真信源编码。从这个角度出发，目前已有 学者开始研究l d g m 码用作量化码用于失真信源编码的问题【2 3 2 刀。l d g m 码作为 l d p c 码的对偶码，定义为一个稀疏生成矩阵g f o ，l r 生成的向量空间。就像 l d p c 码作为信道码能够达到信道容量一样，l d g m 码作为量化码也能够达到最 佳的率失真性能。 m a r t i n i a n 和y e d i d i a t 2 3 】最早针对l d g m 码用于失真信编码进行了深入的研究， 他们重点探讨了二进制删余量化问题( - - 进制删余信道编码的对偶问题) ，证明了 l d g m 码利用改进的消息传递算法( 利用对偶性，将二进制删余信道的译码算法 改进，作为二进制删余量化的编码算法) 能够达到相关的率失真界。后来很多研 究 2 4 - 2 9 】将重点放在二进制对称信源的量化问题( 二进制对称信道的对偶问题) ，也 证明了l d g m 码利用改进的消息传递算法( 同样利用对偶性) 能够达到相关的率 失真界。其中m a r t i n i a n 和w a m w r i g h d 2 8 2 9 】给出了一类结构化的l d g m 码，并且 给出这类码的严格的二进制率失真函数的上界，而且证明了这类l d g m 码随着列 度的增加能达到很好的量化性能。d i m a l d s 3 0 1 和k u d e k a r 等【3 1 】给出了使用l d g m 码 时的严格二进制率失真函数的下界。还有一些学者利用统计物理学方面的技术 3 4 - 3 6 1 ，研究了l d g m 码用作量化时的性能以及l d g m 码的率失真界和量化算法等。 在有失真信源编码量化算法方面，一些学者研究了使用s p ( s u r v c y p r o p a g a t i o n ，s p ) 算法【2 5 】，【蚓时基于l d g m 码的二进制信源量化问题。s p 算法源 于统计物理学，用于解决计算机科学中经典的k - s a t 问趔3 5 , 3 6 。l d g m 码的量化 问题与m a x - x o r s a t 问题有一定的相似性，都是在一类满足的值中寻找一个最 优值的问题( s a t i s f i a b i l i t yp r o b l e m ) 。还有一些学者对已有的置信度传递( b e l i e f p r o p a g a t i o n ，b p ) 译码算法进行了有效的改进【2 4 】，【3 2 】，【3 3 1 ，其中w a i n w r i g h t t 2 5 1 认为 偏置传播( b i a sp r o p a g a t i o n ，b i p ) t 3 2 】算法是s p 算法的一个特例。b i p 算法基于一个 足够简单的框架，在支持高速率的同时能达到很好的率失真性能。上述的算法都 能逼近最佳的二进制信源量化性能，但都具有一定的局限性，如信源必须是二进 制信源以及对码的结构的限制等。此外，有关研究指出【3 7 1 ，s p 算法可视作某种特 定因子图上的b p 算法。 。 m a r t i i l i 觚和w a i n w r i g h t 2 9 j 还对l d g m 码和l d p c 码进行联合设计，构造出了 第一章绪论 3 能达到率失真界的l d g m l d p c 复合码( 有限度分布) ，并且研究了将这种复合码 应用到具有边信息的信源和信道编码问题【2 6 矧。该复合码基于装箱技术【3 引，可以 等效为嵌套格码【3 9 柏】。 以上算法都是针对二进制对称信源( b s s ) 的有失真压缩而提出的。w a n g 和 h e 3 3 】研究了在实数域上的最小均方误差量化，其中量化也是基于b p 算法。文 3 3 】 在b p 算法的迭代过程中引入了抽取( d e c i m a t i o n ) 步骤，通过对某些最可靠比特 进行硬判决以使b p 算法朝着正确的方向迭代下去。仿真结果表明，使用该算法可 以得到较好的成形增益。 本文重点研究实数域上的基于最小均方误差( m e a ns q u a r ee r r o r , m s e ) 测度 的量化算法，将基于l d g m 码的量化算法由b s s 推广到实数域的信源上。我们将 介绍基于m s e 的b i p 算法的具体实现，仿真结果表明：和t c q 相比，使用l d g m 码的量化速度和性能都提高了很多。 1 3 本文研究内容及安排 本文结合国家自然科学基金项目，研究了l d g m 码在信道编码和信源量化方 面的应用。详细研究了l d g m 码作信道编码时的串行级联方案，以及l d g m 用作 信源量化时的各种量化算法。结合计算机仿真和理论分析，最后给出了相关算法 的性能对比。全文共分五章，其他章节安排如下。 第二章介绍了l d g m 码作为信道码时的应用，其中译码使用b p 算法。由于 l d g m 码是线性码，故其编码较简单。又因为系统的l d g m 码的校验矩阵也是低 密度的，故采用b p 算法进行译码的计算复杂度也比较低。由于l d g m 较差的距 离特性，单一l d g m 作为信道码使用时会产生较高的错误平层。因此我们又研究 了串行级联l d g m 编码方案，以克服单个l d g m 码存在的较高错误平层。结合计 算机性能仿真，我们发现串行级联l d g m 码的纠错性能接近t u r b o 码和l d p c 码， 距离容量限仅0 8 d b ，但其编码复杂度却远低于l d p c 码，且译码复杂度远低于 t u r b o 码。 第三章重点针对二进制对称信源介绍了信源压缩。首先，我们介绍了量化的 基本知识，然后介绍了b i a sp r o p a g a t i o n 、t r u t h i n e s sp r o p a g a t i o n 、m o d i f i e dt r u t h i n e s s p r o p a g a t i o n 、s u r v e yp r o p a g a t i o n 等算法。针对不同的量化算法，我们分别进行了 性能仿真。结果表明，这些算法都能提供逼近最佳的二进制信源量化性能。然而， 这几种算法都具有一定的局限性，如信源必须是二进制信源以及对码的结构的限 制等。这方面的内容有待进一步的研究。 第四章对实数域上的量化算法进行了研究。本章我们将量化算法推广到实数 4 低密度生成矩阵码的研究 域信源。在b i p 算法的基础上，提出了基于均方误差的b i a sp r o p a g a t i o n ( b i pm s e ) 算法。与t c q 相比，其算法复杂度低且具有低的失真度。 第五章对全文工作进行总结并提出了存在的问题，确定了今后的研究方向。 第二章l d g m 作为信道码的编译码算法 5 第二章l d g m 码作为信道码的编译码算法 本章阐述l d g m 码的基本知识和基础的译码算法( b e l i e f p r o p a g a t i o n ) ，为后 续内容做铺垫首先介绍l d g m 码的基本知识，l d g m 码作为特殊类的l d p c 码 具有稀疏性。接着介绍l d g m 码的编译码算法，因为l d g m 码是线性的，故l d g m 码的编码方法非常简单因为系统l d g m 码的校验矩阵亦为稀疏的线性码，这样 其译码可以用和积算法，实现起来非常简单最后给出l d g m 码作为信道码的性 能仿真，并针对l d g m 码糟糕的错误平层，研究了串行级联l d g m 码的性能其 性能接近t u r b o 码和l d p c 码，距离容量限仅o 8 d b ，但其编码复杂度低于l d p c 码且译码复杂度远低于t u r b o 码。 2 1低密度生成矩阵( l d g m ) 码的定义 低密度生成矩阵码用生成矩阵g f o ，l m 五来表示。系统的l d g m 码是具有稀 疏生成矩阵的系统线性码，生成矩阵g = l ip l ，其中p 是一个k f 一k ) 的稀疏 矩阵，故码率r = 叫n 。信息序列定义为n = k ，1 ，编码后得到 c = 【c ，巳】= u g ， 包含系统比特( q = ，n = l k ) 和编码比特 ( 乞= “。，力= k + l n ) 。我们很容易得到校验矩阵h = lp tii 。注意到矩阵h 也 l 一 是稀疏的。 图2 1 ( a ) 表示了l d g m 码的生成矩阵和相应的校验矩阵。( b ) 表示相对应 于h 矩阵的因子图。由于生成矩阵是稀疏的线性矩阵，所以编码过程是线性的， 其复杂度要比t u r b o 码和l d p c 码低；又由于校验矩阵也是稀疏的，所以实际上 是l d p c 码的一类，其译码过程和l d p c 码一样，也同样采用基于因子图的b p 译 码算法。但与l d p c 码不同的是，在译码过程中，变量节点中有一k 个变量节 点的度为l 。因此，从这些变量节点传递给对应校验节点的信息永远都是它们自己 的先验信息，无法得到更新，可能会对译码过程造成影响，从而产生较高的错误 平层。 g = l i p - - 10 0 o001l0 ol0 000 oll 0o10 0010l 000l 001 l0 o0 0 0l00ll 00 0o0ilol 低密度生成矩阵码的研究 il 01l0ll00l h = e p ti i = l1 lollo o1o l l0l 10ll0 01l c l2 乞= “2c 3 = 吩气= c s = 蚝c 6 = u 6 ( b ) 对应i ：i 矩阵的因子图 图2 1 系统l d g m 码因子图 t 代表系统比特 c l - - - - u - - - - i 盖) 和变量节点 + c ) ， “ 代表校验节点。 2 2 和积译码算法 2 2 1l d g m 译码的初始化 一个典型的数字通信系统如图2 2 所示。信源序列u 经过信道编码产生码字c ， 信号映射器将c 映射为b p s k 信号序列x ，信道受加性高斯白噪声影响。接收端接 收到的信号为 图2 2 数据传输系统框图 假定信源为二进制信源，ro 、1 等概率分布，即p r ( 而= + 1 ) = p r ( 一= 一1 ) = 丢。那 么，根据接收序列y 可以计算出发送比特的后验概率信息，此后验概率信息被用 作l d g m 译码时的初始信息。 第二章u ) g m 作为信道码的编译码算法 7 p r ( x ，f f i x i 小萼铲= 型铲 p r ( y l x 。= z ) p r ( 五- - - - x ) = _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ 二_ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ - _ _ 。- _ _ - _ _ - 一 p r ( y l x , = + 1 ) p r ( 而- - + 1 ) + p r ( y i x , = 一1 ) p r ( x i = - 1 ) 2 焉圈 l + e x p i _ = 笋f 故概率和积算法的初始信息为 q ( o ) t 1 ) = p r ( q = l l 咒) = p r ( 玉= 一l l y , ) = 瓦矿1 ( 。) = 毗= 。i 咒) = p r ( x ，= + 1 1 乃) = 瓦万1 2 2 2 和积算法 和积算法是一种基于因子图的迭代译码算法。其译码的每次步骤包括两步：校 验节点的处理和变量节点的处理。在每次迭代中，所有校验节点从其相邻的变量 节点处接收消息，处理后，再传回到相邻的变量节点；然后所有的变量节点进行 同样的过程；最后变量节点收集所有可以利用的消息进行判决。 二进制信道模型中，每个码字c = ( c 1 ) c 2 ，巳) 经b p s k 调制后映射为传输序列 x = ( 而，也，毛) ，然后x 通过信道，接收到的序列为y = ( y i ，y 2 ，y 。) 。根据y ， 译码得到译码序列为5 。 首先介绍所用到的有关符号的含义。 ( b ) ( 6 = o ，1 ) 表示校验节点，传给变量节点f 的外部概率信息，即在给定信 息位及其他信息为具有独立概率分布条件下，校验方程，满足的概率； ( b ) 表示变量节点f 传给校验节点的外部概率信息，即在得到除_ ，以外其他 所有校验节点和信道的外部信息后，判断变量节点g = 6 的概率； c ( f ) 表示与变量节点f 相连的校验节点的集合，q ； _ ，：| j l ，f = 1 ； r ( j ) 表示与校验节点相连的变量节点的集合，尺，= f ：j j l 帮= l ； c ( i ) ，表示除，外与变量节点f 相连的校验节点的集合； r ( ，) f 表示出i 外语校验节点，相连的变量节点的集合； 低密度生成矩阵码的研究 c 簟：包含c f 的第个校验方程中的第k 个比特； 蜘：对应于的接收值； ( 1 ) = p r ( c = l 只) ：接收到咒后判断发送比特位q = 1 的后验概率。 p i c ( 1 ) = p r ( = 1 ) ：接收到均后判断q 的第_ ，个校验方程中的第七个比特位 = l 的后验概率； 墨：占中的比特满足包含q 的吐个校验方程。 因此，b p 译码步骤总结如下。 1 初始化 计算信道传递给变量节点的初始概率只( 1 ) ，只( o ) = l 一只( 1 ) ，1 = l ，2 ，刀。 然后对每一个变量节点f 和与其相邻的校验节点j c ( i 1 ，设定变量节点传向校验 节点的初始消息 秽( o ) = 只( o ) 秽( 1 ) = 只( 1 ) 2 迭代处理 步骤l ：校验节点消息处理。 对所有的校验节点和与其相邻的变量节点f 尺( ) ，第1 次迭代时，计算变 量节点传向校验节点的消息 j 柏) = j 1 畦腮( 一2 纠- ) ) l ( 1 ) = l 一拶( o ) = i 1 一i 1n ( 1 2 硝叫( 1 ) ) l 1 - i - ，r e r 。、， 步骤2 ：变量节点消息处理 对所有的及节点变量i 和与其相邻的检验节点，c ( i ) ，计算校验节点传向变量节 点传向变量节点的消息 醪( o ) = 心只( o ) n 拶( o ) 沁 衫( 1 ) = 扬只( 1 ) n ，= j ：( 1 ) ，吒、j 其中是校正因子，使醪( o ) + 西( i ) - 1 。 步骤3 ：译码判决。 对所有变量节点计算硬判决消息 玉，) ( o ) = k 霉( o ) 兀拶( o ) j e c i 象，) ( 1 ) = k 只( 1 ) 兀拶( 1 ) j e c i 其中k 是校正因子，使玉，) ( o ) + 玉，) ( 1 ) = l 。若彰气1 ) 丞j ( o ) ，则毒= l ，否则乏j = o 。 第二章l d g m 作为信道码的编译码算法 9 3 停止 若h f = 0 或者达到最大迭代次数，则结束运算，否则从步骤2 继续迭代。 如果矩阵h 中不包含循环，则迭代次数趋于无穷时，q f ( o ) 和q ( 1 ) 收敛于色的 后验概率；对于好的l d p c 码，算法可以检测不正确的码字。 2 3l d g m 码用作信道码 2 3 1 单个l d g m 码作信道码 由2 1 2 知，系统的l d g m 码的生成矩阵g = 【ip 】，其中p = p 耐】是一个 k x ( n - k ) 的稀疏矩阵，码率r = k n 编码： c = u g 信息序列u = “，心】，编码得到码字c = h 巳】= u g 。 因为其校验矩阵h = - p ti 也是稀疏的，所以实际上是l d p c 码的子类，其译码 过程和复杂度与l d p c 码一样，同样也采用基于因子图的b p 译码算法( 2 2 节中 介绍) 。 图2 3 给出了码率o 5 信息为长度分别为1 0 0 0 0 和1 0 0 0 0 0 的l d g m 码，经过 a w g n 信道，在b p s k 调制方式下，采用b p 算法的性能曲线。图中标识d 中x 表示相应码字的列重，】，表示相应码字的行重。从图中可以看出，l d g m 码会引 入高的错误平层，增大码长和度分布，其性能不会改进，这是由于l d g m 码本身 差的距离特性引起的。 1 0低密度生成矩阵码的研究 图2 3 不i 司码长和度分布的l d g m 码性能比较 2 3 2 串行级联l d g m 码 尽管l d g m 码会引入高的错误平层，但采用串行或并行级联系统可以解决这 个问题，并能够在低的编译码复杂度条件下达到非规则l d p c 码和t r u b o 码的性 能。在串行级联系统中，外码采用高码率的l d g m 码，主要用来减低错误平层； 内码采用低码率的l d g m 码，主要用来决定收敛阈值。通过选择合适码率的l d g m 码，并且采用迭代译码算法，使得整个串行级联系统既有较低的收敛阈值又有较 低的错误平层，从而达到优越的性能。但级联系统同时也增加了硬件实现的复杂 度【5 3 1 1 5 4 1 。图2 4 为串行级联l d g m 码的基本框图。 o u t e rl d g mc o d e i n n e rl d g mc o d e 图2 4l d g m 码的旱行级联 编码： 信息序列u = “。，“：，】首先由外码系统l d g m 码编码得到编码序列 c 1 = u g l = “，“：，p ：，e ， 1 ，外码生成矩阵g 1 i 置，砭屿 ，砭。厶是外 码校验部分。这些比特然后再由内l d g m 码编码产生最终的码字。 c = 【c l ，c 2 ，c 】- c 2 = c 1 g 2 = “。吃，d ，矗，矗，彳，西，既2 。 其中 n = k + 厶+ 厶，g 2 = i k + h p + l 1 ) x l ： 。咏+ l 1 ) x l 2 是内码的校验部分。整体码率 l 净k ，n 。 图2 5 表示了s c l d g m 码的因子图。外码校验节点定义为厂1 ，内码校验节点 定义为厂2 。 第二章l d g m 作为信道码的编译码算法 图2 5 串行级联码( s c l d g m ) 的因子图 译码： 在s c l d g m 因子图上应用和积算法( 2 2 节中介绍) ，能够进行有效的译码。 图2 6 给出了不同串行级联l d g m 码，在b p s k 调制下通过a w g n 信道的性 能比较。图中，串行级联系统中内码和外码都是l d g m 码，信息位是9 5 0 0 ，总码 率是0 4 7 5 ，可以看出串行级联l d g m 码的错误平层明显降低，并且性能得到很 大的改善。在b e r = i o 巧时，距离容量限( 码率为0 4 7 5 时，容量限是0 1 d b ) 不到 0 8 d b 。充分说明了串行级联l d g m 码可以达到非规则l d p c 码和t u r b o 码的性能。 耋 l 竺 图2 6 不同的串行级联l d a 订码性能比较 1 2低密度生成矩阵码的研究 2 4 本章小结 由于系统l d g m 码的生成矩阵是稀疏的线性矩阵，故其编码复杂度和码长呈 线性关系。我们可以容易的得到校验矩阵也是稀疏的，所以l d g m 码是特殊的 l d p c 码，可以用因子图进行表示。使用和积算法对其译码，译码过程和复杂度与 l d p c 译码相同。 但由于l d g m 码糟糕的距离特性，产生了较高的错误平层。改变码长和行重 列重并不能降低错误平层。但是通过串行或并行方案可以在较低的编译码复杂度 下，降低错误平层并接近t u r b o 码和l d p c 码的性能。 第三章基于l d g m 码的二进制对称信源的压缩 1 3 第三章基于l d g m 码的二进制对称信源的压缩 本章将主要介绍l d g m 码用于二进制对称信源的压缩算法，如s u r v e y p r o p a g a t i o n , b i a sp r o p a g a t i o n , t r u t h i n c s sp r o p a g a t i o n , m o d i f i e dt r u t h i n e s s p r o p a g a t i o n 等等。首先，介绍了率失真，有失真信源压缩基本知识：接下来介绍 了l d g m 码进行信源压缩的基本原理；最后我们介绍了几种二进制对称信源的压 缩算法并给出其相应的性能仿真 3 1 率失真 3 1 1 失真定义 假定某信源产生随机序列墨，p 29 9 z ，f 彳p ( y ) ，y 少。信源序列】，”的编码 用索引厂( 】，“) l ，2 ，2 从) 表示，r 的译码估计用矿“歹”表示，如图3 1 示。 图3 1 率失真编码器与译码器 定义失真函数或者失真度量是从信源字母表与再生字母表的乘积空间到非 负实数集上的映射 d ：少少寸矿 失真d ( y ，夕) 的意义是使用夕表示y 时的损失度量。在本文中，我们用基于 l d g m 码的压缩算法充当映射关系。 常用的失真函数的例子有： h a m m i n g 失真。h a m m i n g 失真定义为 d ( y ，夕) = ：；二； 平方误差失真。平方误差失真 d ( y ，夕) = ( y 一夕) 2 是针对连续字母表的最常用的失真度量。 失真度量是定义在字符上的。下面我们把这个定义推广到序列上去。 定义y ”与夕”的序列间失真定义为 d y n , 夕”) 2 i - id ( 乃，训 1 4低密度生成矩阵码的研究 3 1 2 率失真函数 定义设信源x 的失真度量为a ( y ，夕) ，定义其信息率失真函数r p ( d ) 为 尺p ( d ) 2 “如) ：z 嚣陟p ( 灿净。z ( y ：譬) 其中的最小值取自使联合分布p ( y ，夕) = p ( y ) p ( 夕iy ) 满足期望失真限制的所有条 件分布p ( 夕i y ) 。 b 绷d “坳) 信源在汉明失真度量下的率失真函数为【蚓 即) = p 叫0p 卜篡涮，1 - p , l p - ) p 如果信源是二进制对称信源，则 即) = 一p ) 0 淼兰5 如图3 2 给出了二进制对称信源，码率和失真之间的对应关系。 卫 e 毫 。 图3 1 二进制对称信源率失真函数 3 2l d g m 码用于信源压缩的基本知识 3 2 1l d g m 与l d p c 对偶关系 【咒，七】线性码c 是刀维线性空间、j ：l 中的一个七维子空间v 由生成矩阵g 生 成，对于码字c ，有h c r = 0 ，其中h 是校验矩阵。它的对偶码c 上必是一个刀一k 维 第三章基于l d g m 码的二进制对称信源的压缩 1 5 子空间v 。4 ，由生成矩阵g 上生成，因为、7 ：l j 与v ：l j 互为对偶空间，则可以把c 的 h 当成是对偶码矿的g 上，把c 的g 当成是对偶码c 上的校验矩阵h 上。由此可见， 对偶码c 上的生成矩阵为g 上= h 。如图3 3 ，给出线性码c 的h 矩阵和对应的因子 图。图中3 3 ( b ) 中方框表示校验节点，弓o = l ，2 3 ，4 ) 表示每个校验节点的校验关系。 圆圈表示变量节点，c = 心，c 2 ，c 3 ，c 4 ，c 5 ，c 6 ，c 7 ，龟) 表示一个码字。下面的横线 y = “，儿，乃，y 4 ，弘，y 6 ，乃，y 8 ) 表示信道信息。图3 4 给出对偶码c 上的g 上矩阵和对 应的因子图。根据对偶关系，对偶码矿的g 上就是码c 的h ，它的因子图跟码c 的 因子图也是一种对偶关系，即通过交换图3 3 ( b ) 的校验节点和变量节点就可以得到 ( 如图3 4 ( b ) ) 。图3 3 的信道码c 的因子图中每个校验节点表示一种校验关系， 而对偶码的因子图中校验节点表示一种编码关系。图中3 4 ( b ) 中方框也表示校验节 点，c f 表示信源码字比特，c = ( q ，c 2 ，岛，c 4 ，c s ，c 6 ，c 7 ，岛) 是一个信源码字。圆圈表示 变量节点，w o = 1 2 ，3 ，4 ) 表示信息比特，下面的横线y = ，兄，乃，y 4 ，乃，咒，乃，盹) 表 示信源信息。 h = l0 l0 0l ol lo 0l l0 0 1 l0 01 0l l0 lo 01 lo 01 ( a ) 校验矩阵和校验关系 乞 乃 h y 2 y 3 y 4y sy 6y 1y s ( b ) 因子图表示 图3 3 线性码c 的h 矩阵和对应的因子图 0 0 0 o = = = = 勿珞勿玩 + + + + 彩靠彩 + + + + 白“臼以 + + + + 臼所以以 1 6 低密度生成矩阵码的研究 g = 11 0 0 10 0l 10 0l lo 0l 00 l1 10 ol 0l l0 10 0l c l = + ，1 2 c 22 ，坞+ c 32m + m 3 q = ，1 2 + 岛= ，l l + 鸭 c 6 = ，| 2 + ，坞 岛= ，l l + ，吩 龟= m 2 + ( a ) 生成矩阵和编码关系 y l y 2y 3 y y 5 y 7 y s ( b ) 因子图表示 图3 4 对偶码c 上的g 上矩阵和对应的因子图 根据信道编码问题和率失真理论中的有失真信源编码的对偶关系【2 3 1 ，我们知道 一个性能好的纠错码可以用作高效的有失真信源编码。我们给定一个l d p c 码， 能够达到信道容量，则它的对偶码l d g m 码进行信源压缩也能够达到最佳的率失 真性能。假设l d p c 码h ，码长为刀，码率r = 1 - 一m ，则它的对偶码l d g m 码 仃 g = h 一，码率r = 兰。 以 在引入有效的信源编码算法之前，我们先给出l d g m 码的因子图表示( 如图 3 4 ) 。给定生成矩阵g ，l d g m 码一般可以用因子图o r - - ( 职g 四表示，其中 v = - 1 ，2 ，聊) 表示信息比特集合，庐 1 ，2 ，甩 表示校验节点集合，骧示连接校验 比特和信息比特的边的集合。每个信源比特有一个独有的校验节点邻居，每个校 验比特和至多册个信源比特连接( 由生成矩阵g 确定) 。这里，采用字母a ，b ，c 表示集合础元素，f ，工k 表示集合啪元素。对于每个信息比特f y ，定义 c ( i ) c 为该比特的校验节点邻居 c o ) - 口c l ( a ，f ) 四 第三章基于l d g m 码的二进制对称信源的压缩 1 7 相似的，对于每个校验节点a c ，定义v (