（通信与信息系统专业论文）多进制ldpc码的译码算法及应用研究.pdf

多进制l d p c 码的译码算法及应用研究 专业：通信与信息系统 硕士生：滕蔓 指导教师：刘星成副教授 摘要 l d p c 码是一类具有稀疏校验矩阵的线性分组码，它凭借着其优秀的逼近 s h a n n o n 限的性能从上世纪9 0 年代以来就一直备受众多学者的关注，目前l d p c 码已经成为了继t u r b o 码之后纠错编码领域的又一个研究热点。 多进$ 1 j l d p c 码是d a v e y 和m a c k a y 提出的基于g f ( q ) 上的l d p c 码，研究结 果表明，良好构造的多进制l d p c 码的性能要优于二进s t l d p c 码。在译码方面， 由于多进$ 1 j l d p c 码的译码复杂度要大大高于二进制l d p c 码，因此如何能在保证 误码性能的前提下有效地降低译码的复杂度就具有重要的研究意义。 本文提出一种多进$ 1 j l d p c 码基于比特翻转方法的改进b p 译码算法，它与多 进制傅立叶变换译码算法不同之处在于，在译码每一次迭代结束之后如果还没有 得到合法的码字，则利用比特翻转的思想，按照一定的策略对不符合所设条件的 符号进行翻转。在如何翻转对应的符号上，本文提出了两种翻转方法并分别对这 两种方法进行了实验仿真。在文中给定的参数和仿真平台下，仿真结果表明所用 的各种码长在使用所提出的改进译码算法译码时均能取得比傅立叶变换译码算 法更好的误码性能，其中所提出的第二种翻转方法比第种方法取得的性能要 好。另外，文中对所提出的改进算法和傅立叶变换译码算法的复杂度进行了仿真 比较和分析，结果显示使用改进算法在较高信噪比条件下可以有效地降低译码的 复杂度。 在应用方面，针对k a r a k u l a k 和s i e g e l 等人在图案介质存储( p a t t e r n e dm e d i a 中山大学硕士学位论文 s t o r a g e ) 中提出的一种新的读信道模型一“单磁头多磁岛( m u l t i p l ei s l a n d sp e r r e a dh e a d ) 模型，本文提出了将l d p c 码应用于该信道模型并采用联合迭代的方 式进行序列检测译码的方案。对于该模型的不同信道情况，本文提出采用不同元 域的l d p c 码来进行编译码。仿真实验表明，所提出的方案运用到三种不同形式 的磁头响应矩阵，在考虑i s i 和a w g n 噪声时都获得了优异的性能改进。 关键词：多进制l d p c 码，置信传播( b p ) 算法，比特翻转算法，图案介质存储 ( p a t t e m e dm e d i as t o r a g e ) ，“单磁头多磁岛模型 s t u d y o nd e c o d i n ga n d a p p l i c a t i o n so fn o n - - b i n a r y m a j o r ： n a m e ： l d p cc o d e s c o m m u n i c a t i o na n di n f o r m a t i o ns y s t l m u n l c a t i o na n da t l o ns y s t e m t e n gm a n 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 rl i ux i n g c h e n g a b s t r a c t l d p cc o d e sa r eac l a s so fl i n e a rb l o c kc o d e sd e f i n e di nt e r m so fs p a r s ep a r i t y c h e c km a t r i c e s s i n c e19 9 0 st h e yh a v ea t t r a c t e de n o u g ha t t e n t i o nb e c a u s eo ft h e i r s u p e r i o rp e r f o r m a n c et h a ta p p r o a c h e ss h a n n o n sl i m i t n o w a d a y sl d p cc o d e sh a v e b e c o m eas t u d yh o t s p o ti ne r r o rc o r r e c t i o nc o d i n ga f t e rt u r b oc o d e s t h es t u d i e so nn o n - b i n a r yl d p cc o d e sw e r ef i r s tm a d eb yd a v e ya n dm a c k a y a n dt h e yd e m o n s t r a t e das i g n i f i c a n t i m p r o v e m e n t o v e rt h e b i n a r y o n e si n p e r f o r m a n c ew h e nc a r e f u l l yc o n s t r u c t e d h o w e v e r ，t h eh i g hc o m p u t a t i o nc o m p l e x i t y o ft h ed e c o d i n ga l g o r i t h m sf o rn o n b i n a r yl d p cc o d e sc a n n o tb ei g n o r e di nm o s t a p p l i c a t i o n s t h e r e f o r ei t i sn e c e s s a r yt oe x p l o r eh o wt or e d u c et h ed e c o d i n g c o m p l e x i t yo fn o n b i n a r yl d p cc o d e sw i t h o u tp e r f o r m a n c el o s s i nt h i st h e s i sam o d i f i e db pa l g o r i t h mb a s e do nb i t f l i p p i n gm e t h o df o rd e c o d i n g n o n b i n a r yl d p cc o d e si sp r o p o s e d i td i f f e r sf r o mt h ec l a s s i c a lf o u d e rt r a n s f o r m d e c o d i n gi nt h a tt h eb i t f l i p p i n gm e t h o di se m p l o y e dt of l i pt h es y m b o l sw h e nn o v a l i dd e c o d i n go ft h es y n d r o m ei si d e n t i f i e da tt h ee n do fe a c hi t e r a t i o n w ec o m p a r e t h ed e g r e eo fe a c hv a r i a b l en o d ew i t ht h en u m b e ro fs i g n a l st h a tt h ev a r i a b l en o d e h a sa c c u m u l a t e d i ft h et w on u m b e r sa r ee q u a l ，t h e nt h ec o r r e s p o n d i n gs y m b o li s f l i p p e d s i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h ma c h i e v e ss u p e r i o rs e r i i i 中山大学硕士学位论文 p e r f o r m a n c ei m p r o v e m e n t so v e rt h ef o u r i e rt r a n s f o r md e c o d i n ga l g o r i t h m ，i nt h e r e l a t i v e l yh i g he d n or e , o n , t h ed e c o d i n gc o m p u t a t i o nc o m p l e x i t yi se f f i c i e n t l y r e d u c e d 、肮t i lt h ep r o p o s e da l g o r i t h m t h ep a t t e r n e dm 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 dw a sp r o p o s e db y k a r a k u l a k , s i e g e l ，e ta 1 t h i sn e wt y p eo fm e d i ai sap r o m i s i n gs u b s t i t u t e f o r l l i g h - d e n s i t ym a g n e t i cr e c o r d i n gm e d i a i nt h i st h e s i sas c h e m e 嘶t i ll d p cc o d e s a n dj o i n ti t e r a t i v ed e c o d 崦f o rt h i st y p eo f p a t t e r n e dm e d i as t o r a g ei sp r o p o s e d f o r r e a dh e a dm o d e l sw i t hd i f f e r e n tn u m b e ro ft r a c k sa n d i s l a n d s ，l d p cc o d e s 证m d i f f e r e n tgo v e rg a l o i sf i e l dg f ( q ) a l es u g g e s t e dt ob ee m p l o y e d t h es i m u l a t i o n r e s u l t sa n da n a l y s e ss h o wt h a tt h es u g g e s t e ds c h e m eo ft h el d p cc o d e sa n dt h ej o i n t d e c o d i n gs i g n i f i c a n t l yi m p r o v et h es e rp e r f o r m a n c eo v e rt h ep a t t e r n e dm e d i a m a g n e t i cc h a n n e l s k e yw o r d s ：n o n b i n a r y l d p cc o d e r b e l i e f - p r o p a g a t i o n ( b p ) a l g o r i t h m ， b i t f l i p p i n g ( b f ) a l g o r i t h m ，p a t t e r n e dm e d i ag o r a g e ，“m u l t i p l ei s l a n d sp e rr e a d h e a d ”m o d e l i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行 研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其 它个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由 本人承担。 学位论文作者签名：膝蔓 日期：j 口口7 年岁月乃日 使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料 室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、 缩印或其他方法保存学位论文。 学位论文作者签名：滕蔓 日期：埘7 年乡月乃日 导师签名引 日期：卸。7 年 f 月玎日 第1 章绪论 随着今年来移动通信技术的快速发展，纠错编码技术在数字通信技术领域 和传输系统中发挥着越来越重要的作用。本章首先介绍了信道编码的重要性和 发展史，接着介绍了二进制和多进制l d p c 码的研究现状，主要包括码构造， 编译码以及应用等方面，最后阐述了本文的研究意义以及创新点。 1 1研究背景及现状 1 1 1 信道编码的必要性 当今世界科学技术的发展日新月异，移动通信技术从开始兴起到今天蓬勃发 展的几十年中，已经在人类的生产和生活中占据了极其重要的位置。从上世纪7 0 年代第一代模拟蜂窝通信系统的诞生，到上世纪9 0 年代第二代移动通信系统实现 了从模拟技术到数字技术的转变，从而给通信产业带来发展史上空前的繁荣，再 到如今在全球范围内推广的第三代移动通信( 3 g ) 将传统的移动通信方式与开放 的互联网结合，个人移动通信已经进入了其发展史上的快速成长期。 移动通信技术之所以能够得到如此迅猛的发展，主要的原因在于它能够为人 们日常的通信提供信件和固定电话等诸多通信方式所远不能及的便利，它灵活、 方便、高效，极大地满足了现代社会信息化发展的需求，在人们的物质生活和精 神生活中扮演了至关重要的角色。2 0 0 9 年1 月7l q1 4 ：3 0 ，工业和信息化部为中 国移动、中国电信和中国联通发放了3 张第三代移动通信( 3 g ) 牌照，这标志 着我国正式进入3 g 时代。3 g 牌照发放后，我国将形成一条包括3 g 网络建设、 终端设备制造、运营服务、信息服务在内的通信产业链，这对我国扩大内 需、刺激经济增长具有重要的作用。3 g 技术是向未来个人通信演进的一个重 要发展阶段，它的推进必将掀起无线通信的新浪潮，具有划时代的意义。 移动通信的发展必然伴随着通信中各种技术的开发和研究，其中对信号的可 靠传输的相关技术的研究也是人们研究的热点之一。无线移动信道是通信中异常 中山大学硕士学位论文 复杂难测的通信信道之一，无线电波在传播的过程中会发生多径传播引起的衰落 和信道时延扩展，而且衰落的特性随着周围的环境的变化而变化，再加上接收端 移动速度的影响，使得信号产生码问干扰和失真，极大地影响了通信质量，在这 种情况下，采用信道编码是提高通信质量，降低信息传输的错误概率的有效的方 法和手段。 信道编码也称纠错编码，它的本质是增加通信的可靠性，通过在要发送的信 息符号中加入一些冗余符号，使得信息符号和冗余符号之间满足一定的校验约束 关系，然后将它们按照一定的规则组合成码字发送出去，从而达到能够在接收端 根据这种校验约束关系来检错纠错的目的。然而，通信系统最主要的质量指标除 了可靠性之外还有有效性，通过在信息符号中插入冗余符号必然使得在传输的过 程中原始信息的传输速率降低，这就影响了传输的效率，降低了有效性。因此， 可靠性和有效性是一对矛盾体，如何能够在两者之间取得最佳，从而研究出在给 定条件下最合适的技术，是信道编码研究的重要任务。 1 1 2 信道编码的发展 1 9 4 8 年，信息论的主要创始人香农在他发表在贝尔实验室技术杂志上的经典 著作通信的数学理论 1 j d p 建立了通信系统的数学模型，精确地定义了信源、 信道、信宿、编码、译码等概念，提出了信源编码定理和信道编码定理，创立了 信息理论，为通信系统中的消息可靠、有效地传输奠定了理论基础。 在信道编码定理中，香农指出，在满足以下的三个条件的前提下，在有噪信 道中可以实现无差错的传输：( 1 ) 编码采用随机编码的方式；( 2 ) 码长趋于无穷 大；( 3 ) 译码的方式采用最大似然译码。该定理为人们研究探索最佳的编码方案 指明了方向，但是如何才能实现最佳编码从而达到或接近香农限，香农并没有给 出具体的实现方案。 在香农的信道编码理论的指导下，在随后的几十年中，科学家们围绕着香农 所提出的思想进行了不懈的探索，提出了多种信道编码的方案，并逐步向着香农 提出的理论极限靠近。1 9 5 0 年，h a m m i n g 等人提出了能纠正单个错误的h a m m i n g 码【2 】，随后，g o l a y 于1 9 5 4 年提出- g o l a y 码【3 】，r e e d 和m u l l e r 提出了l w 码【4 】， 这些码都是线性分组码。不久之后的1 9 5 5 年e l i a s 等人提出了卷积码【5 】，它具有 2 第l 章绪论 动态的t r e l l i s 结构，但是译码复杂度较高。1 9 6 0 年，b o s e 、r a y c h a u d h u r i 和 h o c q u e n g h e m 发现了 b c h 码 6 】，随后r e e d 和s o l o m o n 发现t r s 码【7 】，r s 码后来 在磁信道和播放器标准等场合应用广泛【8 】。1 9 6 6 年，f o m e y 提出了级联码【9 】， 此后人们都采用级联的方式来构造好码，常用的有以r s 码为外码、卷积码为内 码的级联码。然而，以上所提出的各种码字有些虽然具有优良的性能，但是都与 香农的理论极限差距较大。 1 9 9 3 年，c b e r r o u 等人提出了采用迭代译码的方式来译码的并行级联码t u r b o 码【1 0 】，t u r b o 码很好地应用了香农提出的信道编码定理的条件，将卷积码和交织 器相结合实现随机编码的思想，并且采用软输出迭代译码来逼近最大似然译码， 获得了接近香农限的优异的性能。t u r b o 码的提出使得信道编码领域掀起了一股 研究热潮，并在第三代移动通信中t u r b o 码成为了纠错码标准。 随着t u r b o 码被提出并得到学者们深入的研究和广泛的应用，g a l l a g e r 早在 1 9 6 2 年就提出的l d p c 码( 低密度校验码) 【1 1 】于1 9 9 6 年被m a c k a y 等人重新发现 【1 2 ，他们采用随机构造的l d p c 码进行研究发现，规, 贝i j l d p c 码采用置信传播译 码具有和t u r b o 码相似的性能，在较大码长时l d p c 码的性能甚至于超过了t u r b o 码。这一发现使得l d p c 码成为了继t u r b o 码之后信道编码领域的又一个研究的热 点。目前对l d p c 码的研究主要集中在校验矩阵的构造、译码算法、编码、性能 分析以及应用等方面。 1 1 3l d p c 码的国内外研究现状 自从m a c k a y 等人于1 9 9 6 年重新提f l j l d p c 码 1 2 】以来，经过众多学者的研究， l d p c 码的理论研究得到了蓬勃的发展，对二进$ i j l d p c 码的研究取得了丰硕的成 果。m a c k a y 和n e a l 等人【1 2 】【1 3 】研究的结果显示随机构造的规则l d p c 码在采用和 积译码算法译码时具有和t u r b o 码相似的误码性能，在较大码长时的性能甚至超 过了t u r b o 码。l u b y 等人 1 4 1 提出了不规则的l d p c 码，使l d p c 码的概念得到了 推广，并由实验证明了非规则l d p c 码的性能要优于规则l d p c 码。t j r i c h a r d s o n 和r l u r b a n k 提出了密度进化理论，以该理论可以指导非规贝j j l d p c 码的设计， 通过优化节点度数的分布来寻找性能优异的非规贝i j l d p c 码 1 5 】，并提出了一种 新的编码算法 1 6 】，从而有效降低了编码的运算量和存储量的需求。s k o u 和s 中山大学硕士学位论文 l i n 等人【1 7 】从有限几何理论着手，构造出了具有优异性能的l d p c 码，这类码一 般具有准循环结构，极大的降低了编码复杂度。x yh u 1 8 1 9 2 0 等人提出了 l d p c 码的p e g 构造方法，用该方法构造的l d p c 码i 蜩g a l l a g e r 或m a c k a y 的方法 构造的码都更具优势。在译码算法的研究方面，常用的译码算法主要有两类【“】， 一类是比特翻转算法，一类是基于置信传播的译码算法，也称b p 算法。这两种 译码算法相比，比特翻转算法复杂度低，实现较为简单；而置信传播算法虽然运 算比较复杂，但是性能好。为了降低译码复杂度，f o s s o r i e r 笔j g 人作了比较深入的 研究 2 1 1 1 2 2 2 3 ，提出了简化的迭代译码算法，这些算法大大降低了译码复杂度， 却可以得到接近于b p 算法的性能。j z h a n g 等人提出了s h u f f l e db p 算法 2 4 1 ，这 种算法通过利用已经更新的节点的信息来进行迭代，从而加快了收敛的速度。在 应用方面，h x s o n g 等人【2 5 】对l d p c 码在磁记录系统方面的应用情况作了研 究，针对非高斯的低质量信道上译码算法的研究也已经展开，如瑞利衰落信道、 部分响应信道、i s i 信道等【2 6 】 2 7 】 2 8 】。 基于g f ( q = 2 p ) 的多进f l ；i j l d p c 码是1 9 9 8 年f l j d a v e y 和m a c k a y 提出的，他们用 已构造的二进制校验矩阵，将矩阵中的“l 元素用g f ( q ) 域中的非零元素代替， 将l d p c 码从二元域扩展到了多元域上【2 9 】【3 0 】。研究结果表明，良好构造的多进 制l d p c 码在a w g n 信道下的性能要优于二进制l d p c 码，并且多进f l ；i j l d p c 码的 抗突发错误性能也明显优于二进f l 割 l d p c 码【2 9 】 3 0 】。误码性能最优异的l d p c 码 是非规则的多进$ i l d p c 码【3 l 】。c h a r l yp o u l l i a t ，m a r cf o s s o r i e r 和d a v i dd e c l e r c q 等人提出了用二进制映像的方式来构造多元规则的变量节点度数为2 的l d p c 码， 用这种方式构造的l d p c 码具有低差错平底的性能【3 2 】。s h ul i n 等人提出了基于 有限域构造多进制准循环l d p c ( q c l d p c ) 码的方法【3 3 】【3 4 】【3 5 】。这种用代数方 法构造的多元l d p c 码具有较低的错误平层，且其编码增益超过采用代数译码算 法下相同码长和码率的r s 码。在多进f l ；i l d p c 码译码方面，由于多进$ 1 j l d p c 码 具有大大高于二进$ i j l d p c 码的译码复杂度，因此在如何降低译码复杂度方面研 究人员也做了大量的努力：针对d a v e y 和m a c k a y 最初提出的概率域的译码算法， t j r i c h a r d s o n 和r l u r b a n k e 提出了用傅立叶变换译码的方法来降低译码的复 杂度【3 6 】，d a v e y 于1 9 9 9 年在他的博士论文中具体阐述了概率域的快速傅立叶变 换的译码算法【3 7 】，之前所采用的多进制l d p c 码在g f ( q ) j 二的概率域译码方法， 4 第1 章绪论 其复杂度与9 2 成正比，而t j r i c h a r d s o n ，r l u r b a n k e 和d a v e y 所提出的傅里叶 变换译码的方法在不降低译码性能的情况下可明显减少计算的复杂度。h e n k w y m c c r s c h ，h e i d is t e e n d a m 和m a r cm o c n e c l a e y 提出了对数域的和积译码算法 【3 8 ，该算法在计算复杂度和应用上都比概率域算法更具有优势【3 9 】。b a r n a u l t ， d e c l e r c q 和f o s s o r i e r 提出了基于g 元域上的快速傅里叶变换的和积译码算法 ( f f t - q s p a ) 4 0 4 1 】，这种算法比g 元和积算法更为简单有效。a d r i a nv o i c i l a , d a v i dd e c l e r c q ，f r a n g o i sv e r d i e r 等人提出了e m s 译码算法，该算法具有低复杂度， 低存储的性能，适于硬件实现 4 2 】。 1 2 论文的研究意义及创新点 l d p c 码自1 9 9 6 年被研究人员重新发现并发展至今，一直凭借着它的优异的 纠错性能和简单的并行译码算法得到研究工作者们的广泛青睐。与t u r b o 码相比， l d p c 码的译码是并行操作，译码复杂度低，适合硬件实现；同时它可以达到很 高的码率，传输的效率高；它具有很低的差错平底，抗干扰能力强。因此，l d p c 码具有广阔的发展和应用潜力，未来它将在光纤通信、深空通信、数字水印、磁 光全息存储、卫星数字视频、移动和固定无线通信等方面得到广泛的应用。 多进制l d p c 码是将l d p c 码从二元域扩展到了多元域上，它具有比二进制 l d p c 码更重的列重，也具有优异的接近香农限的性能，无论是在信道条件相对 较好的a w g n 信道下，还是在信道条件相对恶劣的瑞利衰落信道和突发噪声信道 下，多进带j j l d p c 码均表现出r s 码所无法达到的优越性能，如在磁盘存贮系统中， 多进铝i j l d p c 码的纠错。i i , 土q - 台日匕b 要大大好于r s 码的性f l 皂 4 3 4 4 ，因此，多进制l d p c 码在磁盘存储、下一代a d s l 系统以及无线通信、深空通信方面是取代作为高码 率短帧码工业标准之一的r s 码的强有力的候选者，有着极其重要的应用价值。 另外，多进$ 1 j l d p c 码结合高阶调制技术在3 g 、b 3 g 和第四代移动通信中将得到 广泛的应用。 本文主要做了两个方面的工作，一方面是把比特翻转的思想融入到多进制 l d p c 码的傅立叶变换译码的迭代过程中，提出了多进伟w j l d p c 码基于比特翻转的 b p 译码算法；另一方面是将l d p c 码应用到图案介质存储( p a t t e r n e dm e d i as t o r a g e ) 的“单磁头多磁岛”的模型中，对于不同的磁头响应矩阵提出了用不同元域上的 中山大学硕士学位论文 l d p c 码来编译码的方法。 多进f l ；i l d p c 码有着优越的性能，然而它在译码的过程中大大增加的复杂度 也是不容忽视的。因此，如何能够在不影响性能的情况下有效地降低译码的复杂 度就成了一个需要研究的问题。本文把比特翻转的思想融入到多进铝i l d p c 码的 傅立叶变换译码的迭代过程中，在傅立叶变换译码每一次迭代结束之后如果还没 有得到合法的码字，则运用比特翻转的思想，采取投票的方式，找出不满足校验 的校验节点，对和它相连的变量节点进行投票，然后翻转那些对应的变量节点度 数与其所得的投票数相等的符号。这样一方面不会破坏原有的傅立叶变换译码的 迭代部分的结构，没有降低译码性能；另一方面可以通过减少译码的平均迭代次 数，从而减少译码的复杂度。仿真实验表明，该方法能够在不使译码性能退化的 情况下有效地降低多进f l 刘l d p c 码的译码复杂度。 图案介质存储( p a t t e r n e dm e d i as t o r a g e ) 是一种可将硬盘记录密度大大提高的 候选技术，它可以使每个磁性颗粒携带l b i t ，从而大大提高了存储面密度 4 5 】。 针对这一技术，k a r a k u l a k 和s i e g e l 等人提出了一种新的读信道模型一“单磁头多 磁岛 ( m u l t i p l ei s l a n d sp e rr e a dh e a d ) 模型 4 6 】，然而，对于这一模型仿真得出的 误符号率( s e r ) 的性能却不能很好地满足实际应用中的需求。基于这一情况，我 们提出利用纠错码技术对该模型的不同磁头响应矩阵采用不同元域的l d p c 码来 进行编译码，从而改善在该信道条件下的误码性能。仿真实验表明，针对不同的 磁头响应矩阵，运用不同伽逻华域上的l d p c 码均能有效地改善误码性能。 1 3论文的课题来源及项目资助 国家自然科学基金项目( t h en a t i o n a l n 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 tn o 6 0 6 7 3 0 8 6 ，6 0 7 111 4 0 4 1 9 ) ：l d p c 码的构造及基于置信传播的译码 算法研究。 1 4论文的结构安排 第l 章绪论，首先介绍了在现代通信系统中进行信道编码的重要性和信道编 码的发展过程，然后介绍- j l d p c 码的国内外研究现状，包括二进制 和多进$ l j l d p c 码的码构造、编译码以及应用等方面，最后指出了本 6 第1 章绪论 论文的研究意义以及创新点。 第2 章介绍了l d p c 码的一些基本原理等知识，首先介绍了二进制l d p c 码 的腓巨阵表示、t a n n e r 图表示以及编译码。然后介绍了准循环l d p c 码的结构，接着介绍了多进带i j l d p c 码的结构及描述，最后介绍了多 进f 1 i l d p c 码的译码算法，包括传统译码算法和快速译码算法等。 第3 章提出了多进制l d p c 码基于比特翻转的b p 译码算法。首先介绍了所提 出的算法的基本思路，并对该算法进行了复杂度的分析，最后给出了 仿真实验结果。 第4 章提出将l d p c 码应用于图案介质存储( p a t t e m e dm e d i as t o r a g e ) 中，针 对k a r a k u l a k 和s i e g e l 等人提出的的“单磁头多磁岛模型，对不同类 型的磁头响应矩阵提出用不同伽逻华域上的l d p c 码进行编译码，并 给出了实验结果。 第5 章对研究成果进行总结，提出了需要进一步进行研究的问题。 7 第2 章l d p c 码的基本原理 本章主要介绍l d p c 码的基本概念，包括二进制和多进制l d p c 码的表示 方法、码构造及译码算法等，其中对二进制l d p c 码的译码算法主要介绍了硬 判决译码算法和和积译码算法，对多进制l d p c 码的译码算法主要介绍了传统 译码算法和快速译码算法。 2 1 二进制l d p c 码的结构及描述 2 1 1二进制l d p c 码的日矩阵表示及编码 l d p c 码( 1 0 wd e n s i t yp a r i t yc h e c kc o d e s ：低密度奇偶校验码) 是具有稀疏校验 矩阵日的一类线性分组码。所谓稀疏校验矩阵是指校验矩阵日中的非0 元素的 个数远远小于0 元素的个数，正是由于这种校验矩阵的稀疏性，才使得l d p c 码表现出优异的纠错性能。 二进制l d p c 码是定义在二元域上的( 聆，肋低密度校验码。我们用力来定义 l d p c 码的码长，用k 来定义l d p c 码的信息序列的长度。二元域是指二元伽 逻华域g f ( 2 ) ，在该域中只有“o 和“1 这两个元素，其中“0 ”和“l 按 照模2 加和模2 乘构成域。l d p c 码可以由它的校验矩阵日或生成矩阵g 唯一 确定，对于维数为m x n 的校验矩阵日，它的m 行对应着m 个校验方程，而以 列对应着一个码字的n 位，在校验矩阵日是满秩的情况下，m = l , i ，k ，此时码率 r = k n = ( n m ) n = 1 ( m n ) ；如果校验矩阵日不是满秩的，那么日矩阵的秩小于m ， 则m n k ，此时码率r i 一( m n ) 。图2 1 给出了g a l l a g e r 11 】构造的一个二进制 l d p c 码对应的日矩阵表示的例子，该例中码长为2 0 ，然而该日矩阵不是满秩 的，它的1 5 行中只有1 3 行是线性无关的，在这种情况下k = - 2 0 1 3 = 7 ，码率 r = k n - - o 35 。 在图2 1 的日矩阵中，每一行的非零元素的个数都是4 ，每- n 的非零元素 的个数都是3 ，我们称日矩阵中各行非零元素的个数和各列非零元素的个数均 为定值的l d p c 码为规则l d p c 码，否则为非规则l d p c 码。l d p c 码日矩阵 9 中山大学硕士学位论文 中每一行的非零元素的个数称为行重，每一列的非零元素的个数称为列重。 = 图2 ir r = 2 0 ，r - - 0 3 5 的二进制l d p c 码 对于一个由校验矩阵日定义的l d p c 码，为了得到它的生成矩阵g 从而进 行编码，我们可以通过高斯消元法确定一个m m 的矩阵 p 1 ，从而将校验矩阵 日变为如下的形式： 日= 砟- 1 h = l 。历p r 胍七】 ( 2 - 1 ) 如果矩阵珥不存在，则说明日矩阵不是满秩的，在这种情况下截去运用高 斯消元法得到的矩阵中线性相关的行就可以得到仃矩阵，此时的r i ( m n ) 。 由仃矩阵可以得到生成矩阵g ： g = 最朋厶七】 ( 2 - 2 ) 此时h g = o ，在矩阵珥存在的情况下h n l - l g = h g = o ，因此g 是校验矩阵 日对应的生成矩阵，由生成矩阵g 和信息码元叠通过6 = g 曼可以得到编码后的 码字6 。 2 1 2 二进制l d p c 码的t a n n e r 图表示 l d p c 码除了可以由它的校验矩阵日表示外，还可以用图模型来表示，我 们称之为t a n n e r 图【4 7 】的表示方法。t a n n e r 图与校验矩阵是一一对应的，它包 含了两类节点的集合，一类是变量节点的集合，另一类是校验节点的集合。对 o o o o l o o o o l o o o o l o o o o l o o o l o o o l o o o o o o i o o l o o l o o o o o o o o l o l o o o o o o l o o o o i o o o o o l o i o o o o o o l o o o o i o o o o o l o o o l o o o l o o o o o l o o o o l o i o o o o o o l o o o o o o o o o o o o o o o o l o o o o o l o o l o o o o o l o o o l o o o o o o o l o o o o o o o o o o o o o l o o o o 0 o o l o o l o o o l o o o o o l o o o l o o o o i o o o o i o o o o o o o o i o o o o o o o 0 o o o i o o o o o o o l o o o o l o l o 0 o o o o l o o o o l o o l o o o o o l o o o o i o o o o o o o o o o o o o o o 第2 章l d p c 码的基本原理 于二进制l d p c 码，t a n n e r 图中包含了力个变量节点和m 个校验节点，这力个 变量节点也称为比特节点，它们分别代表着一个码字的r i 个比特，也分别对应 着校验矩阵日的每一列，而这脚个校验节点则对应着所个校验约束，即分别 对应着校验矩阵日的每一行。如果t a n n e r 图中第，个变量节点和第f 个校验节 点由一条边连接，则对应着矩阵日中的f 行，列的位置值为“1 。t a n n e r 图中 与变量节点相连的边的数目称为该变量节点的度数，与校验节点相连的边的数 目称为该校验节点的度数。对于规则l d p c 码，t a n n e r 图中所有校验节点的度 数都相等，等于日矩阵的行重；所有的变量节点的度数也相等，等于日矩阵的 列重。式( 2 3 ) 所示的日矩阵所对应的t a n n e r 图如图2 2 所示，图中圆形表示变 量节点，方形表示校验节点。由图可知，h 矩阵对应的t a n n e r 图的校验节点的 度数为3 ，变量节点的度数为2 ，对应的码为规则l d p c 码。 h = l0 ol 0l l0 0l 1l 00 l0 ol 0 o 1l l0 q呸qc 4 图2 2 校验矩阵日对应的t a n n e r 图表示 ( 2 - 3 ) 在图2 2 所示的t a n n e r 图中，6 条粗线组成了一个闭合的环路，由耽起始， 经过q _ 心_ c l _ _ o ，最后返回屹，这样，变量节点惕心、和校验节点 c l 、c 2 、c 3 就构成了一个长为6 的环。在一个l d p c 码的t a n n e r 图中，每个节 点都会存在这样的环，我们将其中长度最小的一个称为该节点的最小环长。 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 码的性能产生重要的影响【4 8 】。由于l d p c 码的基于置信传播的译码算法是假设各个变量节点是相互独立的，而环的存在 破坏了这种假设，使得译码的性能明显下降。围长越长，那么消息传递算法就 中山人学硕士学位论文 越接近于最优算法。因此我们在构造l d p c 码的校验矩阵时，要尽量避免t a n n e r 图中出现短环的情况。 2 1 3 准循环l d p c 码 准循环l d p c 码的校验矩阵是由一系列大小相等的l l 的循环移位子矩阵 或全零矩阵构成。对于二进制l d p c 码，它的循环移位子矩阵的第一行是由最 后一行的循环右移一位得到，其他的每一行都是由上一行的循环右移一位得到； 它的第一列是由最后一列的循环下移一位得到，其他的每一列都是由上一列的 循环下移一位得到。x l i u 等人【4 9 】中提出了p e g 算法【1 8 】 1 9 】【2 0 】与结构化相 结合的准循环l d p c 码的构造方法，由于在后文的实验仿真中会用到该方法构 造的l d p c 码，因此在这里对该构造方法进行介绍。 x l i u 等人【4 9 】所构造的校验矩阵日可以用两个矩阵进行表示，一个称为基 矩阵m 它是c x t 维的二进制矩阵，另一个称为移位次数矩阵尸，它的每一个 元素代表矩阵日中相应的子矩阵的循环移位次数。要构造矩阵日，只需要确定 矩阵m 和矩阵p 即可。x l i u 4 9 先用p e g 算法【1 8 】【1 9 】【2 0 】构造出基矩阵m 然后根据式( 2 - 4 ) 得到移位次数矩阵p ( 式( 2 - 4 ) q b 的p v 和口 分别是矩阵p 和矩阵 m 中第f 行和第，列的元素，z 表示矩阵m 中每一行非零元素的相对位置) ，最 后通过维数为l x l 的循环移位后的子矩阵替换矩阵m 中的“1 元素( 其中子矩 阵循环移位次数由p 矩阵决定) ，同时用全零矩阵替换矩阵m 中的“o 元素就 得到了校验矩阵日。 p o ： ( i x z ) m 甜口 = 三( 2 - 4 ) 2 1 彳= o 2 2二进制l d p c 码的译码 2 2 1 硬判决译码算法 在二进制l d p c 码的硬判决译码算法( b f 算法) 1 1 】中，沿t a n n e r 图上传递 的是二进制值，译码器首先对输入的数据进行硬判决得到“0 或“1 值，然 后对序列计算奇偶校验，根据校验结果对不满足校验方程最多的比特位进行翻 1 2 第2 章l d p c 码的基本原理 转，至此完成一次迭代。译码过程中不断的重复迭代步骤直到所有的校验都成 立或者达到最大迭代次数为止。具体步骤为： 1 初始化：对译码器接受到的数据，进行硬判决，硬判决的方法如( 2 5 ) 式 所示，得到初始译码序列扩= ( 0 ，c ：0 ，c 品) 。这里初始化迭代次数卢o ，序列长 度为。 c = 三 2 将代入校验方程计算校验和s = 于。h t ，得到各个校验式的校验结果： s = ( ，吐) 。这里校验方程的个数为从 3 统计每个变量节点所对应的校验式中不成立的个数z = 。这里 m e u ( n ) m ( n ) 表示变量节点r l 参加的校验的集合，若第m 个校验式成立，则s m = 0 ，否 则s m = l 。 4 从f 。= ( 爿，矗)