（电路与系统专业论文）准循环ldpc码的构造及其在图案介质存储中的应用研究.pdf

准循环l d p c 码的构造及其在图案介质存储中的应 用研究 专业：电路与系统 硕士生：张伟波 指导教师：刘星成副教授 摘要 低密度奇偶校验( l o wd e n s i t yp a r i t y c h e c k , l d p c ) 码是一类由稀疏校验矩阵 定义的线性分组码，它具有优异的逼近s h a n n o n 限的性能。经过十多年来众多研 究人员孜孜不倦的探求，l d p c 码的研究硕果累累，目前l d p c 码已经成为第四代 移动通信( 4 g ) 的关键技术之一。 随机构造方法构造的l d p c 码编码需要占用大量的存储空间，计算复杂度高， 准循环l d p c 码则能很好地解决这一问题。但是，准循环l d p c 码的性能通常不如 随机构造方法构造的l d p c 码，因此如何提高准循环l d p c 码的性能具有重要的研 究意义和实用价值。 本文提出一种基于p r o g e r s s i v ee d g eg r o w t h ( p e g ) 算法的准循环l d p c 码的构 造方法，整个算法可以分为4 个步骤：第1 步和第2 步通过计算机搜索的办法来避 免短环，在环不可避免的时候，第3 步和第4 步则通过增加环的外信息及节点信息 的可靠度等方法来避免不可靠信息在环内传播。在此算法基础上，本文进一步构 造性能优良的多进制准循环l d p c 码。文中分别对不同的码长和码率的码字进行 仿真，结果表明，这种方法构造的l d p c 码的性能可以与随机方法构造的l d p c 码相媲美，甚至超过后者。 本文所做的另外项工作是在已有的研究的基础上，进一步探讨l d p c 码在 图案介质存储的“单磁头多磁岛 ( m u l t i p l ei s l a n d sp e rr e a dh e a d ) 模型中的应用。 中山大学硕士学位论文 文中针对“单磁头3 磁岛 模型，探讨了该信道模型利用二进锘s j l d p c 码作为纠错 码的可行性。同时，本文分析了高码率l d p c 码不能直接应用于此信道模型的原 因。最后，文中将之前提出的基于p e g 算法构造的准循环l d p c 码应用到该信道 模型中，并仿真了磁头响应矩阵为飓l 时的误码性能。实验结果表明，这种方法 所构造的l d p c 码能有效的改善该模型的误码性能。 关键词：多进带j j l d p c 码，准循环l d p c 的构造，p e g 算法，“单磁头多磁岛 模 型 i i s t u d yo nc o n s t r u c t i o no fq u s i c - c y c l i cl d p c c o d e s a n da p p l i c a t i o n so np a t t e r n e dm e d i as t o r a g e m a j o r ： n a m e ： c i r c u i t sa n ds y s t e m s w e i b oz h a n g s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rx i n g c h e n gl i u a b s t r a c t 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 sa r eac l a s so fl i n e a rb l o c kc o d e s d e f i n e di nt e r m so f s p a r s ep a r i t yc h e c km a t r i c e s ，w h i c hc a na p p r o a c hs h a n n o nl i m i t a f t e rt e ny e a r so fc o n t i n u o u se f f o r t s ，t h el a r g en u m b e r so fa c h i e v e m e n t si nt h e r e s e a r c ho nl d p cc o d e sa r eo b t a i n e d l d p cc o d e sh a v eb e c o m eo n eo ft h ek e y t e c h n o l o g i e si n4 gm o b i l ec o m m u n i c a t i o n s l d p cc o d e sc o n s t r u c t e db yr a n d o mc o n s t r u c t i o nm e t h o d sr e q u i r eal a r g e a m o u n to fm e m o r yt os t o r e p a r i t y c h e c km a t r i c e s ，a n d m a i n t a i nah i 曲 c o m p u t a t i o n a lc o m p l e x i t yi nt h ec a l c u l a t i o n t h eq u a s i c y c l i cl d p c ( q c l d p c ) c o d e sc a na l l e v i a t et h e s ep r o b l e m s h o w e v e r ，t h ee r r o r - c o r r e c t i o np e r f o r m a n c eo ft h e q c - l d p cc o d e si sn o tc o m p a r a b l et ot h a to ft h er a n d o m l yc o n s t r u c t e do n e s f o rt h i s r e a s o n ，i ti sn e c e s s a r yt oe x p l o r eh o wt oi m p r o v et h ee r r o r - c o r r e c t i o np e r f o r m a n c eo f t h eq c - l d p cc o d e s i nt h i st h e s i sa ne f f i c i e n ta l g o r i t h mf o rc o n s t r u c t i n gq c l d p cc o d e sb a s e do n p r o g r e s s i v ee d g eg r o w t h ( p e g ) a l g o r i t h mi sp r o p o s e d t h i sa l g o r i t h mc a nb e d e v i d e di n t o4s t e p s ：s t e p1a n d2a t t e m p tt oa v o i ds h o r tc y c l e sb yc o m p u t e r s e a r c h i n g ；b yi n s c r e s i n gt h ee x t r i n s i cm e s s a g ed e g r e e ( e m d ) a n dr e d u c i n g u n r e a l i a b l ef a c t o r , u n r e l i a b l ei n f o r m a t i o nt r a n s f e r r i n gi st r i e dt ob ea v o i d e di ns t e p3 a n d4w h e nc y c l e sa r ei n e v i t a b l e b a s e do nt h ep r o p o s e da l g o r i t h m ，a na l g o r i t h mf o r i i i 中山大学硕士学位论文 c o n s t r u c t i n gn o n b i n a r yq c l d p cc o d e s 、 r i t l lg o o dp e r f o r m a n c ei sp r o p o s e d i nt h i s p a p e r , w ec a r r yo u tt h es i m u l a t i o nw i t ht h ec o d ew o r d so fd i s t i n c tc o d el e n g t ha n d c o d er a t e t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep e r f o r m a n c eo ft h ec o d ew o r d s c o n s t r u c t e d 谢t l lt h ep r o p o s e da l g o r i t h mi sc o m p a r a b l et o ，a n de v e nb e r e rt h a nt h a t o ft h er a n d o m l yc o n s t r u c t e do n e s m a k i n gaf u r t h e ra n a l y s i so nt h ea p p l i c a t i o no fl d p cc o d e si nt h ep a t t e r n e d m e d i aw i t hm u l t i p l ei s l a n d sp e rr e a dh e a db a s e do nt h ep r e v i o u sr e s e a r c hi st h eo t h e r w o r ko ft h i sa r t i c l e f o rt h e “3i s l a n d sp e rr e a dh e a d ”m o d e l f e a s i b i l i t ya n a l y s i so n u s i n gb i n a r yl d p cc o d e sa se r r o rc o r r e c t i n gc o d ei sp e r f o r m e d b e s i d e s ，t h er e a s o n t h a tt h el d p cc o d e so fh i g hc o d er a t ec a nn o tb ee m p l o y e di n t h i sc h a n n e lm o d e l d i r e c t l yi sd e s c r i b e di nd e t a i l a tl a s t ，t h eq c l d p cc o d e sw ec o n s t r u c t e da r e a p p l i e di n t h i sc h a n n e lm o d e l ，a n dt h es i m u l a t i o ni sc a r r i e do u tu n d e rt h eh e a d r e s p o n s em a t r i x - 3 , t h es i m u l a t i o nr e s u l t ss h o w t h a tt h ep r o p o s e dl d p cc o d e sc a n i m p r o v et h ee r r o r - c o r r e c t i o np e r f o r m a n c eo ft h i sc h a n n e lm o d e l k e yw o r d s ：n o n b i n a r yl d p cc o d e s ，c o n s t r u c t i o no fq u s i c c y c l i c ( q c ) l d p c ， p e ga l g o r i t h m ，“m u l t i p l ei s l a n d sp e rr e a dh e a d m o d e l i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行 研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其 它个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由 本人承担。 学位论文作者签名： 日期：】_ o o m 月7 e l 使用授权声明 本人完全了解t ，山人学有关保留、使用学位论文的规定，h p ：学校仃权保留 学位论文并向幽家主管部门或其指定机构送交论文的电了版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名： 瓣波 导师签名： 卅易氐l n 同期：z o o 年6 月7 f = j i - 其, j j ：2 惭石月7 r 第1 章绪论 2 0 0 9 年国内3 g 牌照正式发放，宣布我国正式进入第三代移动通信时代。 一方面，国内3 g 产业正在轰轰烈烈地发展，另一方面，国内外的研究人员也 逐渐把目光投向了下一代移动通信系统。而l d p c 码作为4 g 通信系统编译码 方案强有力的竞争者，自然就成为了研究的焦点。本章首先介绍了信道编码发 展史，接着介绍了l d p c 码的研究现状，最后阐述了本文的研究意义以及创新 点。 1 1研究背景及现状 1 1 1 信道编码发展 随着社会的发展，人们对通信的需求越来越迫切，对通信质量的要求也越来 越高。近3 0 年来，移动通信产业迅猛发展，已广泛深入到国民生产的各个部门和 人民的生活当中。目前我国已经进入第三代移动通信时代，可以预计，今后对移 动通信的需求和对通信质量的要求会进一步提高。 在通信系统中，为了在已知信噪比的条件下达到一定的误比特率指标，除了 合理设计基带信号，选择合适的调制解调方式，采用均衡技术等等，利用信道编 码技术，即差错控制编码技术也是一种重要手段。信道编码的基本思想是在要发 送的信息中加入一些校验码元，并在两者之间建立特定的校验关系，一旦传输过 程中出现差错，则这种校验关系将受到破坏，从而可以发现错误，乃至纠正错误。 香农在有噪信道编码定理【1 】指出只要信息传输速率小于信道容量，就存在一类 编码，使信息传输的错误概率可以任意小，在满足以下的三个条件的前提下，在 有噪信道中可以实现无差错的传输：采用随机的编码方式；码长趋于无穷大；采 用最大似然译码。该定理指出了最佳的编码方案所能达到的性能极限，但是对于 如何才能实现最佳编码，香农的论文中并没有给出具体的实现方案。 自信道编码定理提出至今，无数科学家和研究人员通过不懈的努力，提出了 中山大学硕士学位论文 许多信道编码方案，其获得的编码增益也逐步逼近香农所证明的性能极限。 19 5 0 年，h a m m i n g 等人提出了能纠正单个错误的h a m m i n g 码【2 】。不久之后 的1 9 5 5 年e l i a s 等人提出了卷积码 3 ，它具有动态的t r e l l i s 结构，但是译码复杂度 较高。1 9 6 0 年，b o s e $ 1 r a y c h a u d h u r i 提出了纠正多个随机错误的循环码一b c h 码【4 】，1 9 6 5 年b e r l e k a m p 等人提出利用迭代算法译b c h 码 5 】，从而大大加快了译 码速度，使b c h 码迅速走向实用。随后r e e d 和s o l o m o n 用数论方法实现- j r s 码 6 】， 它实际是多进制的b c h 码，r s 码后来在磁信道和播放器标准等场合应用广泛【7 】。 1 9 6 5 年，f o m e y 提出了级联码 8 】，此后人们都采用级联的方式来构造好码，常用 的有以r s 码为外码、卷积码为内码的级联码。然而，以上所提出的各种码字均 与香农的理论极限差距较大。1 9 9 3 年，b e r r o u 等人提出了并行级联码t u r b o 码【9 】， 获得了接近香农限的优异性能。从此以后，t u r b o 码得到了广泛的关注和发展， 并对当今的编码理论和研究方法产生了深远的影响，信道编码学也随之进入了一 个新的阶段。t u r b o 码的提出为获得接近香农限的编码方式提供了一个全新的思 维角度，l d p c 码【1 0 】也是在t u r b o 码的影响下被重新发现的。 1 1 2l d p c 码的国内外研究现状 l d p c 码是1 9 6 2 年g a l l a g e r 1 0 在其博士论文中提出的，但由于当时的硬件实 现能力有限，无法达至i j l d p c 码大存储量和高计算复杂度的要求，因而未能获得 广泛的重视。直至u 1 9 9 6 年，在m a c k a y 等人【1 1 的研究的推动下，l d p c 码才重新 进入了研究人员的视线。经过十多年来的努力，l d p c 码尤其是二进制l d p c 码的 研究取得了丰硕的成果。 l u b y 等人 1 2 】提出了不规则的l d p c 码，使l d p c 码的概念得到了推广，指出 不规贝j j l d p c 码性能更加优异，这是l d p c 码发展过程中跨出的非常重要一步，而 进一步研究表明，不规贝t j l d p c 码的理论门限值在a w g n 信道下距离香农限只有 0 0 0 4 5 d b 1 3 。在码构造方面，h u 等人【1 4 】【1 5 】 1 6 】提出的p r o g r e s s i v ee d g eg r o w t h ( p e g ) 算法利用计算机搜索的办法，获得了性能优异的l d p c 码，而l i n 等人【1 7 】 提出的代数方法构造的l d p c 码和k o u 等人【1 8 】提出的基于有限几何构造的l d p c 码则克服了随机构造方法不利于硬件实现的缺点。在理论研究方面，则出现了密 度进化算法( d e n s i t ye v o l u t i o n ) 19 和e x t r i n s i ci n f o r m a t i o nt r a n s f e r ( e x i t ) 1 羽 2 0 】 2 第1 章绪论 优化设计方法。这两种方法通过分析l d p c 码的渐近性能，为l d p c 码的优化设计 与分析提供了新的方法和理论依据。 与二进$ i j l d p c 码相比，多进制l d p c 码具有更优异的性能 2 1 1 。已有的研究 表明，具有相同参数的多进$ i j l d p c 码l t - - 进$ i j l d p c 码具有更强的纠错能力；多 进带t j l d p c 码由于可以将多个突发比特错误合并成较少的符号错误，因而具有更 强的抗突发错误能力；多进$ 1 l d p c 码是基于高阶有限域的，因此适合与高阶调 制或者多天线系统结合，从而提高信息传输速率和频谱利用率。多进制l d p c 码 的构造大多通过随机的方法构造，因此编码复杂度高，不利于硬件实现，而且多 进l j l d p c 的译码算法和多进制的阶数有密切的关系，因此现有译码算法的译码 复杂度比二进制高得多。这些因素大大阻碍了多进s t j l d p c 码的实用化进程。 近年来对多进制l d p c 码的研究主要集中在码的构造、编码的实现、译码算 法及其改进和在实际系统中的应用等几个方面。 多进$ 1 j l d p c 码的构造是一个研究热点。d a v e y 和m a c k a y 等人于1 9 9 8 年将 l d p c 码由二元域推广到多元域上【2 l 】。该方法首先构造出二进铝i j l d p c 校验矩 阵，然后将矩阵中的“1 随机地用o f ( q ) 域中的非零元素代替。结果表明，多进 制的l d p c 码具有优于二进f l ；i j l d p c 码的纠错性能。该方法简单方便，但性能上不 是最优的。p o u l l i a t 和f o s s o r i e r 等人提出了用二进制映像的方式来构造多元规则的 变量节点度数为2 的具有低误码平底的l d p c 码 2 2 1 。l i n 等人则提出了基于有限 域构造多进制准循环l d p c ( q c - l d p c ) 码的方法 1 7 1 1 2 3 1 1 2 4 。这种用代数方法构 造的多元l d p c 码具有较低的误码平底，且其编码增益超过采用代数译码算法下 相同码长和码率的r s 码的编码增益。 在译码方面，由于多进s m l d p c 码的译码复杂度大大高于二进制l d p c 码，因 此降低译码复杂度成为研究人员主要的努力方向。针对d a v e y 和m a c k a y 最初提出 的概率域的译码算法，r i c h a r d s o n 和u r b a n k e 提出了一种快速译码算法，利用傅立 叶变换来降低复杂度，这种方法在不降低译码性能的情况下可明显减少计算的复 杂度 2 5 1 。w y m e e r s c h ，s t e e n d a m 和m o e n e c l a e y 提出的对数域的和积译码算法在 计算复杂度和应用上都比概率域算法更具有优势【2 6 【2 7 】。b a m a u l t ，d e c l e r c q 和 f o s s o r i e r 等人提出的基于q 元域上的快速傅里叶变换的和积译码算法( f f t - q s p a ) 则进一步降低了运算复杂度 2 8 】 2 9 】。v o i c i l a ，d e c l e r c q 和v e r d i e r 等人提出的e m s 中山大学硕士学位论文 译码算法具有低复杂度，低存储量要求的特点，适于硬件实现 3 0 1 。 1 2论文的研究意义及创新点 l d p c 码性能优异，具有广阔的应用前景。t u r b o 码是第三代移动通信系统的 信道编码方案，l d p c 码在许多场合下性能优于t u r b o 码。与t u r b o 码相比，l d p c 码具有较低的误码平底 3 1 】，同时译码复杂度低，可实现完全的并行操作，吞吐 量大，具有极高的应用潜力。目前，l d p c 码已经成为w i m a x 3 2 ，第二代卫星 数字视频广播( d v b s 2 ) 【3 3 和数字电视广播服务( d t m b ) 【3 4 的编码标准之一而 得到广泛应用。将l d p c 编译码加入到o f d m m i m o 系统当中，能大大提高系统 的性能 3 5 】，因此l d p c 码极有可能成为4 g 通信中的编码标准之一。此外，可以 预计l d p c 码在超高速局域网，光通信，量子保密通信，深空通信和硬盘驱动( h d d l 信号处理电路等领域也将得到广泛应用。 已有的研究表明，多进制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 码是基于高 阶有限域的，因此适合与高阶调制或者多天线系统结合，从而提高信息传输速率 和频谱利用率，更适合高速率传输系统。因此，多进常u l d p c 码在下一代通信系 统中必将发挥重要作用。 本文主要做两个方面的工作，一方面将l d p c 码的随机构造方法的思想融入 到准循环l d p c 码的构造当中，构造兼有两者优点的二进锋j l j l d p c 码，并在此基础 上构造多进制准循环l d p c 码；另一方面是在本实验室研究的基础上，进一步研 究l d p c 码在图案介质存储的“单磁头多磁岛的模型中的应用。 随机构造方法构造的l d p c 码需要占用大量的存储空间，不利于硬件实现， 而一般方法构造的具有准循环结构的l d p c 码硬件实现简单，但是其性能往往比 不上随机构造方法构造的l d p c 码。本文将一种经典的随机构造方法- p e g 算 法的思想融入到准循环l d p c 码的构造当中，在构造过程中力图避免产生短环， 并在形成的环中尽可能地增加外信息，从而获得具有优异性能的二进制准循环 l d p c 码，最后在此基础上构造准循环多进带i j l d p c 码。仿真结果表明，该方法能 4 第1 章绪论 够明显地改善准循环l d p c 码的误码性能。 图案介质存储是一种可将硬盘记录密度大大提高的候选技术 3 6 】。针对这一 技术，k a r a k u l a k 和s i e g e l 等人提出了一种新的读信道模型一“单磁头多磁岛模 型 3 7 】，然而，由于该模型在传输过程中存在不可识别的符号，使得对于这一模 型仿真得出的误符号率( s y m b o le r r o rr a t e ，s e r ) 的性能却不能很好地满足实际应 用中的需求。基于这一情况，本实验室提出利用l d p c 码作为纠错码，同时提出 用b c j r 算法与l d p c 码进行联合迭代的编译码方案，从而大大改善在该信道条件 下的误码性能 3 8 】。本文在之前已有的工作的基础上，分析了二进相j l d p c 码对 此信道的适用性，研究高码率情况下利用l d p c 码作为纠错码的可行性，并就提 高编码增益和传输速率进行了探讨。 本文的创新点在于把随机构造方法构造l d p c 码的思想融入到准循环l d p c 码的构造当中，并把所这种算法构造的l d p c 码应用到图案介质存储的应用当中， 获得了良好的性能。 1 3论文的课题来源及项目资助 国家自然科学基金项目( t h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no fc h i n a u n d e rg r a n t ，n o 6 0 6 7 3 0 8 6 ，6 0 9 7 0 0 41 ) 。 1 4论文的结构安排 第l 章绪论，首先介绍了在现代通信系统中进行信道编码的必要性和发展过 程，然后介绍了l d p c 码的国内外研究现状，最后指出了本论文的研 究意义以及创新点。 第2 章介绍了l d p c 码的一些基本知识，首先介绍了二进制l d p c 码的日矩阵 表示、t a n n e r 图表示以及编码方法。然后介绍了二进f l ；i j l d p c 码的p e g 构造方法和准循环l d p c 码的结构及构造算法，最后介绍了二进制 l d p c 码和多进f 1 i j l d p c 码的译码算法。 第3 章提出了基于p e g 算法的准循环l d p c 码的构造。首先介绍了所提出的 算法的基本思路，并在该算法的基础上构造准循环多进f 1 l j l d p c 码， 最后给出了仿真实验结果。 5 中山大学硕士学位论文 第4 章针对k a r a k u l a k 和s i e g e l 等人提出的的“单磁头多磁岛 模型，在已有 研究的基础上分析了该信道模型利用二进制l d p c 码作为纠错码的可 行性以及l d p c 码的码率在该模型中对误码性能的影响，同时将之前 提出的基于p e g 算法构造的准循环l d p c 码应用到该信道模型中，并 给出了实验结果。 第5 章对研究成果进行总结，提出了需要进一步进行研究的问题。 6 第2 章l d p c 码的基本原理 本章主要介绍l d p c 码的基本概念，包括二进制和多进制l d p c 码的表示 方法、码构造及译码算法等。其中，在译码算法方面主要介绍了二进制l d p c 码的和积译码算法，在码构造方面主要介绍了p e g 算法以及两种基于p e g 算 法的准循环l d p c 码的构造算法。在多进制l d p c 码译码算法方面则主要介绍 了两种译码算法：置信传播迭代译码算法和快速译码算法。 2 1二进制l d p c 码的结构及构造 2 1 1 二进制l d p c 码的日矩阵表示及编码 低密度奇偶校验( l o wd e n s i t yp a r i t yc h e c k ，l d p c ) 码是一类具有逼近香农 限的优异性能的线性分组码。所谓线性分组码，就是把每k 位信息位作为一个 分组u = ( “o ，u l ，u k - 1 ) ，然后按照一定的编码规则映射为刀( 通常t l 助位码字 c = ( c o ，c l ，c n 1 ) ，其中，信息组和码字的各分量取自某个有限域g f ( q ) ，我们 把这样的码字称为，幼线性分组码。如果q = 2 ，那么这就是二进制l d p c 码， 如果矿2 ，这就是多进制l d p c 码了。 一般而言，l d p c 码是通过它的校验矩阵来描述的。l d p c 码的校验矩阵日 具有稀疏性，即校验矩阵日中的非0 元素的个数远远小于0 元素的个数，正是 由于这种校验矩阵的稀疏性，大大降低了l d p c 的硬件要求，从而走向实用。 对于维数为m x n 的校验矩阵日，它的m 行对应着m 个校验方程，而n 列 对应着一个码字的胛位，在校验矩阵日是满秩的情况下，k = 抑m ，在这里，k 即分组信息位长度，此时码率胆k n = ( 刀m ) n = 1 - ( m n ) ；如果校验矩阵日不是 满秩的，那么日矩阵的秩小于m ，则m t l k ，此时码率r l 一( m 励) 。 我们把l d p c 码校验矩阵日中每一行的非零元素的个数称为行重，每一列 的非零元素的个数称为列重。如果校验矩阵日中各行非零元素的个数和各列非 零元素的个数均相等，我们把具有这种性质的l d p c 码称为规则l d p c 码，否 则为非规则l d p c 码。 7 中山人学硕士学位论文 对于一个由校验矩阵日定义的l d p c 码，为了对信息组进行编码，我们首 先要从校验矩阵日获得它的生成矩阵g 。这一步我们可以通过高斯消去法来确 定生成矩阵g ，从而获得一个m m 的矩阵，然后将校验矩阵日变为如下的 形式： 日= 上易h = i m 。肼p t 册。d( 2 1 ) 如果矩阵缉不存在，则说明日矩阵不是满秩的，在这种情况下除去得到 的矩阵中线性相关的行就可以得到f 矩阵，此时的r 1 - ( r e n ) 。由f 矩阵可以 得到生成矩阵g ： g = p k 小i k d( 2 2 ) 此时日g _ 0 ，在矩阵缉存在的情况下珥日g = h g = o ，因此g 是校验矩阵 日对应的生成矩阵，由生成矩阵g 和信息码元五通过0 = g 白可以得到编码后的 码字仑。 2 1 2 二进制l d p c 码的t a n n e r 图表示 l d p c 码的稀疏校验矩阵可以通过二分图来表示，我们把这种图称为t a n n e r 图 3 9 】。t a n n e r 图和校验矩阵是一一对应的，维数为m n 的校验矩阵的t a n n e r 图中包含m 个校验节点和刀个变量节点。 t a n n e r 图由边的集合e 和节点集合y 组成，节点集合y 又包含两类节点， 分别是变量节点集合圪和校验节点集合圪，即y = 圪u 圪，其中圪= s o ，s l ， 1 为变量节点研的集合，圪= c 0 ，c l ，c m 1 ) 为校验节点c f 的集合。e 为校验 节点与变量节点之间的边的集合。如果校验矩阵口中第i 行第，列的元素h f ，不 为0 ，那么校验节点。和变量节点s j 之间就有一条边。 校验矩阵日和t a n n e r 图之间的关系如图2 1 所示。 h - - l 9 正0 0 ： 如0 1 疆0 1 1 一o - - ：1010 o 1o o1 1 c oc 1c 2 c 3 s qs 1s 2s 3s 4 s s 图2 1 校验矩阵日对应的t a n n e r 图表示 8 第2 章l d p c 码的基本原理 在图2 1 所示的t a n n e r 图中，6 条虚线组成了个闭合的环路，由s o 起始， 经过c o 峪3 叼l 蛄2 一晚，最后返回s o ，这样，变量节点s o 、s 2 、趵和校验节点 c o 、c l 、c 2 就构成了一个长度为6 的环。在一个l d p c 码的t a n n e r 图中，环几 乎是不可避免的，我们把长度最小的环的长度称为t a n n e r 图的围长( g i r t h ) 。 t a n n e r 图中短环的存在会对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 码的t a n n e r 图中几乎是不可避免的，如何 减少错误信息在环内传播则成了研究热点。t t i a n 4 0 等人提出外信息度数 ( e x t r i n s i cm e s s a g ed e g r e e ，e m d ) 的概念。 外信息节点：一个变量节点集合的外信息节点定义为那些只连接到这个变 量节点集合一次的校验节点的集合。 外信息度数：一个变量节点集合的外信息度数定义为这个变量节点集合的 外信息节点数。 在此基础上，我们定义一个环的外信息度数为参与这个环的变量节点所组 成的集合的外信息度数。 在设计l d p c 码时，我们应该让它的环具有尽可能大的外信息度数，从而 降低环内错误信息的影响。 2 1 3p e g 算法 l d p c 码的构造方法可以分为两大类：随机构造方法和结构化构造方法。 h u 1 5 1 6 等人提出的p r o g r e s s i v ee d g eg r o w t h ( p e g ) 算法是一种著名的l d p c 码随机构造方法。这个算法在每次添加边的时候可以使得环长尽可能地大，但 不能保证得到的t a n n e r 图是最优的。利用这个算法构造l d p c 码之前必须给出 变量节点的数目和度数分布，下面我们简单介绍一下这个算法。具体步骤为： 1 对于任意一个变量节点s j ，在对它添加第一条边时，只需找到在当前子 图中具有最低度数的校验节点白，然后把它们连起来作为第条边p 。 9 中山大学硕士学位论文 2 对于其它边，以变量节点s ，为根节点把当前t a n n e r 图展开到深度，。把 以s j 为根节点展开到，层所能到达的校验节点集合记为州，与之相应的补集为 n 。i ，即n i = 圪n 勺i 。如果蜕g 而呜1 = a ，或者集合n 勺t 中的校验节点 不再增加但：中的校验节点数仍小于全体校验节点数，就在! 中选取度数最 低的校验节点与s ，相连。 3 重复第2 步直到所有与s j 相连的边添加完毕。 4 重复上述3 步，直到所有变量节点的边都添加完毕。 p e g 算法构造的l d p c 码获得了优异的性能，但是这种算法具有一般随机 构造方法的共同的缺点：构造的l d p c 码的校验矩阵中非零元的位置是没有规 律的，存储这样的矩阵就需要占用大量的存储空间，编码时也难以找到快速的 编码方法，不利于硬件实现。准循环l d p c 码则很好地解决了这一问题。 2 1 4 准循环l d p c 码 准循环l d p c 码的校验矩阵是由一系列大小相等的循环移位方阵或全零矩 阵构成的。一个m x n 的准循环l d p c 码的校验矩阵结构可以表示如下： h = g ，oq o 1 一线f - l q l ，oq l ，l q l ，f - l ； q - l oq - l i q c _ l ，_ l 其中，q f ( 0s f c - 1 ，05 st - 1 ) 称为准循环l d p c 码校验矩阵的子矩阵， 它是一个维数为三的方阵，三与刀的关系为：m = c x l ，船= t x l 。每个子矩阵 都是一个循环矩阵，也就是它的第一行( 列) 是由最后一行( 列) 的循环右( 下) 移一位得到，其它的每一行( 列) 都是由上一行( 列) 的循环右( 下) 移一位 得到，因此只要子矩阵中的任意一行( 列) 确定了，则整个子矩阵也就确定了。 由于该类码的校验矩阵是由循环移位子矩阵或零矩阵组成，因此，不需要很多 存储单元来存储该校验矩阵。同时，这种类型的码由于具有非常好的校验矩阵 结构，编码器和译码器都能用简单的移位寄存器来实现，而且能达到具有线性 关系的低编码复杂度【4 l 】。 1 0 第2 章l d p c 码的基本原理 2 1 5 p e g - q c l d p c 码 p e g 算法构造的l d p c 码获得了优异的性能，引起了研究人员的关注。l i 4 2 】 等人将p e g 算法引入到准循环l d p c 码的设计当中，构造性能良好的 p e g q c l d p c 码。根据该算法，要构造一个7 x 维，子矩阵维数为三的准循 环l d p c 校验矩阵首先要把变量节点和校验节点分组，每组有三个节点，这样， 我们就可以得到f ( = 儿) 组校验节点集合和t ( = n l ) 组变量节点集合。然后我们对 t a n n e r 图以组为单位添加边，而不是以节点为单位添加边。每组中只要有一个 节点的边确定了，其它点的边就可以根据循环特性确定。该算法的具体步骤如 下： 1 在对变量节点譬添加第一条边时，如果j = k l ，则将校验节点c f 与s j 相连作为变量节点s j 的第一条边，其中，白是当前t a n n e r 图中度数最低的校验 节点( o n 果这样的校验节点个数大于1 ，则随机选取一个) 。如果础x 三+ “o s ， 9 1 ) ，该变量节点的入射边可以根据循环特性来确定：将s 与校验节点 c i ，腑卜肿m o o t m ，。) 相连即可。 2 在对变量节点母添加其它边时，如果j = k l ，则以变量节点s j 为根节点 把当前t a n n e r 图展开到深度，直至校验节点集合州a 但：”= a ，或者集 合中校验节点的个数不再增长，但仍小于全体校验节点个数时，我们从校验 节点集合n ，t 中选出度数最低的校验节点白和譬相连。如果= 取+ f ( o s ，9 1 ) ， 该变量节点的入射边可以根据循环特性来确定：将$ 与校验节点c i 砌脚+ 。l l o d ( m ，。) 相 连即可。 3 根据以上两步添加所有的变量节点的边后，把所有变量节点的第一条入 射边删除，然后为变量节点点( j f = 七三) 重新选择一个具有最低度数的校验节点与 研相连，然后其它的变量节点同样根据循环特性来确定。 除了l i 等人在这一方面做了深入的研究，l i u 等人【4 3 】中也提出了一种 p e g 算法与结构化相结合的准循环l d p c 码的构造方法，并把构造的l d p c 码 应用到了图案介质存储当中。他们所构造的m x f 维校验矩阵日可以用两个矩阵 进行表示，一个称为基矩阵m ，它是c x t 维的二进制矩阵，m ，刀和c ，的关系 中山大学硕一l 学位论文 可表示为m = c x l ，刀= t x l ，另一个称为移位次数矩阵p ，它的每一个元素代表 矩阵日中相应的子矩阵的循环移位次数。要构造矩阵日，只需要确定矩阵m 和 矩阵p 即可。x c l i u 等人先用p e g 算法构造出基矩阵m ，然后根据式( 2 3 ) 得到移位次数矩阵p ( 式( 2 - 3 ) 中的p 和呀分别是矩阵p 和矩阵m 中第i 行和第 列的元素，z 表示矩阵m 中每一行非零元素的相对位置) ，最后通过维数为l x l 的循环移位单位阵替换矩阵肘中的“1 元素( 其中子矩阵循环移位次数由p 矩 阵决定) ，同时用全零矩阵替换矩阵m 中的“0 元素就得到了校验矩阵日。 鳓= r ：矾2 三0 1 ( 2 - 3 ) 鳓2 1 奠： 2 2二进制l d p c 码的译码 2 2 1 对数域置信传播算法 二进制l d p c 码的译码方法很多，本文无法对此一一介绍。我们在这里仅 对一种经典的方法对数域置信传播算法作简单介绍，而我们随后的二进制 l d p c 码仿真中也是采用这种译码方法。对数域置信传播算法【4 4 】【4 5 】实质上是 二进制l d p c 码的概率域译码算法 4 6 1 的对数域运算。译码器的输入为接收序 列的对数似然比，并在对数空间下，通过t a n n e r 图的校验节点和变量节点的连 接关系来传递信息。在介绍该算法之前，先给出如下定义： n ( m ) ：n ( m ) = n t i 0 ) ，即参加校验方程m 的变量节点的集合。 ( ，z ) ：( 坍) 切= 刀j 上0 ，刀却 ，即除去变量节点n 以外参加校验方程m 的变量节点的集合。 m ( n ) ：m ( n ) = i 风k 0 ) ，即变量节点n 参加的校验方程的集合。 致以) 切：旭船) ，z = 珑i 上乙疗o ，m 聊)