准循环码论文

《准循环码论文》由会员分享，可在线阅读，更多相关《准循环码论文（6页珍藏版）》请在装配图网上搜索。

1、准循环LDPC码的构造研究聂静（西北工业大学 软件与微电子学院，陕西 西安，710072） 摘要：低密度奇偶校验（Low densi ty pari ty code）码以其接近香农限的性能和 相对简单的译码结构而得到信道编码界的广泛关注。性能好的QC-LDPC码不仅具 有较低编码复杂度和较少的存储空间，而且在相同的信噪比的情况下，QC-LDPC 码的误码率与随机构造的LDPC码相比并没有退化。因此，在实际应用中，QC-LDPC 码是一类具有较好应用前景的LDPC码。虽然QC-LDPC码有众多优点，但想构造 一个性能良好的码字却并非易事。关键字：线性分组码，低密度奇偶校验（LDPC）码，Tann

2、er图（二分图），圈长， 准循环低密度奇偶校验码（QC-LDPC）.1. LDPC码的基础知识1.1 LDPC码的定义及优点LDPC码是低密度奇偶校验码，严格的说，它并不是一种与以往的编码完全 没有关系的新码，实际上，它是一种特殊的线性分组码。一个线性分组码可以用 校验矩阵来定义也可以用生成矩阵来定义，LDPC码的定义是通过校验矩阵给出 的。稀疏矩阵（Sparsity Matrix）在LDPC码中会经常用到，当一个矩阵中的元素大 部分元素都是0只有很少一部分元素非0时，这样的矩阵就被称为稀疏 矩阵。矩阵的稀疏程度与矩阵密度有关，即矩阵中的非0元素所占的比例。 当一个矩阵的矩阵密度小于等于0.5

3、时，那么这个矩阵是稀疏的。如下式给出的 矩阵矩阵1 0 H= 0 1 0（1）1 0 1它的矩阵密度是0.55，是一个稀疏矩阵。当一个线性分组码的H是稀疏矩阵时，则由H给出的码称为LDPC码。LDPC码的H是稀疏矩阵，非0元素相对于0元素具有低密度性，低密 度校验码的名称也是因此而来的。定义1.1 (Gallager, 1962年)：一个LDPC码被定义为校验矩阵H的零空间,且H具有下列结构特征：(1) 每一行有k个“1”(2) 每一列有j个“1”(3) 任意两列(行)具有共同“1”的位置个数不大于1；(4) k和j与H的列数、行数相比是很小的。LDPC码之所以引起人们关注，主要归结于自身的许

4、多独特优点：(1) 当码长趋近于很大的时候，LDPC码的最小码距和码长的比趋于一个常 数而不是零。(2) Mackay和Neal的研究表明，采用优化设计的LDPC长码可以达到Turbo 码的性能。最近的研究表明在非规则图上构造的LDPC长码的性能已非常地接近香农限1 ，这也是引起理论界极大关注的主要原因。(3) LDPC码的译码算法是一种基于稀疏矩阵的并行迭代译码算法，并且由 于结构并行的特点，在硬件实现上比较容易。(4) LDPC码的码率可以任意构造，也可以打孔得到，有很大的灵活性。1.2线性分组码定义212：个长度为n，有2k个码字的分组码C，当且仅当其2k个码字构 成域GF(2)上所有n

5、维向量空间Fn的一个k维子空间时，称该分组码为(n，k) 线性分组码，且c F”，k称为C的维数。通常情况下，任何(n,k )线性分组码可由其校验矩阵或生成矩阵唯一确定。2QCLDPC码的构造2.1基矩阵构造这里的基矩阵其实就是QC-LDPC码定义中的循环子矩阵。构造基矩阵面临 的首要问题就是基矩阵的选择。对于规则QC-LDPC码，表示其性能的重要参数 是行重和列重。考虑到单位矩阵是行重和列重固定为1的方阵，如果选择单位阵 作为基矩阵，就可以构造任意行重和列重的规则QC-LDPC码3当然同时也带 来弊端：首先是构造出来的矩阵存在短环；其次是因为H矩阵由基矩阵构成，则H的行数和列数显然和基矩阵的

6、维数有着对应关系，这就注定了代数构造法不能 构造任意码长和码率的QC-LDPC码(规则码本身就含有该约束)。然后就是基 矩阵的变换规则，对QC-LDPC码而言，可以通过循环平移的变换方式。实现循 环平移只需要一个参数即循环平移量。2.2 Tanner图构造Tanner提出可以在奇偶校验矩阵中用基于模m的乘法群结构放置循环矩阵来 构造规则的QC-LDPC码，其中m为整数。对一个素数m,整数集0,1,m-1的模m加法运算和乘法运算形成一个域，即GF 域。GF(m)域中的非零元素形成一个循环乘法群。令a和b为乘数阶分别为o(a)=k, o(b)=j的两个非零元素，于是我们可以在GF(m)域内构成一个

