（通信与信息系统专业论文）稀疏信源下ldpc码信道编译码技术研究.pdf

中山大学硕士学位论文中文摘要 稀疏信源下l d p c 码信道编译码技术研究 专 业：通信与信息系统 硕士生：王学超 指导教师：马啸教授 摘要 在信源编码系统中，图像、视频数据传输是多媒体业务的重要组成部分，数 据量庞大。无线信道的带宽资源十分有限，必须对数据进行压缩才能提高传输的 效率。 本文根据低密度奇偶校验码( 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 ) 的自 身特性及其优势，提出了两种设计方案，方案i 根据信源信道分离编码理论，对 稀疏信源首先进行无失真信源压缩编码，去除冗余，再进行较低码率的信道编码， 增加相对较多的冗余；方案仅对稀疏信源进行较高码率的信道编码，但两种 方案之间存在约束关系，即稀疏信源的分组长相等，经信道编码后的码字长也相 等。用仿真的方法在加性高斯白噪声( a w g n ，a d d i t i v ew h i t e g a u s s i a nn o i s ec h - a n n e l ) 信道下和b p s k 调制时分析它们的传输性能。仿真结果表明方案i 的f e r 性能比方案i i 有0 2 ld b 的提高。 方案i ：稀疏信源一理想信源压缩一信道编码( 可变码率l d p c 码) - a w g n 信道一信道译码( b p 译码算法) 一误帧率( f e n ) 。 方案i i ：稀疏信源一信道编码( 可变码率l d p c 码) 一a w g n 信道一信道 译码( b p 译码算法) 一误帧率( f e r ) 。 信道编码采用可变码率的k i t e 码，它是一类新的l d p c 码，属于系统编码。 k i t e 码的显著特性是编码速率“在线”可调。该类码的编码速率灵活可变，比较 适合本文所提方案要求很多组码率的情况。l d p c 码是以校验矩阵为特征的，构 造l d p c 码，实质就是构造它的稀疏校验矩阵，常用的编码方法是把校验矩阵系 统化得到生成矩阵。k i t e 码的校验矩阵由两部分组成，左边的子矩阵随机生成， 中山人学硕士学位论文稀疏信源下l d p c 码信道编译码技术研究 受一个整数序列( 即参数p ) 控制，这个参数是决定码字性能优劣的关键。右边 的子矩阵结构固定。 用译码性能仿真的方法来筛选参数p 是比较繁琐的，因为优化的过程就是根 据码参数预先设计一系列p ，这也就确定了码字，再从中选取使码字性能较好的 p 。而把密度进化应用到分析码字性能优劣的过程中，不经过译码性能仿真就可 以初步判定码字的好坏，方便快捷，为筛选k i t e 码的控制参数p 提供了便利。 但是e x i t ( 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 rc h a r t ) 图是一种比密度进化更有效的分 析迭代译码收敛性的工具，然而，本文没有涉及。 本文的译码选用置信传播( b p ，b e l i e fp r o p a g a t i o n ) 算法，是迭代译码。每次 迭代包括两步：校验节点消息的处理和变量节点消息的处理。在一次迭代中，所 有校验节点从与其相邻的变量节点接收信息，处理后，再传回相邻的变量节点。 然后，所有的变量节点进行同样的过程，且变量节点收集所有的置信消息进行判 决。t a n n e r 图可以直观地表示迭代译码的消息传递模式。用信息论的理论分析两 种方案的约束关系，可以选取任意码率的码来进行仿真比较。本文设计出1 1 组 数据，并从中选取4 组码进行译码性能仿真，结果表明方案i 的性能更优，与理 论分析吻合。 关键词l d p c 码，密度进化，稀疏信源，k i t e 码，置信传播算法 h 中山大学硕士学位论文a b s t r a c t r e s e a r c ho nl o w - d e n s i t yp a r i t y - c h e c kc o d e s o v e rc h a n n e l sw i t hs p a r s es o u r c e s m a j o r ：c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m n a m e ：x u e c h a ow a n g s u p e r v i s o r ：p r o f x i a om a a bs t r a c t i nt h es o u r c ec o d i n gs y s t e m ，d a t at r a n s m i s s i o nf o rv i d e oi m a g ei sa ni m p o r t a n t c o m p o n e n to fm u l t i m e d i as e r v i c e s ，w h i c hh a v eah u g ea m o u n to fd a t a b e c a u s et h e w i r e l e s sc h a n n e lb a n d w i d t hi sl i m i t e d ，i ti sn e c e s s a r yt oc o m p r e s st h ed a t at oi m p r o v e t r a n s m i s s i o ne f f i c i e n c y i nt h i sp a p e r , a c c o r d i n gt ot h ec h a r a c t e r i s t i c sa n da d v a n t a g e so fl o wd e n s i t y p a r i t yc h e c kc o d e s ，w ep r o p o s et w od e s i g n s a c c o r d i n gt os o u r c e c h a n n e lc o d i n g s e p a r a t i o nt h e o r y , s c h e m ei f i r s th a ss p a r s es o u r c ef o rl o s s l e s ss o u r c ec o d i n gt o r e m o v er e d u n d a n c y , a n dt h e nt ot h el o w e rr a t ec h a n n e lc o d et oa d dm o r er e d u n d a n c y s c h e m ei ih a ss p a r s es o u r c ef o rah i g h e rb i tr a t ec h a n n e lc o d i n g ，b u tt h e r ea r e c o n s t r a i n tr e l a t i o n sb e t w e e nt h et w os c h e m e s ，t h a ti st h eb l o c kl e n g t ho fs p a r s es o u r c e i se q u a l ，s oi st h el e n g t ho fw o r dc o d e s u s i n gs i m u l a t i o nt oa n a l y z et h e i rt r a n s m i s s i o n p e r f o r m a n c eo fb p s km o d u l a t i o no v e ra d d i t i v ew h i t eg a u s s i a nn o i s ec h a n n e l ，t h e r e s u l t ss h o wt h a tt h ef r a m ee r r o rr a t ep e r f o r m a n c eo fs c h e m eii s0 2 - 1d bb e t t e rt h a n t h a to f s c h e m ei i s c h e m ei ：s p a r s es o u r c e s i d e a ls o u r c ec o d i n g ( s u c ha sj e p g ) 一c h a n n e l c o d i n g ( v a r i a b l ec o d i n gr a t el d p cc o d e s ) _ a w g nc h a n n e l c h a n n e ld e c o d i n g ( b pd e c o d i n ga l g o r i t h m ) 一f r a m ee r r o rr a t e ( f e r ) s c h e m ei i ：s p a r s es o u r c e s c h a n n e lc o d i n g ( v a r i a b l ec o d i n gr a t el d p cc o d e s ) _ a w g nc h a n n e l 叶c h a n n e ld e c o d i n g ( b pd e c o d i n ga l g o r i t h m ) - f r a m ee r r o rr a t e ( f e r ) c h a n n e lc o d i n gw i l lu s ean e wc l a s so fl d p cc o d e s 、) r i lv a r i a b l eb i tr a t e ，a l s o k n o w na sk i t ec o d e s ，w h i c hi ss y s t e mc o d i n g c o d i n gr a t e “o n l i n ea d j u s t a b l e i sa i i i 中山大学硕士学位论文稀疏信源下l d p c 码信道编译码技术研究 s i g n i f i c a n tf e a t u r eo fk i t ec o d e s s os u c hc o d e sh a v eaf l e x i b l ev a r i a b l ec o d i n gr a t e ， m o r es u i t a b l ef o rt h ep r o p o s e ds c h e m e sr e q u i r i n gm a n yg r o u pr a t e s l d p cc o d ei s c h a r a c t e r i z e db yi t sp a r i t yc h e c km a t r i x t h e r e f o r e ，c o n s t r u c t i n gl d p cc o d e si n e s s e n c ei st oc o n s t r u c ti t ss p a r s ep a r i t yc h e c km a t r i x ，a n dt h ec o m m o n l yu s e dm e t h o d o fc h a n n e lc o d i n gi st oo b t a i ng e n e r a t o rm a t r i xg b ys y s t e m a t i z i n gp a r i t yc h e c k m a t r i xh t h ec h e c km a t r i xo fk i t ec o d ei sc o m p o s e do ft w os u b - m a t r i c e s ，t h el e t t s u b - m a t r i xi sr a n d o m l yg e n e r a t e db yas e q u e n c eo fi n t e g e r s ( i e p a r a m e t e r 力t o c o n t r o l ，a n dt h ep a r a m e t e ri st h ek e yt od e t e r m i n et h ep e r f o r m a n c ei n d e xf o r c o d e w o r d ；t h er i g h ts u b m a t r i xs t r u c t u r ei sf i x e d u s i n gs i m u l a t i o n t of i l t e rp a r a m e t e rpi s v e r yc o m p l i c a t e d ，b e c a u s et h e o p t i m i z a t i o np r o c e s si sf i r s tt od e s i g nas e r i e so fp a r a m e t e r spa c c o r d i n gt ot h ec o d e p a r a m e t e r s ，w h i c ha l s oi d e n t i f i e dt h ec o d e w o r d ，t h e nt op i c kpt h a tg i v e sb e r e r d e c o d i n gp e r f o r m a n c ef r o mt h e s ep a r a m e t e r s w eu s ed e n s i t ye v o l u t i o nt oa n a l y z e c o d e w o r dp e r f o r m a n c e ，s ot h a tt h ed e c o d i n gp e r f o r m a n c ec a nb ew a si n i t i a l l y d e t e r m i n e dw i t h o u ts i m u l a t i o n ，c o n v e n i e n t l ya n de f f i c i e n t l y , w h i c hp r o v i d e sa c o n v e n i e n tf o rt h es e l e c t i o no fk i t ec o d ep a r a m e t e r s t h ee x i t ( e x t r i n s i ci n f o r m a t i o n t r a n s f e rc h a r t ) c h a r ti sam o r ee f f e c t i v ea n a l y s i st o o lt h a nt h ed e n s i t ye v o l u t i o nf o r i t e r a t i v ed e c o d i n gc o n v e r g e n c e ，b u tn o tc o v e r e di nt h i sp a p e r i nt h i sp a p e r , w eu s eb e l i e fp r o p a g a t i o n ( b p ) d e c o d i n ga l g o r i t h mt h a ti sa l s o i t e r a t i v ed e c o d i n g e a c hi t e r a t i o nc o n t a i n st w os t e p s ：c h e c kn o d em e s s a g ep r o c e s s i n g a n dv a r i a b l en o d em e s s a g ep r o c e s s i n g a l lt h ec h e c kn o d e sf r o mi t sa d j a c e n tv a r i a b l e n o d e sr e c e i v em e s s a g e s ，f o l l o w e db yp r o c e s s i n g ，a n dt h e nt r a n s m i ti tb a c kt ot h e a d j a c e n tv a r i a b l en o d e s t h e n ，a l lt h ev a r i a b l en o d e sd ot h es a m ep r o c e s s f i n a l l y ， v a r i a b l en o d ec o l l e c t sa l lm e s s a g e sf o rd e c i s i o n t a n n e rg r a p hc a nb ei n t u i t i v e l yt h a t t h ep r o c e s so fc o n v e r g e n c eo fi t e r a t i v ed e c o d i n g u s i n gt h et h e o r yo fi n f o r m a t i o n t h e o r yt oa n a l y z ec o n s t r m n tr e l a t i o n so ft h et w os c h e m e s ，y o uc a ns e l e c ta r b i t r a r y c o d i n gr a t eo fk i t ec o d e st oc o m p a r es i m u l a t i o nr e s u l t s w ed e s i g n e d11s e t so fd a t a , f r o mw h i c hw ep i c k e d4g r o u p st oc a r r yo u ts i m u l a t i o n ，a n dt h e s er e s u l t si n d i c a t et h a t t h ef e rp e r f o r m a n c eo fs c h e m eii sb e n e r ，w h i c hi sc o n s i s t e n t 、析t i lt h et h e o r e t i c a n a l y s i s k e y w o r d sl d p cc o d e s ，d e n s i t ye v o l u t i o n , s p a r s es o u r c e ，k i t ec o d e s ，b e l i e f p r o p a g a t i o na l g o r i t h m i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：王学趣 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：式l 超 e t 期：曲l o 年6 月4 日 导师签缸劲荡导师签名：t 协7 闷 e t 期：2 0 o 年6 月4 - 日 中山大学硕士学位论文第一章绪论 1 1 研究的背景及意义 第一章绪论 1 9 4 8 年香农发表开创性文章“通信的数学理论【l 】，香农在该文中提出了著 名的信道编码定理，只要码率r 小于信道容量c ，就能实现信息的可靠传输。香 农定理说明了当码长充分长时，存在错误概率随码长按指数减小的好码。他 虽然没有给出构造最佳码的方法，但却为后来的研究指明了方向，在此基础上， 人们开发出了大量实用的信道编码。 低密度奇偶校验码( l d p c ，l o w - d e n s i t yp a r i t y c h e e kc o d e s ) 早在19 6 2 年由 r o b e r tg g a l l a g e r l 2 】首先提出，它就是一种实用的编码。l d p c 码是一种线性分组 码，采用迭代译码算法进行译码，可以并行实现。因此，便于用硬件构造快速的 译码器，同时减少了译码时延。1 9 8 1 年t a n n e r 提出了l d p c 码的双向图p j ( 也 称为t a n n e r 图) ，t a n n e r 图可以直观地表示迭代译码的消息传递模式，但是在实 际当中t a n n e r 图的构造很难避免小环的出现，这使得小环上的置信消息会被重 复传递，如此以来译码中的信息就不再严格满足独立性假设，势必影响迭代译码 的收敛，甚至会导致译码失败。此外，后来出现的重复累积码( r a ，r e p e a t a e c u m - u l a t e d ) 等“类t u r b o 码( t l c ，t u r b o 1 i k ec o d e s ) ”也都是基于图模型和迭代译码 的好码，这表明了迭代译码算法应用的广泛性。1 9 9 6 年d j c m a c k a y 在g a l l a g e r 思想的基础上，详细地论述了和乘积算法( s p a ，s u mp r o d u c ta l g o r i t h m ) 的实现 方法，s p a 算法也称为置信传播算法( b p , b e l i e fp r o p a g a t i o na l g o r i t h m ) 或消息 传递算法( m e s s a g ep a s s i n ga l g o r i t h m ) 【4 j 。 l d p c 码的编码比它的译码要复杂，构造性能优异的l d p c 码是从构造它的 校验矩阵日开始的。l d p c 码的校验矩阵是稀疏矩阵，依据月构造方式的不同， 通常将它分为两大类：随机校验矩阵和结构化校验矩阵。虽然随机生成的l d p c 码的纠错性能好，但是由于其校验矩阵的随机性，无法实现简单编码。结构化校 验矩阵具有确定的结构，实现起来比随机结构的码容易，纠错性能稍差一些，但 是精心设计的结构化校验矩阵的纠错性能已能达到随机校验矩阵生成的码。 中山大学硕士学位论文 稀疏信源下l d p c 码信道编译码技术研究 l d p c 码的参数，比如g i r t h 、节点的度分布等，是构造l d p c 码的关键。对 于不规则码的设计与分析，t h o m a sj r i c h a r d s o n 和r l u r b a n k e 等提出了密度 进化( d e n s i t ye v o l u t i o n ) 的方法【5 1 ，无需通过大量的仿真就能初步判断码字的性 能，有利于优化不规则码的度分布，从而方便地筛选出l d p c 好码。但是密度进 化方法的计算仍然复杂，1 9 9 9 年由s t e nb r i n k 提出的外部信息转移图( e x i t , 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 rc h a r t ) 是一种更简单的分析迭代译码收敛性的工 具，它从互信息的角度来跟踪译码的收敛过程，已经应用到了l d p c 码的误码率 估计、门限值估计以及码型设计等方面【6 1 。 鉴于l d p c 码的诸多优点，可以预见它将是一个有广阔的应用前景的信道编 码类型。 1 2 信道编码的基本理论 对许多信道而言，高斯信道都是一个很好的信道模型，本文的研究主要是在 加性高斯白噪声信道( a w g n ，a d d i t i v ew h i t eg a u s s i a nn o i s ec h a n n e l ) 下进行 的，故首先对a w g n 信道模型作一下论述。 1 2 1 离散时间高斯信道 图1 1 中的高斯信道是一个时间离散信道，在时刻f 时，输出信号只是输入 信号x j 和信道噪声珥之和，其中n j 是统计独立同分布( i i d ，i n d e p e n d e n ti d e n t i c a l d i s t r i b u t i o n ) 变量且服从方差为盯2 的高斯分布，噪声和信号薯相互独立，用公 式表示为 = 薯+ 吩，吩一n ( o ，仃2 )( 1 - 1 ) 噪声 2 输入薯输出只 图1 1 离散时间高斯信道模型 般地，信道输入受能量或者功率的限制，决定了信道容量是有限的。本文 中山大学硕士学位论文第一章绪论 假设输入受平均功率的限制，即在信道上传输的任意码字( 五，屯9 q9 ) 都满足 寺善# ( 1 - 2 ) 实际信道中的噪声来源可能很多，但是在很多情形下高斯假设都是有效的，这是 因为，根据中，i b 极限定理可知，大量的小随机效应的累积效应渐近于正态分布【刀。 假设信道一次发送1 个字节，在给定功率p 的限制下，最佳的传输方案是发 送+ 歹或一芦中的一个。接收者根据y 来判定x 的值，假设信源发送二者的概 率相等，则最优的译码规则是当y o 时判决为+ 万，当y 扛) _ 1 - ( 厣) 其中o ( x ) 是累积正态分布的分布函数 ( x ) = l i 。_ l 卉( 1 - 4 ) 可以看出，此方案把高斯信道转化成了交叉概率为的离散二进制对称信道【8 】 ( d b s c ，d i s c r e t eb i n a r ys y m m e t r i cc h a n n e l ) 。 信道容量是用输入和输出的互信息定义的，互信息用符号，表示。假定功率 限制为尸的高斯信道，信源z 所包含的信息量为 n ( x ) - - - p ( x ) l o g p ( x ) ( 比特信源符号) ( 1 5 ) 接收者接收到的有关x 的信息量称为x 和y 的互信息 ，( x ；y ) = 日( x ) 一日( x iy ) ( 比特信源符号) ( 1 6 ) 其中h ( x ly ) 是经信道传输后x 损失的信息量。对于具体的信道，互信息i ( x ；y ) 是 信源概率分布的凸函数，存在使互信息达到最大值的信源概率分布，这个最大值 称为信道容量，用c 表示 c = m 鲜l ( x , y ) ( 比特信源符号)( 1 7 ) ，( j ) ：臌s p 3 中山大学硕士学位论文稀疏信源下l d p c 码信道编泽码技术研究 计算方法如下，由于刀和x 相互独立，则 ，( x ；y ) = 日( y ) 一日( j ，ix ) ：= h 川( y ) - 一h 刚( x + x n ) ( 1 8 ) = 日( j ，) 一日( 聍i x ) r 叫 = 日( j ，) 一日( ，2 ) 此时日( 刀) = 1 。g2 万p 盯2 。又因为噪声均值为勘= 。，所以 矽2 = e ( x + ”) 2 = e x 2 + 2 e x e n + e n 2 = p + o - 2 ( 1 9 ) 此时，y 的熵的上界忉为主l 0 9 2 石p ( p + 盯2 ) 。综上所述，可以得到互信息的上界 ，( x ；y ) = h ( y ) - h ( n ) 丢l 。9 2 万p ( p + 盯2 ) 一圭l 。9 2 万p 盯2 ( 1 - 1 0 ) = 扣( + 7 p ) 当x 一( o ，p ) 时取得最大值。因此，高斯信道的容量为 c = 小m ) ：序a x s p ，( x ；y ) = 云1l o g ( 1 + 7 p ) ( 比特信源符号) ( 1 1 1 ) 1 2 2 有限带宽信道 1 2 1 节所描述的a w g n 信道对带宽没做限制，而在许多情况下信道的功率 和带宽都是受限的。假定信道带宽为w ，使用采样时间间隔为1 2 ws 的序列表 示输入和输出。如果噪声的双边功率谱密度为盯2 = 2 ，那么噪声功率为n o w 。 在时间区间【o ，t 】内，每个噪声采样值的方差为n o w t 2 w t = 2 ，每个信号采 样值的功率为p t 2 w t = p 2 w ，因此每个采样的信息容量为 c 扣( ，+ 学卜1g ( t + 万p 卜特倮样， m 协 每秒内有2 w 个采样值，故信道容量为 c - 肌。g ( 1 + 专) 吡特秒) ( 1 1 3 ) 式( 1 1 3 ) 是信息论中最著名的公式之_ _ 1 7 1 。 4 中山大学硕士学位论文第一章绪论 1 2 3 最大似然译码 译码器根据译码规则由接收序列y 对信息序列u 作出最相似的估计序列五。 由于信息序列u 与码字序列c 是一一对应的，这等价于根据y 对c 做一个最佳估 计序列占。若给定y ，则译码的错误概率为p ( 6 ciy ) ，故译码平均错误概率为 = p ( 6 c l y ) p ( y ) ( 1 1 4 ) y 因为p ( y ) 是接收y 的概率，与译码方法无关，所以最佳译码规则满足 m i n p 。= m i n p ( 6 c l y ) ( 1 1 5 ) 而由式( 1 1 5 ) 可知 m ，i n 尸( 占c ij ，) j 呼尸( 。= c i ) ，) ( 1 - 1 6 ) 因此，如果译码器能在码字集c 中选出一个码字q ( f = l ，2 ，2 ) 使p ( 乞= c i y ) 最 大，那么这种译码规则一定是最佳的，称为最大后验概率译码刚( m a x i m u m ap o s t e r i o r i ) 。 由贝叶斯公式 盹= 嗍 ( 1 1 7 ) 可知，若发送每个码字的概率p ( q ) 均相同，则 警尸心l y ) j m 忸a x p ( y l q ) ( 1 - 1 8 ) 对于离散无记忆信道( d m c ，d i s c r e t em e m o r y l e s sc h a n n e l ) 尸( y i q ) = 兀尸( 乃ic ：f ，) ( 1 - 1 9 ) 其中，码字为q = ( q l ，q 2 ，) ，接收序列为y = ( 乃，奶，兄) 。 若能选出满足式( 1 1 8 ) 的码字，则称这种译码规则为最大似然译码【9 】( m l d ， m a x i m u ml i k e l i h o o dd e c o d i n g ) ，p ( yiq ) 为似然函数。由于对数的单调性，可将 式( 1 - 1 8 h 1 1 9 ) 写为 蹬1 。g e ( y l q ) = m 铲a x z 。l 。g 尸( 乃i 勺) ( 1 - 2 0 ) 其中l o g p ( yic j ) 为对数似然函数。由于尸( q ) ( q c ) 均近似相等，所以对d m c 5 中山大学硕士学位论文稀疏信源下l d p c 码信道编译码技术研究 信道而言，m l d 被认为是一种最佳译码准则。 1 3 本文的研究内容与结构安排 本文的主要研究对象是l d p c 码，包括它的参数、结构、编码、译码以及分 析工具等，l d p c 码是一类先进的信道编码，它自身的结构决定了它有优异的性 能，这早已引起了热烈的关注。然而，本文的研究还很浅薄。 本文的研究思路如下。 1 ) 研究一种信道编码首先是从认识它的结构开始的，由于l d p c 码的奇偶 校验矩阵是稀疏矩阵，则它的行重与列重和码字长度相比是很小的。此外，t a n n e r 图直观地表示了码字的校验关系，t a n n e r 图中的g i r t h 和节点的度分布决定了码 字的性能，这为构造l d p c 码指明了努力的方向。 2 ) l d p c 码的编码相对比较复杂，对于规则码的构造已经有了一些好的方 法，对于非规则码可以运用密度进化和e x i t 图来跟踪分析码字的译码收敛性能， 进而根据不同的应用需求，设计出好的节点度数分布对。非规则码的度分布与规 则码相比更加灵活，能更好地平衡变量节点和校验节点在度分布上的矛盾。此外， 把信息按重要程度分配到度数不同的变量节点上，能实现信息的不等错误保护 e p ，u n e q u a le r r o rp r o t e c t ) 。 3 ) l d p c 码的译码是迭代译码，已经取得了很好的性能，但是仍然复杂。 译码复杂度与节点消息的处理方式密切相关，对节点消息处理算法做简化处理， 再添加最佳的校正因子，可以在性能与复杂度之间取得良好的折衷。 4 ) 在l d p c 码的研究基础上，针对稀疏信源，本文提出了两种设计方案， 方案i 首先对稀疏信源进行理想信源压缩编码，去除冗余，再进行较低码率的信 道编码，增加相对较多的冗余。方案i i 仅对稀疏信源进行较高码率的信道编码， 但两种方案之间存在约束关系，即稀疏信源的分组长相等，经信道编码后的码字 长也相等。 本文的章节安排如下。 全文分为六章。第一章为绪论，介绍了l d p c 码的发展历史及其研究现状， 阐述了研究的目的及意义，最后论述了信道编码的基本理论。 第二章对l d p c 码做了必要的概述，首先介绍了l d p c 码的校验矩阵与编 6 中山大学硕士学位论文 第一章绪论 译码的关系。其次，介绍了l d p c 码的t a n n e r 图表示，并在此基础分析了规则 码与非规则码的异同。 第三章首先论述了t a n n e r 图中的循环、g i r t h 以及它们对码字性能的影响， 并指出了编码的两个约束条件。其次，通过论述几种系统编码得出结论实现 线性编码须校验矩阵的非零元素和码长成比例。最后，论述了k i t e 码的结构特 点及其编码算法，并把它运用到本文所提的方案中。 第四章着重论述了b p 算法的消息密度进化及其算法实现。其次，针对 a w g n 信道，论述了密度进化的一种简化形式高斯近似。最后，把密度进 化运用到k i t e 码的设计中，为筛选参数p 提供了便利。 第五章论述了迭代译码算法，重点介绍了概率b p 算法和l l rb p 算法。其 次，用仿真的方法比较了b p 算法及它的两种简化形式的b e r 和f e r 性能。最后， 给出了本文所提方案的仿真曲线，且信源压缩能取得一定的编码增益。 第六章对全文的主要工作和结论进行了总结，并对后续的学习研究提出了想 法。 7 中山大学硕士学位论文第二章l d p c 码的概述 2 1l d p c 码 第二章l d p c 码的概述 1 9 6 2 年r o b e r tgg a l l a g e r 提出了一种新的线性分组码低密度奇偶校验 码，同时提出了用迭代译码的方法来进行译码【l 们。但是，由于当时计算机仿真 水平和存储介质的限制，这种编码并没有得到关注，码字的性能也没有得到应有 的体现。后来，由于d j c m a c k a y 和m n e a l 等的工作【】，情况发生了变化， 人们开始重新审视l d p c 码，发现它具有优越的性能和巨大的实用价值。1 9 9 6 年m a c k a y 证明了利用迭代译码的l d p c 码字具有接近s h a n n o n 极限的性能【l l 】。 然后，m a c k a y 和s p i e l m a n 提出了不规则l d p c 码的编码方式【1 2 1 ，在l d p c 码的 发展进程中具有里程碑的意义。近几年，t h o m a sj r i c h a r d s o n 和rl u r b a n k e 开创了利用软判决的迭代译码算法一置信传播算法，该算法把人工智能中的信 度传播思想运用到和乘积算法中，使l d p c 码的译码变得易于实现，推动了l d p c 码的实用化。而在理论分析方面，由t h o m a sj r i c h a r d s o n 等提出的密度进化成 为现代编码理论中分析纠错码的渐进性能的有力工具【1 3 1 。 虽然l d p c 码可以被定义在g f ( q ) 域上，但是本文只讨论g f ( 2 ) 域上的情 况。一个( 刀，后) 分组码的码字空间c 可以用行维二元向量空间彤的一个k 维子空 间来描述。对于消息序列u = ( ，d 2 c u k ) ，编码器将k 比特消息序列映射为刀比 特码字序列c = ( c l ，c 2 ，巳) ，这个过程可以由一个k x 刀维的生成矩阵g 来完成， 即c = 甜g 。与生成矩阵g 对应的是l d p c 码的校验矩阵日，两者之间满足关系 q 埘e l 所= o k 。厢，而码字序列满足校验方程h c t = 0 ，即每个码字都满足日对 应的m 个校验方程。例如，式( 2 1 ) 是一个4 7 的校验矩阵及其校验方程，其 中码字c = ( q ，c 2 ，c 7 ) c ，满足日c t = 0 。 h = lo ol111 ol0l0l0 oll0 o o 0 10oolo 1 9 2 o = 白 o + l l 坛却 坛 彩环d 以 + + = + 以艮白彩 + + + + “勿晚岛 ，l 专 中山大学硕士学位论文 稀疏信源下l d p c 码信道编译码技术研究 如果校验矩阵日是满秩的，那么m = 刀一k ，码率为，= 一m ) n = l m n 。 然而，日的各行不总是线性无关的，此时日的秩小于m ，则k 刀一m ，码率为 ， 1 一m 。 根据l d p c 码的定义，由校验矩阵日并不能直接构造合法的码字集c ，需 要把日转化为g ，常用的方式是g a u s s i a ne l i m i n a t i o n ( 高斯消去法) 或列变换法。 通过高斯消去可以把一个维数为m n 的校验矩阵h 变成如下形式 j ：彳= ：i , n ( 疗一) 鼻) 。 c 2 2 ， 其中，若h 是满秩的，变换后不存在全零行。 由以上变换可以得到系统形式的生成矩阵g = 只咖圳厶。】。其中，p 是g 的校验阵列，厶。七是单位矩阵。信息序列u = ( u i , 甜：，) 通过c = u g 映射为码 字c 。虽然日是稀疏的，但是p 通常不是稀疏的，这意味着编码过程中需要存储 大量p 的元素。 2 2t a n n e r 图 从2 1 节知道，l d p c 码的校验矩阵能有效地表示码字比特之间的校验关系， 除此之外，t a n n e r 提出使用二部图来形象地表达l d p c 码校验节点的性质，此二 部图常称为t a n n e r 刚1 4 】。图2 1 所示的t a n n e r 图中有两类节点，变量节点( v a r i a b l e n o d e ) 和校验节点( c h e c k n o d e ) 。其中，圆圈是变量节点，表示码字比特，方块 是校验节点，表示校验方程，即要求与每一个校验节点相连的变量节点的校验和 为零。t a n n e r 图是一种双向图，可以用集合g = ( y ，e ) ) 来表示，其中y 是所有 节点的集合，用公式表示为v = ku k 。对于维数为m n 的校验矩阵，k = ( h ，y 2 ， ，v 。) 是变量节点或比特节点的集合，对应校验矩阵中的列和码字中的位。圯= ( q ，c 2 ，) 是校验节点或函数节点的集合，对应校验矩阵中的行，即校验方程。 e 是所有的变量节点和校验节点之间相连的边的集合，( v ，c ，) 表示连接k 和c ，的 边。如果用集合h = h f i ) 来表示校验矩阵，那么( 一，c ，) e 的充要条件是办= l 。 h 。= 1 说明码字的第f 个比特参与第，个校验方程的校验，即第f 个变量节点和第 _ ，个校验节点相连。节点的度( d e g r e e ) 是与节点相连的边的数目。图2 1 所示 1 0 中山大学硕士学位论文第二章l d p c 码的概述 的t a n n e r 图中有1 0 个变量节点和5 个校验节点，每个变量节点有2 条边，每个 校验节点有4 条边。 q c 2吃qg 量节点 巧易 哆 均 吩咯 哆吩 侈 巧口 图2 1 校验矩阵的t a n n e r 图 在t a n n e r 图中从某个节点出发经过一些边后又回到该节点，中间历经的边 就构成了一个环路，称为t a n n e r 图中的圈，也叫循环。所历经的边的个数称为 圈的长度或循环长度，最短的圈长叫做t a n n e r 图的西n h 。因为圈长会严重地影 响译码的性能，所以t a n n e r 图中的西m 1 是一个衡量码字性能的重要标准。图2 1 中用粗线标出了一个圈，圈长为6 。 2 3 节点的度分布 为了更好地描述节点度的状况引入度分布函数的概念，定义如下 旯( x ) = 纠_ ： ( 2 3 ) 口 、 夕( z ) = p j x 产1 j = 2 其中，五( x ) 表示变量节点的度分布，p ( x ) 表示校验节点的度分布，且要求 名( 1 ) = p o ) = l 。或表示变量节点最大的度，吃表示校验节点最大的度。五表示 与度数为f ( f 2 ) 的变量节点相连的边的数目占总边数的比例，p ，表示与度数为 ( 2 ) 的校验节点相连的边的数目占总边数的