（通信与信息系统专业论文）低密度奇偶校验码编译码原理及实现.pdf

摘要 低密度校验码( 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 ) 是一种能逼近 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 编译码的实 现有一定的指导意义。 本文根据i e e e 8 0 2 1 6 e 中准循环移位的l d p c 码设计了串并结合的硬件编码结 构。这种结构使用移位寄存器实现，思想简单，不需要使用存储器对校验矩阵的 信息进行存储。同时，对非简化的译码方法( 和积译码算法、t d m p ( t u r b o d e c o d i n g m e s s a g e p a s s i n g ) 算法) 硬件实现的特点进行了简单的讨论。p e g ( p r o g r e s s i v e e d g eg r o w t h ) 算法是一种重要的随机构造校验矩阵的方法，本文给出了p e g 算法 在消确定围长时的应用，通过对各种方法的时间复杂度的分析比较和仿真，得到 了较有效的实现方法。这里得到的较有效方法同样适用于原始的p e g 算法。在译 码时要求接收端对数据进行同步，本文使用m 序列作为帧头对数据进行同步检测。 相关运算时，接收到的信息不经过硬判直接与本地m 序列进行相关运算( 这里称 为：软相关) 。把漏同步和假同步概率和最小作为确定相关门限值标准，通过理论 分析得到相关门限值，并通过仿真进行了说明。除了上述的主要内容，本文通过 一个例子对和积译码方法进行了说明，并对密度进化的基本思想进行了描述。 关键词：低密度奇偶校验码( l d p c )f p g a 同步 a b s t r 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 l eac l a s so fc a p a c i t ya 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 ne 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 fd e c o d i n g a n dl o w e re r r 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 dg 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 r o u g ht a k i n gp a r ti nt h ep r o j e c t ：t h ei m p l e m e n t a t i o no fl d p ce n c o d e ra n d d e c o d e r , ih a v eu n d e r s t o o dt h et h e o r i e so fi d p cc o d e s t h o s ea r em a i nc o n t e n t si n t h i sp a p e r t h ei m p l e m e n t a t i o no fl d p ce n c o d e r , t h ec h o i c eo fl d p cd e c o d i n g m e t h o d sa n dt h em e t h o do fs y n c h r o n i z a t i o na r ep r e s e n t e d t h o s ec o n t e n t sa r eu s e f u l f o rt h ei m p l e m e n t a t i o no fl d p c b a s e do nt h es t r u c t u r eo fl d p ci ni e e e 8 0 2 1 6 e ac o m b i n e ds e r i a la n dp a r a l l e l e n c o d i n gs e h e m ei sp r e s e n t e d s h i f tr e g i s t e ri su s e di nt h ee n c o d e rw i t h o u ts t o r i n gt h e c h e c km a t r i xo fl d p c ，w h i c hi s s i m p l y t h ei m p l e m e n t a t i o nc h a r a c t e r i s t i c so f s u m - p r o d u c ta l g o r i t h ma n dt u r b o d e c o d i n gm e s s a g e p a s s i n ga l g o r i t h ma r ed i s c u s s e d p r o g r e s s i v ee d g eg r o w t ha l g o r i t h mi sa ni m p o r t a n tm e t h o do fc o n s t r u c t i n gac h e c k m a t r i xr a n d o m l y i nt h i sa r t i c l e ，p e gi su s e dt oc o n s t r u c tac h e c km a t r i xw i t h o u t a s c e r t a i ng i r t h t h r o u g ha n a l y z i n gt h et i m ec o m p l e x i t ya n ds i m u l a t i o n ，a l le f f e c t i v e i m p l e m e n t a t i o nm e t h o da l ep r o p o s e d ，w h i c ha r ef i tf o rt h eo r i # h a la l g o r i t h m w h e n d e c o d i n g , t h ed a t am u s tb cs y n c h r o n i z e d h e r e m s e q u e n c ei su s e db e f o r et h ef r a m e l o c a l m s e q u e n c ec o r r e l a t e sw i t hi n f o r m a t i o nf r o mt h ec h a n n e lw h i c hi sn o th a r d d e c i d e d ( n a m e l ys o f tc o r r e l a t i o n ) t h e nc o m p a r et h ec o r r e l a t i o nv a l u ew i t ht h r e s h o l d , w h i c hc a l ld e c i d ew h e t h e ri n f o r m a t i o ni ss y n c h r o n i z e d w h e nt h ep r o b a b i l i t ys u mo f f a l s es y n c h r o n i z a t i o na n dm i s s e ds y n c h r o n i z a t i o ni sm i n i m i z e d t h et h r e s h o l dw i l lb e d e c i d e d t h es i m u l a t i o ni sg i v e nt o o b e s i d e sa b o v ec o n t e n t s ，a ne x a m p l ei sg i v e nt o e x p l a i nt h et h e o r yo fs u m p r o d u c ta l g o r i t h m t h et h e o r yo fd e n s i t ye v o l u t i o ni s d e s c r i b e dt o o 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 s f g p as y n c h r o n i z a t i o n 创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个 人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特 别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰 写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 日期： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期问论文工作的知识产权单位属西安电子科技大学。本 人保证毕业离校后，发表论文和使用论文工作成果时署名单位仍然为西安电 子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校 可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复印手段 保存论文。同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律 署名单位为西安电子科技大学。( 保密的论文在解密后遵循此规定) 本人签名： 导师签名： 日期 日期。磁z ：龌_ 第一章绪论 第一章绪论 本章简要介绍了数字通信与信道编码的关系，回顾了信道编码理论；概述了 l i ) p c 码的历史和现状；最后总结了作者在攻读硕士期间所做的主要工作并给出了 本文内容安排 1 1 数字通信与信道编码 通信系统旨在将信息由信源高效、可靠、有时还需安全地传送到信宿。有扰 通信信道的噪声会对传输信息产生干扰，从而可能降低通信可靠性。所以，通信 系统设计的中心问题是在随机噪声干扰下如何有效而可靠地传输信息在数字通 信系统中可靠与快速往往是一对矛盾。若要求快速，必然使每个数据码元所占用 的时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误的可能性增加， 传送信息的可靠性减低。若要求可靠，则使得传送消息的速率变慢。因此，如何 较合理地解决可靠性与速度这一对矛盾，是正确设计一个通信系统的关键问题之 一。 数字通信系统的可靠性用错误比特率( b e r ) 衡量，有效性用传输速率衡量。 早期的人们普遍认为：通信系统的可靠性与有效性是一对不可调和的矛盾，在有 扰通信信道上实现任意小错误概率的信息传输的唯一途径就是把传输速率降低至 零i n 。s h a n n o n 信息和编码理论的奠基性论文“通信的数学理论1 2 j ”于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 1 。一 般的通信系统均可以用图1 1 来表示。如上图所示，发送端包含四个模块：信源、 信源编码、信道编码和数字调制器。 信源编码就是用二进制( 或多进制) 序列来表示信源输出的过程，其目的是 除去信源的冗余以减少通信负担，因而也称为数据压缩。任何信源都有一个被称 为信源熵的量，它表征了信源的平均不确定程度。信源编码定理【4 】指出信源熵是 数据压缩的下界；信道编码与信源编码正相反，它通过在信息序列中引入冗余来 实现通信的可靠性，任何信道都存在一个被称为信道容量的值，它表征了信道的 传输能力；数字调制就是将信息序列映射成适合信道传输的信号的过程。对应地 在接收端也有相应的四个模块用于实现相反的过程。 综上所述，信道编码是解决通信有效性和可靠性这对矛盾的关键，也是实现 2 低密度奇偶校验码编译码原理及实现 通信系统经济性所必需的。但是，s h a n n o n 在 2 l q a 关于信道编码定理的证明是存 在性的，因而如何在实际系统中实现信道编码仍然是一个难题 蝴 ( ! 到调制信道 编码信道 图1 1 数字通信系统的模型 1 2 信道编码定理和s h a n n o n 限 1 2 1 信道编码定理 信道编码定理和信源编码定理、率失真理论一起构成了s h a n n o n 三大编码定 理。s h a n n o n 在证明上述信道编码定理时的三个条件： 编码采用了随机编码思想； 让码长趋于无穷； 译码采用了最大似然译码。 1 ) 、2 ) 使得码本身具有卓越的纠错性能，而3 ) 中的最大似然译码使得码的纠 错性能得以从分发挥。但是，采用随机编码，使码长趋于无穷大并且采用最大似 然译码将会使系统的复杂度和延时变得太大，因而无法在实际中使用。 每个信道具有确定的信道容量c ，对任何小于c 的码率r ，存在有速率为r 码长为n 的分组码及( n o ，k o ，m ) 卷积码，若用最大似然译码，则随着码长的增 加其译码错误概率p 可任意d d 4 j ，即 ps a n e 峨“ ) p 4 e 州m 砷- a c e 一“ ( 1 劲 式中，4 和4 为大于0 的系数，毛俾) 和匪( r ) 为正实函数，称为误差指数。 通过增加信道容量c ，从而使( r ) 增加；在r 一定的情况下，增加分组码长 n ；这两种方法都可以使p 指数下降。 任意离散输入无记忆平稳有噪信道都有一个被称为信道容量的值c ，它标志 着信道传输能力的上限，只要信息传输速率r c ，就存在一种编码方式，当平 第一章绪论 均码长足够大时，译码错误概率可以做到任意小；反之，则无论采用何种编码方 式也不可能保证错误概率任意小 1 2 2s h a n n o n 限 3 1 9 4 8 年s h a n n o n 在【2 】推导了波形信道在加性高斯白噪声下的信道容量： “l 0 9 2 【l + 最卜 式中矽是信道带宽，是信号的平均功率，n o 是噪声的单边功率谱密度，c 是信道容量( 单位为b i t s ) 。在数字通信系统中，& 是每信息比特需要的传输能 量。 参- l 0 9 2 ( 1 + 谚c 刍n o e b 2 c 怿一1 n nc | w 惫- 船等- 1 n 2 - - 1 鲫 毛o ，一1 6 d b 就可以实现高斯白噪声信道下的无误传输。这是带宽无限高 斯白噪声信道的极限传输能力，称为s h a n n o n 限。 1 3 l d p c 码的历史和现状 l d p c 码最早出现于1 9 6 2 年g a l l a g c r 提出的二元规则l d p c 码1 5 j ，它可看作 一个具有稀疏校验矩阵( 校验矩阵中“1 ”的数量很少) 的线性分组码。当l d p c 码的校验矩阵的行和列中“1 ”的数目分别固定为c 和r 时，被称为规则( f ，c ) l d p c 码，否则称为非规则l d p c 码【6 】。g a l l a g e r 证明了l d p c 码具有很好的汉明距离 特性，是具有渐进特性的好码，但由于计算工具的缺乏，l d p c 码一度被认为是 一种不实用码，在很长的一段时间内没有受到人们的重视。 1 9 8 1 年t a n n e r 重新研究了l d p c 码，使用图的形式表示了校验码的约束关 系，并证明g a l l a g e r 的译码算法与l d p c 码对应二步图中的环有关。在无环图的 基础上给出了证明了最小和算法等价于最大似然译码，和积算法实现了最小符号 错误概率的最大边界后验概率算法。 w i b e r g 等结合对t u r b o 码和网格的研究，把t a n n e r 图推广到具有隐含状态变 4 低密度奇偶校验码编译码原理及实现 量的码图( w i b e r g 图) 上，使网格型结构作为其特殊情况，从而使消息传递算法包 容了v a ( v i t e r b ia l g 嘣t h m ) 【4 】等基于网格的译码算法。他们的图模型还允许使用更 一般性的量度( m e t r i c ) 作为成本函数，从而适用于非均匀先验概率分布模型或有记 忆信道模型。他们证明：最小和算法是v a 算法的直接推广，和积算法是b c j r 算法的直接推广。v a 算法、s o v a 算法、b c j r 算法、g a l l a g e r 计算树译码算法 等，都认为是基于t a n n e r 图模型的消息传递算法的特例1 7 】l 引。 对于码的构造，g a l l a g e r 5 1 给出了最初的l d p c 的构造方法。在这个基础上， 人们对码的构造进行了很多的研究。部分研究如下： 1 ) 【9 】给出了离s h a n n o n 限只有0 0 0 4 5 d b 的l d p c 码，是目前得到的最接近 s h a n n o n 限的码。由于是随机构造，实现起来并不容易。 t o r n a d o 码【1 0 l ，重复累积码 1 1 1 1 1 2 1 ，这些码都具有线性的编码复杂度，容易 实现快速编码。通过对这些码结构的变形，又产生出其他的快速编码方式。 3 ) 【1 3 1 i 正明了具有优化度序列分布、无限码长的非规则l d p c 的性能可以逼 近s h a n n o n 限。 4 ) 【1 4 1 指出对于码长较短的l d p c 码，其t a n n e r 的连接特性和扩展性以及图 中环长及分布都是影响码性能的重要因素。， 5 ) 【1 5 1 中给出了使用t a n n e r 图来构造最大围长的校验矩阵的方法，即：p e g 方法。林舒提出在r s 码的基础上构造u ) p c 的到了很低的错误平层。 6 ) 【1 6 t a n n e r 利用q c - l d p c 码的循坏矩阵构造了l d p c 卷积码，中短码长 时性能与随机构造的规则码相当，长码略差于随机构造的码。 1 4 本文的主要研究工作和内容安排 作者采用理论分析和计算机仿真相结合的方法，对低密度校验码的理论和应 用中的问题进行了深入研究。全文共分四章，具体安排如下： 第一章回顾了信道编码理论与技术的发展历程；第二章系统地阐述了低密度 校验码基于图模型的译码原理；第三章针对l d p c 码消围长的算法复杂度进行了 分析；第四章针对i e e e 8 0 2 1 6 e 中的l d p c 码结构进行了描述，并对其编码结构 使用f p g a 进行了实现：第五章对l d p c 码密度进化理论的基本思想进行了描述。 第六章针对实际使用中的帧同步问题进行了研究，使用软相关的方法对相关的最 佳门限进行了确定。 第二章l d p c 码译码原理 第二章l d p c 码译码原理 本章对l d p c 码的译码原理使用简单的例子进行了说明，并在网格图的基础上 对和积译码方法进行了证明并对和积译码算法和最小和算法进行了比较 2 1l d p c 码的译码原理n 力 l d p c 码的译码是建立在校验矩阵的基础之上的。通过校验矩阵建立网格图 来对接收到的信息进行译码。下面针对于单校验码的译码进行说明。 2 1 1 信息传递的基本概念 一在l d p c 码进行译码的时候使用了信息传递，下面针对信息传递进行一个说 明。假如一群士兵排成一列，要想知道所有士兵的数目，可以使用以下的规则： 当堡丛苤二倒担蝤基馒塑= 仝数目盟：整运仝錾目加二告翅星二倒的担蟾基： 筮达耋推。从这个规则可以知道士兵从某侧得到的数字其实就是这一侧士兵的个 数。可以使用图2 1 士兵队列图进行解释： 图2 1 士兵队列图( 内信息i n t r i n s i ci n f o r m a t i o n ) 初始时，每个士兵都知道至少有一个士兵( 自己，称作：内信息) ，如：图 2 1 。接下来，最右边和最左边的士兵把这个1 ，即：内信息告诉他的相临士兵。 而相临士兵都把这个信息加1 后传给下一个士兵。 图2 2 报数后的信息传递( 外信息e x t r i n s i ci n f o r m a t i o n ) 图2 2 给出了报数后的信息传递情况。对于每一个士兵通过得到的两边的外 信息和自身的内信息，就可以得到整个队列的信息( o v e r a l li n f o r m a t i o n ) 。图2 3 5 6 低密度奇偶校验码编译码原理及实现 给出了全局信息传递过程。即：全局信息( o v e r a l li n f o r m a t i o n ) 为内信息( i n t r i n s i c i n f o r m a t i o n ) 与外信息( e x t r i n s i ci n f o r m a t i o n ) 之和。 图2 3 全局信息传递( o v e r a l li n f o r m a t i o n ) 2 1 2 使用t a n n e r 图进行译码 6 l d p c 码使用校验矩阵进行译码。h 矩阵的每一行可以看作一个单校验码。 每一列可以看作一个重复累计码【1 7 1 。 ( 一) 对于h 矩阵的某一行，假如有no 册：o 鸭一0 。图2 4 表示h 矩阵 中该行对应得t a n n e r 图。 a m 2m 3 图2 4h 矩阵某一行对应的t a n n e r 图 啊为0 的概率为圪，为1 的概率为墨。；m ：为0 的概率为，为1 的概率为只l ； 鸭为0 的概率为，为1 的概率为弓，。表2 1 单校验码满足条件的码字概率有 四个。 表2 1 单校验码满足条件码字概率 ，啊m 2鸭 概率 ooo 曷。只0 & 一日 t n 。0 l 01 只。岛只。一乓 o l1 号。昱l e 3 1 一岛 阮一1 l lo 号。只。& 一焉 第二章l d p c 码译码原理 可以得到一糟，一揣。而a ，+ a l 尉a 3 卺， p a l - 争，只。i l i 。1 表示的全信息，k l j 表示m z 的外信息对于、鸭同 样可以得到外信息和内信息的1 、0 概率比。 ( 二) 对于h 矩阵的每一列( 即对应于每一个变量节点，这里假定每个变量 节点参与了三个校验方程) ，对应于三个校验方程的三个变量节点满足 t n l 朋2 - r f f 3 。图2 5 表示了该列对应得t a n n e r 图。 a 图2 5h 矩阵某一列对应的t a n n e r 图 同样假定，1 1 为0 的概率为，为1 的概率为最。；m ：为0 的概率为，为1 的 概率为罡，；为0 的概率为& ，为1 的概率为弓，。满足重复累积码关系得码字 有表2 2 的两个。可以得到 只。、。釜墨l 。a ，a ，其中a ，。墨，a ，。生。 矿嚣l a 3 濮叭，蔷a i 。薏1 0 。4 1 0 1 加加 对于啊、鸭同样可以得到外信息的1 、0 概率比。 表2 2 重复累积码满足条件的码字概率 嬲2 掰3 概率 o o o 只。民民 ll1 e 。最，b ， 从而得到了和积译码算法。 7 8 低密度奇偶校验码编译码原理及实现 2 2 基于网格图的l d p c 码译码方法 对于l d p c 码校验矩阵的每一行可以看作一个单校验码，每行的译码就是为 了得到每个b “的外信息。从而可知每个单校验码都可以使用两状态的网格图来 表示。下面针对不同的测度方法对单校验码的译码进行说明，并给出各种方法之 间的关系。 2 2 1 置信传输的因子图表示及几种概率测度“8 1 根据2 1 节的描述，l d p c 码可以根据校验矩阵构造t a n n g 图，并在t a n n e r 图的基础上进行译码。如图2 6 所示的置信传输译码的因子图。 | ：程 图2 6 置信传播译码网格的因子图 图2 6 中所有变量节点为父亲节点，其邻节点为孩子节点。通过2 1 节中的 分析，可以得到基本传递消息的过程。群是节点向而节点传递的校验消息，饼 是x ，节点向节点传递的变量消息，群和娣是外信息。用贝叶斯网络术语，群 表示t 根据其他父亲 t ：七一，k e n q ) 当前状态向石，宣称的“x ，一口使满足 的”的可信度，q ；表示石，根据其他孩子包括z 和 ：七- f ，七m ( ，) ) 向t 宣称 的“x ，一a ”的可信度。按照t u r b o 原理，每个局部约束z ；视为一个子码，这时群 也称为子码五产生的外信息。 对于二元输入信道中，对码符号u o 1 和信道输入符号h 扎一1 的讨论 是等价的，因此我们在下文中不致混淆时。设一个二元随机变量的概率分布率由 ( p 。p 一，) 或( 岛，见) 等价表示，下面式子定义了似然t c 0 - r ) 、对数似然比( u 且) 和 概率差三种量度1 1 州 ，。p 1 p _ l( 2 1 ) ( 2 2 ) 第二章l d p c 码译码原理 可以得到如下的转换公式： 印1p + l p - l v l + a p 1 一卸 知生 1 v + i 朋1 0 9 生垒 l 一印 ( 2 3 ) ( 2 - 4 ) ( 2 - 5 ) ( 2 6 ) 印等itanhm_(2-7)e1 2 4 糟+ 其中t a n l l 争一1 ) 舻+ 1 ) 2 2 2 基于概率测度的和积算法n 町 根据2 2 1 中的表示，在概率测度下，变量消息和校验消息分别定义为 瑶- p 嘶- 口i 乃， ：七”( ，) f ) 和碍- p ( 弓l t 一4 ) 嘲。对两者进行如下的推 导： q；一pg，-口ly，tz。：七肘c，、r，)一!i；ii：iii；i器 p o j 一口i y j ) p ( z t ：k e m ( j ) i ) | y ，石j 一口) 。1 磊i 函丽而万一 弛枇讹。：k e m ( j ) i ) l x ，叫雌，叫p ，四k ，卅) p ( 瓴：七 f ( ，) i )p ( 口。：k m ( ，) 、f ) 嘞f 几磁 ( 2 - 8 ) 彤一p ( z 。i x ，一口) 一p ( z z ，x l x ，- a ) - p ( z ，i x j n ，x ) p ( x i x ，一口) - 。器也i j ) p ( 工i 驴口) i ，：黟l j 谰黔) - ，：黔厕尹 ( 2 。9 ) 其中式( 2 8 ) 中，为归一化常数，碍是从上一次迭代中传递来的函数消息， 首次迭代时为初始值。式( 2 - 9 ) 中，尸瓴) 是指特定求和组合z 中各分量取相应值 9 1 0 低密度奇偶校验码编译码原理及实现 的概率，显然，群是一个似然概率。用于逐符号判决的最终变量消息为 彰。口疗觇，喵( 2 - 1 0 ) 其中，a 为归一化因子。相应的判决准则是 膏，一a r g m a x q ； ( 2 1 1 ) 【+ l 一1 状态0 1 b i - bj - l ，x i ，s 图2 7 检验约束的状态图 若码字均匀分布，式( 2 9 ) 中p 纯lx ) 替换为局部指示函数z ( 伽，：，( f ) ) ， 表示校验约束弓只对码字x 局部进行约束。 若码字非均匀分布，假设码字概率分布为p ( x ) ，其中x c ，一般地p 瓴ix ) 计算如下 p ( ix ) 一f ( 协，：，u ) ) 尸g ) ( 2 1 2 ) 霖 上述各式中，我们限定五一0 ，表示满足校验约束；( f ) ，表示从n q ) 中去 掉，后的子集，m ( ，) f 从j i f ( ，) 中去掉f 后的子集。消息修正公式是基于无环有向 树结构推导的，即变量节点之间相互统计独立，函数节点之间也相互统计独立。 为实施有效计算，下面基于状态图对式( 2 - 9 ) 进行简化。设一个度数为d 。的校 验节点z 具有父亲变量节点集 墨，瓢 ，考虑节点z 向节点。传递消息。校验 约束关系可以用一个如图2 7 所示的有限状态s t ( f s m 3 描述。这是一个状态空问为 g f ( 2 ) 的一阶马尔可夫( m a r k o v ) 源，初始和终止状态均为零状态，g f ( 2 ) 上的部 分校验和为转移状态s ，一s 一+ _ t ：。以。 用3 重组q o ，。，一，s ，) b 对转移分支进行标识，显然一+ s ，。，且有 j b l 一4 。分支概率 p ( q ) 一p q ，ls 4 ) = p ( x j s ，一s 卜1 ) 对状态屯，我们有 e ( s 2 0 ) 。p ( b - 0 ) p ( j r 2 - 0 ) + 尸( h 一1 ) e ( x z ；1 ) e ( s 2 1 ) - p 瓴一o ) p ( 而一1 ) + p “1 1 ) p 沁。o ) 第二章u ) p c 码译码原理 1 1 冥概率差为 p ( s 2 - o 一，( 如- 1 ) 一( p ( 鼍一o ) - p “- 1 ) ) ( p ( j 乞一o ) 一p ( x 2 - 1 ) ) 经过有限归纳，对任意时刻七仉2 ，吃一1 ，得叫& ) 一丌：。a e ( z j ) 不同时刻的一对状态& 和岛 一cf ) 之间一条路径的路径值为其所含分支概率 测度值的乘积。满足局部校验约束z 的任意一组配置 ，必然对应图上 一条有效路径，且应该有一。式( 2 - 9 ) 则表示所有蠢一0 的有效路径值之和 或者所有- 1 的有效路径值之和。根据以上推导，得 p 心) = p 魄一t ) _ 兀：= l a p q ) ( 2 1 3 ) ( 2 1 4 ) 式( 2 - 9 ) 重新写为 蝇。飘，玩 ( 2 - 1 5 ) i 目，西、j 为了满足式( 2 - 8 ) 的计算要求，需要做中间变换弼一( 1 + 峨) 2 和碍一l 一碍 2 2 3 基于似然比度量的和积算法“阳 f 向给出似然比度量： y ii | f 1 一e x p 2 y 。| s 3 p 1 6 ) y 口- 碍噶一o + a r ；, ) 0 - a a o ) ( 2 一1 7 ) 巧。嬲俺嘶飒。( 2 - 1 8 ) 为保证式( 二1 5 ) 的计算，需要做中间变换a 岛- ( 嘞一1 ) ( + 1 ) 。最终消息定 义为： v 堪泄飞：n 2 2 4 基于对数似然比度量的和积算法“耵 ( 2 - 1 9 ) 对数似然比量度的初始消息、校验消息和变量消息分别定义为，i l ll o g ( r ) 、 对甜 一 一 嘭 - 峨 锡 令 以所 低密度奇偶校验码编译码原理及实现 i l o g ( r “) 、l o g ( ) 。根据以上定义，的初始值为0 ，判决规则为 t = n 0 】。 h i 一2 y l | s ： ，咄，+ 三，材 ( 2 2 0 ) 但- 2 1 ) t 卸h - 取t a 曲( 等) 蚴， ”l o 蚓- l o g ( 霹- l o g 错) 峨- 鲁一取，岈篙一取，薯一而e u o - 1 一。飘，瓦e t m - 1 篙一风、，而e ” j - 1t 篙阱鼠t 姐n ( 等) 2 2 5t d m p ( t u r b o - d e c o d i n gm e s s a g e - p a s s i n g ) 算法 t d m p l l 9 j 【2 0 】算法将l d p c 码的校验矩阵每一行看作子码。使用t u r b o 码的译 码方法，使用两相图得到每个信息比特的外信息值1 2 1 l 。在纵向，逐次修改每个比 特的全信息，进行判决。 状态0 1 图2 8 b c j r 影射网格图 o t ：一l o g ( e 1 + + e 。+ 屯) 一。l o g ( e + + e t h + , h ) a ：一l o g ( e + 护“) 疋- i o g ( e + 屯+ e 6 + 1 ) ( 2 - 2 3 ) ( 2 2 4 ) ai l n ( e q + + e “z + 岛) 一i n ( e a , + 以+ e 屯+ 岛) ( 2 2 5 ) 这里九一 是变量节点传递到校验节点的全信息，a 是校验节点传递到变量 节点的外信息【2 。使用a a q 一口：，a , a l i e 届一岛。对于( 2 2 3 ) 可以转化为： 第二章l d p c 码译码原理 1 3 a a _ l n ( 1 + e “+ 从) 一l n ( e “+ e 4 l a ) 。这里使用了关键的方程：( x ，y ) - i n ( e + e ) 【2 2 】对， ，y ) 进行了近似，( x ，_ ) ，) m a x ( x , y ) + i n o + e 十一7 0 ) 一m a x ( z ，) ，) + 6 0 y ) ， 这里6 一y ) - m a x ( 5 8 一i 并i 4 ，o ) 。 2 2 6 最小和算法纠埘 通过上面各小节的描述，可以知道和积译码方法中的单校验码在求解各个变 量节点的外信息时使用的是所有可能路径。而最小和算法在网格图上只挑选一条 最可能的有效路径。最小和算法则认为是退化的和积算法，其性能更差一些。这 一点在以误比特率( b e r ) 评价码的性能时，尤为明显。 考虑一个度数为3 的校验节点，令( p 5 l ，p 1 ) ) 和( p 5 2 ) ，p ：2 ) 是两个输入概率分 布，输出概率分布( p o ，a ) 由下式给出： p o 一口m a x ( p o ( 1 砖”，d ”西2 ) ( 2 2 6 ) p 1 一口m a 】【( 甜矗”，硝1 硝) ( 2 2 7 ) 其中，口是归一化因子。 因此，最小和算法也称为最大乘积算法( m a x p r o d u c t ) 。令h 、吃和分别表 示上述输入、输出概率测度的对数似然比量度消息，有 “一器黼一地器一蜘哪一毗， v 2 ，b i v 2i - - v 2 ，v i g l - - i i v 2l 。s g l l “) s g i l ( v z ) m i n 毗l ，k 1 ) ， u ，i 2 爿v 1i h ，v 2 一i h i 其中，s g n ( x ) 是正负符号函数，当算0 时，s g n ( x ) 一1 ；否则s 鲈o ) - - 1 a 若一个校验节点的度数为d2 ，输入对数似然比消息为c 2 p ，：，一1 ，d c 一玲，则输出消息“必然等于2 4 1 “一肘d “，一1 )(2e-iv 2 2 8 ) 【2 4 1 q 。给出了原始的最小和算法，使用局部节点成本( 1 0 c a ls i t e sc o s t ) 和全局成 本( g l o b a lc o s t ) 对算法进行描述。定义全局成本： 。磊r 魄) + 荟以 在典型的信道译码环境下，局部校验节点成本y 。) 是一个0 的集合，局部变量 节点成本y ，( t ) 一一l o g p ( y ，l ) 。所以最大似然译码在这里可以看作寻找最佳的 1 4 低密度奇偶校验码编译码原理及实现 x 的配置是全局成本g o ) 最小。在无环情况下，最小和算法可以使全局成本最小。 定义检验节点成本 r ( x d 一- l o g p ( x ) - ( x d g o ) - - l o g p o ) 一l o g p ( ) ，i 并) 一- l o g p o i y ) 一l o g p ( y ) 。 可见最小化成本等价于最大化后验概率。 对( 2 2 6 ) 、( 2 2 7 ) 进行变形可得： p o 。口l i i i n ( _ 甄1 万，蒯1 ( 2 - 2 9 ) 伽协斋鬲秽( 2 - 3 0 ) 对( 2 2 9 ) 、( 2 - 3 0 ) 求对数可得 p o - m i n ( - i o g ( p o a p o , 2 ) ，一l o g ( p t l 硝2 ) ) a 一口r a i n ( - l o g ( p 0 0 硝2 ) ，一l o g ( p = 1 p 5 2 ” 所以最小和算法也称为最大乘积算法。 同理，如果使用上面几个小节中的全信息量进行推倒，如下： 川o s 鬻高謦_ 1 0 9 筹- 】o g ) - l 嘶) ( 2 。1 ) 使用( x ，y ) 一m a ) 【 ，y ) + l n ( 1 + e + 一7 0 ) ，m a x ( x ，y ) + 6 0 y ) 进行近似计算，不 考虑a ( x - y ) 这个修正量时有：u m a x ( v 1 + v 2 ，1 ) 一m a x ( v i ，v 2 ) 。可见和积译码算 法与使用最小和算法之间的差别。 2 3 小结 本章对l d p c 码的译码方法进行了推导。通过算法的比较，可知l d p c 码译 码方法可以从两个方面进行变形处理。横向，对单检码的译码进行一定的简化( 降 低复杂度) ；纵向，单检码之间可以使用不同的信息传递机制( 得到不同的收敛速 度) 。这为后面章节中译码的实现奠定了基础。 第三章l d p c 码的消环构造 第三章l d p c 码的消环构造 1 5 这一章主要描述了p e g 算法在消确定围长中的应用并对几种实现方法的时 间复杂度进行了分析，仿真 3 1 算法描述 p e g 算法在随机构造l d p c 码和构造准循环l d p c 码中都得到了较好的使 用，是一种高效的方法。p e g 算法是在构造过程中要求保证步步最大围长，即： 得到尽可能大的围长。实际的使用中消确定围长的构造方法也经常用到。在此对 p e g 算法进行了修改使用到了消确定围长的校验矩阵构造中。 下面给出了一些符号与定义1 1 4 1 ： l d p c 码边的度分布序列可用多项式 j：-虹de。 x ( x ) - 善 ，p ) 一荟n ， 表示。在上面定义的情况下，随机分配各个变量节点和校验节点的连边情况。记 为：皿一纸，d 。， ，d f - 魄，d 。，t ，其中矗( 叱) 表示变量节点 丑( 校验节点c i ) 的连边个数。 变量节点集合为k p ：，”1 ，0 4 ，同样校验节点的集合为 k - 嚣，c o ”1 ，0 。c 鲁”1 变量节点所有的连边集合为 e 一毛u 毛u u & _ l 其中毛一蠼，0 k 一1 表示所有与变量节点墨相连 的边构成的集合，磋为第k 个边。彬，表示为从变量节点s 。延伸的深度为z 的子树 所连接的校验节点集合，n 。i - k ；表示校验节点集k 中除去蜕后剩余的集 合。 在当| j 连边的情况( d 下，如果有校验节点连接的变量节点的个数达到了该 校验节点可连接的最大数，那么这些校验节点的集合用，表示，这里称这些校验 节点为永不可用点。一k 、。，表示在当前连边的情况( 目下，以后的分配中变 量节点可以连接的校验节点的集合。 1 6 低密度奇偶校验码编译码原理及实现 图3 1p e g 算法拓展树 如图3 1 所示，令当前所要生成的校验矩阵要满足消掉g 围长。那么对于任 意一个变量节点s ；来说，所连接的校验节点2 ，不能是从校验节点1 延伸出的 f 。g 2 1 深度的予树所连接的校验节点，即要在集合虬n 彬中，进行选取。 这里使用了随机的选取集合瓦n 川中的验节点为连接校验节点2 时的可用校验 节点。使用q 表示集合。n 叫的势。 下面给出消确定围长的p e g 算法： f o r j = o t o 玎一1d o b e g i n f o r k = 0 t o d l i 一1 d o b e g i n i f