基于位置矢量构造准循环LDPC码

周景芝，宋玉连

（连云港师范高等专科学校数学系，江苏连云港 222006）

1 引言

低密度奇偶校验（LDPC）码由于具有非常优良的性能而受到人们广泛的关注.准循环LDPC码是LDPC码的一类非常重要的分支.Yu Kou等人提出了利用有限域里的欧氏几何和投影几何来构造LDPC码［1］，这种方法构造出的码字具有循环或者准循环特性，但是产生了许多长度为6的环.LDPC码的Tanner图中长度为4的环会造成译码性能的降低.Shu Lin课题研究小组指出利用平衡不完全区组设计［2］（BIBD）构造LDPC码是一个很好的方向.BIBD构造法和随机化构造法相比，具有循环或准循环结构，编码实现起来非常简单.为了进一步研究LDPC码的构造并考虑它的实用性，利用 Bose构造的BIBD，基于位置矢量构造出译码性能非常好的准循环LDPC码，用此设计构造的LDPC码最小环长大于等于6.

2 Bose－BIBD的关联矩阵的结构特性

以 （m，q，ρ，γ，λ） 为参数的基于 BIBD 的 LDPC码校验矩阵构造过程为［3］:（1）建立集合X=（x1，x2，…，xq），获取其n个分组Q1，Q2，…，Qn，其中Qi为X的子集，包含γ个元素;要求集合X的任意一个元素xi需在ρ个分组中出现;且集合X的任意两个元素xi，xj在n个分组中同时出现的次数相同，均为 λ;（2）所有参数间需满足qρ=nλ和λ（q－1）=ρ=（λ－1） 条件.实际上，以（n，q，ρ，γ，λ） 为参数的基于平衡不完全区组设计过程都可用一个q×n的关联矩阵H=（hij）q×n表示.如果X中的第i个元素落在Qj分组中，令hij=1，否则hij=0.相关矩阵H成为行重为ρ，列重为γ，任意两列重复为1的次数至多为1的矩阵，符合规则LDPC码的校验矩阵定义.

Bose在有限域上构造了下面这类BIBD.令t是一个使得12t+1为素数的正整数，从而GF（12t+1）={0，1，2，…，12t} 是一个有12t+1 个元素的有限域.令α是有限域GF（12t+1）上的一个本原元，满足α4t－1=αc，其中c是一个小于12t+1的奇整数，则GF（12t+1）的元素可由0，α0=1，α，α2，…，αq－2来表示，其中 αq－1=1.于是，存在一个参数为q=12t+1，n=t（12t+1），ρ=4t，γ=4 和 λ=1的BIBD.该BIBD的t个基础区组是:Bi={0，α2i，α2i+4t，α2i+8t}，其中 0 ≤i＜t.我们将有限域GF（12t+1）的12t+1个元素依次加到每一个基础区组Bi得到了t（12t+1）个区组，每个区组中有γ=4个元素组成，每个元素恰好在ρ=4t个区组中出现，每个元素对恰好在λ=1个区组中出现.这t（12t+1）个分组构成的BIBD称为（t（12t+1），12t+1，4t，4，1） －Bose－BIBD，其关联矩阵H是一个（12t+1）×t（12t+1）矩阵，列重是4，行重是4t，这样可以得到一个长度为n=t（12t+1）的 LDPC码，其Tanner图中没有长度为4的环.

由于H可以写成H=［G0，G1，…，Gt－1］，所以，H的零空间就给出了一个准循环LDPC码，其长度为n=t（12t+1）.我们也可以选择其中k个循环阵G0，G1，…，Gk－1来构造矩阵H（k）:H（k）=［G0，G1，…，Gk－1］，其中 1 ≤k≤t.H（k） 是一个（12t+1）×k（12t+1）矩阵，其列重和行重分别为4和4k.这样可以得到一个长度为n=k（12t+1）的准循环LDPC码，其Tanner图中没有长度为4的环.

3 基于位置矢量的准循环BIBD－LDPC码

定义1［4］令p为素数，在模p的加法和乘法下构成有限域GF（p）.我们对GF（p）上的元素定义一个p－元位置矢量.当i∈GF（p）时，i位置矢量记为:

其中li∈GF（2），即L（i）中除分量li=1，其它分量均为0.

定理1 若i，j∈GF（p），且i≠j，则L（i） ≠L（j）.

定理2 若i∈GF（p），则L（i+1）是L（i）的右循环移位向量.

显然A，是一个在GF（2）上的p×p的循环置换方阵.

Bose－BIBD在有限域GF（12t+1）中有t个基础区组:Bi={0，α2i，α2i+4t，α2i+8t}，其中0 ≤i＜t.令矩阵Qi是将GF（12t+1）的各个元素依次加到Bi构成的一个（12t+1）×4矩阵.

Qi具有以下结构特性［5］:

（l）各列的12t+1个元素互不相同，分别为GF（12t+1）的12t+1个元素;

（2）任意两列或两行在同一位置都没有相同的元素;

Qi的每一行都是（t（12t+1），12t+1，4t，4，1）－Bose－BIBD的一个区组，Qi的行标记从0到12t，每一列标记从0到3.用位置矢量替换Qi的每一个元素，从而得到一个在GF（2）域上的（12t+1）×4（12t+1）矩阵Mi，它是由4个（12t+1）×（12t+1）循环置换矩阵组成:

其中0≤i＜t，Ai，j是由Qi的第j列所有元素的位置矢量组成的（12t+1）×（12t+1）方阵，其中0≤j≤3.对于Bose－BIBD所有的t个基础区组，可以构造一个由t×4个（12t+1）×（12t+1）循环置换矩阵构成的矩阵Z:

令H=ZT，因此H是由4×t个（12t+1）×（12t+1）的循环置换矩阵构成的，在GF（2）上的一个4（12t+1）×t（12t+1）的矩阵，它的列重为4，行重为t.H的零空间给出了一个（4，t）－正则准循环的BIBD－LDPC码，其码长为n=t（12t+1）.

若γ和ρ均为正整数，且满足1≤γ≤4和1≤ρ≤t，令H（γ，ρ）是H的一个 γ（12t+1）×ρ（12t+1）的子矩阵，即H（γ，ρ）由 γ×ρ个（12t+1）×（12t+1）的循环置换矩阵构成的，其列重和行重分别为 γ和 ρ.于是，H（γ，ρ）的零空间给出了一个（γ，ρ）－正则准循环LDPC码，其码长为ρ（12t+1），并且该码的Tanner图中没有长度为4的环，环长至少为6.

:

［1］KOU Y，LIN S，FOSSORIER M P.Low － density parity － check codes based on finite geometries:a rediscovery and new results［J］.IEEE Trans Inform Theory，2001，47（7）:2711 －2736.

［2］Bose R C.On the construction of balanced incomplete design［J］.Annals of Eugenics，1939，9（1）:353 －399.

［3］Lan L，Ying Y T，Shu L，Memari B，and Honary B.New constructions of quasi－ cyclic LDPC codes based on special classed of BIBD＇s for the AWGN and binary erasure channels［J］.IEEE Transactions on Communication，2007，55（12）:2381.

［4］Djurdjev I，Xu J，and Lin S.Construction of low － density parity－ check codes based on shortened Reed － Solomon codes with two informations symbols［J］.IEEE Transactions on Communication，2003，17（7）:317 － 319.

［5］Lan L，Ying Y T.Constructions of quasi－ cyclic LDPC codes for the AWGN and binary erasure channels:a finite field approach［J］.IEEE Trans Inform Theory，2007，53（7）:2429 －2458.