（信号与信息处理专业论文）ldpc码的设计与实现.pdf

摘要 低密度奇偶校验( l d p c ) 码由麻省理工学院的g a l l a g e r 博士发明于上世纪6 0 年代，和t u r b o 码一样，l d p c 码也具有近香农限的性能，并且其全并行迭代译码器 的复杂度和码长成线性关系，能获得数十倍于t u r b o 码的吞吐量。因此近年来，l d p c 码成为了信道编码领域的热点课题，在无线通信，深空通信，有线通信及存储工业等 各个领域都展开了应用。 本文首先简述了通信系统以及信道编码理论的基础知识，介绍了l d p c 码的定义。 接着介绍了几种编码方法，对其进行了复杂度分析和性能比较，并采用其中的一种q 矩阵编码对编码器做了硬件实现。然后重点介绍软判决译码算法，对其进行了仿真， 分析了影响译码性能的几个主要因素，并采用l o g _ b p 算法对译码器各个模块进行了 f p g a 实现。 关键词：l d p c 码，编码，软判决译码，f p g a 实现 a b s t r a c t l o w d e s i t yp a r i t y c h e c k ( l d p c ) c o d ew a si n v e n t e db yd r g a l l a g e ri nt h e y e a ro f1 9 6 2 ，b u ti t si m p o r t a n c ew a sn o tr e a l i z e du n t i it h ee n do ft h el a s t c e n t u r y i tc a na c h i e v ei n f o r m a t i o nr a t ev e r yc l o s et os h a n n o nl i m i t 。w i t h ad e c o d e rw h i c hi so fl i n e a rt i m ec o m p l e x i t yv e r s u sb l o c kl e n g t ha n dc a n s u p p o r tt h et h r o u g h p u tt e n st i m e so ft u r b oc o d ed e c o d e r w i t ht h es u c c e s s ， i nt h ef i e l d so fs p a c ec o m m u n i c a t i o n ，f i b e rc o m m u n i c a t i o na n ds t o r a g e i n d u s t r y ，l d p ci sb e c o m i n gap o w e r f u lc o m p e t i t o r i nt h i st h e s i s ，a tf i r s t ，t h eb a s i so fc o m m u n i c a t i o na n dc h a n n e lc o d i n g t h e o r yi si n t r o d u c e db r i e f l y a f t e rt h ed e f i n i t i o no fl d p cc o d e ，s e v e r a l m e t h o d so fe n c o d i n ga l g o r i t h m sa n dt h e i rp e r f o r m a n c e sa r es t u d i e d a f t e rt h e a n a l y s i so ft h e s em e t h o d s ，t h ea l g o r i t h mo fq _ m a t r i xe n c o d i n gi ss e l e c t e dt o i m p l e m e n tt h ee n c o d e rw i t hf p g at e c h n i q u e t h e nw ep r e s e n tt h es o f t d e c i s i o n d e c o d i n ga l g o r i t h m se m p h a t i c a l l y ，a n du s i n gm a t l a bt oa n a l y z es e v e r a lm a i n f a c t o r sw h i c ha 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 e a tl a s t w ec h o o s el o g _ b p a l g o r i t h mt oi m p l e m e n tt h ep a r a l l e ld e c o d e rw i t hf p g at e c h n i q u e k e yw o r d s ：l d p cc o d ee n c o d i n g s o f t d e c i s i o nd e c o d i n g f p g ai m p l e m e n t a t i o n 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：囱回垫捌年月眵日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名鱼l 虱茧如_ 6 月涉日 硕士论文l d p c 码的设计与实现 1绪论 1 1 数字通信与纠错编码 1 9 4 8 年，香农( c e s h a n n o n ) 的发现宣告了现代通信理论的诞生“1 。香农指出所 有的通信系统，都可以归结为图1 1 所示的模型。 图1 1 香农的通信模型 信源产生待传送的信息，在数字通信系统中，我们可以抽象的认为信源输出 的是表征信息的二进制比特流。不失一般性，我们可以认为信源发送0 的概 率和发送1 的概率相等。 发射机将信息转换为适合的信号形式以适合信道传输。 信道是对传送信号的物理介质的抽象。 接收机从信道接收信号并对信息进行重建。 信宿将接收到的信息恢复。 从信道引入的噪声对接收机重建信息带来了很大麻烦：因为噪声的存在，重建的 信息并不是信源信息的复制版本，而是引入了传输差错，这显然是我们所不希望的。 通信的目的是要把对方不知道的消息及时可靠地( 有时还需秘密地) 传送给对方， 因此，要求一个通信系统传输消息必须可靠与快速，在数字通信系统中可靠与快速往 往是一对矛盾。若要求快速，则必然使每个数据码元所占的时间缩短、波形变窄、能 量减少，从而收到干扰后发生错误的可能性增加，传送信息的可靠性减低。若要求可 靠，则使得传送消息的速率变慢。因此如何较合理的解决可靠性与速度这一对矛盾， 是正确设计一个通信的关键问题之一。通信理论本身( 包括纠错码) 也正是在解决这对 矛盾中不断发展起来的。 数字通信系统中，为了减小或消除传输差错而采取的差错控制方式大致可以分为 以下几个类型3 ： 1 重传反馈方式( a r 0 ) 。a r q 方式的系统如图1 2 所示。在发射端发送具有检 硕士论文 l d p c 码的设计与实现 错能力的码，接收端的译码器检测接收到的码序列是否有错，并将判断结果通过反向 信道告诉发射端。发射端根据这个判断结果，把接收端认为有错误的消息再次发送， 直到接收端认为接收正确为止。 图1 2 重传反馈通信系统 a r q 方式的编码器和译码器设计比较简单，同时，整个系统的纠错能力很强，能 够使系统获得很低的误码率：由于检错码的检错能力一般与信道的变化情况没有关 系，所以这种系统适应性很强。但是，系统需要发射端和接收端密切协调配合因此 控制比较复杂：在信道恶劣的环境中，由于系统可能经常处于重发的阶段，因此传送 的连贯性和实时性很差，所以一般只适合于非实时的数据传输业务。 2 前向纠错方式( f e c ) 。前向纠错方式的系统如图l3 所示。发送端发送具有 纠错能力的码，接收端收到码序列后，利用纠错译码器，不仅能发现错误，还能够自 动的纠正错误。其中，编码器通过增加冗余信息，将长度为k 的信源序列k 映射为长 度为n 的码字c ，送入编码信道。编码信道将噪声图案e 迭加到发送码字上，使得接 收端接收到序列r 。接收端通过对r 译码得到重建后的码字c 和重建后的消息序列k ，。 我们称这种纠错码是( n ，k ) 纠错码，并定义其码率为k n 。在一次通信中，总的差错 比特数和总的传送比特数之比称为误码率( b e n ) 。显然，误码率是衡量纠错码的一个 重要指标。误码率这个参数往往需要通过蒙特卡罗仿真来得到，为了使结果更加靠近 真实情况，需要很大的仿真点数。 图1 3 前向纠错通信系统 2 硕士论文l d p c 码的设计与实现 前向纠错方式的优点在于实时性好，控制电路较重传反馈方式简单，因此能够适 用于多种通信业务。其缺点在于编译码器比较复杂，而且受信道环境影响很大。随着 编码理论的发展和硬件水平的提高，性能强大且可行性较好的纠错码编译码器已经在 当前的数字通信系统中得到了广泛应用。 3 混合纠错方式( h e c ) 。混合纠错方式是指发送的码同时具有检错和纠错的能 力。因此获得接收序列后，首先检查错误情况，如果在纠错码的纠错能力内，进行纠 错。如果不在纠错码的纠错能力内，则采用重传反馈方式。因此，这种纠错方式是重 传反馈方式和前向纠错方式的结合与折中，在实际通信系统中，也有着很广泛的应用。 总而言之，差错控制是为了解决通信的可靠性问题的。如果对于一个通信系统， 在某种通信环境中的差错概率为零或者无限的趋近于零，我们就说在这种环境中该通 信系统是可靠的。接下来，本文将把讨论范围局限于前向纠错方式。前向纠错方式中， 纠错码的选择及其编码、译码器的设计是决定纠错能力的最重要的因素，这也是信道 编码研究的主要内容。 纠错码需要加入冗余信息，利用发送信息的相关性来实现检错和纠错的功能，因 此始终有码率r l ，也就意味着信息的传输速率降低了。于是，提出了两个新的问题： 1 在保证通信的可靠性下，在某个确定的发射功率和信道环境下，能够达到的 最大有效传输速率是多少? 从另外一个等效的角度，这个问题也可以这样描述：在保证 通信的可靠性下，在某个确定的信道环境和信息传输速度下，至少需要的发射功率是 多少? 2 应如何设计码字和编、译码器才能保证通信的可靠性，并且达到最大传输速 率。 1 2 香农信道编码定理： 1 2 1 最大似然译码 在己知接收值r 的条件下找出所有的发送码字c 中可能性最大的发送码字作为译 码估值c ，即是说： c = m a x e ( c , i 胄) ( 1 1 ) 这种译码方法叫做最大后验概率译码嘲，它是一种通过经验与归纳，由接收值推 测发送码字的方法，是我们认为的最优译码算法。但在实际译码时，后验概率的定量 确定是很困难的。 在已知r 的条件下使似然概率最大的译码算法叫最大似然译码( m l d ) ，即是： 硕士论文 l d p c 码的设计与实现 c = m 驭联盖 q ) ( 1 2 ) 在每个码字等概发送的条件下，根据b a y e s 准则，我们很容易知道，最大似然译 码等价于最大后验概率译码，因此也是最优的。 1 2 2 信道编码定理 1 每个信道具有确定的信道容量c 。一。，对于任何小于c 。的传输速率r ，存在 码长为n 的码。若采用最大似然译码，则随着码长n 的增加，其译码错误概率p ，可 以任意的小。 2 ( 逆定理) 对于任何大于k 。，的传输速率r ，不论使用何种编译码方法，错 误概率始终会大于某个常数。 在高斯信道环境下，对某个码长为n ，信息位长度为k 的码，其码率为r = k n 。 假设传送一个n 长码字所用的时间为f 秒，在带宽为b 的情况下，根据n y q u i s t 定理， 至少有： 2 b = 旦( 1 3 ) 而传输速率r = k r ( b i t s s ) ，所以r = k r = 2 b r 。根据信道编码定理和高斯信道 容量，有： 2 b r l d p c 码的译码算法，是一种基于稀疏矩阵的并行迭代译码算法，运算量要低 于t u r b o 码译码算法，并且由于结构并行的特点，在硬件实现上比较容易。 因此在大容量通信应用中，l d p c 码更具有优势。 l d p c 码的码率可以任意构造，有更大的灵活性。而t u r b o 码只能通过打孔来 达到高码率，这样打孔图案的选择就需要十分慎重的考虑，否则会造成性能 上较大的损失。 l d p c 码具有更低的错误平层，可以应用于有线通信、深空通信以及磁盘存储 工业等对误码率要求更加苛刻的场合。而t u r b o 码的错误平层在1 0 1 量级 上，应用于类似场合中，一般需要和外码级联才能达到要求。 l d p c 码是上个世纪六十年代发明的，现在，在理论和概念上不再有什么秘密， 因此在知识产权和专利上不再有麻烦。这一点给进入通信领域较晚的国家和 公司，提供了一个很好的发展机会。 而l d p c 码的劣势在于： 硬件资源需求比较大。全并行的译码结构对计算单元和存储单元的需求都很 大。 编码比较复杂，更好的编码算法还有待研究。同时，由于需要在码长比较长 的情况才能充分体现性能上的优势，所以编码时延也比较大。 相对而言出现比较晚，工业界支持还不够。 1 5 本文主要研究工作和内容安捧 本文主要讨论了目前信道编码领域的热点课题一一低密度奇偶校验( l d p c ) 码。 分析了l d p c 码的编译码算法以及性能，并介绍了编，译码器的硬件实现方法。本文 的内容安排如下： 第一章绪论。 第二章主要介绍l d p c 码的基本原理，定义及其几种描述方法和分类。 第三章主要讨论了l d p c 码的几种构造方法：g a l l a g e r 随机置换构造法，准循环 的代数构造法，以及基于q 矩阵的伪随机构造法。对三种方法的复杂度进行了分析， 并对伪随机构造法中获得q 矩阵的皇后算法进行了详细描述。 8 硕士论文 l d p c 码的设计与实现 第四章主要讨论l d p c 码的编码。比较了传统编码算法和基于q 矩阵的编码算法 的复杂度。并利用第二种算法对编码器进行了硬件实现，详细介绍了编码器各模块的 具体实现方法。 第五章讨论了译码算法。主要介绍了肝算法集中的b p 算法和l o g _ b p 算法，并 对l o g b p 算法的误码率性能进行了分析。用m a t l a b 仿真了几种因素：码长，码率， 信噪比，迭代次数对译码性能的影响。 第六章主要讨论了译码器的硬件实现。详细讨论了各个模块的实现结构，并行译 码器的整体结构，并给出了译码器的时序仿真图。 第七章总结全文，讨论下一步工作和需要解决的问题。 9 硕士论文 l d p c 码的设计与实现 2 l d p c 码的简介 任何一个( n ，k ) 分组码，如果其信息元与监督元之间的关系是线性的，即能用一 个线性方程来描述的，就称为线性分组码。 低密度奇偶校验码”1 ( l d p c 码) 本质上是一种线形分组码，它通过一个生成矩阵 g 将信息序列映射成发送序列，也就是码字序列。对于生成矩阵g ，完全等效地存在 一个奇偶校验矩阵h ，所有的码字序列c 构成了h 的零空间，即h c t = o 。 l d p c 码的奇偶校验矩阵h 是一个稀疏矩阵，相对于行与列的长度，校验矩阵每 行、列中非零元素的数目( 我们习惯称作行重、列重) 非常小，这也是l d p c 码之所以 称为低密度码的原因。由于校验矩阵h 的稀疏性以及构造时所使用的不同规则，使得 不同l d p c 码的编码二分图( t a n n e r 图) 具有不同的闭合环路分布。而二分图中闭合环 路是影响l d p c 码性能的重要因素，它使得l d p c 码在类似可信度传播( b e l i e f p r o p a g a t i o n ) 算法的一类迭代译码算法下，表现出完全不同的译码性能。 当h 的行重和列重保持不变或尽可能的保持均匀时，我们称这样的l d p c 码为正 则l d p c 码，反之如果列、行重变化差异较大时，称为非正则的l d p c 码。研究结果表 明正确设计的非正则l d p c 码的性能要优于正则l d p c 。根据校验矩阵h 中的元素是属 于g f ( 2 ) 还是g f ( q ) ( q = 2 ) ，我们还可以将l d p c 码分为二元域或多元域的l d p c 码。 研究表明多元域l d p c 码的性能要比二元域的好。 2 1l d p c 码的因子图 2 1 。1l d p c 码的因子图表示 为了分析方便，我们一般用因子图来表示一个l d p c 码m 1 。因子图上所有的代码 点可叭分成互不相关的两类，我们称之为信息点和校验点。因子图上的边以一定的规 律把它们连接起来，但是同一类中的代码点不能用边连接起来。事实上因子图与用来 定义码字的奇偶校验矩阵h 是相对应的，即因子图上的变量节点对应矩阵h 的列向 量，校验节点对应因子图上的行向量，而矩阵中非零元素就对应因子图上的每一条边。 在定义新的码字时，每一次构造的码字在二进制矢量域中定义为x = ( x i ，x z , ，矗) 。当 且仅当方程h x r _ 0 时为一码字，也就是说，当且仅当每一个校验点的相邻变量节点的 异或值为0 时，对应的二进制矢量x = ( x 。，x ：，x 。) 才是一个码字。假设因子图上每 一个变量节点的度数是y ，每一个校验点的度数是p ，节点的次数为与该节点相联边 的个数。如果y ，p 相对于码字总长n 来说很小，则该因子图对应的奇偶校验矩阵是 稀疏矩阵。 1 0 硕士论文l d p c 码的设计与实现 一个码长n = 6 ，码率r = i 3 ， h = 1010 01l 010 0111 0 01110 11010 0 其对应的因子图如图2 1 所示 校验节点 变量节点 图2 1l d p c 码的因子图表示 2 1 2 因子图中短环对码性能的影响 ( 2 1 ) 如图2 2 所示，是一个含有短环的因子图片段，可以看出，信息比特x 。，x ：和校 验比特c 。，c ：构成了一个长度为4 的环( 用粗线表示) 。如果图中3 个变量节点都发生 了差错，五个相关的校验节点中只有一个能够检测到发生了错误。在这种情况下，要 从一个检测到错误的校验节点来纠正三个错误是不可能的，校验约束c 。和c 2 对于 ( x 。，x ：) 是( 0 ，0 ) 或者( 1 ，1 ) 是无法区分的。从而导致译码算法失效 校验节点 变量节点 。 c 1c 2c 3 c 4 x 1 x 2x 3 】( 4x 5 ) ( 6 图2 2 具有长度为4 的短环的因子图片段 根据图2 3 所示某校验矩阵的因子片断，变量比特x 。，】( 3 ，k 和校验比特c - ，c 2 ，c “ 构成了一个长度为6 的环( 用粗线表示) 。这时编码的最小距离可能为4 ，如果在某个 码字中这3 个变量节点的取值为6 1 6 3 6 4 ，那么在其他变量节点保持不变的情况下，这 3 个节点全部取反变为瓦丢万，所有的校验约束仍然得到满足，因此也是一个码字， l l 硕士论文l d p c 码的设计与实现 这两个码字的距离为3 ，这么小的码距会使编码性能恶化。因为最小码距不大于4 的 码的纠错能力小于2 ，即该码无法纠正所有差错个数大于等于2 的差错事件。这是非 常坏的情况，应当尽量避免，所以短环的存在降低了校验约束正常检错和纠错的能力。 校验节点 变量节点 c lc 2c 3 c 4 x lx 2 x 3x 4x 5 x 6 图2 3 具有长度为6 的短环的因子图片段 l d p c 码的信息传递( m e s s a g ep a s s i n g ) 译码算法是假定变量节点是相互独立，短 环的存在必然破坏了独立性的假设，使得译码性能明显下降。事实上，环4 、环6 等 短环的存在使得变量节点在迭代译码的过程中频繁给自己传递正反馈信息，这对于迭 代译码而言是不希望出现的。我们知道，t u r b o 码也是迭代译码的，它正是使用交织 器来减少这种正反馈效应的。对于没有环( c y c l ef r e e ) 的t a n n e r 图，信息传递算法 会导致最优解码，而环的存在使得信息传递( m e s s a g ep a s s i n g ) 算法是一种次优 ( s u b o p t i m a l i t y ) 的迭代译码算法，事实上最短环长度( g i r t h ) 越长，信息传递算法 越接近最优算法。所以二分图中环的存在是我们对迭代译码过程进行准确概率分析的 一个障碍，并且图中的环越短，分析过程也将越早被中断。 2 2 正则与非正则l d p c 码 在l d p c 码的校验矩阵中，如果行列重量固定为( p ，y ) ，即每个校验节点有p 个 变量节点参与校验，每个变量节点参与y 个校验节点，我们称之为正则l d p c 码。 g a l l a g e r 最初提出的g a l l a g e r 码就具有这种性质。从编码二分图的角度来看，这种 l d p c 码的变量节点度数全部为y ，而校验节点的度数都为p 。我们还可以适当放宽上 述正则l d p c 码的条件，行列重量的均值可以不是一个整数，但行列重量尽量服从均 匀分布。另外为了保证l d p c 码的二分图上不存在长度为4 的圈。我们通常要求行与 行以及列与列之间的交叠部分重量不超过1 ，所谓交叠部分即任意两列或两行的相同 部分。我们可以将正则l d p c 码校验矩阵h 的特征概括如下： 1 h 的每行行重固定为p ，每列列重固定为y 。 2 任意两行( 列) 之间同为l 的列( 行) 数( 称为重叠数) 不超过l ，即h 矩 阵中不含四角为l 的小方阵，也即无4 线循环。 硕士论文l d p c 码的设计与实现 3 行重p 和列重y 相对于h 的行数m 、列数n 很小，h 是个稀疏矩阵。 在正则l d p c 码的校验矩阵中。行重和列重的均值保持不变，所以校验矩阵中1 的个数随着码长的增加而线性增长，整个校验矩阵的元素个数则成平方增长。当码长 达到一定长度时，校验矩阵h 是非常稀疏的低密度矩阵。对于正则的l d p c 码，m a c k a y 在“”中给出了以下两个结论： 1 对于任意给定列重大于3 的l d p c 码，存在某个小于信道传输容量且大于零 的速率r ，当码长足够长时，可以实现以小于r 且不为零的速率无差错的传 输。也就是说任意给定一个不为零的传输速率r ，存在一个小于相应香农限 的噪声门限，当信道噪声低于该门限且码长足够长的时候，可以实现以r 速 率无差错的传输。 2 当l d p c 码的校验矩阵h 的列重y 不固定，而是根据信道特性和传输速率来 确定时，则一定可以找到一个最佳码，实现在任意小于信道传输容量的速率 下无差错的传输。 对于l d p c 码的每个变量节点来说，当它参与的校验式越多，即度数y 越大，则 它可以从更多的校验节点获取信息，也就可以更加准确的判断出它的正确值。对于h 的每个校验节点来说，当它涉及的变量节点越少，即度数p 越小，则它可以更准确的 估计相关变量节点的状态。这种情况对于正则l d p c 码来说是一对不可克服的矛盾， 于是l u b y ，m i t z e m n a c h e r 等人就引入了非正则l d p c 码的概念。 在非正则l d p c 码的编码二分图中，两个集合内部的节点度数不再保持相同，印 每个变量节点参与的校验式数目或每个校验式中含有的变量节点数目不再保持均匀， 而是有意设置部分突出的变量节点和校验节点。在译码过程中，那些参与较多校验式 的变量节点迅速得到它们的正确译码信息，这样它们就可以给相邻的校验节点更加有 效的概率信息，而这些校验节点又可以给与它们相邻的次数少的变量节点更多的信 息。整个译码的过程呈现出一种波状效应，次数越高的变量节点首先获得正确信息， 然后是次数较低的节点，然后依次往下，直到次数最低的变量节点。正是这种波状效 应，使得非正则l d p c 码获得比正则l d p c 更好的译码性能。 2 3 二元域与多元域l d p c 码 前面对l d p c 码的定义都是在二元域基础上的，m a c k a y 在“”中对上述二元域的 l d p c 码又进行了推广。如果定义中的域不限于二元域就可以得到多元域g f ( q ) 上的 l d p c 码。多元域上的l d p c 码具有较二进制l d p c 码更好的性能，而且实践表明在越 大的域上构造的l d p c 码，译码性能就越好，比如在g f ( 1 6 ) 上构造的正则码性能已经 和t u r b o 码相差无几。多元域l d p c 码之所以拥有如此优异的性能，是因为它有比二 硕士论文l d p c 码的设计与实现 元域l d p c 码更重的列重，同时还有和二元域l d p c 码相似的二分图结构。 假设在域g f ( 2 ) 和域g f ( q ) ( q = 2 9 ) 上构造的l d p c 码所对应的校验矩阵分别是h 。 和h q 。h 2 中的元素是0 或l ，而h 。是由元素0 ，1 ，q 一1 构成，h q 中的每个元素都是 h 2 中p 个元素的合成。如果设域g f ( q ) ( q = 2 ) 上的一个值a 与一个l * p 的二进制向量 相关联，那么把这个向量代入心中，就可以得到h q 的二进制表示。对于二进制l d p c 码来说，如果它的校验矩阵h 的列重量足够大，那么它可以任意地接近香农限，但是 如果增加列重量会使得二分图中节点之间短圈的数h 急剧增加从而使b p 算法的性能 下降。而在g f ( q ) 域上构造的l d p c 可以解决这个矛盾，它的检验矩阵h 。可以增加与 之对应的二进制校验矩阵h ：中列的平均重量，且它的二分图结构并没有改变，不会 造成节点之间短圈数目的增加，从而使得译码性能得到显著的提高。这种多元域上的 编码构造会增加译码复杂度，但是相对于译码性能的提高来说这种增加是值得的。 2 4 本章小结 本章主要介绍了l d p c 码的定义及因子图表示。阐述了l d p c 码的一些基本特性， 如行重，列重，二分图中的环对l d p c 码性能的影响。描述了正则码的特点，非正则 码的特点以及二者相比较后者的优势。最后简介了多元域l d p c 码。 硕士论文 l d p c 码的设计与实现 3 l d p c 码的构造 g a l l a g e r 于1 9 6 3 年提出的l d p c 码“，揭示出了一种新的具有低密度校验矩阵的 分组编码结构，它利用校验矩阵的稀疏性解决长码的译码问题，可以在线性时间内译 码，同时又近似于香农提出的随机编码，获得了优秀的编码性能。 对l d p c 码来说，不考虑码长和次数分布的情况下，校验矩阵的结构就成了影响 其性能的重要因素，反映在二分图上对编码性能有重要影响的就是图中环的长度分 布，需要采用一定的方法对校验矩阵进行构造，获得好的编码。 目前l d p c 码的构造方法主要可以分为两大类：随机或伪随机构造方法和代数的 构造方法。 随机或伪随机的构造方法主要考虑的是码的性能，在码长比较长( 接近或超过 1 0 0 0 0 ) 时，性能非常接近香农限。代数的构造方法通常考虑的是降低编译码的复杂 度，在码长比较短的时候更有优势。 3 1 g a l l a g e rl d p c 码 用和乘积算法( s p a ：s u m p r o d u c ta l g o r i t h m ) 进行译码取得最大后验概率的译码 性能的条件是二分图中没有小的环，即g i r t h 为4 的环，无4 环的条件反映n - - - 分图 中就是任意两行中1 的交迭数目不超过1 个。无4 环的二元高比特率l d p c 码可以通 过随机生成行构成，一般来说，这种方法不能生成固定行重量的矩阵。 g a l l a g e r 提出了一种替代的方法：采用随机置换的方法来构造规则l d p c 码。对 于码长为n 的( j ，k ) 正则码，将蜘n 矩阵h 通过j 个大小为( m j ) 州的子矩阵构成， 每个子矩阵本身也是l d p c 矩阵，列重量为1 ，行重量为k ，第一个子矩阵为阶梯型， 即第i 行的k 个1 的列号是从( i 一1 ) 术k + 1 到i * k ，而其他子矩阵都是第一个子矩阵 的随机列置换，这样每个子矩阵每行都有k 个1 ，每列都有1 个l 。这种构造方法要 求m 必须是j 的整数倍。 。 g a l l a g e r 曾给出了一个码长为2 0 的规则( 3 ，4 ) l d p c 码的校验矩阵，如图3 1 所示。图中的第一个子矩阵就是一个阶梯型矩阵，而第2 个和第3 个矩阵都是第一个 子矩阵的列置换。 硕士论文l d p c 码的设计与实现 图3 1 ( 2 0 ，3 ，4 ) l d p c 码的校验矩阵 g m l a g e r 同时证明了随机置换得到的g a l l a g e rl d p c 码的最小汉明距离能够随 着码长的增加而线性增加，而且在对称无记忆信道中，采用最大似然译码时，其误码 率随着码长的增加而呈指数形式下降，这说明随机置换得到的g a l l a g e rl d p c 码是一 类相当好的码。 但是，g a l l a g e r 在构造l d p c 码时采用的是随机置换，这就给实现带来了麻烦， 就需要大量的存储单元来存储校验矩阵中这些l 的位置。 3 2 确定性结构的l d p c 码 确定性结构的l d p c 码也称为准循环l d p c 码。相对于随机结构的矩阵是很容易获 得的确定性结构的矩阵，这种矩阵可以通过更少的参数来定义l d p c 码。确定性结构 的l d p c 码的构造方法基于“阵列码”( a r r a yc o d e ) 。阵列码是用来检测和纠正突发 差错的二维码。 通过三个参数定义l d p c 码。一个基本参数p 和两个整数j 和k 。令h 为j p * k p 的矩阵，定义为： o 0 o o l 。0 o o l 西o o o 1 o o 0 o l 仃o 0 1 o o 0 o o o o o o 1 o o l o o i o o o o o o 0 o l d 1 o o o 玎o o l o o o o l o u 0 0 o 1 d l o o o o o 0 l 0 d o o 1 0 西o o o 1 o o o l o 盯o 1 o o o o o 1 o o o o l o t 0 o o o o o l o o o o 1 o 0 玎o o o l r o o o o o 0 1 0 o o o 0 1 o o l o o o o o 1 0 o 玎1 o o 0 西o o o l o 0 l o o t o 0 o o 可o o l o o l o 0 o u o 0 o 1 u o l o 0 o 1 o o 0 仃o 1 0 o 一0 1 0 o 0 o l o o o o l o o o i o o o o o l o o o r o o o o d 0 o o 1 1 o o o o 盯o o 1 o o 0 0 1 o l o o o o o o l o o o o 1 o o l o 0 o o 仃1 o o o 一0 1 0 o o|二|二 一 = 王h 硕士论文l d p c 码的设计与实现 h _ i i肛2 i ： l iib j 2 b 2 ，k i i b j k l - j ( 3 1 ) 其中这里的i 是p * p 的单位阵，。b “是i 。的左循环移位矿。或右循环移位矿“的 置换矩阵。显然，h 矩阵中1 的分布就只与循环位数a l “有关。对l d p c 码的分析就可 以转换为对矿。的分析。 将各小矩阵的循环移动位数写成一个矩阵为： 卜。一o a ：i o a 2 2a 2 ，3 a 2 k l l ： ：i l ：) 二z 二一 二一 。， 矿。取值为1 到k 一1 之间的随机整数。如当a n - 1 ，p = 4 ，则采用左循环移位时 b “4 = 采用右循环移位时 b ”，= o o 10 ol o o ol o 0 00 1o 0l o o 0 o lo o o 1o o1 0 0 ( 3 3 ) ( 3 4 ) 上面的校验矩阵提供了一个可以用于s p a 译码的稀疏矩阵。而且，这个校验矩阵 结构上没有四线循环。当k p 时，相当于截短阵列码。参数j 和k 分别作为l d p c 码 h 矩阵的列重量和行重量。这种编码方式可以应用于a d s l 的传输。 3 3q 矩阵构造的l d p c 码 3 3 1q 矩阵的定义 若n * r l 阶非对角单位方阵( n 为任意正整数) 的每行、每列及每对角线均只有一 个1 ，则该矩阵称为q 矩阵。 1 7 3 ，v 胪；刖 硕士论文l d p c 码的设计与实现 q 矩阵的结构对l d p c 码的奇偶校验矩阵的构成具有特殊意义，如果将多个不同 布局的q 矩阵按一定规则排列，这样构成的奇偶校验矩阵可使任两列的重叠数不超过 l 的约束条件得到满足。或者说，矩阵可以从软件和硬件两个方面实现l d p c 码的奇 偶校验矩阵的结构，这样构成的奇偶校验矩阵中不存在4 线循环。采用矩阵的另一个 好处是可以利用“皇后算法”( “q u e e np r o b l e m ”q 矩阵由此得名) 来寻找随机矩阵。 3 3 2 q 矩阵的快速搜索算法 “皇后问题”是这样描述的：由n 个方块排成n 行n 列的正方形称为“n 元棋盘”。 若任意两个皇后位于n 元棋盘上同一行、同一列或同一对角线，则称它们为互相攻击。 要求找出使n 元棋盘上的n 个皇后互不攻击的布局。 皇后算法与寻找每行、每列和每个对角上只有一个1 的q 矩阵的算法是等效的。 设皇后的编号为1 ，2 ，n ，且第i 个皇后位于n 元棋盘的第i 行上( i = 1 ，2 ，n ) 。 显然，第i 个皇后与第j 个皇后互相攻击的条件为： l q ( 0 一q o ) l i f 一卅= 0 ( 在同一对角线上) ( 3 5 ) g ( f ) 一q ( j ) = 0 ( 在同一列上) ( 3 6 ) 其中q ( i ) 表示第i 个皇后在n 元棋盘上的列号。 具体的搜索算法步骤如下： 步骤1 初始化：对每列的皇后q u e e n 。，q u e e n ：，