（通信与信息系统专业论文）低密度奇偶校验码的译码技术研究.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 码的几种主要泽码算法，包括软判决置信传播( b p ) 算法以及各 种加权比特翻转( w b f ) 算法。我们深入分析了w b f 算法中的校验式权重和l 变量节点可靠度 对译码结果的影响，并在此基础上对现有算法进行了修上e ，提出了两种改进的w b f 算法。 仿真结果表明，这两种改进算法能在少量增加计算复杂度的情况下，使译码性能得到明显 提升。本文还介绍了多元域l d p c 码的软判决译码算法，并在二元域比特翻转算法基础上， 提出了一种多元域l d p c 码的硬判决符号翻转算法。 文章最后研究了l d p c 码并彳? j j t l 权比特翻转( p w b f ) 算法的硬件实现。p w b f 算法不仅 在收敛速度上明显优于其它比特翻转算法，其译码性也能够逼近软判决b p 算法，冈此具 有很好的实际应用潜力。但目前还没有文献给出完整的p w b f 译码器设计方案。本文对 p w b f 算法的定点量化性能和译码器存储单元访问方式进行了研究，并在此基础上首次提 出了一种基丁部分并行结构的译码器设计方案。整个设计方案己用v e r i l o g 语言描述，并在 m o d e l s i m 平台上成功通过了功能仿真验证。 关键词：低密度奇偶校验码，比特翻转算法，多元域l d p c 码，并行加权比特翻转算法 东南人学坝i j 学位论文 a b s t r a c t t i t l e ：r e s e a r c ho i lt h ed e c o d i n go fl o w - d e n s i t yp a r i t y - - c h e c kc o d e s s o u t h e a s tu n i v e r s i t y s t u d e n tn a m e ：q i a nd a j u na d v i s o rn a m e ：z h a oc h u n m i n g l o wd e n s i t yp a r i t y c h e c k ( l d p c ) c o d e sw e r ef i r s td i s c o v e r e db yg a l l a g e ri nt h ee a r l y 19 6 0 sa n dr e c e n t l yh a v eb e e nr e d i s c o v e r e da n dg e n e r a l i z e d s t u d i e ss h o ws u c hc o d eh a sn e a r s h a n n o nl i m i tp e r f o r m a n c ew h e nd e c o d e du s i n ga ni t e r a t i v ep r o b a b i l i s t i ca l g o r i t h m i nt h i s t h e s i s ，w em a i n l yf o c u so nt h ed e c o d i n ga l g o r i t h m f o rl d p cc o d e sa n di t sh a r d w a r e i m p l e m e n t a t i o n i nt h i st h e s i s ，s e v e r a l d e c o d i n ga l g o r i t h m sf o r l d p cc o d e sa r es t u d i e d ，s u c ha s s o f t d e c i s i o nb 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 ma n dv a r i o u sw e i g h t e db i tf l i p p i n g ( w b f ) a l g o r i t h m s 。f o rw b fa l g o r i t h m s t h ec h e c k s u mw e i g h ta n dv a r i a b l e n o d er e l i a b i l i t y e x e r t i m p a c to nd e c o d i n gr e s u l t sa n di t h a sb e e nc a r e f u l l ya n a l y z e d b a s e do nt h i sa n a l y s i s ，t w o m o d i f i c a t i o ns c h e m e sf o rw b fa l g o r i t h m sa r ep r o p o s e d s i m u l a t i o nr e s u l t ss h o wt h a tb o t h m o d i f i c a t i o n sc a nb er e a l i z e dw i t has m a l li n c r e a s ei nc o m p l e x i t y , b u tl e a dt oa na p p e a l i n g i m p r o v e m e n ti ne r r o rp e r f o r m a n c e f u r t h e r m o r e ，t h es o f t - d e c i s i o nd e c o d i n ga l g o r i t h mf o rq a r y l d p cc o d e si si n t r o d u c e d ，a n dah a r d d e c i s i o ns y m b o lf l i p p i n ga l g o r i t h mf o rq a r yl d p cc o d e h a sb e e np r o p o s e da sw e l l ，b a s e do nt h ec o r r e s p o n d i n ga l g o r i t h mf o rb i n a r yc o d e f i n a l l y ，t h eh a r d w a r ei m p l e m e n t a t i o no fp a r a l l e lw e i g h t e db i tf l i p p i n g ( p w b f ) a l g o r i t h m i s i n v e s t i g a t e d t h ep w b fa l g o r i t h m ，w i t h ag o o dp o t e n t i a lf o rp r a c t i c a lu s e ，s h o w sa n a d v a n t a g ei nc o n v e r g e n c es p e e do v e ro t h e rw b fa l g o r i t h m s ，a sw e l la sas u b o p t i m a le r r o r p e r f o r m a n c et ob pd e c o d i n g h o w e v e r ，t h ed e t m l e dd e s i g nf o rp w b fd e c o d e ri sn o ty e tg i v e n t h ef i n i t ep r e c i s i o na n a l y s i sf o rp w b fa l g o r i t h ma n dt h es t u d yo fm e m o r y a c c e s ss c h e m eh a v e b e e ni n c l u d e di no u rw o r k m o r e o v e r ，t h eo r i g i n a ld e s i g nf o rp w b fd e c o d e ri np a r t i a l l yp a r a l l e l a r c h i t e c t u r ei sp r o p o s e d t h 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 a n dh a sb e e ns u c c e s s f u l l yt e s t i f i e dv a l i di nf u n c t i o n a ls i m u l a t i o nu n d e rm o d e l s i mp l a t f o r m 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 e s ，b i tf l i p p i n ga l g o r i t h m ，q a r yl d p cc o d e s ， p a r a l l e lw e i g h t e db i tf l i p p i n ga l g o r i t h m i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 日期： 第章绪论 第一章绪论 通信的目的是把对方不知道的讦| i 息i 叮靠地传送给对方。但在数宁通信系统中，信道存 在着种种噪声和j 二扰，使传送消息的可靠性减低。一种克服噪声和j f ：扰的有效方法就是使 用纠错编码，在传输序列中添加冗余的信息，利用它们进行检错和纠错。自s h a n n o n 创立 信息理论以来，如何构造逼近s h a n n o n 限的好码以及如何有效的译码一直足纠错码理论研 究巾的重要课题。同时纠错码的编解码技术在各种实际的数7 通信系统和计算机系统中都 起到了举足轻重的作用。伴随着世界范围内的信息科技革命，特别是通信技术，计算机理 论以及网络技术的互相融合，纠错编码技术止以前所未有的速度在发展和i 更新。 本章将综述纠错编码的发展现状，特别是近儿年在l d p c 码译码算法办而的最新进展。 最后将给出全文的内容安排。 1 1 论文的研究背景 在数字信号传输l l ，由j ：信道不理想以及加性噪声的影响，被传输的信丌码元波彤会 变坏，造成接收端错误判决。为了尽量减小数字通信巾信息码元的差错概率，一种有效的 方法就是采用信道编码，又称为差错控制编码。 信道编码实质是给信息码元增加冗余度，即增加一定数量的多余码冗( 称为监督码元或 校验码元) ，由信息码元和监督码元共同组成一个码字，两者问满足定的约束关系。如果 在传输过程中受到干扰，某位码元发生了变化，那么就破坏了它们之间的约束关系。接收 端通过检验约束关系是否成立，完成识别错误或者进一步判定错误位置并纠正错误，从而 提高通信的可靠性1 9 4 8 年，s h a n n o n 在信息论1 1 j 中提 bs h a n n o n 限的概念，即纠错编码 能够有效纠错所需的最小比特信噪比。该极限确定了纠错编码抗干扰能力的极限。但当时 s h a n n o n 并未提出如何构造编码达到该极限。所以寻找能够实际应用的逼近s h a n n o n 限的 编码方案和译码算法就成了后人奋斗的目标。在此后的研究中，为了达到这个目标，人们 提出了一系列著名的纠错编码方法。 线性分组码是发展最早的一类分组码。一个线性分组码码字由两部分构成，即信息码 元和监督码元。监督码元是根据一定规则由信息码元变换得到的，变换规则不同就构成不 同的分组码。如果监督位为信息位的线性组合，则称其为线性分组码。如常见的奇偶校验 码，汉明码都是线性分组码。作为分组码中一个重要的分支，循环码则是以代数中的群论、 东南人学硕十学位论文 域论等理论作为数学基础。它的检、纠错能力较强，编码和译码设备并不复杂，所以循环 码受到人们的高度重视，在前向纠错系统中得到了广泛应月j 。如r s 码、b c h 码都是著名 的循环码。 分组码的约束关系完全限定在各码组之内，而卷积码充分利用了各码组之l 、日j 的相关性， 所以能够得到很好的性能。但对卷积码的分析至今还缺乏像分组码那样有效的数学：l ：具， 往往要借助于计算机才能搜索到一些好码的参数。近些年发展起来的l 由4 格编码调制t c m 技术，则是以卷积码为基础，将信道编码和调制技术结合起来，改变了纠错编码与调制是 各自独立设计并实现的传统。 到了上世纪八十年代和九十年代初，纠错编码理论和技术取得丫很大的发展。法国的 c b e r r o u 等人在于1 9 9 3 年提出了一种全新的编码方案t u r b o 码【2 1 。t u r b o 码采用了m a p 迭代译码算法，性能可以趋近于s h a n n o n 限。 低密度校验( l d p c ) 码是g a l l a g e r 于1 9 6 2 年提出的一种编剧3 1 。在很长的一段时间单， l d p c 码并未受到人们的重视。受到t u r b o 码的启发，m a c k a y 等人对g a l l a g e r 提的 l d p c 码进行了重新研究1 4 1 1 5 1 ，并发现其具有接近香农限的性能。近的十年里来，l d p c 码 越来越受到人们的关注，成为纠错编码领域的一个研究热点。h 前与l d p c 码编解码技术 相关的研究已取得了长足的进步，已有的研究结果表明精心设计的非止则l d p c 码长码 1 6 】f 7 1 1 8 1 能逼近信道容量极限。而如何在有限长度和硬件可实现的条件f ，构造性能优越的 l d p c 码字及改进编解码算法已经逐步成为移动通信、卫星通信、深空通信等领域中一个 重要的研究方向。 1 2l d p c 码的最新研究进展 在近几年的研究中，l d p c 码的码字构造，译码算法和编、译码器硬件实现方面又自 很多新进展。 l d p c 码的码字构造不仅对译码算法的性能影响非常大，也很大程度上决定l d p c 码 编、译码器的硬件实现复杂度，所以必须精心设计。目前，在码字设计上已经有了些比 较成熟的方案，比如m a c k a y 构造的g a l l a g e r 码【5 】x i a o - y uh u 构造的p e g 码f g i t l 0 1 ，s l i n 设计的准循环( q c ，q u a s ic y c l i c ) l d p c 码1 l 【1 2 1 及有限几何域( f 1 3 lf i n i t eg e o m e t r y ) l d p c 码 1 3 1 。第二章会提到，l d p c 码中的短圈会直接影响迭代译码性能，而p e g 码的构造就是针 对这个问题提出的，其在减少短圈方面有不错的效果。q c l d p c 码和f g l d p c 码都是基 2 第一章绪论 于有限域构造的，这类码字的校验矩阵有很强的规律性，非常适合用j ：编、译码器的硬件 实现。 在译码算法方面，l d p c 码主要有软判决和硬判决两类译码算法。目前l d p c 码性能 最好的软判决算法是置信传播( b 只b e l i e fp r 叩a g a t i o n ) 迭代译码算法1 4 1 。l d p c 码还有。类基 于比特翻转( b f b i tf l i p p i n g ) 的硬判决算法f 1 4 】。这类算法泽码复杂度低，实现简单，译码速 度快，但其误比特率性能与软判决算法相比还有很大差距。为了提高比特翻转算法的性能， 人们又提出了一种加权比特翻转( w b ew e i g h t e db i tf l i p p i n g ) 算法 1 3 1 以及多种改进方案 i 1 6 1 1 7 1 1 8 1 【1 9 1 1 2 0 1 1 2 i i ，这类算法利用了各个变量节点卜接收信号的叮靠度信息，增加了翻转判 决的可靠性。如何利用l d p c 码中的信息改进翻转判决策略，是进一步改善这类算法性能 的一个研究方向。比特翻转算法的另外一个问题是，通常一次迭代中只有一个比特被翻转， 算法收敛速度较慢，为了实现高吞吐率的译码就必须采用并行的比特翻转。针对这。问题， 文献【2 2 1 提出了并行加权比特翻转( p w b f ，p a r a l l e lw e i g h t e db i tf l i p p i n g ) 算法。该算法不仅有 收敛速度上的优势，在性能上也与b p 算法筹距不大，具有i 箭在的应用价值。 近几年来，多元域( q a r y ) l d p c 码正成为一个研究热点。d a v e y 在论义中2 3 1 提出多元 域l d p c 码的性能在理论上可以更进步超过二元域l d p c 码。所谓多元域l d p c 码遗将 二元域l d p c 码转化到有限域g f ( q ) 。由于g f ( g ) 域上构造的l d p c 码l 叮以解决二元域 时增加列重量和产生短圈的矛盾，所以性能要u - - 元域的l d p c 码好，而且在越大的域上 构造l d p c 码，其性能可以得到越大的提高。尽管多元域l d p c 码忭能卓越，但是多元域 l d p c 码译码算法的高复杂度足影响其应用的一个主要问题。近几年针对这一问题，义有 不少新的研究成果。在2 0 0 3 年h o n g x i ns o n g 和l b a r n l a t 几乎同时提出了多元域l d p c 码 的快速译码算法2 4 1 1 2 5 1 。他们提出在译码时使用f f t 来计算，从而简化算法复杂度。本文将 针对多元域l d p c 码的译码算法做进步的研究。 尽管g a i l a g e r 早在1 9 6 2 年就提出了l d p c 码，但直到上世纪九十年代它才重新引起人 们的注意，其中一个重要原因是对于当时的技术条件来说，l d p c 码编、译码器的实现过 于复杂。近几年来，随着专用集成电路的设计技术不断突破，在l d p c 码硬件实现方面也 有大量研究成果涌现。在译码器设计上，译码速率和硬件资源消耗是两个重要的因素。不 同应用环境对译码器的译码速率和资源消耗有不同的要求，为了适应不同的情况，人们提 出了三种不同的硬件结构：全并行结构1 2 6 、串行结构i 2 7 1 和部分并行结构l 船i 。现在已经有不 少文献给出了完整的软判决及硬判决译码算法的硬件实现方案1 2 9 1 1 3 0 1 1 ”1 。 3 东南夫学硕十学位论文 1 3 论文的研究内容 本文的主要内容是研究了_ 元域l d p c 码的译码算法，多元域l d p c 码的译码算法， 以及l d p c 码p w b f 算法译码器的硬件实现。 第二章主要介绍了l d p c 码的几个基本概念，几种重要的l d p c 码码7 构造办法，以 及多元域代数的基本知识。 第三章重点探讨l d p c 码基于比特翻转的硬判决算法，分析比较了w b f 算法及其各 种改进方案的性能和复杂度。我们深入分析了w b f 算法r f i 校验式权霞及变量节点可靠度 对泽码结果的影响，并在此基础上对现有算法进礼：了修正，提出了两种的改进的w b f 算 法。仿真结果表明，这两种改进方案能在少量增加计算复杂度盼隋况f ，使译码性能得剑 明显提升。 第四章主要讨论了多元域l d p c 码的译码算法。我们分析了多元域l d p c 码的软判决 译码算法的性能和复杂度，并在二元域的比特翻转算法基础上，提出了种多元域l d p c 码的硬判决符号翻转算法。 第五章研究了l d p c 码p w b f 算法的硬件实现。我们对p w b f 算法的定点量化性能和 译码器存储单元访问方式进行了分析，并在此基础上提出了一套肇于部分并行结构的译码 器设计方案。全部设计方案已在m o d e l s i m 平台卜成功通过了功能仿真验证。 第六章是对论文工作的总结，概括了论文已取得的成果，同时对可以进。一步研究的工 作进行了探讨。 参考文献 1 1 c e s h a n n o n am a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n s 【j 】b e l ls y s tt e c hz1 9 4 8 ，v 0 1 2 7 ： 3 7 9 - 4 2 3 ，6 2 3 - 6 5 6 【2 】b e r r o uc ，g l a v i e u xa ，t h i t i m a j s h i m aen e a rs h a n n o nl i m i te r r o r - c o r r e c t i n gc o d i n ga n d d e c o d i n g ：t u r b o c o d e s 【c 】i np r o c e e d i n g s 1 9 9 3i e e ei n t e r n a t i o n a lc o n f e r e n c eo n c o m m u n i c a t i o n s ，g e n e v a , s w i t z e r l a n d ，1 9 9 3 ：1 0 6 4 - 1 0 7 0 【3 】g a l l a g e rrg l o w - d e n s i t yp a r i t y - c h e c kc o d e s 【j 1 i r et r a n s i n f o r m t h e o r y ，19 6 2 ， 8 ( 1 ) ：2 1 - 2 8 【4 】m a c k a ydjc ，n e a lrm n e a rs h a n n o nl i m i tp e r f o r m a n c eo fl o w - d e n s i t yp a r i t y c h e c k c o d e s 【j 】e l e c t r o n l e t t ，1 9 9 6 ，3 2 ( 1 8 ) ：1 6 4 5 - 1 6 4 6 【5 】m a c k a yd jc g o o de r r o r - c o r r e c t i n gc o d e sb a s e do nv e r ys p a r s em a t r i c e s 【j 】i e e et r a n s 4 第- 章绪论 i n f o r m t h e o r y , 19 9 9 ，4 5 ( 2 ) ：3 9 9 4 3l 【6 】l u b ym ，m i t z e n m a c h e rm ，s h o k r o i l a h im ，s p i e l m a nd i m p r o v e dl o wd e n s i t yp a r i t y c h e c k c o d e su s i n gi r r e g u l a rg r a p h s 【j 】i e e et r a n s i n f o r m t h e o r y ，2 0 0 1 ，4 7 ( 2 ) ：5 8 5 5 9 8 【7 】r i c h a r d s o ntj ，s h o k r o l l a h ima ，u r b a n k erl d e s i g no fc a p a c i t ya p p r o a c h i n gi r r e g u l a r l o w d e n s i t yp a r i t y - c h e c kc o d e s j 】i e e et r a n s i n f o r m t h e o r y ，2 0 01 ，4 7 ( 2 ) ：619 - 6 3 7 【8 】c h u n gsyo nt h ec o n s t r u c t i o no fs o m ec a p a c i t y - a p p r o a c h i n gc o d i n gs c h e m e s 【d 】p h d d i s s e t a t i o n ，m i t , c a m b r i d g e ，m a ，2 0 0 0 【9 】h ux i a o y u ，e e i e f i h e r i o u ，d m a r n o l d p r o g r e s s i v ee d g e - g r o w t ht a n n e rg r a p h s 【c 】 g l o b e c o m2 0 0 1 v 0 1 2 n o v 2 0 0 1 ：9 9 5 1 0 0 1 【1 0 】h ux y e l e f i h e r i o ue ，a r n o l ddm r e g u l a ra n di r r e g u l a rp r o g r e s s i v ee d g e - g r o w t ht a n n e r g r a p h s 【j 】i e e et r a n s i n f o r m t h e o r y , 2 0 0 5 ，5 2 ( 1 ) ：3 8 6 3 9 8 【l l 】ll a n ，lz e n g ，y yt a i ，lc h e n ，sl i n ，e ta 1 c o n s t r u c t i o no f q u a s i - c y c l i cl d p cc o d e sf o r a w g na n db i n a r ye r a s u r ec h a n n e l saf i n i t ef i e l da p p r o a c h j i e e et r a n s i n f o r m t h e o r y , 2 0 0 7 5 3 ( 7 ) ：2 4 2 9 - 2 4 5 8 【12 】t a i ，y ，y l a n ，l z e n g ，l l i n ，e ta i a l g e b r a i cc o n s t r u c t i o no fq u a s i - c y c l i cl d p cc o d e s f o r t h ea w g na n de r a s u r ec h a n n e l s 【j 】。i e e et r a n s c o m m u n ，2 0 0 6 ，5 4 ( 10 ) ：i7 6 5 - 17 7 4 【13 k o uyl i ns ，f o s s o r i e rm l o wd e n s i t yp a r i t yc h e c kc o d e sb a s e do nf i n i t eg e o m e t r i e s ：a r e d i s c o v e r ya n dm o r e 【j 】i e e et r a n s i n f o r m t h e o r y ，2 0 0 1 ，4 7 ( 1 1 ) ：2 7 11 - 2 7 3 6 1 4 】s i p s e rm ，s p i e l m a nda e x p a n d e rc o d e s 【j 】i e e et r a n s i n f o r m t h e o r y ，l9 9 6 4 2 ( 11 ) ：1 7 l o - 1 7 2 2 【l5 】z h a n gj ，f o s s o r i e r , mpc am o d i f i e dw e i g h t e db i t f l i p p i n gd e c o d i n go fl o w - d e n s i t y p a r i t y c h e c kc o d e s 【j 】i e e ec o m m u n l e t t ，2 0 0 4 ，8 ( 3 ) ：16 5 16 7 【1 6 】g u of h a n z ol r e l i a b i l i t yr a t i ob a s e dw e i g h t e db i t f l i p p i n gd e c o d i n gf o rl o w d e n s i t y p a r i t y - c h e c kc o d e s j 1 e l e c t r o n l e t t ，2 0 0 4 ，4 0 ( 2 1 ) ：1 3 5 6 1 3 5 8 【1 7 l e ec h ，w o l fw i m p l e m e n t a t i o n - e f f i c i e n tr e l i a b i l i t yr a t i ob a s e dw e i g h t e db i t f l i p p i n g d e c o d i n gf o rl d p cc o d e s 【j 】e l e c t r o n l e t t ，2 0 0 5 ，41 ( 13 ) ：7 5 5 7 5 7 【18 】l i uz ，p a d o sda ad e c o d i n ga l g o r i t h mf o rf i n i t e g e o m e t r i cl d p cc o d e s 【j 】i e e et r a n s c o m m u n 2 0 0 5 ，5 3 ( 3 ) ：415 - 4 21 【1 9 】s h a hm ，z h a oc ，j i a n gm i m p r o v e dw e i g h t e db i t - f l i p p i n ga l g o r i t h mf o rd e c o d i n gl d p c c o d e s 【j 】1 e ep r o c c o m m u n ，2 0 0 5 ，1 5 2 ( 6 ) ：9 1 9 - 9 2 2 【2 0 】j i a n gm ，z h a oc ，s h iz c h e ny a ni m p r o v e m e n to nt h em o d i f i e dw e i g h t e db i tf l i p p i n g a l g o r i t h mf o rl d p cc o d e s 【j 】1 e e ec o m m u n l e t t ，2 0 0 5 ，9 ( 9 ) ：8 1 4 8 1 6 【2 1 1c h a r tam ，k s c h i s c h a n gf &a s i m p l et a b o o - b a s e ds o f t - d e c i s i o nd e c o d i n ga l g o r i t h mf o r e x p a n d e rc o d e s 田i e e ec o m m u n l e t t ，1 9 9 8 ，2 ( 7 ) ：1 8 3 1 8 5 2 2 1w ux i a o f u , z h a oc m , y o ux h p a r a l l e lw e i g h t e db i t f l i p p i n gd e c o d i n g 【j 】i e e e c o m m u n l e t t e r s , 2 0 0 7 ，l1 ( 8 ) ：6 7 1 - 6 7 3 【2 3 m c d a v e ya n dd j c m a c k a y l o wd e n s i t yp a r i t y - c h e c kc o d e so v e rg f ( q ) 阴i e e e i e e e c o m m u r t l e t t e r s ，v 0 1 2 ，p p 1 6 5 - 1 6 7 ，j u n e1 9 9 8 5 东南人学硕十学位论文 【2 4 h o n g x i ns o n ga n dj r c r u z r e d u c e d - c o m p l e x i t yd e c o d i n go fq - a r yl d p cc o d e sf o r m a g n e t i cr e c o r d i n g 【j 】i e e et r a n s a c t i o n so nm a g n e t i c sv 0 1 3 9 , n o 2m a r c h2 0 0 3 【2 5 】l b a m a u l ta n dd d e c l e r c q f a s td e c o d i n ga l g o r i t h mf o rl d p co v e rg f ( q ) 【c 】i t w 2 0 3 , p a r i s ，f r a n c e m a r c h 31 - a p r i l42 0 0 3 【2 6 】b l a n k s b ya ，h o w l a n dc a6 9 0 - m wl - g b p s1 0 2 4 一br a t e - i 2l o w - d e n s i t yp a r i t y c h e c kc o d e d e c o d e r 【j 】i e e ej o u r n a lo f s o l i ds t a t ec i r c u i t s ，2 0 0 2 ，3 7 ( 3 ) ：4 0 禾41 2 【2 7 】b l e v i n e ，r t a y l o ra n dh s c h m h i m p l e m e n t a t i o no fn e a rs h a n n o nl i m i te r r o r - c o r r e c tc o d e s u s i n gr e c o n f i g u r a b l eh a r d w a r e 【c 】i e e es y r u p o n ，( 1 c ml o sa l a m i t o s ，a p r 2 0 0 0 ：217 - 2 2 6 2 8 】s h i m i z uk ，l s h i k a w at t o g a w an p a r t i a l l y - p a r a l l e l l d p cd e c o d e r a c h i e v i n g h i g h - e f f i c i e n c ym e s s a g e - p a s s i n gs c h e d u l e 【j 】i e l c et r a n so nf u n d a m e n t a l so f e l e c t r o n i c s , 2 0 0 6 ，e 8 9 - a ( 4 ) ：9 6 9 9 7 8 【2 9 】z h a n gt ，p a r h ikk a5 4m b p s ( 3 ，6 ) 一r e g u l a rf p g al d p cd e c o d e r 【c 】i e e ep r o c o f s m s s a nd i e g o , c a ，u s a ，o c t 2 0 0 2 ：1 2 7 - 1 3 2 【3 0 】z a r u b i c a , r w i l s o n ，s q ，h a l l ，e m u l t i g b p sf p g a b a s e dl o wd e n s i t yp a r i t yc h e c k ( l d p c ) d e c o d e rd e s i g n 【c 】g l o b a lt e l e c o m m u n i c a t i o n sc o n f e r e n c e ，n o v 2 0 0 7 ：5 4 8 5 5 2 【3l 】c u i ，z h i q i a n gw a n g ，z h o n g f e n gs t u d i e so n p r a c t i c a ll o wc o m p l e x i t yd e c o d i n go f l o w d e n s i t yp a r i t y 7 - c h e c kc o d e s 【c 】s i g n a lp r o c e s s i n gs y s t e m s , 2 0 0 7i e e ew o r k s h o po c t 2 0 0 7 ：2 1 6 。2 2 l 6 第+ ：章l d p c 码的基本介绍 第二章l d p c 码的基本介绍 g a l l a g e r 提出的低密度奇偶校验( l d p c ) 码是- - 种线忭分组码，线件分组码总是通过一 个生成矩阵g 将信息序列映射成发送序列，也就是码字序列。对于生成矩阵g ，完全等效 的存在一个奇偶校验矩阵日，所有的码宁序列构成了的零窄问，h w 7 = 0 。l d p c 码的特点完全取决予它的奇偶校验矩阵日。该矩阵的结构微大程度1 ：影响了l d p c 码的译 码性能。本章将在简要介绍l d p c 码的几个荩本概念后，讨论几类重要的码7 构造方法。 二元域的l d p c 码可以推广成多元域上的l d p c 码。本章还将简述多元域代数的基本知识， 这是多元域l d p c 码的数学基础。 2 1l d p c 码的基本概念 低密度奇偶校验( l d p c ) 码足一种线性分组码。和一般的线件分组码的编码过程一样， l d p c 码足将长度为k 的信息序列经过个行列为( k ，n ) 的生成矩阼g 处理后得到长度 为的码字形。生成矩阵g 对应着一个行列为( a 彳，) 的校验矩阵，_ j e i i in m = k 。 经过生成矩阵g 产生的所有码字形，满足m 矿7 = 0 。这是进行码字校验的重要依据。 之所以说这种码低密度，是冈为相对于校验矩阵行与列的长度( m ，) ，校验矩阵的 最大行列重量( 以，z ，) 非常小。矩阵的非零元只占了很小一部分，是一个非常稀疏的矩阵。 l d p c 码校验矩阵日的构造很大程度上影响r 迭代译码性能的好坏。我们常常使用二分图 ( t a n n e r 图) 来对校验矩阵h 进行研究i i j 。t a n n e r 图是根据l d p c 码的码字和校验式的关系 建立的。t a n n e r 图中有阿类节点，变量节点和校验节点。每个变量节点对应码宁形中的一 个码元，每个校验节点对应着一个校验方程。我们分别用节点y 和节点c 来表示变量节点 和校验节点的集合。如果某个码元参与了某个校验方程，则这个码元对应的变量：肖点和这 个校验方程对应的校验节点之间就有一条边相连。一个行列为( m ， r ) 的校验矩阵日有m 个校验方程，处理的码字长为，所对应的t a n n e r 图有m 个校验节点和个变量：宵点。 图2 1 是一个( m ，) = ( 4 ，8 ) 的线性分组码的校验矩阵以及该矩阵对应的t a n n e r 图。 7 东南人学硕士学位论文 图2 1 校验矩阵及其对应的t a n n e r 图 图2 1 的二分图结构中，四条粗体连线构成了，个有向的闭合纠：路，由嵋起始，最后 返回，长度为4 。在一个l d p c 码的编码二分图中，会存在许多这样的闭合环路，其中 最短的闭合环路的长度，称之为最小豳长( g i r t h ) ，上例的二分图中，g i r t h 即为4 。 l d p c 码二分图中的最小圈长和闭合环路的分布，会直接影响到l d p c 码迭代译码的 性能。仿真结果表明，如果二分图的g i r t h 为4 ，则l d p c 码的误码率性能将会很差。这种 现象的原阗是，l d p c 码迭代译码算法主要是b p 迭代译码，变量节点和校验节点根据 t a n n e r 图的连接情况互相传递信息。当t a n n e r 图中存在短圈时