（通信与信息系统专业论文）ldpc码编译码算法研究.pdf

硕士论文l d p c 码编译码算法研究 摘要 低密度奇偶校验( l d p c ) 码是一种基于稀疏奇偶校验矩阵的线性分组码。由于 l d p c 码是性能接近s h a n n o n 极限的好码，并且具有较强的纠错能力、较大的灵活 性和较低的译码复杂度，使它成为近年来编码领域研究的一个热点，在通信的多个 领域得到了应用。 本文主要对l d p c 码的编译码算法进行研究。首先，介绍了通信系统和信道编码理 论。其次，阐述了l d p c 码的性能特点、发展应用以及l d p c 码的基本理论知识。再次， 介绍了l d p c 码的随机构造方法和结构构造方法，并对两大类构造方法进行了分析和比 较。最后，展开对l d p c 码编译码算法的研究。在译码算法上，重点对b p 译码算法进 行了介绍和性能分析。研究了l d p c 码b p 译码算法的四种简化算法和一种改进算法， 并通过m a t l a b 实验仿真对几种译码算法进行了详细的对比和分析。与几种简化算法 相比，改进算法可以在较低硬件复杂度的情况下提高译码的性能。在编码算法上，探讨 了l d p c 码的三种编码算法，并对每种编码算法的复杂度进行了分析。研究了一种基于 t a n n e r 图的、可以适用于任意l d p c 码的线性复杂度的编码算法，并对该算法整个分析、 编码过程以及编码的复杂度进行了详细的介绍。 关键词：l d p c 码，编码，b p 译码 a b s t r a c t硕士论文 a b s t r a c t l o w d 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 eo n eh n do fl i n e a rb l o c kc o d e sa p p r o a c h i n g s h a n n o nl i m i tb a s e do ns p a r s ep a r i t y c h e c km a t r i c e s t h e ya r e 、析t i le x c e l l e n te r r o rc o r r e c t i n g a b i l i t y ，f l e x i b i l i t y ，a n dl o wd e c o d i n gc o m p l e x i t y s ot h e ya r eb e c o m i n gap o w e rc o m p e t i t o ri n t h ec o d i n gr e s e a r c hf i e l d ，a n dh a v eb e e ns u c c e s s f u l l y a p p l i e d i nv a r i o u sf i e l d so f c o m m u n i c a t i o n sr e c e n t l y i nt h i sp a p e r ，t h ee n c o d i n ga n dd e c o d i n ga l g o r i t h m sf o rl d p cc o d e sa r em a i n l ys t u d i e d f i r s t l y ，t h ec o m m u n i c a t i o n sa n dc h a n n e lc o d i n gt h e o r y a r ei n t r o d u c e d ；s e c o n d l y ，t h e p r o p e r t i e s ，d e v e l o p m e n t sa n da p p l i c a t i o n so fl d p cc o d e sa r ep r e s e n t e d ；t h i r d l y ，t h er a n d o m c o n s t r u c t i o n sa n ds t r u c t u r e dc o n s t r u c t i o n sf o rp a r i t y - c h e c km a t r i c e so fl d p cc o d e sa r e a n a l y z e d l a s t l y ，t h ee n c o d i n ga n dd e c o d i n gi s s u e sa r es t u d i e d f o rt h eb pd e c o d i n g a l g o r i t h r n s ，s e v e r a lm a i nf a c t o r sa f f e c t i n gt h ed e c o d i n gp e r f o r m a n c ea l ea n a l y z e d a n dt h e n , f o u rs i m p l i f i e da n do n ei m p r o v e db pd e c o d i n ga l g o r i t h m sf o rl d p cc o d e sa r ep r o p o s e d ， w h i c ha r ea n a l y z e da n dc o m p a r e di nd e t a i lw i t hm a t l a bs i m u l a t i o n c o m p a r e d 、析t l l s i m p l i f i e da l g o r i t h m s ，t h ei m p r o v e db pd e c o d i n ga l g o r i t h mh a sb e t t e rp e r f o r m a n c e f o rt h e e n c o d i n gi s s u e ，t h r e ee n c o d i n ga l g o r i t h m sf o rl d p cc o d e sa n dt h e i rc o m p l e x i t i e sa r es t u d i e d e s p e c i a l l y ，al i n e a rc o m p l e x i t ye n c o d i n gm e t h o di si n v e s t i g a t e db a s e do nt a n n e rg r a p h sf o r a r b i t r a r yl d p cc o d e sa n di t sp e r f o r m a n c ei sa n a l y z e d k e yw o r d s ：l d p c ，e n c o d i n g ，b pd e c o d i n g i i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 汐f 。年占月f g 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：趟f d 年易月倌日 硕士论文l d p c 码编译码算法研究 1 绪论 1 1通信系统 通信是指人和人或者人和自然之间通过某种行为或媒介进行的信息交流与传 递，其目的就是传递消息，也就是传输信息。基本的点对点通信，就是把发送端的 信息通过某种信道传递到接收端。近代的通信主要是借助电或者光信号以及有关的 设备来完成的。 最简单的通信系统是由信源、信道和信宿三大部分组成的。信源的作用是产生 信息，信宿是接收信息。信道是传递信息的通道，是信源到信宿之间传递物理信号 的传输介质和设施，通常可以分为调制信道和编码信道两种。信息能够在噪声信道 中可靠地进行传输是通信系统的基本要求。图1 1 所示是一个典型的点对点单向通 信系统模型框图【l 】。在这个单向模型的基础上可以构成点对点的双向通信系统、点 对多点的单向广播通信系统以及多点对多点的多向卫星通信系统等等。 编码信道 信息厂磊石磊。l信息 图1 1通信系统模型 图1 1 中，左边发送端部分的任务是将信源产生的信息变换成为适合于信道传 输的信息发送出去。信源用来产生将要发送的信息，这些信息可能会因为表示方式 不适宜或者含有冗余而不适合直接通过信道进行传输。因此，先要通过信源编码器 把各种不同符号表示的信息变换成统一的信息序列，并除去存在的冗余，使信息能 够以最小的冗余进行传输。为了避免信道传输过程中受到各种噪声的干扰而导致接 收的信号发生错误，可以采用信道编码器在信源编码器输出的信息序列中再增加一 些冗余，尽量使得信道中引入差错造成的影响最小。在把数据送入信道进行传输前， 还要通过调制的方法把信道编码器输出的数据变换成为适合信道传输的信号。信号 经过调制以后，还可以提高频带的利用率，这时就可以通过发送设备将信号送入介 质中进行传输，传输的介质可以是有线电缆、无线电磁波等等。在传输过程中，信 1 绪论硕士论文 号必然会受到各种各样的噪声和干扰的影响，使得信号的波形遭到破坏。为此，接 收端部分就是要最大限度无差错地将发送端信源所产生的信息进行恢复，将传输过 程中噪声和干扰所造成的影响降至最低。可以说，接收端对信息的处理过程是发送 端处理过程的逆变换。 图1 1 中调制信道输入输出的一般是模拟波形信号，用连续函数表示。若以调 制信道作为信道，传输模拟信号的通信系统称为模拟通信系统。编码信道输入输出 的一般是码字符号序列，也就是离散数字信号。将编码信道作为传输信道的通信系 统是数字通信系统。 数字通信系统中常用传输速率和差错率来衡量性能。传输速率一般用码元传输 速率来表示，而差错率常用误码率或者误比特率描述。这两种性能指标分别反映的 是数字通信系统中的有效性和可靠性问题。信源编码采用信源编码技术除去信息中 的冗余，用尽可能少的码字来表示要进行传输的信息，同时提高编码的效率，主要 解决的是有效性的问题。信道编码技术在信息中增加冗余，即加入校验码元来尽量 减小误码率或者误比特率，解决可靠性的问题。所以说，可靠性和有效性在实现的 时候是互相矛盾的。信道编码增强了传输的可靠性，减小或者消除了信道噪声导致 的差错，确保通信系统造成的差错在可容许的范围内。虽然牺牲了传输效率，但很 多时候这种代价是值得的。 1 2信道编码及其发展 1 2 1 信道编码理论 1 9 4 8 年，c e s h a n n o n 在b e l l 系统技术杂志上发表了题目为通信的数学理论 的经典论文【2 】，标志着现代信息论和编码理论作为一门学科的诞生。这篇论文中提 出了著名的信道编码定理，也就是对于任意通信信道，一定存在一个非负的参数c 可 以用来表示信道传输信息的最大能力，称其为信道容量。当信息的传输速率r 小于 信道容量c 时，存在一种编码方法，能在码长，2 足够长，并且采用最大似然译码时， 使系统译码后的差错率达到任意小。这一定理证明了好码的存在，为l d p c 码和整 个信道编码提供了理论根据。 s h a n n o n 的信道容量公式是在引入加性高斯白噪声( a w g n ) 为信道噪声的情 况下推导出的。在a w g n 信道下，如果信道带宽是b ( h z ) ，信道输出的信号功率 是s ( w ) ，输出的噪声功率是n ( w ) ，那么，信道容量c 可以表示为： c = b l 0 9 2 ( 1 + 争 ( 1 1 ) 式( 1 1 ) 就是s h a n n o n 公式，其中，s 是信噪比。由于噪声功率与信道带宽有关， 当噪声的单边功率谱密度为n 时，噪声功率等于n = n o b ，此时，s h a n n o n 公式变换 2 硕士论文l d p c 码编译码算法研究 为： c 一引c t + 嘉， 2 ， 由于a w g n 是信道干扰当中危害最大的一种，因此，在非a w g n 的信道干扰 情况下，信道容量c 应该大于按s h a n n o n 公式计算得出的结果。 若系统以最大传输速率实现无误码传输时，传输速率r b 等于信道容量c ，此时 最大频谱效率是t 1 一= c b ，根据这些可以得到： 萨s 一惫 3 ) 万韧一盛 u j ) 式( 1 3 ) 中，毛0 表示每比特能量和噪声单边功率谱密度的比值， 将式( 1 3 ) 代入式( 1 1 ) 可得： 一c 丘= l 0 9 2 叶”一知 即功率效率。 ( 1 4 ) 墨：2 n - - 1 ( 1 5 ) o1 1 麟 当信道带宽b 无限大，即b j 时，最大频谱效率t 1 一j 0 ，这种情况下实现 无误码传输的最小邑o 为： e ，) 1 m “一1 l i m 竺= 三_ 二= l i l 2 - 1 6 d b( 1 6 ) t i 一呻o ot 1 由式( 1 6 ) 可知，在a w g n 信道，带宽召无限情况下，实现无误码传输的最 小信噪比为一1 6 d b ，这是理想情况下a w g n 信道的极限传输能力，称为s h a n n o n 限。根据s h a n n o n 的信道编码定理可知，采用不同的编码方法在不同的信道中传输 时，性能会有所差异。对于某种信道编码，可以用其与s h a n n o n 限的距离来衡量其 性能。可以这么说，构造出在性能上尽可能接近s h a n n o n 极限，复杂度较低而且可 以实现的信道编码就是实用的好码。 1 2 2 信道编码理论的发展 从1 9 4 8 年s h a n n o n 提出信道编码理论，证明了好码的存在至今，信道编码理 论的发展已历经6 0 多年。这期间，研究人员不断努力地寻找性能上尽可能和s h a n n o n 限接近，复杂度较低并且可实现的信道编码方法。 线性分组码是起步最早的一类信道编码，它是以代数几何为理论基础设计出 的。1 9 5 0 年，h a m m i n g 提出第一种线性分组码，即可以纠正出单个错误的汉明码。 1 9 6 0 年，b o s e 等人发现了构造简单并能纠正多个错误的b c h 码。同年，r e e d 和 1 1 绪论硕士论文 s o l o m o n 发现了多进制结构的r - s 码。而后，在1 9 6 2 年，g a l l a g e r 提出了采用迭代 的方法进行译码的l d p c 码【3 】。1 9 7 0 年，g o p p a 构造了一类新型的线性循环码g o p p a 码，它的一个子类的性能可以达到s h a n n o n 信道编码定理中好码的标准。 卷积码是另一类重要的信道编码，属于非分组码。由于它的编码器是有记忆性 的，从而增强了前后各组码元的相关性。卷积码最早由e l i a s 于1 9 5 5 年提出。1 9 6 3 年，f a n o 完善了序列解码算法，创立了f a n o 算法。1 9 6 6 年，z i g a n z i r o v 等人设计 出了堆栈算法。相比而言，在与分组码具有同样的信息传输速率和设备复杂度的条 件下，卷积码可以获得比分组码更好的性能，但是其分析设计的复杂性较高。伴随 译码方法的发展，特别是1 9 6 7 年提出的性能良好且译码复杂度适中的经典v i t e r b i 算法，更是推动了卷积码的大规模应用，并使其成为卷积码译码算法中最常用的一 种，极大地推进了信道编码的实用化。 然而，传统的纠错编码都不能算是真正实用的好码，因为其性能与实用性没能 够做到很好地统一。一直到1 9 9 3 年，c b e r r o u 等人提出t u r b o 码1 4 】，才使信道编码 理论的发展逐渐走向成熟。t u r b o 码将简单卷积码通过并行级联，使其能实现长码 的编码，同时由于它可以采用软输出迭代算法来逼近最大似然译码，其性能很接近 s h a n n o n 极限，实现起来复杂度也较低，可以称得上是一种实用好码。由于t u r b o 码第一次构造性地回答了s h a n n o n 之前提出的问题，再次引发研究人员对信道编码 理论研究的极大兴趣，在这之后，各种现代信道编码理论相继提出。1 9 9 6 年，m a c k a y 和n e a l 重新发现l d p c 码的优越性能1 5 j 。之后，研究人员用非规则l d p c 码仿真出 的门限值距离s h a n n o n 极限只有0 0 0 4 5 d b 6 。，性能超过了已知最好的t u r b o 码，证 明了l d p c 码是一种实用好码。正是t u r b o 码和l d p c 码的出现，揭开了信道编码 理论的新篇章。 1 3l d p c 码的性能特点及其发展应用 1 3 1l d p c 码的性能特点 l d p c ( l o w d e n s i t yp a r i t y c h e c k ) 码【3 1 ，即低密度奇偶校验码，是一种基于稀 疏奇偶校验矩阵的线性分组码。由于l d p c 码具备的特点和优良性能，使它成为编 码领域研究人员探索的一个新热点。 s h a n n o n 在信道编码理论中，证明了好码的存在，但没有给出具体的构造办法。 早期，性能优良的好码被认为是不可能构造出的。而现代研究人员证实这种好码是 可以实现的。l d p c 码就是这种可构造的好码。由于它具有强大的纠错能力和灵活 性，可以被用于几乎所有信道。 l d p c 码的表述简单，相比t u r b o 码而言更易实现，且可获得甚至超越t u r b o 4 硕士论文 l d p c 码编译码算法研究 码性能的系统。由于其奇偶校验矩阵的稀疏性，它在译码过程中复杂度很低，运算 量与码长呈线性关系，不会因为码长增大带来运算量的快速增加，克服了一般分组 码在长码长时译码过程中复杂度较大的缺点。同时，l d p c 码编码后可以克服突发 性的错误，对于较长编码的分组，可对距离很远的信息比特实现统一的校验，这样 就可以降低连续突发错误可能对译码产生的不良影响。和卷积码级联而成的t u r b o 码不同的是，l d p c 码采用迭代译码算法，使其可以并行地实现，达到高速译码， 能使系统具有较高的传输效率，利于硬件的实现。在l d p c 码的稀疏校验矩阵中， 由于非0 元素的随机排列，确保了它的随机性，也使得它相比t u r b o 码更加的实用 和灵活。除此以外，l d p c 码还具有较低的错误平层和相对容易的码率调整。它所 具备的这些优点使人们相信，对l d p c 码的研究必将会有非常广阔的应用价值。 1 3 2l d p c 码的发展和应用 l d p c 码早在1 9 6 2 年就由g a l l a g e r 提出，但是由于当时计算机水平的限制，硬 件实现困难，一直没有引起人们的重视。只有1 9 8 1 年t a n n e r 从图模型的角度进行 过研究。直到1 9 9 6 年，m a c k a y 和n e a l 重新发现l d p c 码与t u r b o 码相比有着同 样的优越性能【5 】，并且在长码长时的性能还超过了t u r b o 码，这才带动起人们对 l d p c 码的再次研究。1 9 9 7 年，l u b y 等人首先提出了非规则l d p c 码，并证明非规 则码比规则码具有更好的性能。此后，r i c h a r d s o n 和u r b a n k e 等人在l u b y 分析方法 的基础上，提出了用密度进化的方法来测算l d p c 码的性能，并设计出了接近 s h a n n o n 限的非规则码，推动了l d p c 码的进一步研究和应用。近年研究表明，在 非规则图上构造基于g f ( 2 ) 域的l d p c 码是最佳码，性能要好于t u r b o 码，在现 有的技术条件下也可以实现应用。l d p c 码正逐渐展现出它的优势，在实际系统中 得到应用，显示出它的社会价值。 美国f l a r i o nt e c h n o l o g y 公司将l d p c 码应用于f l a s h o f d m 移动无线芯片组中， 实现了可编程l d p c 译码器，增强了无线信道环境下的抵抗能力，使传输距离有了 很大提高，传输的数据速率可以达到3 m b i t s 。美国l u c e n tt e c h n o l o g i e s 公司将l d p c 码应用于光纤网络中，在1 0 g b i t s 速率运行时，使误码性能达到了1 0 - 1 5 。v o c a l t e c h n o l o g i e s 公司推出的用于w l a n 的l d p c t u r b o 不对称解决方案，上行链路采 用t u r b o 码，下行链路采用l d p c 码，可使移动终端的电池寿命延长4 倍，很好的 实现了节能。在2 0 0 4 年制定的数字卫星电视新标准d v b s 2 中，l d p c 码也得到了 很好的应用。若将l d p c 码用于压缩图像传输中，可对头语法和图像数据分辨采用 不同码率的l d p c 码进行编码，可以明显改善重建图像的质量。在目前应用较广泛 的数字水印技术中采用l d p c 码的编码技术，可以体现水印传输系统的可靠性。在 新一代移动通信中采用l d p c 码编码技术，可以实现较低的误码率，表现出更好的 l 绪论硕士论文 纠错性能，更好地适应新一代移动通信的需求。而l d p c 码也将有可能在第四代移 动通信系统中得到实际的应用。随着l d p c 码的进一步研究，其优越的性能必将使 其有更广阔的应用。 1 4论文的主要工作和内容安排 本文主要研究的是低密度奇偶校验( l d p c ) 码。介绍了l d p c 码的编译码算法， 并对l d p c 码的性能进行了仿真和分析。论文内容安排如下： 第一章，绪论，简述通信系统和信道编码的基本理论及其发展，并介绍l d p c 码的性能特点及其发展和应用。 第二章，简述线性分组码的概念，介绍l d p c 码的基本原理，包括定义、图模 型表示以及分类。 第三章，分析校验矩阵结构与l d p c 码性能的关系，介绍两大类校验矩阵构造 法。第一类随机构造法，主要讨论g a l l a g e r 构造法、m a c k a y 构造法、7 c 矩阵构造法、 q 矩阵构造法；第二类结构构造法，主要讨论有限几何构造法和组合构造法。并对 两大类构造法进行比较。 第四章，主要介绍l d p c 码的译码算法。重点介绍b p 译码算法，并对b p 译码算 法进行了性能分析。讨论b p 译码算法的四种简化算法和一种改进算法，并通过 m a t l a b 仿真进行详细的性能分析和比较。 第五章，主要介绍l d p c 码的编码算法。介绍全下三角形式的编码、类下三角 形式的编码以及兀矩阵和q 矩阵的编码三种算法及其复杂度分析。研究并详细分析一 种基于t a n n e r 图的适用于任意l d p c 码的线性复杂度的编码算法。 第六章，总结全文，讨论下一步工作和需要解决的问题。 6 硕士论文l d p c 码编译码算法研究 2l d p c 码概论 l d p c 码是线性分组码当中的一种，它能够在大量数据进行发送及存储信道中提供 接近于信道容量的性能，同时能够提供复杂度较低的可以实现的译码。要了解l d p c 码， 我们首先来看看线性分组码的介绍。 2 1线性分组码 信道编码时，在每个长度为k 位的信息序列之后，按照某种规则添加长度为，位 的校验位，共同组成总长度为门= k + ，位的码字。若校验位与其它组的信息位无关， 而只与本组的k 个信息位有关，在译码的时候也仅用到本组的码元，这种码就是分 组码，用( 挖，k ) 表示。 线性分组码是分组码当中最重要的一类，它的基本特征就是具有线性的结构， 也就是码中的信息位和校验位之间是线性的关系，因而可以利用线性空间的数学方 法进行分析，这种结构也使得它的编码器和译码器的实现更为简单。 对于二元线性空间，长度为，2 的码字可编成2 ”个码字的集合，构成g f ( 2 ) 域上 的刀维线性空间，类似地，k 个信息位可编成2 。个码字的集合，构成g f ( 2 ) 域上的k 维线性空间。线性分组编码通过在总共，z 维空间的2 ”个元素中选出2 个元素来建立 可用码字空间，并将其与信息位的k 维线性空间的2 。个元素一一对应。由于这里的 映射是两个线性空间的线性变换，所以称其线性分组码。倘若线性分组码的最小码 距为d ，那么可将线性分组码表示成( 珂，k ，d ) 。 ( n ，k ) 线性分组码的编码实际上就是通过建立一个线性方程组，由已知的k 个信 息码元求出未知的，z k 个校验码元。一般说来，线性分组码可以由其校验矩阵日或 者生成矩阵g 唯一地确定。若朋= f 嘲，m 2 ，m k ) 是k 维的信息序列，则对于任 意码字c 有：c = m g ，h c 7 = 0 。 码字经过编码后送入信道进行传输，在这过程中会受到各种噪声的干扰，因而 接收端要进行检错和纠错，也就是进行译码。对于线性分组码，其最大似然译码在 实际系统中是无法实现的，所以通常采用的是伴随式译码。 2 2l d p c 码的定义 l d p c 码【3 1 ，即低密度奇偶校验码，是一种线性分组码，它可以由校验矩阵唯 一地定义。它的校验矩阵日是稀疏矩阵，即每行或者每列当中只有非常少的非0 元 素，其余的大部分元素都是0 ，这也正是l d p c 码名称的来源。 在g f ( 2 ) 域上，码长力，信息位长度k 的l d p c 码可以表示成( ，z ，j i ) ，它的m x n 阶 7 2 l d p c 码概论硕士论文 校验矩阵日可按式( 2 1 ) 所示进行表示。 h = 啊。啊： 啊。 吃。坞：缟。 。： ( 2 1 ) 如式( 2 1 ) 所示日中，每行对应一个校验方程，每列对应码字的一位。倘若码 字为c ，那么其满足等式h c r = 0 ，也就是满足由校验矩阵日的行变量所确定的m 个 校验方程。在日中，每行和每列中非o 元素的数量分别称作行重和列重。由于日的 稀疏特性，因此它的行重和列重相比码长都很小。 倘若校验矩阵日的行变量线性独立，也就是当日满秩时，那么m = 刀一k ，此时 l d p c 码的码率为： r ：r - - ? ：l 一丝( 2 2 ) ，z疗 由于构造日的行变量经常是线性相关的，即不是满秩的，这时m i - - k ，码率 为： r n - m ：1 一里( 2 3 ) 刀刀 l d p c 码的校验矩阵日经常采用随机化方法进行构造，这种情况下，可以在编码 时利用高斯消元法将日表示成系统码的形式，即 h = j p 】 ( 2 4 ) 再将式( 2 4 ) 经过变换得到生成矩阵为： g = lp 7 ，i ( 2 5 ) lj 式( 2 4 ) 和( 2 5 ) 中，是k 阶单位矩阵，p 是g f ( 2 ) 域上k x ( n - k ) 阶矩阵。倘若 信息序列n l = ，z l ，m ：，m k ) ，此时由等式c = m g 就可以映射得出码字c 。我们 注意到，尽管日是稀疏矩阵，可是p 一般不是稀疏的，因此在编码的时候p 需要的 存储量比较大。 2 3l d p c 码的图模型表示 上节介绍了l d p c 码用校验矩阵表示的形式，此外，我们还可以用图示的方法 对l d p c 码进行有效的描述，这种图示方法能在l d p c 码的译码过程中发挥很重要 的作用。通常我们用稀疏的二分图即t a n n e r 副7 】来对其定义。这种无向图中分为两类 节点，即校验节点( c h e c kn o d e ) 和变量节点( v a r i a b l en o d e ) 或者比特节点( b i tn o d e ) ， 分别对应校验矩阵日的行和列，也就是说，l d p c 码的t a n n e r 图和校验矩阵日是等价 的，都是对应一个l d p c 码c 。 r 硕七论文 l d p c 码编译码算法研究 对于m 挖阶校验矩阵日所确定的l d p c 码的t a n n e r 图，其中包含两部分，即n 个变量节点以及m 个校验节点。通常变量节点和校验节点分别位列图的上、下两边。 由于同一个l d p c 码的t a n n e r 图与校验矩阵日是一一对应的，所以码字c 的，z 个码 元分别对应肛个变量节点，m 个校验方程分别对应m 个校验节点。在t a n n e r 图中， 倘若第f 个校验方程与第，个码元相关，那么图中就会出现一条连接第f 个校验节点 和第，个变量节点的边，其对应于日，就是非0 元素忽，对应的两类节点之间存在有 相连接的边，即玩= 1 。我们把边两侧所连接的节点称作相邻节点，和每一个节点相 连的边数称为节点的度。节点的度与校验矩阵日的行重和列重是一致的。这里我们 必须注意一点，只有不同类节点间的两个点才能够相互连接。当且仅当所有校验方 程都满足的时候，变量节点构成一个码字。图2 1 所示是1 0 个变量节点和5 个校验 节点构成的t a n n e r 图，图中每一个变量节点连接两条边，也就是度数都是2 ，每一 个校验节点连接四条边，也就是度数都是4 ，这种情况下，l d p c 码的行重、列重 都是常数，属于规则码。 b l b 2 b sb 4b 5b 6b 7 b 8 b 9 b l o c i 变量节点 节点 图2 1l o 个变量节点和5 个校验节点的规则l d p c 码t a n n e r 图 如图2 1 中粗线所示，若将节点包作为起点，依次经过节点c l 、6 4 和g 之后到达 的终点仍然是节点6 1 ，此时，其所历经的路线形成了一个环路。对于这样在t a n n e r 图中，某个节点既是起点又是终点，则其所历经的路线称作一个循环，历经的边数 称作循环长度，所有循环中，最短的一个循环长度称作图的g i r t h 。倘若l d p c 码的 t a n n e r 图中存在有循环时，从某一节点发出的信息历经一个循环长度的传递后又再 次回到该节点，这样就会造成统计时相关信息的叠加，对译码时的准确程度产生影 响。研究表明，l d p c 码最短循环的长度越大，码的性能越好。因此，我们希望l d p c 码的t a n n e r 图中，大循环多，小循环少，这样可以提高l d p c 码的整体性能，也是 设计l d p c 码的目标之一。 2 4l d p c 码的分类 l d p c 的分类方法有很多种，可以根据不同角度和不同特点分为以下几类8 1 。 9 2 l d p c 码概论 硕士论文 ( 1 ) 按照校验矩阵日中行重和列重的分布规律，是否为常数，可以分为规则 l d p c 码和非规则l d p c 码。 ( 2 ) 按照码元如何取值，可以分为二元l d p c 码( 二进制码) 和g 元l d p c 码 ( 高阶有限域g f ( q ) 码) ，q = 2 ”。 ( 3 ) 按照校验矩阵构造方法，可以分为随机l d p c 码、半随机l d p c 码和结 构l d p c 码。 ( 4 ) 按照码字的循环特性，可以分为循环l d p c 码、准循环l d p c 码和非循 环l d p c 码。 ( 5 ) 按照校验矩阵日中元素如何约束，可以分为l d p c 分组码、l d p c 卷积 码和广义l d p c 码。 ( 6 ) 按照码字的纠错方式，可以分为纠随机错误l d p c 码和纠突发错误l d p c 码。 2 5本章小结 本章主要介绍了l d p c 码的基本理论。首先概述了线性分组码的概念，在此基 础上阐述了l d p c 码的定义，介绍了l d p c 码的矩阵表示和t a n n e r 图模型表示，并 说明了t a n n e r 图中循环对译码性能的影响。最后简要介绍了l d p c 码的分类。 1 0 硕士论文l d p c 码编译码算法研究 3l d p c 码的构造 l d p c 码的构造实际上就是通过运用不同的方法构造出具有低密度特性的稀疏 校验矩阵日。用不同方法构造出的校验矩阵，由于日的结构各不相同，其编译码的 复杂度和性能有很大的差别。日的稀疏性和非0 元素排列的随机性直接影响着编码 和译码的复杂度以及l d p c 码的性能。因此，我们的目标就是希望可以构造出性能 优越，而编译码又简便的l d p c 码。一般来说，l d p c 码校验矩阵的构造方法主要 分为两大类：一类是随机构造法，即先对校验矩阵做一些属性的限制，再通过计算 机搜索的方法随机生成校验矩阵日。g a l l a g e r 、m a c k a y 等构造的校验矩阵都是采用 这种方法。另一类是结构构造法，即通过代数几何或者组合理论构造校验矩阵，使 其具有确定的结构。首先讨论l d p c 码校验矩阵结构与性能的关系。 3 1校验矩阵结构与性能的关系 l d p c 码构造校验矩阵h 的关键就是要构造出具有低密度特性的稀疏校验矩 阵，并且要尽量地避免短循环的出现。在2 3 节中，介绍了l d p c 码的图模型表示法， 知道了t a n n e r 图中如果存在有循环，就会影响l d p c 码的性能。t a n n e r 图中的循环可 以直接从校验矩阵日看出来，也就是在校验矩阵日中若干个非零元素用垂直或者水 平的箭头线能够连接起来所构成的闭合路径，同时必须保证水平线不在同一行，垂 直线不在同一列。如式( 3 1 ) 所示，在日的两行中同时存在有两个“1 处于相同 的两列中，构成了循环长度为4 的闭合路径，也就是形成了一个循环。 h = ； 1 ；个 1 ： ： 1 上i 1 ： ( 3 1 ) 当t a n n e r 图或者校验矩阵口中存在有循环，特别是循环长度较短时，节点的信 息经过迭代后又传回原节点，使得节点间传递外部信息时独立性减小，降低了抗干 扰的能力。也就是说，如果一个节点传出的消息是错误，则会产生错误的传播，致 使译码的速度减慢，无法收敛到最优的译码结果，甚至导致无法正确译码。因此， 在构造校验矩阵日时要使得最短循环的长度g i i r t h 尽量大，避免出现短循环，同时日 要足够的稀疏，也就是码长要足够的长。对于规贝u l d p c 码，当最短循环的长度g i i r t h g 给定的时候，g a l l a g e r 给出了码长，z 的一个下界p j ： 一 一 3l d p c 码的构造 硕士论文 g 2 4 m 时 船? + 1 s ，s = 1 ，s = j ( j 1 ) 卜2 ( j i 一1 ) 卜1 ，f 2 ( 3 2 ) l g = 4 m + 2 时胛? 厶， 厶= k ( j - 1 ) 1 ( k - 1 ) h 式中，k 为行重，为列重。按照式( 3 2 ) 的方法，对于行重k = 6 ，列重，= 4 ，最 短循环的长度g i r t h g = 1 2 的l d p c 码，其码长应为刀1 4 4 6 。不过，即使码长超过这 个下界，也不是一定存在最短循环长度g i r t h 达到要求的码。 我们以玎= 1 0 0 0 ，k = 6 ，= 4 ，码率为1 2 的规贝j j l d p c 码为例，比较在a w g n 信道下，b p s k 调制时，g i r t h ) 白4 的循环对l d p c 码译码性能的影响，如图3 1 所示。 宙 s n r ( d b ) 图3 1有无4 循环的( 1 0 0 0 ，4 ，6 ) l d p c 码性能比较 从图3 1 的仿真结果可以看出，倘若不存在g i r t h 为4 的循环，译码收敛速度较快， 误码率b e r 性能较好；而存在g i r t h s 4 的循环时，使得译码收敛的速度降低，b e r 的 性能下降。这是因为如果存在g i r t h 为4 的循环时，节点的信息仅仅经过两次迭代就又 回到原节点，降低了外部消息的独立性，使得译码的速度减慢甚至会影响译码的正 确性。因此，在构造校验矩阵时要尽可能消除g i r t h 为4 的循环。 3 2随机构造法 随机化构造的l d p c 码是基于一定的设计规则或者图结构，例如g i r t h 、节点的 度分配等，再由计算机搜索得到，其没有确定的数学结构。随机化构造的方法有很 多种，一般都是先随机构造小矩阵，再组合成大矩阵。下面将介绍几种l d p c 码的 随机构造方法。 硕士论文l d p c 码编译码算法研究 3 2 1 g a l l a g e r 构造法 g a l l a g e r 方法构造l d p c 码校验矩阵的基本思路是【9 】，通过某种确定的方式构造 一个规则子矩阵，再将该子矩阵经过某种变换生成一系列规则子矩阵，最后把这些 子矩阵拼接起来组成最终所需的大校验矩阵h 。g a l l a g e r 码的校验矩阵日具体构造 如下： ( 1 ) 将校验矩阵日按照行划分成日到日，共个子矩阵，如下式所示： h = 目 h 2 ： h j ( 3 3 ) 式( 3 3 ) 中，子矩阵日1 到日，都包含着相同的行数，并且每个子矩阵中的每- - n 只 含有一个“1 。 ( 2 ) 构造校验矩阵日的第一个子矩阵日。按照如下规律进行：目的第1 行中， 第1 到第k 个元素为“l ”，其余元素为“o ；第2 行中，第k + 1 到第2 七个元素为“1 ”， 其余元素为“o ”；以此类推，第所亍中，第“一1 ) k + 1 到第腩个元素为“l ，其余元 素为“0 。这样使得比特“1 ”在子矩阵日1 的行中按照降幂进行排列。 ( 3 ) 校验矩阵日中余下，一1 个子矩阵是对子矩阵甄的随机列变换。 按照以上g a l l a g e r 的方法经过三个步骤构造得到的l d p c 码，其校验矩阵h 的 行重和列重是固定的，每行中有七个“1 ，每列中有j f 个“l 。这样，就能够使日中 包含大量的“0 ”元素，满足稀疏矩阵的要求。另外，这种方法在构造日中余下歹一1 个子矩阵时，采用了随机编译码方式，在编码中引入了一定的随机性，符合s h a n n o n 信道编码定理引用的必要条件的要求。 由于在这种构造方法中，子矩阵日，到日，的列变换是随机的，为了确保日中没 有长度为4 的循环，g a l l a g e r 在论文中给出了一个限定条件，即当列重，3 ，行重k 大于列重，时，采用该方法构造的l d p c 码能够具有良好的距离特性。与此同时， 他也给出了几个结论：倘若列重，给定，在信噪比足够低并且码长足够长的情况下， 最佳译码器的错误概率随着码长的增大呈指数下降，而码间最小距离随码长增大而 线性增加。图3 2 是g a l l a g e r 构造的力= 2 0 ，k = 4 ，= 3 的l d p c 码的校验矩阵p j 。 从图中可以看出，下面两层的子矩阵由最上面一层子矩阵的随机列变换得到的。 3 l d p c 码的构造 硕士论文 llll0 000 0 oo 00 oo oo o0o 0 oo 01ll1o 0o 0o 00 o0 o00 000 00 000 l ll1o 00 o0 o0o 000oo 0o 00o00llll0 oo 0 0 oo 00 o0o0 00 o0 0o ollll l oo0 1 000lo00 lo00o 0oo olo 0olo0 0l000 00 0l00o 0 oloool0 0 o0 o0lo 0ol00 o oolo0 0o 0 olo0 01oo olo 000 00 00l0 00lo ool00ol l00 0ol0o0oo l 0o 0 0olo o 0l0 oo olo o ol00 00lo o0o oolo00 0lo o001o 0 oool0 00 0lo0 0o1oo 00l0 0l000 0o 0ol0 00 ol0 o0olo0o ol 图3 2 g a l l a g e r 构造的l d p c 码校验矩阵实例 3 2 2 m a c k a y 构造法 m a c k a y 构造l d p c 的方法是基于t a n n e r 图的思想，其方法的关键是要消除 t a n n e r 图中的短循环。通过前面的介绍我们知道，t a n n e r 图中倘若存在短循环会增 大误码率，从而影响l d p c 码的译码。m a c k a y 的构造方法就是要使校验矩阵日对 应的t a n n e r 图中存在的短循环数量尽可能的少，确保构造的口中，任意两列之间的 重叠数不大于l 。 对于m n 阶校验矩阵h ，m a c k a y 提出的四种构造方法依次为【l o 】： 构造1 ：基本构造方法。矩阵日由随机构造得到，确保h 每列中的“1 一样 多，也就是列重t 固定，同时，每行中的“1 要做到均匀分布，并且不存在长度为 4 的短循环，也就是任意两列元素的重叠数不大于l 。他在论文中证明了，t = 3 时c 的译码效果能够达到最好。如图3 3 所示。 构造2 ：校验矩阵h 中有叫2 列的列重t 为2 ，由两个( m 2 ) x ( m 2 ) 阶的单位矩 阵上下摆放，余下，z m 2 列按照构造l 的方法进行。同时仍要保证任意两列之间的 重叠不大于l 。如图3 4 所示。 构造3 、构造4 ：分别在构造1 和构造2 方法构造的校验矩阵日的基础上，删 除一些产生短循环的列，保证日所对应的t a n n e r 图中最短循环的长度大于某个值。 1 4 n 八 u 图3 3构造1 八 (3) u 图3 4构造2 硕士论文l d p c 码编译码算法研究 图3 3 中，构造1 的校验矩阵t = ，行重= ，码率为l 2 。图3 4 中，构造2 c