一种用于删除信道的前向纠错码及其构造方法

摘要

本发明涉及一种用于删除信道的前向纠错码及其构造方法，其主要技术特点是：该前向纠错码由G_LDPC矩阵和G_LT矩阵构成，G_LDPC矩阵为GF(256)上的LDPC矩阵，G_LT矩阵为Raptor10码的LT矩阵；其构造方法包括以下步骤：构造G_LDPC矩阵，构造G_LT度生成函数、随机数生成函数、生成三元组函数，并构造G_LT矩阵。本发明在使用基于Raptor10码的G_LT矩阵的同时，将G_LDPC和G_HDPC合二为一，并将新的G_LDPC扩展到GF(256)；去掉了原有子矩阵后侧的单位矩阵，而改为依靠G_LDPC子矩阵自身构造来保证G_LDPC满秩性；改进了Raptor10中LT矩阵每行之间的线性无关性以提升性能。本发明构造的前向纠错码，其在译码复杂度和性能上相对于Raptor10和RaptorQ具有较大的提升，可广泛用于广播通信传输领域。

说明书

技术领域

本发明属于广播通信技术领域，涉及前向纠错码，尤其是一种用于删除信道的前向纠错码及其构造方法。

背景技术

在通信传输中，通信信道质量是影响信息传输的主要因素。为了保证通信系统的可靠性，通常使用反馈重传(ARQ)以及前向纠错(FEC)技术两种方法进行差错控制。传统的纠错码是固定码率的，无法适应多变信道。喷泉码是一种新兴的前向纠错编码方式，作为一种无速率码，喷泉码可以应用于各种多变信道，其无需反馈和编译码复杂度低的特性降低了传输时延。因此，喷泉码在高可靠低时延的广播通信系统中具有重要的研究价值和意义。

自动请求重传即信道发送端根据接收端的反馈重传信息，以此确保接收端收到所有信息。反馈总是存在时延，对于极差信道，反馈带来的开销极大，因此，通过LDPC码、Turbo码等码字辅助译码的前向纠错技术得以被提出。发送端通过编码增加部分冗余，接收端则通过这些冗余辅助纠正传输出错的信息，这类码字编码传输信息之前需要提前预估信道状态，然后根据信道情况预设合适的码率。尽管这种编码方式确实带来了一定的传输性能提升，但是却很难为时变的信道提供合适的估计值，因此，这种方式难以应用于复杂多变的信道。针对上述差错控制码的难题，以喷泉码为代表的无速率码应运而生，无速率码的无速率体现在编码码字无固定码率，编码端不停编码，直到接收端收到足够的编码包并且译码成功，因此编码端生成的编码包数量不是一个固定值，码率自然也就无法固定了。现有的国际标准中推荐的前向纠错码为Raptor10和RaptorQ。虽然两个码以其新颖的构造和优良的性能独树一帜,并在众多领域获得了广泛的应用。但是，Raptor10与RaptorQ在性能和应用上都存在不足。具体表现为：

Raptor10的不足表现为：(1)虽然译码复杂度低，但是性能并不好，根据仿真结果，在接收为K+10个符号的条件下，译码成功率才能到达99％以上。(2)其构造在GF(2)上，信息处理速度有限，一个Byte的源数据还要分成8个bit的源数据才能使用；而且限制元素在GF(2)上，由于其生成矩阵A容易产生行相关，其性能很难再有突破。(3)其LT矩阵设计并不太优，行与行之间的线性无关性，随修复包的增多而变差。(4)在RaptorQ中，改进了LT矩阵的设计，同时将G_HDPC从GF(2)扩展到GF(256)，以提高矩阵A的满秩可能性，大大提升性能。

RaptorQ的不足表现为：尽管性能优异，但译码复杂度太大，结构过于复杂，A矩阵子元素多，尤其是G_HDPC的非零元素密度很大，增加了译码复杂度。这种问题在K很大时尤为突出，因为随着K的增大，G_HDPC虽然行数没增加，但是列数增大，进而非零元素数目增加显著，译码时间增大。

综上所述，如何提高前向纠错码的性能是目前所需要解决的问题。

