（通信与信息系统专业论文）基于fpga的ldpc码的实现.pdf

摘要 低密度校验码( l d p c ) 是一种能逼近s h a n n o n 容量限的渐进好码，其长码性能 甚至超过了t u r b o 码。低密度校验码以其迭代译码复杂度低，没有错误平层，码 率和码长可灵活改变的优点成为t u r b o 码强有力的竞争对手。目前，l d p c 码已广 泛应用于深空通信、光纤通信、卫星数字视频和音频广播等领域，因此l d p c 码编 译码器的硬件实现已成为纠错编码领域的研究热点之一。 本文在分析l d p c 码的基本编码结构基础上，首先研究了l d p c 码的随机构造 方法，并给出了有效的p e g ( p r o g r e s s i v ee d g eg r o w t h ) 算法实现方法，重点分析了 用环消除( c y c l ee l i m i n a t i o n ) 算法实现的准循环l d p c 码的构造。然后对l d p c 码的 几种不同译码算法进行分析比较，讨论了一种适合硬件实现的译码算籼d m p 算 法，并对易于硬件实现的t d m p 算法进行了性能仿真，仿真结果表明t d m p 算法 作为硬件实现的译码算法具有优异的性能优势。最后针对a l t e r a 公司的s t r a t i x e p l $ 2 5f p g a 芯片设计了一个基于t d m p 算法的( 4 0 9 6 ，2 0 4 8 ) 非规则l d p c 码译 码器，内部用了4 个单校验码译码器并行译1 帧数据，3 帧同时译码，作者详细 介绍了该译码器芯片的设计过程和内部结构和工作流程。 关键词：低密度奇偶校验码( l d p c ) f p g at d m p 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 r 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 l le v i lo u t v 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 o w e rc o m p l e x i t yo fd e c o d i n g ，l o w e re r r o rf l o o ra n d t h ec h a n g e a b l ec o d er a t ea n dl e n g t h ，l d p cc o d e sh a v eb e c o m et h es e r i o u sc o m p e t i t o r s t ot u r b oc o d e s a tp r e s e n t ，l d p cc o d e sh a v eb e e nw i d e l yu s e di nt h ea r e ao f d e e p s p a c ec o m m u n i c a t i o n ，f i b e rc o m m u n i c a t i o n ，t h ed i g i t a lv i d e oa n da u d i ob r o a d c a s t o fs a t e l l i t ec o m m u n i c a t i o n se r e h e n c e ，t h es t u d y0 1 1t h eh a r d w a r ei m p l e m e n t a t i o no f l d p cc o d e sh a sb e c o m eo n eo ft h em o s ta t t r a c t i v ei s s u e si nc h a n n e l c o d i n g c o m m u n i t y t h i st h e s i sa n a l y z e st h eb a s i ce n c o d i n gs c h e m e s f i r s t l y , w ei n t r o d u c et h er a n d o m c o n s t r u c t i o nm e t h o d so fl d p cc o d e s ，i n c l u d i n gt h ep r o g r e s s i v e e d g e g r o w t h ( p e g ) a l g o r i t h m a n dt h a nw es t u d yt h ec o n s t r u c t i o no fq u a s i c y c l i c ( q c ) l d p cc o d e su s i n g t h ec y c l ee l i m i n a t i o n ( c e ) a l g o r i t h m s e c o n d l y , w ec o m p a r et h r e ed e c o d i n gm e t h o d s a n dd i s c u s st h et 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 ) a l g o r i t h mw h i c hc a nb e e a s i l yi m p l e m e n t e di nh a r d w a r e w es i m u l a t et d m pa l g o r i t h ma n df i n di th a sg r e a t p e r f o r m a n c ea d v a n t a g e f i n a l l y , a n ( 4 0 9 6 ，2 0 4 8 ) t d m pd e c o d e ri sd e s i g e n e db a s e do n a l t e r as t r a t i xe p1s 2 5f p g ad e v i c ew h i c hu s i n gf o u rs i n g l ep a r i t yc h e c ku n i t st o d e c o d eo n ef r a m ei np a r a l l e la n dt h r e ef r a m e sa r ed e c o d e ds i m u l t a n e o u s l y t h i st h e s i s a n a l y z e st h es t r u c t u r eo ft h ed e c o d e ra n di t sw o r k i n gf l o w 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 at d m p 西安电子科技大学 创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期： 丝卫! 竺 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文和使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复印手段保存论文。同时本人保 证，毕业后结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大 学。( 保密的论文在解密后遵循此规定) 本人签名： 导师签名： 日期 竺! z ：至：! ! 日期 哗；。z 乙么 第一章绪论 第一章绪论 本章简要介绍了数字通信系统的基本组成以及信道编码的基础知识，回顾了 信道编码理论；概述了l d p c 码的历史和现状以及特殊构造和特点；最后总结了 作者在攻读硕士期间所做的主要工作并给出了本文内容安排。 1 1数字通信系统的基本组成部分 图1 1 显示了一个数字通信系统的功能框图和基本组成部分。信源输出的可 以是模拟信号，如音频信号；也可以是数字信号，如电传机的输出信号。信源编 码的作用是使由信源产生的消息变换成二进制的数字序列。为了提高通信的有效 性，使其很少产生或不产生冗余，应当用尽可能少的二进制数字表示信源输出任 何信源都有一个被称为信源熵的量，它表征了信源的平均不确定程度【1 】。信源编 码定理指出信源熵是数据压缩的下界【2 l 。 众所周知，信道中各种噪声的干扰是造成数字通信系统接收机误码的主要原 因。信道编码器的作用是在二进制数字序列中受控的引入一些冗余，用来克服信 号在信道中遭受的噪声和干扰的影响。信道编码与信源编码相反，它通过在信息 序列中引入冗余来实现通信的可靠性，任何信道都存在一个被称为信道容量的值， 它表征了信道的传输能力。 信道编码器输出的二进制序列不适合直接在信道中传输，必须送到数字调制 器，将二进制信息映射成适合信道传输的信号波形。通信信道是用来将发送机的 信号发送给接收机的物理媒质。 图1 1 数字通信系统模型 在数字通信系统接收端，数字解调器对接收信号波形进行相应的处理，还原 成一个数字序列，这个序列表示发送数据符号的估计值。这个数据序列被送至信 2 基于f p g a 的l d p c 码的实现 道译码器，它根据信道编码器所用的关于码的知识及收到数据所含的冗余度重构 初始的信息序列。 数字通信系统的可靠性用错误比特率( b e r ) 衡量，有效性用传输速率衡量。 早期的人们普遍认为：通信系统的可靠性与有效性是一对不可调和的矛盾，在有 扰通信信道上实现任意小错误概率的信息传输的唯一途径就是把传输速率降低至 零【3 1 。s h a n n o n 于1 9 4 8 年提出的有噪信道编码定理，首次阐明了在有扰信道中实 现可靠通信的方法，指出实现有效而可靠地传输信息的途径是编码【4 】。 综上所述，信道编码是解决通信有效性和可靠性这对矛盾的关键。但是， s h a n n o n 指出了可以通过差错控制码在信息传输速率不大于信道容量的前提下实 现可靠编码，却没有给出具体的实现差错控制编码的方案，因而如何在实际系统 中实现信道编码仍然是一个难题。 1 2 1 信道容量的定义 1 2 信道编码理论 信道容量表示一个信道的传输能力，它与信道的噪声大小和分布、传输信号 的功率以及传输带宽有关。对于所有信道都有一个最大的信息传输率，称为信道 容量c 【1 1 。它是信道可靠传输的最大信息传输率。对于不同的信道，存在不同的 噪声形式，信道带宽，因而具有不同的信道容量。考虑离散无记忆信道( d m c ) ， 信道容量定义【2 1 为： c = 错删阶嘴陬y ) 删叫= 鬈委q - i 毗删圳。g 等 式( 卜1 ) 其中，变量x 和y 分别代表信道的输入和输出；p ( x ) 代表输入变量的概率 密度函数；i ( xi 】，) 代表x 和y 的互信息；日( x ) 为信源熵；h ( xl 】，) 为条件熵。 一般时间连续信道的信道容量为： c = m m a x ) l 丁l i m 。1 丁( x ；聊 = m m a x ) 【丁h l i m 。1 1 i 【日( y ) 一日( 】，ix 玲 式( 1 2 ) 1 2 2s h a n n o n 限 广义香农限是指在一定误码率条件下单位时间单位带宽上传输一比特所需的 最小信噪比。当没有误码率时，就是狭义的香农限。 第一章绪论 s h a n n o n 在【4 】中推导了波形信道在加性高斯白噪声下的信道容量： 。肌0 9 z 1 + 蒜1 式( 卜3 ) 这个容量仅在输入服从高斯分布的情况下可以达到。如果输入信号调制受限， 那么容量将会小于上面这个值。 公式( 卜3 ) 中形是信道带宽，只是信号的平均功率，o 是噪声的单边功率谱 密度，c 是信道容量( 单位为b i t s ) 。在数字通信系统中，尾是每信息比特需要 的传输能量。由公式( 卜3 ) 变形可得： c = l 0 9 2 ( ，+ 参半知 式( 1 叫 墨：2 c l w - 1 式( 1 5 ) = - = 一 n ii 一：) j n oc w 每= 嬲努= i n 2 = - 1 6 抬 舶删 当毛o - 1 6 d b 就可以实现高斯白噪声信道下的无误传输。这是带宽无限 高斯白噪声信道的极限传输能力，称为高斯白噪声信道下s h a n n o n 限。 1 2 3 信道编码定理 信道编码定理【5 】：每个信道具有确定的信道容量c ，对任何小于c 的码率r ， 存在有速率为r 码长为，l 的分组码及( 以。，k o 扰) 卷积码，若用最大似然译码，则随 着码长的增加其译码错误概率p 可任意小，即 p 4 矿哦r 式( 卜7 ) p 4 p 一删幔的= 4 p 一毛的 式( 卜8 ) 一个译码器的译码规则若能在2 个码字c 中选择某一个码字e 使得 尸( ric ) 最大，这种译码规则称为最大似然译码。最大似然译码的复杂度随着码 长的增加而增长，当码长趋于无穷大时，最大似然译码是无法实现的。 公式( 卜7 ) 和公式( 1 - 8 ) 中，4 和4 为大于0 的系数，既( r ) 和e ( r ) 为正实 函数，称为误差指数。当尺一定时，信道容量c 越大，e ( r ) 越大；信道容量c 一 定时，r 越大，e ( 尺_ ) 越小。 根据公式( 1 - 8 ) 以及e ( 尺) 和尺的关系可知：为了满足一定错误概率p 的要求， 可以通过增加信道容量c ，从而使e ( r ) 增加；也可在r 一定的情况下，增加分组 4 基于f p g a 的l d p c 码的实现 码长栉，也就是增加分组信号持续时间；这两种方法都可以使p 指数下降。增加 信道容量c 可以通过增加系统带宽或增加信噪比的方法来实现。 任意离散输入无记忆平稳有噪信道都有一个被称为信道容量的值c ，它标志 着信道传输能力的上限，只要信息传输速率r c ，就存在一种编码方式，当平 均码长足够大时，译码错误概率可以做到任意小；反之，则无论采用何种编码方 式也不可能保证错误概率任意小【5 】。 1 3 l d p c 码的发展与现状 早在1 9 6 2 年g a l l a g e r 已经提出正则低密度校验码( r e g u l a rl o wd e n s i t yp a r i t y c h e c kc o d e s ) 和迭代译码( i t e r a t i v ed e c o d i n g ) 的概念【6 】，然而直到上世纪9 0 年代中期 l d p c 码被s p i e l m a n 、m a c k a y 和n e a l 等学者【7 】【8 】重新发现后，它才重新引起人们 的广泛关注。 g a l l a g e r 提出的二元规则l d p c 码，它可看作一个具有稀疏校验矩阵( 校验 矩阵中“1 的数量很少) 的线性分组码。当l d p c 码的校验矩阵的行和列中“1 的数目分别固定为，和c 时，被称为规则( ，c ) 一l d p c 码，否则称为非规则l d p c 码。g a l l a g e r 证明了l d p c 码具有很好的汉明距离特性，是具有渐进特性的好码。 因为当l d p c 码很长时，需要十分复杂的估算，所以人们在很长一段时间里忽略 了l d p c 码的存在。 1 9 8 1 年t a n n e r 重新研究了l d p c 码，使用图的形式表示了校验码的约束关系， 即把码校验约束建立在局部码元集合上的t a n n e r 图，并证明了g a ll a g e r 的译码 算法与l d p c 码对应二部图中的环有关【9 1 。同时在无环图的基础上证明了最小和算 法与和积算法的最优性( 最小和算法准确实现了最小码字错误概率的最佳最大似 然译码，和积算法实现了最小符号错误概率的最大边界后验概率算法) 。但t a n n e r 图在实际中采用随机构造的方法，不可避免的出现小环现象，影响迭代译码的收 敛性。 1 9 9 5 年，m a c k a y 和n e a l 重新发现了l d p c 码，发现采用和积译码的正则l d p c 码有和t u r b o 码相似的译码能力，在长码时甚至优于t u r b o 码【8 1 ，这一结论迅速 引起了编码届的强烈反响和极大关注。 与此同时，w i b e r g 1 0 】结合t u 内o 码和网格图的研究，把t a n n e r 图推广到具有 隐含状态变量的w i b e r g 图上，使网格型结构作为其特殊情况，从而使消息传递算 法包扩了v a 等基于网格的译码算法，证明了最小和算法与和积译码算法在本质 上的同一性。w i b e r g 研究发现无环图具有较大的状态复杂度，证明了基于有环 t a n n e r 图的l d p c 码具有较低的译码复杂度。 l d p c 码的兴起，使基于图模型的消息传递译码算法的分析、具有快速编码 第一章绪论 5 结构的t u r b o 1 i k e 码的设计、l d p c 码集合度序列优化得到了深入的研究。近年 来，r i c h a r d o n 等人应用密度进化理论分析了l d p c 码的性能1 1 1 1 。r i c h a r d s o n 等人 发现，l d p c 码译码信息的迭代传递过程中存在着译码阙值现象，即当信噪比大 于译码阈值时，迭代译码可使误码率趋于零，反之无论采用多长的l d p c 码，经 过多少次迭代译码，总存在一定的错误概率。r i c h a r d s o n 等人系统建立了无环图 上的密度进化理论，分析了译码阈值的存在性和收敛条件，证明了随机构造l d p c 码的特性收敛于集合平均特性；而无限码长的有环随机图的阈值逼近无环图的阈 值【1 1 】【1 2 】。 l d p c 码理论的深入发展推动了其硬件实现的研究进程。从1 9 9 8 年以来，l d p c 码的硬件实现成为一个研究热点。l o e l i g e r 等学者认识到和积算法非常适合模拟 v l s i 实现【1 3 】f 1 4 1 。s u n g w o o kk i m 等人构造了一种生成矩阵和校验矩阵都是稀疏矩 阵的l d p c 码，由于其编、解码结构的简单性，非常适合使用超大规模集成电路来 实现【i5 1 。z h a n g t o n 等人详细介绍了最大容量为5 4 m b p s ，列重为3 ，行重为6 ，码 长为9 2 1 6 比特的低密度校验码的译码器【1 6 j 。j h o w l a n d 1 7 1 在2 0 0 2 年就采用全并 行结构实现了码长为1 0 2 4 ，码率为1 2 ，译码速率达到1g b i t s 的l d p c 译码器， 译码器的时钟频率为6 4 m h z 。尽管译码速度很快，但是是以巨大的硬件资源消耗 为代价的。尽管工业界也已经有l d p c 编译码芯片问世，但从其编译码器的性能来 看，在硬件设计实现方面还有可以进一步研究。 l d p c 码研究表明，它是一类具有优异性能的好码：其具有较大的灵活性和 较低的错误平层( e r r o rf l o o r s ”) ；译码复杂度低于t u r b o 码，且可实现完全的并 行操作，硬件实现复杂度低；吞吐量大，具有高速译码潜力；在突发状况下，具 有较好的纠错性能；在编码和译码时不需要相关性；一个单一的l d p c 码可广泛 用于一系列信道；对严格的理论分析具有可验证性。和t u r b o 码相比，l d p c 码 在良好的距离性，低复杂度和高并行译码方法上都显示其更优越的性能，是近年 信道编码领域的研究热点，目前已广泛应用于深空通信、光纤通信、卫星数字视 频和音频广播等领域。l d p c 码已成为第四代通信系统( 4 g ) 强有力的竞争者，而 基于l d p c 码的编码方案已经被下一代卫星数字视频广播标准d v b s 2 采纳。 然而，l d p c 码的编码复杂度仍然过高，这是在其设置上需要解决的主要问 题。现在已经有一些研究，通过采用特殊形式的矩阵如低阶三角矩阵或者半随机 矩阵来降低其编码复杂度。如何有效构造易于硬件实现的l d p c 码及设计简单易 行的译码结构称为我们进一步研究的方向。 1 4 本文的主要研究工作和内容安排 作者采用理论分析和计算机仿真相结合的方法，对低密度校验码的理论和应 6 基于f p g a 的l d p c 码的实现 用中的问题进行了深入研究。全文共分五章，具体安排如下： 第一章回顾了数字通信系统的基本原理及l d p c 码技术的发展历程；第二章 介绍了l d p c 码的基础知识，先系统地介绍了l d p c 码的定义和t a n n e r 表示以及 l d p c 码几种常用的构造方法，重点讨论了准循环l d p c 码的构造，比较了p e g 随机构造和环消除( c e ) 算法构造的准循环码的性能；第三章详细介绍了l d p c 码 的几种译码算法，重点介绍了t d m p 译码算法，通过仿真三种不同码率的u ) p c 码t p m p 算法和t d m p 算法的译码性能，证实了t d m p 算法收敛速度快的优点， 为后面的译码器硬件实现提供了理论基础；第四章主要分析了译码器的硬件实现， 介绍了f p g a 的开发流程，通过仿真给出了译码器实现的量化方案，并给出了硬 件实现的总体框架以及核心模块的电路结构；第五章对全文的工作进行总结并提 出进一步的研究方向。 第二章l d p c 码的定义与编码 第二章l d p c 码的定义与编码 本章首先介绍了线性分组码的基本定义及u ) p c 码的因子图表示，然后介绍 了l d p c 的几种构造方法，重点介绍了准循环l d p c 码的构造，最后分析了p e g 构造和准循环构造的l d p c 码的性能。 2 1 线性分组码 l d p c 码是一种普通的线性分组码，可以用生成矩阵和校验矩阵来表示。 l d p c 码又是一种特殊的线性分组码，特殊性就在于它的奇偶校验矩阵中1 的数 目远小于o 的数目，称为稀疏性，低密度也来源与此。为此，我们在研究l d p c 码前先简单介绍线性分组码的相关定义与性质。 2 1 1 线性分组码的定义 分组码是对每段k 位长的信息组，以一定规则增加，- = 刀一k 个校验元，组成长 为刀的序列：( q 小q 彬，c l ，c o ) ，称这个序列为码字。在二进制情况下，信息组总 共有2 个，因此通过编码器后，相应的码字也有2 个，称这2 个码字集合为( 刀，尼) 分组码。 v 长序列的可能排列总共有2 ”种( 每一”长序列称为g 重) ，而( ，l ，后) 分组码 的码字集合只有2 种。分组码的编码问题就是定出一套规则，以便从2 ”个以重中 选出2 个码字，不同的选取规则得到不同的码。定义r = k n 为码率，在( ，z ，七) 分 组码中，它表示了信息位在码字中所占的比重。r 是衡量分组码有效性的一个基 本参数。( 刀，后) 线性分组码是g f ( q ) 上的刀维线性子空间圪中的一个后维子空间 k p 两个v i 重码字i ，多之间，对应位取值不同的个数，称之为它们之间的汉明距 离，用d ( i ，歹) 表示。力重码字j 中非零码元的个数，称为它的汉明重量，用“元) 表 示。( ，l ，七) 分组码中，任意两个码字之间的距离的最小值，称为该分组码的最小汉 明距离以。 以是分组码的另外一个重要参数。它表明了分组码抗干扰能力的大小。研究 表明1 5 】：d o 越大，码的抗干扰能力越强，在相同译码方法下它的译码错误概率越 小。纠错码的基本任务就是构造出r 一定，以尽可能大的码，或以一定r 尽可能 大的码。 7 8 基于f p g a 的l d p c 码的实现 关于分组码有如下定理【5 1 ：任- ( n ，k ) 分组码，若要在码字内，检测p 个随机 错误，则要求码的最小距离d 。e + 1 ；若要纠正f 个随机错误，则要求d o 2 t + l ； 若要纠正f 个随机错误，同时检测e 个错误，则要求d o t + e + l 若要纠正，个随机 错误和g 个删除，则要求d o 2 t + g + l 。 2 1 2 生成矩阵和校验矩阵 设信息位为。，：，则编码器输入矢量为：以= 【，靠：，】编码 器的输出矢量记为：c 二= 【。，：，】，对于二进制线性分组码，编码运算可 以用一组方程表示如下： 2 x , 1 9 l j + x m 2 9 2 j + + 稚岛，歹= 1 ，2 ，n式( 2 1 ) 公式( 2 1 ) 中，劭为0 或1 ，线性方程组也可用矩阵形式表示： q = 以瓯 式( 2 2 ) 公式( 2 2 ) 中，g 称为该码的生成矩阵： g = 卜g i 一 卜9 2 一 卜瓯一 9 1 19 1 2 9 2 t 9 2 2 g k lg t 2 式( 2 - 3 ) 即： 巳= l g l + x m 2 云+ + 嚣 式( 2 4 ) 由于具有2 个码字的( 刀，k ) 线性分组码构成k 维子空间，生成矩阵g 的行矢量 必须是线性无关的，即它们必须能扩张成整个尼维子空间。 虿) 必然是( 力，后) 码的 基底。但是基底的矢量集不是唯一的，即g 不是唯一的。 ( 刀，k ) 码可以通过行运算和列置换简化成系统形式： g = 【厶e l = 式( 2 5 ) 这里是k x k 的单位阵，p 是尼( ，l 一尼) 维矩阵，由它决定( n - k ) 个校验比 特。由系统形式的生成矩阵所生成的线性分组码中，每个码字的前k 位与所发送 的信息比特相同，其余( n 一七) 位是信息位的线性组合。这种( 刀，七) 码称为系统码。 任何( 刀，k ) 线性码都有，l k 维对偶码与之关联。对偶码是一种( 1 1 , n k ) 线性 码，有2 ”个码矢量，这些矢量属于( ，l ，k ) 码的零空间。对偶码的生成矩阵用日来 开 开 封 ； o “ o 绯； 助； m l 七 a 见； 既 0 0 ；1 0 o ；o 0 1 ；0 l 0 ；0 第二章l d p c 码的定义与编码 表示，它是由零空间中n k 个线性无关的码矢量组成的。( 以，七) 码的任意一个码 字e 均正交与其对偶码的任意一个码字，因此( 刀，七) 码的任意一个码字均正交与 日的每一行，即g h r = 0 ，0 代表由n k 个元素组成的全零行矢量，c 。是( ，l ，尼) 码的一个码字。因为公式( 2 - 5 ) 对( ，l ，尼) 码的每个码字都成立，所以有g h r = 0 ，0 代表七o j j ) 维全零矩阵。如果( 刀，尼) 线性码是系统码，由于g h r = 0 ，必有： h = l p rl 一。l ，一p 7 是一个o 一尼) k 阶矩阵，它是p 矩阵的转置，“一 号表 示一p 7 矩阵中的每一个元素是p 矩阵中对应元素的逆元，在二进制情况下，仍然 是该元素自己。 2 2l d p c 码因子图表示 9 l d p c 码是一类可以用稀疏矩阵日或因子图定义的线性分组码。 根据稀疏矩阵日的特点可以将l d p c 码分为规则l d p c 码和非规则l d p c 码。如果一个l d p c 码日的每行有个l ，每列有m = w ( 以一 个，其中r k ) n 1 w ，n ，”n k ，这样的l d p c 码称为规则l d p c 码；反之，则称为非规则 l d p c 码。g a l l a g e r 证明，在规则l d p c 码的码集合中，只要m 3 ，w ，嵋并 且当n 很大时，随机选择所得到的l d p c 码具有较好的距离特性【6 】。 因子图是引入状态变量的广义t a n n e r 图模型，它归纳了目前所有的图模型定 义，提供了一个关于迭代译码的一般性框架。因子图模型实质上是表达一个全局 函数到一组局部函数乘积的有效分解。图中每一个变量节点对应一个变量，每一 个因子节点对应一个局部函数，当且仅当变量是局部函数的自变量时，相应的变 量节点和函数节点之间存在一条连接边。 l d p c 码是通过校验矩阵日来定义的，日具有稀疏性。已知l d p c 码的校验 矩阵日的情况下，可以根据下面的规则做出l d p c 码的因子图：如过检验矩阵某 一元素= l ，那么检验节点岛和变量节点y ，用一条无向线段进行连接【9 j 。 校验矩阵的每一行表示一个校验约束c ，其中所有非零元素对应的码元变量 ，；构成一个校验集，由一个校验方程表示。校验矩阵的每一列表示一个码元符号 参与的校验约束。下面，我们主要针对二元l d p c 码进行讨论。 g a l l a g e r 最早定义的二元( ，d ，d 。) l d p c 码，为码长，或为每列1 的个数， 即变量节点的度数，以为每行1 的个数，即校验节点的度数。由于满足这个结构 条件的校验矩阵并不唯一，所以具有参数( ，正，以) 的l d p c 码构成了一个码集 合。日可以依上述结构条件随机生成，但所给码的性能差异较大。如果日矩阵各 行线性独立，则实际码率r = g o = k ，其中k 为信息比特数，为码长；否则， 实际码率r = ( 一m7 ) n r 。，其中m 是日行空间的维数。 l d p c 码具有校验矩阵h = ( j l l ，) m 。，其因子图模型可以表示为一个二部图。 1 0 基于f p g a 的l d p c 码的实现 码字向量 ，= ( v l ，吃，v ) 表示为一组变量节点 v j ：j = 1 ， ，校验约束表示为一 组校验节点 q ：i = 1 ，彤 。仅当= l 时，节点y ，和q 之间由一条边连接，节点v ， 和q 互称相邻节点，其间连接边称为这两个节点的相邻边。日中每列有以个1 ， 故每个变量节点有d ，条入射边，即与d 。个校验节点相连，d ，称为变量节点的度数。 日中每行有以个l ，每个校验节点具有d ，条入射边，即度数为d 。，共有 e = n d ，= m d 。条边。令集合m ( ) = i ：= 1 ) 表示变量节点1 ，相连的所有校验 节点结合；令( f ) = j ：h 打= 1 ) 表示与校验节点q 相连的所有变量节点集合。 图2 1 是一个( 9 ，2 ，3 ) 短码的校验矩阵及校验方程组，图2 2 是相应的因子图 表示。公式2 - 6 表示了校验约束结构码的全局函数厂( v 1 ，) ，也称码特征函数。 每个校验节点q 表示一个局部约束函数z ( y ，：j ( f ) ) ) 。全局函数因式分解为： 厂( u ，v 9 ) = z ( m ，屹，嵋) 厶( h ，吃，k ) ( 屹，v 4 ，屹) 厶( 屹，k ，唯) 六( ，屿，嵋) 以( 屿，) 式( 2 - 6 ) 公式( 2 - 6 ) 中的各个函数均为指示函数，其中全局函数的逻辑命题为“ ，是一 个码字”，每个局部函数的逻辑命题为图2 1 中的校验方程。公式( 2 6 ) 又写作： f ，c 】= 【m + 吃+ b = o i l y , + 屹+ k = o v 3 + + 吃= 0 】 【鸭+ + 屹= o + 岣+ 嵋= o 】【v 7 + + v 9 = o 】 式( 2 7 ) = 1 110 0 0 0 0 0 11010 o 0 0 0 0 01110 0 0 0 0 0 0 011010 00 0 001101 0 0 0 0 0 0111 学+ 哆+ 垮= 0 巧十巧手均= 0 垮手均手哆= 0 b + + = 0 + 功+ 吩= 0 崎+ 崦+ 啼= 0 图2 1 ( 9 ，2 ，3 ) 短码的校验矩阵及校验方程组 图2 2 为( 9 ，2 ，3 ) 短码的因子图表示。当因子图为无环图时，它不仅可以 有效表示一个函数的因式分解，而且也可以表示一个边缘函数的数学计算表达式。 为更好理解边缘函数的计算过程，可以将因子图的每个节点对应一个处理器，边 表示处理器之间通信的信道。图2 2 所示的因子图中存在长度为4 和6 的短环。 用粗线表示的边即为长度为4 和6 的环的边。所谓环就是从某一个变量节点( 或 校验节点) 出发不经过重合的边又回到该变量节点( 或校验节点) 的环路。环的 长度即为环路中边的数目。一般码长较长时消除4 环即可获得较好的性能，而对 于短码，环的影响更大一些。我们设计的准循环l d p c 码，主要考虑4 环的影响。 第二章l d p c 码的定义与编码 采用迭代置信传播算法译码时，这种短环路将极大地影响码性能6 1 。码的最小汉 明( h a m m i n g ) 距离及距离谱直接取决于环路的分布情况。因此构造码时，应该尽 量消除短坏路。 弓弓弓白弓岛 v 2峙 图2 2 ( 9 ，2 ，3 ) 短码的因子图表示 l d p c 码的因子图表示中，可用一对度数分布序列力= ( a ，九) 和 p = ( 岛，p d ，) 表示入射边分布情况，其中旯，和p ，分别表示度数为的变量节点 的入射边比例和度数为i 的校验节点的入射边比例，d ，和d ，分别是最大变量节点 度数和最大校验节点度数。也可用多项式允o ) = 磐1 乃工歹一1 和p o ) = 垒1 岛一1 表示，这时设计码率为： r ( 兄，p ) = l - f p ( x ) 出f 兄( x ) d x = l 一( 乏：辟f ) ( 复：乃) 式( 2 8 ) 当l d p c 码为规则( ，d ，d 。) 码时，度数分布多项式退化为兄g ) = z 口v - 1 和 p ( x ) = x d c 。具有优化度数分布旯( z ) 和p ( z ) 的非规则l d p c 码一般要好于规则 l d p c 码，而且非规则l d p c 码的性能已经超过了最好的t u r b o 码。 通常，正则码是建立在已知的特性参数之上，这样就可以利用这些参数来分 析正则码的性能。然而，对好的非正则码的分析是采用概率的方法逐渐获得，由 于码的质量由码字的平均性能来决定，所以可以通过适当地选择码重分布使得码 字在低的s n r ( 信噪比) 中获得增益。通过增加s n r ，码的距离特性在一定错误 概率的情况下是确定的。增益是可以通过分析正则码的最小距离、采用较好的光 谱特性来构造等方法而获得。 2 3l d p c 码的随机构造 校验矩阵可以唯一确定一个线性分组码，因此构造正则低密度校验码只需要 构造它的校验矩阵。随机或伪随机的构造方法主要考虑的是码的性能，通常在码 长较长( 接近或超过1 0 0 0 0 ) 时性能比用代数方法构造的l d p c 码好，非常接近 1 2 基于f p g a 的l d p c 码的实现 香农限，但构造的随机性使它们通常具有太高的编、译码复杂度。代数的构造方 法在兼顾码的性能的同时降低了编、译码复杂度，通常在码长较短时性能与随机 构造的l d p c 码性能相当甚至更好。由于准循环( q u a s i c y c l i c ) l d p c 码的编码可 以用移位寄存器在线性时间内完成，译码也可用计数器寻址，且便于部分并行译 码，因此在实现上更有优势，我们将重点讨论准循环l d p c 码的构造。 2 3 1 g a l l a g e rl d p c 码构造 g a l l a g e r 在文献【6 】中采用( 一，_ ，尼) 来表示一个正则低密度校验码，其中，2 表示 码长，表示校验矩阵中每列所含1 的个数，而k 则表示校验矩阵中每行所含1 的个数。g a l l a g e r 采用随机置换的方法来构造校验矩阵，方法如下： 1 ) 将校验矩阵日分成，个子矩阵日1 ，日2 ，日_ ，每个子矩阵有( 以一七) j 行，并且每个子矩阵的每列有且只有一个l ； 2 ) 子矩阵h 1 中的l 呈下降的阶梯状排列，即第f 行的k 个1 从第( f 一1 ) k + l 位 排到第髓位； 3 ) 其余的子矩阵通过对日1 进行随机列置换得到，所有置换是等概出现的。 从上面的构造方法不难知道，由g a l l a g e r 方法构造的校验矩阵并不是满秩的。 g a l l a g e rl d p c 码校验矩阵的每个子矩阵的p 行和均为全1 向量，因此它不是一个 满秩矩阵，其秩至多为p r r + l ，因为任意两个子矩阵的所有行向量是线性相关 的。如果l d p c 码的监督矩阵是满秩的，则其码率r = k 刀= 1 一m 刀= 1 _ ，k ， 因此g a l l a g e r 的方法构造的l d p c 码码率通常小于r 。这里，我们称由上述方法 可以构造的低密度校验码类为g a l l a g e r 码类。 与此同时，g a l l a g e r 还在参考文献 6 中证明了关于g a l l a g e r 码的两个结论： 第一个是关于最小距离的。对于满足参数( 刀，后) 码全体，必定存在另一个参数万， 随着码长狞的增加，几乎所有码都有最小距离为以万，参数万不随疗的变化而变化。 所以，大多数码的最小距离随着n 线性增加。第二个是关于误比特率的。g a l l a g e r 证明：对于g a l l a g e r 码类，在对称无记忆信道中，采用最大似然译码时，其误比 特率随着码长的增加呈指数形式下降。这两个结论说明g a l l a g e r 码类是相当好的 码类。m a c k a y 和d a v e y 曾指出对任何码长和码率，当平均列重j 3 时，随机构 造的g a l l a g e r 码离现在所知最好的码在零点几个d b 之内。 2 3 2 p e g ( p r o g r e s s i v ee d g e g r o w t h ) 构造 理论上，当码长趋于无穷，并采用最有译码器的情况下，j 下则l d p c 码的性 能可以逼近香农限。然而，当码长很长时，最优译码复杂度太高，实际无法实现。 第二章l d p c 码的定义与编码 1 3 非正则低密度校验码和正则码一样也可以通过它的图模型来描述。记度为f 的变量节点的个数为人，度为，的校验节点的个数为p ，。若非正则码的码长为刀， 码率为r ，则有 力= ，人f ，p j = 刀( 1 一r ) 式( 2 9 ) 类似公式( 2 - 9 ) ，根据t a n n e r 图中按校验节点所连边的数目等于按变量节点 所连边的数目，有 ，认，= ，j p j 式( 2 一l o ) 由变量节点度分布序列 人) 和校验节点度分布序列 p j ) ，定义多项式 人( x ) = f 人，x 和p ( x ) = ，p j x ， 式( 2 1 1 ) 由公式( 2 1 1 ) 有a ( 1 ) = 以，p ( 1 ) = n o r ) ，码率为r = 1 一a ( 1 ) p ( 1 ) 。对a ( x ) 和 p ( x ) 求导可得， = 掣= 玲 ，咐= 掣= ，办川 令石= 1 ，有 人( 1 ) = p ( 1 ) = 总边数 式( 2 - 1 3 ) 从边的角度考虑，定义度分布序列 元) 和 力) ，其中磊为与度为f 的变量节 点连接的边的数目占总边数的比例，岛为与度为j 的校验节点的边的数目占总边 数的比例。类似地定义多项式 由公式( 2 1l 广( 2 - 1 6 ) 有： 允( x ) = ，以x 扣1 式( 2 1 5 ) p ( 石) = _ ，岛z 川 式( 2 1 6 ) 砸) = 端及贴) = 器 通过建立t a n n e r 图可以增大一些经验编码的环长g o 。p e g 构造法就是通过 1 4 基于f p g a 的l d p c 码的实现 预先计算得到的消息节点和校验节点在t a n n e r 图中的重量分布而获得的。在已知 旯( x ) 和p ( x ) 的基础上，建构一个图是采用迭代边到边的步骤来增大局域的环长。 这种制图的结果可以是正则的和非正则的形式，主要取决于重量的分布【l 引。 用p e g 算法构造的中、短码长低密度校验码是当前所知具有相同参数的最好 的低密度校验码之一。在介绍具体的p e g 算法之前，先作一些参数的说明。 假设l d p c 码的聆个变量节点集合为圪= v o ，1 , 10 9 一，) ，m 个校验节点集合 为圪= c o ，c l ，一。 。t a n n e r 图由集合( y ，占) 表示。其中v 是节点的集合， v = 圪u 圪。e 是边的集合，当且仅当岛，0 ，红，h ，0 f m - 1 ，0 j 以- 1 时，边( q ，v ，) e 。假设变量节点的度序列为风= 叱，“，“删) ，其中巩，是变 量节点巧的度。校验节点的度序列为眈= 叱，如，噍删) ，其中如是校验节点c