（微电子学与固体电子学专业论文）ldpc码算法研究与asic实现.pdf

摘要 现代编码技术的终极目标是以逼近s h a n n o n 限的有效功耗实现可靠通信，低 密度奇偶校验码l d p c 码的诞生和发展使人们更加接近这一目标。研究结果表明， 采用迭代的概率译码算法，l d p c 码可以达到接近香农极限的性能。本论文主要对 l d p c 码的译码算法和硬件实现进行了较深入的研究。 文章深入研究了g a l l a g e r 的b f 算法、可信度传播( b p ) 算法、最小和算法及最 小和算法的改进算法；推导了硬判决算法译码流程，讨论了不同测度下l d p c 码 和积译码算法的消息迭代更新公式。然后给出了最小和译码算法及其两种修正算 法；为应用于a s i c 实现的算法提供了理论依据。 论文对l d p c 码译码器硬件实现的全并行结构、全串行结构、串并结合结构 ( 部分并行) 进行了重点研究了，给出了基于基本校验矩阵，采用最小和算法的 a s i c 实现结构；解读了基于国家数字电视地面广播传输系统帧结构、信道编码 和调制标准中的校验矩阵的特征，并且给出了0 6 码率下功能模块v n u ，c n u 的a s i c 实现结构。 关键词：l d p c 码迭代译码最小和算法a s i c 实现结构 a b s t r a c t a c h i e v i n gr e l i a b l ec o m m u n i c a t i o na p p r o a c h i n gs h a n n o n sc a p a c i t yl i m i ta te f f e c t i v e p o w e rc o s ti st h eu l t i m a t eo b j e c to fm o d e mc h a n n e lc o d i n gt e c h n i q u e t h ei n v e n t i o n a n dd e v e l o p m e n to fl o w - d e n s i t yp a r i t y - c h e c kc o d e s ( l d p c ) n a r r o wt h eg a pb e t w e e n r e a l s y s t e mp e r f o r m a n c ea n dc h a n n e lc a p a c i t y s i n c et h e i rr e d i s c o v e r y , d e s i g n ， c o n s t r u c t i o n ，d e c o d i n g ，a n a l y s i sa n da p p l i c a t i o n so fl d p cc o d e dh a v eb e c o m ef o c a l p o i n t so fr e s e a r c h i nt h i sp a p e r , m a i n l yo nt h el d p cc o d ed e c o d i n ga l g o r i t h ma n d a s i ci m p l e m e n t a t i o nt oa c h i e v em o r ei n d e p t hs t u d i e s s e v e r a li t e r a t i v e m e s s a g ep a s s i n ga l g o r i t h m s f o rl d p cc o d e s ，s u c ha s g a l l a g e r s b i tf l i p p i n g ( b f ) a l g o r i t h m ，b 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 ma n d m i n - s u n la l g o r i t h me t e ，a lec o n s i d e r e di nt h i st h e s i s t h ep r i n c i p l e so fc o d i n ga n d d e c o d i n ga l g o r i t h mf o rl d p cc o d e sa r es y s t e m a t i c a l l ys u m m a r i z e da n dt h ee q u a t i o n s f o ru p d a t i n gm e s s a g e si ns u m p r o d u c ta l g o r i t h ma r ea l s od e r i v e d a l g o r i t h mf o ra s i c i m p l e m e n t a t i o np r o v i d e sat h e o r e t i c a lb a s i s e v e n t u a l l y , t h ea r c h i t e c t u r e sf o rt h eh a r d w a r ei m p l e m e n t a t i o no fl d p cd e c o d e r , i n c l u d i n gf u l lp a r a l l e la r c h i t e c t u r e ，s e r i a la r c h i t e c t u r ea n dp a r t l yp a r a l l e la r c h i t e c t u r e ， h a v eb e e na n a l y z e d e l a b o r a t e dt h ea s i cs t r u c t u r eb a s e do nf u n d a m e n t a lm a t r i x s m i n s u ma l g o r i t h m a d d i t i o n a l l y , b a s e do nn a t i o n a ls t a n d a r d ( g b ) ，f r a m i n gs t r u c t u r e ， c h a n n e lc o d i n ga n dm o d u l a t i o nf o rd i 酉t a lt e l e v i s i o nt e r r e s t r i a lb r o a d c a s t i n gs y s t e m ， w ep r o p o s e dt h ea s i cs t r u c t u r eo f v n ua n dc n uv i a0 6r a t e s 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 kc o d e s s u m - p r o d u c ta l g o r i t h m m i n s u ma l g o r i t h ma s i cs t r u c t u r e 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：i 笙色些日期型! ：! j 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 日期坐! ： 日期鲨塑! ! ! 芝 第一章绪论 第一章绪论 1 1 数字通信系统的组成及信道模型 1 9 4 8 年s h a n n o n 在贝尔技术杂志上发表的题为通信的数学理论【l l 文， 奠定了现代通信系统设计的理论基础。通信的目的是要把对方不知道的消息及时 可靠地( 有时还须秘密地) 传送给对方。这要求通信系统传输消息必须可靠与快 速，而在数字通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使得 每个数据码元所占的时间缩短、波形变窄、能量减少，从而在受到干扰后产生错 误的可能性增加，传送消息的可靠性减低。若要求可靠，则传送消息的速率必须 变慢。因此，如何较合理地解决可靠性与速度这一对矛盾，是正确设计一个通信 系统关键问题之一。通信理论本身( 包括纠错码) 也正是在解决这对矛盾中不断发展 起来的。 所有的数字通信系统如通信、雷达、遥控遥测、数字计算机的存储系统和内 部运算以及数字计算机之间的数据传输等，都可归结为如图1 1 所示的模型。 编码信道 图1 1 数字通信系统框图 图中，信源编码器把信源发出的消息如语言、图像、文字等转换为二进制( 也 可转换为多进制) 形式的信息序列，并且为了提高传输效率，还去掉了一些与传 输信息无关的多余度；e c c 信道编码器按照某种特定编码方法向信息序列添加冗 余，得到纠错码字，抵抗信道中的噪声和干扰，保证系统的可靠性：码字通过数 字调制器调制成波形信号，送到物理信道。受到噪声干扰的信号经过数字解调器、 2 两安电子科技大学硕士学位论文l d p c 码算法研究及a s i c 实现 e c c 译码器和信源译码器变成对信源信息的估计到达信宿。通信系统设计的中心 问题是在随机噪声的干扰下如何有效而又可靠的传送信息，实现这一目标的途径 就是信道编码【2 州。信道编码定理给出了信道编码研究的指导性原则，是s h a n n o n 信息论的一大贡献。 1 2 1信道编码理论 1 2 信道编码理论及其发展 关于信道编码定理，最初的一些年人们认为它只是一个存在性的证明，无法 指导实用码构造。这是因为s h a n n o n 和g a l l a g c r 在信道编码定理证明过程中均给 出了三个重要的假设【1 】【2 1 ：采用随机编码方式，码长趋于无穷大，译码采用最佳的 最大后验概率或等价表达式译码。一般地，相对而言，设计简单而有效的译码算 法要比编码困难的多。为了逼近信道容量，码长无限增加，导致系统的无限时延 和无限复杂度，直至不能物理实现。香农信道编码定理肯定了逼近香农限的编码 方案的存在，但并未说明如何找到符合要求的编码方案。根据纠错性能的好坏， 一般可将纠错码分为好码和坏码。所谓坏码是指只有将码率降至零才能使误码率 任意小的编码方式；而好码又可以分为当误码率任意小时，码率逼近信道容量的 非常好码，和码率可以达到某个非零最大值却小于信道容量的一般好码。虽然香 农指出一个随机选择的码以很高的概率为好码，但随机码的最大似然译码的复杂 度往往与码长呈指数关系，即在误码率随码长趋于无穷而趋向于零的同时，译码 复杂度以指数增长，而在实际应用中，只能够使用以码长多项式的时间和空间复 杂度内完成编译码的纠错码，因而尽管一般的随机码是好码，但不能看作是实用 码。 1 2 2信道编码理论的发展 自信道编码理论提出以来，如何构造一个逼近信道容量限的实用好码成了众 多学者竞相研究的课题，并逐渐形成信息论的一个重要分支一一信道编码理论。 五十多年来，人们构造实用好码的探索基本上是按照香农所提出的基本条件的后 两条为主线展开的。虽然从理论上讲，除了目前已知的码外，几乎所有的码都是 好码，但到目前为止，离构造出真正意义上的实用好码还有较长的距离。虽然如 此，通过众多学者，特别是有关数字和信息论学术界的研究人员五十多年的共同 努力，目前已经取得了很多成果。 纠错码从构造方法上可分为分组码和卷积码两大类。在分组码方面，第一个 分组码是1 9 5 0 年发现的能纠正单个错误的汉明( h a m m i n g ) 码。1 9 5 0 年汉明 第一章绪论 3 ( h a m m i n grw ) 发表的论文检错码与纠错码【9 】是开拓编码理论研究的第一篇论 文。这篇论文主要考虑在大型计算机中如何纠正所出现的单个错误。 在整个5 0 年代，基于代数理论又发现了短码长的分组码，如1 9 5 4 年g o l a y 发现的g o l a y 码以及r e e d 和m u l l e r 发现的r m 码，1 9 5 7 年p r a n g e 发现的循环码 等。从能够纠正单个错误的汉明码过渡到能够纠正多个错误的所谓b c h 码，整整 经历了1 0 年的时间。因此，可以说2 0 世纪6 0 年代是代数编码理论发展的鼎盛时 期。b o s e 和c h a u d h u r i r 在1 9 6 0 年以及h o c u e n g h e n l 在1 9 5 9 年分别独立发现了能 纠正多个错误的b c h 码，以及r e e d 和s o l o m o n 在1 9 6 0 年发现了非二进制r s 码。 实际上，b c h 码可以看作是某个r s 码的子域子码，而r s 码又可以看作是b c h 码的特例。 其后发现的分组码主要有1 9 7 0 年的g o p p a 码和1 9 8 2 年发现的代数几何码。 在所有的这些分组码中，除了g o p p a 码和代数几何码存在个别达到g v 限的渐进 好码外，其它均不是好码。分组码的译码主要采用基于代数的硬判决译码。 卷积码【lu j 最早由e l i a sp 在1 9 5 5 年提出，早期被称为树码( t r e ec o d e s ) ，现在 称为格码( t r e l l i sc o d e s ) 或卷积码。1 9 6 6 年，f o m e y 将分组码和卷积码结合起来， 提出了级联码【2 2 1 ( c c ，c o n c a t e n a t e dc o d e s ) 的概念。级联码一般采用r s 码为外码， 卷积码为内码的编码方式。f o r n e y 的研究表明，级联码可以使性能得到较大改善， 但译码复杂度并不显著增加。1 9 8 2 年欧洲的u n g e r b o e c k 和日本的i m a i 分别独立 地提出具有扩展频带特性的编码与调制相结合的思想，提高了频带利用率。 1 9 5 2 年f a n orm 给出并证明了费诺不等式，还证明了香农信道编码的逆定理； 1 9 5 7 年沃尔夫维兹采用了类似典型序列的方法证明了信道编码强逆定理；1 9 6 1 年 f a n o 分析了分组码码率、码长和错误概率的关系，并提供了香农信道编码定理的 充分性证明；1 9 6 5 年g a l l a g e r rg 发展了f a n o 关于香农信道编码逆定理的证明结 论并提供了一种简明的证明方法：1 9 7 2 年a r i m o t os 和b l a h u t 分别提出了信道容 量的迭代算法。 1 9 4 8 年香农首先分析了高斯信道问题；1 9 6 4 年h o l s i n g e rjl 进行了有色高斯 噪声信道容量的研究；1 9 6 9 年p i n s k e rms 研究了具有反馈的非白噪声高斯信道容 量问题；1 9 8 9 年c o v e rtm 对p i n s k e r 的结论作出了简洁的证明。根据对接收信号 处理方式的不同，纠错码的译码可以分为硬判决译码和软判决译码。硬判决译码 是基于传统纠错码观点的译码方法，解调器首先对信道输出值进行硬判决，再将 判决结果送入译码器，译码器根据解调器的判决结果，利用码字的代数结构来纠 正其中的错误。而软判决译码则充分利用了信道输出的波形信息，解调器将匹配 滤波器输出的一个实数值送入译码器，由于实数值包含了比硬判决更多的信道信 息，译码器通过概率译码充分利用这些信息，从而获得比硬判决译码更大的编码 增益。 4 西安电子科技大学硕士学位论文id p c 码算法研究及a s i c 实现 总之，尽管随机码是理论上的好码，但由于其编码实现的困难性和无法承受 的译码复杂度而只被用作理论分析的工具。在信道编码理论和后来的许多编码理 论成果中，代数编码理论始终占据了主导地位，但传统的信道编码技术受到临界 速率( c r i t i c a lr a t e ) ，也称作截止速率( c u t o f f r a t e ) r 的限制。 信道编码定理在指导实用的编码设计上取得重大的突破是1 9 9 3 年b e r r o u 设计 的t u r b o 码【1 1 。1 3 1 ，它从真正意义上体现了信道编码定理证明中的三个重要假设：发 送端，编码器采用了伪随机交织器和并行级联结构( 如图1 2 所示) 实现其伪随机 性；接收端，采用软输入软输出的带有交织器的反馈迭代译码( 如图1 3 所示) 来逼近最大似然译码，b i a w g n ，码长在1 0 6 时离s h a n n o n 限o 5 d b 。t u r b o 码巧妙 的实现了随机编码思想，获得了很好的性能，这坚定了研究人员在工程上构造最 优码上遵循这s h a n n o n 信息论这三个重要假设的方向。 列x 图1 2t u r b o 码编码器结构 从编码角度讲，t u r b o 码是由两个递归卷积码通过一个伪随机交织器并行级联 而成。人们从交织增益、有效自由距离、距离谱等角度分析了交织器的作用和对 码性能的影响，认为串行级联码也应该具有好的性能【1 4 】【1 5 1 。从渐近g v 刚8 1 看， t u r b o 码并非好码。从随机码的角度看，好的长码应具有类似于随机码的二项式距 离分布特性，t u r b o 码属于弱类随机码。通过对t u r b o 码在衰落信道中的性能分析， 人们发现最小汉明距离特性不好的t u r b o 码在衰落信道中仍然可以获得良好的性 能【1 6 j8 1 ，原因就是它具有好的汉明距离分布特性。 第一章绪论 y “ y p 图1 3t u r b o 码译码器结构 从译码上讲，t u r b o 码的分量译码器之间也利用交织器和解交织器连接，并且， 译码器中通过的不再是硬判决信息，而是充分利用了译码器之间的相关信息，分 量译码器采用了软输入软输出的译码算法。一个分量译码器的软输出信息作为下 一个分量译码器的输入，根据信息处理定理可知，这样对于任意一个分量译码器， 信息损失的最少，分量译码器可以进行最优译码。为了获得更好的译码性能，将 此过程迭代数次。通过多个软输入软输出译码器之间的迭代，可以使系统渐近性 能逼近最大似然译码。这一惊人发现改变了长期以来把信道截止速率作为实际容 量的历史，使信道编码理论和实践进入了一个崭新的阶段。 t u r b o 码的巨大成功掀起了人们利用简单码和交织器级联构造具有良好随机 性和可利用软输入软输出迭代译码算法的实用好码的高潮。随着对t u r b o 码研究 的深入，人们重新发现g a l l a g e r ：1 9 】早在1 9 6 2 年提出、由m a c k a y l 2 0 】等人重新发现也 是本文的研究重点的低密度奇偶校验码( l o w d e n s i t yp a r i t y - c h e c kc o d e s ，简称 l d p c 码) 也是一种具有渐进特性的非常好码，它的译码性能同样可以逼近香农信 道容量限。l d p c 码具有在中长码长时优于t u r b o 码的纠错性能，并且译码复杂度 更低，能够并行译码以及译码错误可检测等特点，成为目前信道编码理论的研究 热点。研究表明，t u r b o 码只是l d p c 码的一个特例【2 1 1 ，二者都是基于图构造的低 密度码，译码算法具有等价性，二者在基于图论的编译码研究中得到了统一。 1 3l d p c 码的发展历史与现状 1 3 1l d p c 码的提出 l d p c 码的概念及其迭代译码算法的提出要追溯到1 9 6 2 年【1 9 】。g a l l a g e r 在他 的论文中定义了( 甩，j ，k ) ( ，后，j ，k 咒，其中膨是日 行空间的维数。 如果日是一个稀疏矩阵，而每行或每列中“l ”的个数不是常数，则由这样的一 致校验矩阵日定义的是非规则l d p c 码。 2 1 2l d p c 码的环和围长 如图2 2 ( b ) 所示，若由因子图中的某个节点出发，经过不同的连续的节点，最 1 2 西安电子科技大学硕+ 学位论文i ，d p c 码算法研究及a s i c 实现 后可返回所选的起始节点，则该闭合路径即构成因子图中的一个环( c y c l e ) ，环上的 节点数或边数称为环长，图中所有环的最小长度称为围长( g i r t h ) 。图2 2 b 中虚线 边和连接的节点构成长度为4 的环，4 也是此因子图的围长。 h = 100 1 0 ：10 日i 校验节点 11o o1 i o 1 qi i1 01110i 0101 0 0101 ：10 l 变量节点 b l b 图2 2 ( 8 ，2 , 4 ) l d p c 码的校验矩阵和因子图 由和积译码算法的迭代过程可知，当因子图中存在环路时，参与迭代运算的信息 不满足独立性，环的存在使得译码不满足最优性。因此，因子图中的环是影响l d p c 码性能的重要因素之一【4 1 1 。另一方面，文【4 2 】证明无环图对应的码不是渐近好码， 反而环的存在可以改善码的最小距离，对码本身的性能带来好处。可见，在l d p c 码的设计过程中，需要兼顾码结构本身和迭代译码解决环的问题。一般码长较长 时消除4 环即可获得较好的性能，而对于短码，环的影响更大一些。 2 2 正则与非正则l d p c 码 在l d p c 码的校验矩阵中，如果行列重量固定为( py ) ，即每个校验节点有 p 个变量节点参与校验，每个变量节点参与y 个校验节点，我们称之为正则l d p c 码。g a l l a g e r 最初提出的g a l l a g c r 码就具有这种性质。从编码二分图的角度来看， 这种l d p c 码的变量节点次数全部为y ，而校验节点的次数都为p 。我们还可以适 当放宽上述正则l d p c 码的条件，行列重量的均值可以不是一个整数，但行列重 量尽量服从均匀分布。另外为了保证l d p c 码的二分图上不存在长度为4 的圈， 我们通常要求行与行以及列与列之间的交叠部分重量不超过1 ，所谓交叠部分即任 意两列或两行的相同部分。我们可以将正则l d p c 码校验矩阵h 的特征概括如下： 1 、h 的每行行重固定为p ，每列列重固定为y 。 2 、任意两行，两列之间交叠部分重量最多为1 。 3 、行重p 和列重y 相对于h 的行数m 、列数n 很小，h 是个稀疏矩阵。 4 、正则l d p c 码的最小码率，可以通过下式计算： ，= ( 一m ) = 1 一m n = 1 - y p( 2 4 ) 在正则l d p c 码的校验矩阵中，行重和列重的均值保持不变，所以校验矩阵 第二章l d p c 码的简介 中1 的个数随着码长的增加而线性增长，整个校验矩阵的元素个数则成平方增长。 当码长达到一定长度时，校验矩阵h 是非常稀疏的低密度矩阵。对于正则的l d p c 码，m a c k a y 在文【2 6 】中给出了以下两个结论： 1 、对于任意给定列重大于3 的l d p c 码，存在某个小于信道传输容量且大于 零的速率，当码长足够长时，可以实现以小于，- 且不为零的速率无差错的传输。 也就是说任意给定一个不为零的传输速率，存在一个小于相应香农限的噪声门 限，当信道噪声低于该门限且码长足够长的时候，可以实现以，速率无差错的传输。 2 当l d p c 码的校验矩阵h 的列重y 不固定，而是根据信道特性和传输速率 来确定时，则一定可以找到一个最佳码，实现在任意小于信道传输容量的速率下 无差错的传输。 对于l d p c 码的每个变量节点来说，当它参与的校验式越多，即次数y 越大， 则它可以从更多的校验节点获取信息，也就可以更加准确的判断出它的正确值。 对于h 的每个校验节点来说，当它涉及的变量节点越少即次数p 越小，则它可以 更准确的估计相关变量节点的状态。这种情况对于正则l d p c 码来说是一对不可 克服的矛盾，于是l u b y ，m i t z c n m a c h c r 等人就引入了非正则l d p c 码的概念。 在非正则l d p c 码的编码二分图中，两个集合内部的节点次数不再保持相同， 即每个变量节点参与的校验式数目或每个校验式中含有的变量节点数目不再保持 均匀，而是有意设置部分突出的变量节点和校验节点。在译码过程中，那些参与 较多校验式的变量节点迅速得到它们的正确译码信息，这样它们就可以给相邻的 校验节点更加有效的概率信息，而这些校验节点又可以给与它们相邻的次数少的 变量节点更多的信息。整个译码的过程呈现出一种波状效应，次数越高的变量节 点首先获得正确信息，然后是次数较低的节点，然后依次往下，直到次数最低的 变量节点。正是这种波状效应，使得非正则l d p c 码获得比正则l d p c 更好的译 码性能。理论上的极限性能仅仅比香农限高0 0 0 4 5 d b 的非正则码次数分布对已经 找到【4 3 】。 为了描述非正则的l d p c 码，我们需要定义相应的次数分布，节点的次数分 布和边的次数分布是两种常用的次数分布。节点的次数分布 ( 肛) 定义为次数为f 的变量( 校验) 节点在所有变量( 校验) 节点中所占的比例。边的次数分布九( 肛) 定义为与次数为f 的变量( 校验) 节点相连的边数占总边数的比例。若( 办一，吐一) 为变量节点和校验节点中的最大次数，则有 瞥? 函 乃= 岛= 1 ( 2 5 ) i = li = l 根据l d p c 码的编码二分图，每条边两端总对应一个变量节点和校验节点， 所以有( 2 6 ) 式。 1 4 西安电子科技大学硕士学位论文l d p c 码算法研究及a s i c 实现 幸万：m 宰石，万：艺f 幸乃，瓦：窆f 木肛 ( 2 - 6 ) 对应的非止则l d p c 俏阴最小俏翠 ，：1 一( d v m a x ) ( 窆f 事仍) ( 2 - 7 ) 乃( 肛) 和五( 矗) 存在如下的换算关系 i * y i = 万幸五，i * p l = 万磊 ( 2 8 ) 例如有三的变量节点的次数为3 ，丢的变量节点次数为4 ，还有云变量 节点的次数为5 ，我们可以用一组向量来表示该非正则l d p c 的节点次数分布 歹= ( 乃，托，乃，托，r s ) = ( 0 ，0 珏11 西5 ) 类似的我们还可以用边的次数分布来描述 芗= ( 多，r ：，；，多。，多，) = ( 。，o ，石1 2 ，石1 2 ，石2 5 ) 2 3 二元域与多元域的l d p c 码 前面对l d p c 码的定义都是在二元域基础上的，m a c k a y 在m 】中对上述二元域 的l d p c 码又进行了推广。如果定义中的域不限于二元域就可以得到多元域g f ( q ) 上的l d p c 码。多元域上的l d p c 码具有较二进制l d p c 码更好的性能，而且实 践表明在越大的域上构造的l d p c 码，译码性能就越好【4 5 1 ，比如在g f ( 1 6 ) 上构造 的正则码性能已经和t u r b o 码相差无几。多元域l d p c 码之所以拥有如此优异的 性能，是因为它有比二元域l d p c 码更重的列重，同时还有和二元域l d p c 码相 似的二分图结构。 假设在域g f ( 2 ) 和域g f ( q ) ( q = 2 p ) 上构造的l d p c 码所对应的校验矩阵分别是 日2 和。h 2 中的元素是0 或1 ，而峨是由元素o ，1 ，q - 1 构成，以中的每个元 素都是h 2 中p 个元素的合成。如果设域o f ( q ) ( 留= 2 p ) 上的一个值a 与一个l xp 的 二进制向量相关联，那么把这个向量代入q 中，就可以得到q 的二进制表示。 对于二进制l d p c 码来说，如果它的校验矩阵h 的列重量足够大，那么它可以任 意地接近香农限，但是如果增加列重量会使得二分图中节点之间短圈的数目急剧 增加从而使b p 算法的性能下降。而在g f ( q ) 域上构造的l d p c 可以解决这个矛盾， 第二章l d p c 码的简介 它的检验矩阵以可以增加与之对应的二进制校验矩阵2 h 中列的平均重量，且它 的二分图结构并没有改变，不会造成节点之间短圈数目的增加，从而使得译码性 能得到显著的提高。这种多元域上的编码构造会增加译码复杂度，但是相对于译 码性能的提高来说这种增加是值得的。 2 4l d p c 码的最小码重分布 l d p c 码的性能可以根据各个码字之间的最小码距，即最小码重来衡量，码重 越大，则它的纠错能力越强。但随着码长的增加，直接分析l d p c 码的最小码重 很难实现。g a l l a g e r 在【l9 】中提出将特征类似的l d p c 码归为一类，对该集合分析其 中码字的最小码重就比较简单。在集合的最小码重分布特性已经得到的情况下， 我们更有可能从集合中随机挑选出具有较好码重分布特性的l d p c 码。 若某个l d p c 码中，码重为l 的码字数目为w ( 0 ，则表示对于该码中任意一 个码字，与它距离为l 的码字数目为w ( t ) 。因为少数重量较轻的码字主导了整个 码组的译码性能，因此对于给定码长n 、码率为，的l d p c 码，我们总是希望它的 最小码重d 尽可能的大，并且码重等于或稍大于d 的码字数量尽可能的少。e i l i a s 在【4 6 】中分析了在随机产生校验矩阵的情况下，获得的一般奇偶校验分组码的码重 分布界。对于码长n 、码率为，的奇偶校验码，当它的所有码字等概分布时，最小 码重分布有如下的不等式： 一一，、 i 形( ，) = i1 ：1 2 一呱1 。一【2 u n t ，( 1 一艿) 】2e x p m 日( 艿) 一( 1 一r ) i n 2 】 ( 2 - 9 ) l 厂r f p ( w n s ) 瓦 2 刚 a 2 i 万- - m u e x p n h ( 艿) 一( 1 一，) n 2 】( 2 - 1 0 ) ， 1 其中，万= ，日( 万) = 一8 i n - - ( 1 一万) 血( 1 一万) 。 vo 式( 2 1 0 ) 说明，当h ( 艿) 一( 1 一r ) i n 2 0 ，万 o ) ，e l s e 乏= o ；得到初始译码序列 第三章l d p c 码的译码算法1 9 z o = ( 钟9 0 9 露) 。初始化迭代次数：k = - i 。 2 、将z 卜1 左乘校验矩阵h ，获得各个校验式的校验结果：s 扣1 = ( s k - i ，s 。扣1 ) 。 3 、统计每个变量节点所对应的校验式中不成立的个数一= 瓯b 1 。 m e c ( n ) 4 、从，扣1 = ( 一，- 1 ) 中找出最大值在，将它所对应的变量节点的比特 乏：翻转，得到新的的码字 5 、重复2 - - 4 ，直到所有的校验式都满足或到达事先设定的最大迭代次数为止。 b f 算法每次迭代译码选择疋最大的变量节点翻转，每次只改变一个比特的 值，当l d p c 码的码长较长时，需要的迭代次数很大。我们可以设定某个门限， 当，：大于该门限时，进行翻转，这样一次迭代不止翻转一个比特，能够减少迭代 次数。但是如果同时翻转多个比特，有可能导致出现不可检测错误，即译成别的 码字，造成译码性能的下降。 通过上面的介绍我们发现，b f 算法只需要模二运算，并且具有并行结构，硬 件实现比较简单。但与后面介绍的软判决和积译码算法相比，b f 算法的译码性能 要差的多，所以b f 算法适合用于光纤通信等信道条件很好的情况。通常，我们采 用b f 算法来粗略的判断校验矩阵h 对应的l d p c 码是否具有良好的纠错性能。 3 2 和积译码算法 对于l d p c 码，当码长很长时，最大似然译码算法几乎不可实现。因此，寻找 一种有效的译码算法甚至比构造一个好码更为重要。和积译码算法，也就是置信 传播译码算法，通过b a y c s 准则获得近似最大后验概率译码，是基于无环图的l d p c 码的最优迭代译码算法。如果l d p c 码的因子图上有一个环，这时和积算法收敛 到一个稳定的点，获得较好的性能。但无法确定因子图中有多于一个环时的性能 【2 8 】 o 采用与文献 5 1 】中类似的符号表示，朋o ) 表示与变量节点n 相连的校验节点 的集合，即日矩阵第刀列中1 的位置；( m ) 表示参与第m 个校验方程的变量节点 的集合，即日矩阵第m 行中1 的位置。( 聊) 以表示从集合( m ) 中去掉元素，l 之 后的子集，同理m ( 忍) 朋表示从集合朋( 咒) 中去掉元素m 之后的子集。符号。代表 模二和。 3 2 1基于概率测度的和积算法 整个译码过程可以看作t a n n e r 图上的b p 算法的应用。以图3 2 为例，每一个 信息节点v 是校验节点c 的子节点，每一个校验节点c 是信息节点v 的父节点。 吼。( 0 ) 和q n - * m ( 1 ) 分别表示从变量节点”传往校验节点m ，变量节点，l 取值为0 或 西安电子科技大学硕士学位论文l d p c 码算法研究及a s i c 实现 1 的概率，它们的值由变量节点，l 参与的除校验方程m 之外的其他校验方程决定。 类似地，一。( 0 ) 和+ 。( 1 ) 分别表示从校验节点掰传往变量节点，l ，代表变量节点咒 值取o 或1 的信息( 表示在变量节点刀取值为0 或1 的条件下校验节点m 成立的概 率1 ，由参与校验方程m 的除变量节点疗之外的其他变量节点决定，如图3 2 所示。 右边的一排节点代表校验节点，每一个校验节点代表矩阵h 中的一行校验式，称 为校验比特；左边一排代表信息节点，每一个变量节点代表矩阵h 中的- - y u ，称 为信息比特。校验节点和变量节点相连的关系，代表了校验矩阵中相对应那行的 校验式。每一次迭代中，信息节点在被激活之后把吼。( 0 ) 或g 。寸。( 1 ) 作为可信度传 递给和它相连的校验节点。g 。( o ) 或g 。斗。( 1 ) 是在除c 外己知v 参与的其它校验节 点的信息，v 在状态0 或者1 的可信度。节点c 在被激活之后把_ 。( 0 ) 或斗。( 1 ) 作 为其可信度传递给和它相连的信息节点。- + 。( 0 ) 和。( 1 ) 是在信息节点v 状态为 0 或者1 时，校验式c 中其它信息节点状态分布已知的条件下，校验式满足的概率。 在每次迭代中，所有节点的可信度得到更新。每次迭代结束时，计算其伪后验概 率，做一次尝试判决并且进行译码，得到判决比特序列x 。直到判决序列工满足 妇r = 0 ，或迭代次数达到预设的最大值，迭代停止。 变 量 节 点 名，。( o ) o r _ 。( 1 ) 为 l n v 图3 2 校验节点与变量节点 吼。( 1 ) 校 验 节 点 迭代译码步骤如下： 假设a w g n ( n n ( 0 ，仃2 ) ) 信道下、b p s k 调制，其中码元巳 0 ，1 ) ，发送符号 x ，= 1 2 c ， jj ( 3 一1 ) 第三章l d p c 码的译码算法 2 l 输出 y s = + 刀j ( 棚，佃) ( 3 2 ) 概率测度的和积算法流程为： 初始化：，= 0 ，最大迭代次数为k 。对于l d p c 码的一致校验矩阵h 中的每 一个非零元= 1 ，0 m m ，0 n n 初始化： 吼+ 。o ( o ) = 尸( 矗= + 1 以) = l ( 1 + e - 2 y 1 0 2 ) ( 3 3 ) 吼_ ，o ( 1 ) = p ( = 一1 咒) = l ( 1 + e 2 y n i o ) ( 3 - 4 ) 迭代消息传递和更新 第一步( 校验节点更新) ： g f f + ) 。( 6 ) = 尸( = o l c 。= 6 ， 乞，刀m ( m ) 刀) ) 兀g ：已舶( q ) ( 3 - 5 ) 表示当巳= 6 0 , 1 ) ，变量节点以( 聊) 胛的概率g ( 巳) 相互统计独立，第m 个 校验方程满足相加和为零时的概率。式( 2 8 ) 中的条件概率取值1 或0 ，由 弛，i c ( 所) ) 是否参与第m 个校验方程决定。当因子图无环时，这是精确的，如 果因子存在环，则是近似计算【9 】。 第二步( 变量节点更新) ： g 黜( 6 ) = p ( 巳= by 。，p 。，m m ( ，1 ) m ) ) = 口：2 p ( 巳= 6 ) 兀 矗匕。( 6 ) ( 3 - 6 ) 表示由校验节点m m ( 拧) 聊计算得到码字q 取6 o ，1 ) 的概率。取 正n “- - k 1 m = 1 归一化日羰( o ) 和嫂( 1 ) 使 g ：2 ( o ) + g 毙( 1 ) = 1 ( 3 7 ) 第三步( 判决) ： 磊2 ( 6 ) = 尸( q = 6 i 乃) = 竺2 p ( 巳= 6 ) 兀栏。( 6 ) ，口：2 = 1 ( 3 8 ) 掣= 1 , i 。f 畿p p 。瓴_ o i ( 3 - 9 ) 译码尝试： 判决码字；= ；- ，；：，孔】，如果伴随式妇r = 0 ，停止迭代，将；作为译码输出， 否则跳至第一步继续执行。如果迭代次数到达k 仍未成功，则宣告失败，终止迭 代。 两安电子科技大学硕士学位论文l d p c 码算法研究及a s i c 实现 3 2 2基于对数似然比度量的和积算法 置信传播算法的迭代公式是基于独立性假设( i n d e p e n d e n c ea s s u m p t i o n ) 推导得 到的。设二值随机变量x 取值为0 、1 的概率分别为( o ) 和( 1 ) ，为了使所传递的消息 中能够同时包含x 的两个取值概率信息，通常用两者的一个函数变量来表示该信 息，如概率差、概率比、和对数似然比，这些函数变量称作量度( m e t r i c ) 。实际应 用中，如果将对数似然比( l l r ) 作为信息来传递，可以将乘法运算转化为加法并省 去归一化的计算，因此比用概率或者似然比做信息传递有优势。对数似然比 ( 1 0 9 - l i k e l i h o o dr a t i ol l r ) 定义为 地) i l l l 酱裂地而p r ( x n = + 1 1 y ) 汕描( 3 - 1 0 ) 乙斗。( 吒) 兰l o g ( q n - - c m ( o ) q n - - ，r a ( 1 ) ) ( 3 一1 1 ) 厶一。( 以) 兰l o g ( r 棚。( o ) r = _ 。( 1 ) ) ( 3 1 2 ) z 灿端 ( 3 - 1 3 ) 设允= l n ( p o p , ) ，可以得到“t a n h 准则”： 鼬= 而e z - 1 = 晶一眉= l 一2 日 ( 3 - 1 4 ) 重写l d p c 码的和积算法在对数似然比度量下的译码过程： 初始化：，= 0 ，最大迭代次数为k 。对于l d p c 码的一致校验矩阵日中的每 一个非零元= 1 ，0 m m ，o ，l n 初始化： 乙呻。( 吒) = ( l 以) = l o g ( p ( x 。= 0i 乩) 尸( 吒= 1i 儿) ) = 2 咒a 2 ( 3 1 5 ) 迭代消息传递和更新： 第一步( 校验节点更新) ：对每个校验节点m 及咒( 历) ，计算 ，= i 7 n , l 急( m ) n s 毗川) x 2 t a n h - 1k m 鼬( 掣 p 峋 k “= 酬u 圳恤m 鼬【掣j j o - 1 6 第二步( 变量节点更新) ：对每个变量节点n 及m m ( 以) ，计算 乙+ 。( ) = ( 矗i m ) + 乙。( 毛) 胛e ( 月) 、册 乙( ) = ( l y 。) + 厶。( 毛) m e a , t ( n ) m 第三步( 判决) ：如果乙( 矗) 0 ，令吒= 0 ，否则吒= l 。 ( 3 1 7 ) ( 3 1 8 ) 第三章l d p c 码的译码算法 译码尝试： 判决码字；= 【；。，；：，氨】，如果伴随式妇r = 0 ，停止迭代，将三作为译码输出， 否则跳至第一步继续执行。如果迭代次数到达k 仍未成功，则宣告失败，终止迭 代。 3 2 3最小和译码算法 由于b p 译码算法的校验节点更新中包含的双曲正切运算对于实际的应用是很 困难的，为了降低译码复杂度，提高译码性能，从考虑b p 译码算法更具有实用角 度出发，对其进行了改进，对校验节点的更新计算进行了简化处理，探讨了改进 的译码算法。下面将介绍最小和算法。 最小和算法在网格图上只挑选一条最可能的有效路径，在无环图上实现了最小 码字错误概率的译码。但对于有环图码，例如l d p c 码，最小和算法则认为是退 化的和积算法，其性能有损失。最小和译码算法的译码过程中的初始化和变量节 点更新公式和和积译码算法相同。重点考察校验节点消息更新公式的差异。 考虑一个度为3 的校验节点，令( 矗n ，硝”) 和( 反孙，硝2 )