发明内容

本发明的目的在于克服现有技术的不足，提出一种设计合理、性能稳定且译码复杂度低的用于删除信道的前向纠错码及其构造方法。

本发明解决其技术问题是采取以下技术方案实现的：

一种用于删除信道的前向纠错码，由G_LDPC矩阵和G_LT矩阵构成，所述G_LDPC矩阵为GF(256)上的LDPC矩阵，其大小为S*(K+S)；所述G_LT矩阵为Raptor10码的LT矩阵，其大小为K*(K+S)；其中，S为G_LDPC矩阵的行数，K为源符号个数。

一种用于删除信道的前向纠错码的构造方法，其特征在于：包括以下步骤：

步骤S1、构造G_LDPC矩阵：将G_LDPC元素从GF(2)上扩展到GF(256)上，构造出GF(256)上的稀疏矩阵；

步骤S2、构造G_LT度生成函数，该函数的输入参数为v，输出为度d；

步骤S3、构造随机数生成函数，该函数的输入参数为一个三元组X、i和m，其中X和i是一个非负整数，m为一个正整数，输出为生成值；

步骤S4、构造生成三元组函数，该函数的输入参数为一个二元组SI和ESI的值，输出为一个三维向量d、a和b；

步骤S5、构造G_LT矩阵。

进一步，所述步骤S1的具体实现方法包括以下步骤：

步骤S1.1、初始化G_LDPC矩阵，其中行数为S，列数为L，整个矩阵为零矩阵；

步骤S1.2、初始化变量i为0，其后每次转入此步骤i＝i+1，当i＝L时，G_LDPC矩阵构造完成，步骤S1结束；

步骤S1.3、设变量a，其值为1+mod(floor(i/S),(S-1))；

步骤S1.4、设变量b，其值为mod(i,S)；

步骤S1.5、计算G_LDPC矩阵中横坐标为b+1，纵坐标为i+1的符号值，其值等于bitxor(G_LDPC(b+1,i+1),mod((b+1)*(i+b+1)+i*i,base-1)+1)；

步骤S1.6、若由S1.5转入此步骤，则初始化变量j为1；若由S1.8转入此步骤，则j＝j+1，当j的值为CE时，转步骤S1.2；

步骤S1.7、设置b值为mod(b+a,S)；

步骤S1.8、计算G_LDPC矩阵中横坐标为b+1，纵坐标为i+1的符号值，其值等于bitxor(G_LDPC(b+1,i+1),mod((b+1)*(i+b+1)+i*i,base-1)+1)，转步骤S1.6。

进一步，所述步骤S2的具体实现方法包括以下步骤：

步骤S2.1、定义度分布表，通过索引j的值查表得到d[j]；

步骤S2.2、初始化变量j为0，其后每次转入此步骤j＝j+1；

步骤S2.3、通过度分布表判断，如果v

进一步，所述步骤S3的具体实现方法包括以下步骤：

步骤S3.1、设变量InputV0的值为V0(mod(X+i,256)+1)；

步骤S3.2、设变量InputV1的值为V1(mod(floor(X/256)+i,256)+1)；

步骤S3.3、计算mod(bitxor(InputV0,InputV1),m)的值，得到Rand函数的返回值，步骤3结束。

进一步，述步骤S4的具体实现方法包括以下步骤：

步骤S4.1、设变量A的值为mod(53591+SI*997,Q)；

步骤S4.2、设变量B的值为mod(10267*(SI+1),Q)；

步骤S4.3、设变量Y的值为mod(B+ESI*A,Q)；

步骤S4.3、设变量v的值为Rand(Y,0,2^^20)，该Rand为步骤3的生成流程；

步骤S4.5、设变量d的值为Deg(v)；

步骤S4.6、设变量a的值为1+Rand(Y,1,L’-1)；

步骤S4.7、设变量b的值为Rand(Y,2,L’)；

步骤S4.8、返回三元组(d,a,b)；

进一步，述步骤S5的具体实现方法包括以下步骤：

步骤S5.1、初始化G_LT矩阵为全零矩阵，其中行数为K，列数为L；

