低复杂度准循环低密度奇偶校验码

低复杂度准循环低密度奇偶校验码

摘要

本文主要对低复杂度准循环低密度奇偶校验码结构的研究。结果表明，这种编码坦纳图代表与周长不能大于12，代码周长的充分条件有一个6，8，10或12的周长推导。这些结果表明这样周长群的LDPC码的相对容易获得，因此，额外的参数，如最小距离或多余的数量检查总结应予以考虑。为此，为必要条件规范调查，以达到其最大可能的最小汉明距离建议。

正文：

近年来, 已有多种 LDPC 码构造方案被陆续提出, 按照构造方法的不同 LDPC 码可以分为两大类, 随机和伪随机码. 对于第一类随机码和伪随机码.尽管分组长度足够长的随机码具有接近 Shannon 限的性能, 但不具有线性的编码复杂度. 针对随机码编码复杂度高的问题, 学术界提出了另一类 LDPC 码. 这类 LDPC 码通常具有循环或者准循环的结构, 从而可以利用线性反馈移位寄存器实现线性编码, 其在串行编码时的复杂度正比于校验比特的个数, 而并行编码时正比于码长, 根据构造时所采用代数方法的不同, 这类 LDPC 码可细分为 3 个子类. 第 1 类是基于有限几何的 LDPC 码, 该算法将有限几何中的点和线映射为 LDPC 码的变量节点和校验节点. 第 2 类是基于组合设计，特别是基于平衡不完全组合设计的 LDPC 码这两类码均为循环或者准循环 LDPC 码, 并且不含长度为 4 的环路, 但是其分组长度受限. 第 3 类是基于循环置换矩阵的准循环 LDPC 码, 虽然这类码的分组长度的范围远远大于基于有限几何的 LDPC码, 但是如果随机选取每个循环置换矩阵, 将不能避免长度为 4 的环路的出现. 对于给定的期望最小环长 g, 我们可以用列重为 J, 行重为 L 的准循环LDPC 码的随机构造法. 该算法从所有pjl个矩阵中搜索一个期望矩阵 (p 代表每个循环置换矩阵的阶数).

准循环 LDPC 码的随机构造法中，待搜索的矩阵个数是乘积 JL 的指数函数, 对于大的行重 J 和列重 L, 构造复杂度高. 为了降低构造复杂度, 本文首先给出了长度为 2i 环路的几何描述, 并且基于该几何描述提出了一种改进的最小

环长为 g 的准循环 LDPC 码的构造方法. 本文所提出的方案是一种构造型算法, 顺序地生成每个循环置换矩阵, 在生成当前循环置换矩阵时, 首先建立当前循环置换矩阵的候选集合. 候选集合中的元素可以确保当前循环置换矩阵与已构造的循环置换矩阵矩阵之间不会形成长度小于 g 的环路. 候选集合建立完毕后, 从候选集合中随机地选取一个元素作为当前循环置换矩阵的移位阶数, 如果所有的循环置换矩阵都能够被确定, 那么构造完毕的 LDPC 码最小环长为 g.否则当构造某个循环置换矩阵时候选集合为空集, 则构造失败. 与最小环长为 g, 列重为 J, 行重为 L的准循环 LDPC 码的随机构造法相比, 本算法避免了遍历搜索的过程, 因而显著地降低了复杂度.

基于循环置换矩阵的准循环 LDPC 码

基本概念

用 p*p 的矩阵将分组长度为 LP 的 (J，L) 准循环 LDPC 码校验矩阵表示为

其中 J 表示列重, L 表示行重, pj,l(1jJ1)模 p 的整数. I(Pj,l)是 p * p 的块矩阵, 在该矩阵的第 r 行(1rp1)上, 仅第 (r + pj,l) mod p 列上的元素均为1, 其他位置上的元素均为 0, 显然I(0) 是一个 p 阶的单位阵.在公式

（1) 所定义的准循环 LDPC 码的 Tanner 图中存在着环路, 由于环路的存在会影响译码性能, 因此对其进行分析是非常必要的.准循环 LDPC 码中长度为 2i 的环路可以用i 个块矩阵构成的序列来表示

