（信号与信息处理专业论文）ldpc码校验矩阵构造及编码研究.pdf

studystudy onon parity-checkparity-check matrixmatrix constructionconstruction andand encodingencoding ofof ldpcldpc codescodes a a thesisthesis submittedsubmitted toto chongqingchongqing universityuniversity inin partialpartial fulfillmentfulfillment ofof thethe requirementrequirement forfor thethe degreedegree ofof mastermaster ofof engineeringengineering byby yuyu xiaoxiao supervisor:supervisor: associateassociate prof.prof. binglianbinglian zhuzhu major:major: signalssignals andand informationinformation processingprocessing collegecollegecollegecollege o o o of f f f communicationcommunicationcommunicationcommunication engineeringengineeringengineeringengineering ofofofof chongqingchongqingchongqingchongqing universityuniversityuniversityuniversity , , , , chongqing,chongqing,chongqing,chongqing, chinachinachinachina april,2008april,2008 重庆大学硕士学位论文中文摘要 i 摘要 近年来， 无线通信技术发展迅速， 第三代移动通信 3g 技术已经成功实现商用， 对第四代移动通信 4g 技术的研究也正在深入中。 无线通信环境的复杂和无线频谱 资源的有限要求这些通信系统必须满足信号的可靠性和频带的有效性。根据香农 信息论，信道编码技术是确保信息传送可靠的关键技术。 由 gallager 博士在 1962 年首次提出的低密度校验码 （low density parity check code，ldpc ）是一种性能优异的“好码”。20 世纪 90 年代末，d. j. c. mackay 和 r. m. neal 重新研究了 ldpc 码，并将 bp 算法应用到 ldpc 码的译码，这使得其 具有接近香农限的优异性能。ldpc 码的卓越性能来自于其校验矩阵h的特殊结 构以及迭代译码算法。本文深入研究了 ldpc 码的校验矩阵构造及编码方式。 由香农信息论出发， 系统回顾了编码理论的发展及 ldpc 码的发展， 介绍 ldpc 码基于图论的基本知识。重点推导和分析了 ldpc 码采用的几种典型的译码算法并 介绍了分析优化 ldpc 码性能的工具。 接下来介绍几种 ldpc 码校验矩阵的结构化构造和编码方式，包括有限几何 方式，准循环方式和旋转 ldpc 码。重点介绍了旋转 ldpc 码，并给出仿真 结果。 结构化方式构造的 ldpc 码编码方式灵活，但是性能较随机码有一定差距。 因此介绍了 ldpc 码校验矩阵的各种随机算法和线性时间编码方式，并重点研究 了渐进边增长（progressive edge progress，peg）算法。针对编码复杂度问题，在 原 peg 算法基础上提出一种新的改进，使得可以构造适合于线性时间编码的下三 角或者近似下三角校验矩阵。与 xiaoyu hu 的改进 peg 相比，本文的算法适用于 任意度数的符号节点分布对，并且适用于规则 ldpc 码。仿真结果显示，本文算 法构造出的（近似）下三角矩阵具有与原有算法构造矩阵同样的优异性能。由于 二进制 ldpc 码性能的局限性，探讨了用 peg 算法构造多进制（qray）ldpc 码 的问题。本文提出的改进算法也适用于多进制 ldpc 码线性时间编码。给出多进 制 ldpc 码的译码算法。仿真结果显示，随着有限域阶数的提高，多进制 ldpc 码的性能也随之提高。 关键词关键词关键词关键词：ldpc 码，校验矩阵，渐进边增长算法，线性时间编码，多进制 ldpc 码 重庆大学硕士学位论文英文摘要 ii abstractabstractabstractabstract in recent years, wireless communication is developing very fast. the third generation (3g) of mobile communication technology had been put into business applicationsandmoreresearchesaboutfourthgeneration(4g)ofmobile communication are still needed to be done. the complexity of wireless environment and the finites of wireless resources need the communication systems must satisfy both the reliability of the signals and bandwidth efficiency. according to shannon information theory, channel coding is the crucial technology for ensuring the reliability of information transmission. low density parity check code is a kind of good codes, which was first invented by r. gallager in 1962. in late 1990s, d. j. c. mackay and r. m. neal rediscovered ldpc code, and they brought belief-propagation (bp) algorithm into the decoding of ldpc codes and got the excellent performance achieving up to shannon limit. the outstanding performance of ldpc code comes from the special structure of parity check matrix and the iterative decoding algorithm. this thesis investigates the construction of parity check matrix and encoding algorithm of ldpc code. from the view of shannon information theory, gives a systematic review on the development of channel coding theory and ldpc code, introduces basic knowledge of ldpc on graphs. mainly introduces several typical decoding algorithms and optimization and analysis tools of ldpc code. thefollowingsectionintroducesseveralstructuredconstructionmethods, including finite geometry method, circulant matrix method androtation ldpc code. focuses onrotation ldpc codes, and gives simulation results. the encoding of ldpc codes constructed by structured methods is very easy and flexible, but there exists a gap between the performance of these ldpc codes and the performance of ldpc codes constructed by random algorithms. so introduces several random construction algorithms and linear-time-encoding algorithm. research focuses on progressive-edge-progress peg algorithm, and proposes an improved peg algorithm which can construct lower or almost lower triangular parity matrix suitable for linear-time-encoding.compared with xiaoyu hus original improvement, this new algorithm can be applied to any symbol degree distribution pair and also regular codes. simulation results show, the performance of the ldpc codes constructed by algorithm proposed by this thesis is as excellent as the original peg algorithm. due to the limit of 重庆大学硕士学位论文英文摘要 iii binary ldpc codes, have a discussion on the construction of qary-ldpc codes using peg method. and the improved peg algorithm proposed by this thesis is also suitable forconstructiongqrayparity-checkmatrixforlinear-time-encoding.gives correspondingdecodingalgorithm.simulationshowsthattheperformanceof qary-ldpc codes is improved with the increase of the order of finite field. keywordskeywordskeywordskeywords： low density parity check codes, parity-check matrix, progressive-edge-progress, linear-time-encoding, qary-ldpc code 重庆大学硕士学位论文目录 iv 目录 中文摘要中文摘要.i 英文摘要英文摘要.ii 1 1 1 1绪绪论论.1 1.1 数字通信与信道编码数字通信与信道编码.1 1.2 信道编码的发展概况信道编码的发展概况.2 1.3 ldpcldpcldpcldpc 码的发展和现状码的发展和现状.4 1.4 课题主要研究内容及章节安排课题主要研究内容及章节安排.7 2 2 2 2 ldpcldpcldpcldpc 码的定义和编译码基本原理码的定义和编译码基本原理.8 2.1 ldpcldpcldpcldpc 码的定义和码的定义和 tannertannertannertanner 图表示图表示.8 2.1.1 ldpc 码的定义及其描述.8 2.1.2 ldpc 码的 tanner 图表示.9 2.1.3 ldpc 码的性能分析.11 2.2 ldpcldpcldpcldpc 码的编码码的编码.12 2.2.1 gallager 的校验矩阵构造方式. 12 2.2.2 直接编码方式.12 2.3 ldpcldpcldpcldpc 码的译码码的译码.13 2.3.1 置信传播算法.13 2.3.2 基于概率量度的 bp 译码算法.16 2.3.3 基于对数似然比（llr）量度的 bp 译码算法.18 2.4 密度进化理论密度进化理论.20 2.5 ldpcldpcldpcldpc 码的性能码的性能.23 2.6 本章本章小结小结.24 3 3 3 3 ldpcldpcldpcldpc 码校验矩阵的结构化构造方式及编码码校验矩阵的结构化构造方式及编码.25 3.1 有限几何构造的有限几何构造的 ldpcldpcldpcldpc 码码.25 3.1.1 欧式有限几何.26 3.1.2 欧式有限几何 ldpc 码（eg-ldpc）.26 3.2 准循环准循环 qc-ldpcqc-ldpcqc-ldpcqc-ldpc 码码.28 3.2.1 代数初步知识.28 3.2.2 阵列 ldpc 码.29 3.2.2 阵列码的代数特征.30 3.2.3 阵列码子码和阵列码的编码.31 重庆大学硕士学位论文目录 v 3.2.4 阵列 ldpc 码的性能.32 3.2.5 stf 码和 fossorier 码.32 3.3旋转旋转 ldpcldpcldpcldpc 码码.33 3.3.1 旋转 ldpc 码的定义.33 3.3.2 旋转 ldpc 码的编码.35 3.3.3 码距d2和围长的设计.36 3.3.4 仿真结果.37 3.4 本章小结本章小结.37 4 4 4 4 ldpcldpcldpcldpc 码校验矩阵的随机构造方式及线性时间编码码校验矩阵的随机构造方式及线性时间编码.38 4.1 ldpcldpcldpcldpc 码校验矩阵的随机构造方式码校验矩阵的随机构造方式.38 4.1.1 mackay 的构造方式.38 4.1.2 超轻（ultra light）构造方式.39 4.1.3 完全随机方法.40 4.1.4 比特填充（bit-filling）算法和扩展比特填充（extended bit-filling）算法.41 4.1.5 渐进边增长算法（progressive edge growth peg）.41 4.1.6 实验数据与仿真结果.44 4.2 线性时间编码算法线性时间编码算法.46 4.3 一种新的改进一种新的改进 pegpegpegpeg 算法实现算法实现 ldpcldpcldpcldpc 码线性时间编码码线性时间编码.48 4.3.1 改进算法的描述.48 4.3.2 仿真结果及分析.50 4.4 用用 pegpegpegpeg 算法构造多进制算法构造多进制 ldpcldpcldpcldpc 码校验矩阵码校验矩阵.51 4.4.1 多进制 ldpc 码与校验矩阵的构造.51 4.4.2 多进制 ldpc 码线性时间编码.52 4.4.3 多进制 ldpc 码的译码算法.53 4.4.4 仿真结果.54 4.5 本章小结本章小结.55 5 5 5 5 总结与展望总结与展望.56 致致谢谢. 56 参考文献参考文献. 58 附附录录. 62 重庆大学硕士学位论文1 绪论 1 1绪论 1.1 数字通信与信道编码 通信系统旨在将信源产生的信息可靠、高效、有时还需保密的传递到信宿。 所谓可靠，是使信源发出的信息经过信道传输以后，尽可能准确、不失真的再现 在接收端。保证通信的可靠性是所有通信系统追求的首要目标。所谓高效，是指 在一定的时间内如何传输尽可能多的信息量，或在每一个传送符号内携带尽可能 多的信息量1。信息传输的有效性是通信系统追求的另一个重要目标。 信息理论发展的早期，人们认为通信的可靠性和有效性是对立的矛盾，满足 其一必须以牺牲另一为代价，为了在有扰通信信道上实现任意小错误概率的信息 传输的唯一途径就是把传输速率降低至零2。1948 年，香农3shannon 发表了具有 里程碑意义的论文“通信的数学理论”， 他利用概率测度和数理统计的方法系统的讨 论了通信的基本问题，得出了几个重要并且带有普遍意义的结论，由此奠定了现 代信息论的基础。香农信息理论的核心是，否定了通信的可靠性和有效性是不可 调和的矛盾，在通信系统中能够实现高可靠性和高有效性的通信，前提是使用适 当的编码手段。 根据香农信息理论，数字通信系统的基本组成如图 1.1 所示： 信 源信 源 编 码 器 信 源 译 码 器信 宿 信 道 编 码 器 信 道 译 码 器 调 制 器 解 调 器 信 道干 扰 编 码 信 道 调 制 信 道 图 1.1 数字通信系统的模型 fig.1.1 model of digital communication system 香农信息编码理论包括信源编码理论和信道编码理论，信源编码理论关注的 是将信源输出的离散或者模拟消息有效的转化为二进制比特序列的过程，也称为 数据压缩；信道编码理论关注的是按照某种规则引入适量的冗余比特，以克服信 重庆大学硕士学位论文1 绪论 2 息传输中受到的噪声和干扰的影响。因此，信道编码也被称为纠错码 (error-correcting code)或者是差错控制编码(error control code)。本论文研究信道 编码领域的问题。 年， 香农3在“通信的数学原理”中给出了有关信息传输的最基本的定 理有噪信道编码定理，即香农第二定理。 定理定理（有噪信道编码定理）设离散无记忆信道的信道容量为c，信息传输 速率为r，为任意小的正数， 则只要rc。图 2.1 给出一个(20,3,4)规则 ldpc 码的校验矩阵。 11110000000000000000 00001111000000000000 00000000111100000000 00000000000011110000 00000000000000001111 10001000100010000000 01000100010000001000 00100010000001000100 00010000001000100010 00000001000100010001 10000100000100000100 01000010001000010000 00100001000010000010 00010000100001001000 00001000010000100001 图 2.1（20，3，4）规则 ldpc 码校验矩阵 fig.2.1 (20, 3, 4) parity check matrix of regular ldpc code 重庆大学硕士学位论文2 ldpc 码的定义和编译码基本原理 9 2.1.2 ldpc 码的 tanner 图表示 m. tanner9提出用图论中的二部图 (bipartite graph) 概念来表示 ldpc 码， 这 种表示 ldpc 码的二部图被称为 tanner 图。tanner 图与 ldpc 码的校验矩阵h相 对应。 定义定义 2.1 二部图二部图 若图g的节点集v可以划分为两个子集 1 v和 2 v，且满足 vvv= 21 ，= 21 vv，使得任意边ee，e的一个端点属于集合 1 v，另一个端 点属于集合 2 v，则称图g为二部图。若节点集 1 v中所有的节点的度数都相同并且 节点集 2 v的度数也都相同，则称g为规则二部图，否则为不规则二部图。 设一个( , , ) rc n w w码c具有校验矩阵 () ijm n h =h h h h， 其 tanner 图模型可以表示为 一个二部图。码字向量 12 ( ,) n x xx=x x x x表示为一组变量节点，也称为符号节点 : 1, j xjn=，校验约束表示为一组校验节点，也称为约束节点 : 1, i z im=。 本文以后一直称为变量节点和校验节点。仅当1= ij h时，节点 j x和 i z之间由一条边 连接，节点 j x和 i z互称相邻节点，其间连接的边称为这两个节点的相邻边。对于 每一个节点，与之相连的边数成为该节点的度数(degree)。对于规则码( , , ) rc n ww， 每个变量节点与 c w个校验节点相连，每个校验节点与 r w个变量节点相连。所以变 量节点的度数为 vc dw=，校验节点的度数为 cr dw=。 =+ =+ =+ =+ 0 0 0 0 1001 0110 1010 0101 1010 0110 1001 0101 8542 7632 8641 7531 xxxx xxxx xxxx xxxx 是一个(8, 2, 4)短码的校验矩阵及校验方程组 图 2.2 tanner 图表示 fig 2.2 tanner graph representation 图 2.2 是相应的tanner 图表示。图中 “ ”表示变量节点，“”表示检验节点。 四个校验节点表示每个码字必须满足的二元线性方程。因为每个变量节点的度数 都是 2，每个校验节点的度数都是 4，所以图 2.1 是规则 tanner 图。 对于不规则 ldpc 码，其 tanner 图中各节点度数不一定相同，通常用边分布 x1x2x3x4x5x6x7x8 z1z2z3z4 重庆大学硕士学位论文2 ldpc 码的定义和编译码基本原理 10 序列 12 ,., dl 和 12 ,., dr 表示。其中， i 表示与度为i的变量节点相连的 边数占总边数的比率。 j 表示与度为j的校验节点相连的边数占总边数的比率，dl 和dr分别表示变量节点和校验节点的最大度数，有 1 1 dl i i = = 及 1 1 dr j j = = 。这里采用 边的度分布，而不用节点的度分布来表示，是因为边的度分布表示有助于分析其 在给定译码算法下的实际性能和理论性能的上下界。边度分布序列还可以用多项 式表示，即： 1 1 ( ) dl i i i xx = =(2.1) 1 1 ( ) dr j j j xx = =(2.2) 满足 1 (1) dl i i = =和 1 (1) dr j j = =。 规则 ldpc 码可以看作是不规则 ldpc 码的特例，如对于(n,3,6)码，相应边的 度分布多项式分别退化为 2 ( )xx=和 5 ( )xx=。 设 ldpc 码对应 tanner 图中的边的总数为e，根据边的度分布多项式可以得 到度为i的变量节点个数为 ii vei=，度为j的校验节点的个数为 ij uej=，则 变量节点的总数n和校验节点的总数m分别为： 1 11 0 ( ) dldl ii ii nveiex dx = = (2.3) 1 11 0 ( ) drdr ij jj muejex dx = = (2.4) 当矩阵满秩时，不规则码的码率表示为 11 00 ()1( )( )rnmnx dxx dx= (2.5) 矩阵不满秩时，实际的码率要比r略高一些。 与二进制 ldpc 码的定义类似，可通过 tanner 图来定义多进制（qray）ldpc 码38。由于多进制 ldpc 码的码字分量的取值于有限域 gf(q)，因此，其取值不限 于 0 和 1，而是在 0 到1q之间取值。多进制 ldpc 码的 tanner 图的结构与二进 制 ldpc 码相同，不同之处在于，多进制码字的 tanner 图中每一条边对应校验矩 阵中的非零元 mn h，每一个变量节点对应( )gf q上的一个符号（ 2 logq比特） ，而不 是一个二进制符号（1 比特） 。 重庆大学硕士学位论文2 ldpc 码的定义和编译码基本原理 11 110 203 z1 z2 x1x2x3 z1z2 x1x2x3 1 1 2 3 图 2.3 gf（4）域上的多进制 ldpc 码校验矩阵等效 tanner 图 fig. 2.3 tanner graph of qary-ldpc parity check matrix ongf(4) 2.1.3 ldpc 码的性能分析 ldpc 码是线性分组码，因此其纠错性能取决于最小汉明距离 0 d，码率一定 的条件下， 如果 0 d越大则纠错能力越强2， 同样的译码方式错误概率也越小。 但是， 寻找线性分组码的最小码重是 np-完全问题，不能用计算机求出这个问题的解。 而 由于 ldpc 码的性能还取决于校验矩阵的在对应的 tanner 图结构中的环长，具有 较大的最小环长的 ldpc 码更可能有较大的码重。因此可以将问题转化为寻求使 校验矩阵对应的 tanner 图中环长较大的方法。环长对译码性能的分析如下36： 由于 ldpc 码译码采用迭代译码，其算法的推导是基于在节点间传递的信息 统计独立。当 ldpc 码对应 tanner 图中存在短环时，某一节点发出的信息经过一 个环长的传递会被传回本身，从而造成自身信息的叠加，破坏了独立性的假设， 会影响迭代译码的效果。当环长为 4 时，这样的短环会严重的影响译码性能。最 小的环长称之为围长(girth)。 . . . . . . .1.1. . .1.1. . 图 2.4 环长为 4 的环在校验矩阵和 tanner 中的形式 fig. 2.4 4-loop circle in parity check matrix and tanner graph mackay8等指出消除环长为 4 的环对码的性能有很大提高，继续消除其他长 度的短环对提高码的性能的效果越来越不明显。wiberg37证明基于有环 tanner 图 的 ldpc 码具有较低的译码复杂度。mackay 指出只要校验矩阵满足任意两列之间 交叠重量小于 2 便不含环长为 4 的环。 xiaoyu hu19指出， 较大的围长有利于译码， 重庆大学硕士学位论文2 ldpc 码的定义和编译码基本原理 12 并且会显著的影响最小距离从而加强在高信噪比区域的译码性能。 2.2 ldpc 码的编码 ldpc 码的编码包括两个独立的部分，包括校验矩阵h的构造和针对特定结 构的校验矩阵h采用相应的编码方式。这里仅仅只作最基本的讨论，详细研究放 在第三、四章进行。 2.2.1 gallager 的校验矩阵构造方式 gallager4采用了稀疏矩阵的随机置换和级联来生成校验矩阵。先通过确定的 方式构造规则校验矩阵，然后由该矩阵的所有列做随机排列组合形成一系列的规 则矩阵，再将这些规则子矩阵组合成所需校验矩阵。 设 ldpc 规则码为( , , ) rc n ww，其校验矩阵结构如(2.6)式所示： 1 2 c w h h h h = (2.6) 子矩阵具有如下结构，每一个子矩阵都是大小为 r w，行重为 r w，列重为 1。 首先构造 1 h， 使得其第i行从第(1)1 r iw+ 到 r iw列均含有“1”。 其他子矩阵是 1 h 通过随机列置换，即对列重新排列得到的。gallager 构造的(20,3,4)矩阵如图 2.1 所 示。gallager 通过准循环结构的方式构造校验矩阵的思想影响了后来的研究者， 某 些准循环 ldpc 码就是用类似的方式构造的。 2.2.2 直接编码方式 ldpc 码属于线性分组码，按照线性分组码的编码方法，通常需要将校验矩阵 h 通过高斯消去（行与行之间进行模 2 相加）及列交换转化成 0 | m hp i=的新矩 阵，其中i为m阶的单位矩阵，p为()mnm的矩阵。然后得到生成矩阵 | t n m gip =。编码的时候， 将信息比特 1 ()n m s 乘上生成矩阵 ()n mn g 得到输出 的码字 1n c。由于高斯消去破坏了矩阵的稀疏性，所以这样做直接编码的复杂度为 2 ()n。如(2.7)所示，其中r为码率。 2 ()(1) 22 nmmrr n =(2.7) 实际应用中 ldpc 码码长n较长，采用直接编码方式复杂度过高，richardson 提出了一种通用的线性编码方式，具体将在第三章详细讨论。 重庆大学硕士学位论文2 ldpc 码的定义和编译码基本原理 13 2.3 ldpc 码的译码 2.3.1 置信传播算法 mackay 和 neal8首先将人工智能领域的置信传播(belief propagation, bp)算法 引入到 ldpc 码的译码。他们将比特节点的集合与校验节点的集