（通信与信息系统专业论文）一类高码率ldpc码的编译码算法研究与实现.pdf

摘要 摘要 低密度奇偶校验码l d p c 码是首先由g a l l a g e r 在1 9 6 2 年提出的一种纠错码， 在沉寂了多年之后，最近又重新成为通信技术研究的热点。l d p c 码是一种具有 稀疏校验矩阵的线性分组码，研究结果表明，采用迭代的概率译码算法，l d p c 码可以达到接近香农极限的性能。本论文主要对l d p c 码的译码算法和硬件实现 进行了较深入的研究。 本文研究了在高斯白噪声信道下，l d p c 码的几种主要迭代译码算法和复杂 度。这些算法包括：g a l l a g e r 的b f 算法，置信度传播( b p ) 算法，归一化的b p b a s e d 算法等等。给出了一种高码率l d p c 码在不同译码算法下的性能仿真曲线。找出 了一种实现复杂度较低且性能良好的译码算法：n o r m a l i z e db p b a s e d 算法。本文 对l d p c 译码器的关键参数、硬件实现中的量化进行了研究，给出了对译码器硬 件实现具有参考意义的研究结果。 之后讨论了l d p c 码译码器的硬件实现，分析了针对该类高码率l d p c 码译 码实现的硬件实现结构：部分并行结构。这种构造方法不仅能够降低译码器硬件 实现的复杂度，还可以节省一定的硬件开销。并且较详细的介绍了译码器各个模 块的实现方式和结构框图。为了验证该构造方法，利用硬件仿真软件q u a r t u s i i 仿真实现了码长为5 2 9 ，码率为0 8 7l d p c 码译码器。设计采用v e r i l o gh d l 语 言描述，译码器的时钟频率为2 0 m h z ，设置最大迭代次数为1 0 次。 此外，还对该类l d p c 的编码器设计了相应的算法依据，利用该类码校验矩 阵日特定的结构，避免了直接利用生成矩阵对信息位的编码，采用高斯消元以及 二进制的运算完成编码过程。既能降低运算复杂度，又能简化硬件实现的复杂度。 给出了相应编码器的结构框图和仿真波形图。 最后是本文的结论及下一步所需做的工作。 关键词：低密度校验码，软判决译码，半并行译码器，现场可编程门阵列 a b s t r a c t 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 i si n v e n t e db yg a l l a g e rn e a r l y4 0y e a r s a g oa n dh a sb e e nr e d i s c o v e r e d a n dg e n e r a l i z e dr e c e n ty e a r s t h i sk i n do fe r r o r c o r r e c t i n gc o d ec a na c h i e v e n e a rs h a n n o nl i m i te r r o rp e r f o r m a n c ea n dr e p r e s e n tav e r y p r o m i s i n gp r o s p e c tf o r c h a n n e le r r o rc o d i n g l d p cc o d ei sw i d e l yc o n s i d e r e da s n e x t - g e n e r a t i o ne r r o r - c o r r e c t i n gc o d ef o rt e l e c o m m u n i c a t i o na n dm a g n e t i cs t o r a g e t h ed e c o d i n ga l g o r i t h ma n di t si m p l e m e n t a t i o nd e s i g no fas p e c i a ls u b c l a s sl d p c c o d ea r e t h ef o u c sr e s e a r c ha r e ao ft h i sd i s s e r t a t i o n r e g u l a rb 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 m ，o rs l l m p r o d u c ta l g o r i t h m ，c a na c h i e v e g o o dd e c o d ep e r f o r m a n c eb yi t e r a t i v em e s s a g ep r o c e s s i n g b e t w e e nm e s s a g ea n dc h e c k n o d e s b u td u et oi t sh i g hc o m p u t ec o m p l e x i t y , t h e r ec o m eo u ts e v e r a ls i m p l i f i e d d e c o d ea l g o r i t h m ss u c ha sb p - b a s e da l g o r i t h m ，ap o s t e r i o r ip r o b a b i l i t y ( a p p ) b a s e d a l g o r i t h m t h e yr e d u c ed e c o d ec o m p l e x i t yb ys i m p l i f y i n g t h ep r o c e s si ne i t h e rb i t n o d e so rc h e c kn o d e sa tt h ee x p e n s eo fp e r f o r m a n c ed e g r a d a t i o n h o w e v e r , b y i m p r o v i n gt h eb p b a s e da n da p p - b a s e da l g o r i t h m sb yn o r m a l i z a t i o n ；i tc a na c h i e v e b e t t e re r r o rp e r f o r m a n c ew h i l ei n c r e a s el i t t l ed e c o d i n gc o m p l e x i t y t h i sp a p e ri n t r o d u c e sac l a s so fh i 曲r a t el d p cc o d e ，a n dt h e nc o m p a r e s d e c o d i n gc o m p l e x i t i e sa n dp e r f o r m a n c e so fd i f f e r e n td e c o d ea l g o r i t h m s ，a c c o r d i n gt o t h er e s u l t s ，o n ea l g o r i t h mw i t hg o o dp e r f o r m a n c ea n dl e s sc o m p l e x i t yi sc h o s e n a f t e rt h ed i s c u s s i o no ft h ea r c h i t e c t u r e so ft 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 c d e c o d e r , t h ep a r t l yp a r a l l e la r c h i t e c t u r ei ss u i t a b l ef o rr e a l i z a t i o n t od e m o n s t r a t et h i s j o i n td e s i g nm e t h o d o l o g y , af p g ai m p l e m e n t a t i o no f c o d el e n g t h5 2 9 ，c o d er a t eo 8 7 r e g u l a rl d p cc o d ei sr e a l i z e d e v e r ym o d u l eo ft h ed e c o d e ri si n t r o d u c e di nc h a p t e r f o u r , t h ew h o l ed e s i g ni sd e s c r i b e di nt h ev e r i l o gh a r d w a r ed e s c r i p t i o nl a n g u a g e ( h d l ) w i t hm a x i m u m10d e c o d i n gi t e r a t i o n s ；a n dt h ew o r kc l o c ko ft h ed e c o d e ri s2 0 m h z b e s i d e s a c c o r d i n gt ot l l es p e c i a ls t r u c t u r eo ft h i s s u b c l a s so fl d p cc o d e , t h i s a r t i c l ep r e s e n t e da ne f f e c t i v ee n c o d ea l g o r i t h m ，i tc a nm a k et h el i n e a rc o m p l e x i t yo f e n c o d ep r o c e s sp o s s i b l e k e y w o r d s ：l d p cc o d e s ，b e l i e fp r o p a g a t i o n ，p a r t l yp a r a l l e la r c h i t e c t u r e ，f p g a i i 图表目录 图表目录 图1 1 典型数据传输系统框图1 图1 2 作为码率r 的函数的香农限一4 图2 1 ( 8 ，2 ，4 ) l d p c 码的二分图1 1 表3 1 每个变量节点对应的不正确的校验式的个数1 6 图3 1 o ( x ) 曲线图2 2 表3 2 概率域b p 算法一次迭代的复杂度2 5 表3 3 对数域b p 算法与b p b a s e d 算法一次迭代的复杂度2 5 表3 4n o r m a l i z e db p b a s e d 算法一次迭代的复杂度2 5 表3 5o f f s e tb p b a s e d 算法一次迭代的复杂度2 5 图3 2 译码算法仿真流程图2 6 图3 3l d p c 码在a w g n 的性能比较( 短码) 2 7 图3 4l d p c 码在a w g n 的性能比较( 中长码) 2 7 表3 6l d p c 码的参数2 8 图3 5 ( 5 2 9 ，4 6 0 ) l d p c 码的译码算法曲线2 8 图3 6 ( 2 2 0 9 ，2 0 2 1 ) l d p c 码的译码算法曲线2 8 图3 7 ( 4 4 8 9 ，4 15 4 ) l d p c 码的译码算法曲线2 9 图3 8 ( 7 9 2 1 ，7 3 8 7 ) l d p c 码的译码算法曲线2 9 图4 - 1h d l 设计平台和步骤3 2 图4 _ 2l d p c 译码器顶层框图。3 4 表4 1l d p c 项层信号定义表3 4 图4 3 译码器结构框图3 5 图4 4l d p c 码校验矩阵3 7 图4 5l d p c 码部分并行译码器结构3 8 图4 6 量化电平与码元可信度的关系4 0 表4 2 信道转移概率及初始化信息表4 1 图4 7 输入缓冲寄存器写控制仿真波形4 4 图4 8v n u 数据流向4 5 图4 - 9v n u 内部算法数据流向4 6 v i 图表目录 图4 1 0 采用简化b p 译码算法的c n u 结构框图4 8 图4 1 1 首地址为0 的地址发生器仿真波形5 0 图4 1 2 首地址为2 的地址发生器仿真波形5 0 图4 1 3e x tr a m ，v n u ，c n u ，以及地址发生器之间的关系5 1 图4 1 4 译码输出缓存模块读使能时序5 2 图5 1l d p c 码编码器结构框图5 5 图5 2l d p c 编码器仿真波形图5 5 图5 3l d p c 译码器仿真波形5 7 v l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 日期：眸么月乃日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期：伽肄铜。日 第一章引言 1 1 通信系统及差错控制策略 通信的目的是把对方不知道的消息及时可靠的传送到对方。但在数字通信系 统中，可靠和快速往是一对矛盾。若要求快速，则必然使得每个数据码元所占的 时间缩短、能量减小，从而在受到干扰后产生错误的可能性增加，传送消息的可 靠性减低。若要求可靠，传送消息的速率就必须变慢。因此，如何合理的解决可 靠性与速度这一对矛盾，是正确设计一个通信系统的关键问题之一。纠错编码正 是在解决这对矛盾的过程中不断发展起来的。 1 9 4 8 年，香农在一篇具有里程碑意义的论文中f 1 1 证明，只要信息传输速率低 于信道容量，通过对信息适当进行编码，可以在不牺牲信息传输或存储速率的情 况下，将有噪信道或存储媒质引入的差错减到任意低的程度。自从香农的著作发 表以来，人们为了在噪声环境下控制差错而在设计有效的编译码方法方面做出了 大量的努力。近年来的发展趋势是实现目前高速数字系统所要求的可靠性，差错 控制编码的应用已经成为现代通信系统不可分割的一部分。 一个典型的传输系统可以用图1 1 所示的框图表示， 图1 - 1 典型数据传输系统框图 a ) 信源产生待传送的信息，被传送到目的地的信源输出可以是连续波形，也 可以是离散的符号序列。 电子科技大学硕士学位论文 b ) 信源编码器将信源的输出转换为二进制数字序列，即信息序列。对于连 续信源，该过程还包括模拟数字转换。 c ) 信道编码器将信息序列变换成离散的编码序列l ，称之为码字。 d ) 离散符号并不适合在物理信道上传输。调制器将信道编码器输出的每个符 号转换为适合传输的波形。 e ) 信道是对传送信号的物理介质的抽象。 0 接收机从信道接收波形信号并对信息进行重建。相对于编码序列p ，解调 器的输出序列称为接收序列，。 曲信道译码器将接收序列，变换为二进制序列五。噪声可能导致译码错误的 出现。但在理想情况下，五将是信息序列“的重现。 h ) 信源译码器将信息序列五变换为对信源输出的估计，并将该估计序列传送 到信宿。当信源为连续信源时，这一过程还包括数字模拟转换。 信源产生的原始数字序列是无法直接检测和纠正错误的，我们需要在序列中 添加冗余的信息，利用它们进行检错和纠错。纠错编码在数字通信中的作用，就 是检测和纠正传输错误，我们使用纠错码的目的就是要在添加尽可能少的冗余度 的同时，最大化的提高通信系统的抗干扰能力。 图1 1 所示的框图代表了一个单向通信系统。传输严格地按照从发送端到接 收端一个方向进行。单向系统的差错控制策略须采用前向纠错( f o r w a r de r r o r c o r r e c t i o n ，f e c ) ，即利用纠错码在接收端自动地纠正检出的错误。当前大多数的 编码系统都采用某种形式的f e c 。 在某些情况下，传输系统可能是双向的。即发送端也可以作为接收端，反之 亦然。双向系统的差错控制策略同时采用错误检测和重传，被称为自动请求重传 ( a u t o m a t i c r e p e a t r e q u e s t ，a r q ) 。在a r q 系统中，当接收端检测出错误时，就 像发送端送出要求重传该消息的请求，直到接收端认为接收正确为止。a r q 系统 中检错对译码设备的要求比纠错简单。同时，从信息只在出现错误的时候才被重 传的意义上来说，它是一个自适应系统。但当信道的错误率较高时，重传将会过 于频繁。在这种情况下，用f e c 纠正最经常出现的错误信息，同时对不常出现的 错误信息采用检错和重传的混合机制比仅使用a r q 的效率更高。这种混合纠错 方式是上述两种纠错方式的结合和折衷。在实际通信系统中，也有广泛的应用。 2 第一章引言 1 2 性能的衡量 一个编码通信系统的性能通常用译码错误的概率，即误码率( e r r o r p r o b a b i l i t y ) ，和相对于具有相同传输速率的非编码系统的编码增益( c o d i n gg m n ) 来衡量。比特的误码率定义为译码器输出的译码信息比特发生错误的概率，称为 误比特率( b i t e r r o rr a t e ) 。在诸如功率、带宽、译码复杂度等特定系统限制条件 下，设计的编码通信系统应使这两种误码率尽可能的低。 在一个码率为r = k n 的编码系统中，为传输每个信息比特需要传输符号( 或 信号) 的数目为1 r 。若每个信息比特对应的能量最为： e = 巨r ( 1 - 1 ) 一个编码系统的误码率通常用单位信息比特的能量e 与信噪声的单边功率 谱密度n 的比值的形式来表示。 编码系统的另一个性能衡量质变是编码增益。编码增益的定义如下：为获得 一个特定的误码率，编码系统所需e n 比非编码系统的减少值。获得额外的编 码增益的代价是更高的译码复杂度开销。在每分贝的性能提高都将减少整个系统 开销的通信应用中，编码增益显得十分重要。 在为差错控制而设计编码通信系统时，总希望获得特定误码率所对应的单位 信息比特能量与噪声功率密度的比值( s i g n a l t o n o i s er a t i o ，s n r ) 值尽量小。根据 香农的有噪信道编码定理 1 】，可以推导出一个码率为r 的编码通信系统达到无误 码传输状态( 或任意小的误码率) 所必须的最小s n r 的理论极限。这个理论极限 通常称为香农限，它说明对一个码率为r 的编码通信系统，只有当s n r 超过这 个极限值时才可能获得无误码传输。对采用b p s k ( b i n a r yp h a s es h i f tk e y i n g ) 信号 的在二进制输入，连续输出的高斯( a 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 ) 信道上 的传输，香农限( 用e 0 表示) 作为码率r 的函数没有显示表达，但是它可以 用数值的方法进行计算。图1 2 以码率r 的函数的方式，表示了采用b p s k 信号， 连续输出的a w g n 信道上的香农限。从图中可以对给定的码率确定香农限。 电子科技人学硕+ 学位论文 图1 - 2 作为码率r 的函数的香农限 接下来，本文将把讨论范围局限于前向纠错方式。在采用此纠错方法时，纠 错码的选择及其编码，译码器的设计是决定纠错能力的最重要的因素，这也是信 道编码研究的主要内容。 1 3 信道纠错码的发展 香农信道编码定理肯定了逼近香农限的编码方案的存在，但并未说明具体的 符合要求的编码方案。虽然仅仅是一个编码存在性定理，但却推动了信道编码理 论以及数字通信系统的飞跃发展。为了找到逼近香农限的编码方案，上世纪五十 年代到六十年代初，人们相继研究了两大类纠错编码：线性分组码和卷积码。线 性分组码以代数中的群论、域论等理论为数学基础，他们的译码方法通常是大数 逻辑和捕错译码。卷积码在编码过程中引入了寄存器，增加了码元之间的相关性， 在相同复杂度的条件下可以获得比分组码更高的编码增益。卷积码的译码算法主 要有序列译码算法和维特比( v i t e r b i ) 算法。实际应用中，无论是分组码还是卷积 码大多采用短码，因为它们的译码复杂度与码长成指数关系，随着码长的增加， 译码的计算量随之成指数级增加，基本不可能实用。令人失望的是，要达到香农 限，纠错码的码长必须足够长，所以上述的短码都难以达到逼近香农限的目标。 到了上世纪八十年代到九十年代初，经过不断的研究和实践，纠错编码理论 4 第一章引言 和技术取得了突破性的发展。1 9 9 3 年，c b e r r o u 等人在i c c 9 3 会议上提出了t u r b o 码的构想【2 ，它巧妙的将卷积码和随机交织器结合在一起，实现了随机编码的思 想。采用软输入、软输出的迭代译码算法，这种编码能够在码长较长时逼近香农 的理论极限。日前较为流行的t u r b o 码译码算法主要有：m a p 算法、l o g m a p 算法、m a x l o g m a p 算法和s o v a 算法。仿真结果表明，在a w g n 信道和b p s k 调制下，如果采用6 5 5 3 5 的随机交织器，并且进行1 8 次迭代，则在最0 0 7 d b 时，码率1 2 的t u r b o 码的误比特率( b e r ) 1 0 ，逼近了香农限的性能。这一超 乎寻常的优异性能，立即引起信息论与编码学界的轰动。 t u r b o 码的发现，标志着信道编码理论与技术的研究进入了一个崭新的阶段， 它结束了长期将信道截止速率作为实际容量限的历史。t u r b o 码的提出，更新了 编码理论研究中的一些概念和方法。现在人们更喜欢基于概率的软判决译码方法， 而不是早期基于代数的构造与译码方法，而且对编码方案的比较也发生了变化， 从以前的相互比较过渡到现在的均与s h a n n o n 限进行比较。这在某种程度上，也 使得编码理论家变成了实验科学家。尽管目前对于t u r b o 码的作用机制尚不十分 清楚，对迭代译码算法的性能还缺乏有效的理论解释，但它无疑为通过信道编译 码最终达到s h a n n o n 信道容量开辟了一条新的途径，其原理思想在相关研究领域 中具有广阔的应用前景。t u r b o 码被看作是1 9 8 2 年t c m 技术问世以来，信道编 码理论与技术研究上所取得的最伟大的技术成就，具有里程碑的意义。 在t u r b o 码获得巨大成功的启发下，另一种具有相似特性的纠错码复活了， 这就是低密度奇偶校验( l d p c ) 码。l d p c 码是g a l l a g e r 码的推广，1 9 6 2 年，g a l l a g e 在 3 】中提出了一种编码，现在通常称为g a l l a g e r 码，这种编码由于校验矩阵的稀 疏性，使得译码的复杂度与码长成线性关系，当码长较长时，仍然可以进行有效 的译码。然而当时人们普遍认为级联码更容易实现，忽视了g a l l a g e r 码的存在。 d j c m a c k a y 、m n e a l 和n w i b e r g 等人对g a l l a g e r 码重新进行了研究，发现 g a l l a g e r 码性能较t u r b o 码略有差距，但同样具有逼近香农限的性能。在g a l l a g e r 码的基础上，他们进一步研究了多元域上的l d p c 码 3 】，发现多元域上的g a l l a g e r 码较二元域上的码的性能有较大提高。m g l u b y 和m m i t z e n m a c h e r 等人从另一 个角度对g a l l a g e r 码进行了推广，提出非正则l d p c 码【4 】，这种纠错码的性能能 够赶上甚至超过t u r b o 码。 l d p c 码和t u r b o 码有许多相似的地方，在它们的构造方法中存在许多随机 排列的元素，表现出随机码的特性。此外，两者的译码算法也存在着相似性。 n w i b e r g 在他的博士论文 5 】中，构建了迭代译码算法的一个通用结构，通过研究， 电子科技大学硕士学位论文 n w i b e r g 发现l d p c 码的迭代译码算法和t u r b o 码的迭代译码算法都可以用这一 通用结构解释。l d p c 码的迭代译码算法是基于可信度传播的，m c e l i e c e 、m a c k a y 和c h e n g 在【6 】中认为t u r b o 码的迭代译码算法可以看作可信度传播算法( b e l i e f p r o p a g a t i o n ) 7 的一个特例。 1 4l d p c 概述 l d p c 码最早是麻省理工学院的r g g a l l a g e r 于1 9 6 3 年发明的 8 】 9 】。在其博 士论文 8 】中，g a l l a g e r 提出了规则l d p c 码的构造方法、编译码算法以及最小汉 明距离分析和译码算法的性能分析。由于当时的条件限制，编译码器的硬件实现 几乎是不可能的；同时，因为没有足够计算能力的计算机，所以精确细致的仿真 也不能实施，g a l l a g e r 只能给出高于1 0 4 的误码率。由于这些原因，尽管l d p c 码有很好的纠错能力，但仍然被人们忽略了3 0 多年。自从1 9 9 5 年m a c k a y 发表 文章 1 0 】使得l d p c 码被重新认识以来，许多研究人员都投入到l d p c 码的研究 之中，从1 9 9 9 年开始这方面的研究文献大量出现。经过几年的研究，l d p c 码的 理论和应用研究取得了不小的进展，还有一些工作正在进行，下面从几个方面介 绍一下l d p c 码的研究成果和主要研究方向。 1 4 1l d p c 码的编、解码 l d p c 码所面临的一个主要问题是其较高的编码复杂度和编码延时。如果采 用普通的编码方式，l d p c 码具有二次方的编码复杂度，在码长较长时这是难以 接受的。t j r i c h a r d s o n 和r l u r b a n k e 在文献 1 1 q h 给出了一种利用校验矩阵的 稀疏性对校验矩阵进行一定的预处理后，在线性时间内编码的有效算法，初步解 决了l d p c 码编码的复杂度问题。s l i n 等在【1 2 】中提出一种具有循环码特性的 l d p c 码，它同样具有稀疏的校验矩阵，编码可以通过线性移位反馈寄存器来完 成，实现了具有线性复杂度和线性延时的编码。l d p c 码的译码算法是影响其性 能的一个重要因素。研究发现，在理想的编码条件下，即编码结构中没有闭合环 路时，b p 算法与最大似然译码算法效果一致。但是，在码长有限的情况下闭合环 路的存在是必然的，这时b p 算法与最大似然算法有一定的差距。如何在不造成 过高译码复杂度的情况下，缩小这个差距是l d p c 码的一个研究课题。硬判决算 法虽然性能比b p 算法差，但译码复杂度很低，适合在光纤通信等信道条件较好 6 第一章引言 的系统中应用。针对硬判决译码算法的改进也同样引起人们的兴趣。另一方面， 针对非高斯的低质量信道上译码算法的研究也已经展开，如瑞利衰落信道、部分 响应信道、和i s i 信道等【1 3 【1 4 1 5 】。 1 4 2l d p c 码的设计方法 中、短码长的l d p c 码，如果编码结构中有较短闭合环路存在，会大大降低 性能，因此在构造l d p c 码时必须避免较短闭合环路的出现。现有的构造方法主 要有两种：一种是进行类似构造随机码那样的大范围搜索。搜索方法是根据 r i c h a r d s o n 等人提供的局部优化和全局优化搜索方法 1 6 ，它们的搜索量相当大， 需要借助计算机完成，更完善有效的搜索算法有待进一步的研究；另一种l d p c 设计方法是利用一些己有的数学结论进行构造，主要有组合构造法 1 7 、有限几 何构造法 1 2 】、群论构造法 1 8 】和图论构造法 1 9 】。 通过上述方法构造的l d p c 码的校验矩阵中非零元素分布具有随机性，译码 器不具备采用部分并行结构的条件，实用性较差。为了解决这一问题，文献 2 0 1 提出一种从译码角度考虑的l d p c 码构造方法( d e c o d e r - f i r s tc o d ed e s i g n ) ，这种码 的译码器可以采用部分并行结构，但译码器设计中仍然具有很多随机数发生器， 真正实现时复杂度还是很高，同时它的编码器实现也比较复杂。针对这一领域的 研究方兴未艾，拥有广阔的前景。 1 4 3l d p c 码的实现和应用 除了f l a r i o n 公司推出了基于f p g a 和a s i c 的l d p c 编、解码器外，基于 d s p 的l d p c 编、解码器也已经研制成功 2 1 】。同时，由于l d p c 码性能的优越 性，使其有望在通信中得到广泛的应用。日前在第四代移动通信中使用l d p c 码 的提案己经提交；而l d p c 码在d s l 、a d s l 2 2 、深空通信及磁记录介质【2 3 等 信道上的研究正在展开；此外在与t c m 基于l d p c 的时空硬- q 2 4 等与其他技术结 合方面的研究也在进行中。 1 5l d p c 的研究意义 和另一种近s h a n n o n 限的码- t 1 曲0 码相比较，l d p c 码主要有以下几个优势： 7 电子科技大学硕十学何论文 幻l d p c 码的码率构造有更大的灵活性。l d p c 码可以达到0 7 、0 8 甚至0 9 的码率，而t u r b o 码只能通过打孔来达到高码率，这样打孔 图案的选择就需要慎重的考虑，否则会造成性能上较大的损失。 b ) 译码速率快。l d p c 码基于可信度传播的译码算法本质上是并行算 法，有利于硬件的并行实现，可以达到很高的译码速度。例如，f l a r i o n 技术公司已开发了l d p c 编、译码器产品，称为v e c t o rl d p c 。采用 f p g a 实现，时钟频率1 0 0 m h z ，码长l = 1 0 0 0 0 码率r = 0 9 编码器利 用6 4 k 逻辑门和1 3 k b 存储器时，编码速率可达1 9 g b p s ；译码器使 用3 2 0 k 逻辑门和3 8 k b 存储器时，译码速率为3 8 4 m b p s 。采用a s i c 实现，时钟频率3 2 5 m h z 码长l = 5 0 0 0 0 码率r = 0 9 ，译码器使用2 6 m 逻辑门和1 9 0 k b 存储器时，可工作在1 0 g b p s 。 c ) 不可检测错误少。由于l d p c 码码字之间的码距较大，使得已译码 过程中出现不可检测错误的概率很小。 d ) 发生“平板效应”( e r r o r - f l o o r ) 的概率低。随着信噪比的增加，t u r b o 码误码率的下降趋势将趋于平缓，即出现所谓的“平板效应”。但是 l d p c 码发生这种现象的概率低得多，这使得l d p c 码在深空通信或 光纤通信中更具优势。 e ) 理论分析简单。不同于t u r b o 码，l d p c 码有简单的数学模型，理论 分析相对简单。目前，对l d p c 码的译码性能分析己经有了一些较 为完善的理论，但t u r b o 码的性能还缺乏有效的理论解释。 0 l d p c 码可以采用基于硬判决的迭代算法，虽然性能比软判决差，但 实现复杂度很低。t u r b o 码译码在迭代时必须传递软信息，因此无法 使用硬判决算法。 曲由于校验式的存在，使得l d p c 码的译码过程中能够确定码字是否 正确，这样不仅可以省掉c r c 编码，而且可以采用动态中止算法来 减少迭代次数。l d p c 码的译码算法，是一种基于稀疏矩阵的迭代译 码算法，运算量要低于t u r b o 码译码算法，并且由于结构并行的特点， 在硬件实现上较容易。 而l d p c 码的劣势在于： 1 ) 编码复杂度高。虽然最新的研究表明l d p c 码可以在线性时间内编 码，但其复杂度相对于t u r b o 码来说仍然过大，更加无法和卷积码等 即时编码的纠错码相比。 第一章引言 2 1 中短码长的l d p c 码性能不理想。l d p c 码性能的优越性通常在码长 较长时才能体现，当采用中、短长度的l d p c 码时，由于编码时短 长度闭合环路的存在，会在某种程度上降低译码性能。 3 ) 低码率情况下性能不理想。由于低码率的纠错码抗衰落的性能较好， 因此大多数移动通信系统采用码率较低的纠错码，但是低码率l d p c 码的性能与t u r b o 码相比处于下风。 4 1 当l d p c 码译码器采用全并行结构时，虽然译码速率很高，但硬件 资源消耗太大。实际应用中更可能采用的方案是部分并行结构，目前， 适用于部分并行结构的l d p c 码的构造方法还不完善。 5 )相对而言出现比较晚，工业界支持还不够。 t u r b o 码已成为第三代蜂窝无线移动通信系统三种标准的选用方案。在 d v b s 2 系统中，l d p c 码也已成为标准；同时在目前1 0 g b p s 以太网标准的制定 中，l d p c 码也受到了极大的关注。可以预见在未来的1 0 年以内，t u 曲。码和l d p c 码的竞争依然会延续下去。 1 6 本文的主要内容 本论文选择一类适合d s l 传输的高码率l d p c 码作为主要研究方向，仿真了 该类l d p c 码在a w g n 信道下不同译码算法的性能。并研究讨论了该类l d p c 码编译码的硬件实现。 论文共分六章，本章为绪论，简单介绍了l d p c 码的发展、研究现状和优缺 点。 第二章详细阐述了l d p c 码的一些基本理论，包括l d p c 码的二分图结构和 l d p c 码的闭合环路，同时基于不同的方面对l d p c 码进行分类。 第三章中，讨论了l d p c 的主要译码算法，并给出了该类l d p c 在不同译码 算法下的误码率仿真结果。 第四章介绍了l d p c 译码器的f p g a 设计，在本章内对l d p c 译码器的总体 框图，以及系统中各个模块的具体功能和实现方法都做了详细介绍。 第五章是l d p c 译码器的仿真结果和对设计中一些问题的处理，本章还介绍 了l d p c 编码器的结构。 第六章总结全文，讨论下一步的工作和需要解决的问题。 9 电子科技大学硕士学位论文 第二章l d p c 码的简介 低密度奇偶校验码本质上是一种线形分组码，它通过一个生成矩阵g 将信息 序列映射成发送序列，也就是码字序列。对于生成矩阵g ，完全等效的存在一个 奇偶校验矩阵日，所有的码字序列 ，构成了h 的零空间，即v h 7 = 0 。 g f ( 2 ) 域上的l d p c 码c 是一种线性分组码( 咒，助，码长为n ，信息序列长度 为k ，可以由其校验矩阵日唯一定义。h 的维数是m x ”，每一行对应一个校验方 程，每- y t 对应码字的一位。每一行中非零元素的个数称为行重，每一列中非零 元素的个数称为列重。相对于行与列的长度，校验矩阵行重、列重非常小，这也 是l d p c 码之所以称为低密度码的原因。式2 1 是一个5 x 1 0 的校验矩阵及其对 应的校验方程，其中码字c = ( c l ，乞，c 3 ，c 4 ，c 5 ，c 6 ，c 7 ，c 8 ，c 9 ，c 1 。) ，满足日c r = o 。 日= 11 1o ol o 0 1o 0 o 01 11 o0 11 10 o1 lo 01 1o o1 如果校验矩阵日是满秩的，则m = n k ，码率，为伽一m ) m 。有时矩阵日的 行不是线性无关的，此时日的秩小于m ，即m ，1 k ，码率， 1 一m n 。 由于校验矩阵日的稀疏性以及构造时所使用的不同规则，使得不同l d p c 码 的编码二分图( t a n n e r 图) 具有不同的闭合环路分布。而二分图中闭合环路是影 响l d p c 码性能的重要因素，它使得l d p c 码在类似可信度传播( b e l i e fp r o p a g a t i o n ) 算法的一类迭代译码算法下，表现出完全不同的译码性能。 当日的行重p 和列重) ，保持不变或尽可能的保持均匀时，我们称这样的l d p c 码为正则l d p c 码，反之如果列、行重变化差异较大时，称为非正则的l d p c 码。 l u b y ，m i t z e n m a c h 等在文献 2 5 】中证明了正确设计的非正则l d p c 码的性能要优 于正则l d p c 。根据校验矩阵h 中的元素是属于o r ( 2 ) 还是g f ( q ) ( q = 2 p ) ，我们 还可以将l d p c 码分为二元域或多元域的l d p c 码。文献 3 】的研究结果表明，多 元域l d p c 码的性能要比二元域的好。正是因为l d p c 码的校验矩阵非常稀疏， 它的码字还具有较大的最小码间距和较好的码间距离分布，这一点可以和完全随 机构造的，即o 和1 等概分布的校验矩阵所决定的线性分组码相比较。下面将分 1 0 d 一2 ，- 0 0 0 o = = = = 白珞勿珞 + + + + 白岛靠 + + + + 勿岛厶以 + + + + q q 乞q 第二章l d p c 码的简介 别讨论l d p c 码的上述几个重要特性。 2 1l d p c 码f l 勺- - 分图结构 对于任何一种线形分组码，t a n n e r 在【2 7 中提出了种简单的表示形式：编 码二分图( t a n n e r 图) 。l d p c 码的二分图由两类节点组成：变量节点( v a r i a b l e n o d e ) 和校验节点( c h e c kn o d 0 ，分别对应于校验矩阵日中的n 列和m 行。同一个集合 内部的节点没有连线，只有属于不同集合的两点之间可能有连线，每一条连线对 应于校验矩阵中的1 。为了方便，我们借用g a l l a g e r 对l d p c 码的表示方法： 将码长为行重、列重分别为p 和) ，的l d p c 码称为( ，) ，p ) l d p c 码。式2 1 是某( 8 ，2 ，4 ) l d p c 码的校验矩阵和相应的校验方程，根据校验矩阵我们可以画出 它的二分图( 图2 - 1 ) 。图中变量节点集合( m ，屹，匕，y 4 ，屹，v 7 ，) 和校验节点集合 ( c 1 ，c ，b ，c 。) 内部不存在相连的边，但两类节点之间存在着连线。变量节点和校验 节点之间存在连线意味着该变量比特参加了此校验式，也就是校验矩阵某一行中 1 的位置。我们将每个节点上的连线数日称为该节点的度数( d e g r e e ) ，图2 1 中，变量节点的度数( d ，) 为2 ，校验节点的次数( d ，) 为4 。 式2 1 所对应的二分图如图2 1 所示，四条粗线构成了一个有向的闭合环路， 由k 起始，经过c 1 寸屿一g 最后返回v 2 。在一个l d p c 码的二分图中，每个节点 都会存在许多这样的闭合环路，我们将其中长度最小的一个称为该节点的最小环 长( s h o r t e s tc y c l o 。二分图中所有节点的最小环长中，长度最小的称为二分图的最 小围长( 西n h ) ，上例的二分图中，曲咀l 与变量节点2 的最小环长相等，都是4 。 图2 1 ( 8 ，2 ，4 ) l d p c 码的二分图 电子科技大学硕十学位论文 l d p c 码二分图结构中g i r t h 的大小对l d p c 码的译码性能有很大影响。 t a n n e r 2 4 认为g i r t h 的长度将直接关系到l d p c 码码字的最小码距。仿真结果表 明，如果二分图中存在长度为4 的g i r t h ，l d p c 码的误码率性能将会很差，所以在 构造l d p c 码的校验矩阵时，要尽