:

（2）

其中(jk,lk) 代表公式 (1) 中第jk行, 第lk列的块矩阵. 如果jkjk1，lklk1并且ji1j0，li1l0

l那么公式 (2) 中的块矩阵形成长度为 2i 的环路的充要条件为：

（3）

其中jkj0

准循环 LDPC 码的随机构造法

根据公式 (2) 和 (3), 对于给定的块矩阵阶数 p, 准循环 LDPC 码的随机构造法提出了最小环长为 g 的 (J;L) 准循环LDPC 码的随机构造法. 该算法从GF(p)0,1,....p1中随机地选取 JL 个整数来确定一个其结构如公式 (1) 所示的 LDPC 码校验矩阵, 并利用公式 (3) 检测该校验矩阵中是否含有长度小于 g 的环路. 如果存在任何一个长度小于 g 的环路, 则停止检测, 并且生成另外 JL 个整数以指定另一个校验矩阵. 重复该校验矩阵的检测过程直到寻找到一个不含长度小于 g 环路的校验矩阵为止. 如果所有可能的矩阵检测完毕后, 没有发现所期望的矩阵, 则对于该给定的块矩阵阶数 p, 不存在最小环长为 g的准循环 LDPC 码. 很显然该算法是一个搜索的过程, 可能需要检测的矩阵个数为pjl个. 对于随机构造法而言, 较大的 p 包含所期望矩阵的可能性更大. p 值通过公式 L = Np 决定了分组长度, 这意味着包含所期望矩阵的最小整数 p 决定了最小环长为 g 的准循环 LDPC 码的最小分组长度. 给定列重 J 和行重 L, 该随机构造法可以用来寻找包含最小环长为 g 的 (J，L) 准循环 LDPC 码的最小整数p. 首先设定 p 为一个不可能包含期望矩阵的较小整数, 然后对该 p 利用随机构造法寻找最小环长为g 的 (J，L) 准循环 LDPC 码校验矩阵. 增大 p 并重复寻找过程直到找到一个期望矩阵为止, 最后求得包含最小环长为 g 的 (J，L) 准循环 LDPC 码的最小整数 p.

基于循环置换矩阵的准循环 LDPC 码

从环路形成的的充要条件可以看出, 传统的环路检测法是基于块矩阵序列的. 当利用该代数描述来检测给定的校验矩阵中的环路时, 由于不同的块矩阵序列可能会形成相同的环路, 因此存在冗余. 考虑一个形成长度为 2i 环路的块矩

阵序列, (j0,l0);(j1,l1);....;(ji1,li1);(j0,l0), 由于环路是循环的, 因此无所谓起点在哪里, 亦即从除(j0,l0) 之外的其他 i-1 个块矩阵开始的所有环路与(j0,l0);(j1,l1);....;(ji1,li1);(j0,l0)描述的都是同一个环路. 将公式 (3) 展开, 将公式左边的每项交换次序并取反后所得到的公式描述了由块矩阵序列(j0,lj,,3i1);(i1li2);ji(2li)....jk;1(lk l形(成,环)路的充分必要条件, ,)j1;....

(j0,li1);(ji1,li2);(ji2,li3)....;(jk1,lk);....(j1,l0)与原始序列是不相同的, 该序列同样存在其他 i-1 个表示同一个环路的等价序列. 综上所述存在 2i 个不同的序列, 对这 2i 个序列是否形成长度为 2i 的环路进行判断实际是对同一公式的成立与否进行判断.

为了消除因环路代数描述法所带来的计算冗余, 我们做如下定义:

定义 1

定义边为校验矩阵中任意两个位于同列不同行的块矩阵之间移位阶数的差, 其中位于上方的块矩阵的移位阶数为减数.