7、jXk阶的矩阵P，这个矩阵的第(s,t)个元素Ps ,t=bsat 。_ 1aa2ak-1P =baba2 bak-1 b(2)bj-1ab J-1a 2b j-1a k-1b j-1因此，0WsWj-1, 0WtWk-1，此矩阵可称为构造矩阵。由一个jXk的构造矩阵可以构成如式(2.24)的QC-LDPC码的校验矩阵H。Iak tIIIb j-1ab j-1a 2 b j-1(3)bab2 baIIak-b j- 一a k _1b其中Ix是mX m阶的单位矩阵按行向左循环移位x位所构成的循环移位子 矩阵。所以，式3中的校验矩阵H中第(s,t)位的循环移位矩阵即是将mX m阶单 位矩阵按行向左

8、循环移位ps,t位所得。按照这种方法所得的QC-LDPC码的奇偶 校验矩阵为jmXkm阶，因此可得码率R$1-(j/k)(由于H中各行的线性独立性使 得码率可能大于1-(j/k)，事实上，很容易看出H中至少有j-1行是线性独立的)。 按照Tanner的方法所得出的H列重为j，行重为k，所以构造的是一个(j,k)规则 LDPC码。Tanner构造出的QC-LDPC码为周期为k的QC码，即码组中的一个 码元循环移动k位，即可得到另一个码元。2.3环消去法构造该方法首先随机建立一个由循环子块矩阵构成的奇偶校验矩阵，接着检测奇 偶校验矩阵子块循环的特性，短环是以子块为单位成块出现的，只要修改其中一 个

9、短环经过的子块的循环移位值，即可消去对应的短环。环消去算法就是不停 的检测奇偶校验矩阵中的短环回路，调整子块循环移位值，最终将所有的短环消 去来实现无短环的QC-LDPC码奇偶校验矩阵。该方法在奇偶校验矩阵中搜索短环的计算量相当的大，而且收敛上也存在不 确定性，虽然文献中通过一些算法加以改进，但是仍然保持了较大的算法复杂度。 2.4块填充法构造我们利用位填充的基本思想来构造我们的块填充QC-LDPC码的指数矩阵E(H)4。类似位填充算法，我们也考虑如何在m xn指数矩阵的基础上，通过添加 第(n+l列而保留全局最小环为2(G+1的方法。新添列的初始值全为0，然后选 择某些列中的位填入非零值，不

10、同的是，我们现在填入的是1到B之间的整数而不 是简单的 1。由于在指数矩阵中填入的数值代表了H中的一个B x B块，所以 我们称这个算法为块填充算法。块填充在添加新的一列的时候，对填入的子块需要考虑等效基阵中存在，并 包含它的短环，然后根据这些环中其他子块的值，选择新填入块的值使得式久 i (p - p)mod B=0(4)I，jsis +1-jsS 二 1不成立。这样不断的添加列直到得到了设定大小的指数矩阵，那么，将指数矩阵 的指数扩展就可以得到无短环的QC-LDPC码奇偶校验矩阵。3 块填充算法的改进为了避免每次添加新子块的时候对每个具体环路的检测，我们提出一个新的概念: 行与行之间的n步

11、距离。如果指数矩阵的第i行和第了行有非零子块(i, k)和(j， k)位于同一列，我们称从i行至方行的存在1步距离，这个1步距离值为 (P -P )。如果从j行到h行也有1步距离(p -p )，且1工k那么从i行到hi, kj, kj, lh ,l行存在2步距离Kp- p)+ (p- p)。同理，我们可以计算任意两行之间的1、i, kj, kj, lh .12、3、步距离。指数阵中存在着如下一些行间距离：从第4行到第二行有1步距离： P - P2.2、P - P2.4 ；4.2 4.4从第4行到到第3行有2步距离：(p- p )+(p- p )、(p- p )+(p- p )；4.2 2.22

12、.33.34.42.42.33.3从第4行到第1行有3步距离：(p- p )+ (p- p ) + (p- p )、4.2 2.22.33.33.11.1(p- p )+ (p- p)+ (p- p )；4.42.42.33.33.11.1这里每一个距离都可以是若干数值的一个集合。4小结目前的几类准循环码与随机构造的LDPC码相比优点在于：结构简单，易于 硬件实现和线性时间内编码的实现，而且在中，短码长条件下和中，低码率时有 较好的性能。缺点在于码率和码长的参数选择不够灵活，它们只能根据自身的设 计规则首先构造H矩阵，然后由H矩阵求出码长和码率，而不能根据给定的码 长和码率的参数来设计H矩阵。参考文献1D.J.C.Mackay,“Good Error- Correcting Codes Based on Very Sparse Matrices,” M IEEE Trans.on Inform.Theoryvol.45,pp.399-432,Mar.1999。2窦金芳，周诠.基于矩阵分块的LDPC码快速编码结构研究M，微电子与计算 机，2007,24(1):166-168。3刘永山，刘建权，徐友云等.LDPC编码器的FPGA设计与实现M，军事通信技 术，2006,27(4):39-42。4陈正康，准循环LDPC码的研究及其应用D,空军工程大学硕士论文，2009 年12月31日。