基于查表法的LDPC码交替方向乘子译码方法

摘要

本发明公开了一种基于查表法的LDPC码交替方向乘子译码方法，主要解决该译码方法中欧几里德投影计算复杂度高的问题。其技术方案是：(1)构造存储表，用于存储实数向量的欧几里德投影向量；(2)构造辅助数组帮助查找投影向量；(3)输入一个实数向量并将其量化处理，得到量化向量；(4)对量化向量进行一一映射，得到映射向量；(5)对映射向量各分量按升序排序，得到排序向量；(6)通过辅助数组，在存储表中查找排序向量对应的投影向量；(7)将查找到的投影向量各分量恢复原有顺序，得到欧几里德投影向量并输出。仿真结果表明，本发明不仅降低了欧几里德投影方法计算复杂度，得到了相似的纠错性能，而且提高了译码速度，可用于对LDPC码的译码。

说明书

技术领域

本发明属于通信技术领域，特别涉及一种基于查表法的LDPC码交替方向乘子译码方法。

背景技术

逼近香农限的低密度奇偶校验LDPC码由于其结构灵活、校验矩阵稀疏性、译码复杂度低等优点而已广泛应用于光纤通信、深空通信、卫星数字视频和音频广播等领域，而且已经是近年信道编码领域研究的热点问题。

目前，LDPC码的译码方法主要分为消息传递类方法和线性规划译码方法两类。基于凸优化理论的线性规划译码方法具有最大似然认证特性，便于数学分析，但未能充分利用LDPC码校验矩阵稀疏的特点，所以译码复杂度较高。和积译码算法、最小和译码算法等消息传递类方法的优点是实现简单、译码复杂度低，但其不足是易受短环境影响、难以进行数学分析、存在错误平层。

Barman等人提出了一种基于交替方向乘子法ADMM的线性规划译码方法，这种译码方法可显著降低LDPC码译码复杂度，同时具有传统线性规划译码的最大似然认证特性和便于数学分析的特点。其不足是现有的基于ADMM的线性规划译码方法每次迭代在更新校验节点消息时要执行大量耗时的欧几里德投影运算。目前，LDPC码的ADMM线性规划译码中常用欧几里德投影算法有两种，一是X.Zhang and P.H.Siegel,“Efficient iterative LP decoding of LDPC codes with alternating direction method of multipliers,”in Proc.IEEE Int.Symp.Inf.Theory,Istanbul,Turkey,July 2013,pp.1501–1505.；二是G.Zhang,R.Heusdens,and W.B.Kleijn,“Large scale LP decoding with low complexity,”IEEE Commun.Lett.,vol.17,no.1,pp.2152–2155,Nov.2013.中设计的方法。但这两种投影方法都比较复杂，涉及的运算量较大，要耗费大量的运算时间，从而导致译码速度较慢。

发明内容

为解决上述已有方法的不足，本发明提出了一种基于查表法的LDPC码交替方向乘子译码方法，以降低LDPC码的ADMM线性规划译码的复杂度，提高计算投影向量的速度。

实现本发明的技术方案是：利用校验多包体的性质，设计一种表格存储投影向量，通过查表可找到任一d维向量在校验多包体的投影向量，其实现步骤包括如下：

(1)设置初始化参数：

设置向量维数d＝6，设置存储表中投影向量的位置序号n＝1；

设置量化级数Q为正整数，量化区间端点值a和b均为实数，且a≠b；

(2)设置能存放6维实数向量的存储表TAB，用于存放欧几里德投影向量，并用TAB[n]表示TAB表中第n个投影向量，该存储表TAB共有4列，第1列为投影向量在TAB表位置序号，第2列为索引向量，第3列为量化向量，第4列为投影向量；

(3)构造辅助数组：

构造d-1个辅助数组T₁，T₂，…，T₅，每个数组均含有Q个元；

用T₁[i]表示第一辅助数组T₁的第i个元素，存储各分量值均为i的索引向量(i,i,i,i,i,i)的位置序号；

用T₂[i]表示第二辅助数组T₂的第i个元素，存储从该索引向量第2个分量开始的5维初始向量(i,i,i,i,i)到5维终止向量(i,Q,Q,Q,Q)的向量个数；

用T₃[i]表示第三辅助数组T₃的第i个元素，存储从该索引向量第3个分量开始的4维初始向量(i,i,i,i)到4维终止向量(i,Q,Q,Q)的向量个数；

