（通信与信息系统专业论文）ldpc码的代数构造及译码算法研究.pdf

摘要 低密度奇偶校验码( l o w - d e n s 时p 撕锣c h e c k l d p c ，c o d e s ) 是一种基于图 模型和迭代译码的纠错编码方案，性能非常接近s h 锄o n 容量限，且译码算法复 杂度较低，近年来逐渐成为人们的研究热点。 本文对l d p c 码的代数构造及其迭代译码算法进行了深入研究，在以下几个 方面获得了关键性研究成果： 1 研究了基于中国剩余定理的由短分量码设计长码的准循环l d p c 码构造方 法，指出该方法中由于分量码的结构特征导致所构造的新码包含很多短环，在迭 代译码下影响了纠错性能。基于上述研究，对原c r t 方法进行了推广和改进，减 少了新码中短环的数量，从而使所构造的准循环l d p c 码具有更好的纠错性能， 同时通过放宽参数选择的条件，构造出了更多具有优异性能的准循环l d p c 码。 2 利用欧氏几何的结构特征，提出了一种基于循环置换矩阵的准循环l d p c 码构造方法，该方法构造的码对应的t a i l l l e r 图中包含较少的短环，具有与已有的 欧氏几何码几乎相同的纠错性能。 3 研究了一种已有欧氏几何准循环l d p c 码的最低重量码字分布后，找到了 一个产生最低重量码字的充分条件，提出了一种准循环l d p c 码构造方法，该方 法可以减少满足该充分条件的最低重量码字，设计出的准循环l d p c 码具有更低 的错误平层，在低误码率区域具有更好的纠错性能。 4 研究了l d p c 码基于软信息的各种比特翻转译码算法，给出了一种具有极 低计算复杂度的改进比特翻转译码算法，该算法译码速度很快，时延很短。 5 基于卷积l d p c 码连续数据编译码传输的结构特性，给出了一种迭代反馈 译码算法，该算法运用反馈信息，在更新当前变量节点消息时及时应用相关历史 变量节点的最新消息，加快了信息的传递速度。新算法仅需很少的迭代次数，即 可获得比已有算法更好的纠错性能，有效降低了卷积l d p c 码的译码复杂度并减 小了译码时延。 6 根据研究成果5 ，设计了一种卷积l d p c 码的快速收敛译码算法，在不损 失纠错性能的前提下，译码器具有更低的译码复杂度及译码时延，从而使卷积 l d p c 码更适于实际应用。 关键词：低密度奇偶校验码准循环码卷积码迭代译码 a b s t r a c t b e i n gap o w e r 如lc l a s so fe r r o r - c o n i e c t i l l gc o d e sb 2 l s e do n 伊a p h i c a lm o d e l s 锄d i t e r a t i v ed e c o d i n ga l g o r i 恤i l s ，l o w d e n s 毋p 撕妒c h e c k ( l d p c ) c o d e sh a v er e c e n t l y r e c e i v e dn m c ha t t e n t i o nd u et 0t h e i rc a p a c 时印p r o a c h i n gp e r f 0 m 姗c ea n dr e l a t i v e l y l o wd e c o d i n gc o r n p l e x i 够 t h i sd i s s e n a t i o ni si n t e n d e dt 0i i e s t i g a t et l l ea l g e b r a i cc o n 殉r i l c t i o na n dt h ei t c r a t i v e d e c o d i n ga l g o r i t l 蚰o fl d p cc o d e s t h em a i nr e s u l t sa r e 羽l m m a r i z e d 觞f o l l o w s 1 am e t h o do fc o n s t m c t i n gq u a s i c y c l i c ( q c ) l d p cc o d e so fl a 唱e l e n g t hb y c 0 1 1 1 _ b i n i n gq c - l d p c c o d e so fs m a ul e n g t ha sm e i rc o m p o n e mc o d e sv i at h ec h i n e s e r e m a i n d e rt l l e o r e m ( c r t ) i sr e s e a r c h e d d u et ot h es i m i l a r 咖l c t u r a lp r 叩e n yo ft h e c o n l p o n e n tc o d e s ，t h e r ee x i s tal o to fs h o r tc y c l e si nt h et a r m e rg r a p ho ft h ed e s i g l l e d c o d ea n dt h ep e r f o n n a n c ei sn o tg o o de n o u g l lw i t hi t e r a t i v ed e c o d i n g ag e n e r a l i z e d c r tm e t h o di sp r o p o s e dt oi m p r 0 v et h ec i 玎c o r n b i n i n gm e t h o da n dd e s i g l lm u c hm o r e a n db e t t e rq c - l d p cc o d e sw h e nt h ep 撕哆c h e c km a t r i c e so ft h ec o m p o n e n tc o d e sa r e g i v e n b yp e m m t i n gt h eb l o c kr o w so ft h ep a r i t ) rc h e c km a t r i c e so fc o m p o n e n tc o d e s ，a l o to fs h o r tc y c l e si nt h et a n n e rg r a p ho ft h ed e s i g n e dc o d ec 加b ee l i m i n a t e da i l da l a 唱en u n l b e ro fq c l d p cc o d e sw i t hb e t t e rp e i f b l l ：n a n c ec a nb ed e s i g n e d b y 1 0 0 s e l l i n g 恤c o n d i t i o nf o rd e t e 衄i n i n gt h ei n t e m e d i a t ep a r a 衄e t e r s ，am u c hl a r g e rc l a s s o fq c - l d p cc o d e sw i t hb e t t e rp e r f o n n a n c ec a nb ed e s i g n e d 2 b a s e do nt h e 曲n l c t i l r a lp r o p e r t i e so fe u c l i d e a ng e o m e n xa na l g e b r a i cm e t h o di s p r o p o s e dt oc o n s 仃u c tac l a s so fq c l d p cc o d e sw i t l lc i r c u l a n tp e m l u t a t i o nm a t r i c e s t h i sc l a s so fq c l d p cc o d e sc o n t a i n ss m a l l e rn u l n b e ro fs h o r tc y c l e si nt l l e1 a i m e r g r a p h 锄dh a ss i n l i l a rp e 响聊a n c ew i t ht h ce x i s t i n gq ce u c l i d e a ng e o m e 时l d p c c o d e s 3 t h ed i s t r i b u t i o n so fc o d e w o r d sw i t hm i n i m u mw e i g h to ft h ee x i s t i n gq c e u c l i d e a ng e o m e 仃yl d p cc o d e sa r ea 1 1 a l y z e da n das u 伍c i e n tc o n d i t i o nf o rac o d e w o r d t oh a v em i n i m u mw e i g l l ti sf 0 u n d ac o n s t m c t i o nm e t h o d ，w h i c hc a nr e d l l c et h en u m b e r o fi i l i n i m u mw e i g h tc o d e w o r d ss a t i s 母i n gm i ss u m c i e n tc o n d i t i o n ，i sp r o p o s e d t h en e w q c - l d p cc o d e sh a v em u c hl o w e re n 0 rf l o o ra n dp e r f b n nb e t t e ra tl o wb e r 4 s o m ew e i g h t e db i t - f l i p p i n gd e c o d i n ga l g o r i t h m sb a s e do ns o ri n f 0 姗a t i o na r e s t u d i e da n dam o d i f i e d b i t f l i p p i n gd e c o d i n ga l g o r i t h m w i t h s i g n i f i c a n t l y l o w c o m p l e x i 哆i sp r o p o s e d t h en e wa l g o r i m mh a ss i 印i f i c a n t l yh i g hd e c o d i n gs p e e d 锄d s h o r td e c o d i n gd e l a y 5 b a s e do nt h ea b i l i t yo fc o n t i n u o u s 缸a n s 觚s s i o nf o rl d p c c o n v o l u t i o n a lc o d e s 姐 i t e r a t i v ef e e d b a c kb e l i e fp r o p a g a t i o nd e c o d i n g a l g o r i m mi sp r o p o s e d t l l en e w a l g o r i t h mu t i l i z e st h em o s tc u r r e n tv 习u r i a b l ei n f 0 肌a t i o no ft h ep a s tc o d eb i t st 0a c t i v a t e t l l ev a r i a b l en o d e si n o r ee m c i e n t l yb y 印p l y i i l g 佗e d b a c ki n f o m a t i o na te a c hd e c o d i n g i t e r a t i o n t h ep r o p o s e da l g o n m mw i t hs m a un u n l b e ro fi t e r a t i o n sc 龃a c h i e v eb e t t e r p e r f 0 n n a n c et h a nt h a to ft h ee x i s t i n ga l g o r i t h m ，w h i l et h ed e c o d i n gc o m p l e x i 哪a 1 1 d l a t e n c ya r ee f r e c t i v e i yr e d u c e d 6 i n s p i r e db yc o n c l u s i o n5 ，af a s tc o n v e 唱e n c ed e c o d i n ga l g o r i t h mf o rl d p c c o n v o l u t i o n a lc o d e si s d e v e l o p e d ab e t 研p e 墒m 锄c ei s a c h i e v e d ，w h i l et h e c o m p l e x i 够 a n d d e c o d i n gd e l a ya r ee 日e c t i v e l yr e d u c e d ，w h i c hm a k e sl d p c c o n v o l u t i o n a ic o d e sb em o f es u i t a b i ef o r p r a c t i c a ia p p l i c a t i o n s k e y w o r d s ：l o 、r d e n s i t yp a r i t y c h e c kc o d e s q u a s i c y c h cc o d e s c o n v o l u t i o n a lc o d e s i t e r a t i v ed e c o d i n g 独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 本人签名：刘匠竿 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 本人签名： 导师签名： 日期：塑f 翌：主! 隆 日期：丝z 垒：i ：! z 第一章绪论 第一章绪论 本章从s h 锄1 0 n 的信道编码定理出发，概述了信道编码的发展历程。然后对 l d p c 码的提出、发展以及当前研究的热点问题等进行了综述最后给出了本文的 研究范围以及全文的章节安排 1 1 信道编码的发展历程 1 9 4 8 年，美国贝尔实验室的c e s h 锄o n 在其开创性的权威论文通信的数 学理论( t h em a t h e m a t i c a lt h e o 巧o f c o m m u n i c a t i o n s ) 【1 】中提出了著名的信道编码 定理，即：对于一个给定的有噪信道，存在一个确定的信道容量c ，如果信道的信 息传输速率尺小于c ，则当码长足够大且采用最大似然译码时，总存在一种编 码方法，使接收端译码错误概率任意小，反之，如果信息传输速率尺大于信道容 量c ，则不可能实现无差错通信。这个存在性定理告诉我们可以以接近信道容量的 传输速率进行可靠通信，标志着信道编码这一学科的创立。但遗憾的是，该定理 虽然指出了可以通过一定的编码方法在传输速率不大于信道容量的前提下实现可 靠通信，但并没有给出具体实现逼近s h a 妯o n 限的编码方法。 从s h a i l i l o n 信道编码定理可知，随着分组码的码长或卷积码的约束长度的增 加，系统可以取得更好的性能( 即更大的保护能力或编码增益) ，而译码应该采用 最大似然译码。但是，最大似然译码算法的复杂性随码长呈指数增加，当码长较 大时，最大似然译码几乎不可实现。因此，几十年来，信道编码研究者们一直致 力于寻找纠错能力尽可能接近s h a n n o n 极限且编译码复杂度较低的可以实际应用 的信道编码方案。 线性分组码是发展最早的一类纠错码，它以代数中的群、环、域理论和有关 的几何理论作为数学基础【2 1 。第一个线性分组码是由汉明( h a i l l 【i l i n g ) 在1 9 5 0 年发 现的，它能纠单个错误【3 1 。五十年代又陆续发现了g o l a y 码吲以及i u 码【5 6 】，b o s e 和h o c u e n 曲e m 在1 9 5 9 年及r a y c h a u d h 嘶在1 9 6 0 年分别独立发现能纠正多个错误 的b c h 码r e e d 和s o l o m o n 在1 9 6 0 发现了非二进制r s 码【引。 卷积码是另一类重要的信道编码，它最早是由e l i a s 等人于1 9 5 5 年提出【引，在相 同复杂度的条件下可以获得比分组码更高的编码增益，但同时也增加了分析和设 计的复杂性。随后，出现了卷积码的各种译码方法：1 9 6 3 年m a s s e y 提出的门限译 码【l o 】是一种利用码代数结构的代数译码，1 9 6 1 年由w o z e n c r a r 提出，1 9 6 3 年由f a l l o 改进的序列译码 1 2 】是一种实用的概率译码方法，l9 6 7 年v i t e r b i 提出的v i t e r b i 译码 【1 3 】是一种最大似然译码算法。当比特差错概率( b e r ) 是1 0 。5 时，非编码传输下，最 2 西安电子科技大学博士学位论文i ，d p c 码的代数构造及译码算法研究 佳相干p s k 系统的比特信噪比( 眦) 与理论极限情况相差1 1 d b 。而二进制卷积编码 配合序列译码，可以使历o 与理论极限仅差4 6 6 6 d b 。随着卷积码的各种译码方 法尤其是v i t e r b i 译码算法的出现，卷积码逐渐得以广泛应用。 在传统的信道编码技术中，代数编码理论占据了主导地位，传统的纠错码都 不是实用好码，受到截止速率( c u t o f r r a t e ) 的限制。f o m e y 在1 9 6 6 年提出了级联 码( c o n c a t e n a t e dc o d e s ) 【1 4 1 ，通过内码和外码的级联来获得接近信道容量的性能， 同时降低了实现复杂度，向实用好码的方向前进了一大步。将r s 码与卷积码级联， 当b e r 为l o _ 5 时，系统的性能达到与理论极限大概相差1 8 d b 。 1 9 9 3 年，b e 盯0 u 等人提出了t u r b o 码【1 5 ，1 6 1 ，为信道编码理论带来了突破性的革 命，打破了将截止速率作为可靠通信速率门限的概念。b e n d u 等人很好的应用了 s h a i l i l o n 信道编码定理中随机编码的条件，将卷积码和随机交织器结合起来，同时 采用软输出迭代译码算法来逼近最大似然译码，获得了相当接近s h 锄o n 极限的译 码性能。码率为l 2 的t u r b o 码在b e r 为l o 5 时，可以获得与理论极限仅相差0 7 d b 的 优异性能。然而，n 曲。码也存在一些缺点：如译码复杂度高，译码时延长，存在 错误平层现象等。 t u r b o 码的研究引发了人们对图模型和迭代译码的研究热潮，在研究过程中， m a c k a y ，n e a l 和w i b e 略几乎同时发现早在1 9 6 2 年由g a l l a g e r 提出的低密度奇偶 校验码( l o w d e n s 时p 撕西c h e c k ，l d p c ，c o d e s ) 【1 7 博j 也是一种实用好码，具有比 t u r b o 码更低的线性译码复杂度。在b e r 为1 0 击的情况下，码长为l o 、速率为l 2 的l d p c 码的性能与理论极限仅仅相差0 0 4 d b 。与t u r b o 码相比，l d p c 码具有 译码复杂度低，更强大的纠错能力和更低的错误平层等优点，同时由于l d p c 码 迭代译码算法为并行算法，译码时延远远小于t u r b o 码。这些都为l d p c 码的应 用提供了广阔的前景。 1 2l d p c 码的发展与现状 早在1 9 6 2 年g a l l a g e r 就提出了规则低密度奇偶校验码( 也称g a l l a g e r 码) 和 迭代译码的概念【1 7 1 引。g a l l a g e r 证明了这类码具有很好的距离特性，经过迭代译码 可以获得随码字长度呈指数降低的比特错误概率，虽然l d p c 码表现出了非常好 的纠错性能，但由于当时计算能力和存储能力的限制，人们并没有认识到l d p c 码的优越性。在l d p c 码被提出后的三十多年时间里，并未受到应有的重视，只 有少数几篇论文对其进行了进一步的研究。这期间，最重要的成果可能就是r m t a n n e r 提出的l d p c 码的双向图表利1 9 】，在t a n n e r 图上可以直观理解l d p c 码的 译码过程。 直到上世纪9 0 年代中期，m a c k a y 和n e a l 利用随机构造的t a n n e r 图研究了 第一章绪论 3 l d p c 码的性能【2 0 ，2 ，发现采用和积译码算法的规则l d p c 码具有和t u 曲。码相似 的译码性能，长码时甚至超过了t u r b o 码，这一结果引起了信道编码界的极大关注。 1 2 1l d p c 码校验矩阵的构造 在l d p c 码的构造方面，许多学者提出了各种构造方法，主要可以分为两大 类，( 1 ) 随机构造方法：根据一定的设计准则和围长、度分布、止集等条件用计 算机随机搜索出所需要的校验矩阵；( 2 ) 结构化构造方法：利用代数方法或组合 方法构造出所需要的校验矩阵。 在m a c k a y 和n e a l 重新发现l d p c 码优异性能的同时，s p i e l m a n 和s i p s e r 提 出了基于二部图的扩展码【2 2 ，2 3 1 。在对扩展码的研究中，他们证明了一个随机构造 的t a 皿e r 图以很大的概率为好的扩展图，而由好的扩展图构造的线性纠错码是渐 进好码，从而证明了采用随机t a l l l l e r 图构造的l d p c 码以很大概率是渐进好码。 l u b y 等人将采用非规则t a n n e r 图构造的扩展图用于删除信道，称之为t o m a d o 码 【2 4 】。由于采用了非规则的t a m e r 图，t o m a d o 码具有更大的扩展性以及更好的收 敛性，纠错能力更强。此后，采用优化度序列设计的非规则t a l l i l e r 图被用于构造 l d p c 码，称为非规则l d p c 码，与规则l d p c 码相比，非规则l d p c 码的性能 得到了显著的提高。m a c k a v 等人提出的随机l d p c 码构造方法【2 雌1 】可以使码所对 应的t a n l l e r 图中环数目较少，码字具有很好的纠错性能。x i a o y uh u 等学者采用 逐步最优思想提出了一种称为p e g ( p r o g r e s s i v ee d g eg r o w t h ) 的构造方法。该算 法可以在给定度序列条件下构造较大围长的l d p c 码【2 5 1 。p e g 算法是一种逐个建 立变量节点和校验节点之间关联的构造有大环t a i l n e r 图的方法。事实上，影响迭 代译码性能的因素，不仅有环的长度还有环的连通性，因此t a ot i a n 等提出了a c e 构造方法【2 们，在构造l d p c 码时抑制掉连通性差的环，提高了译码性能。c a m p e l l o 等学者提出的比特填充( b i t - f i l l i n g ) 【2 7 】及e x t e n d e db i t - f i l l m 一2 8 】构造方法可以在 给定校验矩阵大小，列重及最大行重时，使得围长尽可能大，或者在给定码长， 围长及行列重时使得码率尽可能大。 在结构化构造方法方面，s h ul i n 等学者提出了基于有限域构造l d p c 码的方 法【2 9 】以及基于有限几何构造l d p c 码的方法【3 0 】，这类码均为循环码或准循环( q c ) 码，具有较好的最小距离，消除了t a n n e r 图中的4 环，在高码率时可以获得较好 的性能，并且可以用简单的反馈移位寄存器实现线性时间编码。同时，q c l d p c 码的代数结构也有利于高速大规模集成电路( v l s i ) 的实现。此外，他们还提出 了基于r s 码构造l d p c 码的方法，这类码也具有良好的最小距离特性【3 l 】。t a n n e r 和f o s s o r i e r 等人提出了基于循环置换矩阵构造的q c l d p c 码【3 2 ，3 3 】，并推导了构 造给定围长的q c l d p c 码的充分必要条件。这类码容易消除小环，并且同样适宜 4 西安电子科技大学博士学位论文i ，d p c 码的代数构造及译码算法研究 用反馈移位寄存器实现线性编码。在此基础之上，t a 皿e r 利用q c l d p c 码的循环 矩阵构造了卷积l d p c 码。此外，还有一些基于其他数学工具构造结构化l d p c 码的方法，包括平衡不完全区组设计( b i b d ) 【3 4 1 、循环差集、二进制序列等。 对于随机构造的码，校验矩阵是随机生成的，码长和码率比较灵活，纠错性能 好，但是由于校验矩阵的随机性，无法实现简单编码，并且校验矩阵的存储复杂 度较高，而复杂度决定了系统结构和设计。结构化构造的码，可以克服短环的产 生，具有确定的结构，生成的l d p c 码是循环码或准循环码，可以实现线性时间 编码，而且可以设计g i n h 较大的码。结构化l d p c 码在中短码长时性能与随机构 造的l d p c 码相当，长码时略差于随机构造的码。 此外，d a v e y 和m a c k a y 从减少t a 衄e r 图上小环的概念出发提出了基于g f ( g ) ， 印 2 的多元l d p c 码陬3 6 1 ，进一步提高了l d p c 码的译码性能，同时也带来了译 码复杂度的提高。 1 2 2l d p c 码的编码 l d p c 码是通过其稀疏的校验矩阵来定义的，编码也可以根据校验矩阵的校验 方程实现。m a c k a v 首先给出了l d p c 码作为线性分组码的编码方案，利用高斯消 去法通过校验矩阵得到生成矩阵，再对信息序列进行系统编码，然而利用高斯消 去法得到的生成矩阵一般不是稀疏的，编码复杂度通常与码长的平方成正比。随 后m a c k a y 又提出了基于校验矩阵下三角形式的线性复杂度编码方法【3 1 7 1 ，但这种 方法对校验矩阵行列重及矩阵形式进行了一定的限制，导致了一定程度的性能损 失。n e a l 提出了基于矩阵l u 分解的编码方法p 引，但是复杂度依然很高。 黜c h a u r d s o n 等学者提出了基于校验矩阵近似下三角形式的低复杂度编码方法 【”】，通过对校验矩阵进行行列变换获得近似下三角矩阵，保持了校验矩阵的稀疏 性，从而在不损失性能的同时有效降低了编码复杂度。l i p i n g 等提出了一类基于 半随机矩阵的编码方法m 】，该方法要求校验矩阵的右半边为双对角方阵，左半边 为随机矩阵，可以实现线性时间编码。 一类具有良好代数结构的l d p c 码一准循环l d p c 码具有更低的编码复杂度， 可以通过反馈移位寄存器实现线性编码【4 1 1 ，在l d p c 码的研究领域受到了广泛的 关注。 1 2 3l d p c 码的译码 g a l l a g e r 在提出l d p c 码的同时，给出了两种迭代译码算法：硬判决 b i t f l i p p i n g ( b f ) 算法和软判决算法。硬判决算法操作简单，易于硬件实现，但 是性能较差；软判决算法性能较好，但实现复杂度太高。 第一章绪论 在硬判决算法方面，为了改善硬判决译码的性能，yk o u 等提出了一种基于 软信息的加权比特翻转( w b f ) 算i 去【3 0 l ，在每轮迭代中，对每个变量节点按某种方 法计算其可靠性，将可靠性最小的变量节点进行翻转，w b f 算法在性能上优于硬 判决b f 译码算法，但引入了可靠性的计算，导致译码复杂度增加。由于w b f 算 法在计算变量节点的可靠性时仅考虑了校验节点的信息，j z h a n g 等人提出了改进 的加权比特反转( m w b f ) 算法【4 2 1 ，在计算变量节点可靠性时加入了变量节点的 信息，提高了译码性能。f g u o 等人注意到w b f 和m w b f 算法中只考虑了校验 节点的特定信息，其提出的l 湛w b f 考虑了校验节点的全部信息【4 3 】，进一步提高 了性能，而没有增加复杂度。 在软判决算法方面，g a l l a g e r 提出了消息传递算法( m p a ，m e s s a g ep a u s s i n g a 1 9 0 r i t h m ) 【1 7 】，也称置信传播算法( b p ，b e l i e f p r o p a g a t i o n a l g o r i t l l i l l ) ，k s c l l i s c h a n g 等对消息传递算法作了推广m 1 ，将它扩展为一种更加通用的算法一和积算法( s p a ， s u m p r o d u c ta 1 9 0 r i t h m ) ，并指出和积算法实际上包含了大量的实用译码算法( 如 前向后向算法、p e a r l s 传播算法、v i t e r b i 算法等) 。和积算法在迭代过程中需计算 三种中间变量消息，即变量消息，校验消息和软判决消息。如果将软判决消息作 为变量消息进行迭代，则和积算法简化为迭代a p p ( ap o s t e r i o r ip r o b a b i l i t y ) 算法， 可以在损失一点性能的基础上减少运算复杂度。和积算法在计算校验消息时需要 用到双曲正切运算，实现较为复杂，f o s s o r i e r 研究了低复杂度的迭代译码算法【4 5 ，4 6 】， 将校验消息的计算简化为简单的求符号运算和求最小值运算，提出了b p b a s e d 算 法( 也称最小和算法( m n s u m a l g o r i t h m ) ) 和a p p b a s e d 算法。由于校验消息计 算的简化，b p b 雏e d 算法的性能受到了一定的影响，修正b p b a s e d 算法一 n o m a l i z e db p b a s e d 算法和o 凰e tb p b a s e d 算法通过对校验消息计算的进一步修 正可以在不太增加复杂度的基础上获得性能的较大提高。 综上所述，l d p c 码采用迭代译码算法，在复杂度和性能上可以得到很好的折 中，既可以选择实现简单、性能稍差的b f 算法，也可以选择实现复杂、性能优越 的b p 算法，又可以选择趋于中间的各种改进算法。 在译码性能分析方面，t a 加e r 在文献 1 9 中详细分析了最小和算法与和积算法 两种信息传递算法，并证明了基于有限无环t a 衄e r 图的最小和译码算法与和积译 码算法的最优性。但在实际当中，t a 皿e r 图中不可避免的存在小环路现象，小环 路会造成译码信息的重复传递，使译码过程中的消息不满足独立性假设，从而影 响了迭代译码算法的收敛性。r i c h a r d s o n 等学者利用密度进化理论来测度l d p c 码 的译码性能【4 7 4 8 1 。r i c h a r d s o n 等在对l d p c 码的研究中发现，译码信息的迭代传递 过程中存在着译码阈值( t h r e s h o l d ) 现象，即当信噪比大于译码阈值时，迭代译码 可使误码率趋于零，反之当信噪比小于译码阈值时，无论采用多长的l d p c 码， 经过多少次迭代译码，总存在一定的错误概率。应用中心极限定理，r i c h a r d s o n 等 6 西安电子科技大学博士学位论文i ，d p c 码的代数构造及译码算法研究 证明了有限随机有环图的译码阈值可以逼近无环图的译码阈值。通过建立在无环 图上的密度进化理论，可以精确地计算无环图上l d p c 码的译码阈值，分析其译 码收敛条件，从而近似估算有环t a r u l e r 图上l d p c 码的性能。研究表明，译码阈 值的大小与l d p c 码的构造参数密切相关，采用优化度序列设计的非规则l d p c 码可以有效地改善阈值，因此密度进化理论不仅可以分析译码性能，还可以用于 指导l d p c 码的优化设计。c h u n g 等人通过对密度进化理论的研究【4 9 巧，进一步 提出了应用高斯逼近原理来简化译码阈值计算和收敛性分析，从而使测度l d p c 码性能的模型由多参数动态系统的密度进化理论模型简化为单一参数动态系统的 高斯逼近模型。 1 3 论文的内容安排及研究成果 本文研究了分组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 码的基本原理，分析了阵列l d p c 码的结构 特征，推广并改进了基于中国剩余定理的由短分量码设计长码的准循环l d p c 码 构造方法，获得了一类具有更好纠错性能的准循环l d p c 码。 第四章研究了欧氏几何l d p c 码的构造技术，提出了两种准循环l d p c 码的 构造方法。第一类准循环l d p c 码是基于循环置换矩阵设计的，其相应的t a l l l l e r 图中具有较少的短环。第二类准循环l d p c 码是基于循环矩阵设计的，该类码具 有较低的错误平层性能。 第五章分析了l d p c 码各种基于软信息的比特翻转译码算法，提出了一种具 有极低计算复杂度的改进比特翻转译码算法，该方法运用两个译码门限，从而有 效地提高了译码性能。 第六章基于卷积l d p c 码连续数据编译码传输的结构特性，给出了两种高效 的迭代译码算法。算法一为迭代反馈译码算法，利用反馈信息有效加快了信息传 递速度，降低了译码复杂度并减小了译码时延；算法二将算法一与已有译码算法 相结合形成一种卷积l d p c 码的快速收敛译码算法，译码器具有更低的译码复杂 度及译码时延，从而使卷积l d p c 码更适于实际应用。 第七章为全文的总结与展望。 第二章l d p c 码的编译码原理7 第二章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 码最初由g a l l a g e r 于l9 6 2 年提出，然而之后的三十年里却被人们所遗 忘，仅有少数学者对其进行了少量研究。直至t u r b o 码的出现，l d p c 码才又重新 受到人们的关注。 域g f ( g ) 上的l d p c 码是一种线性分组码，由其校验矩阵日的稀疏性而得名， 即校验矩阵中大部分元素为“0 ，仅包含很少的非零元素。码长为疗，信息序列长 为七的l d p c 码c 可以由校验矩阵h 唯一确定，码c 就是日的零空间，日的每一 行对应一个校验方程，每一列对应码字的一个比特，满足如下方程的刀维向量l ，： 纠7 t ：0( 2 - 1 ) 即为码c 的一个码字。日的每一行中非零元素的个数称为日的行重，每一列中非 零元素的个数称为日的列重。根据校验矩阵行列重的不同，l d p c 码可分为两类： 规则( r e g u l a r ) l d p c 码和非规则( i r t e g u l a r ) l d p c 码。若校验矩阵日每行的非 零元素个数相同，且每列中非零元素个数也相同，则该l d p c 码称为规则l d p c 码，否则称为非规则l d p c 码。下面给出规则l d p c 码的定义。 定义2 1 ：( 厂，p ) 规则l d p c 码定义为具有如下结构特性的校验矩阵日的零空 间： ( 1 ) h 的每行行重为常数p ； ( 2 ) 日的每列列重为常数y ； ( 3 ) 与码长和日的行数相比，p 和y 都很小。 上述特性( 3 ) 表明校验矩阵日中非零元素的密度很小，即校验矩阵具有稀疏 性。例2 1 给出了一个码长为1 5 的( 4 ，4 ) 规则l d p c 码的校验矩阵。 例2 1 考虑式( 2 2 ) 给出的矩阵何，该矩阵的行重和列重均为4 ，与码长和 的行数相比，行重和列重都比较小，非零元素“l 所占的比例为0 2 6 7 ，日是 个稀疏矩阵，其零空间为一个码长为1 5 的( 4 ，4 ) 规则l d p c 码。 8 西安电子科技大学博士学位论文l d p c 码的代数构造及译码算法研究 日= ( 2 2 ) 根据校验矩阵中元素取自的域不同，l d p c 码可分为二元l d p c 码和g 元l d p c 码。口元l d p c 码可获得比二元l d p c 码更好的纠错性能，但同时具有更高的译码 复杂度，本文主要考虑g f ( 2 ) 上的二元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 码具 有确定的结构，可实现简单编码且存储复杂度较低。 2 2l d p c 码的图模型表示 l d p c 码由于其优异的纠错性能及其简单的迭代译码而备受研究学者们的青 睐，其迭代译码是基于图模型【1 9 朋，5 2 ，5 3 】进行消息传递及消息更新的，因此，有必要 介绍一下l d p c 码的图模型表示。 定义2 2 ：图( g r a p h ) g 定义为一个三元组( y ，e ，) ，其中y a ，是图g 的 节点集合，e 是边的集合，是边集到节点对y y 上的关联函数。 如果节点v y 是边p e 的端点，则称1 ，和p 是相连的。与节点1 ，y 相连的边 的个数称为节点，的度，记为d ( 1 ，) 。若节点与边的交替序列( v l ，p l ，屹，p 2 ，坛， 峙1 ) 满足：与“l f 七) 相连的节点为和v f + l ，则称此序列为一条路径，其中 ，l 和1 分别称为起始节点和终止节点。若一条路径的起始节点和终止节点为同一 节点，并且路径中其他节点仅出现一次，则此路径构成一个环( c y c l e ) 。环的长度 为环所经过的边的数目，图g 中最短环的长度称为图g 的围长( 百n h ) 。 定义2 3 ：若图g 的节点集合y 可以划分为两个子集k 和，且满足 l 0 0 0 1 o 1 l o 0 0 0 0 0 o o o 0 l o l 1 o 0 0 0 0 o o 1 o 0 1 o l 1 0 o 0 0 0 0 0 l 0 o l o 1 1 0 o 0 o 0 0 0 l 0 0 l o l l 0 0 o o o o 0 l 0 o o 0 1 l 0 0 0 o o 0 0 l o o 0 l l 1 o 0 0 o 0 o 0 l 0 0 0 1 0 l o o o o o o o 1 0 o 0 l 0 l o o o o o o 0 1 0 o 0 l 0 l 1 0 0 o o o 0 1 0 o o 1 o l 1 o o 0 0 0 o l o o o 1 o 1 l 0 0 o 0 0 0 l 0 o 0 l 0 l l 0 0 o o o 0 l 0 0 0 l o l l o 0 o 0 o 0 1 o o o l 0 1 1 0 0 o 0 o 0 1 0 o 0 l 0 1 l 0 0 o o 0 o 第二章l d p c 码的编译码原理 9 ku = 矿，kn 圪= a ，使得任意边p e 的一个端点属于集合k ， 属于集合砭，则称图g 为二部图( b i p a i t i t e 伊印h ) 。 若k 中所有节点的度都相等，并且圪中所有节点的度也都相等， 则二部图，否则称为非规则二部图。 另一个端点 则称g 为规 定义2 4 ：g f ( 2 ) 上的l d p c 码的t a 咖e r