步骤S5.2、构造d_Triple矩阵，其中行数为1，列数为S_Max，初始化矩阵为全零矩阵；

步骤S5.3、构造a_Triple矩阵，其中行数为1，列数为S_Max，初始化矩阵为全零矩阵；

步骤S5.4、构造b_Triple矩阵，其中行数为1，列数为S_Max，初始化矩阵为全零矩阵；

步骤S5.5、初始化变量ii为1，其后每次转入此步骤ii＝ii+1，当ii＝S_Max时，转步骤S5.7；

步骤S5.6、执行三元组函数Triple(SI,ii-1)，返回的三元组分别赋值给d_Triple(ii)，a_Triple(ii)和b_Triple(ii)并转步骤S5.5；

步骤S5.7、初始化变量ESI为1，其后每次转入此步骤ESI＝ESI+1，当ESI＝K+1时步骤3结束；

步骤S5.8、设变量d_i，d_i的值为d_Triple(ESI)；

步骤S5.9、设变量a_i，a_i的值为a_Triple(ESI)；

步骤S5.10、设变量b_i，b_i的值为b_Triple(ESI)；

步骤S5.11、当b_i大于等于L时，b_i的值重设为mod(b_i+a_i,L),直至b_i≤L；

步骤S5.12、赋值G_LT(ESI,b_i+1)为1；

步骤S5.13、若由S5.12转入此步骤，则初始化变量j为1；若由S5.16转入此步骤，则j＝j+1，当j＝min(d_i-1,L-1)+1时，转步骤S5.7；

步骤S5.14、赋值b_i为mod(b_i+a_i,L)；

步骤S5.15、当b_i大于等于L时，b_i的值重设为mod(b_i+a_i,L),直至b_i≤L；

步骤S5.16、赋值G_LT(ESI,b_i+1)为bitxor(G_LT(ESI,b_i+1),1)，转步骤S5.13。

本发明的优点和积极效果是：

本发明重新设计了编码矩阵A的架构，使用基于Raptor10码的G_LT矩阵的同时，将G_LDPC和G_HDPC合二为一，并将新的G_LDPC扩展到GF(256)；去掉了原有子矩阵后侧的单位矩阵，而改为依靠G_LDPC子矩阵自身构造来保证G_LDPC满秩性；增大了编码矩阵A的行数，以改进Raptor10中LT矩阵每行之间的线性无关性以提升性能。本发明构造的全新结构的前向纠错码(命名为RaptorG码)，其在译码复杂度和性能上相对于Raptor10和RaptorQ具有较大的提升。

附图说明

图1是Raptor10码的生成矩阵构造图；

图2是本发明中RaptorG码的生成矩阵构造图。

具体实施方式

以下结合附图对本发明做进一步详述。

本实施例用到的基本符号及基本函数如表1所示。

表1.基本符号及基本函数

本发明提出的前向纠错码(RaptorG码)解决的根本问题可以归结于A*C＝D。其中A为编码矩阵，由LT等矩阵构成，C为生成的中间符号，D为接收符号。无论编码、解码根本问题都是求解中间符号C，也就是编码矩阵A求逆。

现有的Raptor10码的构造如图1所示,其中G_LDPC为GF(2)上的稀疏矩阵，大小为S*K，具备较好的行线性无关性。G_HDPC为GF2上的高密度矩阵，大小为H*(K+S)，其非零元素密度为1/2。G_LT为LT矩阵，其非零元素密度非常低。

本发明提出的一种用于删除信道的前向纠错码(RaptorG码)的编码矩阵如图2所示，由G_LDPC矩阵和G_LT矩阵构成，其中，G_LDPC为GF(256)上的LDPC矩阵，大小为S*(K+S)，G_LT为LT矩阵，大小为K*(K+S)，其构造同Raptor10的LT矩阵。

基于上述用于删除信道的前向纠错码(RaptorG码)，本发明提出一种用于删除信道的前向纠错码的构造方法，包括以下步骤：

步骤S1、构造G_LDPC矩阵，首先初始化G_LDPC矩阵为全零矩阵，然后按照算法每一列赋予CE个非零元素。

