（通信与信息系统专业论文）ldpc码在mimoofdm系统中的应用分析.pdf

南京邮电大学硕士研究生学位论文摘要 摘要 随着移动通信业务的飞速发展，用户数量急剧增长，分配给3 g 系统的资源趋于饱和， 通信速率无法满足宽带业务的需求。m i m o 和o f d m 技术的结合可以克服无线信道频率 选择性衰落，增加系统容量，提高频谱利用率，已成为第四代移动通信的关键技术之一。 在提高频谱利用率的同时，通信系统的可靠性也需要得到保证，因此必须采用纠错编 码技术来提高系统的传输可靠性。低密度奇偶校验码( l d p cc o d e s ) ，是一种可以用稀疏 的校验矩阵和二分图的形式来定义的线性分组码，l d p c 码以其具有逼近香农限性能，且 译码简单，易于并行操作，适合硬件实现等优点，已经成为纠错编码领域的研究热点。 本论文研究的主要内容就是l d p c 码在m i m o o f d m 系统中的应用。本文首先介绍 了l d p c 码的构造及其译码算法，并对其性能进行了分析；随后，在深入研究o f d m 和 m i m o 技术基本原理和关键技术的基础上，给出m i m o 和o f d m 优化结合的系统模型； 接下来，基于l d p c 码的优越性能，本文将l d p c 码应用于m i m o o f d m 系统中，并采 用i e e e8 0 2 1 6 e 建议的车载模型作为仿真信道模型，重点研究了采用l d p c 码的 m i m o o f d m 系统在频率选择性信道下的性能，包括：l d p c 码的不同码长、码率和不 同调制方式等因素对该系统性能的影响，并将其与采用t u r b o 码的m i m o o f d m 系统的 性能进行了比较分析，得出了自己的结论。 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t d u et ot h er a p i dd e v e l o p m e n to fm o b i l ec o m m u n i c a t i o na n dt h eg r e a ti n c r e a s eo f s u b s c r i b e r sa sw e l la st h ed e f i c i e n c yo f1 j r e q u e n c yr e s o u r c eo f3 g , i tb e c o m e sm o r ea n dm o r e d i f f i c u l tt os a t i s f yw i t ht h er e q u i r e m e n to fw i d e b a n ds e r v i c e t h ec o m b i n a t i o no fm i m oa n d o f d mt e c h n o l o g yw h i c hi so n eo ft h ek e yt e c h n o l o g i e si n4 g c a nc o n q u e rt h ef r e q u e n c y s e l e c t i v ef a d i n g ，i n c r e a s et h ec a p a c i t yo f s y s t e ma n di m p r o v et h er a t eo fu t i l i z a t i o no f f r e q u e n c y a tt h es a m et i m e ，t oi m p r o v et h e r e l i a b i l i t y o ft r a n s m i s s i o nt h e t e c h n o l o g yo f e r r o r - c o r r e c t i n gc o d i n gm u s tb ea d o p t e d 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 ，w h i c hi sa k i n do fl i n e a rb l o c kc o d e sd e f i n e db yt h es p a r s ec h e c km a t r i xa n db i p a r t i t eg r a p h ，h a sa t t r a c t e d m u c ha t t e n t i o ni nt h ef i e l do fc o d i n gf i e l df o ri t sa d v a n t a g e so f a p p r o a c h i n gt os h a n n o nl i m i t s a n ds i m p l ed e c o d i n ga l g o r i t h m sa sw e l la si t sg o o d p a r a l l e lo p e r a t i o na n dh a r d w a r er e a l i z a t i o n t h i sp a p e rm a i n l yd i s c u s st h ea p p l i c a t i o no fl d p ci nm i m o - o f d ms y s t e m a tt h e b e g i n n i n g ，i ti n t r o d u c e st h ea r c h i t e c t u r e ，d e c o d i n ga l g o r i t h m sa n dt h ep e r f o r m a n c e so fl d p c n e x t ，o nt h eb a s i so ff u r t h e rs t u d yo nt h ep r i n c i p l e so fo f d ma n dm i m o ，t h ep a p e rh a s p r o p o s e dt h es y s t e mm o d e lo fm i m o o f d m f i n a l l yt h ew r i t e ro ft h i sp a p e ra p p l i e sl d p ct o m i m o o f d ms y s t e ma n da d o p t st h es i m u l a t i o nc h a n n e lm o d e la d v i s e db yi e e e8 0 2 16 e ， w h i c hw i l ld oar e s e a r c ho nt h ep e r f o r m a n c e so fl d p cw i t hd i f f e r e n tc o d el e n g t h ，r a t ea n d m o d u l m i o nm e t h o d sa sw e l la st h ec o m p a r i s o nw i t l lt u r b oc o d ea p p l i e di nm i m o o f d m 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：魈犀 日期生! z 兰! 至 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：垄鲤导师签名： 南京邮电大学 硕士学位论文摘要 学科、专业：工 学通信与信息系统 研究方向： 无线数据与移动计算网络 作者：2 0 0 4 级研究生宋雪雁指导教师钱学荣 题目：l d p c 码在m i m o o f d m 系统中的应用分析 英文题目： a n a l y s i so np e r f o r m a n c e so fl d p cc o d e d m i m o - o f d m s y s t e m 主题词：l d p c 码正则码非正则码正交频分复用 多天线技术8 0 2 1 6 e k e y w o r d s ：l d p cc o d e sr e g u l a rc o d e si r r e g u l a rc o d e s o f d mm i m 0 8 0 2 1 6 e 南京邮l 乜入学硕一i j 研究生学位论文第一章绪论 第一章绪论 1 1信道编码的发展历史和l d p c 码的产生 在现代数字通信系统中，为保证各种数掘能够可靠、有效地传输，需要采用纠错编码 技术。近年来，随着无线数字通信的发展及各种高速率、突发性强的新业务的出现，研究 并利用好纠错编码技术就显得越来越重要。 纠错编码技术的起源可以追溯到1 9 4 8 年香农信息论的问世。从那时起，其理论不断 发展、成熟，成为- - f - 重要的学科。纠错码主要有分组码和卷积码两大类。无论是分组码、 卷积码，还是级联码、乘积码，相对于未编码的情况，编码所带来的性能上的改善存在一 个理论上限，即香农限( s h a n n o nl i m i t ) 。香农信息论指出了设计纠错码的方向，具有重 大意义。 香农第二定理( 也称信道编码定理) 【。2 峙旨出实现可靠通信所允许的传输速率的上限 为信道容量。在信道带宽受限和功率受限的条件下，带限a w g n 信道的信道容量c 表示 为： c = + 甜洲s m ， 其中w 为带宽，v 为信道输入带限信号的平均功率。如果传输速率为r ，= c ，则 诼c l o g _ , 旧鲁 m 2 ， 益：型( 1 - 3 ) 一：= 一 n o c w f 争1 叫驷竺上_ l n 2 - l 伽( 1 - 4 ) l o ，j 。i 。f o c w 表明带限信道中，传输速率达到信道容量时，可靠通信所需的最小比特能噪比为 一1 6 d b ，称之为香农限。香农限成为设计信道编码时试图逼近的信噪比下限。 信道编码定理的提出奠定了纠错编码的基石，此后，人们根据香农的思想，提出了一 系列设计好码和有效码的方法，使纠错编码技术得到了飞速的发展。 最初的研究主要集中在以代数理论为基础的线性分组码，出现了汉明码、循环码等一 系列好码。五十年代引进的卷积码在编码过程中引入了寄存器，增加了码元之i 、日j 的相关性， 堕塞堂皇奎兰堡圭里壅兰兰垡堡茎 至二雯堕丝 从而在相同的复杂度下获得比分组码更高的编码增益，同时也增加了分析和设计的复杂 度。随着各种卷积码译码算法的出现，尤其v i t e r b i 算法，促进了卷积码的深入研究和应 用。而后来出现的t c m ( 格栅编码调制) 技术，奠定了卷积码在通信领域中的主导地位。 八十年代和九十年代初，经过几十年的研究和实践，纠错编码理论和技术取得了很大 的发展。法国的c b e r r o u 等人在卷积码和级联码的基础上，于1 9 9 3 年提出了一种全新的 编码方案n 码，在信道编码的理论和应用中取得了突破性的进展。这种编码能够随 着码长的增加而逼近香农的理论极限，同时译码复杂度也可以接受。t u r b o 码采用并行级 联递归的编码器结构，是一种系统的卷积码。其译码算法主要有m a p 算法、l o g m a p 算 法、m a x l o g m a p 算法、s o v a 算法等。t u r b o 码具有独特的编码结构和译码思想：在 子编码器中采用了反馈型的系统卷积码，且在子编码器间引入交织器，减少了子编码器间 信息的相关性，模仿了随机编码的形式；同时在译码中采用了软输入、软输出的译码信息 和信息反馈的译码器形式，并引入了迭代译码的思想。 t u r b o 码的提出，被认为是信道编码的一个里程碑。1 9 9 5 年，m a c k a y 和n e a l 通过对 低密度码( m nc o d e ，m a c k a c y - - n e a l 码) 的研究重新发现了l d p c 码。l d p c ( l o wd e n s i t y p a r i t yc h e c k ) 码是一种可以用非常稀疏的奇偶校验矩阵或者二分图定义的线性分组码， 它最初是由g a l l a g e r l 3 1 于1 9 6 2 年提出的，所以也称为g a l l a g e r 码，这种编码由于校验矩阵 的稀疏性，使得译码复杂度与码长成线性关系。之后，d j c m a c k a y 、m n e a l 4 和n w i b e r g 等人对其重新进行了研究，发现它也具有逼近香农限的特性。现在它已成为通信技术中的 新的研究热点，其技术也日趋成熟。 l d p c ( l o wd e n s i t yp a r i t yc h e c k - - 低密度奇偶校验) 码是一种具有稀疏校验矩阵的 线性分组码；其性能优于t u r b o 码，具有能够逼近香农限的性能特性；具有较大灵活性和 较低的差错平底特性( e r r o rf l o o r s ) ；由于其校验矩阵的稀疏性，它的译码复杂度低于t u r b o 码，可以在线性复杂度内实现译码，并可以实现完全的并行操作，硬件实现复杂度低，可 以实现大吞吐量高速译码。 但l d p c 码的编码复杂度较高，虽然近来的研究表明它可以在线性时间内编码，但 是其复杂度相对于卷积码等可以即时编码的码来说仍然过大。同时在码长很长的情况下， 由于必须在接收到所有的信息比特后才能够进行编码，这就会给编码带来一定的时延，在 对实时性要求较高的场合，其应用会受到限制。另外，l d p c 码性能的优越性通常要在码 长较长时才能够体现出来，当码长为中短长度时，由于编码中短长度环的存在，编码的性 能会有所损失。 虽然如此，l d p c 码仍具有巨大的应用潜力，目前基于l d p c 在各通信领域应用的研 2 南京邮电大学硕士研究生学位论文第一章绪论 究在移动和固定无线通信、深空通信、光纤通信、卫星数字视频和声频广播、磁光全息 存储、电缆调制解调器和数字户线( d s l ) 等领域都有应用。本文的工作正是着眼于l d p c 码在b 3 g 和4 g 移动通信系统中的应用。 1 28 0 2 1 6 e 协议 宽带无线接入( b w a ) 是无线通信革命中最具挑战性的部分，它能解决从客户网到 核心网之间的接入瓶颈问题，所以近年来无线接入技术越来越受到人们的重视。针对这种 情况，i e e e 8 0 2 委员会于1 9 9 9 年成立了8 0 2 1 6 标准。i e e e 8 0 2 1 6 工作组成立于1 9 9 9 年 7 月，至今制定了一系列地标准；2 0 0 1 年1 2 月颁布地8 0 2 1 6 对使用1 0 - - 6 6 g h z 频段地 固定宽带无线接入系统地空中接口物理层和m a c 层进行了规范，由于其使用地频段较 高，因此仅能应用于视距范围内。2 0 0 3 年1 月颁布地8 0 2 1 6 a 对8 0 2 1 6 进行了扩展，对 使用2 l1 g h z 许可和免许可频段地固定宽带无线接入系统的空中接口物理层和m a c 层 进行了规范，该频段具有非视距传输的特点，覆盖范围最远可以达到5 0 k m ，通常小区半 径为6 1 0 k m 。另外，8 0 2 1 6 a 的m a c 层提供q o s 保证机制，可支持语音和视频等实时 性业务。这些特点使得8 0 2 1 6 a 与8 0 2 1 6 相比更具市场应用价值，真正成为用于城域网的 无线接入手段。8 0 2 1 6 d 是2 - - 6 6 g h z 的固定宽带无线接入系统的标准，是对8 0 2 1 6 、 8 0 2 1 6 a 和8 0 2 1 6 c 的修订，已经于2 0 0 4 年6 月在i e e e 8 0 2 委员会获得通过，将以 i e e e 8 0 2 1 6 - 2 0 0 4 名称发布。8 0 2 1 6 d 可以应用于2 1 1 g h z 非视距( n l o s ) 传输和l o 6 6 g h z 支持移动性的宽带无线接入空中接口标准。8 0 2 1 6 e 的标准化工作基本上是在 8 0 2 1 6 d 的基础上进行的。为了支持移动特性，8 0 2 1 6 e 又加入些新的特性。 8 0 2 1 6 e 工作组是为了实现宽带无线接入系统移动化而成立的标准制定组织。它的工 作基本上是在8 0 2 1 6 d 的基础上进行的。8 0 2 1 6 e 系统工作在2 - - 6 g h z ，双工方式为f d d 和t d d 。载波带宽可以选择在1 2 5 m h z - - 2 0 m h z 之间。在空中接口上，它的物理层实现 方式与8 0 2 1 6 d 基本一致，即采用的核心技术是o f d m 和o f d m a 。主要差别是对o f d m a 进行了扩展，可以支持2 0 4 8 点、1 0 2 4 点、5 1 2 点和1 2 8 点的快速傅里叶变换【5 】，以适应 不同载波带宽的需要，而8 0 2 1 6 d 中o f d m a 固定为2 0 4 8 点。另外，为了更好地支持移 动性，8 0 2 1 6 e 中的导频和前导信号也同8 0 2 1 6 d 中的有所不同。 南京邮电大学硕士研究生学位论文 第一章绪论 1 3o f d m 简介及多天线技术 正交频分复用( o f d m ，o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x i n g ) 实际上是一种特 殊的多载波传输技术，其主要思想是：将信道分成若干正交子信道，将高速数据信号转换 成并行的低速子数据流，调制到在每个子信道上进行传输。正交信号可以通过在接收端采 用相关技术来分开，这样可以减少子信道之间的相互干扰( i c i ) 。每个子信道上的信号带 宽小于信道的相关带宽，因此每个子信道上的衰落可以看成平坦性衰落，从而可以消除符 号间干扰。而且由于每个子信道的带宽仅仅是原信道带宽的一小部分，信道均衡变得相对 容易。可见，o f d m 技术能够有效对抗多径干扰与频率选择性衰落，并具有频谱利用率高， 成本偏低等优点。随着高速无线局域网和第四代移动通信概念的提出，o f d m 技术已成为 继c d m a 后的技术热点，并可能成为4 g 主要的调制标准。 不过o f d m 提高频谱利用率的作用毕竟是有限的，在o f d m 的基础上合理开发空间 资源，也就是多天线m i m o 技术，可以提供更高的数据传输速率。另外o f d m 由于码率 低和加入了时间保护间隔而具有很强的抗多径干扰能力。由于多径时延小于保护间隔，所 以系统不受码间干扰的困扰。 m i m o ( m u l t i p l e i n p u tm u l t i p l e o u t p u t ) 技术最早是由m a r c o n i 于19 0 8 年提出的，是 第三代和未来移动通信系统实现高数据率、高系统容量和提高传输质量的重要途径。 m i m o 技术能在不增加带宽的情况下成倍地提高通信系统的容量和频谱利用率。在室内， 电磁环境较为复杂，多径效应、频率选择性衰落和其他干扰源的存在使得实现无线信道的 高速数据传输比有线信道困难，多径效应会引起衰落，因而被视为有害因素。然而研究结 果表明，对于m i m o 系统来说，多径效应可以作为一个有利因素加以利用。m i m o 系统 在发射端和接收端均采用多天线( 或阵列天线) 和多通道。 在平坦衰落信道中，应用多天线系统时，将形成多个空间信道，而这些信道不可能同 时有很大的衰落。正是这种空间分集可以通过减小衰落冗量提高系统性能。o f d m 可以把 频率选择性信道转变成多个平坦衰落的子信道，因此可以把o f d m 与m i m o 技术相结合， 使系统达到既增加了信道容量，提高了频谱利用率，同时又可以抗多径衰落。 4 南京邮电大学硕上研究生学位论文第一章绪论 1 4 本文的内容和框架 第二章详细说明l d p c 码的概念，构造和编译码算法以及优异非正则码的选取。 第三章将主要介绍o f d m 系统和m i m o o f d m 系统模型和关键技术。 第四章讲述了本文仿真系统所采用的信道模型。 第五章将l d p c 码应用于m i m o o f d m 系统中，研究了信道模型的架构和优化，以 及仿真的结果及比较分析。 第六章总结本文所做工作，结合目前研究现状，指出本文有待改进并对可以进一步深 入探讨的问题进行了展望。 5 南京邮电入学硕i ：研究生学位论义 第一二帝l d p c 码的构造 第二章l d p c 码的构造 2 1l d p c 码的分类 简单的说，l d p c ( 低密度奇偶校验码) 码是一种具有稀疏校验矩阵的线性分组码。 低密度是指在校验矩阵h 中非零部分的比例很小，甚至和码长成线性关系。当码长很长 时，非零元l 的个数将远远小于0 的个数，校验矩阵就成了稀疏矩阵。图2 一l 是一个参 数为( n ，m ，i ，k ) 的校验矩阵h ，与一般的分组码是一样的，行数m 代表校验位的个 数，列数n 代表编码后的码字长度，j 代表每列中“l ”的个数，k 代表每行中“1 ”的个数。 可见，图2 一l 中的码字为n = 1 2 ，m = 9 ，i = 3 ，k = 4 。 h = 图2 1l d p c 码一例( f 则码) 1 9 8 1 年，n e r 【6 】关于图模型化编码结构的理论是纠错编码的另一个重大突破。他创 造性地把l d p c 码的校验矩阵h 用二分 訇( b i p a r t i t eg r a p h ) 的形式表示出来。二分图由比 特节点( b i tn o d e s ) 、校验节点( c h e c kn o d e s ) 及连接它们的边( e d g e ) 组成。图2 - 1 中的校验 矩阵对应图2 - 2 ( a ) 的二分图。左侧的节点为比特节点，代表了编码后的比特位，对应校 验矩阵中的列；右侧的节点为校验节点，代表了编码比特组成的校验方程，对应着校验矩 阵中的行：图中的边则代表左侧的某个比特出现在右侧的某个校验方程中，对应于校验矩 阵中的非o 元。 6 o 1 0 o o 1 0 0 o 0 1 o 1 o o 1 o 0 o ，o 0 0 o ， 0 o 1 0 0 1 o 0 1 1 0 0 o l o 0 1 0 l 0 o 1 o 0 1 o o 0 o o o 0 o 0 l o 0 0 l 1 0 o o o 1 o 0 1 1 0 0 l 0 o o 1 o o 0 o l 0 1 0 o 0 0 l 0 l 0 0 1 0 l o 0 南京邮电大学硕士研究生学位论文第二章l d p c 码的构造 b i tn o d e s b i tn o d e s n o d e s ( a ) 正则l d p c 码( b ) 非正则l d p c 码 图2 2l d p c 码的二分图 2 1 1 正则码和非正则码 上述例子代表的是一个二元域上的l d p c 码，其编码的校验矩阵h ，我们可以描述 为c ( h ) ：= x f ”：h x 7 = 0 ) 。图中我们可以看出矩阵中的每- n 有矾( - - 3 ) 个非零元，每 一行有d c ( = 4 ) 个非零元。即：编码码字x 中的每个比特参加矾个校验约束，而每个校验 约束包括4 个比特。在二分图中，矾、以分别表示与比特节点和校验节点相连的边数， 成为该节点的次数( d e g r e e ) 。当d e g r e e 为常数时，即所有比特节点的矾相同，而所有校验 节点的吐相同，这样的l d p c 码称为正则( r e g u l a r ) l d p c 码，简称正则码。否则当二分 图中的比特节点的次数各不相同或者校验节点的次数也有相应变化时，对应的l d p c 码 为非正则( i r r e g u l a r ) l d p c 码，简称非正则码。 7 南京邮电火学硕士研究生学位论文 第二章l d p c 码的构造 2 1 2 多进制l d p c 码 上述例子讲到的是二元域上的l d p c 码，事实上，l d p c 码的定义可以推广到多元域 g f ( q ) 。多进制l d p c 码具有较二进制l d p c 码更好的性能，而且研究表明在越大的域 上构造编码，它的性能便能得到越大的提高【7 1 。 这是因为对于l d p c 码来说，如果它的校验矩阵h 列重量足够大，那么它可以更加 接近于香农限；但是如果增加列重量，会使得二分图中圈的数目急剧增加，从而使得迭代 译码算法的性能下降。而在g f ( q ) 上构造的l d p c 码则可以解决此二者的矛盾，从而使得 译码性能获得了显著提高，但是在译码性能获得提高的同时译码复杂度也会必然增加。 2 2l d p c 码的编码 根据分组码编码理论我们知道：作为分组码，确定了生成矩阵g ( 校验矩阵日) ，也就 唯一地确定了可用码组。对于l d p c 码来说，构造码字就是要构造稀疏地校验矩阵h ， 再根据变换得到生成矩阵g 。 值得注意地是，l d p c 所说地稀疏是指的校验矩阵h 是稀疏的，但这并不说明其对 应地生成矩阵g 也是稀疏的，所以尽管直接给出生成矩阵g 对于码字地生成便于计算( 减 少了和g 之间地运算) ，但是我们还是要必须从构造校验矩阵h 入手。 如上文所述，校验矩阵日除了采用传统地矩阵直接表示之外，我们还引入了基于 t a n n e r 地二分图来描述校验矩阵日。相应地，我们采用地码字构造规则也从这两个方面 来入手。即，直接对校验矩阵h 进行设计，或者通过二分图节点之间地关系来调整改变 码字。 l d p c 码最初是由g a l l a g e r 【3 1 提出的，在刚提出时，构造方法极为简单，而且也仅仅 针对较短地正则二进制码。在近几年地研究中，特别是在非正则码提出之后，正则码已被 看作是非正则码地特例，因此，l d p c 码的构造问题就都统一到了对于度分布对函数( 兄，p ) 的优化问题上来。但是为了使文章更具连贯性，我们还是先从介绍g a l l a g e r 构造方法开始 讲起。 8 南京邮i 乜人学顺i j 训究生学位论义第二章l d p c 码的构造 2 2 1 正则l d p c 码的构造 g a l l a g e r l 3 1 给出了( 矾、以) f 则码的构造方法：对于码长为门的( 以、以) 正则码，他 将校验矩阵按行水平的分割为矾个相同大小的子矩阵，每个子矩阵的任- y u 都只包含一 个l 。第一个子矩阵以预定的方式构造，如可以用递减的形式包含所有的l ，矩阵的第f 行 所有的l 都分布在第( f 一1 ) 4 + 1 到i 4 列。其它下面的d 一1 个子矩阵都是第一个子矩阵的 随机排列。这种构造方法可如下表示： h o = 1 11 1 k - v 以 1 11 1 、， 以 1 11 1 、，j 以 风为第一个子矩阵，校验矩阵h 如下构造： h = h a 万2 ( h o ) 万以( 日o ) 这里兀为矩阵风的列置换。上面h 矩阵的第一个子矩阵为h o ， 置换代替，得到如下更加对称的构造方法： h = 7 i ( h o ) 万2 ( h o ) 万吐( 日o ) ( 2 - 1 ) ( 2 2 ) 也可以用h o 的任一 ( 2 3 ) g a l l a g e r 构造方法简单，但是也只能构造出一些较短的f 则码，而对于l d p c 码来 说，短码并不能体现出其性能上的优点，甚至短码的l d p c 码其性能还不如一些我们熟 悉的信道纠错码，只有在相关长度较大时彳能看到l d p c 码性能上的优势。当计算能力 突破了g a l l a g e r 提出l d p c 码时的情况，当l d p c 码再次被发现时，再次吸引我们的l d p c 长码的优异性能，但是g a l l a g e r 的方法对于长码的构造显然是不完善的，因此随着学术界 对对l d p c 码构造规则研究的深入，很多学者都提出了新的构造规则，在此方面最具代 表性的是m a c k a y 的构造规则【8 】如：c 1 a ，c 2 a ，c i b ，c 2 b ，c u l 2 a ，c u l 2 b 等，此处便不再一一细讲。 q 南京邮电大学硕士研究生学位论文第二章l d p c 码的构造 2 2 2 非正则l d p c 码的构造 对于一个固定码率天的正则l d p c 码来说，比特节点一定，则其次数越高，对其监 督的校验节点数越多则译码越准确；而同时，当校验节点一定，则希望次数越低越好，以 便更加有效的给相邻的比特节点传递信息。这两种情况必须合理地平衡以得到较好的效 果，因此非正则码在平衡两者关系上比正则码更具优势，这也正是我们研究和优化非正则 码的目的所在。 与正则l d p c 码不同，非正则l d p c 码校验矩阵列的码重不是固定的，而是经过优 化后确定的。从二分图的角度看，则比特节点和校验节点间的连接数目不是固定不变的， 通常用度分布对函数( d e g r e ed i s t r i b u t i o np a i r ) ( 2 ，p ) 来描述。 比特节点和校验节点的次数分布多项式分别定义为： 名( 石) = 丑x 卜1 ，p ( x ) = 尼x 卜1 j - 2 和 i = 2 式中丑( 尼) 表示与次数为f 的比特( 校验) 节点相连的边数在总边数中所占的比例， d 、矿表示比特和校验节点的最大次数。图2 - 2 ( b ) 茭j - - f f g 五= 0 4 ，乃= 0 6 ，岛= 0 6 ， p 4 = 0 4 的非正则码。 对于( a ，p ) 的非正则码，若给定码长为刀，码率为月，则校验节点数m = ( 1 一r ) n 。设 二分图中的总边数e ，则有： e 军孚= 协所j e 2 面n2 百m 。面 陋4 ) 由线性分组码的定义，假设校验矩阵以。是线性独立的，则码率为： r ：! 竺：l 一一m ( 2 5 ) 因此，( 兄，p ) 非正则码的码率为： 枷_ 1 粤堂 ( 2 - 6 ) j ：五( x ) 出 事实上，非正则l d p c 码的构造关键在于度分布对函数( 五，p ) 的确定，当( a ，p ) 确定 后，非正则l d p c 码和正则l d p c 的构造过程类似，即通过对分布值来确定比特节点和 南京邮电大学硕十形f 究生学位论文 第二章l d p c 码的构造 校验节点之间的关系，目前比较常用的方法有l u b y 构造方法和m a c k a y 构造方法等。下 面讲述下l y b y 方法【9 1 。 构造法i r ：令t 为矩阵中非零元的总数。t 由下式给出： t = 玎，z = 朋谚 ( 2 7 ) 例。 这罩甩是码长，m 是校验的个数，z 是重为，的列所占比例，万，是重为i 的行所占比 考虑一个具有t 个左节点 厶，厶) 和t 个右节点 蜀，r r ) 的二分图。对每一个重 量为j 的列，我们给_ ，个二分图的左节点标号，号码为该列的列号。相似的，对每一个重 量为f 的行，我们给f 个右节点标上该行的行号。将节点厶与节点足相连。 最后，随机的排列右节点的标号。这样就给出了非币则校验矩阵。当排列右节点的时 候，应避免重复边的出现：对矩阵所有的行，检查有相h 标号，的右节点是否与相同标 号的左节点相连。若有则重新排列，直至所有相同标号的右节点都与不同标号的左节点相 连。 构造法i r u l a ，i r u l b ： 如果矩阵的列中有重量为2 的列，可用一种由i r 变化而来的方法构造。在这些变化 后的方法i r u l a 和i r u l b 中，我们选择二分图右节点行标号的一种排列使得重量为 2 的列具有u l a 和u l b 构造法的构造形式。其它的构造方法与i r 法相同。 j c a m p e l l o 等【1 0 】提出采用扩展的b i t f i l l i n g 算法来设计具有n i - q , g 、高g i r t h 和b e r 性能良好的l d p c 码；s j j o h n s o n 和s r w e l l e r 11 提出一种基于k i r k m a nt r i p l e 系统的组 合设计方法，适合于构建短码长、高码率和在其t a n n e r 图( 即二分图) 中不出现坏长为 4 、g i r t h 至少为6 的币则l d p c 码：y k o u ，s l i n 和m f o s s o r i e r 1 2 1 3 探讨了基于有限 几何学的l d p c 码的结构，将编码简化至用循环码编码电路即可实现。 2 2 3 多元域l d p c 码的构造 经过研究表明，在g f ( q ) ( q = 2 6 ，b 是大于1 的整数) 上构造的l d p c 码性能要优 于g f ( 2 ) 上构造的l d p c 码。如图2 - 3 ，从t n f l 勺_ 2 分图中可以看到，( b ) 中的比特位五：、 一，和校验位z ：、z ：之间存在一个长为4 的坏。而( a ) 图中则不存在环，事实上这些短 环是影响l d p c 码性能的一个重要原因，而多进制l d p c 码l l - 进制l d p c 码优越也证 i i 南京邮电大学硕士研究生学位论文 第二章l d p c 码的构造 是因为其消除了二分图中可能存在的短环。 z l z 2 llo 30 2 z l l 磊： 互。 互： 10l000 olo l0o 0lo 0 ll l10olo x lx 2 而 x l lx 1 2x 21 x 2 2x 3 ix 3 2 ( a ) 基于g f ( 4 ) 的校验矩阵及其二分图( b ) 基于g f ( 2 ) 的校验矩阵及其二分图 图2 - 3校验矩阵及其二分图在g f ( 4 ) 和g f ( 2 ) 的表示图 多进制l d p c 码包括正则多进制l d p c 码和也非正则多进制l d p c 两种码。多进制 l d p c 码的构造类似于二进制l d p c 码的构造，对于正则多进制l d p c 码的构造关键在于 校验矩阵见的确认，其中影响较大的是d a v e y 和m a c k a y 提出的多进制l d p c 码的构造 规则：( 1 ) 生成矩阵巩，列重量， 2 ，行重量尽量一致；( 2 ) 非零元素取自g f ( q ) ( q = 2 b ) ； ( 3 ) 每行的元素将不再只是0 、1 ，而是适当地选取以保证向量z = h x 的熵最大( x 为假 想噪声的取样值) 。 对于非正则l d p c 码的构造，则需要先确认度分布对函数( 旯，p ) ，然后采用类似于正 则多进制l d p c 码的方法来构造出校验矩阵即可。 2 3l d p c 码的译码 l d p c 码在编码领域内备受亲睐的一个重要原因在于其译码算法上的优势。l d p c 码 是一种基于稀疏校验矩阵的线性分组码，使得它存在高效的译码算法；而稀疏矩阵的特性 使得连续突发差错对译码影响不大；可以实现完全的并行操作使得硬件实现复杂度低。 1 2 南京邮电大学硕士研究生学位论文第二章l d p c 码的构造 在2 0 世纪6 0 年代，g a l l a g e r 提出了两种l d p c 码的译码方法：一种是基于硬判决的 树型译码算法，一种是基于软判决的迭代译码算法。前者适用于短码、误码要求低的情况， 易实现复杂度低，后者则第一次在编码领域引入了软输入、软输出的迭代解码思想，此译 码算法虽会产生性能优异的码但是迭代比较复杂。后来，m a c k a y 等人【m l 在前人研究的基 础上，总结归纳了“和一积”( s p a ：s u m p r o d u c ta l g o r i t h m ) 算法，随着l d p c 码的校验 矩阵被模型化为其对应的二分图，r i c h a r d s o n 等人【l5 】在m a c k a y 的基础上又总结归纳出一 类基于二分图结构的消息传递( m p - m e s s a g ep a s s i n g ) 算法。m p 算法是一个算法类，其译码 性能随对译码消息( m e s s a g e ) 的量化阶数的增加而提高，但计算复杂度也会提高。当对 译码消息采用二阶量化时，m p 算法即成为o a l l a g e r 的硬判决译码算法；当量化阶数趋于 无穷，即当消息m e s s a g e 为连续变量时，m p 算法则成为信度传播( b p b e l i e f p r o p a g a t i o n ) 算法。此文中将主要讲到这三种解码算法。 2 3 1s p a 算法 算法中假设：n ( m ) = 刀：= 1 ) 表示参与校验方程坍的比特的集合，( 聊) 玎表示 集合n ( m ) 中去除元素刀后构成的集合，m ( n ) = m ：i - t = 1 表示比特刀参与的校验方程的 集合，m ( 刀) m 表示集合m ( n ) 中去除元素m 后构成的集合；g 二为比特n 从集合m ( 力) m 得到校验信息后被译作x 的条件概率：r l 为比特玎固定为x ，其它比特具有不同的分布且 概率为 g 。 y l ( m ) 刀) 时，校验方程朋成立的条件概率；码字x 的似然度( 1 i k e l i h o o d ) 定义为i 二1 斤，其中而表示码字x 中的第，? 位比特的取值，爿= i 写石f 元1 厕， r = 1 一爿，以为k 时刻的信道输出。 s p a 算法步骤如下： 初始化：q o = f o ，g k = 爿： 迭代： ( 2 a ) 水平迭代步骤 6 q 删= q o 。一g k ，对每个所、刀的取值，求出万= 兀曲册。， n e n ( m b n 再计算吃= 圭( 1 + 万厂卅) ，匕= 圭( 1 一万) ； 1 3 南京邮电大学硕士研究生学位论文第二章l d p c 码的构造 ( 2 b ) 垂直迭代步骤 对每个聊、门的取值和x = o ，1 ，更新g 二= 。片兀。， 用。e m ( n ) 、脚 其中为一个保证9 ：+ 如= 1 的可调变量： 计算“伪后验概率( p s e u d o p o s t e r i o rp r o b a b i l i t i e s ) ”： 靠= 片兀厂二，似= o ，1 ) ； ( 2 - 8 ) m d v t ( n ) 基于“伪后验概率”的判决： 若g ： 0 5 ，则= 0 ，反之，则毛= l ； 若根据“伪后验概率”判决得到的码字x 满足h x = 0 时，则译码结束，否则，从水平 迭代步骤( 2 a ) 开始新的迭代译码； 若经过最大迭代次数后仍然未找到满足h x = 0 的码字，则宣布译码失败。图2 4 示 出了在二分图上的译码过程中译码信息的传递。 o o 2 3 2l 帅算法 mn 4 5 8 口 u o o 图2 4l d p c 码解码信息的传递图 m m p ( m e s s a g ep a s s i n g ) 算法是一类基于二分图结构的算法。由于在译码过程中，消 息( m e s s a g e ) 沿着边在校验节点和比特节点之间传递，由此得名为m e s s a g ep a s s i n g 算法。 1 4 南京邮电大学硕士研究生学位论文第二章l d p c 码的构造 m p 算法中重要的一点是“消息独立性”。即在解码过程中，某节点m 沿着某条边e 发 送的消息应该与上次节点m 从边e 得到的消息无关，而是决定于和节点m 相连的除去边e 的其他边传递来的消息。这保证了在任一条边上只有外来消息的传递，而不会产生同一消 息反复迭代的情况。这是m p 算法优秀性能的保证。 m p 的算法假设同s p a 算法，算法步骤如下： 初始化：对每一个满足= 1 的( n ，删) ，比特节点的q o 。和9 k 分别被初始化为f o 和 爿。这里爿= 1 ( 1 + e x p ( 一2 a y 。a 2 ) ) ，r = l 一爿，儿是时刻门信道的输出。 第一步：这一步对每一校验节点m 及相应的每一个甩n ( m ) 计算两个概率测度：第 一个，匕：当毛= 0 ，其它的比特节点 矗：1 玎) 服从相互独立的概率分布 g 二，g _ ：，。) 时， 校验节点m 得到满足的概率，计算如下： 厂、 匕= l 尸( e 毛= o ix = o ) 兀翰x n , f( 2 - 9 ) l ：n q e n ( r e ) i n n e n ( m ) l n p l e n ( m ) n 第二个，匕，当= 1 时，校验节点m 得到满足的概率，计算如下 ，、 = i 尸( 毛= l lx = 1 ) 兀砩1( 2 - 1 0 ) l j 一h e n ( m l n ”。e n ( m ) nn e n ( m ) n 这里最外层的求和对集合( 册) 刀中比特节点所有可能的取值集合进行，该集合大小为 2 l 椰叫