根据公式 (3) 对长度为 2i 环路的代数描述, 我们首先提出一种新的坐标(jk,lk)来描述块矩阵序列中的任意块矩阵. 与(jk,lk)代表每个块矩阵的绝对坐标不同, 新坐标(jk,lk)代表相对坐标. 通过依次确定序列中第 k 个块矩阵的新坐标(jk,lk), 可将利用绝对坐标(jk,lk) 表示的毫无规律的序列代表性地分为若干类. 在此基础上分析每一类块矩阵序列, 借助于边的概念, 得到该类块矩阵序列形成长度为 2i 环路的 i 条边的位置与它们之间需要满足的关系. 将每类块矩阵序列形成环路的情况进行总结, 即可得到长度为 2i 环路的边的几何描述, 进而消除了采用代数描述法进行检测时所存在的冗余. 接下来, 我们将讨论如何定义(jk,lk)以及如何通过顺序的确定序列中每个块矩阵的新坐标(jk,lk)来对块矩阵序列进行分类.

对于长度为 2i 的环, 序列中的块矩阵最多位于第 i 行. 将可能生成 2i 环的块矩阵序列按照可能位于的行数进行分类, 不失一般性，假设 i 个块矩阵位于

第m(2mi)行, 并按照从上至下的顺序对 m 行进行标记 (1， 2，……m). 令每个块矩阵新的行坐标取值范围Jk1,2,...,m, 由于相邻块矩阵之间不能位于同行, 因此Jk1,2,...,m\Jk1. 其中2ki. 当 k = i 时, 由于第 i 个块矩阵除了与第 i - 1 个块矩阵相邻, 还与第一个块矩阵相邻, 因此Ji1,2,...,m\J1,Ji1.

对于列坐标, 令L1 = 1, “1”并不代表该块矩阵位于第 1 列, 而表示该块矩

阵所在的列在序列中是第 1 次出现, 之后的块矩阵, 其新的列坐标Lk按照其绝对坐标出现的顺序依次进行标记.

我们采用如下的步骤来实现,

首先设置参数Mkmaxi1:kLi, 则Mk代表前 k 个块矩阵所分布的列数, 接着对于第 k 个块矩阵, 令Lk1,2,...,Mk1,Mk11\Lk1, 则Lk1,2,...,Mk1 表示该列可以与前 k-1 个块矩阵位于不同的列, 即另起一列. 但由于相邻的块矩阵之间不能位于同列, 最终我们可以得到Lk1,2,...,Mk1,Mk11\Lk1, 其中2ki, 当 k = i 时, 由于第 i 个块矩阵除了与第 i-1 个块矩阵相邻, 还与第一个块矩阵相邻, 因此, Jk1,2,...,m\Li,Li1.

由于环路无所谓从哪个块矩阵开始, 因此我们仅仅需要从最上方的块矩阵开始考虑, 对于第 i 个块矩阵位于第m(2mi)行, 第一个块矩阵J1 = 1; L1 = 1, 即新坐标为 (1,1), 且M1 = 1, 对于第 k 个块矩阵, Jk1,2,...,m\Jk1,Lk1,2,...,Mk1,Mk11\Lk1 ,

从而当

m1前块矩阵序列,1m新坐标有mu1n,2,M..m.M1m,L,种可能性1u\n, 遍历每种可能k1, mJ2,..

性, 当确定完第 i 个块矩阵的所有分支后, 将会得到一个 i 层的树形图, 并且树形图中的每条新坐标表示的序列代表了一系列具有相同相对位置用的绝对坐标表示的序列. 利用公式 (3) 并且结合边的概念, 得到每类序列生成环所需要的边以及边之间需要满足的关系, 得到相应长度环路基于边的直观表现形式.

给定周期的充分必要性

定理2.1：对于Hanner图表示的矩阵H给定一个周期至少为2(i1)的一个充分必要条件是

对所有m, 2mi, 对于所有jk，0jkJ1，对于所有jk1，有0jkJ1，0lkJ1。j0jm,jkjk1

推论2.1，对于QC LDPC code, J =2，G=4I是可能的。

这一结果直接从如下（2），其中J0给予系列和J1有备用。在接下来的两个小节，一个最低下限p的值是6和8，分别是确定的。不幸的是，对更大大的周长值，没有得到有意义的约束。