步骤S1.1、初始化G_LDPC矩阵，其中行数为S，列数为L，整个矩阵为零矩阵；

步骤S1.2、初始化变量i为0，其后每次转入此步骤i＝i+1，当i＝L时算法结束，G_LDPC构造完成，步骤S1结束；

步骤S1.3、设变量a，其值为1+mod(floor(i/S),(S-1))；

步骤S1.4、设变量b，其值为mod(i,S)；

步骤S1.5、计算G_LDPC矩阵中横坐标为b+1，纵坐标为i+1的符号值，其值等于bitxor(G_LDPC(b+1,i+1),mod((b+1)*(i+b+1)+i*i,base-1)+1)；

步骤S1.6、若由S1.5转入此步骤，则初始化变量j为1；若由S1.8转入此步骤，则j＝j+1，当j的值为CE时，转步骤S1.2；

步骤S1.7、设置b值为mod(b+a,S)；

步骤S1.8、计算G_LDPC矩阵中横坐标为b+1，纵坐标为i+1的符号值，其值等于bitxor(G_LDPC(b+1,i+1),mod((b+1)*(i+b+1)+i*i,base-1)+1)，转步骤S1.6；

本发明构造的G_LDPC的结构特点包含以下三点：

(1)延续Raptor10的G_LDPC基本架构，将G_LDPC元素从GF(2)上扩展到GF(256)上，构造出GF(256)上的稀疏矩阵。G_LDPC的取值和元素位置(i,b)相关，通过扩展到2次方、3次方的方式，破坏掉原有斜对角元素i+b相等的情况，使得非零元素取值更加离散，以提高G_LDPC的行线性无关性；同时因为G_LDPC在GF(256)上，所以也提高了G_LDPC与G_LT线性无关的概率，进而提高A的满秩概率。

(2)对比于Raptor10，大大增大S值也就是G_LDPC行数。一般来说，S≈K/2。增加S值可以带来的好处如下：

①G_LDPC的梯形结构可以带来天然的行线性无关性，同时由于元素都在GF(256)上，则线性无关性更大。随着S的增大，底下的LT矩阵的列数增加，但每一行中1的个数不变，则每一列中1的个数会减少，这就显著改善了与上层G_LDPC矩阵发生线性相关的可能性，进而提高矩阵A的满秩概率；

②S的增加可以导致G_LT矩阵向扁平化发展，同样的度分布下，非零元素的分布会更加的稀疏，可以提高G_LT矩阵行的线性无关性，进而提高矩阵A的满秩概率；

③S的增加使得G_LT更加扁平，则在冗余很大的条件下，比如K个源数据包喷出K个冗余数据包。若S较小，则从2K发送包中选择K个接受包，A的满秩概率也会比较小。若S较大，则从2K发送包中选择K个接受包，A的满秩概率会大很多；典型的，在RaptorG中S通常设置为K/2，则RaptorG中的A矩阵大小为3/2K*3/2K，而RaptorQ中S,H值相对于K是一个很小的数值，则RaptorQ的A矩阵大小为(K‘+S+H)*(K’+S+H)，比RaptorG的A矩阵要小的多。例如K＝1000时，RaptorG的A矩阵大小为1503*1503，而RaptorQ的A矩阵大小为1071*1071。两者都喷出K，则接收LT矩阵大小分别为2000*1503和2000*1071，这两个矩阵之中选取1000行，在行重和非零元素分布类似的情况下，显然宽度越大的矩阵，这1000行越容易形成行满秩。

④S的增加虽然增加了译码复杂度，但由于G_LDPC是一个稀疏阵，且随着K的增大而更加稀疏，并不会像G_HDPC那样显著增加译码复杂度。同时S的增加具备上述各项好处，故总体来讲，S的增加利大于弊；