用T₄[i]表示第四辅助数组T₄的第i个元素，存储从该索引向量第4个分量开始的3维初始向量(i,i,i)到3维终止向量(i,Q,Q)的向量个数；

用T₅[i]表示第五辅助数组T₅的第i个元素，存储从该索引向量第5个分量开始的2维初始向量(i,i)到2维终止向量(i,Q)的向量个数，其中i＝1,2,…,Q；

(4)输入一个6维实数向量v＝(v₁,…,v_j,…,v₆)，其中v_j为第j个分量，j＝1,2,….6；

(5)对实数向量v各分量v_j在区间[a,b]上进行Q级均匀量化，量化的间隔为量化后，得到量化向量其中为第j个分量；

(6)对量化向量的各分量值进行一一映射，得到映射向量w＝(w₁,w₂,w₃,w₄,w₅,w₆)；

(7)对映射向量w的各分量进行升序排序，得到排序向量w′＝(w′₁,w′₂,w′₃,w′₄,w′₅,w′₆)，且有w′₁≤w′₂≤w′₃≤w′₄≤w′₅≤w′₆；

(8)通过辅助数组，在表TAB中查找排序向量w′对应的投影向量z′；

(9)将投影向量z′的各分量恢复原有顺序，得到实数向量v的欧几里德投影向量z并输出。

本发明设计了一种表格来存储校验多包体上的欧几里德投影向量，并通过辅助数组在表格中查找任一向量的投影向量，与现有欧几里德投影运算相比，本发明方法降低了计算复杂度，取得了相似的纠错性能，而且提高了译码速度。

附图说明

图1是本发明的实现流程图；

图2是本发明与现有方法的译码性能对比图；

图3是本发明与现有方法的译码收敛速度对比图。

具体实施方式

以下结合附图对本发明的具体实例和具体效果作进一步描述。

参照图1，本发明的实现步骤如下：

步骤1，设置初始化参数。

本发明参数包括实数向量维数d，量化级数Q，量化区间端点值a和b，存储表TAB中投影向量位置序号n，其中d、Q和n为正整数，a和b为实数，且a≠b。在实施例中设置d＝6，n＝1。

步骤2，构造存储表TAB。

设置能存放6维实数向量的存储表TAB，用于存放欧几里德投影向量，并用TAB[n]表示TAB表中第n个投影向量，该存储表TAB共有4列，第1列为投影向量在TAB表位置序号，第2列为索引向量，第3列为量化向量，第4列为投影向量。

所述欧几里德投影向量为实数向量在检验多面体PP_d上的投影向量，可用(u)表示实数向量u在PP_d上的欧几里德投影向量，该检验多面体PP_d是由长度为d且含偶数个1的二元向量构成的凸包，表示为：PP_d＝conv(P_d)，其中P_d＝{x∈{0,1}^d|||x||₁为偶数}，||x||₁为向量x的1范数，d为正整数。

步骤3，构造辅助数组。

构造d-1个辅助数组T₁，T₂，…，T₅，每个数组均含有Q个元；

用T₁[i]表示第一辅助数组T₁的第i个元素，存储各分量值均为i的索引向量(i,i,i,i,i,i)的位置序号；

用T₂[i]表示第二辅助数组T₂的第i个元素，存储从该索引向量第2个分量开始的5维初始向量(i,i,i,i,i)到5维终止向量(i,Q,Q,Q,Q)的向量个数；

用T₃[i]表示第三辅助数组T₃的第i个元素，存储从该索引向量第3个分量开始的4维初始向量(i,i,i,i)到4维终止向量(i,Q,Q,Q)的向量个数；

用T₄[i]表示第四辅助数组T₄的第i个元素，存储从该索引向量第4个分量开始的3维初始向量(i,i,i)到3维终止向量(i,Q,Q)的向量个数；

用T₅[i]表示第五辅助数组T₅的第i个元素，存储从该索引向量第5个分量开始的2维初始向量(i,i)到2维终止向量(i,Q)的向量个数，其中i＝1,2,…,Q。

步骤4，输入一个6维实数向量v＝(v₁,…,v_j,…,v₆)，其中v_j为第j个分量，j＝1,2,…,6。

步骤5，量化实数向量v。

对实数向量v各分量v_j在区间[a,b]上进行Q级均匀量化，量化的间隔为量化后，得到量化向量其中为第j个分量，

