（通信与信息系统专业论文）ldpc码编译码算法的研究.pdf

中国科学技术大学硕士学位论文 摘要 l d p c ( l o wd e n s i t yp a r i t yc h e c k ) 码是一种具有稀疏校验矩阵的线性分组t t t a 码，其逼近 香农极限的优异性能和在信息可靠传输- i 的良好应用前景( 如深空通信、第四代移动通信系统、 高速与共高速数字用户线、磁记录系统等) ，已引起各困学术界和i t 业界的广泛关注。但是采 用常用的分组编码方法会严重破坏校验矩阼的稀疏性，导致l d p c 码编码复杂度的增加：而且 由于译码器实现过程中的各种约束条件，使得译码算法的复杂度也钉待于进。步的降低。本论 文的目的是研究采用线性时问l d p c 编码方法的硬件实现，以及如何降低译码算法的复杂度。 本文的研究工作主要分为以下两个部分： 第。分析了常用的系统分组码编码复杂度的问题。对于常用的编码方法，l d p c 码具有很 高的编码复杂度，而采用准下三角校验矩阼的编码方法则可以实现线性时i 日j 编码。利用r u 算 法可以行效的将检验矩阵变换为准下三角阼而1 i 改变校验矩阼的稀疏性。针对r u 算法，设计 出- 种编码器的硬件实现，推导出了相心的结构和运算单元，以及反映编码器性能的参数。由 最终编码器参数值可知，采用r u 算法进jj ：预处理的l d p c 编码器，灵活性高，编码时延小， 所耗资源少，可以在线性时i n j 内完成编码。 第_ 介绍了l d p c 码译码算法，算浊i - 需要用查找表来近似算法l l j f j 到的t a n h 函数。但 是采用这种方法会降低译码的吞吐率。为此推导基于b c j r 算法的简化复杂度的洋码算法，对 算法- l - 的纠正函数给出了各种近似方法，比较和分析了这些4 i 同近似方法。上述的算法简化了 运算单元的计算复杂度，本文接着提出了。种简化迭代过程复杂度的门限译码算法。最后给出 了l d p c 码译码算法的计算机仿真和分析。仿真结果表明，所提出了算法可以有效的降低译码 复杂度。 l d p c 码由于其性能的优越性及数学分析上的相对简单性，引起了编码界的广泛兴趣。对 l d p c 码的数学模型一二分图的研究又给其它的编码带来了新的血液，引起了对诸如t u r b o 码 等其它编码的再认识。相信这样种具自卓越性能及简单数学结构的编码必将再理论上自更进 步的发展并再实际i 一得到广泛的应用。 关键_ 宁l d p c 码贪心算法编码器硬件实现简化复杂的译码算法 2 中国科学技术大学硕士学位论文 a b s t r a c t l d p c ( l o wd e n s i t yp a r i t yc h e c k ) c o d e ，al i n e a rb l o c ke r r o rc o r r e c t i n gc o d e ，w h i c hh a sas p a r s e c h e c km a t r i x ，h a sae x c e l l e n tp e r f o r m a n c eo fc l o s i n gt os h a n n o nl i m i ta n dag o o dp r a c t i c a i f o r e g r o u n di nt h es t a b l ei n f o r m a t i o nt r a n s m i s s i o n t h i sm a k e st h i sc o r r e c t i o nc o d ew i d e l yn o t i c e db y a c a d e m i e sa n di ti n d u s t r ya l lo v e rt h ew o r l d b u tt h et r a d i t i o n a la p p r o a c h e so fb l o c ke n c o d i n gw i l i d e s t r o yt h es p a r s ec h a r a c t e r i s t i c so ft h ec h e c km a t r i xs e v e r e l ya n dw i i lc a u s et h ei n c r e a s eo ft h e c o m p l e x i t yo fe n c o d i n gp r o c e d u r e f u r t h e r m o r e ，t h el i m i t a t i o no fd e c o d i n gi m p l e m e n tp r e s e n t st h e r e q u i r e m e n to fl o wc o m p l e x i t ye n c o d i n ga l g o r i t h m i nt h i sp a p e r , w ef o c u so nt h er e s e a r c ho ft h e h a r d w a r ei m p l e m e n to fl i n e a rt i m el d p ce n c o d i n gm e t h o d a n dh o wt or e d u c et h ec o m p l e x i t yo f d e c o d i n ga l g o r i t h m r e s e a r c hi nt h i sp a p e ri sd i v i d e di n t ot w op a r t s ： f i r s t l y 。d i s c u s s e da ni m p o r t a n tp r o b l e mi nt h ea p p l i c a t i o no fl d p cc o d e s t h a ti sh o wt oo v e r c o m et h e c o m p a r a t i v e l yh i g hd e c o d i n gc o m p l e x i t y ，a n dp r o p o s e dr ua l g o r i t h m ，w h i c hp e r f o r m se n c o d i n g u s i n gt h es p a r s ep r o p e r t yo fl d p cc o d e sc h e c km a t r i x b a s e do nt h i sa l g o r i t h m ，d e s i g n e dak i n do f h a r d w a r ei m p l e m e n t a t i o no fe n c o d e r , a n dd e d u c e dt h ec o r r e s p o n d i n gs t r u c t u r ea n do p e r a t i o nu n i ta n d t h ep a r a m e t e rt h a td e m o n s t r a t e st h ep e r f o r m a n c eo fe n c o d e r t h r o u g ht h ef i n a ie n c o d e rp a r a m e t e r , i t c a nb ec o n c l u d e dt h a tl d p ce n c o d e rt h a tp e r f o r m sp r e t r e a t m e n tu s i n gr ua l g o r i t h mi sm o r ef l e x i b l e h a sas h o r ti a t e n c y n e e di e s sr e s o u r c ea n dc a nf i n i s he n c o d i n gi nl i n e a rt i m e s e c o n d a r i l y l d p cd e c o d i n ga l g o r i t h mi si n t r o d u c e d w h i c hn e e d st oa p p r o x i m a t et h et a n h f u n c t i o n u s e di n t h i sa l g o r i t h mb yl o o k i n gu pt h ed a t a b a s e i no r d e rt oa v o i dt h er e d u c t i o no fd e c o d i n g t h r o u g h p u to ft h i st r a d i t i o n a la l g o r i t h m ，ac o m p l e x i t ys i m p l i f i e dd e c o d i n ga l g o r i t h mw h i c hb a s e do i l t h eb c j ra l g o r i t h mi se l a b o r a t e d a n ds o m ea p p r o x i m a t e dm e t h o d so fc o r r e c t i n gf u n c t i o na r e p r e s e n t e d , a n a l y z e da n dc o m p a r e dw i t he a c ho t h e r i na d d i t i o n at h r e s h o l d d e c o d i n ga l g o r i t h mw i t h s i m p l i f i e di t e r a t i v ep r o c e d u r ei sb r o u g h tf o r w a r d i nt h ee n d t h e r ea r ec o m p u t e rb a s e ds i m u l a t i o na n d a n a l y s i so fl d p ce n c o d i n ga l g o r i t h m w i t ht h es i m u l a t i o nr e s u l t s w ec a nd r a wt h ec o n c l u s i o nt h a t t h ep r e s e n t e da l g o r i t h mc a nr e d u c et h ed e c o d i n gc o m p l e x i t ye f n c i e n t l y k e y w o r d s ：l d p cc o d e s ，g r e e d ya l g o r i t h m ，h a r d w a r ei m p l e m e n t a t i o ne n c o d e r ， r e d u c e d c o m p l e x i t yd e c o d i n ga l g o r i t h m 3 中国科学技术大学硕士学位论文 第一章绪论 1 1 差错控制编码的发展和l d p c 码的产生 在通信l i ，由于信道i - 符种噪声的t 扰，使人们难以进 j ：可靠的通信。为了实现信息的可 靠传输，人们提出了纠错编码的方法，以抵抗信息传输过程i l 信道噪声的t 扰，纠正因t | 扰而 产生的接收错误。但是这种方法抗t 扰的能力怎样，秆没行性能上的极限呢? 1 9 4 8 年，香农建 立了信息论，同答了这个问题，并为纠错码的研究指n 月了方向。由香农理论可以知道纠错编码 能够进行自效纠错的最小比特能噪比为香农极限。从那以后，寻找能够实际应用的逼近香农极 限的编码方案就成了纠错编码理论的最终u 标。 陶绕上述目标，在+ k 十年f 至1 0 八十年代初，人们主要研究了线性分组码。这类编码以代数 - i 的群论，域论等理论为数学基础，利用再种代数方法设计好的纠错码，并研究与之柏适心的 译码算法。这4 时期内相继出现了戈雷码、汉明码、循环码和b c h 码等短码。其i l i 重要的+ 类 编码足b c h 码，由它进步演化出了扩展b c h 码、缩短b c h 码、r s 码等编码，在通信系统 i - 得到j ，广泛的心用。它们的译码方浊通常都采用人数逻辑障码和捕错洋码。这些编码都是短 码，冈为它们的译码复杂度与码长成指数关系，随码长的增加，译码的计算晕极人的增加，基 本上足f i 能实用的，能够实际j 逦用的只足短码长的情形。而短码的性能足仃限的，难以达到逼 近香农限的目标，香农限的逼近需要长码长的编码。这样，寻找能够仃效译码的长分组码就成 了信道编码的。个重要的研究方向。幸运的足，g a l l a g e r 在1 9 6 2 年找到了这样。种编码【l 】，现在 通常称为g a l l a g e r 码。这种编码由于校验矩阼的稀疏性，使得译码的复杂度只与码长成线性关 系，在长码长的时候，仍然可以自效的进 j ：译码。然而1 i 幸的足，由于当时技术条件的限制， 再加上人们普遍认为级联码史窖易实现，导致人们逐渐忽视了这种编码的存在，几十年来这方 面的进展甚微，在m c m a c k a y 和n w i b e r g 之前这方面仪自的研究t 作只有t a n n e r 7 等人作 了零旱的t 作。 卷积码也是五十年代提出的另。类重要的纠错码。它在编码过稃l - 引入了寄存器，增加了 码元之i 日j 的相关性，在相同复杂皮的条件下可以获得比分组码史高的编码增益，但是这种相关 性同时也增加了分析和设计卷积码的复杂性。随着人们对卷积码研究的深入，在卷积码的译码 算法力。卣出现了序列译码算法和维特比( v i t e r b i ) 译码算法。而维特比译码算法的出现，使卷积 码逐渐成为研究和应用的重点。 纠错码主要就分为上述的分组码和卷积码两类。它们各自优缺点。此# l - r h 于在实际心用r i j ， 短码的性能有限，只有长码才能得到优秀的性能，人们于是设想足否能够在短码的基础上构造 长码。由此提出了利用短码的级联或乘秋码来得到长码，以提高编码的性能，同时能够在短码 的基础上洋码，使得译码的复杂度又1 i 会太高。 到了八十年代和九十年代初，经过几十年的研究和实践，纠错编码理论和技术取得了很人 的发展，但是离香农理论的极限性能仍然仃一定的距离，难以找到能够逼近香农极限的编码方 案，人们一度失望，认为无法找到能够实际应用的好码。就在这个时候，法凼的c b e r r o u 等人 4 中国科学技术大学硕士学位论文 在卷积码和级联码的基础上，于1 9 9 3 年提出了种全新的编码方案：t u r b o 码。在信道编码的理 论和应用中取得了突破性的进展，这种编码能够在长码长时逼近香农的理论极限，同时泽码复 杂度也是可以接受的，在当时的硬件水平下可以实际心用。t u r b o 码采用并行级联递归的编码 器结构，是一种系统的卷积码。t u r b o 码之所以具仃逼近香农限的性能，是因为其独特的编码 结构和新的译码思想：在子编码器- l ，采用了反馈掣的系统卷秋码，且在予编码器间引入交织器， 减少了子编码器问信息的相关性，模仿了随机编码的形式，同时在译码l 一采用了软输入、软输 出的译码算法信息和信息反馈的译码形式。 由于t u r b o 码优秀的性能，使其度成为编码界研究的热点，其理论和技术也逐渐成熟起 来。t u r b o 码在通信中有广阔的应用前景。在诸如星际探测、移动通信、数字电视、数字广播、 卫星通信中都可以得到应用。但是t u r b o 码也自其缺点，它的译码复杂度仍然较大，且在码长 较长时，由于交织器的存在具自较火的时延。 在获得巨人成功的t u r b o 码的启发下，另一类具仃相似特征和性能的编码复活了。这就是 l d p c ( l o wd e n s i t yp a r i t yc h e c k ) 码。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 r u b o 码稍秆霹距，但是它同样具柯逼近香农限 的性能【4 1 。【5 】中的研究结果显示，对于a w g n 信道，码率为l 2 的非正则l d p c 码可具自距 容晕小到0 0 6 d b 的门限；计算机仿真结果表明，精心设计的非正则l d p c 码( 长度为1 0 0 ) 可 获得在b e r = l0 - o 时仪偏离奔景0 1 3 d b 的性能，优于迄今所知道的最佳t u r b o 码。而具柯最新 的研究结果，理论上的极限性能仪仪比香农限高0 0 0 4 5 d b 的非正则码次数分布对l 二经找到【6 】。 l d p c 码的优异性能及其在信息可靠传输- i - 的良好应用前景( 如深空通信、第四代移动通信系 统、高速与甚高速数字用户线、磁记录系统等) ，l 引起器凼学术界和l t 业界的广泛关注。l d p c 码将取代t u r b o 码的趋势已很明显，研究l d p c 码具自很多的学术、工程应用和商业价值。 1 2l d p c 码的特点和发展动态 l d p c ( l o wd e n s i t yp a r i t yc h e c k ) 码最初由g a l l a g e r i 】上个世纪六十年代初发现，它是一 类可以用非常稀疏的奇偶校验矩阼或二分图定义的线性分组纠错码。但是限于当时的计算水平 和人们对这种形式非常简单的码认识不足，数十年来它一。直遭受冷遇，这期问只有r m i c h a e l t a n n e r 7 等对它进行了零星的研究，且几乎没有实质性的进展。而自从l d p c 码被m a c k a y 和 n e a l 等人重新发现之后，其优越的性能很快引起研究人员的重视，l d p c 码迅速成为人们研究 的焦点。经过几年的研究与发展，人们在各方面都取得了突破性的进展，l d p c 码的相关技术 也日趋成熟，甚至已经开始有了商业化的应用成果。 i l d p c 码的特点 l d p c 码足一种具有稀疏校验矩阼的线性分组码，有能够逼近香农极限的性能特性；同时 得益于校验矩阵的稀疏性，这样优秀的性能是在不太高的译码复杂度戡性复杂度内实现的； l d p c 码的描述和实现简单，对严格的理论分析具有可验证性：译码算法本质上是并行算法， 有利于硬件的并行实现，减少了译码时延；它能够在自己的迭代运行过程中确定码字是否已译 出，以决定译码过程是否结束，减少迭代次数：同时其译码错误都是可以检测的，目前的实验 5 中国科学技术大学硕士学位论文 研究表明彳i 可检测的错误几乎从为出现；译码后的误码率可以随信噪比的增加任意减小，没自 误码率下降减速的错误，f 层现象：m e s s a g ep a s s i n g ( 消息传递) 算法存在。种译码门限效应， 只有当信道噪声方差低于门限值时，译码后的误码率可以趋于0 ，否则处于概率演化方程。l i 的 不动点的1 i 可逾越性，将小能趋于0 ；在编码的数学模型上，小像t u r b o 码，l d p c 码具仃自己 简单的数学模型；二分图。 2 l d p c 码的研究与进展人体包括下几个方面： 1 ) l d p c 码结构及其优化 因为l d p c 码是一种线性分组码，它的码结构可由校验矩阼确定，所以所谓码结构设计也 就是校验矩阵的构造。l d p c 码的校验矩阵构造方法目前主要有几何方法、图论方法、实验设 计方法、置换方法等。 按照校验矩阵的行和列是否都具仃同定个数的非零元素可将l d p c 码分为正则码和非正 则码。另。种分类方法是将它分为_ 元域和多元域上的l d p c 码。而m c l u b y 等【8 】指出，非 正则l d p c 码的性能由于相应的正则l d p c 码。而m c d a v e y 9 等的研究表明多元域上的l d p c 码的性能较- 元域上g a l l a g e r 码的性能行较高提高，且域的阶数越高，编码的性能越好。 在寻找好的码结构( 所谓好的码结构就足既自好的性能又钉较低的编码复杂度的码结构) 方血，l u b y 等【8 】采用基于线性规划的疗法柬设计线性时问可编码的非正则码。d j c m a c k a y 等【1 0 】提出对非正则码采用先选择轮廓再选择结构的两步选择方法，并指出能快速编码的l d p c 的矩阵通常具有下三角形结构。t j r i c h a r d s o n 等【5 】通过优化二分图的次数分布，设计出性能逼 近香农限的非正则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 il 】探讨了奇偶校验矩阵如何确定的 问题，并找到了一种使编码时间与码块长度实际上符合线性关系的码构造方法。m g l u b y 1 2 】 等也提出。类基于级联二分图的l d p c 码，用于可抹信道，它不仪使线性时间编码，而且也可 以实现线性时间译码。 2 ) l d p c 码的译码算法 在译码算法的研究方面，g a l l a g e r 【l 】曾给出了两种l d p c 码的迭代译码算法：硬判决算法 和软判决算法。硬判决算法简单易i j ：，但是性能较差；后者虽有好的性能，但是实现复杂度太 高。于是作为二者的折衷，【5 】提出了消息传递算法( m e s s a g ep a s s i n ga l g o r i t h m ) 。f r k s c h i s c h a n g 等【2 3 】对消息传递算法做了推广，将它扩展为一种更加通用的算法：和积算法( s l i m p r o d u c t a l g o r i t h m ) ，并指出和积算法实际上包含了人量的实际译码算法( 如前向后向算法、b p 算法、 维特比算法等) ，它可应用于任何冈子图，众多的实际译码算法均可有和积算法框架导出。 m p c f o s s o r i e r 1 8 】研究了降低复杂度的l d p c 码的译码算法，提出了a p p - b a s e d 和b p - b a s e d 算法。在此基础上，j i n g h uc h e n 和m p c f o s s o r i e r 1 2 1 3 提出了两种改进的b p b a s e d 算法的 密度演进算法及其离散形式。 3 ) l d p c 码的实现 6 中国科学技术大学硕士学位论文 t b h a t t 等 1 4 1 提出采用定点d s p 实现l d p c 译码的方案。h a l o c l i g e r 等【1 5 】建议用模拟 v l s i 实现l d p c 码的和积算法译码模块，以避免数字实现l l i 十分复杂的实数运算。t z h a n g 和 k k p a r h i 2 6 提出了一种码和译码器联合设计的面向v l s i 实现的方法，适合执行部分并行译 码。b l e v i n e 2 7 贝t 给出了种用h 前商用f p g a 实现的l d p c 码验证设计方案。 4 ) l d p c 码的应用 由于l d p c 码性能的优越性，行望在通信- i 一得到广泛的心用。目前在第四代移动通信i l i 使 用l d p c 码的提案已经提交：而l d p c 码在d s l ，a d s l 2 8 2 9 1 ，深空通信及磁记录信道 3 0 31 】 等信道上应用的研究正在展开。除了l d p c 码本生外l d p c 的原理也打望得到广泛的应用。由 于l d p c 码数学模型上的成功性，引起了人们用l d p c 码的观点对许多编码进行了重新的研究， 获得了许多新的认识和成果。 1 3 本文内容安排 第_ 章引入了l d p c 码的定义，简要的介绍了l d p c 码的校验矩阼的符种构造和它们的优 缺点。 第三章讨论了l d p c 码编码的复杂度的i u j 题，描述了t j r c h a r d s o n 和r l u r a b n k e 提出了 一种线性时问编码力法，并给出j ，具体的可实现的编码器结构。 第四章，对l d p c 译码算法进行了研究，推导了基于b c j r 算法的l d p c 译码器算法。提 出一种简化复杂度的的洋码算法，并给出了相心的仿真和分析结果。 第血章，讨论了目前的可实现的符种译码的结构，它们的优势和缺点以及设计难点。还讨 论具体设计的平台和编码构造对译码器实现的影响。 7 中国科学技术大学硕士学位论文 第二章l d p c 码的构造 g a l l a g e r 在1 9 6 2 年提出了l d p c 码，揭示出了一种新的具自低密度校验矩阼的分组编码构造 方法，它利用校验矩阵的稀疏性解决长码的译码问题，可以在线性时问内洋码，同时又近似于 香农提出的随机编码，获得了优秀的编码性能。g a l l a g e r 提出的l d p c 码具有正则的二分图结 构，其一分图每个信息节点都有相同的次数，每个校验节点也都有相同的次数，通常称为正则 码【l 】。经过近几年的研究，人们在正则码的基础上进行推广，又提出了非正则码【3 2 】及多元域 上的l d p c 码【3 3 】。非正则码在分图结构中节点次数的分布上是自由的，不要求同类型的节 点仃相同的次数。仔细选择编码的次数分布对，就自可能在编码性能获得较正则码较火的改进。 多元域上的编码可以在增加列重景的同时小增加分图- i 圈的数晕，较人的改进编码性能，域 的阶数越高，性能改善越人。 对l d p c 码来说，在4 i 考虑码长和次数分布对的情况下，编码校验矩阼的结构就成了影响其 性能的重要因素，反映在二分图上对编码性能行重要影响的就足图i | 环的长度分布，需要采用 定的方法对校验矩阵进行构造，获得好的编码性能。 本章肖先介绍了正则码的构造，并从分图的角度给出了非正则码的定义，分析了非正则码 性能成冈，然后给出构造l d p c 码校验矩阼的一些指导性的方法。 2 1l d p c 码的结构 所谓l d p c 码是特指一类校验矩阼h 的人多数元素为0 ，只柯少数元素为l 的分组码，也即 l d p c 码的校验矩阵是稀疏矩阵。由线性分组码的性质，长度为玎，k 维的编码c 可以用 一k ) ”维的校验矩阵h 来描述： c ( g ) = 缸”：h x 7 = 0 ) l d p c 码也4 i 例外，可以用校验矩阼描述。 2 1 1 正则l d p c 码 下面是g a i l a g e r 最初提出的l d p c 码的结构。一个参数为( n ，以，以) 的l d p c 码是一种长度 为n 线性二进制分组码，它的校验矩阵有一个特点，就是每一列自也个i ，每一行有以个 1 ，其余的元素都是0 。既编码码字中的每个比特参与矾各校验约束，而每个校验约束涉及以个 比特。矾和吐与n 相比很小，因此日矩阵是稀疏矩阵以下是个l d p c 码，码长为1 2 的 ( 3 ，6 ) 校验矩阵的示意图： 8 中国科学技术大学硕士学位论文 h = 图ll d p c 码的校验矩阵的示意图 给定( 以，吃) 正则码的校验矩阼后，若校验矩阼的行是线性无关的，那么编码的码率为卜妄， 侧，若校验矩阵的狮是线性无关的，那么编码的码率人于卜毫也就是说上述的正则码 的码率不小于卜毒 任意一个二进制的线性分组码，都可以简单的用：分图将编码表示出来【7 】。个分图是 个包括两个顶点集合的图，只行属于1 i 同集合的顶点问可能仃边相连，同个集合的顶点之 间没行边相连。若将分图的两个顶点集合分别称为信息节点集合和校验节点集合。而将信息 节点集合t t 的节点( 信息节点、变最节点，比特节点) 对心码宁i i l 的比特或者说足校验矩阼的 列；将校验节点集合i 的节点( 校验节点) 对心编码的码宁所要满足的校验约束方程或者说足 校验矩阵中的行。若某个校验约束方程t i 出现了某个码字比特，则在相应的信息节点和校验节 点之l 日j 存在一条边。定义与某个顶点相关联的边数为给顶点的次数( d e g r e e ) ，该次数表示某 个节点的约束程度。这样生成的分图就是相心的分组码的分图。上面例子t 1 i 编码的分图 表示如图2 2 所示。图中用方节点表示比特节点，圆节点表示校验节点。每个校验节点表示。 个校验约束方程( h 矩阵的一行) 。在该编码中，若没自校验约束，自由度为1 2 ( 1 2 个比特 节点) ，6 个线性约束最多减少6 个自由度( 如果所有线性约束是线性无关的那么 4 0 好减少6 个自由度，如例中所示) 。这样最少剩下6 个自由度。由此得到例- i - 所示编码的码率最少为o 5 。 图2l d p c 码的二分图的表示 9 o，o o o，o 0 o o l l 0 l 0 0 o l l l o 0 l l l o 1 o l o l o l 0 l 0 0 l 0 l 0 0 l l o l o 0 l l o o o l l o o l o oo o 中国科学技术大学硕士学位论文 2 1 2 非正则l d p c 码 正则l d p c 码所对应分图的比特节点或校验节点的次数都是固定的。如果允许节点的次数 发生变化，并仔细的选择节点的次数分布t 匕例，将能够极人的改善l d p c 码的性能，这就足非 正则l d p c 码【1 3 】。非正则l d p c 码可定义为每种次数节点的比例都根据实现顶的次数分布比 例选择的l d p c 码。例如，个非正则l d p c 码可能具行这样的分图表示，其半比特节点 的次数为3 ，另。半比特节点的次数为4 ，而半校验节点的次数为6 ，另一半校验节点的次数 为8 。 2 2l d p c 码校验矩阵的构造 分组码的构造关键在于校验矩阵，只要给定了校验矩阵，编码就究全确定了，可以用之进 j ： 编码和泽码。对于l d p c 码来说，由于编码的图结构对码距及译码算法的性能有较人的影响， 其构造问题主要在于如何构造没仃短长度环和环的j i 均长度塔可能人的校验矩阼。 2 2 1 图结构对编码的影响 编码分图结构环的存在及数黾的多少，尤其式短长度环的存在及数最的多少对编码的码距 和性能行重要的影响，考察如图3 所示模校验矩阼的分图片断： 图3 禽自4 环的l d p c 码的分图片断 在图示的- 分图片断中，有一个长度为4 的环( 用粗线条表示) 。如果图中3 个信息比特 都发生了差错，五个相关的校验约束1 1 1 只有。个能够检测到发生的错误。在这种情况下，要从 一个检测到错误的校验约束来纠正三个错误是困难的，译码算法变得无能为力。 从上面简单图结构的分析可以看出，_ 分图中的环，特别是短长度的环对编码有重要的影响， 并l tr h 于译码算法是建立在二分图巾没柯环的假设之上，环的存在会降低译码算法的性能。因 此在构造编码时，如何消除短长度环，提高环的平均长度时需要着重考虑的问题。 下面给出一些粗略介绍l t 前存在的些l d p c 码的构造。 2 2 2g a l l a g e rl d p c 码的构造 在g a l l a g e r 最初的工作中【l 】，给出了( 矾，以) 正则码的构造方法，这是一种伪随机的构造 方法：对于码长为刀的( 瓯，以) 正则码，将校验矩阵按水平的分割为或个相同火小的子矩阵， 1 0 中国科学技术大学硕士学位论文 每个子矩阵的任一列都只包含，个l 。第一个子矩阼以预定的方式构造，如可以用递减的形式 包含所有的1 ，矩阼的第， r 所自的l 都分布在第( i - 1 ) d c + 1 到f 以列。其它下面的j - i4 - = f 矩 阵都是第一个子矩阵的随机排列。这种构造方法可如下表示： h o = 1 1l 1 、， 以 l il l 、，j 以 l l 卜1 、- - v ， 吒 4 0 为第一个子矩阵，校验矩阼h 如下构造： h = t t o 7 c l ( o ) ( 日o ) 这里丁c 为矩阵h o 的列置换。上面h 矩阼的第+ 。个子矩阼为h o ，也可以用4 0 的任。置换代替， 得到如下更加对称的构造方法： h = h o 7 c i ( 日o ) ( 日o ) g a l l a g e r 经过推导得出下面的结论：给定一个i e s u 码系列，如果其校验矩阵的列重量为某个给 定的吨，满足咖3 ，且可以任意选择码长，那么该编码足。个好码，也就是说当给定通 信信道的时候，存在某个低于信道存最的最大信息传输速率，使得当通信速率低于该速率时， 当该码系列中编码的码长足够人时，以之进行通信能够时误码率任意的低。 2 2 3m a c k a y 的构造方法 m a c k a y 在校验矩阵中引入一些重最为2 的列，降低整个校验矩阼的重量以减少二分图r i 环 的数量，由此减少译码算法收到圈的影响，但是引入重量为2 的列会导致低重量码字的出现， 需要采取措施减少其出现概率。m a c k a y 给出了如下指导性的构造方法【3 】。 中国科学技术大学硕士学位论文 构造法i a ：这是最基本的构造方法，该方法构造的矩阼每列的重角= 都为一个阎定值t ，( 例如 ，= 3 ) ，随机的构造矩阼使每行的重最烬可能的相等，而每两列之i 日j 重叠的l 的个数l i 人于l 。 如图。 构造法2 a ：该构造法构造的校验矩阵前詈列的重晕都为2 ( 肌为矩阼行数) 。这些重为2 的 列由两个竺2 竺2 的单位矩阵构成，一个在上，一个在下。 构造法l b ，2 b ：由构造1 a 或构造2 a 构造校验矩阼，并从该矩阼重删除一些仔细选择的列， 使得结果矩阵对应的_ 分图没行小于某个给定长度，( 例如，= 6 ) 的王1 ：。 m a c k a y 还推广了g a l l a g c r 的随机构造法，利用排列矩阼的叠加构造正则码和非正则码的校 验矩阼。 2 2 4 超轻( u r l t r a l i g h t ) 构造法 m a c k a y 利用了最多为詈列的重为2 的列以减少矩阵的重黾。对_ 进制编码来说更多的重为 2 的列使升i 可接受的，因为这样会增加译码的误码率，导致1 i 可检测的译码错误。而非_ 进制 的编码可以包含更多的重为2 的列而4 i 显著降低误码率。这种构造方法由m a c k a y 的构造法2 a 变化而来，该构造方法中堆积了一系列更小的单位矩阼。 超轻构造法a ：构造了詈列重为2 的列后，进一步在一个詈詈的单位阵旁放置两个署百m 的 单位阼。重复该过程直到最多有m 个重为2 的列被构造出来，每次都将新的小单位阼放在上次 构造的某一单位阵旁，这样的矩阼行的重晕为3 ，4 或史高，这依赖与上述过程重复了几次。最 后填充剩余的列，使每行的重量尽可能的相等。 超轻构造法b ：该构造法与a 相似，只不过小单位阵的放置使得每行的重量在填充剩余部分之 前最多为2 。 2 2 5 非正则l d p c 码的构造 【5 】和【8 】通过次数分布多项式兄( x ) 和p ( x ) 定义了非正则码集，并给出对于不同的信道如何优 化这些多项式。这里最优的意思指的是码集中的一类码比码集外的码在相同信道条件下可以更 加可靠的通信。最坏的信道条件情况成为译码门限。最优的t ( x ) 和p ( x ) 通过称为密度演化的 1 2 中国科学技术大学硕士学位论文 算法得到。密度演化是指译码器t a n n e r 图上不同传递信息的概率密度函数的演化。对于给定 ( a ，p ) 对，译码门限通过对数似然比的概率密度函数的估计获得。 使用这种方法设计出非正则的l d p c 码在_ 输入a w g n 信道上，仿真的性能距离香农限 只有o 0 0 4 5 d b 。该码码长为码率为l 2 。通常，采用密度演化方法最好应用于码率1 i 太高( 小 于3 4 ) ，码长巧i 太短( 人于5 0 0 0 ) 的情况。这是因为密度寻优设计算法是假设码长无穷的情 况下的，所以次数多项式也是针对非常长的码情况时才是最优的。在t 1 一等长度或短码长的情况 下，这种设计f i 是最优的。 2 2 5 有限域上的构造方法 在【1 6 r l , ，作者采用【1 7 】t i t 基于有限域的技术构造了正则的l d p c 码。采用这种方法构造出 的l d p c 码是+ 类循纠：或准循环的的分组码，这使得它们的编码变的很简单，只需要采用移位 寄存器电路就可以实现了，。循环仃限域编码还具有相对人的最d , 足b l 离，但是准循环码的最小距 离稍微小些。同时，利用这种方法构造的短l d p c 码( 码长在2 0 0 比特左右) 通常比采用伪 随机方法构造的码的性能要好。 循环有限域码构造方法的缺点是它的译码校验矩阼是刀打维的，而升i 是( 刀一七) x 刀维。( 可 以选择校验矩阵l i ( 刀一七) x 玎人小的子矩阵来译码，但是会造成1 i 可忽略的性能的损失) 。另 一个缺点是以和z 的值比较人，这是我们所4 i 希望的，因为迭代译码算法的复杂度是和这些 值成正比的。最后。个缺点是无法灵活的选择的码长和码率。 2 2 6r a ，i r a ，和c i r a 码构造方法 在【1 9 】中提出了种具有串行t u r b o 码和l d p c 码双重特性的。类码，称为r a ( r e p e a t - a c c u m u l a t e ) 码。图4 显示了r a 码的编码器结构。可以看到，用户的数据被重复( 典 型的是2 到3 次) ，转置，然后被送入一个累加器( 筹分编码器) 。这类具囱逼近香农限的能 力，但是它们的缺点是码率低( 码率为1 2 和更低) 。 当r a 码中的某些比特重复的次数多于另外的一些比特是就生成了i r a ( i r r e g u l a r r e p e a t - a c c u m u l a t e ) 码【2 0 】。如图所示，i r a 编码器由个低密度生成矩阼，一个转置器，和一 个累加器构成。这样的码可以比r a 码在理论上更加的逼近香农限，同时它们也可以由更高的 码率。这种i r a 码构造方法的缺点是它们通常不是系统码，尽管它们是以系统码的形式出现。 y a n g 和r y a n 2 1 提出了类有效的非正则l d p c 码的构造方法，称为扩展i r a 码。扩展i r a 码的编码器结构如图所示。注意扩展i r a 码编码器是系统码，对高和低的码率都是适用的。 1 3 中国科学技术大学硕士学位论文 i r a u - - 扩展l r a u f ? - k x ( n - k ) 图4r a ，i r a ，和e i r a 码构造方法示意 k ) 本章讨论了l d p c 码的结构机器校验矩阼的构造方法。构造了编码的校验矩阵，就可以进 r 编码和译码了。 1 4 中国科学技术大学硕士学位论文 第三章l d p c 码线性时间编码原理与硬件实现 我们知道稀疏矩阼的运算复杂度取决与矩阼r - 非零元素的个数，对于l d p c 码的奇偶校验 矩阵而言，每一。列中非零元素个数对于正则码是常数，对于非正则码也是确定的，总之，列重 量独立于码长：事实上，无论正则码还是非正则码校验矩阵非零元素的个数都是码长的几倍 到几十倍，是线性关系，如果我们能够很好利用校验矩阼的稀疏性来编码的话，我们就可以实 现线性时间内编码( 即编码的运算次数是o ( u ) ) 。如果l d p c 码通过生成矩阼g 来编码，其 算法具有码长次方的时问复杂度，这将制约l d p c 码的应用。 针对l d p c 码的编码问题，许多学者进行了研究。s i p s e r 和s p i e l m a n 提出用级联图而刁i 是 二分图以减小编码复杂度【2 2 】。通过仃细的选择级联的层数以及每层的人小可以构造线性时间 内可编码和译码的码，它的一个缺点在于实际上每层的长度通常都是远小于整个编码码长的。 这通常会导致在同样码长的情况下较标准的l d p c 码有性能上的损失。 m a c k a y ，w i l s o n 和d a v e y 建议强制性地使奇偶校验矩阵具有下三角阼的形式，码集校验矩 阵必须满足下三角形式的约束，这个约束保证了编码具有线性的编码时间复杂度，但足这种约 束太强，必然破坏了校验矩阼的g i r t h 约束和变晕节点及校验节点的次数约束，从而导致性能明 显下降，所以在满足g i r t h 约束和次数约束的条件下实现线性时问编码是l d p c 码走向实用的关 键。 本市l | j 的仃效编码方法来自t j r i c h a r d s o n 和r l u r a n k e l 1l 】，提出了重排稀疏校验矩阵的 行或列，从而得到具自- 准下三角结构的校验矩阼，利用下三角系数线性方程可以线性时l 日j 求解， 适当的处理后，我们就可以实现线性时问编码。通过这种方法，仪仪对编码的校验矩阼进行4 些重排的顶处理，就能使编码的时问复杂度在决人多数情况下都是相当可控的甚垒具行线性时 间复杂度。例如，对于一个码长为的( 3 ，6 ) 正则码，编码的复杂度表面上看起来足2 阶 的，但是实际所需的操作4 i 超过0 0 1 7 2 刀2