ldpc编码译码方法研究及误码率实现.doc

LDPC码作业）通信与信息系统LDPC编码译码方法研究及误码率实现摘要低密度奇偶校验 LDPC 码(Low-Dens i ty Pari ty-Check codes ) 是继Turbo码之后又一种逼近香农极限的信道编码相对于 Turbo, LDPC码有着诸多的优势，以及更加广阔的应用前景，因此 它已经成为编码界当前最热门的研究课题本文主要研究了低密度 校验码(LDPC码)的编译码方法及不同信噪比下所得到的误码率 编码通常有高斯消元法、基于近似下三角化的LDPC编码方法和特 殊码字LDPC编码方法译码通常有消息传递算法.最小和译码算 法、比特翻转译码算法等AbstractThe Low-density parity check LDPC codes (Low-Density Parity-Check codes to) is yet another after the Turbo codes approaching the Shannon 1 imit of channel coding・ Relative to the Turbo and LDPC codes have many advantages, as well as more broad application prospects, so it has become the coding community is the most popular research topics・ In this paper, the BER encoding and decoding methods and different signal to noise ratio of low density parity check code (LDPC code)・ Coding usually Gaussian elimination method, based on the approximate lower triangular LDPC encoding method and special codeword, LDPC encoding method・ Decoding typically message passing algorithms, belief propagation algorithm, the smallest and decoding, bit flipping decoding algorithm・第一章引言1. 1 LDPC码介绍低密度校验码（LDPC码）是一种前向纠错码，它最初在1962年 由麻省理工学院的Galfager在其博士论文中提出。

那时候，世界 才刚刚脱离真空管，进入第一代晶体管时代，实验仿真所要求的的 计算能力并不发达，所以LDPC码无与伦比的潜能没能引起人们的 重视，而被长久地忽视了 35年同一时期，主流的前向纠错技术是高度结构化的代数分组码和卷积码尽管上述这些纠错码技术 在实际中获得了巨大的成功，但是它们的性能却远没有达到 Shalmon在其1948年发表的开创性论文中所指出的理论可达限 到了 20实际80年代末，经过几十年的尝试，学者们已经接受了这 个理论与实际之间无法逾越的鸿沟编码学研究经过了相岂的一段沉寂之后，被"turbo码”的出 现彻底唤醒turbo 码由 B u, Glavieux 和 Thi t ima jshima 在 1993 年提出，它彻底颠覆了所有人们认为成功的纠错码所要具备的因 素:turbo码涉及非常少的代数，运用迭代，分布的算法，专注于 平均（而非最差）性能，同时仰赖从信道中获取的软（或者似然）信 息一夜之间，在复杂度可控的译码器的协助下，达到Shannon限 所要越过的鸿沟已不复存在LDPC码不仅蕴含有很高的理论价值，而且已经为卫星数字视频广播标准和长途光通信标准所采纳，还极有可能被吸收入IEEE 无线局域网标准中，人们还正在考虑把LDPC码应用到第四代移动 系统的长期发展规划中O1. 2 LDPC码的特点LDPC码是一种分组码，其校验矩阵只含有很少量非零元素。

正是校验矩阵H的这种稀疏性，保证了译码复杂度和最小码距都只 随码长呈现线性增加除了校验矩阵H是稀疏矩阵外，LDPC码本身与任何其它的分 组码并无二致其实如果现有的分组码可以被稀疏矩阵所表达，那 么用于LDPC码的迭代译码算法也可以成功的移植到它身上然而，一般来说，为现有的分组码找到一个稀疏矩阵并不实际不同的是, LDPC码的设计是以构造一个校验矩阵开始的，然后才通过它确定 一个生成矩阵进行后续编码而LDPC的编码就是本论文所要讨论 的主体内容译码方法是LDPC码与经典的分组码之间的最大区别经典的分组码一般是用ML类的译码算法进行译码的，所以它们一般码长 较小，并通过代数设计以减低译码工作的复杂度但是LDPC码码 长较长，并通过其校验矩阵H的图像表达而进行迭代译码，所以它 的设计以校验矩阵H的特性为核心考虑之一目前的研究均表明LDPC码是信道编码中纠错能力最强的一种码， 而且由于其译码器结构简单，可以用较少的资源消耗获得极高的吞 吐量，因此应用前景相当广泛1. 3 LDPC码的历史和现状LDPC码于1962年由Gallager提出，因此它也被称为 Gallager码，它是Turbo码之外的另一种逼近香农极限的码字。