Q(v_j)表示对v_j进行Q级均匀量化，表示小于等于的最大整数，q_k为该集合的第k个元素，q_k＝a+(k-1)τ,k＝1,2,…,Q。

步骤6，映射量化向量

对量化向量各分量取值通过映射函数进行一一映射，即用映射函数分别把各分量的取值q₁，…，q_k，…，q_Q依次映射为1，…，k，…，Q，其中k＝1,2,…,Q。映射后，将得到的映射向量记为：w＝(w₁,w₂,w₃,w₄,w₅,w₆)。

步骤7，对映射向量w的各分量进行升序排序，得到排序向量w′＝(w′₁,w′₂,w′₃,w′₄,w′₅,w′₆)，且有w′₁≤w′₂≤w′₃≤w′₄≤w′₅≤w′₆。

步骤8，通过辅助数组，在存储表TAB中查找排序向量w′对应的投影向量z′。

8a)根据第一个分量w′₁进行一次查找，并计算第一辅助序号n₁＝T₁[w′₁]-1；

8b)根据第二个分量w′₂进行二次查找，并计算第二辅助序号n₂：

若w′₁≥w′₂-1，则n₂＝n₁+T₂[w′₁]；

若w′₁<w′₂-1，则n₂＝n₁+T₂[w′₁]+T₂[w′₁+1]+…+T₂[w′₂-1]；

8c)根据第三个分量w′₃进行三次查找，并计算第三辅助序号n₃：

若w′₂≥w′₃-1，则n₃＝n₂+T₃[w′₂]；

若w′₂<w′₃-1，则n₃＝n₂+T₃[w′₂]+T₃[w′₂+1]+…+T₃[w′₃-1]；

8d)根据第四个分量w′₄进行四次查找，并计算第四辅助序号n₄：

若w′₃≥w′₄-1，则n₄＝n₃+T₄[w′₃]；

若w′₃<w′₄-1，则n₄＝n₃+T₄[w′₃]+T₄[w′₃+1]+…+T₄[w′₄-1]；

8e)根据第五个分量w′₅进行五次查找，并计算第五辅助序号n₅：

若w′₄≥w′₅-1，则n₅＝n₄+T₅[w′₄]；

若w′₄<w′₅-1，则n₅＝n₄+T₅[w′₄]+T₅[w′₄+1]+…+T₅[w′₅-1]；

8f)根据第六个分量w′₆进行六次查找，计算排序向量w′的位置序号n＝n₅+w′₆-w′₅+1；

8g)通过位置序号n在TAB表中找到对应的投影向量z′。

步骤9，将投影向量z′的各分量恢复原有顺序，得到实数向量v的欧几里德投影向量z并输出。

本发明的效果通过以下仿真进一步说明：

仿真内容：在加性高斯白噪声AWGN信道下，分别用本发明的投影方法和现有的ADMM中欧几里德投影方法对码率为0.5的(2640,1320)规则LDPC码进行译码，译码过程中使用本发明方法时分以下5种情况设置参数，分别为：

情况1：a＝-1.0，b＝2.0，τ＝0.2，Q＝16；

情况2：a＝-1.0，b＝2.0，τ＝0.3，Q＝11；

情况3：a＝-1.3，b＝2.3，τ＝0.3，Q＝13；

情况4：a＝-0.9，b＝1.9，τ＝0.4，Q＝8；

情况5：a＝-1.3，b＝2.3，τ＝0.4，Q＝10。

译码后，所得译码纠错性能如图2，译码收敛速度如图3所示。

由于文献[1]和[2]中的欧几里德投影方法在纠错性能方面的区别可忽略不计，因此在图2中用一条曲线表示二者的纠错性能；但在平均译码时间方面二者区别明显，所以在图3中用两条曲线分别表示二者的平均译码时间。

由图2可以看出，在情况1、2和4下，本发明方法的纠错性能弱于现有的ADMM译码方法纠错性能，而在情况3和5下本发明方法和现有的ADMM译码方法有相似的纠错性能。

由图3可以看出，在情况1、3和5下，本发明方法的收敛速度明显高于两种现有的ADMM译码方法。

综上，本发明设计的一种基于查表法的LDPC码交替方向乘子译码方法，不仅降低了现有交替方向乘子译码方法中欧几里德投影运算复杂度，取得了相似的纠错性能，而且提高了译码速度。