（信号与信息处理专业论文）ldpc码的理论研究与编码优化.pdf

中文摘要 中文摘要 摘要：低密度奇偶校验( l o wd e n s i t yp a r i t yc h e c k ，l d p c ) 码以具有非常逼近容 量限的优异性能在通信编码领域引起了广泛关注，并且已被应用于各个方面，包 括太空及卫星通信，无线通信，磁记录和网络包传输等。本文研究的主要目的是 实现u ) p c 码的优化设计。 本论文的主要工作为： 一、在分析l d p c 码的t a n n e r 图中的环在校验矩阵中的形状的基础上，提出 了两种环数检验算法，1 、提出了基于逐点搜寻法的短环( 四环，六环) 检验算法。 在分析l d p c 码在t a n n e r 图中的环在校验矩阵中的形状的基础上，根据组成短环 ( 四环，六环) 的“1 ”之间的相对位置关系，在校验矩阵中依次搜寻符合上述关 系的点的组合从而对校验矩阵中的短环( 四环，六环) 数进行统计。2 、提出了基 于排列组合法的短环( 四环，六环，八环，十环) 检验算法。该方法首先对校验 矩阵中一定数且的行组合中的短环( 四环，六环，八环，十环) 数进行统计，然 后将所有行组合中的环数相加即可得到校验矩阵中的环数。环数检验算法除了可 以对已知校验矩阵中的环数进行检验外，还可以用于设计性能优异的大围数准循 环( q u a s i - c y c l i c ，q c ) 码。 二、本文还提出了一种性能优异的l d p c 码的设计方法，该方法利用三个不 同的子矩阵分别进行文中提到的移位运算，然后组合成为基本矩阵，基本矩阵可 以避免短环( 四环，六环) 的存在，最后将基本矩阵用单位矩阵及其移位矩阵扩 展即可生成校验矩阵。利用本文设计出的校验矩阵所对应得生成矩阵对随机信息 进行编码，a w g n 信道下的仿真结果表明具有逼近随机l d p c 码的误码率性能。 关键词：通信；低密度奇偶校验码；校验矩阵；环：检验算法；分支法； 准循环码 北京交通大学硕士学位论文 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 yc h e c kc o d e sh a v ea t t r a c t e dc o n s i d e r a b l ea t t e n t i o ni n t h ec o d i n gc o m m u n i t yb e c a u s et h e yc a l la c h i e v en e a r - c a p a c i t yp e r f o r m a n c e ，a n dm a n y o f t h ea p p l i c a t i o n sb e i n ge x p l o r e df o rl d p cc o d e s ，i n c l u d i n ga p p l i c a t i o nt od e 印s p a c e a n ds a t e l l i t ec o m m u n i c a t i o n s ，w i r e l e s sc o m m u n i c a t i o n s ，m a g n e t i cs t o r a g e ，a n di n t e r a c t p a c k e tt r a n s m i s s i o n i nt h i sp a p e r , w em a i n l yd ot h er e s e a r c h o nt h ee n c o d i n g o p t i m i z a t i o no f l d p cc o d e s t h em a i nw o r k so f t h i sp a p e ra l ea sf o l l o w ： f i r s t ，b ya n a l y z i n gt h es h a p e so ft h ec y c l e so ft gi np a r i t yc h e c km a t r i x ，t h i sp a p e r p r e s e n t st w ok i n d so fa l g o r i t h m sf o rc o u n t i n gt h en u m b e ro fs h o r tc y c l e s 1 i nt h e p a r i t yc h e c km a t r i x ，w es e a r c ht h en o d e so fac y c l eo n eb yo n e w h e nf i n d i n ga l lt h e n o d e so fac y c l e ，w ef i n dac y c l ei nt h ec h e c km a t r i x b yc h e c k i n ga l lt h ep o s s i b l e n o d e s - c o m b i n a t i o n si nt h ec h e c km a t r i x ，w ec a nf i n dt h en u m b e ro f c y c l e si ni t 2 t h e a l g o r i t h mb a s e do nt h ec o m b i n a t i o n s t a k i n go u ta c e t t a i nn u m b e ro fr o w sf o rd i f f e r e n t c y c l e s ，c o u n t i n gt h en u m b e ro fc y c l e sc o n t m n e di nt h e s er o w s ，t h e na d d i n gu pa l lt h e n u m b e ro fc y c l e st h a tc o n t a i n e di na l lp o s s i b l ec o m b i n a t i o n so ft h er o w si nt h em a t r i x ， a n dw ec a ng e tt h en u m b e ro fc y c l e si nt h em a t r i x u s i n gt h ec h e c ka l g o r i t h m sw ec a r l c a l c u l a t et h en u m b e ro fs h o r tc y c l e si nt h ec h e e km a t r i x w ec a na l s ou s et h ec h e c k a l g o r i t h m sf o rf i n d i n gt h e9 0 0 dq u a s i c y c f i c ( q c ) c o d ew i t hl a r g eg i r t h s e c o n d t h i sp a p e ra l s op r e s e n t 锄a p p r o a c hf o rc o n s t r u c t i n gl d p cc o d e sw i t hg i r t h8 f i r s t ，w ed e s i g n3s u b m a t r i c e s 谢t l ld i f f e r e n ts h i f t i n gf u n c t i o n sg i v e nb yo i l l s c h e m e s ， t h e nc o m b i n et h e mi n t oam a t r i xa c c o r d i n gt oo u r a p p r o a c h , f m a l l y , e x p a n dt h em a t r i x i n t oad e s i r e dp a r i t y - c h e e km a t r i xu s i n gi d e n t i t ym a t r i c e sa n d c y c l i cs h i f tm a t r i c e so f t h e i d e n t i t ym a t r i c e s t h es i m u l a t i o nr e s u l t si na w g nc h a n n e l ss h o wt h a tt h e s ec o d e s w h i c hc a nb eo b t a i n e db yt h eg e n e r a t o rm a t r i xd e r i v e df r o mt h i sc h e e km a t r i xf o r e n c o d i n gt h er a n d o mi n f o r m a t i o nb i t sa r e a s9 0 0 d 嚣r a n d o ml d p cc o d e s k e y w o r d s ：c o m m u n i c a t i o n ；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 s ； c h e c km a t r i x ；c y c l e ；c h e c ka l g o r i t h m ；b r a n c hm e t h o d ；q u a s i c y c l i c ( q c ) c o d e s 致谢 本论文的工作是在我的导师肖扬教授的悉心指导下完成的，肖老师学识渊博， 治学严谨，对学术有很敏锐的洞察力，对科研工作有执著的热情。在读研究生期 间，肖老师对我严格要求，在各方面给予悉心指导和帮助，使我的科研和工作能 力有了很大的提高。从硕士论文的选题、撰写至最后的定稿，肖老师给予我很多 建议和教导，使论文的研究能够顺利完成。 感谢我的父母，是他们的培养和支持使我取得今天的成绩。在此，深切地感 谢父母亲二十多年来的养育之恩和教导。 感谢谢玉明，郭华平，曹振臻，孔令军，刘成，郭振清，候迎宾，陈芬同学 在我研究生学习和生活期间给我无微不至的关心和帮助。两年半的研究生阶段， 大都是在与他们共同探讨中走过来，他们提供的建议使我受益匪浅。 感谢师姐鲁凌云，师兄赵莹，杜海峰以及众位师弟师妹对我的支持和帮助， 他们为我提供了一个温暖的集体氛围，使我能更投入的完成论文。 最后向所有关心、帮助和支持我的人致以衷心的感谢! 序 序 本论文的研究工作是在国家自然科学基金项目( 6 0 5 7 2 0 9 3 ) 的资助下完成， 在肖扬老师的大力帮助下，本文作者对l d p c 码编译原理进行了深入研究。l d p c 码以其优异的性能在今后新一代移动通信系统中具有潜在的应用前景，因此本论 文研究内容具有理论和实用意义。 本文在分析影响l d p c 码的因素( 如环，最小码距等) 的基础上，实现了l d p c 码的优化设计。本文设计的码字性能在不同码长、码率下均具有优异的性能，且 设计的码字具有准循环的特性，具有硬件实现简单的特性 引言 1 引言 本章简要介绍了l d p c 码的背景知识与现实意义，包括l d p c 码的实际应用 和线性分组码的基础知识；结合纠错码的发展过程介绍了l d p c 码的出现及其发 展；最后总结了作者在攻读硕士期间所做的主要工作并给出了本文内容安排。 1 i 研究的背景和意义 1 1 1 实际应用背景及其意义 通信的目的是提高信息传输的可靠性和有效性1 。纠错码是提高信息传输可 靠性的一种重要手段，它已经经历了4 0 年的历史，在此期间有了很大的进展。伴 随着信息时代的到来以及微电子技术的飞速发展，今天纠错码已不再单纯是理论 上探讨的话题了它已经成为一门标准技术而被广泛采用。在通信领域中，c r c 校验已成为c c t 对各类线路传输建议中不可缺少的一部分；在移动通信中，纠错 码被广泛用于模拟体制的信令传输及数字体制的整个传输，以提高传输的可靠性 和节省珍贵的频谱资源；在卫星通信中，纠错码技术已成为用来降低对高功放的 要求和减少地球站天线孔径的尺寸的经济可靠的方法，v s a t 和u s a t 的兴起， 都是和纠错码技术的应用有关的；在电话网上的数据传输中，纠错码、差错控制 技术已是使高速数据传输( 9 6 k b i t s 以上的数据率) 成为现实的关键技术。纠错码 技术还广泛应用于计算机存储和运算系统中，此外，纠错码技术还应用于超大规 模集成电路( v l s i ，u l s i ) 设计中，以提高集成电路芯片的成品率，降低芯片的 成本。 随着移动通信的发展，对纠错码不断地提出新的要求。t u r b o 码虽已成为3 g 的信道编码标准，但其译码复杂度高，时延长，难以适应最高数据速率远比3 g 要 高的后3 g ( 即b 3 g 。或4 g ) 未来移动通信系统的需求。l d p c 码是一类可以用非 常稀疏的校验矩阵( p a d t y - c h e c k ) 或二分图( b i p a r t i t eg r a p h ) 定义的线性分组纠 错码，最初由g a l l a g e r 发现，故亦称g a l l a g e r 码【4 5 l 。经过数十年的沉寂，随着计 算机能力的增强和相关理论的发展，l d p c 码重新被重视，并证明它在采用基于置 信传播( b e l i e f - p r o p a g a t i o n ，b p ) 的迭代译码算法的条件下具有逼近s h a n n o n 限的 良好性能，可以这么说，u ) p c 码的重新发现是继t u r b o 码后在纠错编码领域的又 一重大进展。 北京交通大学硕士学位论文 l d p c 码在新一代移动通信超3 g 中有着很大的用武之地，因为l d p c 码本身 即有抗突发差错的特性；不需要引入交织器，避免了可能带来的时延；可以实行 完全并行的操作，便于硬件实现；吞吐量大，极具高速译码的潜力；它不仅具有 接近s h a n n o n 限的优异性能，同时由于在码的构造、译码方法上的相关成果的获 得使得l d p c 码在信道条件较差的无线通信中展现出了巨大的应用前景，非常适 合于在未来的移动通信系统中的实现。 1 1 2 理论背景 本文首先浏览一下纠错码的基础知识m ，作为研究l d p c 码的开始。首先， 我们回顾一下s h a n n o n 的信道编码定理。 定理1 1 每个信道具有确定的信道容量c ，对于任何小于c 的码率胄，存在 有速率为r 码长为n 的分组码及( 再。，k 0 ，肌) 卷积码，若用最大似然译码，则随着码 长的增加其译码错误率p 可任意小，即 和 p 4 矿晦。 p sa c e 一( 。+ 1 ) 弛。) = a c e 一乓( 2 ) 式( 卜1 ) 和( 卜2 ) 中，4 和4 为大于0 的系数，易俾) 和e ( r ) 为正实函数， 称为误差指数，它与r 、c 的关系如图卜l 所示。图卜1 中，c l 、c 2 为信道容量， 且c i c 2 。由信息论的基础知识可知，在高斯白噪声信道时，信道容量 c = w l 0 9 2 e l + p , 聊 ( b i t s ) ( 1 - 3 ) 式( 卜3 ) 中，是信道所能提供的带宽， r 是分组码信号的持续时间即信号宽度， 位频带的噪声功率，只( 聊v o ) 是信噪比。 只= e t 是信号功率，e 是信号能量， 只w 是单位频带的信号功率，“是单 2 引言 图卜1e ( r ) 与r 的关系 由式( i - 2 ) 和图i - i 可看出，信道容量c 、码长，l 和错误概率p 之间的转换 关系。为了满足一定误码率p 的要求，可以用以下两类方法实现。 一是增加信道容量c ，从而使e ( 五) 增加。由f 的表示式式( 卜3 ) 可知，增加c 的方法可以采用如加大系统带宽或增加信噪比的方法来达到。例如，采用调频、 调相等宽带调制方法；增加发射机的功率；应用高增益天线；采用分集接收及低 噪声器件等方法。这些措施是从根本上改善信道、增加信道容量、减少误码率的 方法，是通信设计工作者经常采用的传统方法。 另一种方法是在r 一定下，增加分组码长h ( 也就是增加分组信号持续时间 r ) ，可使p 随月的增加而呈指数下降。 但由于码长疗的增加，当r 保持一定时， 可能发送的码字数2 七指数增加，从而增加了译码设备的复杂性。这种方法就是信 道编码定理所指出减少误码率的另一方向，它为通信设计工作者提供了一条新的 途径 纠错编码的意义就在于：保持一定的信息传输效率条件下，通过编译码来降 低误码率以实现可靠通信，并且要求译码器尽可能简单 利用纠错码进行差错控制的数字通信系统如图卜2 所示，由此可如下定义分 组码。 定义1 1 分组码是对每段位长的信息组，以一定规则增加，= n k 个校验 元，组成长为n 的序列：( q - ”c w ：，c l ，c o ) ，称这个序列为码字。在二进制情况下， 信息组总共有2 个，因此通过编码器后，相应的码字也有2 个，称这2 个码字集 合为( 月，七) 分组码。 3 北京交通大学硕七学位论文 图1 - 2 利用分组码的数字通信模型 线性分组码是分组码中最重要的一类码，它是讨论各类码的基础。虽然这类 码的概念比较简单，但却非常重要，特别是有关码的生成矩阵g 和校验矩阵日的 表示法，以及它们之间的关系，而曰与纠错能力之间的关系则更为重要。 一个( 玎，j i ) 线性分组码，是把信息划成k 个码元为一段( 称为信息组) ，通过编 码器变成长为n 个码元的一组，作为( n ，七) 线性分组码的一个码字。在二进制情况 下，有2 4 个数组，2 个码字集合构成了一个k 维线性子空间，则称它是一个( 刀，七) 线性分组码。 定义1 2 【露，明线性分组码是g f ( q ) ( 在二元域情况下为g f ( 2 ) ) 上的n 维线 性空间匕中的一个| | 维子空间圪。 定义1 3 两个二元向量和c 。( 其中m ，打e 1 , - - - , m ) 的距离定义为它们之 间对应位取值不同的个数，称为它们之间的汉明距离，记为d ( ，c a ) 。 定义1 4 在一个( h ，k ) 线性分组码中，任两个码字之间距离的最小值，称为 该分组码的最小汉明距离，记为d 。 定义1 5 二元向量吒中1 的个数，称为它的汉明重量，简称重量，记为“巳) 。 定理1 2 任- - ( n ，| i ) 线性分组码，若要在码字内： ( 1 )检测p 个随机错误，则要求码的最小距离d e + i ； ( 2 )纠正t 个随机错误，则要求d 2 2 t + 1 ； ( 3 ) 纠正f 个随机错误，同时检测e ( t ) 个错误，则要求d t + e + l 。 ( 4 ) 纠正f 个错误和p 个删除，则要求d 2 t + p + l 。 4 引言 该定理确定了码的纠错能力与它的距离之间的关系，是纠错码理论中最基本 的定理之一。 定理1 3 若巧是胛维空间v 的子空间，则和巧中每一个珂维矢量均正交的所 有矢量，构成y 的另一个子空间k ，称匕为k 的零空间或解空间。 定理1 4 若n 维空间y 的子空间嵋的维数为七，则k 的零空间的维数为 刀一| 。 ( 一，后，d ) 线性分组码的编码问题就是在疗维线性空间中，如何找到满足一定 要求的，有2 个矢量组成的| 维线性子空间圪。或者说，在满足给定条件( 码的 最小距离d 和码率r ) 下，如何从已知的七个信息元求得，= 打一七个校验元。这相 当于建立一组线性方程组，已知七个系数，要求开一七个未知数，使得到的码恰好 有所要求的最小距离d 。 一般情况下，任何一个( 玎，】 ，d ) 码的日矩阵可以表示为 i | i l l 州噍以 日：i 嘻一- 啤朋 l 氏一h - k ，2 i 啊。 ，。 i 嘻，。唣，2： h 知i 吃山2 或 1 岛，o i( 1 4 ) j 快地建立码的线性方程组： 当。k 一。1 气，o l i q 一2i ：0 7( 1 - 5 ) 蠢。，kj h 一一i 簪魄p n - 2 f ：。m 6 ， b 一。巳。c 0 1 冬川 冬一。； 冬。i ：o ( 1 6 ) 【玩。氏k 肿吃k m j 5 北京交通大学硕士学位论文 简写为 或 日c 7 = o t( 1 - 7 ) c h 7 = 0 ( 1 8 ) 由于( n ，k ，d ) 码的每一码字必须满足式( 卜7 ) 或式( 卜8 ) ，即它的每一个码字 必然在由日矩阵的行所张成的圪。空间中的零空间中。由定理1 4 可知，圪。的 零空间必然是一个k 维子空间圪。，而这正是( h ，k ，d ) 码的码字集合全体。所以， 圪。与( n ，k ，d ) 码的每一个码字均正交，也就是日矩阵的每一行与它的码的每一码 字的内积均为o 。 ( n ，k ，d ) 分组码的2 个码字组成了一个k 维子空间，因此这2 个码字完全可由 k 个独立矢量所组成的基底而张成。设基底为 若把这组基底写成矩阵形式，则有 f g i 。 g ：1 9 2 ，一t i ： l g , _ 一l蚓 ( h ，k ，d ) 码中的任何码字，都可由这组基底的线性组合生成，即 c = m g = b 。 蜀，。 m 。1 【g t ：。 g i ，：9 1 ，。1 9 2 p ；擘。l 颤：未。j ( 1 9 ) 式中，m = ( m 。m 。m 。) 是| 个信息元组成的信息组。因此，若已知信息 组m ，通过式( 卜1 1 ) 可求得相应的码字，称式( 卜1 0 ) 的g 为( 以，k ，d ) 码的生成 矩阵。 6 = 一 圆心 b 呈 跖“ = | l = k 腌心 引言 l d p c 码是一种线性分组码，它的校验矩阵h = 魄) 忙。m 是稀疏矩阵，即非零 元素( 在g f ( 2 ) 域上即为1 ) 的个数占总元素个数的比例非常小。前面介绍了线性 分组码可以由它的生成矩阵g = 鼽) m 决定，l d p c 码同样可以由其生成矩阵来决 定，给定生成矩阵g ，l d p c 码的码字集合可以表示为 c = 协一i j = q 蜀，a i f q 其中g l 为生成矩阵g 的第i 行。等价地，l d p c 码也可以由校验矩阵日来决 定。给定校验矩阵，码字集合可以表示为 c = 缸巧j ，吩) = o ，i = 1 ，2 ，n - k 其中，h j 为校验矩阵日的第行亍。因此选定了校验矩阵，那么这个l d p c 码 也就确定了。 1 2 纠错编码领域的相关发展 1 9 4 8 年香农( s h a n n o n ) 在他的开创性论文“通信的数学理论”中，首次阐明 了在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，奠定了 纠错码的基石。自此以后汉明( h a m m i n g ) 、斯列宾( s l e p i a n ) 、普兰奇( p r a n g e ) 等人在5 0 年代初根据香农的思想，给出了一系列设计好码和有效译码的方法。以 后，纠错码受到了越来越多的通信和数学工作者，特别是代数学家的重视，使纠 错码无论在理论还是在实际中都得到飞速发展。 信道编码定理指出，随着码长胛的增加，译码错误概率按指数接近于零。因此， 为了使码有效就必须用长码。但是，随着码长的增加，在一个码组中要求纠错的 数目相应增加，译码器的复杂性和计算量也相应增加以致难以实现。为了解决性 能与设备复杂性的矛盾，1 9 6 6 年f o r n e y 提出了级联码概念。级联码是一种用 r e e d - s o l o m o n 码做外码，卷积码做内码的编码方式。级联码不仅有极强的纠突发 和纠随机错误的能力，更重要的是利用级联码的构造方法，能达到信道编码定理 所给出的码限，也就是能构造出渐近好码( s h a n n o n 码) 。 b c r r o u 等在1 9 9 3 年提出的t u r b o 码 6 1 ，在加性白噪声信道下的性能接近了 s h a n n o n 限，这标志着实用的接近s h a n n o n 限的信道编码的开始。t u r b o 码，又称 并行级联卷积码( p c c c ) ，是由b e r r o u 等在i c c 9 3 会议上提出的。他巧妙地将 卷积码和随机交织器结合在一起，实现了随机编码的思想；同时，采用软输出迭 7 北京交通大学硕士学位论文 代译码来逼近最大似然译码。模拟结果表明，如果采用大小为6 5 5 3 5 的随机交织 器，并且进行1 8 次迭代，则在e n o 0 7 d b 时，码率为1 2 的t u r b o 码在a w g n 信道上的误比特率( b e r ) 1 0 一，达到了近s h a n n o n 限的性能( 1 2 码率的s h a n n o n 限是o d b ) 。因此，这一超乎寻常的优异性能，立即引起信息与编码理论界的轰动。 由于t u r b o 码的上述优异性能并不是从理论研究的角度给出的，而是从计算机 仿真的结果。因此，t u r b o 码的理论基础还不完善。后来经过不少人的重复性研究 与理论分析，发现t u r b o 码的性能确实是非常优异的。因此，t u r b o 码的发现，标 志着信道编码理论与技术的研究进入了一个崭新的阶段，它结束了长期将信道截 止速率作为实际容量限的历史。 低密度奇偶校验( l o w d e n s i t y p a r i t y - c h e e k ，l d p c ) 码是由g a l l a g e r 在1 9 6 3 年就提出的一种具有稀疏校验矩阵的线性分组码h 一1 ，但是由于其硬件实现特别复 杂，当时并不被人所关注。而当时人们的兴趣大都集中在有可能实现的编码方式 上，例如级联码等。所以在接下来的3 0 年来一直被人们忽视了，1 9 9 3 年b e r r o u 提出了t u r b o 码吲，l d p c 码才重新吸引了研究者的兴趣，几乎同时，m a c k a y 和 n e a l p 町，s i p s e l 和s p i e l m a n t 9 】以及w i b e r g t ”1 等人对它重新进行了研究，发现l d p c 码同样具有逼近香农限的优异性能。从那时起该码逐渐成为编码领域的一个研究 热点。 l d p c 码是基于稀疏校验矩阵的线性分组码，具有类似t u r b o 码的良好纠错性 能。1 9 8 1 年，t a n n e r 提出的用二部图表示一个低密度线性分组码的方法成为u ) p c 码的主要分析工具 i l l 。二部图是由比特节点和校验节点以及连接它们的边组成。 比特节点对应校验矩阵中相应的列；校验节点对应校验矩阵中相应的行。一个二 部图和一个校验矩阵完全对应。 根据校验矩阵的不同，l d p c 码分为两大类：正规低密度校验码和非正规低密 度校验码。正规低密度校验码的校验矩阵每行( 列) 中的非零元素个数是相同的， 而非正规低密度校验码的校验矩阵每行( 列) 中的非零元素个数未必相同。此外， 根据校验矩阵中的元素取自的域不同，l d p c 码还可以分为二元l d p c 码和多元 l d p c 码。本文中仅考虑二元l d p c 码，多元的情形可以由二元的推广得到。 1 3 本文的研究重点和所作的工作 本文结合国家自然科学基金项目( 6 0 5 7 2 0 9 3 ) ，采用理论分析和计算机仿真相 结合的方法，对l d p c 码的优化设计进行了深入研究。主要对影响l d p c 码性能的 环进行了研究，设计了两种环数检验算法，这两种方法分别与准循五l z ( q u a s i c y c l i c ， q c ) 码的设计思想m 。3 1 相结合可以设计出性能优异的大围数l d p c 码。此外，在 8 引言 分析校验矩阵中四环和六环的形状的基础上设计出无四环，无六环的校验矩阵， 利用该校验矩阵设计的l d p c 码具有逼近随机l d p c 码的误码率性能。 全文共分五章，具体安排如下。 第一章是引言，概述了本论文内容的理论背景知识与现实意义，通过回顾纠 错码的相关发展介绍了l i ) p c 码的产生与发展。 第二章对当前u ) p c 码的校验矩阵的主要的几种构造方法进行了介绍，接着 对l d p c 码的编译码方法进行了总结性的阐述，最后对影响l d p c 码的重要因素 之一的环进行了相关介绍。 第三章详细介绍了本文提出的两种环数检验算法的设计方法以及其在设计性 能优异的u ) p c 码时的应用。 第四章本文提出了一种基于子矩阵移位法的大围数u ) p c 码设计方法。该方 法设计的校验矩阵避免了短环( 四环，六环) 的存在，此外，由于加入了随机扩 展因子，避免了设计的校验矩阵过于规则的情况，使得设计的码具有较好的距离 特性。b e r 性能分析表明该码的性能非常接近m a c k a y 随机码。 第五章对本文的工作进行总结以及对u ) p c 码的展望。 9 北京交通大学硕士学位论文 2l d p c 码的编译原理 本章首先介绍了几种主要的l d p c 码的校验矩阵的构造方法；然后给出了 l d p c 码的编译码方法；最后介绍了影响l d p c 码性能的重要因素之一环。 2 1 l d p c 码的校验矩阵构造法 由前面的介绍可知，u ) p c 码的编码关键在于其稀疏校验矩阵的构造。下面具 体介绍一些具有代表性的编码算法。 1 g a l l a g e r 构造方法 最初的l d p c 码的编码方法是g a l l a g e r 在其论文中提到( 栉，工k ) 规则l d p c 码设计方法，其中玎表示码长，j 表示校验矩阵中每列所含1 的个数，而k 则表示 校验矩阵中每行所含1 的个数。它的校验矩阵日构造方法如下 ( 1 ) 将校验矩阵日分成，个子矩阵日l ，日：，q ，每个子矩阵的每列有且只 有一个l ： ( 2 ) 子矩阵甄中的1 呈下降的阶梯状排列，即第f 行的七个1 从第( 卜- 1 ) 七十l 位排到第琥位： ( 3 ) 其余的子矩阵通过对且进行随机列置换得到，所有置换是等概率出现 的。 日：冈 沼。， 旧j 上述设计方法设计的校验矩阵日是规则的，行重为k ，列重为- ，。该校验矩阵 虽然不能保证一定没有四环，但是可以通过计算机设计来避免出现四环。g a l l a g e r 的这种设计方法在j 3 ，k j 的时候有很好的距离特性。 g a l l a g e r 的编码方法于1 9 8 1 年被t a n n e r 推广，并且被应用于c d m a 通信。 g a l l a g e r 码的设计方法随后被m a c k a y 等人进一步推广。 1 0 l d p c 码的编译原理 2 m a c k a y 构造方法 m a c k a y 发现了通过稀疏矩阵日编码的优势，并且首先显示了这类码的优异 性能。m a c k a y 在其网站1 6 1 上公布了大量他设计的l d p c 码，这些码大部分是规 则的，可以应用于数据通信与储存。 m a c k a y 提出了4 种l d p c 码的构造方法可以避免所构造的校验矩阵中存在四 环。 构造方法1 a ： 这种方法是最基本的一种构造方法，保证校验矩阵的列重为一个固定值w c ( 比 如w e = 3 ) ，行重大于w c 且分布尽可能均匀，同时要求任意两列重叠的1 的个数不 超过l 。 图2 - 1 m a c k a y 构造方法l a 构造方法2 a ： 设所设计的校验矩阵的维数是m 以，让m 2 列的列重为2 。这些列由两个维 数为m 2 x m 2 的单位阵构成。其它列的构造同构造方法1 a 。 ( 3 ) 图2 - 2m a c k a y 构造方法2 a 构造方法1 b 、2 b ： 对由构造方法1 a 和2 a 构造的校验矩阵进行消列，将某些精心挑选的列去掉 使得设计的校验矩阵中的最小环的长度大于l ( 比如l = 6 ) 。 m a c k a y 构造方法构造的l d p c 码的优点是距离特性特别好而且避免了短环 北京交通大学硕士学位论文 ( 四环) ，缺点是编码复杂度高。 3 准循环码的构造方法 准循环的l d p c 码的校验矩阵日由一系列的m m 小循环方阵组成 1 2 , 1 3 】，这 些小循环方阵可以是置换矩阵或是基于有限几何的矩阵等。 h = p 4 1 2 p 4 ” ： p 2 ( 2 2 ) 式( 2 2 ) 中p 代表m m 单位阵，上标a 表示平移的数。选用不同的a 的构成 规则，可形成不同的编码方法。由于准循环码的准循环特性，可以得到系统形式 且也具有准循环特性的生成矩阵，则只需要采用移位寄存器即可实现输入码字和 生成矩阵的相乘。 2 2l d p c 码的主要编码算法 目前的研究结果表明，u ) p c 码是信道编码中纠错能力最强的一种码，而且 由于其译码器结构实现简单，可以用较少的资源消耗获得极高的吞吐量，因此应 用前景相当广泛。而编码器的复杂度问题作为不利的因素制约了u ) p c 码的应用。 传统的编码方法是通过生成矩阵生成码字，其复杂度和码长的平方成正比，这使 得l d p c 码在编码上需要大量的硬件资源和很长的延时。r i c h a r d s o n 在文献【1 4 1 中 引入了一种新颖的算法在很大程度上解决了该问题。对于基于有限几何或其他置 换方法等构造出的具有循环或准循环特性的l d p c 码，可以简单地用移位寄存器来 实现编码，编码器复杂度非常低。下面分别介绍传统的基于高斯消去的编码方法 和基于近似下三角矩阵的有效编码方法。 2 2 1 基于高斯消去的直接编码 在有限域g f ( 2 ) 中，l d p c 码校验矩阵的每个校验式都是二元异或运算，校验 矩阵可定义为 h = 【u 1 】 1 2 ( 2 3 ) 眺乏叽一； 嘶 一旧 l d p c 码的编译原理 式中q 是朋x m 稀疏可逆方阵；以；是r e x ( n - m ) 的稀疏矩阵。圻为以的逆矩阵。 由线性码编码理论 4 - - 8 1 得：l d p c 码的生成矩阵为 g = h 町v 2 。一舳l 。j l 。为m m 的单位矩阵。 l d p c 码的编码为 q = 。g = 眩。】 ( 2 - 4 ) ( 2 5 ) 式中“。= 阻柚，”，“。，一。】是肼个信息元组成的信息组。因此，若已知信息组 吒和g 就可以生成相应的l d p c 码的码字。 2 2 2 基于近似下三角矩阵的有效编码 在文献中畔】给出了一种简化的编码方式，基于近似下三角矩阵的有效编码。 该方法充分利用了校验矩阵的稀疏性，使l d p c 码的编码方法下降到接近线性复 杂度。为了保证矩阵的稀疏性，对校验矩阵只做了列之间的顺序的调整，生成一 个近似下三角形式的矩阵，见图2 3 。 图2 3 校验矩阵的近似下三角形式 北京交通大学硕七学位论文 上图可用矩阵的形式表示为 日：4 丑t ( 2 - 6 ) l cde j 由上面的分析可知，近似下三角矩阵中的子矩阵均为稀疏矩阵，子矩阵r 为 下三角矩阵且主对角线上的元素都为1 。 ： 三： = 一e r 一。a 爿+ c e r b 一。口+ 。 令工= o ，p 。，p ：) ，其中s 表示系统部分，p 。与p ：联合表示校验部分，p 。长为g ， p 2 长为( 聊一g ) 。根据公式日x t = o r 可得到下面两个等式： 和 a s 7 + 现7 + 印2 7 = o ( 2 8 ) ( - e t 。1 a + c ) s 7 + ( 一e t b + d ) p 1 7 = o ( 2 - 9 ) 按照式( 2 8 ) 与式( 2 9 ) 可递推出两块校验比特p 1 与p 2 。文献i t 4 通过进一 步的分析可以得到求解p 。的运算量为o ( n + 9 2 ) ，p 2 的运算量为d ( ) 。 由上面对该简化的编码算法的运算量分析可知，只要使g 的值尽量小就可达到 接近线性的编码复杂度。 2 3l d p c 码的译码 l d p c 码最优译码算法是置信传播算法吣1 ( b e l i e f - p r o p a g a t i o na l g o r i t h m ， b p a ) ，该算法核心思想在于利用接收到的软信息在比特节点和校验节点之间进行 迭代运算，从而获得最大编码增益，因此具有很好的性能。 1 4 l d p c 码的编译原理 在编码的校验矩阵曰中，将参与第m 个校验约束的信息比特集合记为 ( 肌) z p ：日。，= 1 ) 。同样的，将第，个信息比特参与的校验集合记为 m u ) ；伽：日。= l 。( m ) f 为j ( 埘) 与第z 比特的差集。算法包括两个交替执行的 部分，与日中非零元素相关的数值q 。和逐次更新。靠，是指已知除第m 个外其 他所有校验约束的信息时，j 的第，比特取值为x 的概率( 工为发送端发送的码字) 。 r 二是指在已知z 的第，比特值为x ，其它比特满足相互独立的概率分布 g 。，：j ，( 埘) ) 时第r t t 个校验约束得到满足的概率。如果日的二部图没有环，在 经过一定次数的迭代后，该算法可以得到所有比特的精确后验概率。 初始化：令刃= p “= o ) ( 比特而取0 的先验概率) ，d = p “= 1 ) = 1 一。 对于每一个满足= 1 的( ，所) ，变量口：，和g 二分别被初始化为钟和p ；。 迭代过程： 第一步：对于每一个校验约束m 和对应的每一个，三( 埘) 计算两个概率：一个 是0 ，当而= o ，且其它比特 _ ：， 对应于相互独立的概率分布磁，办 时， 校验约束m 得到满足的概率，定义如下： ，二；，却。磊，j j j i c 2 一t 。， 却。e l ( m ) v ll ，t 伽) v j “佃 另一个是匕，当而= l 时，校验约束得到满足的概率，定义如下： 扣五，净= x j ，酬j ，o = p l = l i 而= l兀g 二i i 一e ，( _ ) v jll ，“( _ ) u ，“_ ) v 式中概率内的求和为模2 和条件概率的取值为0 或l ，取决于于假设的_ 的值 是否满足模2 求和式。 这一步的计算可以根据前后向递归算法适当简化。定义 北京交通大学硕七学位论文 可以得到： 利用数学归纳法可得到瑶o = o o z 戈i ) 的计算式： 壕= 半 经过简化，瑶的计算量大大减少。 第二步：利用计算所得值名和匕更新概率值g 。o ，和g 二。对于每个，计算： 以，= 钟兀，：= _ ， me m ( 1 ) 、m 如= a m ，爿兀 _ e 村( ，) 、辨 其中，a 。为归一化系数使得g ：，+ g _ = l 。 同时计算出比特，取值为0 和l 的伪后验概率g ? 和g ；： 卵= 口，钟兀喝 _ e 射i f ) 口；= a t p j 兀匕 m e m i f ) ( 2 1 7 ) 第三步：当g b 0 5 时令x 产l ，反之x l = o ，这样就生成了x 。如果校验方程 a x = 0m o d 2 成立，则译码成功并结束，石= j ；否则若迭代次数t 少于预先设定 的最大迭代次数丁，重复迭代过程；如果t t 时仍没有得到正确的译码，译码结 1 6 l d p c 码的编译原理 束，并声称译码失败。当译码失败时，部分译码的x 可以作为其它译码算法的有 效译码起点。 b p 算法的复杂度为码长的线性函数，在硬件中的并行实现能够极大地提高译 码速度，在迭代过程中，如果试验译码得到成功，译码过程立即结束而不是进行 固定次数的迭代，有效的减少了算法的迭代次数；译码后的误码率可以随信噪比 的增加任意减少，没有误码率下降减速的差错平台现象。b p 算法不论在理论上还 是实际中能够在a w g n 环境下达到非常接近信道容量的性能，因此得到了广泛 的认可。 2 4 影响l d p c 码性能的重要因素环 l d p c 码是一种基于稀疏校验矩阵的线性分组码，1 9 8 1 年，t a n n e r 提出的用 二部图来表示一个低密度的线性分组码的方法【l ”，成为了l d p c 码的主要分析工 具设一个l d p c 码，码长为，信息位长为足，校验位长为m = n k ，则该 码的校验矩阵日是一个大小为m n 的矩阵。日的二部图表述如下：二部图下边 的个节点代表个码字，称为信息节点；上边肘个节点代表肘个校验式，称 为校验节点，当下边的信息节点和上边的校验节点存在于同一个校验式时，就用 边连接。校验矩阵同样可以用树图来表示，树图中的校验节点代表校验矩阵中的 行，变量节点代表校验矩砗中的列。图2 - 4 为一稀疏校验矩阵日，图2 5 为校验 矩阵目的二部图表示，图2 - 6 为校验矩阵日对应的树图。图2 5 和图2 - 6 中，校 验节点代表校验矩阵中的一行，变量节点代表校验矩阵中的一列。 日； 囡 00l0 0 10010 01010 0 仔001 01o0011 l0 0 001010001 图2 - 4 校验矩阵日 1 7 北京交通大学硕士学位论文 c 1c 2c 3c 4 c 5 c 6 v lv 2v 3v 4v 5v 6v 7wv 9 图2 - 5 校验矩阵日的二部图表示法 ” v 5 v 8 v 6 c 3 口校验节点 0 变量节点 口校验节点 6 变量节点 图2 - f i 校验矩阵日的树图表示法 所谓环是指图中的一条路径，它由一些节点和边构成，任选一个节点作为起 始节点，这条路径经过每个节点一次，经过每条边一次，最后返回所选的起始节 点。而环长指的是环上的节点数或边数( 由环的定义可知，环上