虽然Gallager证明了 LDPC码是渐进好码，但是受限于当时的计 算能力，LDPC码一度被认为是一种无法实现的信道编码方式，在 很长一段时间内没有得到人们的重视1981年随着Tanner著作 的出现，LDPC码可以用图论的角度进行新的理解和诠释，然而不 幸的是这一理论成果依然没有得到人们的重视知道90年代初， 随着Turbo码的出现，这才引发了学者们对于LDPC码研究的热 情oMackay和Neal在上世纪九十年代利用随机构造的Tanner图 研究了 LDPC码的性能，釆用Belief Propagation （BP算法）译 码算法的LDPC码字具有与Turbo码相似的译码性能，长的LDPC 码在BP译码算法下性能甚至超过了 Turbo码，它可以达到距离 香农限只有0. ldB的距离这个发现是的LDPC码比Turbo码在 需要高度可靠性的通信和存储系统纠错中更具有竞争力从此以 后，有关LDPC码的文献大量涌现第二章LDPC码的编码和译码分析2. 1 LDPC码的编码方法2. 1. 1 LDPC码的标准编码方法设LDPC码的码长为n,信息码长度为k,校验码长度为m=n — k.已经讨论过，校验矩阵H经过高斯消元可以化为：吐[H Im*m]其中H:是尺寸为mxk的二进制矩阵，可以得到：Imxm是尺寸为 m. m的单位矩阵。

于是可以得到：G= [Ik*k Hl]通过生成矩阵G就可以进行编码以下用一个例子说明如何由 校验矩阵H得到生成矩阵G.2.1.2 LU分解编码算法首先推导出根据校验矩阵直接编码的等式将尺寸为mxn校验 矩阵H写成如下形式:H =【H 1 H 2】其中H 1的尺寸为m * k , H 2的尺寸为mx m,设编码后的码字 行向量为x,它的长度为n,把它写成如下形式：c= [ s pl其中S是信息码行向量，长度为k, P为校验码行向量，长度为m. 根据校验等式有H x cT=O上式展开得：展开该矩阵方程，并考虑到运算是在GF (2)中进行，得到： p • H 2 T=s • HT (2. 1)如果校验矩阵H是非奇异，则HZ满秩，所以有：p=s -HT -HT (2. 2)式(2.1)和式(2.2)就是不通过生成矩阵而直接由校验矩阵 进行编码的等式，一切只依赖校验矩阵的编码都是通过这两个式子 实现的从式(2.1)可以看出，一般来说，只要校验矩阵具有下三角结 构，它总是能够通过迭代方法进行编码的引入了迭代，就大大降 低了编码的复杂度LU分解编码算法就是以这个思想为基础的 2. 2 LDPC译码算法2. 2. 1消息传递算法：在消息传递(MessagePassing, MP)算法中，概率信息依据二 分图在变量节点和校验节点之间传递，逐步进行迭代译码。

节点沿 边发送的信息与上次从接收到的信息无关，而取决于和相连的其它 边上接收的信息目的在于使得任一条边上，只有外来信息传递， 从而保证译码性能如果1DPC码对应的二分图中不存在环，则任一节点接受的信息都与从该节点发出的信息无关，从而保证了迭代 译码的性能如果二分图中存在环，经过一定次数的迭代之后，节 点收到的信息将将与其发出的信息存在相关性，这将影响译码算法 的性能2. 2.2最小和译码算法：最小和(Min — sum)译码算法是根据对数域BP译码算法提出的 一种近似简化算法，它利用求最小值的运算简化了函数运算，大大 降低了运算复杂度且不需要对信道噪声进行估计，但其性能也有一 定程度的降低2. 2. 3比特翻转译码算法：比特翻转(Bit - Flipping, BF)译码算法首先将输入译码器的 数据进行硬判决，然后将得到的u0\ T”序列代入所有的校验方 程，找出使校验方程不成立数目最多的变量节点，最后将该变量节 点所对应的比特位翻转，至此完成一次迭代整个译码过程不断地 进行迭代，直到所有的校验方程都成立或者达到了设定的最大迭代 次数比特翻转译码算法只进行比特位的翻转等儿种简单的运算， 没有复杂的操作，因此非常适合硬件实现，但其性能相对于BP译 码算法有所降低，适用于硬件条件受限而性能要求较低的场合。

附一部分关于比特翻转译码仿真程序：function vHat 一 decodeBitFlipping (rxr Hz iteration)% rx : Received signal vector (column vector)% H : LDPC matrix% iteration : Number of iteration % vHat : Decoded vector (0/1)[M N] = size (H);% Prior hard-decisionci 0.5*(sign(rx1) + 1);% Initialization rji ■ zeros(Mr N);% Asscociate the ci matrix with non-zero elements of Hqij ■ H・*repmat(ci/ M, 1);for n = 1: iteration% Horizontal step for i = 1:Mcl = find(H(1,:));for k = 1:length(cl)rji (1, cl(k)) = mod(sum(qij(i, cl)) + qij(i, cl(k)), 2); endend% Vertical step for j ■ 1:Nrl - find(H (:, j)); numOfOnes = length(find(rji (rlr j)));for k = 1:length (rl)% Update qijr set 111 for majority of Is else 101r excluding rl(k)if numOfOnes + ci (j) >= length(rl) - numOfOnes + rji(rl(k)r j) qij(rl(k), j) = 1；else qijtrKk), j) - 0;endendif numOfOnes + ci(j) length(rl) - numOfOnesvHat (j) ■ 1;。