（通信与信息系统专业论文）ldpc码的几个关键问题研究.pdf

摘要 l d p c f l 0 w d 锄s i t yp 撕t y c h e c kc o d 鼯，低密度校验码) 是一种能逼近s h 籼o n 容量限的渐进好码，其长码性能甚至超过了n - r b o 码。由于低密度校验码具有译 码复杂度低、错误平层低等诸多优点，它在信息可靠传输中的良好应用前景已经 引起学术界和i t 业界的高度重视，成为当今信道编码领域最受瞩目的研究热点 之一。 本文作者结合国家8 6 3 计划项目( 2 0 0 6 a a 0 1 2 2 6 7 ) 和p h i l i p s 公司等科研项目， 采用理论分析和计算机仿真的方法，对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 的译码方面，研究了硬判决和软判决两类译码算法。硬判决方面， 介绍了一种常用的比特翻转( b f ) 算法，得出了高码率的l d p c 码更适合采用b f 硬判决译码算法的结论；对于软判决，首先介绍并比较了软判决译码的三种测度 的译码算法，分析了对数似然比( l l r ) 测度下译码算法的优势。然后对s t i m i 标 准中的l d p c 码在各种l u t 译码算法下的性能进行了计算机仿真，对仿真结果并 结合这些译码算法的复杂度进行了分析，得到了在性能和译码复杂度之间折衷的 最优算法n o n a l i z e dm s a 。 在l d p c 的量化译码方面，采用理论分析和仿真相结合的方法分析出了对数 似然比测度量化译码性能的优越性，给出了s t i m i 标准中l d p c 码的最终量化设 计方案。 最后用仿真方法探讨了u ) p c 码在衰落信道中的应用并得到了两个结论：低 码率l d p c 码比高码率l d p c 码具有更强的抗多径衰落的能力；l d p c 码具有能 够良好地抵御快衰落的内在交织特性。 关键词：l d p c 码l d p c 码构造和积译码算法量化衰落信道 a b s 仃a c t l o w d c n s 崎p a r i t y - c h e c k ( l d p c ) c o d 髂a r ead a s so fc 印a c i t ya p p m a c h i n g 锄r _ c o n c t i n gc o d c s w i t hl o n gc o d e - 1 g t l l s ，l d p cc o d e sc 狮c v o u t p e r f b 咖 t h r b oo o d 髓d u et ot l l ea d v a n t a 毋器o fl d p cc o d 器，s u c ha sl o w e rc o m p l e x i t yo f d e c o d i n ga n d1 0 w e re r r o rf l o o r m c i ra p p l i c a t i o n si nr e l i a b l eo 咖m u n i 训o n sh a v e r e c e i v e d 毋- e a ti n t e r e s t s 龃dh a v eb e c o m eo n eo f m o s ta 抽r a c d v e 丘e l di nc h 砌e lc o d i n g m 岫i 吼 t h i st l l c s i si n v e s t i g a t e ss o m ek c yp r o b l 锄so fl o w - d e n s 时p a r i 妒c h e c k ( l d p c ) c o d 髓谢mm e o r c t i c a la n a l y s i s 锄ds i i n u l a t i o n t h em a i nr 嚣u l t s 肌dc o n t e n t sa r e 嬲 f o l l o w s f i r 咄w eg e n e r a l l yi n 仰d u c e dt l l em c t h o do fc o n 咖c t i n gu p cc o d 舒，锄dt h 吼 g a v et h em e 山o do fc o n s 仃c t i n g ( 舢勰j c y c l i cl d p cc o d 姻，卸d 孤a p p r o a c ht o c o n s 仃u c te 币c i t l y 髓c o d a b l el d p cc o d c si sp r e s e n t 。da tl 嬲t t b ee i l c o d 盯o fm e p m p o s e dl d p cc o d em a yb e c h a r a d c r i z c db yag r o u po fi n t e r l e a v 哪 a n d o d n v o l u t i o n a lc i l c o d e 侣l i r l l 【c di i lp 删l d a n dt h ec o r r e s p o n d i n gp a r i t yc h e c km a 研x c a i lb ed c c 舳p o s e di n t o 咖s u b m 缅c e sw h i c ha r ed c t e n n i n e db yt h ei m e r l e a v e r sa n d t h eg e n e r a t o rm 删c 嚣o fc o n v o l u t i o n a l 印c o d e r s ，r e s p e c t i v c l y e v e r yi 1 1 t e r l e a v c ri s d e s i 髓e db 私o do nt h eo q u i v a l e n tr 印心s a n a t i o n so faf i n i t cf i l 。dd 锄e n t ，s on 锄c da 矗n i t cf i l c di n t 甜e a v 盯w i t ht h i ss 缸1 l c t u r e ，懿昀o r d i n a r yf 弧e n c o d i n go fl d p cc o d c 柚b ea c t l i c v c d b yo p t i m i z i i l gt h et w d 鲫b - m 撕c e sr e s p c c t i v d y ，a no v c r a l l e 伍c i e n n y 锄c o d a b l el d p cc o d e 、】l r i n lg o o dd e c o d i n gp e r f o 皿a n c ci so b t a i n e d t h e埘n c i p l c so fh a r d d e c i s i o n d e c o d i n g 锄dr d e c i s i o n d e c o d i n g a r c s y s t 锄a t i c a l l ys u m m 撕z c d i nm eh a r d d e c i s i o nd e c o d i n gh a l l d ，b i t n i p p i n g ( b f ) a l 鼬r i t h m 矗h a r d d e c i s i o nd c c o d i n gi sd i s c u s s c d ，a n dt t l el d p cc o d 髓w i ml l i g l l 盯 r a t ea r cm o r c 邳l p 】r o 研a t ef o rt l l eu s eo fb fa l g o r i t h mi sc o n c l u d e d ；i nt 1 1 es o r d e c i s i o n d e c o d i n gh a n d ，f i r s t l y ，w ei 1 1 仃o d u c e da n dc o m p a r e dt h es o f t d e c i s i o nd c c o d i n g a i 枷t l l i no ft l l et h r e em e a s u r e s ，t 1 1 ec q u 撕o n sf o r 印d a t i l l gm e s s a g e si ns u m p r o d u c t a l g o r i t h i l la r ed c r i v e da n dt h em o s t 既c d l e n t l yp e r f o m l a n c eo fm el l rm e a s u r ei s 扑a l y z e d s e c o n d l y b e t 、e e ns i m u l a t i o np e 晌瑚a n c c 髓dt t l e 叩酬i o nc o m p l c x i t yw e c o m 邮m i s e 血a tn o m a l i z o dm s aa l g o r i t h mi so p 旺m a l i t yi ns t i m is t 锄d 矾s b yt l l c o r c t i c a l 锄a l y s i sa n ds i m u l a t i o n ，q u a n t i z a t i o nd e c o d i n go fl d p cc o d e si s s t u d i e d w ea n a l y z et l l e 卯p e r i o t yp e r f b n n a n c eo ft l l el l rm e 鹪u r eq u a n t i z a t i o n d c c o d i n g ，a i l dd c s i 弘t h eu l t i m a t el d p cc o d 髓q u 瓶t i z a t i o nd e c o d i n gs c h 锄eo f s t i m is t a n d 矾s i nm ee l l d ，s i m u l a 廿o n sa p e r f o n 】1 c df o r 廿l ep l l r p o s eo fe x p l o i 血gt 1 1 e a p p i i c a t i o n so fl d p cc o d e s 抽白d i n gc h 锄e j sa n d “，oc o n c l u s i o n sa r ea b t a i n e d t h e 矗r s ti st l l a tl d p cc o d 器w i u ll o w 贯m t eh a v eas 仃o n g e r 锄d m u l t i p a m 脚i n g c a p a b i l i t i 骼t h e c o n di s t l l a tt 1 1 ei i l l l e r e n ti n t e r l e a v i n ge 饪b c t sf o l l o w i n gt h ev e r y s p a r s es t m 咖r ea r ei n v e s t i g a t e d ，w h i c he n a b l et h et 0 1 e r a n c eo fl d p cc o d e sf 0 rs o m e f b t c rf 甜髓o rl o n g e rb l l r s t 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 鹳 c o n s 仃u c 廿o no fl d p cc o d e s s u m - p i o d u c ta j g o r i t h m q u a n t i z a 廿o n f a d i n gc h a n n e l s 创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指 导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所 罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得 西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 邋墨堑 日期 关于论文使用授权的说明 芝丝 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发 表论文和使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论 文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采 用影印、缩印或其它复印手段保存论文。同时本人保证，毕业后结合学位论文研究课题 再撰写的文章律署名单位为西安电子科技大学。( 保密的论文在解密后遵循此规定) 本人签名： 邋垒堑 日期 导师签名 i ! ! 也 第一章绪论 l 第一章绪论 本章首先简要阐述了数字通信系统的模型和编码系统性能的度量标准 一s h 锄o n 容量限；接着介绍了本文的中心议题u ) p c 码；最后给出了本文的主要 工作和以后章节的行文安排 1 1 数字通信与信道编码 通信系统致力于在信源与信宿之间提供一条快速、可靠、安全地交换信息的 通道。但是，通信系统中电子设备以及传输媒质等引入的各种噪声和干扰降低了 通信的可靠性。在各种限制条件及噪声干扰下如何实现可靠而高效的传输信息是 通信系统设计的关键问题【i 】【5 1 。通信历史中，人们曾一度认为：传输的可靠性与 高效性是一对不可调和的矛盾，有干扰信道上实现无错误传输的唯一途径是使信 息传输速率降到零。直到1 9 4 s 年，s h 锄一篇名为通信的数学理论论文的 发表，改变了人们的这一观点，奠定了信息论及编码理论的基础。s h 锄o n 证明： 只要传输的信息速率小于信道容量，就可以通过编码方式实现信息的可靠传输 【2 卅。根据s h 锄o n 信息传输理论，点对点数字通信系统的基本组成如图1 1 所示： 编码信道 - 1 竺竺兰h 洲雠 厂翮i 桶 图1 1 数字通信系统的模型 当译码采用最大似然( m l ) 译码时，随着分组码的码长或卷积码的约束长度的 增加，系统可以取得更好的性能( 即更大的保护能力或编码增益) ，但是，最大似 然译码算法( m u ) a ) 的复杂性随码长n 指数增加，当一较大时，m l d a 几乎物理 不可实现。因此，必须研究新的编码方案。寻找好码及其有效译码算法一直是信 道编码理论与技术研究的中心任务。 2 l d p c 码的几个关键问题研究 1 2 码率与s h a 肿彻容量限 任意离散无记忆信道都存在称之为信道容量的信息传输速率上界，它表示信 道传送信息的最大能力。信道编码研究的中心问题之就是在给定的性能指标下 构造一个信息传输速率逼近信道容量的码。 信道编码定理：给定一个容量为c 的信道，只要信息传输速率r 小于c ，就 存在一对编、译码器，使译码错误概率p 随着编码长度的增加而变得任意小。 信道编码定理是存在性定理，它证明了在有扰信道中，只要传输速率小于信 道容量，就有可能通过信道编码的方法实现任意可靠的信息传输。信道编码逆定 理则指出如果信息传输速率大于信道容量，不论采用何种编译码方法都不可能使 平均译码错误概率趋于零。 在对不同的信道编码方案进行性能分析与比较时，我们经常需要将计算机模 拟结果与相应码率的s h 锄o n 限( s h 砌o nb o 吼硼i m j t ) j 差行比较。由于信息理论主 要考虑的是单个孤立电脉冲( 即信道符号) 所能承载的信息量( 在任意小误比特率意 义下) ，而脉冲的传输速率受限于n y q u i s t 准则，所以我们通常是以给定每符号 含有的信息比特数( 即码率) 下，为保证无误传输所需的最小信噪比来描述s h 锄 容量限的。当信道编码的码率不同时，容量限也会不同。下面分别对a w g n 信 道下不同码率的容量限作一介绍。 a w g n ( 即加性高斯白噪声信道) 是通信理论中最重要的信道模型之，该信 道上只有加性噪声的干扰，加性噪声是均值为o 和方差为盯2 的高斯变量，概率密 度函数记为( o ，仃2 ) 。设。是单边噪声功率谱密度，则0 = 2 盯2 。 1 9 4 8 年s h 籼o n 在【1 2 】推导了a w g n 信道在加性高斯白噪声下的信道容量： rf 、 c 【】堋1 。9 2 ( 1 + 姗) 圳l o g z 【1 + 彘j ( 卜1 ) 式中默傻是信噪比，矿是信道带宽，晟是单位信息比特需要的传输能量，地 是噪声的单边功率谱密度，c 是信道容量( 单位为b i t s ) 。 假设在a w g n 信道二进制情况下译码错误概率为m ，接收端译码后误比特 率为风情况等效于发送端对信源作误比特率为仇的编码而接收端译码无误的情 况。按照s h 锄o n 的率失真理论f j2 j 得到传送后b i t s 的平均误比特概率为纫6 ，所以 当码率为月b i t 幽时，信源的信息量为r ( 1 一j j l ( 只) 1 ，其中： ( p ) = 一p l 0 9 2 p 一( 1 一p ) l 0 9 2 ( 1 一p ) ( 1 2 ) 要实现高斯白噪声信道下的无差错传输，信信的传输速率必须小于等于信道 容量，即： 第一章绪论 r ( 1 一 ( 只) ) q m 】 ( 1 - 3 ) 将式( 1 1 ) 代入式( 1 3 ) 可得： 芈掣弛9 2 ( 1 + 彘) c ，q 矿v i 聊v j 、 7 令r 2 参，可将式( 1 4 ) 进一步化简为： 矧。2 芝 c 旧 “k 2 也 、7 s h a i l t l o n 限给出了码率忍，信噪比点o ，误码率n 三者之间的关系，即为 式( 1 5 ) 。图1 2 实线从右到左依次是尼= l 2 ，l 3 ，1 4 ，l 5 ，1 6 的s h 跏o n 限， 虚线从左到右依次是尼= 2 3 ，3 4 ，4 5 ，5 6 的s h 锄o n 限。 曼 罡 呈 山 盏 图1 2 且。固定时误码率随信噪比的变化曲线 1 3u ) p c 码的发展现状及其未来的研究方向 1 3 1l d p c 码 l i ) p c ( l o w d 髓s 时p 撕妒c h e c k ，低密度奇偶校验) 码是一类逼近s h 锄o n 限 的编码，其校验矩阵为稀疏矩阵，它是g a l l a g e r 在1 9 6 2 年提出的嗍。然而不幸得 是，g “l a g 盯的重大发现被编码人员忽略了大约2 0 年，直到1 9 8 1 年n e r 在他 的工作中从图的角度提供了一种对l d p c 的全新解释。t a 加c r 的工作又被忽略了 1 4 年，直到1 9 9 3 年b e n d u 等提出了t u m o 码【7 _ 8 】，人们发现t u r b o 码从某种角度 4 l d p c 码的几个关键问题研究 上说也是一种u ) p c 码。近几年人们重新认识到l d p c 码所具有的优越性能和巨 大的实用价值。1 9 9 6 年m a c k a y 和n e a l 的研究【1 3 】表明，采用l d p c 长码可以达 到t u r b o 码的性能，而最近的研究表明，被优化了的非规则l d p c 码采用和积译 码算法( s p a ) 时，能得到比t u r b o 码更好的性能。l d p c 码是目前人们发现的纠错 性能最好的一种码。为了说明这一问题，下面对l d p c 码和t u l b o 码进行了简要 比较。简单的说，l d p c 码与t u r b o 码区别在于，l d p c 码是一种线性分组码， 采用s p a 迭代译码；而t u f b o 码采用的是卷积码，译码方法主要有m a p 类的算 法和软输出v i t e r b i 算法的迭代译码。l d p c 码的理论极限性能优于t u r b o 码，给 定1 2 码率条件下，采用b p s k 调制的a w g n 信道中两种编码方法的纠错性能比 较，u ) p c 码比t u r b o 码更接近s h 蛐o n 限，目前最优的l d p c 码方案离s h 锄o n 限仅有0 0 0 4 5 d b 【1 4 1 。相对于t 1 l r b 0 码而言，u ) p c 码具有以下优点：1 ) 不需要深 度交织就能获得好的误码性能，所以系统的时延比n 曲。码短；2 ) 具有更好的分 组误码性能；3 ) 错误平层大大降低；4 ) 译码不基于1 i r c l l i s 图。 目前，l d p c 码被认为是迄今为止性能最好的码，是当今信道编码领域的研 究热点。近几年国际上对l d p c 码的理论研究以及工程应用和v l s i ( 超大规模集 成电路) 实现方面的研究都己取得重要进展。l d p c 码即将广泛应用于光通信、卫 星通信、深空通信、第四代移动通信系统、高速与甚高速率数字用户线和磁记录 系统等。 1 3 2l d p c 码的应用与进展 l d p c 码理论的深入发展推动了其实用化进程。 为达到数字高清标准，第二代卫星数字电视广播( d s 2 ) 中采用了b c h 码 和l d p c 码级联的方案【。其中，l d p c 码长度分别为6 4 8 0 0 和1 6 2 0 0 ，最低码 率为l 4 ，最高码率为9 1 0 。意法半导体开发的l s i 的晶体管数为8 5 0 万个，门 电路数为1 5 0 万门。l s i 中纠错处理电路所占面积均较大，1 3 0 i 皿版为 9 3 m m 6 3 m m ，9 0 砌版为4 3 m m 3 7 m m 。该l s i 具有很高的性能，调制方式 为o p s k 时，译码迭代运算5 0 次，离s h 锄o n 限只有o 3 0 5 d b 。 在无线城域网的i e e e 8 0 2 1 6 e 【1 9 1 草案中，l d p c 码与t u i b o 码一起作为编码调 制的备选方案。草案中，采用矩阵分块技术( 码长从2 0 3 4 到5 7 6 ，码率为1 2 ，2 3 ， 3 4 1 ，将大规模的矩阵乘运算分解为小规模矩阵乘的并行结构，有效的解决了 l d p c 码编码复杂度高的问题。国家广播电影电视总局广播科学研究院的s t m 方案【l s 】性能较好。该方案最大的技术亮点就是采用了l d p c 码信道编码技术。 d v b s 2 和i e e e 8 0 2 1 6 e 标志着u ) p c 码实用化进程的开始。随着l d p c 码 理论的成熟和l s i 技术的进步，l d p c 码将应用到更多的通信系统中。 第一章绪论 5 1 4 本文研究内容及安排 本文作者结合国家8 6 3 计划项目( 2 0 0 6 从0 l z 2 6 7 ) 和p h i l i p s 公司等科研项目， 采用理论分析的方法，对l d p c 码的几个关键问题进行了研究，包括码构造、译 码算法、量化译码和衰落信道上的译码性能；同时结合计算机仿真的方法对d m b t 标彬“】和s t d “i 标准中的l d p c 码的译码进行了深入的研究。全文共分为六章， 其它章节具体安排如下： 第二章主要研究l d p c 码的构造方法。先介绍了规则l d p c 码和非规则l d p c 码的构造；在此基础上重点研究了两种有结构的u ) p c 码的构造：准循环l d p c 码的构造和并行卷积l d p c 码的构造。并对这两种方法构造的l d p c 码进行了性 能仿真。 第三章从硬判决和软判决两个方面对l d p c 码的译码算法进行了系统的研 究。介绍了一种常用的硬判决译码算法比特翻转( b f ) 算法和八种软判决译码算法 概率测度的s p a 、似然比测度的s p a ( l r s p a ) 和对数似然比测度的三种 l l r s p a ( 基于t a l 血规则的l l r s 队、g a l l a g e rl l r s 队、j a c o b i 肌l l r s 队) 、最 小和算法( m s a ) 、n o n n a l i z e dm s a 和o 凰e tm s a ；分析了l l r 测度下各种译码 算法的复杂度；并对i e e e 8 0 2 1 6 e 标准、d m b t 标准【l l 】、s t i m i 标泄1 8 1 中u ) p c 码的各种译码算法进行了仿真和性能分析。 第四章主要研究了l d p c 码的量化译码问题。介绍了采样值的定点量化方法。 从消息测度上分析出了对数似然比测度量化译码性能的优越性。最后研究了对数 似然比测度下l d p c 码的初始消息和中间消息的特性，并给出了s t “i 标摧1 8 】中 l d p c 码的最终的定点量化设计方案。 第五章主要研究u ) p c 码抵御多径衰落的特性，介绍了两种常用的平衰落信 道模型一独立衰落信道模型和相关衰落信道模型。并对s t i m i 标”】中l d p c 码进 行了独立和相关衰落性能仿真和性能分析。 第六章对全文工作进行总结，并且提出了下一步的研究工作。 第二章l d p 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 码的构造方法；最后我们给出了 一种并行卷积l d p c 码的构造方法，在构造中，利用有限域交织器提高码的随机性、 并行卷积码编码器实现快速编码。将l d p c 码的校验矩阵分解为分别对应有限域交 织器和并行卷积编码器的两个子矩阵，通过子矩阵的设计对编码器进行优化，既 可以保证码的性能，又有效地提高了编码速度。 2 1l d p c 码的概念 l d p c 码是一种线性分组码，它的名字来源于其校验矩阵的稀疏性，即校验矩 阵中只有数量很少的非零元素，大部分都是零元素。 任何一种线形分组码都可用t 趾n c r 在 2 0 中提出的一种简单的表示形式一编码 二分图( t 锄n e r 图) 来表示。l d p c 码的t a 曲c r 图由两类节点组成：变量节点( v a 【r i a b l e n o d e ) 和校验节点( c h e c k n o d e ) ，分别对应于校验矩阵h 。( 为码长，m = j 一x 为 校验位数，置为信息位数) 中的列和m 行。同一个集合内部的节点没有连线，只 有属于不同集合的两点之间可能有连线，每一条连线对应于校验矩阵中的l 。 根据校验矩阵我们可以画出它的t a l l n e r 图( 图2 1 b ) 。图中变量节点集合( ，屯，而) 和校验节点集合( 毛，z ：，乙) 内部不存在相连的边，但两类节点之间存在着连线。 变量节点和校验节点之间存在连线意味着该变量比特参加了此校验方程，也就是 校验矩阵某一行中1 的位置。 h = 1oo1of 一石一司校验节点 11oo1 i o 1 q 1 0ll10i ol a i o olo1 i 1 o i l 变量节点 b 、 b 图2 1 ( 8 ，2 ，4 ) u ) p c 码的校验矩阵和t 姐n c r 图 图2 i b 的仇m e r 图中，四条虚线构成了一个有向的闭合环路，由五起始，经 过托_ 乙一乓晟后返回z 。在一个l d p c 码的t a 彻e r 图中，每个节点都会存在许 多这样的闭合环路，我们将其中长度最小的一个称为该节点的最小环长( s h o f t e s t c y c l e ) 。t 孤n c r 图中所有节点的最小环长中，长度最小的称为t a 肌e r 图的最小环长 ( 画m 1 ) ，上例的t a 仙e r 图中，百m l 与变量节点1 的最小环长相等，都是4 。 在译码过程中，每个子集合单独译码，子集合间通过共同拥有的变量节点进 l d p c 码的几个关键问题研究 行信息传递，经过多次迭代完成译码。t 锄n 盯还仔细分析了基于信息传递的译码 算法，证明了无环伽m e r 图上的信息传递的译码算法的最优性。但在实际当中， 伽m c r 图的构造采用随机图的方式，从而使得t a l l i l c r 图中存在小环路现象，这些 小的环路会造成译码信息的重复传递，影响了迭代译码算法的收敛性。所以在对 l d p c 码进行构造时，要尽量消除小环 6 】 2 2 。2 引。 2 2l 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 码校验矩阵列中非零元素的数目则是按一定比例变化的值。 2 2 1 规则l d p c 码的构造方法 我们将码长为h ，行重、列重( 校验矩阵中行和列的非0 元素的数目) 分别为后 和j 的规则l d p c 码表示为( 九，七) 。其中，玎= p 七。g a l l a g e r 证明当，3 时，码 的最小汉明距离与码长成正比，是满足g v 限的渐近好码【2 l j 【2 6 j 。d a v e ) ，等人通过 对l d p c 码性能研究发现，校验矩阵的列重量是决定l i ) p c 码性能的主要因素， 行重量对l d p c 码性能影响不大，因此，对于列重量固定而行重量不固定的l d p c 码也被看作是规则u ) p c 码。 m nc o i u n mw e i 呈l t 图2 2 ( a ) l 2 码率l d p c 码图2 2 ( b ) l ，4 码率l d p c 码 研究表明，不同码率对最优平均列重量的要求有所不同【27 。】。当误码率等于 1 0 弓时，图2 2 为通过m o n 协c 训。仿真得到的关于不同平均列重量校验矩阵所对 应的1 纪和1 愆码率u ) p c 码性能曲绀2 他引。在图2 2 ( a ) 中，1 2 码率l d p c 码的 最优平均列重量约为2 9 ，此时信噪比值为1 1 d b ；图2 2 ( b ) 中，l ，4 码率l d p c 码 最优平均列重量为2 6 ，其信噪比值为o 6 d b 。 g a l l a 盼提出的构造规则l d p c 码方法是将校验矩阵分解成- ，个子校验阵 h ，h ，一，h ，子矩阵中每列只含有一个非o 元素：第一个子矩阵的结构如一个单 让。仲让，姑 岔p)。 拈“妇o佶他， 第二章l d p c 码的几种构造方法 9 位阵，只是单位阵中的非零元素由1 行是列非o 元素代替：其它的子矩阵中的列则 是第一个子矩阵中的列的随机置换，如图2 3 所示，是g a l l a g 盯曾给出了一个 ( 2 0 ，3 ，4 ) 规则l d p c 码。 iiltoo000oo0oo0ooooo ooool 1l10ooo00o0oo0o 0oooo000l1 llo00o000 0 000oooo0 0 0 0 0l 1 1l00o0 o00ooo00oo o0ooo0111l l00 01oo010 0 0lo0 0ooo 0 010o0100 0l0 0o00 0lo0 0 0oloo010 0 o 0 0ol000l0o 0oolo00oool0o0l000l o oo0ooool0o0lo001000l loo00l0o0 oo1ooooo1oo 01ooo010001o o001ooo0 0olo0 00l0 0 0 olo00oo1o oo0lo 0 0olo 0 0olo 0looo oo0olo00oloo0o1ooooi 图2 3 ( 2 0 ，3 ，4 ) 1 氐密度校验码的校验矩阵 显然，g a l l a g e rl d p c 码校验矩阵的每个子矩阵的p 行的和均为全1 向量，因 此它不是一个满秩矩阵，其秩至多为珂一，+ l ，因为任意两个子矩阵的所有行向量 是线性相关的。而且，对于随机置换构造的g a l l a g 盯l d p c 码的校验矩阵，其秩以 很大的概率为一_ ，+ 1 。所以g a l l a g e rl d p c 码码率略大于1 舭。g a l l a g e r 的这种 构造l d p c 码的方法采用随机置换，这给实现带来了麻烦。而且这种随机构造的 l d p c 码的t a 皿e r 图中常有小环，影响了迭代译码算法的收敛性。 2 2 | 2 非规则l d p c 码的构造 在g a l l a g e r 构造的u ) p c 码中，检验矩阵的行重量和列重量都是恒定的。l u b y 等人研究发现，在经过优化设计的非规则扩展图上构造的扩展码具有更好的扩展 性能和更强的纠错能力【2 刀：此后，众多学者将这种思想用于u ) p c 码的设计。 研究表明，通过非规则t a 皿e r 图构造的非规则l d p c 码具有远好于规则l d p c 码 的译码性能，特别是在大码长的情况下表现尤为突出。在a w g n 信道中，误码率 为1 0 一，l 4 码率的情况下，d a v e y 设计的码长1 6 0 0 0 比特非规则u ) p c 码性能与 码长为4 0 0 0 0 比特的规则码相比，有o 4 d b 左右的编码增益【2 ”。 非规则n 仃图中，与变量节点和校验节点相连边的数目不固定，它们分布 遵循一对分布序列x = ( ，五，屯) 和p = ( 珐，见，如) ，其中丑、p ，分别表示 与度为f 的变量节点相连的边占总边数的比例和与度为的校验节点相连的边占总 边数的比例，吐，和d ，分别是变量节点和校验节点的最大度数。度序列满足关系 生。 = 1 ，名乃= 1 。度序列分布的多项式表示为旯( 工) = 垒丑工“1 ， p ( 工) = 乞p f 了川，且满足五( 1 ) = 1 和p ( 1 ) = 1 。对于( n ，工序) 规则l d p c 码，度分 布函数退化为五( 曲= 工卜1 ，p o ) = 工“1 。 0 l d p c 码的几个关键问题研究 三墓妻 仁。， 划脚，嚣划高 通过度序列分布五( 工) 和p ( x ) 构造的非规则u ) p c 码的码率为 r i， 胄p ) ：生坐；l 一攀 ( 2 2 ) j ：五( j ) 出 根据非规则t a l l t l e r 图的特点，我们可以对非规则u ) p c 码性能好于规则u ) p c 码的原因给出一个较直观的解释。在t 孤n c r 图中，与变量节点和校验节点相连边 的总数相等；从变量节点的观点来看，节点的度越大，它从相邻校验节点得到的 信息越多，这样就可以更加准确地判断出它的正确值；但从校验节点的观点来看， 却是相反的，对于校验节点来说度越小越好，如果校验节点的度越小，那它可以 给相邻的信息节点发送更多的有效信息。对于两种相反的需求，相对于规则t a 衄盯 图，非规则t a 衄e r 图显然能更好地实现两者的平衡。采用非规则t a t l i l c r 图构造的 l d p c 码，具有大度数地变量节点能很快地得到它的正确值，这样它就可以给校验 节点更加正确的概率信息，而这些校验节点又可以给小度数的变量节点更多的有 效信息，从而产生雪崩效应，大度数的变量节点首先获得正确的值，把它传送给 相邻的校验节点，通过这些校验节点又可以使度数小的变量节点获得正确信息， 因而非规则码就可以获得比规则码更好的性能。 非规则码的设计集中解决的问题之一是码的度序列分布选取。鼬c h a r d s o n 等人 提出的密度进化理论，可以用来指导非规则码的设计。 2 3 准循环l d p c 码 准循环u ) p c 码实际上属于g a l 】a g 盯l d p c 码，只是它不是采用随机列置换。 一个长聆= p c 的准循环的规则仳，c ) 一l d p c 码的校验矩阵可表示为： 日= l n p i p 。p i ，p 噬p j ，pb ：p ( 2 3 ) k 瞄； 第二章l d p c 码的几种构造方法 其中啭均为单位方阵。，循环右移q ，后构成的矩阵，显然该校验矩阵的秩至多 也是一，+ 1 。 由于其结构的特殊性，准循环l d p c 码只要有一个小环，就至少有p 个同样 大小的环，而正如2 1 中所说的，小环对码的性能影响很大，因此构造时要避免小 环的存在。准循环l d p c 码的环的分布只与d ，的取值有关，因此对它的环的分析 比较简单。 将各个小矩阵循环右移的位数写成个矩阵为： 巩= oo 0 0 4 2 j 口2 o 口r 2 口r ， ( 2 4 ) 在该矩阵上按行列交替顺序画一个环路，若奇数节点上的数值和与偶数节点上的 数值和相同( 模力，则该环路构成一个环，否则该环路不构成环【鹌弗】。对于相同码 长和码率的消去4 环后随机构造的准循环l d p c 码的性能基本相同，而且消4 环 最简单，只需保证( 2 - 4 ) 中任意画一个矩形的两个对角线元素和不相等( 模p ) 。因此 本文后面采用的码就是通过消4 环后随机构造再择优选取的，具体构造算法如下： 步骤1 初始化：将所有子矩阵循环右移的位数初始化为0 。 步骤2 从第2 行第2 列开始按先列后行的顺序，在l 到p 1 之间产生随机数， 每产生一个新随机数就与已经产生的所有随机数进行比较，若有相同的就重新产 生一个该位置的随机数并重新进行比较，直到该随机数与已经产生的所有随机数 都不同为止。 步骤3 从第2 行开始，让其与后面各行开始逐行检查两行所构成的所有矩形 的两个对角线元素模p 和是否相等( 无需检查第1 列) ，若发现有相等的，返回步骤 2 。 上面的步骤2 保证了包含第1 行和第1 列元素的所有矩形的对角线元素模p 和不会相等，步骤3 保证了其它矩形的对角线元素模p 和不会相等，因此该算法 生成的准循环l d p c 码不会有4 环的存在。当然在产生随机数的同时，也可以考 虑其它矩形的对角线元素模p 和是否相等，但作者觉得这样编写程序比较复杂， 而且当p 的值比较大，而，和c 的值比较小时，该算法的重复次数还是相当少的。 对于非规则的准循环l d p c 码，日中的含有p p 的零阵，也是大小为忾。，l b 的矩阵。在巩中日的零阵用1 表示。而只要保证了巩中非零的对角线元素模p 和不会相等，就不会有四环的存在。 i e e e8 0 2 1 6 e 标准【1 9 1 中构造了非规则的准循环l d p c 码，构造中采用优化的 度序列分布。我们采用计算机仿真的方法对该标准中码长为2 3 0 4 ( 旷9 6 ，l i = 2 4 ) ， l d p c 码的几个关键问题研究 码率为1 2 ，2 3 ，3 4 ，5 6 的l d p c 码进行了性能仿真，2 3 a ，3 4 a 与2 3 b ，3 “b 分别具有相同的度序列分布，但循环移位元素的位置不同。仿真所采用的信道模 型是a w g n 信道，假定采用b p s k 调制方式，译码采用和积算法( s p a ) ，最大迭 代次数为2 0 次。仿真曲线如下图2 4 所示，从图2 4 可以看出，码长相同时，码 率越小的l d p c 的性能越好：对于相同码长、码率和度序列分布的随机构造的非 规则u ) p c 码的性能基本相同。 。、迤，：，一 ：、 ： 每 f 、 t尊j jij j t x = ： = ! # ：= = ： ：= = 一 、 t t、：。 一一码率1 ，2 5 涎骁j 杀 一一码率2 ，3 + 码率2 ，阳 i j 、 、 码率“：j 、 、 十码率3 ，4 b、 n 弋； + 码率5 ，6 1 一 e n o ( d b j 图2 4 e e8 0 2 1 6 c 中码长为2 3 0 4l d p c 码的性能 2 4 并行卷积l d p c 码的构造 本节给出并行卷积u ) p c 码的一种构造方法。在构造中，利用有限域交织器 提高码的随机性、并行卷积码编码器实现快速编码。将l d p c 码的校验矩阵分解 为分别对应有限域交织器和并行卷积编码器的两个子矩阵，通过子矩阵的设计对 编码器进行优化，设计更为简单。仿真结果表明，与p e g 方法构造的l d p c 码相 比，在码长1 0 0 8 时，误码率性能上约有o 2 d b 的提高。 2 4 1 研究背景 1 9 6 3 年，g a l l 醒盯在他的博士论文【6 】中给出了一种随机构造规则l d p c 码的方 法。采用这种方法构造的u ) p c 码在中短码长时，其t a n n 盯图中存在大量的小环， 严重影响了迭代译码的收敛性能；并且编码时直接采用信息比特序