(3)去掉了G_HDPC以减少译码复杂度，G_HDPC非零元素密度太大，导致译码复杂度高，对于RaptorQ来说更是如此。RaptorQ的G_HDPC非零元素比Raptor10的G_HDPC非零元素密度还要大。可以说，G_HDPC的存在导致了译码复杂度过高。RaptorG通过GF(256)上的G_LDPC结构，同时具备了非零元素的稀疏性以保证译码复杂度不过高，以及GF(256)所带来的高线性无关性，大大提升了A的满秩概率。相对于Raptor10，大大提升了性能；相对于RaptorQ，大大降低了复杂度，同时性能不降。

步骤S2、构造G_LT度生成函数(Deg函数)，函数的输入参数为v，输出为度d。

本步骤生成的Deg函数与Raptor10的构造方法相同，包括以下步骤：

步骤S2.1、定义度分布表，通过索引j的值查表得到d[j]，如表2所示。

表2.G_LT度分布表

步骤S2.2、初始化变量j为0，其后每次转入此步骤j＝j+1；

步骤S2.3、通过查表2判断，如果v

步骤S3、构造随机数生成函数(Rand函数)，函数的输入参数为一个三元组X，i和m，其中X和i是一个非负整数，m为一个正整数，输出为生成值。

步骤S3.1、设变量InputV0的值为V0(mod(X+i,256)+1)。

步骤S3.2、设变量InputV1的值为V1(mod(floor(X/256)+i,256)+1)。

步骤S3.3、计算mod(bitxor(InputV0,InputV1),m)的值，得到Rand函数的返回值，步骤3结束。

步骤S4、构造生成三元组函数(Triple函数)，函数的输入参数为一个二元组SI和ESI的值，输出为一个三维向量d，a和b。

步骤S4.1、设变量A的值为mod(53591+SI*997,Q)；

步骤S4.2、设变量B的值为mod(10267*(SI+1),Q)；

步骤S4.3、设变量Y的值为mod(B+ESI*A,Q)；

步骤S4.3、设变量v的值为Rand(Y,0,2^^20)，这里的Rand为步骤3的生成流程；

步骤S4.5、设变量d的值为Deg(v)；

步骤S4.6、设变量a的值为1+Rand(Y,1,L’-1)；

步骤S4.7、设变量b的值为Rand(Y,2,L’)；

步骤S4.8、返回三元组(d,a,b)；

步骤S5、构造G_LT矩阵。

本步骤构造G_LT矩阵方法与Raptor10相同，具体实现方法为：

步骤S5.1、构造G_LT矩阵，其中行数为K，列数为L，初始化矩阵为全零矩阵；

步骤S5.2、构造d_Triple矩阵，其中行数为1，列数为S_Max，初始化矩阵为全零矩阵；

步骤S5.3、构造a_Triple矩阵，其中行数为1，列数为S_Max，初始化矩阵为全零矩阵；

步骤S5.4、构造b_Triple矩阵，其中行数为1，列数为S_Max，初始化矩阵为全零矩阵；

步骤S5.5、初始化变量ii为1，其后每次转入此步骤ii＝ii+1，当ii＝S_Max时，转步骤S5.7；

步骤S5.6、执行函数Triple(SI,ii-1)，返回的三元组分别赋值给d_Triple(ii)，a_Triple(ii)和b_Triple(ii)并转步骤S5.5；

步骤S5.7、初始化变量ESI为1，其后每次转入此步骤ESI＝ESI+1，当ESI＝K+1时步骤3结束；

步骤S5.8、设变量d_i，d_i的值为d_Triple(ESI)；

步骤S5.9、设变量a_i，a_i的值为a_Triple(ESI)；

步骤S5.10、设变量b_i，b_i的值为b_Triple(ESI)；

步骤S5.11、当b_i大于等于L时，b_i的值重设为mod(b_i+a_i,L),直至b_i≤L；

步骤S5.12、赋值G_LT(ESI,b_i+1)为1；

步骤S5.13、若由S5.12转入此步骤，则初始化变量j为1；若由S5.16转入此步骤，则j＝j+1，当j＝min(d_i-1,L-1)+1时，转步骤S5.7；

步骤S5.14、赋值b_i为mod(b_i+a_i,L)；

步骤S5.15、当b_i大于等于L时，b_i的值重设为mod(b_i+a_i,L),直至b_i≤L；

