多进制线性分组码的线性规划译码方法

摘要

本发明公开了一种多进制线性分组码的线性规划译码方法，主要解决现有技术译码复杂度高、译码速度慢、运算量大的问题。其实现步骤是：(1)生成多进制码字；(2)对多进制码字进行调制后发送到信道；(3)接收发送码字并从中获得软信息值；(4)利用软信息值，通过线性规划译码方法获得对发送码字的估计；(5)对估计结果取整并转换为多进制码字；(6)将多进制码字作为译码结果输出。本发明具有复杂度低、译码速度快、误码性能好、输出整数码字均为最大似然码字的优点，可用于深空通信、卫星通信、光纤通信以及大规模磁盘存储等高速率通信系统中。

说明书

技术领域

本发明属于信道译码技术领域，特别涉及一种多进制线性分组码的线性规划译码方 法，可用于深空通信和卫星通信等通信系统中。

背景技术

多年来，纠错码理论经过的国内外众多学者的努力，已取得了飞速的发展，工程应 用也得到了广泛的推广。比如，Turbo码已成为第三代移动通信系统中作为其传输高速数 据的信道编码标准，低密度奇偶校验LDPC码已在深空通信和电磁记录系统得到了广泛的 应用。随着信息时代的到来，人们对可靠性更强、速率更快的通信需求越来越迫切，然 而现有的技术仍然无法满足人们的需求，还需要进一步改善。多进制线性分组码与带宽 效率更高的高阶调制方式相结合就能实现数据的高速率传输，此外通过进一步改进译码 方法来提高通信系统的可靠性也同样意义重大。事实上，在工程中多进制分组码的译码 实现复杂度较高，因此研究利用复杂度低的译码器实现性能优异的译码算法尤为关键。

采用线性规划译码的方法是近年来较为热门的方法之一，与传统的译码算法如置信 传播BP译码算法相比，线性规划LP译码有着它自己独特的优势，因为LP译码是基于数学 规划进行的，所以LP译码能提供算法收敛性、复杂度以及算法合理性的理论分析依据。 早在2004年左右就有国外的学者Feldman等提出了LP译码算法，并将其译码性能与传统的 BP算法做了比较，也就是从那时开始，越来越多的人开始了LP译码的研究。直到2009年， Flanagan才提出多进制线性分组码的LP译码算法。但是由于Flanagan的LP译码算法的复杂 度随着问题规模呈指数增长，在工程中难于实现，因此他的方法并没有被广泛推广。于 是对于多进制线性分组码的LP译码算法，研究复杂度更低的算法成为了现阶段的一个主 要的课题。

LP译码算法提出了近10年的时间，尽管取得了很多成果，但是这些进步并不能掩盖 其发展中的不足：现有的多进制线性分组码LP译码算法的译码复杂度还是较高，导致其 在工程中存在较大的译码计算时延。

发明内容

本发明的目的在于针对背景中的不足之处，提出一种多进制线性分组码的线性规划 译码方法及其装置，在不影响系统误比特率性能的情况下，简化多进制线性分组码的译 码复杂度，提高译码速度。

为实现上述目的，本发明的技术方案包括如下步骤：

1.一种多进制线性分组码的线性规划译码方法，包括如下步骤：

(1)生成码字：

(1a)设定多进制校验矩阵H，并对该校验矩阵进行变换得到生成矩阵；

(1b)输入待编码的信息序列，用该待编码的信息序列乘以生成矩阵，得到一个2^q进 制线性分组码码字u，其中2^q为多进制线性分组码u的进制数；

(2)对分组码码字u进行调制：将多进制线性分组码码字u中的码元符号进行映射， 得到调制后的符号矢量序列s，并将其通过传输信道发送出去；

(3)接收信道发送的符号矢量序列，得到矢量序列r，计算矢量序列r中的软信息值：

(3a)将多进制校验矩阵H的列编号和行编号分别作为变量消息处理的编号i和校验 消息处理的编号j；

(3b)分别计算矢量序列r实部和虚部的初始概率：

$\left(\begin{array}{c}p\left(\mathrm{Re}\left(r_i\right)\right|\mathrm{Re}\left(s_i\right))=\frac{1}{\sqrt{\pi n_0}}\exp (-\frac{{(\mathrm{Re}\left(r_i\right)-\mathrm{Re}\left(s_i\right))}^2}{n_0})\\ p\left(\mathrm{Im}\left(r_i\right)\right|\mathrm{Im}\left(s_i\right))=\frac{1}{\sqrt{\pi n_0}}\exp (-\frac{{(\mathrm{Im}\left(r_i\right)-\mathrm{Im}\left(s_i\right))}^2}{n_0})\end{array}\right),$

其中，r_i为矢量序列r中第i个元素，s_i为调制后的符号矢量序列s中第i个元素， Re(r_i)和Im(r_i)分别代表矢量序列r中第i个元素的实部值和虚部值，Re(s_i)和Im(s_i)分别 代表调制后的符号矢量序列s中第i个元素的实部值和虚部值，p(Re(r_i)|Re(s_i))为矢量序 列r中第i个元素实部的初始概率，p(Im(r_i)|Im(s_i))为矢量序列r中第i个元素虚部的初始 概率，n₀为传输信道的噪声功率谱密度，i表示变量消息处理的编号，i＝1,2,...,n，n表 示多进制线性分组码码字与变量消息处理的编号对应的长度；

