利用双重扩展RS码及循环MDS码构造实用化的LDPC码.doc

第6期张国华等：利用双重扩展RS码及循环MDS码构造实用化的LDPC码105利用双重扩展RS码及循环MDS码构造实用化的LDPC码张国华，王新梅（西安电子科技大学 ISN国家重点实验室， 陕西 西安 710071）摘 要：提出了利用双重扩展RS码和循环MDS码来构造无4-环准循环LDPC码的两类实用方法。第一类构造法利用双重扩展RS码中的所有非零码字来构造校验矩阵，因此在LDPC码的参数选择上比基于单扩展RS码的构造法更加灵活；推导出与双重扩展RS码构造法完全等效的直接构造法，利用RS码的生成多项式可以直接生成LDPC码的校验矩阵，从而避免了RS码字双重扩展、码字分类等预处理步骤。第二类构造法直接根据循环MDS码的生成多项式构造了一类无4-环的准循环LDPC码。仿真结果表明，基于双重扩展RS码和循环MDS码的准循环LDPC码在AWGN信道下均可取得很好的误比特性能。关键词：LDPC码；迭代译码；RS码；MDS码中图分类号：TN911.22 文献标识码：B 文章编号：1000-436X(2008)06-0100-06Applied quasi-cyclic LDPC codes from doubly-extended RS code and cyclic MDS codeZHANG Guo-hua, WANG Xin-mei（State Kay Lab. of Integrated Service Networks,Xidian Univ.,Xian 710071,China）Abstract: Based on doubly-extended RS codes and cyclic MDS codes, two construction schemes were proposed for applied quasi-cyclic LDPC codes whose Tanner graph is free of 4-cycles. In the first approach, all the nonzero codewords within a doubly-extended RS code were employed, and hence provided more flexible parameters than the original or singly-extended RS codes. Equivalent to the method from doubly-extended RS code, a straightforward procedure was derived, by which given generator polynomial of an RS code,LDPC codes could be constructed directly without pretreatment such as double extension and classification of codewords. In the second method, generator polynomials of cyclic MDS codes were utilized in a straightforward manner to build quasi-cyclic LDPC codes with its Tanner graph free of 4-cycles. Experimental results showed that the constructed codes from the two methods perform well over AWGN channels.Key words: LDPC code; iterative decoding; RS code; MDS code1 引言收稿日期：2007-01-15；修回日期：2008-02-20基金项目：国家自然科学基金资助项目（U0635003，60572149）Foundation Item: The National Natural Science Foundation of China (U0635003, 60572149)低密度奇偶校验（LDPC）码是一类线性分组码，其特殊性在于LDPC码的校验矩阵是稀疏矩阵，即矩阵中非零元素的数目远小于“0”的数目。在SPA等迭代译码算法下，LDPC码可以获得逼近Shannon极限的优异性能；目前,LDPC码的构造、译码、分析和应用等问题已经成为编码领域的研究热点。在构造方面，除了带约束的伪随机方法外，主要是数学气息相当浓厚的结构化构造方法，例如有限几何13、平衡不完全区组设计46等。目前，多项通信标准已将LDPC码作为下一代通信系统的信道编码方式，LDPC码正在逐步进入实用化阶段。而实用化的一个巨大障碍就是LDPC码构造方法的不确定性和复杂性。因此，如何构造出既简单实用，又性能优异的LDPC码是目前的一大研究热点。利用双重扩展RS码和循环MDS码，本文提出了2种简单实用的LDPC码构造方法。使用RS码来构造LDPC的思想源于I.Djurdjevic7，这种方法得到的LDPC码缺乏准循环结构，因而不便于编码器的硬件设计；随后，L.Chen仅利用RS码中的最小重量码字，以非/单扩展RS码为基础构造出两类具有准循环结构的LDPC码8,9：non-extended RS-LDPC codes（N码）和singly extended RS-LDPC codes（S码）。本文从2种角度发展了这种构造方法。一方面，本文将这种方法推广到双重扩展RS码的情形，得到了一类更一般化的LDPC码（D码，doubly extended RS-LDPC code），N码和S码都是D码的特殊情形，而D码在参数选择上更加灵活。另一方面，本文推导出与双重扩展RS码构造法完全等效的直接构造法，根据RS码的生成多项式可以直接得到LDPC码的校验矩阵，从而避免了RS码字的扩展与分类等预处理步骤，使这种构造方法更加实用化。此外，利用循环MDS码的生成多项式得到了另一种校验矩阵，不仅具有简单实用的优点而且具有紧凑的描述方式。2 双重扩展RS码设是GF(q)中的本原元，则 构成GF(q)中的所有元素。(q1,k,d=qk) RS码的生成多项式为其中，。与系统码相对应的H矩阵为根据矩阵H，可以得到双重扩展RS码的校验矩阵10因此，RS码的任意码字，添加一个全校验位将得到单扩展码字，再添加一个校验位，就得到了双重扩展码字。改变记号，则。因为双重扩展RS码是MDS码，所以由MDS码的重量分布10可知(q+1,k=2,qk+2=q)双重扩展RS码中包含1个全零码字和个重量为q的码字。设是一个非零码字，它在第个位置为0。集合中的所有码字均在位置处为零；而且除此以外，不存在其他非零码字在位置处为零。事实上，如果存在一个之外的码字在位置处为零，则必与中某个码字在两个位置取相同元素，而这与最小码距为相矛盾。因此，个重量为q的码字可以划分为q+1个不相交的集合。3 D码及其等效构造法3.1 D码的构造方法本节符号沿用文献8中的记法。设是有限域GF(q)中的本原元。定义1 GF(q)中每个非零元素对应于一个GF(2)上的q1重：，其中，其他为0；GF(q)中0元素对应于分量全部为零的q1重。GF(q)中每个元素对应的q1重称为该元素的位置矢量。定义2 对于，将中码字的所有符号用位置矢量表示，可以得到一个重。所对应的重称为的符号位置向量。对于，中全部码字所对应的符号位置向量按行的顺序排成一个的矩阵；则可以看作是由q+1个的循环置换矩阵拼接而成的行，其中包括一个全零矩阵。将所有（）排成一列，可以得到一个的矩阵H；则H可以看作一个的阵列，阵列的每个元素都是一个的循环矩阵（或全零矩阵）。对于任意正整数（且），设是H的一个的子阵列。由于由循环矩阵构成，因此与之对应的LDPC码为准循环码。对于GF(q)上的RS码，任意2个非零码字至多在一个位置取相同符号。因此，对应的Tanner图上不含4-环，即girth至少为6。由上述构造方法容易知道，的零空间给出的LDPC码具有如下参数：码长；校验矩阵对应Tanner图的girth至少为6；校验矩阵的列重为或；校验矩阵的行重为或；稀疏性（即“1”占的比例）。除了girth，影响LDPC码性能的另一个参数是码字的最小距离：最小距离较小LDPC码通常会在高信噪比区产生错误平层。使用与文献9相同的讨论，可以得到最小距离的下界：若不含全零矩阵则最小码距至少为，若包含全零矩阵则最小码距至少为。其中表示不大于的最大整数。N码和S码是D码的2个特例。如果删除D码的最后一个符号，将得到S码；如果进一步删除S码的最后一个符号，将得到N码。D码利用了双重扩展RS码的所有非零码字，因而在参数选择上比另外2种码更加灵活。这3种码的参数如表1、2所示，其中列重，。表13种规则LDPC码的参数比较码类列重，行重设计码率NSD表23种准规则LDPC码的参数比较码类列重，行重设计码率NSD原则上，双信息符号的MDS码都能构造出Tanner图不含4-环的LDPC码；除了RS码、缩短RS码、单/双重扩展RS码，非RS码的MDS码也是存在的。但是，对于GF(q)上的双信息符号MDS码，码长至多取q+1 10。对于双信息符号的双重扩展RS码，其码长为q+1，因而对码长继续扩展是不可能的。因此，在所有基于MDS构造无4-环LDPC码的方法中，本文方法为参数选择提供了最大可能的灵活性（见表1、表2所示）。3.2 D码的等效构造方法由第3.1节可知，通过对RS码进行双重扩展、码字分类等操作可以构造出LDPC码的校验矩阵。本节将推导一种D码的等效构造方法。使用该方法，不必列出双重扩展RS码的码字就能直接构造出D码。首先证明3个性质。性质1 ， ，和 都是双重扩展RS码的码字。证明 根据RS码的校验矩阵H可知是(q1,2,q2) RS码的一个码字；根据全校验关系可知，是单重扩展(q,2,q1) RS码中的一个码字；根据，可知 是双重扩展(q+1,2,q) RS码中的一个码字。同理可证是双重扩展(q+1,2,q) RS码中的一个码字。对应于(q1,2,q2) RS码中一个重量为q2的码字,，所以是双重扩展(q+1,2,q) RS码中的一个码字。性质2 设是循环右移m位算子。若对应的双重扩展码是，则 对应的双重扩展码是。证明 显然保持不变。令，根据有根据性质1和2可以得到共计1+1+(q1)=q+1个双重扩展RS码字，它们的零分量出现位置各不相同。用GF(q)中的(q1)个非零元素与每个码字相乘，可得(q1)(q+1)个非零码字，它们就是双重扩展(q+1,2,q) RS码的所有非零码字。由于码字和固定不变，因此为了构造D码，我们只需求出，然后计算出和；事实上，根据以下性质只需求出，和可由直接得到。性质3 。如果q为奇数，；如果q为偶数，。根据以上讨论，D码可根据以下步骤等价地构造出来。1) 根据和构造母矩阵M2) 对于非零元素，定义为一个 的置换矩阵：如果，；否则。对于零元素，定义一个的全零矩阵。3) 从矩阵M中选择一个的子阵列，称此子阵列为矩阵；将矩阵中的所有元素用相应的置换矩阵（或全零矩阵）替代，将得到一个的矩阵，称此矩阵为。4) 将作为校验矩阵，则其零空间对应于一个准循环LDPC码。D码的母矩阵M包含了S码和N码的母矩阵。母矩阵M的前q1行、前q1列对应于N码的校验矩阵；母矩阵M的前q行、前q列对应于S码的校验矩阵。根据母矩阵M的性质，不必计算即可直接得到。性质4 在母矩阵M中，除末行以外任意行的前q个元素两两不同，即这q个符号恰是GF(q)上的所有元素。 证明：第q行的前q个元素显然两两不同。假设第行（）的前q个符号中存在2个相同的元素，该行与矩阵M末行对应的2个双重扩展RS码字，可以线性组合出一个至少包括两个零元素的非全零码字。矛盾。4 利用循环MDS码构造LDPC码为便于使用理论方法对最小距离、girth等重要参数作深入分析，校验矩阵一般希望具有较强的结构特征。母矩阵M在形式上比较对称，但其最后两行和最后两列影响了母矩阵M整体上的循环性质。虽然双重扩展RS码的码字之间一般不存在循环关系，但是存在与双重扩展RS码参数相同的循环MDS码10。利用循环MDS码，可以得到具有循环性质的母矩阵。设，是上的本原元。令，则。根据的取值，可以分为两种情况。（1）若，令 ，则是(q+1,2,q)循环MDS码的生成多项式10。（2）若，令，可以验证是的连续q1个零点。因为，所以生成一个(q+1,2)循环码；根据BCH限，该循环码的最小距离为q，因此生成一个(q+1,2,q)循环MDS码。令。则对应的母矩阵可表示为由母矩阵构造LDPC码的方法同3.2节完全相同，这里不再重复。与直接利用组合数学（例如有限几何、平衡不完全区组设计等）的方法相比，以上2种方法（等效构造法和循环MDS码构造法）利用了通信领域的已有标准技术，可以方便直观地作出LDPC码的校验矩阵；惟一需要计算的是码的生成多项式，而这是基本和简单的。除本文方法外，还存在其他能够简洁构造出校验矩阵的方法。例如，利用有限域和仿射变换（FFAM），文献11,12提出了2种构造LDPC码的简洁方法。它们与本文构造法有以下异同之处。一方面，FFAM方法与本文方法都是基于MDS的构造方法；根据文献13中的定理2.3.3，利用FFAM的构造方法在本质上是基于线性MDS码的构造方法。另一方面，FFAM方法与本文方法得到的校验矩阵，在描述形式上存在较大差异。在FFAM方法中，有限域上一组相异的元素被施加仿射变换后得到母矩阵，母矩阵中每个元素被相应的位置矢量替换后即得校验矩阵。这种方法得到的母矩阵采用元素之差的形式来描述，在实施位置矢量替换之前必须完成元素之差表示到指数表示的转换，这对实用来说是不方便的。本文得到的母矩阵直接采用指数形式描述，不仅结构紧凑而且便于实用。5 例子与仿真仿真条件：迭代译码算法采用BP算法14，最大迭代次数设定为100，信道模型为AWGN，采用BPSK调制。在下面2个例子中，误码率数据均仿真到了量级；量级以下的仿真超出了目前计算机的运算速度。为了保证仿真数据的准确性，仿真数据量至少比误码率高出2个量级。LDPC码的误比特性能可以与相应参数的伪随机LDPC码比较，也可以直接与Shannon限相比较。为了保证比较的客观性和可重复性，本文采用第二种方式。例1 使用有限域上的(129,2,128)双重扩展RS码构造QC-LDPC码。设是的本原元，满足。(127,2,126) RS码的生成多项式为；用本原元的幂次表示，对应的码字为 。根据等效构造法，作出一个的母矩阵M。取。将矩阵的前8行和后32列作为子阵列，对应的行重为32，列重为8。零空间可以给出一个码率为0.783，最小距离至少为10的规则(4064,3181) QC-LDPC码。在误码率为时，(4 064,3 181) QC-LDPC的性能距离Shannon限约1.7dB。取。将矩阵M的前4行和后8列作为子阵列，对应的行重为8，列重为4。零空间可以给出一个码率为0.517，最小距离的规则(1016,525) QC-LDPC码。在误码率为时，(1016,525) QC-LDPC的性能距离Shannon限约2.4 dB，对于结构化的短码而言，这是比较好的性能。图1 (129,2,128)双重扩展RS码构造的2个QC-LDPC码例2 使用有限域上的长度为33的循环MDS码构造QC-LDPC码。设是上的本原元，满足。令，则是的本原元。设，则(33,2,32) MDS码的生成多项式为；用本原元的幂次表示，则对应的码字为。作出一个的母矩阵。设。将矩阵的前16行和前32列作为子阵列，对应的行重为31，列重为15和16。零空间可以给出一个码率为0.772、最小距离至少为16的准规则(992,766) QC-LDPC码。在误码率为时，准规则(992,766) QC-LDPC的性能距离Shannon限约2.0dB。设。将矩阵的前6行和全部列作为子阵列，对应的行重为32，列重为5和6。零空间可以给出一个码率为0.857、最小距离至少为6的准规则(1 023,877) QC-LDPC码。在误码率为时，准规则(1 023,877) QC-LDPC码的性能距离Shannon极限约1.5dB。图2 长度为33的循环MDS码构造的2个QC-LDPC码6 结束语首先利用双重扩展RS码构造出一类无4-环的准循环LDPC码。使用非扩展RS码和单扩展的RS码得到的LDPC码是新方法的两个特例。由于双重扩展RS码中所有非零码字均被利用，因此构造出的LDPC具有更加灵活的参数选择范围。给定RS码的生成多项式，利用等效构造法可以直接得到LDPC码，它与通过双重扩展RS码得到的LDPC码完全等价。在所有基于MDS构造无4-环LDPC码的方法中，本文方法为参数选择提供了最大可能的灵活性。此外，利用循环MDS码也可以简便地构造出准循环LDPC码，而且对应的校验矩阵结构非常紧凑。在LDPC码的实用中，通常要求校验矩阵易于构造、编码器易于实现。本文提出的两种实用化QC-LDPC码构造方法可以满足这两个要求。但是，目前绝大多数校验矩阵的结构化构造方法（包括本文方法）存在一个不足，即校验矩阵只有在构造出来之后才可以确定LDPC码的码率。这对应用来说是不方便的。给定码长和码率，如何构造性能优异的校验矩阵是LDPC码实用中需要解决的一个问题，也是我们下一步的一个研究方向。参考文献：1KOU Y, LIN S, FOSSORIER M P C. Low-density parity-check codes based on finite geometries: a rediscovery and new resultsJ. IEEE Trans Inform Theory, 2001,47(7):2711-2736.2WELLER S R, JOHNSON S J. Regular low-density parity-check codes from oval designsJ. Euro Trans Telecomms, 2003,14: 399-409.3JOHNSON S J, WELLER S R. High-rate LDPC codes from unital designsA. IEEE Globecom2003C. San Francisco, CA, 2003. 2036-2040.4WELLER S R, JOHNSON S J. Construction of low-density parity-check codes from Kirkman triple systemsA. Proceedings of IEEE Globecom conferenceC. San Antonio, TX, 2001.970-974.5AMMAR B, HONARY B, KOU Y, et al. Construction of low-density parity-check codes based on balanced incomplete block designsJ. IEEE Trans Inform Theory, 2004,50(6):1257-1268.6VASIC B, MILENKOVIC O. Combinatorial constructions of low-density parity-check codes for iterative decodingJ. IEEE Trans Inform Theory, 2004,50(6):1156-1176. 7DJURDJEVIC I, XU J, ABDEL-GHAFFAR K, et al. A class of low-density parity-check codes constructed based on Reed-Solomon codes with two information symbolsJ. IEEE Commun Lett, 2003,7(7): 317-319.8CHEN L, DJURDJEVIC I, XU J, et al. Construction of QC-LDPC codes based on the minimum-weight codewords of RS codesA. Proc.IEEE Int.Symp.Inform.TheoryC. Chicago, 2004.239-239.9