DOI:10.11991/yykj.201505021
,
,
寻找一种能够获得信道容量的信道编码方案一直是编码界的重要研究方向。格码(lattice codes)可以看作是欧式空间的线性码，它能够达到加性高斯白噪声(additive white Gaussian noise,AWGN)信道的信道容量[1, 2]。然而最初的格码的设计都是基于固定维度的经典格或是代数纠错码，并没有直接在欧几里得空间设计格码的可行方案。为了寻求一种具有高效编译码方案的实用格码，2007年Sommer等人提出了低密度格码(LDLC)，在LDLC中，编码和信道都是基于实数域上的运算，这使得在连续取值的AWGN信道上的编译码得到了极大的简化[3, 4, 5]。与低密度奇偶校验码(low density parity codes,LDPC)类似，LDLC由一个稀疏的校验矩阵定义。校验矩阵的稀疏性使得我们能够利用迭代译码算法对LDLC进行高效译码，且译码复杂度与码长呈线性关系[4, 5]。实验表明LDLC能够达到高斯信道容量。例如，当码长n=100 000时能够获得距信道容量仅0.5 dB的性能[3]。在文献[3]中，Sommer等提出了一种构造六环LDLC校验矩阵的方法，这种方法首先随机生成一个排列矩阵，然后通过随机交换排列矩阵中元素的位置来消除二环和四环，最终通过该排列矩阵来生成六环校验矩阵。该方法能够得到一个六环的校验矩阵，但是校验矩阵中六环的存在对LDLC译码性能有一定的影响，并且若用这种方式消除六环，将会大大增加构造复杂度，实验证明也很难得出结果。本文在此基础之上，提出了一种新的构造八环LDLC校验矩阵的方法。在本文的构造方法中，首先由排列矩阵生成一个六环的校验矩阵，随后所有参与六环的非零元素通过邻接矩阵的相关理论被检测出来，最后通过移动六环元素的位置来消除检测到的六环，消除六环的过程中需要保证移动元素之后不会产生新的四环和六环。当所有的六环都被消除之后，最终得到一个八环的校验矩阵。仿真结果表明，本文所构造的八环LDLC校验矩阵与文献[3]的构造结果相比，具有更低的误符号率性能。
1 格和格码格定义[6]: 一个n维格Λ是Rn中的一个离散子群，因此具有群的性质。即对于任何x1,x2∈Λ，有x1+x2∈Λ。一个n维格Λ可以用一个生成矩阵G来表示：
一个n维格码由一个格G与成形区域B⊂Rn共同定义，格码的所有码字都是落在成形区域B中的格点[7]。每个码字均满足 x=Gb,b∈Zn。
2 低密度格码及其二分图表示码n维低密度格码定义为具有非奇异生成矩阵的G的n维格码，并且该生成矩阵所对应的校验矩阵H=G-1满足稀疏性。如果一个LDLC的校验矩阵H的每一行和每一列都有相同的d个非零元素 h1,h2,…,hd，而且这些值仅仅是排列顺序和符号不同，那么该LDLC称为拉丁方LDLC。这d个非零元素构成的序列h1≥h2≥…≥hd > 0称为LDLC的生成序列。
例如，图 1(a)中的校验矩阵H就是一个维度n=6，度数d=3的拉丁方LDLC校验矩阵，该LDLC的生成序列为h={1,0.6,0.3}。
|
| 图 1 低密度格码 |
与LDPC类似，LDLC也可以由一个二分图表示，如图 1(b)所示。在二分图中，变量节点xi和校验节点cj分别被放在图的两侧，当 H(j,i)≠0时，变量节点xi与校验节点cj有一条边相连。对于度数为d的拉丁方LDLC，每个变量节点和校验节点都有d条边与之相连。在二分图中，路径被定义为由节点和边交替组成的有限序列，路径中边的数量称为路径的长度。一个闭合的路径被称为一个环，例如，图 1(b)中长度为4的闭合路径x1→c1→x3→c3→x1构成了一个4环。
LDLC校验矩阵的结构对译码的性能有很大影响，由于LDLC译码采用置信迭代译码，该算法的推导是基于在节点间传递的消息统计独立性。当LDLC的校验矩阵对应的二分图中有短环存在时，某一节点发出的信息经过一个环长的传递会被传回本身从而造成自身信息的叠加，破坏了节点间消息独立性的假设，这会严重影响译码的准确性[8, 9]。因此，在LDLC校验矩阵的构造中，要尽量避免短环的出现。
3 八环LDLC校验矩阵的构造校验矩阵中四环和六环的存在会严重影响LDLC译码的性能，因此希望消除矩阵中的四环和六环，构造出一个八环的校验矩阵。下面的八环LDLC构造算法主要分为2个步骤，首先由排列矩阵生成一个六环矩阵，然后检测并消除矩阵中的六环。
3.1 由排列矩阵生成一个六环矩阵H1给定矩阵维度n，度数d及生成序列h={h1,h2,…,hn}，生成六环矩阵的大致思路是，首先随机生成一个d×n的排列矩阵J，然后依次搜索该矩阵中的二环和四环。并通过移动排列矩阵中元素的位置来消除二环和四环，最后由这个消除了二环和四环的排列矩阵来生成六环矩阵H1，排列矩阵和排列矩阵中的二环及四环如图 2所示。具体的生成方法步骤如下：
1)随机生成一个d×n的排列矩阵J，排列矩阵的每一行都是一个从1到n的随机排列。
|
| 图 2 4×8的排列矩阵及二环(虚线框)和四环(实线框) |
2)从第一列开始依次搜索排列矩阵J中的二环。这里的二环定义为位置矩阵同一列中含有2个相同的元素，即满足i≠j，J(i,c)=J(j,c),1≤c≤n。如果一个二环被检测出来，标记该列出现二环的行。
3)如果排列矩阵第c列没有二环，则依次搜索排列矩阵中的四环。若排列矩阵的任意列c0≠c与第c列存在至少2个相同的元素，那么一个四环就被检测出来，标记该列第一个相同元素所在的行。
4)修正步骤2)和3)中标记行的排列。假设标记的行号为s，随机选择一个整数 1≤j≤n，然后交换该行中第j个元素J(s,j)和第c个元素J(s,c)的位置。
5)重复步骤2)~4)，直到位置矩阵的每一行都不存在二环和四环。
6)由位置矩阵J生成一个六环校验矩阵 H1。H1(J(j,i),i)=hj,1≤i≤n,1≤j≤d。值得注意的是，在得到矩阵H1之后，需要给H1中每个非零元素随机添加正负号。
经过以上步骤可以得到一个六环的校验矩阵H1，但由于该矩阵中六环的存在会对译码性能产生一定的影响，为了进一步提升译码性能，必须要消除校验矩阵中的六环。
3.2 消除H1中的六环在定位一个六环时，我们所关心的是参与该六环非零元素的位置，而这些非零元素的值可以忽略。基于这种考虑，先引入一个二元矩阵H1b：
矩阵中的短环可以通过计算邻接矩阵的不同次幂来检测。邻接矩阵是一个2n×2n(n为二元矩阵的维数)的对称二元矩阵，当且仅当变量节点vi与校验节点cj相连时，邻接矩阵对应元素取值为1。对于拉丁方LDLC，邻接矩阵定义为
定理 1：二分图[10, 11]中的变量节点vi和校验节点cj，k为整数，矩阵A的2k次幂为A2k，元素A2k(i,j),(i,j=1,2…,2n)满足：Ak(i,j)≥2，A(k－2)(i,j)=0，则存在一个经过节点vi和cj长度为2k的环。
根据定理1可以很方便地检测矩阵中的六环，并且定位参与六环元素的位置；当一个六环被检测出来时，通过移动该六环元素的位置来消环。消除H1中的六环主要有以下步骤。
1)定位一个六环元素的位置。由定理1可知，当A3(i,j)≥2且A1(i,j)=0成立时，可以断定节点i参与了一个六环，设节点i在矩阵H1中的位置为 (i,k)，k满足限定条件Ai,k1=1，Ak,j 2> 0。
2)移动该元素来消去六环。令H1(i,k)=hs，首先搜索H1矩阵，找到一个元素使它的值也为hs，假设该元素的在H1中的坐标为(p,q)，即H1(p,q)=hs。如果满足以下3个条件，移动这2个元素的位置来消去这个被检测出来的六环。即H1(i,q)=H1(p,q),H1(p,k)=H1(i,k),H1(p,q)=0,H1(i,k)=0，移动过程如图 3所示。
|
| 图 3 移动元素消去六环 |
3)如果不存在满足条件的(p,q)，返回步骤1)重新定位一个六环元素，继续执行移动消环步骤。
条件 1：为了保证移动这2个元素之后校验矩阵 H1每行的度数及非零元素序列一致，必须满足H1(i,q)=0，H1(p,k)=0。
条件2：移动这2个元素不会产生新的四环。设移动这2个元素之后所对应的二元矩阵为
，为了判断条件2是否成立，分别计算中第i行和第p行与其余各行的内积，如果所有这些内积结果都小于2，那么移动元素之后就不会产生任何四环。即
(i,:)表示矩阵 的第i行，dot(·,·)代表内积运算。
条件 3：移动这2个元素不仅能消除检测到的六环，同时还不能产生新的六环。由于移动元素之后会用一个零值替换掉原来六环中的这个非零元素，这就破坏了原来的六环结构，所以移动这个元素能够消除检测到的六环。同时，根据邻接矩阵的理论，如果满足A5(i,(q+n))=0和A5(p,(k+n))=0，这意味着在校验矩阵H1对应二分图中不存在从节点i到节点q长度为5的路径。同理，也不存在从节点p到节点k长度为5的路径。这就表明H1中不存在围长为6的环。因此，移动这2个元素不会产生新的六环。
4)重复步骤1)和步骤2)，直到步骤1)找不到任何参与六环的元素，这就意味着所有的六环都已被消除。
经过上述步骤之后，所有的六环都被消除，最终得到一个最小围长为8的校验矩阵H。
4 仿真结果分析首先，根据本文构造算法对不同维数和度数构造了3个拉丁方LDLC校验矩阵，并在高斯白噪声信道下对其误码率性能进行性能仿真，构造参数如表 1所示，在得到校验矩阵H之后用
对其进行标准化，使得|det(H)|=1。其中，det(·)表示求矩阵的行列式运算。仿真中的译码方案选用文献 [3]的量化迭代译码，量化迭代译码的参数设置如表 2所示。
将本文构造算法与文献[3]的构造六环LDLC的方案以及文献[12]中基于子集矩阵的LDLC构造算法进行比较。构造结果用误符号率和信道噪声σ2距信道容限的距离来描述，仿真结果如图 4所示。
|
| 图 4 不同构造算法下的误符号率性能 |
从仿真结果中可以看到对于不同维度和度数的LDLC，本文的构造算法与文献[3]的构造方案相比误码率性能有明显的提高。例如，在SER=10-4的情况下，维度n=200的LDLC，本文构造算法的误符号率性能大约有0.2 dB的增益。同时，本文构造算法与文献[12]中的构造算法相比，在维度n=200和n=500时，本文构造算法有0.1 dB的增益，维度为n=1 200时，二者性能无明显差异。
5 结束语本文对文献[3]中的构造算法进行改进，提出了一种八环拉丁方LDLC校验矩阵的构造算法，仿真分析了其误符号率性能。仿真结果表明，在相同参数条件下，本文的构造算法与现有构造算法相比能够获得更低的误符号率性能。但是，对于维度较低的LDLC，度数取值不能太大，否则可能无法消去矩阵中的所有六环。因此，寻求取值更为灵活、性能更为优异的校验矩阵构造方案仍然是下一步的研究方向。
| [1] | EREZ U,ZAMIR R.Achieving 1/2 log(1+SNR) on the AWGN channel with lattice encoding and decoding[J].IEEE transactions on information theory,2004,50(10):2293-2314. |
| [2] | ZAMIR R.Lattice coding for signals and networks:a structured coding approach to quantization,modulation and multiuser information theory[M].Cambridge:Cambridge University Press,2014:11-37. |
| [3] | SOMMER N,FEDER M,SHALVI O.Low-density lattice codes[J].IEEE transactions on information theory,2008,54(4):1561-1585. |
| [4] | YONA Y,FEDER M.Max-product algorithm for low density lattice codes[C]//IEEE International Symposium on Information Theory Proceedings(ISIT).Cambridge,UK,2012:1727-1731. |
| [5] | KURKOSKI B,DAUWELS J.Reduced-memory decoding of Low-density lattice codes[J].IEEE communications letters,2010,14(7):659-661. |
| [6] | PRASAD N,WANG Xiaodong,MADIHIAN M.Spherical lattice codes for lattice and lattice-reduction-aided decoders[P].US:8091006,2012-01-03. |
| [7] | SONG Yiwei,DEVROYE N.Lattice codes for the Gaussian relay channel:decode-and-forward and compress-and-forward[J].IEEE transactions on information theory,2013,59(8):4927-4948. |
| [8] | WIBERG N.Codes and decoding on general graphs[D].Linköping:Linköping University,1996:25-37. |
| [9] | 王晓松.下一代无线通信系统中调制与编码关键技术研究[D].沈阳:东北大学,2009:69-82. |
| [10] | MCGOWAN J A,WILLIAMSON R C.Loop removal from LDPC codes[C]//Proceedings of IEEE Information Theory Workshop.Paris,France,2003:230-233. |
| [11] | WANG Xiaosong,CHANG Guiran.A method to construct girth-8 low density lattice codes[C]//Proceedings of the 11th IEEE Singapore International Conference on Communication Systems. Guangzhou,China,2008:258-262. |
| [12] | 朱联祥,李想.基于子集矩阵的LDLC短环消除方法[J].电视技术,2014,38(3):131-134,166. |