步骤S5.16、赋值G_LT(ESI,b_i+1)为bitxor(G_LT(ESI,b_i+1),1)，转步骤S5.13，SI的取值见表3；

表3.RaptorG关键参数

RaptorG的G_LT矩阵构造类似于Raptor10的G_LT矩阵，S的增大，使得G_LT更加扁平化，以提高矩阵A的满秩概率。同时也提升了大冗余条件下，接收G_LT满秩的概率，进而改善大冗余条件下的接收性能，从后续的仿真结果来看，在大冗余条件下的译码成功概率也是满意的。由于RaptorG的G_LDPC的重构，对每一个K，需要重新搜索匹配的SI。

下面对本发明构建的RaptorG码的译码过程进行说明。

Raptor10的失活译码算法是一个非常高效的译码算法，其运算速度大大优于传统的高斯消元算法。但RaptorG的G_LDPC矩阵是在GF(256)上的，因此需要将此失活算法从GF(2)上扩展到GF(256)上，需要注意以下几个基本操作的更改：

(1)矩阵A的两行互换，对应D的两行互换，在GF(256)上同样操作；

(2)矩阵A的两列互换，对应C的两行互换，在GF(256)上同样操作；

(3)矩阵A的某一行A(i,:)要对另外一行A(j,:)进行高斯消除，清零的列为第k列，对应GF(256)上需要做两个操作，

a)若A(i,k)>1，则行a所有元素A(i,:)＝A(i,:)/A(i,k),对应的D(i)＝D(i)/A(i,k),将A(i,k)元素归1,这里的除法(/)是GF(256)上的除法；

b)行A(j,:)＝A(j,:)+A(j,k)*A(i,:)，对应的D(j)＝D(j)+A(j,k)*D(i)，这里的*,+都是GF(256)上的运算，可以通过查表法求值，在我们的仿真中，直接调用了Matlab的GF函数。通过上述操作，则A(j,k)被清零；

(4)做高斯消元时，行选择按照Raptor10上的选择方式，需要计算最大的component，其过程复杂，在参考文献[3]中，Kim提出了一个比较简便易于计算的方法，RaptorG采用了该方法，适当减少了复杂度。

综上，RaptorG的G_LDPC与G_LT都是非零元素低密度的，尽管RaptorG的A矩阵行列数比较大，但是其非零元素总个数对比RaptorQ还要少一半左右。因此，其译码复杂度也要远低于RaptorQ，非零元素个数详见表4所示。

表4.非零元素个数对比表

下面通过一个仿真测试，对本发明的性能进行说明。

测试环境配置如表5所示。

表5.测试环境配置表

由于程序是单线程程序，故仿真结果与CPU核心数目关系不大。

RaptorG码性能如下，RaptorG码虽然基于Raptor10的LT矩阵构造，但其性能远超Raptor10，因此，性能对比选择RaptorQ：(K个源符号，喷出K个冗余符号，即冗余率为1，表中深色底色的为RaptorQ性能，浅色底色的为RaptorG性能。RaptorQ性能通过公式计算得出，RaptorG的性能通过仿真得出，RaptorQ的计算时间通过仿真一帧来确定，K>200时，简单写为>(K＝200的用时))。详细仿真结果如表6和表7所示。

表6.仿真结果1

表7.仿真结果2

根据上表所示，RaptorG码在性能不弱于RaptorQ的前提下，其译码复杂度远低于RaptorQ。由于RaptorQ的译码采用了查表计算，相对较慢，而RaptorG码的译码直接调用了Matlab的GF函数，该函数在乘法进行了部分优化，故实际译码速度差距并没有上表所示那么大。尽管RaptorG的A矩阵行列数较大，但在比较两者A的非零元素个数中，RaptorG的非零元素个数约为RaptorQ的一半，经过仿真验证RaptorG译码速度较RaptorQ有质的提升。

需要强调的是，本发明所述的实施例是说明性的，而不是限定性的，因此本发明包括并不限于具体实施方式中所述的实施例，凡是由本领域技术人员根据本发明的技术方案得出的其他实施方式，同样属于本发明保护的范围。