(3c)根据上述实部和虚部的初始概率p(Re(r_i)|Re(s_i))和p(Im(r_i)|Im(s_i))，分别计算多 进制线性分组码码字u中第i个元素u_i对应的比特x_i,t的条件概率p(r_i|x_i,t＝0)和 p(r_i|x_i,t＝1)，其中x为与多进制线性分组码码字u等价的二进制码字，x_i,t为二进制码字x 中的第i*t个元素，t＝1,2,...,q，i＝1,2,...,n，n表示多进制线性分组码码字与变量消息 处理的编号对应的长度；

(3d)按照上述比特x_i,t的条件概率p(r_i|x_i,t＝0)和p(r_i|x_i,t＝1)，计算矢量序列r中的软 信息值：

${\lambda }_{i,t}=\log \frac{p\left(r_i\right|x_{i,t}=0)}{p\left(r_i\right|x_{i,t}=0)},$

其中r_i为矢量序列r中第i个元素，u_i为发送的多进制线性分组码码字u中的第i个元 素；

(4)利用矢量序列r中的软信息值λ_i,t，通过线性规划译码方法得到二进制估计码字

(5)判断上述二进制估计码字中的元素是否都为整数，若是，则将二进制估计码字 转换成多进制估计码字否则，将二进制估计码字中的非整数元素按照四舍五入进 行取整，得到取整后的二进制估计码字，再将二进制估计码字转换成多进制估计码字

(6)将多进制估计码字作为输出的译码码字。

本发明与现有技术相比具有以下优点：

第一，由于本发明所构造的奇偶校验多面体，变量以及约束条件都远低于现有方法 构造的多面体，克服了现有技术译码速度慢，复杂度高的缺点，使得本发明显著提高了 译码效率，译码复杂度降低为多项式复杂度。

第二，由于本发明在译码时采用了线性规划译码方法，克服了现有技术中校验矩阵 中四环对于译码性能的影响，使得本发明具有了最大似然特性、误码性能好、误码平层 低的优势。

附图说明

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

图2为本发明与Flanagan提出的线性规划译码方法误码率性能仿真结果对比图。

具体实施方式

下面结合附图对本发明做进一步的描述。

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

步骤1，生成码字：

(1a)设定多进制校验矩阵H，并对该校验矩阵进行变换得到生成矩阵：

本发明实例中设定的多进制校验矩阵H是50行125列的16进制校验矩阵，矩阵元素是 16元有限环上的全部元素；

对多进制校验矩阵H进行变换得到生成矩阵，该变换方法可采用多种现有方法进行， 例如：高斯消元法、系统形式编码和三角分解法，本实例采用高斯消元法对多进制校验 矩阵H进行变换，得到生成矩阵；

(1b)输入待编码的信息序列，该信息序列是一个随机发送的行向量，且向量元素是 16元有限环上的全部元素，码字长度n＝125，信息位长度k＝50，编码效率为0.4；

(1c)用待编码的信息序列乘以生成矩阵，得到一个2^q进制线性分组码码字u，其中2^q为多进制线性分组码u的进制数。

步骤2，对分组码码字u进行调制。

该调制方法可采用多种调制方法进行，例如：16PSK、16QAM、16OWM等；

本实例中采用的是16QAM调制，即将生成码字中的每个码元映射到16QAM的符号星 座点上，使生成码字被调制成为一个符号矢量序列s，并将其通过传输信道发送出去。

步骤3，接收经信道传输后的符号矢量序列s，得到矢量序列r，并按如下步骤计算 矢量序列r中的软信息值：

(3a)将多进制校验矩阵H的列编号和行编号分别作为变量消息处理的编号i 和校验消息处理的编号j；

(3b)分别计算矢量序列r实部和虚部的初始概率：

$\left(\begin{array}{c}p\left(\mathrm{Re}\left(r_i\right)\right|\mathrm{Re}\left(s_i\right))=\frac{1}{\sqrt{\pi n_0}}\exp (-\frac{{(\mathrm{Re}\left(r_i\right)-\mathrm{Re}\left(s_i\right))}^2}{n_0})\\ p\left(\mathrm{Im}\left(r_i\right)\right|\mathrm{Im}\left(s_i\right))=\frac{1}{\sqrt{\pi n_0}}\exp (-\frac{{(\mathrm{Im}\left(r_i\right)-\mathrm{Im}\left(s_i\right))}^2}{n_0})\end{array}\right),$

