（通信与信息系统专业论文）ldpc高效编译码及其组合均衡技术在无线通信中性能的研究.pdf

南京航空航大人学硕十论文 摘要 低密度校验码( l o w d e n s i t yp a r i t y c h e c kc o d e s ) 是一类可以用稀疏的校验矩 阵定义且可用迭代方法译码的线性分组纠错码。它最初由g a l l a g e r 于1 9 6 2 年提 出，近来由于受到t u r b o 码研究的启发，l d p c 码被重新发现并受到编码界的 极大关注，己成为目前最热门的研究领域之一。 l d p c 码和t u r b o 码以各自的方式实现接近香农极限这一目标。l d f c 码具 有较大灵活性，描述简单，并且当码长足够长时，l d p c 码显示出比t u r b o 码更 为良好的性能。近年来l d p c 码作为一种性能优越且具有极大潜在应用价值的 纠错编码越来越受到编码学者和工程师们的关注。 本文对l d p c 码进行了较系统的分析和研究。首先介绍了l d p c 码的编码 结构，并给出了编码复杂度分析：然后介绍了标准b p 译码算法，给出了该算 法的理论基础和实现步骤，并在a w g n 信道及衰落信道下对其进行性能仿真， 研究不同因素对译码性能的影响；为了进一步改善译码性能，本文提出了一种 能够消除短周长环路的l d p c 编码方法，同时从理论和数值模拟两个方面研究 了咀信源与信宿为表征的l d p c 译码的收敛特性；最后，将l d p c 码与信道均 衡技术相结合，研究了组合l d p c 编码均衡系统的性能，并对浚系统的误码和 收敛特性进行了数值仿真。 关键词：l d p c 码，b p 算法，置信传播算法，t a n n e r 图，二分图，环路，信道均 衡，码间串扰信道( i s i ) ，最小均方误差( m m s e ) l d p c 高效编译码及其组台均衡技术在无线通信中性能的研究 a b s t r a c t t h el i n e a rb l o c kc o d ei sc a l l e dab i n a r yl o w - d e n s i t yp a r i t y c h e c kc o d ei fi t s p a r i t y c h e c k m a t r i xi s s p a r s e t h i ss o r t o fc o d ew a so r i g i n a l l yp r o p o s e db yd r g a l l a g e ri n19 6 2 ，w h i c hi sn o w r e d i s c o v e r e da n da t t r a c t sal a r g ea m o u n to fi n t e r e s t p a r t l yd u e t ot h ee x t r e m es u c c e s so f t u r b oc o d e sb o t hi nt h e o r ya n dp r a c t i c e l d p cc o d e sa n dt u r b oc o d e sa r es i m i l a ri nm a n ya s p e c t s ，b o t hc a r le x t r e m e l y a p p r o a c ht ot h es h a n n o nl i m i t sb yt h e i ru n i q u ew a y s m o r e o v e r , l d p cc o d e sa r e r e l a t i v e l ye a s yt ob ec h a r a c t e r i z e d ，a n dc a no u t p e r f o r mt u r b oc o d e sw i t hs u f f i c i e n t l y l o n gb l o c kl e n g t h s 一 t h i st h e s i sp r e s e n t sa c o m p r e h e n s i v es t u d yo n t h ep e r f o r m a n c eo fl d p cc o d e s a n dc o m b i n e de q u a l i z a t i o n 晰ml d p cc o d e s f i r s t w e b r i e f l y i n t r o d u c et h e e n c o d i n g s t r u c t u r eo fl d p cc o d e sa n dr e l a t e d c o m p l e x i t yi s s u e s ，t h e n f o ri t s d e c o d i n gu s i n gs o c a l l e ds t a n db e l i e fp r o p a g a t i o n ( b p ) a l g o r i t h mt o g e t h e rw i t ht h e t h e o r e t i c a lf u n d a m e n t a l sa n dt h e p r a c t i c a ls t e p sa c h i e v i n g t h i s g o a l t h e p e r f o r m a n c es i m u l a t i o n sa r ea l s oc a r r i e do u to v e ra na d d i t i v ew h i t eg a u s s i a nn o i s e ( a w g n ) a n df a d i n gc h a n n e l st of i n do u tt h ec r u c i a lf a c t o r st h a tc a ns e r i o u s l ya f f e c t t h ed e c o d i n g p e r f o r m a n c e i no r d e rt of u r t h e ri m p r o v et h ep e r f o r m a n c e ，w ep r o p o s e an e w a p p r o a c h t h a tc a ne f f e c t i v e l ye l i m i n a t et h es h o r tc y c l e so f t h e b i p a r t i t eg r a p h f o rt h el d p c e n c o d i n g m e a n w h i l e ，w ea l s oi n v e s t i g a t et h ec o n v e r g e n c ep r o p e r t i e s o fi t e r a t i v el d p c d e c o d i n gc h a r a c t e r i z e db yb o t hs o u r c ea n de s t i m a t e ds y m b o ls e t s f r o mt h e o r ya n dn u m e r i c a ls i m u l a t i o n s f i n a l l y ，w ef o c u so nt h ep e r f o r m a n c eo f c o m b i n e d e q u a l i z a t i o n a n dl d p cc o d e s ，a n db e rr e s u l t sa n d c o r r e s p o n d i n g c o n v e r g e n c ep r o p e r t i e sa l et h u so b t a i n e do v e rt h ei s ic h a n n e lb yt h es i m u l a t i o n s k e yw o r d s ：l d p cc o d e s ，b p , m a s s a g ep a s s i n g ，t a n n e rg r a p h ，b i p a r t i t eg r a p h ， c y c l e ，c h a n n e le q u a l i z a t i o n ，i s i ，m m s e 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立 进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容 外，本学位论文的研究成果不包含任何他人享有著作权的内容。对本 论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明 确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 童銮鉴皇堕鲞叁堂婴主堡茎 a w g n b p b s c d f e d m c i s i l d p cc o d e s m m s e 注释表 a d d i t i v ew h i t eg a u s s i a nn o i s e 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 b i n a r ys y m m e t r i cc h a n n e l d e c i s i o n f e e d b a c ke q u a l i z a t i o n d i g i t a lm e m o r y l e s s c h a n n e l i n t e r s y m b o li n t e r f e r e n c e l o w - d e n s i t yp a r i t y - c h e c kc o d e s m i n i m u m m e a n s q u a r e e r r o r 加性白高斯噪声 置信传播算法 二进制对称信道 判决反馈均衡器 离散无记忆信道 码间干扰 低密度奇偶校验码 最小均方误差 南京航空肮天人学硕十论文 第一章绪论 1 1s h a n n o n 信息理论及信道容量 一个基本的数字通信系统可以用下图来表述 幽1 1 数字通信系缆的基本模型 信源的功能是将载有信息的消息传送出去，一般而言信源输出的消息为模 拟信号，信源编码器将其转化为二进制或多迸制离散序列，信道编码起则是对 信源编码起输出的离散信息序列适当地添加冗余度( 或相关性) ，使接收机译码起 具有自动纠检错能力，以降低比特( 或符号) 误码率。 信道编码大致可以分为两类问题，一类是信道编码定理，解决编码器和译 码器存在的问题：另一类编码方法及其性能界限。信道容量是信道能传送的最 大信息率。编码定理是用来解决达到这个最大值的可能性和超过这个最大值时 传输问题的方法：是在有扰信道中进行可靠信息传输的基石。s h a n n o n 于1 9 4 8 年提出的有扰信道随机编码定理，简称为s h a n n o n 定理。它明确的指出任何一 个有扰信道均存在一个确定的信道容量c ，对于小于此信道容量的信息传输速 率，存在一种编码方式，当采用最大似然译码且码长趋近无穷大条件下，其译 码错误概率亦趋近于零。 1 1 1b s c 信道容量 l d p c 高效编译码及其组合均衡技术在无线通信中性能的研究 为了更完整和准确的理解s h a n n o n 定理，先研究最简单的基本信道，m 迸 制( m 2 ) 输入q 进制( q m ) 输出离散无记忆信道( d m c ) 。 如图1 1 所示，由信道编码器输出至d m c 的m 进制符号集为 x = x 。，z 。一 ，d m c 输出的q 符号集为y = k ，门，y 。， ，该信道的转 移概率为p b ，i j ，) 。信道输入x 和输出y 的平均互信息定义为 删=窆孰)pd，)logx11=0i - 0甜 ( 1 t ) ，；y ) = 尸g ，) p b ，：；掣 ( 1 1 ) 1v j ， 输出y 与自身的平均互信息，( e l ，) 为 7 ( y ；y ) 2 善尸& ) l o g 东西 ( 1 t 2 ) ，( 1 ，； ，) 亦称作为输出y 的( 无条件) 熵，通常用h ( y ) 表示。在输入x 被观察 到情况下输出y 的条件熵h ( y i x ) 定义为 砷2 嘉p l o g i - o南i ( 1 ，) ，l o 1 vi “， 它表示输出h y 由于输入x ，e x 被观察到后所减少的熵( 不确定性) 。易证 ，似：y ) 也可以表示为输入x 由于输出y 被观察到后所减少的熵，即 i ( x ；y ) ；h 伍) 一片ly )( 1 4 ) 对于一般d m c ，s h a n n o n 定义它的信道容量c 为 o m a x i ( x y 枷j 1 叫一i ( i 5 ) 如果对数以2 为底，c 的单位为比特( b i t s ) 信道符号 为底，单位为奈特( n a t s ) 信道符号。 如果对于b s c 信道( 二进制对称信道) 。 c 。鼍鬻 ( 砷一( y f z 叫一， 一个b s c 信道可用如图1 2 所示的转移概率表示 如果采用自然对数e ( 1 6 ) 南京航空航犬人学硕十论文 1 一p 图1 2 二进制对称信道( s s c ) 的转移概率 则条件熵h ( y l x ) 为 p l x ) = 一p l o g p 一( 1 一p ) l 0 9 0 一p ) = h 0 )( 1 , 7 ) 由上式可知道条件熵h ( y l x ) 与输入x 的概率分布无关，因此求c 也就是求 h ( y ) 的最大值。即信道容量c = 1 一r ( p ) 。它是一个仅与转移概率有关的函数。 采用类似的方法，我们可以推导出二进制删除信道( b e c ) 3 5 i 二元输出o 元 ( q ，2 ) 输出离散无记忆信道的信道容量。详见口2 1 。 1 1 2 a w g n 信道容量 上一节我们研究了离散无记忆信道( d m c ) 的信道容量，然而对于许多实际的 数字通信系统，等效的为离散输入连续输出型，特别是二进制输入，即 j = + 爿，一爿) 且y = ( _ 。o ，- 啪) 。信道所受到的噪声为加性白高斯噪声或者拉普拉斯 噪声等。可以证明二进制输入在等概率条件下，输入x 和输出y 的平均互信息 ，；y ) 达到最大，本节我们将研究二进制输入连续输出型信道的容量。 若x ，y y 且加性白高斯噪声的均值为零方差为a2 ，随机变量y 的概率 密度函数为 p p ) = | p 0 = + 一) p 0 【z = + 一) + p ( x = 一一) 尸0 i x = 一a ) = 志h 一爿。卜刘，s ， 信道容量为 c = 陋( y ) 一h ( y l z ) 】h 。m 。一。瑚，2 ( 1 9 ) y 的熵为 = e p o ) | 0 9 z 未矽一艮o ) l o g 2 靠协( 1 i o ) l d p c 高教编译婴苎堡盒塑塑垫查鱼垂垡望堕! 竺璧塑型! 塞一 一一 输出y 在输出x 己知下的条件熵为 x ) = 一e p ( y 卜= + 一) i o g ：卢锄x = + a ) d y j 1e p i x = - a ) l o g 。py t x = - a 匆 ：昙l o g ：( 2 磨仃z ) ( 1 ，1 1 ) 则得到二进制输) l k g 续输出s w g n 条件下的信道容量 c ：阻妒) 一日( y i x ) i e ( 。, - + ) e l ：- , 0 - 1 s 2 = - e 厶) i 。g ：厶( y ) 方一吉i 。g ：( 2 m 口2 ) ( 1 1 2 ) 而对于带宽受限的加性白高斯噪声( a w g n ) 信道，s h a n n o n 定义它的信道容 量为 c 2 j 魄错亭7 ；】，) ( 1 1 3 ) 输入输出信号和单边功率谱密度为o 的a w g n 分别为x ( f lj ，( f ) 和一o ) ，假设 接收机的带宽b 与发射信号的带宽相同，接收机在时间间隔t 内用速率为2 b 的采样速率对接收信号进行采样，得到一组n = 2 b t 个独立离散值的采样序列 h = y ，y ：，y 。 ，与此对应的发射信号x ( f ) 的离散样值为x 。= k ，x z ，x 。 且 满足y = + 。，t i 为a w g n 的采样值( i = 1 , 2 ，) 。发射信号和接收信号序列 x 。和的平均互信息为 ，；r ) = 鸶p ( y ，i b b ) l 。g ：；竿出，咖， ( 1 1 4 ) a w g n 经过相关接收后的噪声功率为n o 2 故条件獠军翟魇函数为 p ) = 两1 e x p 1 ) 2i n o 】 ( 1 1 5 ) 可以证明当扛； 为零均值方差为一；的独立高斯序列时，即 加，= i f p ( x 扣( 去 ”尊忖e x p 别1 6 ) i j 口“埘，x w ) = 。) = i 而 i 兀j 一专l j ( 1 f lv v t ，= 】 。j l 式( 1 1 4 ) 所示的平均互信息s ( x 。；) 达到最大，将( 1 15 ) 和( 1 1 6 ) 代入( 1 1 4 ) 可得 擀，) = 删。- + 瓦s a y ( 1 ) 其中s 。，是发射信号x ) 的平均功率，因此带限a w g n 信道的信道容量为c 南京航空航天火学硕+ 论文 c - 胁小蔫j 我们定义传输系统的谱功率为输入编码器的比特速率与传输信号所占用的 信道带宽之比，即_ = “b ( 比特秒h z ) 。由于s 。与该比特序列的功率是相同的， 故有 显：l i r a 监：l i m 生 f 1 1 9 ) n o_ ( b n o “一( n o 、 其中e 。为单位比特能量。与上一节所述b s c 中的s h a n n o n 定理类似，在带 限a w g n 信道中，若， 0 ，因此15 9 d b 是所有编码 系统的i | 缶界( 门限) 值( t h r e s h o l d ) 。也就是说，单位比特能量e 与白高斯噪声的单 边功率谱密度虬的比值小于此值时，不可能存在任何能实现无差错传输的编码 方式。 无限接近这一极限值是信息论和信道编码学术界为之奋斗的最终目标。当 e 。n ，大于此极限值时，码长足够长的l d p c 码，能够无限接近于实现无差错 传输这一终极目标，这也是为何本文研究l d p c 的编译码的理论依据。 1 2 信道编码概述 在通信中，出于信道中各种噪声的干扰，使人们难以进行可靠的通信。为 了实现信息的可靠传输，人们提出了纠错编码，纠错编码是提高信息传输可靠 性的一种重要手段。在传输过程中发生错误后能在接收端自行发现或纠f 的码， 称j , s 2 t l 错码。为使一种码具有检错或纠错能力，须对原码字增加多余的码元， l d p c 高效编涕码及其组合均衡技术在无线通信中性能的研究 以扩大码字之问的差别，即把原码字按某种规则变成有一定剩余度的码字，并 使每个码字的码之间有一定的关系。这种关系的建立称为编码。码字到达收端 后，可以根据是否满足编码规则来判定有无错误。当不能满足时，按一定规则 确定错误所在位置并予以纠正。纠错并恢复原码字的过程称为译码。检错码与 其他手段结合使用，可以纠错。纠错码主要分为分组码和卷积码。我们下面来 分别介绍。 1 2 1 分组码 分组码是信息序列以k 个码元分组，通过编码器对每组的k 元信息通过一 定的规律产生r 个冗余码元( 称为校验元或监督元) ，输出长为n = k + r 的一个码字 ( 码组) 。分组码用( n ，k ) 表示，n 表示码长，k 表示信息位数髫，r = k n 表示分组 码的编码速率( 编码率或码率) 。线性分组码是分组码中最重要的一类码，也是讨 论各类码的基础。 任一个分组码( n ，k ) ，如果其信息元与监督元之间的关系可以用次方程表 示，也就是说他们之间的关系是线性的，那么就称其为线性分组码。一个( n , k 1 分组码，长为r l 的所有二进制组( 或重) 共有2 ”个，但长为k 的信息组共有2 t 个， 而分组码编码就是如何从已知的k 个信息元求得，= 一一k 个校验元，必须有。一k 个独立的线性方程，根据求监督元的不同线性方程，就得到不同的( n ，k ) 线性分 组码。如果线性分组码的前k 位就是由信源输出的未变化的信息位，而后。一 位 就是监督位，这样得到的线性分组码是线性系统码。 一般情况下，二进制线性分组码( n ，k ) 的校验矩阵可表示为 卜一一札。h 。 l 2 ，n lh 2 ，n 一2 一 h 2 o l l l 一一 叱m 蠢d 由此校验矩阵可以很快的建立码的线性方程组 南京航空航天人学硕十论文 fh i ，h 一1h ln 一2 一。 h 2 、n 一1 2 一2 - i! i 。一。一i 。一。一2 一 h 。 刮 ：0 7 简写成 h c 7 = 07 或者c7 = 0 ( 1 2 3 ) 二进制线性分组码( n ，k ) 的每一个码字都必须满足式( 1 2 3 ) ，也就是说| ，校验 矩阵的每一行与它的码的每一码字的内积均为零。 例1 1 ，一个系统( 7 ，4 ) 码的校验矩阵为 州 可以根据其校验矩阵得到相应的校验方程 c o + c i + c 24 - c 4 = 0( 1 2 4 ) c l + c 2 + c ) + c 5 = 0( 1 ，2 5 ) 设c = c 0 ，c 一，g 1 ) 是一个二进制n 重的分组码，那其汉明距离则为码字中 非零元的数目，而两个码字问对应位不同的数目为汉明距离。( n ，k ) 线性码的2 个 码字的最小距离称为最小汉明距离，简称最小距离盛，分组码的最小距离f 5 6 j 等 于码中非零码矢的最小重量。 可以证明，对于一个晟小距离为哦的( n ，k ) 线性分组码，有 1 若盛e + i ，则此分组码能检验p ；d o 1 个随机错误。 2 若乩2 f + l ，则此码能纠正扣鱼；个随机错误。 3 若d 。t + e + 1 ，则此码能同时纠正t 个随机错误同时e 个锚误。 由上知，一个线性分组码有两个重要的参数，一个是最小距离d a ，一个是码 率r 。最小距离哦反映纠错能力，矗越大，码的检错能力和纠错能力就越强。 r 表示信息位在码组中所占的e c 重，r 越大，信息位占的比重越高，码的有效 性越高。 1llllljf_ i t o 一 一 ! 里! 竺壹塾塑堡里墨茎丝盒垫堡垫查鱼蒌些望堕主堂堂盟婴塑一 卷积码是将序列以k 个码元分段，通过编码器输出长为n 的码段。该码段的 。一女位校验元不仅与本段的信息元有关，也与前m 段的信息元有关a 故卷积码 用，k ，m ) 表示。 图1 3 给出了一个n = 3 ，k = 1 ，m = 2 的( 3 ，1 ，2 ) 卷积码编码器。图中t 为移位寄 存器，若每一时间单位输入编码器一个新的信息元，编码器输出3 个码元 c = 仁，p ，f ，p ，2 ) 输 圈1 3 ( 3 ，1 ，2 ) 卷积码编码器 由图可知 p ，i2 m i + m i i p t 22 m i + m p 2 下一个时间单位输入的信息元为m 。与其相应的两个校验元 出 ( 12 7 ) ( 1 2 8 ) p i = m + m ，( 1 2 9 ) p 2 = m + m h( 1 3 0 ) 和分组码一样，卷积码的编码效率定义为r = k i n ，对于具有很好的纠、检 错功能并能合理又实现简单的大多数卷积码，总是k = 1 或是 一k = 1 。 卷积码的译码大致分为代数译码和概率译码两种前者是从码字本身的代 数结构出发，不考虑信道统计特性：后者尚需计及信道特性，真f 用到实际中 的是维特比译码，它是概率译码算法中的一种。 1 3l d p c 码的特点及研究情况 l d p c ( l o w e r d e n s i t yp a r i t yc h e c k ) 码最早在1 9 6 2 1 2 】年出g a l l a g e r 提出， 因为其校验矩阵含有大多数的0 而仅含有少数的1 而得名；也就是说它是一类 南京航空航天大学硕十论文 可以用稀疏的校验矩阵( p a r i t y c h e c km a t r i x ) 定义的线性分组纠错码。g a l l a g e r 在 他的文章 2 中一个重要的创新就是引入迭代译码算法( i t e r a t i v ep r o b a b i l i s t i c d e c o d i n g l 2 】1 现在被称为置信传播( b e l i e fp r o p a g a t i o n ) 算法的一种特殊情况。但 是由于当时的技术条件的限制，从l d p c 码的发现到t u r b o 码的出现，在这将 近三十年的时间里，人们逐渐淡忘了这种编码。随着计算机能力的增强和相关 理论( 如图论、b e l i e fp r o p a g a t i o n ( b p ) 等) 的发展，人们重新发现了l d p c 码。m a c k a y 、n e a l 、r i c h a r d s o n 和u r b a n k e 证明l d p c 码，尤其是非正规l d p c 码在与基于b e l i e f p r o p a g a t i o n ( b p ) 的迭代译码相结合的条件下具有逼近香 农限的性能【1 1 。以下是l d p c 码的特点和研究现状： 根据t a n n e r 图中信息节点和校验节点次数分布的不同，l d p c 码可以分为 正觌码和非正规码。正规码是所有信息节点有相同次数，所有的校验节点也有 相同次数的编码。而非f 觌码是正规码的推广，它的次数分布无论是信息节点 还是校验节点都不再有次数相同的限制。由于次数分布选择上的自由性，只要 适当选择非正规码的次数分布，会在译码时导致一种波状效应，极大的提高译 码的门限值，相应的在性能上相对正规码也有极大的提高。 由于l d p c 码校验矩阵的稀疏性，矩阵中非零元的个数与码长成线性关系。 这就使得它可以在线性时间内进行译码。其译码算法主要有信息传递( m e s s a g e p a s s i n g ) 算法pj 。这是一个算法类，我们可以根据自己的需要在性能和复杂度间 折中的选择合适的算法。其中性能最好的是连续性的b e i i e f p r o p a g a l i o n ( b p ) 算法 4 1 。 l d p c 码具有能够逼近香农极限的性能特性；同时得益于校验矩阵的稀疏 性，这样优秀的性能是在不太高的译码复杂度一一线性复杂度内实现的：l d p c 码的描述和实现简单，编码的译 i 2 q ( m e s s a g ep a s s i n g ) 算法本质上是并行算法，有 利于硬件的并行实现，减少译码时延；m e s s a g ep a s s i n g 算法存在一种译码1 7 限效 应，只有当信道噪声方差低于门限值时，译码后的误码率可以趋于0 ，否则由 于概率演化方程中不动点的不可逾越性，将不能趋于o ；l d p c 码性能的优越性 通常要在码长较长时才能够体现出来，当码长为中短长度时，由于编码中短长 度环的存在，会在某种程度上降低编码的性能。在编码上，l d p c 码具有自己 简单的数学模型：t a n n e r 图。l d p c 码的缺点主要在于编码的复杂度较高，虽然 最新的研究表明它可以在线性时间内编码，但是其复杂度相对于卷积码等可以 即时编码的码来说仍然过大。同时在码长很长时，由于必须在接收到所有的信 息比特居彳能够进行编码，这就会给编码带来一定的时延。 然而，l d p c 码所面i 临的一个主要问题是其较高的编码复杂度和编码时延。 对其采用普通的编码方法具有二次方的编码复杂度，在长码长时，这是难以接 l d p c 高效编泽码及其组合均衡技术在无线通信中性能的研究 受的。t h o m a sj r i c h a r d s o n 和r u d i g e rl u r b a n k e 在文献 7 】中给出了利用校验 矩阵的稀疏性，对校验矩阵进行一定的预处理后，在线性时削内编码的有效算 法。初步解决了l d p c 码的应用所面临的一个主要问题。但是编码前的数据接 收过程引入的编码时延仍然是l d p c 码需要研究解决的一个问题。 l d p c 码性能的好坏受到众多因素的影响，而编码的长度决定了其性能能够 在何种程度上逼近该门限值。在中短码长给定次数分布对的条件下，编码二分 图的结构对码的性能又有着显著的影响，图中短长度环的数量越少越好，环的 平均长度越长越好。在接收端，译码算法的选择是影响编码性能的决定性因素 要得到好的性能就需要付出在实现复杂性上的代价。在译码过程中，对信道信 噪比估计的准确性也是影响译码性能的一个重要因素，如果信噪比估计失配会 使译码性能降低，估计的偏差越大，性能的损失越大，甚至不能够正常译码。 考虑到影响l d p c 码性能的因素，要设计好的l d p c 码，首先要根据应用中性 能和时延等方面的要求选择合适的码长，然后根据信道类型和性能需求寻找具 有较高译码门限值的次数分布对，这方面现有的搜索方法主要有t h o m a s j r e c h a r d s o n 等人提供的局部优化和全局优化的搜索方法【8 】，但是它们的搜索量 都相当大，需要借助计算机进行搜索，故而我们需要研究合适的构造方法，以 构造出好的校验矩阵，获得好的编码性能。 由上述介绍的l d p c 码性能的优越性，我们可以预测，l d p c 码将在通信中 得到广泛的应用。目前，l d p c 码由于出色的纠错性能以及适合并行操作的译 码算法成为人们关注的热点，例如应用于压缩图像的传输1 9 】，信源遍码方案采 用j p e g 静止图像压缩标准，信道遍码方案采用l d p c 码：l d p c 码也应用于深 空通信及磁记录信道1 1 0 i 1 】和d s l ，a d s l 1 3 】1 1 4 】。而且在工程实现上。一些试 验性的硬件已经研制出来，如：可编程码率可调的l d p c 译码芯片 1 5 】等等。另外 对l d p c 码其他方面应用的研究也非常广泛，包括应用于外层空削和卫星通信、 下一代无线通信、磁存储器，网络数据包传输等等，l d p c 码被认为是能够应 用于高速宽带传输系统中的理想编码方式。总之在未来移动通信系统物理层的 编码方案的选择上，正规( r c g u l l a r ) l d p c 码比卷积码再数据传输方面有更强的 竞争力。 1 4 本文的主要工作及内容安排 下面简要叙述本论文的大致组织情况。在论文的第一章绪论，介绍了本文 的背景和基本理论，回顾了分组码和卷积码的理论，并在此基础上简单的介绍 了l d p c 码；第二章介绍了l d p c 码的定义及不同的表示法：在论文的第三章， 南京航空航天人学硕+ 论文 介绍了b p 译码算法的基本原理，讨论了译码算法的外部信息，为研究该译码 算法的性能，分别在白高斯信道和平坦瑞利衰落信道下、在不同的数据长度， 不同的迭代次数下对b p 译码算法进行了模拟和分析；在这一章，作者还分析 了t a n n e r 图中的环对译码性能的影响，并介绍了一种构造消除4 环的l d p c 码 的方法，并对其进行了仿真，对比消除4 环的前后，译码性能的变化；在第三 章的最后，作者对b p 算法的收敛特性进行了研究，并通过信源和信宿两种不 同的表征方式来模拟其收敛特性。在论文的第四章，首先介绍了i s i 信道和信 道均衡技术，引入了将均衡技术与l d p c 码b p 算法相结合，并对其进行了模 拟和分析。最后，在第五章我们对整个研究内容进行了总结。 总之，l d p c 码是目前研究的热点，对其作深入的研究将有助于l d p c 码在 实时通信系统中的应用。 ! 旦! 璺壹塑塑堡里墨茎塑鱼塑塑垫查垄重垡望笪丝堂塑塑型 第二章l d p c 码的结构及编码 本章我们主要介绍l d p c 码的定义及编码。l d p c 码是一类可以用非常稀疏 的校验矩阵( p a r i t y c h e c km a t r i x ) 定义的线性分组纠错码，并以其优越的性能 受到广泛的关注。 针对l d p c 码的编码问题，很多研究人员进行了研究，s i p s e r 和s p i e l m a n 提出永缴联图来减小编码复杂度 1 6 l 【1 7 】，通过选择级联的层数以及每层的大小可 以构造线性时间内可编码和译码的码。m a c k a y ，w i l s o n 和d a v e y 建议强制性的 使奇偶校验矩阵具有下三角阵的形式，这个约束保证了编码具有线性的编码 时间复杂度，但是它通常也会导致性能上的一些损失。本章中的有效编码方法 来自予t h o m a sj r i c h a r d s o n 和r u d i g e rl u r b a n k e 【7j ，在这种编码方案下，仅 仅对编码的校验矩阵进行一些重排的预处理，就能使编码的时间复杂度在绝大 多数情况下都是相当可控的甚至具有线性时间复杂度。 本文以f 规( r e g u l l a r ) l d p c 码为主要研究对象，以下论文中l d p c 即指正 规l d p c 码，非正规( i r r e g u l l a r ) l d p c 码将特别加以说明。 2 1l d p c 码的定义及表示法 21 1l d p c 码的稀疏矩阵表示法 l d p c 码因为其校验矩阵含有大多数的0 而仅含有少数的l 而得名；也就 是说它是一类可以用非常稀疏的校验矩阵( p a r i t y c h e c km a t r i x ) 定义的线性分 组纠错码。l d p c 码分为传统的j 下规( r e g u l l a r ) l d p c 码和非正规( i r r e g u l l a r ) l d p c 码。如果线性分组码的奇偶校验矩阵每一列含有d 、，个1 ，每一行含有d ，个l ， 其中d 户d 。，那么我们就称这样的线性分组码为二进制f 规l d p c 码。我们用 a ( n ，d ，d c ) 来表示个l d p c 码。奇偶校验的等式方程数量是m = n d 。d 月就 是l d p c 码的码长。我们用a ( n ，d 。，d c ) 来表示一个l d p c 码。换句话说，每 个码字比特参与了d 。个奇偶校验方程，而每个校验方程包含了一个码字比特。 相形之下，d 。和t 要远远小于n ，这正体现了低密度的特性。码率 ，= 和一m ) l n = ( 以一d 。) 以= i d ，以。值得注意的是陔式子只有在h 是满秩矩 阵的时候成立否则，= ( 一r a n k ( h ) ) ”。 由线性分组码的性质，域f 上长n ，m 维的编码c 可用“一m ) x 维的校验矩 堕窒塾至堕鲞奎堂婴主堡苎 阵h 描述： c ( m ：k e ：h x l = 0 l d p c 码也不例外。 例2 1 一个l d p c 码a ( 9 ，2 ，3 ) 的校验矩阵如下： 片“9 = ( 2 1 ) 那么满足该校验方程的码字应满足 h c 7 = 0 7 ( 2 2 ) 该例中的l d p c 码每一列含有2 个l ，每一行含有3 个1 ，共有m = 9 x 2 3 = 6 行，也就是说共有6 个校验方程。 例2 2 一个l d p c 码a 0 2 ，3 ，6 ) 的校验矩阵如下： 风m = 则c = 【1 00000 01100 1 】满足式风m c = 0 7 ，也就是晚c 是 a ( 1 2 ，3 ，6 ) 的一个码字。 2 1 2l d p c 码的t a n n e r 图表示法 l d p c 码的特殊性就在于它的奇偶校验矩阵中1 的数目远小于一0 的数目， 根据上一节介绍的校验矩阵的规律性，可以用二分图表现出来。在图论中一 个图是由顶点和边组成的，二分图：图中所有的顶点分为两个子集，任何一个 子集内部各个顶点之间没有边相连，任意一个顶点都和一个不在同一个子集罩 的顶点相连。l d p c 码的二分图表示法，组称为变量节点( 对应于码字比特， 也就是矩阵中的y r j ) ，另一组成为校验节点( 对应于奇偶校验约束，也就是矩阵中 的行) 。若某个校验约束方程中出现了某个码字比特，则在相应的信息节点和校 验节点之间出现了连边，也对应着相应的h 阵中的l 。 例2 3 上节例2 1 中的l d p c 码a ( 9 ，2 ，3 ) 码的相对应的二分图如下 1 0 0 0 1 l l 0 l l 0 0 o o l o ，l 0 o o 0 1 1 ，o o o o 1 o 0 l o l 1 o 1 1 0 0 o l l i o o o o i ，0 0 1 o o，0， l l l 0 0 0 兰旦! 竺壹塑塑堡塑墨茎丝鱼塑塑垫查鱼蚕丝望堡! 堡鐾塑型堕l 校验节点 变带节点 v i v 2 v 3v 4v 5 v 6v 7v 8v 9 图2 1a ( 9 ，2 ，3 ) l d p c 的二二分图 图中的黑点表示变量节点，白点表示校验节点，每一个校验节点表示一个 约柬方程( 校验矩阵中的一行) ，每一个变量节点表示码字比特( 校验矩阵中的一 列) 。每个变量节点有2 根连线( 因为每一列含有d ，个1 ，此处d 。= 2 ) ，每个校验 节点有3 根连线( 因为每一列含有d 。仑l ，此处d 。= 3 ) 。 l d p c 码的二分图又称为t a n n e r 图f 2 引，t a n n e r 图的提出其实是为了能用一 个或者更多的短纠错码来表示长的纠错码。这是由t a n n e r 在1 9 8 1 年首次提出， 并以t a n n e r 的名字命名。一个t a n n e r 图和一个校验矩阵完全对应：如上例中的 正规码的二分图，可以把它拆成一个一个字码来表示，其中一个子码表示如下： 图2 2 a ( 9 ，2 ，3 ) l d p c 的一个( 3 ，2 ) 子码 t a n n e r 图中的环是指连接变量节点和校验节点的，起始和结束于同一节点 并且不重复包括同一个节点的路径。环的长度也就是边的数量，而t a n n e r 图的 周长也就是环的最小长度。 定理l d p c 码的任意个周长l 的环，满足l 4 ，且l 是2 的倍数。 证明 出于构成一个环需要至少经过3 个节点，所以上3 ：下面证明l 是 2 的倍数，根据t a n n e r 图的性质，信息节点h l i = 1 , 2 ，n 和校验节点 p ，f - ，= 1 , 2 ，m 之f b 可能有边相连，但是信息节点和校验节点内部没有相连的 边。假如从一出发经过奇数步回到节点，那么必然在集合f _ 1 , 2 ，月 或者集 合扛加= 1 , 2 ， 内部存在一条边，这与t a n n e r 图的性质是不相符合的，因此 4 。_ 上4 南京航空航天大学硕+ 论文 例2 4 ：一个正规l d p c 码a ( 8 ，2 ，4 ) 的校验矩阵如下： 氐。= 卜凇一* 十o e一引1 0 0-0-0-1 ll l 卜j - 一一 一 - 一一l 校验节点 变量节点 一 图2 3a ( 8 ，2 ，4 ) l d p c 的校验矩阵和t a n n e r 图 t a n n e r 图中长度为4 的环是很容易从校验矩阵直观地检测出来，以校验矩 阵的非零元素“1 ”为一个顶点，则校验矩阵中的一个矩形就是一个周长为4 的环， 如图2 3 虚线画出了校验矩阵中的2 个矩形，分别对应于t a n n e r 图中一个环， v 2 斗c l 寸v g _ 乃哼v 2 ，v l 专c 2 斗v 4 斗c 4 哼v i 就构成长度为4 的环。虽然这 种方法很容易检测出周长为4 的环，但是对于周长大于4 的环，使用这种方法 判定还是很困难的。 2 2l d p c 码的编码 n n 黼- q ，也就是在给定了一个g f ( 2 ) 域上的l d p c 的奇偶校验矩阵h 的 基础上，产生一个n 维的( g f ( 2 ) 域上的) 向量，使其满足 h x 。= 0 ( 2 _ 3 ) 2 2 1 高斯消元法 这旱我们要说的编码的算法是高斯消元法f 6 1 。 一般地，爿中的m 个行向量不一定是线性无关的。当然，高斯消元法可 利用行变换和列变换将任意校验矩阵h 变换成一个下三角阵。行变换并不会 改变码字的结构，但是列变化会改变二分图中变量节点的位置，而此时产生的 码字就是满足经过列变换后的新的校验矩阵日的码字。经过列变换的。， 与原矩阵日的区别反映在二分图上只是一些校验节点的位置发生了变化，并 没有改变l d p c 码的纠错能力。 下面我们来举例看看，列变化所引起的校验矩阵的相应变化。 l d p c 高效编泽码及其组合均衡技术在无线通信中性能的研究 例2 5 一个a ( 9 ，2 ，3 ) 的校验矩阵为