规则低密度奇偶校验码的研究

规则低密度奇偶校验码的研究 华中科技大学博士学位论文规则低密度奇偶校验码的研究姓名陶雄飞申请学位级别 博士专业微电子学与固体电子学指导教师邹雪城20070606 华 中 科 技 大 学 博 士 学 位 论 文 摘 要 1948年香农首次阐明了在有扰信道上实现可靠通信的方法 了信道编码是信息可靠传输的有效手段信道编码技术成为通信系统的核心之 一。香农信息论一直是信道编码技术的理论基础指导着信道编码技术的研究与发展。 Gallager于1962年提出的低密度奇偶校验码Low-Density Parity-Check CodesLDPC是 一类利用稀疏矩阵或二部图定义的线性分组码然而限于当时的计算能力难以逾越的 复杂程度使得LDPC码未能引起太多重视。近年来随着计算能力的大幅提升以及 VLSI超大规模集成电路技术的成熟LDPC技术的价值被重新发掘成为近年来信道编 码领域的研究热点并取得了不少新的成果。本文的主要工作以LDPC码为基础围绕 着它的一些关键技术展开研究。 首先研究的是LDPC码的编译码算法。由于直接编 码破坏了校验矩阵的稀疏性复杂度较高本文提出了一种利用纠删译码进行编码的方 法预处理过程简单在预先计算出几个关键的校验比特信息后将剩余的校验比特看作 是被删除的比特进行迭代解码这个解码的过程实际上是方程组回代求解的过程十分 有利于硬件实现。在译码方面本文重点研究了消息传递Message Passing Algorithms 的迭代算法并对BP译码算法进行改进从优化译码程序的流程结构的角度出发对算 法进行简化减少了一次迭代过程中的循环次数在不损失解码性能的同时加快了解码 速度。 消息传递算法是基于无环图推出的当应用于LDPC码译码时其Tanner图中的 短环会影响译码性能因此圈长最小环长girth是LDPC码的一个重要的参数。在构造 LDPC码的时候应该使所构造的码的圈长尽可能的大本文提出了几种构造规则码的 方法采用这些方法所构造的LDPC码均具有较大的圈长构造列重为2的码采用递推 构造法码的圈长可以达到12或16构造列重大于2的码采用三维点阵构造法可以构造 出圈长为8的规则码此外还提出了一种在二维点阵中构造圈长为10列重为3的码。除 了具有较大的圈长所构造的码还具有循环和准循环特性编码容易利于实际应用。 分 析LDPC码性能的主要方法除了圈长外还有密度进化DE:Density Evolution法和 计算最小距离等方法。最小距离与码的纠错能力有直接的关系本文在对目前几种主 要的计算最小距离的方法进行研究后提出了一种基于环扩展的计 I 华 中 科 技 大 学 博 士 学 位 论 文 算最小距离的思想对于Tanner图中的小环将环中的变量 节点逐级扩展成树后结合纠删译码得到LDPC码的停止集保留其中的小重量码字从 而计算出码的最小距离计算方法具有较低的复杂度。 关键词LDPC码 快速编码 迭 代译码 二维/三维点阵构造 递推构造 圈长 最小距离 II 华 中 科 技 大 学 博 士 学 位 论 文 Abstract In 1948 Shannon clarified the approach for reliably communication is channel coding. As one of the cores in communication system the channel coding arrests more and more engineers attention. The Shannon information theory is elementary in the field of channel coding technology which also guided their developments. LDPCLow-Density Parity-Check Codes who have sparse check matrix and can be denoted by bipartite graph were proposed by Gallarge in 1962. The codes have performance approaching Shannon limit their decoding procedure have low complexity and can be operated parallelly which suits for hardware application. The LDPC codes attracted few attentions at that time due to the computation limit until the invention of Turbo codes. Since the rediscovery of LDPC codes in recent years there has been renewed interest in LDPC codes. This paper first researched LDPC codes in encoding and decoding respectively. On the hand of encoding the direct encoding destroys the sparse property of the check matrix the complexity was high. The paper studied some simplify encoding algorithm which can encode under approximately linear complexity and proposed an algorithm based on iteratively erasure decoding which also has approximately linear complexity and the preprocessing is simplerthe algorithm calculated a few key check bites first then regarded the remain check bits as erased those erased bits can be recovered through the iterative erasure decoding. On the other hand of decoding iterative message passing algorithm has been employed to decode. In each iteration the message was propagated between the check nodes and bit nodes in the Tanner graph. Having studied the iterative algorithm based on probability domain and LLR domain a simplified BP algorithm was present. The algorithm improved the flow of decoding procedure and speeded up the decoding by decreasing the number of loops in each iteration. Tanner graph for LDPC codes have cycles when the number of iterations reach the quantity of the minimum cycle girth the messages propagated between the nodes became dependent which will hurt the performance. So the girth should be considered in III 华 中 科 技 大 学 博 士 学 位 论 文 the construction of LDPC codes. The paper reviewed some present construction and proposed some design method to construct LDPC codes with large girth. The first one was based on 3D lattice under this construction girth 8 LDPC codes can be designed with column weight greater than 3 for column weight 3 codes design a method based on 2D lattice was present the last construction was recursive one which was used to designed column weight 2 LDPC codes with girth 12 or 16. All the codes are cyclic or quasi-cyclic which is easy to encode and store. Due to the important role of girth the paper studied the girth distribution of LDPC codes. Beside it density evolution and code distance are also studied. Density evolution is a very important tool to analyze LDPC code which is used to calculate the capacity of an ensemble of codes with specified degree distribution additionally it can solve the problem of finding good degree distribution. Beside it minimum distance is also important for error correcting codes. The most popular way to compute the code weight distribution was based on impulse-error method. Different from it a novel algorithm based on cycle-expanding was introduced. For a cycle in the Tanner graph a tree was expanded from the bit nodes in the cycle in each depth employing the erasure decoding algorithm to find stopping set due to a code word can be regarded as a special stopping set so the algorithm can find a lot of low weight code words the lowest weight found was the minimum distance of the LDPC code. Comparing with other algorithm it was relatively fast. KeywordsLow-Density Parity-CheckLDPC codes fast encoding iterative decoding construction based on 2D/3D lattices recursive construction girth minimum distance IV独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的 研究工作及取得的研究成果。尽我所知除文中已经标明引用的内容外本论文不包含 任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人 和集体均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名 日期 年 月 日 学位论文版权使用授权书 本学位论文作者完全 了解学校有关保留、使用学位论文的规定即学校有权保留并向国家有关部门或机构 送交论文的复印件和电子版允许论文被查阅和借阅。本人授权华中科技大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。 保 密 在____________年解密后适用本授权 书。 本论文属于 不保密?。 请在以上方框内打“?” 学位论文作者签名 指导教师签名 日期 年 月 日 日期 年 月 日 华 中 科 技 大 学 博 士 学 位 论 文 1 绪论 1.1信道模型和信道容量 现代社会己步入信息时代在各种信息技术中信息有效和可靠的通信起着至关重要的作用。通信的目的是要把对方不知道的信息及时、可靠的传给对方。因此一个通信系统传输信息必须可靠且快速而实际系统中可靠与快速往往是一对矛盾可靠性用误比特率BER衡量有效性以信息传输速率R来度量。早期的人们普遍认为1通信系统的可靠性与有效性是一对不可调和的矛盾一方的改善总是以牺牲另一方为代价要保证信息可靠的传输只有两个自由度可选择一是提高系统的信噪比二是选用不同的调制方式。当系统的功率受限时在有扰信道上实现以任意小错误概率的信息传输、唯一途径就是把信息传输速率降低至零。1948年香农Shannon发表了关于信息和编码理论的奠基性的论文《通信的数学理论》为通信的可靠传输提供了理论基础2。在这篇论文中他首次阐明了在有扰信道上实现可靠通信的方法指出实现有效可靠地传输信息的途径就是信道编码。 接收机采用信道编码技术来或纠正在无线信道中传输引入的一部分或全部的误码。解码是在接收机进行解调之后执行的所以编码被看作是一种后检测技术。 Shannon信道编码定理认为对任意一个平稳离散无记忆有噪信道都有一个固有的量称之为信道容量。只要信息的传输速率低于信道容量总可以找到一种编码方法使得差错概率任意的小反之如果信息的传输速率超过信道容量则不存在这样的编码方法。这就是著名的信道编码定理。信道编码定理表明信道容量正好等于信息传输速率的上确界任意给定的信源都有一个量称为熵entropy它表征了信源的平均不确定性。 由香农信息论的基本原理由于编码后会使信道传输速率提高这样就扩展了信道的传输带宽。信道编码通常分为两类分组编码和卷积编码。香农信息论一直是信道编码技术的理论基础和指导它一直在指导着信道编码技术的发展。 最简单的通信系统模型如图1.1所示某时刻信源X发送消息符号集合I中的某一个符号x输入到信道中信宿接收的Y是可能符号集合O中的某一个符号y X和Y都是随机变量x和y是取值。 1 华 中 科 技 大 学 博 士 学 位 论 文 图1.1 简单的通信系统模型 有关的概率分布定义如下 xXPxp 信源的先验概率 1.1 yYPyp 1.2 xXyYPxyp 信道的转移概率 1.3 yYxXPyxp 后验概率 1.4 yYxXPyxp 1.5 由此信源X所包含的信息量为 ???xxpxpXHlog2 比特每信源符号 1.6 通过有噪信道后信宿Y接收到的有关X的信息量称为X和Y的互信息 YXHXHYXI?? 比特每信道符号 1.7 其中表示接收Y后信道损失的X的信息量。对于特定的信道互信息是信源x的概率分布的?型凸函数互信息是概率分布的函数函数的平均值小于或等于平均值的函数则一定存在一种信源的概率分布使互信息达到最大值这个最大值就称为信道容量3。 ????xyyxpyxpYXHlog2xypYXIxpFYXIxEFxFE?maxYXICxp 比特每信道符号 1.8 如果信道每秒传送个符号则信道容量可用信息传输速率表示为 sRsxptRYXIC??max 1.9 表示信道传输的最大信息量是衡量信道信息传输能力的指标。 如果信道的输出只与信道的即时输入即与信道输出对应的信息符号有关 2 华 中 科 技 大 学 博 士 学 位 论 文 则称信道为无记忆memoryless信道即如果信道输入为X x1x2x3…xn并且信道输出为Y y1y2y3…yn则有 ...332211nnxypxypxypxypxyp 1.10 这样使得信道可以完全由输入符号X和输出符号Y以及pyx决定。 下面讨论几种常用的离散无记忆信道Discrete Memoryless Channel DMC的信道模型图1.2和信道容量。 1-p1-ppp01011-p1-ppp0101p0yp1y01y a BSC信道 b BEC信道 c BIAWGN信道 图1.2 二进制输入信道模型 1. 二进制对称信道Binary Symmetry Channel BSC 二进制对称信道是一类简单信道只由一个参数p决定又因为具有对称的性质所以能简化一些复杂的分析特别是在编码应用研究中BSC信道为基本的信道模型之一。在BSC信道中输入符号为X-11输出符号为Y-11并且信道转移概率为ppp????1111如图1.2a所示其信道容量为 1pHCBSC?? 1.11 其中为二进制熵函数。 pH2. 二进制删除信道Binary Erasure Channel BEC 二元删除信道为一个非平凡的简单信道信道的输入符号集X-11信道的输出符号集为Y-101输出符号0表示删除即码符号丢失二元输出符号与二元输入符号相等的概率为ppp??????11111输出符号丢失的概率为如图1.2b所示这类信道上的编码称为纠删码Erasure Code又称为复损码Loss-Resident Code该信道可以扩展为包删除信道Packet ppp??1010 3 华 中 科 技 大 学 博 士 学 位 论 文 Erasure Channel PEC即一个数据包分组要么正确接收概率为1-p要么数据分组丢失概率为pPEC信道的典型例子为Internet。BEC信道容量为 pCBEC??1 1.12 3. 二进制输入加性高斯白噪声信道Binary-Input Additive Gaussian White Noise Channel BIAWGN 二进输入加性白高斯信道是常用的通信系统的信道模型如图1.2c所示输入基带符号集X-11输出符号集Y为连续实数集R输入符号和输出符号之间满足关系YXN其中N为均值为0方差为σ2的高斯白噪声那么为均值为x方差为σ2的服从高斯分布的随机变量的密度函数。 xyp由于BIAWGN信道的条件概率密度函数满足对称条件所以信道容量为在信源等概分布2/111??XPXP时的输入输出之间的互信息所以BIAGN信道的信道容量为 ?????dxeeHCxxBIAWGN22221/2211211σσπσ 1.13 1.2 接近信道容量的信道编码技术 从通信的基本要求信息传输的有效性和可靠性方面来看编码调制处于核心的位置。从第三代及以后移动通信系统的发展方面来看这些系统的共同特征是信息的传输越来越高效由此带来对于信道编码及载波调制的要求也就更高信道编码是保证信息传输可靠性的重要措施在现代技术条件下传统上认为实现复杂性较高的迭代译码算法的实现屏障已被打破。 自从Shannon证明了信道编码定理以来编码理论的主要目标是构造实用的逼近容量。 定义1.1好码在给定信道中能够以任意小的错误概率完成任意小于信道容量的非零速率通信的码就称为好码good codes否则称为坏码bad codes。 定义1.2实用码:在给定信道中能够以码长多项式的时间和空间复杂度完成编码和译码的码就称为实用码practical codes。 通信专家们致力于寻求设计方案以达到这一个信息界。对于寻找能够比较好地 4 华 中 科 技 大 学 博 士 学 位 论 文 接近信道容量的一些好码典型方法是采用代数分组码和卷积码但是对于每类码是否具有现实可行的编码方案或者译码方案一般地相比较而言编码问并非特别困难译码却是最严重的瓶颈4译码方法可粗略分为代数译码和概率译码两类。代数译码典型地基于功能非常强大的码适用于相对可靠的通信在弱噪声信道上它可以保证真正的无差错通信。概率译码是一种能有效地利用信道输出且达到较好译码性能的译码方法和代数译码相比较它更适用于在强噪声信道上渐进逼近最佳译码。但是不可能完全避免译码错误要在强噪声信道上实现无差错通信经典的做法是组合应用代数译码和概率译码。为了逼近信道容量码长将无限增加导致系统的无限时延和无限复杂度直至不能物理实现。如卷积码当它们的限制长度增加时可以接近信道容量但是它们的最大似然译码MLD的复杂度将依约束长度呈指数增加对于等概输入的信道最大似然译码等价于性能最佳的最大后验概率MAP 译码。因此长期以来这些码大都是不能实现现实可行的译码方案所以同香农信道编码定理2一样这些只有理论上的意义它们是好码但是不是实用码。 Forney证明了存在现实可行的“级联”码5构成码以顺序方式进行编码和译码。外码一般采用RS码内码采用卷积码内外编码器之间可以增加一个分组交织器block interleaver以打乱内码可能产生的突发错误图样。Forney的分析表明级联码能够获得较大性能改善而译码复杂度并不显著增加。两个以上的短码通过级联有效地获得了接近长码的性能同时使最大似然译码的复杂度显著降低因而级联码是一个次优而实际可行的策略。 第一个被人认识的切实可行而性能又充分接近信道容量的码是Turbo码1993年出现的PCCC码parallel concatenated convolution codes并行级联卷积码也称Turbo码6首先解决了这个信息编码的问题Turbo码使用一种称之为迭代译码算法的解码算法使得在并行设计的情况下产生了不可思议的优良性能同时复杂度不是太高。Turbo码成功的根本原因在于其实现方案中长码构造的伪随机性是核心。在发送端其伪随机性是通过编码器中的交织器以及并行级联方式来实现的在接收端则是利用具有软输入/软输出特性的带有交织器的反馈迭代译码来实现接近最佳译码的。于是通过将卷积码和随机交织器结合在一起实现了随机编码的思想从而为 Shannon随机码理论的应用研究奠定了基础。通过多个软输出译码器之间的迭代系统渐进性能逼近最大似然译码。这一惊人发现使信道编码理论和实践进入了一个崭新的阶段。虽然Turbo码标志着人们构造其性能接近Shannon限的好码的开 5 华 中 科 技 大 学 博 士 学 位 论 文 始但它也有许多缺点71译码时延大这就使Turbo码在某些对时延要求高的通信系统如数字电视中的应用受到限制2计算量大为达到高码率需要很大的交织器这就增加了时延3有错误平层error floor现象。 然而Turbo码并不是唯一、也并不是最早的接近信道容量的编码方案最早的方案要追溯到1962年由Gallager提出的LDPClow density parity check 低密度奇偶校验码89。LDPC码是基于稀疏随机二部图的线性码具有稀疏的校验矩阵LDPC码的校验矩阵H满足以下几个条件 1 H的每行有ρ个“1” 2 H的每列有γ个“1” 3与H中的列数和行数相比较ρ和γ很小。 矩阵H的每列各自包含γ个“1”表示每个码元比特受到相同数目的校验约束每行也都各自包含ρ个“1”表示每个校验集对相同数目的码元比特进行校验约束同时行和列所包含的“1”的数目不同。由于ρ和γ很小所以校验矩阵H具有低的“密度”即表示与校验矩阵H的列数和行数相比较H中每行和每列的“1”的数目很小。因此由校验矩阵H所确定的码称为LDPC码。Gallager证明了这类码具有很好的汉明距离特性在计算树上进行的I?loglogN次迭代后验概率译码可以获得依码字长度指数降低的比特错误概率。然而限于当时的计算能力LDPC码被认为是不实用码未能够引起编码学领域的太多重视。 Turbo码的良好性能使许多学者又回想起LDPC码近年来对Gallage提出的低密度码重新进行了研究和认识10-17证明同Turbo码一样它也是一种可实现的非常好的码1117同时Mackay认为.