其中，r_i为矢量序列r中第i个元素，s_i为调制后的符号矢量序列s中第i个元素， Re(r_i)和Im(r_i)分别代表矢量序列r中第i个元素的实部值和虚部值，Re(s_i)和Im(s_i)分别 代表调制后的符号矢量序列s中第i个元素的实部值和虚部值，p(Re(r_i)|Re(s_i))为矢量序 列r中第i个元素实部的初始概率，p(Im(r_i)|Im(s_i))为矢量序列r中第i个元素虚部的初始 概率，n₀为传输信道的噪声功率谱密度，i表示变量消息处理的编号，i＝1,2,...,n，n表 示多进制线性分组码码字与变量消息处理的编号对应的长度；

(3c)根据上述实部和虚部的初始概率p(Re(r_i)|Re(s_i))和p(Im(r_i)|Im(s_i))，分别计算多 进制线性分组码码字u中第i个元素u_i对应的比特x_i,t的条件概率p(r_i|x_i,t＝0)和 p(r_i|x_i,t＝1)，其中x为与多进制线性分组码码字u等价的二进制码字，x_i,t为二进制码字x 中的第i*t个元素，t＝1,2,...,q；

(3d)按照上述比特x_i,t的条件概率p(r_i|x_i,t＝0)和p(r_i|x_i,t＝1)，计算矢量序列r中的软 信息值：

${\lambda }_{i,t}=\log \frac{p\left(r_i\right|x_{i,t}=0)}{p\left(r_i\right|x_{i,t}=0)},$

其中，r_i为矢量序列r中第i个元素，u_i为发送的多进制线性分组码码字u中的第i个 元素。

步骤4，获得二进制估计码字：

(4a)将多进制校验矩阵H中第j行非零元素组成行向量h_j，再将行向量h_j转化成二 进制等价行向量

${\bar{h}}_j=[2^{q-1}{h}_j,...,{2h}_j,h_j]\oplus 2^q,$

其中2^q为多进制线性分组码的进制数，为取模运算，j为校验消息处理的编号， j＝1,2,...,m，m为校验消息处理的编号对应的长度；

(4b)利用二进制等价行向量通过如下公式构造第j个校验消息处理所对应的码 字集合多面体

其中为x_j的转置；

(4c)将上述码字集合多面体进一步细化为码重为k的子多面体集合该集合 中的每一个多面体满足下式：

其中，x_j,k为第j个校验信息处理所包含的码重为k的局部二进制码字，k为码重；

(4d)将子多面体按如下所述方法松弛：在每一个子多面体中选取一个点x_j,k， 引入两个辅助变量，即向量z_k＝[z_k,1,z_k,2…,z_k,i,…z_k,d]和标量α_k，d为行向量的长度， 使其满足下述关系：

${\alpha }_k{x}_{j,k}=z_k./{\bar{h}}_j,$

其中./代表两个向量对应元素分别做除法运算，向量z_k中的元素z_k,i与α_k还需满足 $0\le z_{k,i}\le {\alpha }_k{\bar{h}}_{j,i},\underset{i=1}{\overset{d}{\Sigma }}{z}_{k,i}=2^q{\mathrm{k\alpha }}_k,\underset{k}{\Sigma }{\alpha }_k=1$这三个条件，为行向量中的元素， i＝1,…,d；

(4e)通过上述的松弛方式即可得到松弛后的多面体

(4f)对松弛后的多面体取交集，得到奇偶校验多面体

(4g)将奇偶校验多面体中的顶点依次代入目标函数寻找使得目标函 数取值最小的顶点，将该顶点作为二进制估计码字的输出。

步骤5，对二进制估计码字中的元素进行整数判断。

判断二进制估计码字中的元素是否都为整数，若是，直接执行步骤(5b)，否则，执 行步骤(5a)；

(5a)将二进制估计码字中的分数码字按照四舍五入进行取整，得到取整后的二进 制估计码字，执行步骤(5b)；

(5b)将二进制估计码字转换成多进制码字，译码结束。

步骤6，将多进制估计码字作为输出的译码码字。

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

1.仿真条件

使用Matlab 7.11.0仿真软件，仿真次数为5000次，系统仿真的参数与实例中所述的 参数一致，传输信道为加性高斯白噪声信道。

2.仿真内容

对本发明以及Flanagan提出的方法分别进行误比特率BER性能仿真，并计算译码速 度的平均值。

3.仿真结果

仿真误比特率BER的性能曲线，如图2中所示，其中“三角形”曲线表示本发明的 误比特率，“加号形”曲线表示Flanagan提出的方法的误比特率BER性能曲线。图2中 横轴表示比特能量和噪声功率谱密度比，单位为分贝，纵轴表示误比特率。与此同时， 在仿真的过程中仿真软件记录了本发明和Flanagan方法的仿真所用的时间。

由图2的仿真结果可见，在相同比特能量和噪声功率谱密度比的条件下，本发明的 误比特率与Flanagan提出的线性规划译码方法的误比特率相同，均能获得很好的误比特 性能。

根据仿真软件记录的本发明仿真用时458秒和Flanagan方法的仿真用时5967秒，及 系统仿真的发送总帧数为5000帧，通过如下公式计算两种方法的译码速度：

通过计算可得本发明译码速度为0.0916秒/帧，而Flanagan方法译码速度为1.1934 秒/帧。

两者相比，本发明的译码速度比Flanagan方法提高了12倍。