一种用于二元擦除信道前向纠错的喷泉编解码方法

摘要

一种用于二元擦除信道前向纠错的喷泉编解码方法，编码方法在维持同传统Raptor Codes编码算法相同输出的同时，无需计算中间节点，直接通过生成矩阵计算校验节点，更加高效和简单。解码方法在维持传统Raptor Codes相同冗余率的同时，无需计算中间节点，且对修复节点进行降度之后组成的矩阵Z′

说明书

技术领域

本发明属于通信领域，涉及一种二元擦除信道中进行前向纠错的喷泉编解码方法。

背景技术

随着通信技术的发展，使用编码技术解决数据传送过程中的安全问题成为计算机和通信领域研究的热点。在寻找逼近香农理想的“好码”过程中，由Michael Luby提出了LT Codes编解码方法。LT Codes具有线程的编码和多项式的解码时间，但也存在一些不足如解码的时空代价不固定等。为了克服LTCodes的局限，Amin Shokrollahi进一步提出了Raptor Codes编解码方法。Raptor Codes方法能够产生稍大于源节点集合的编码节点，对于任何给定的编码节点子集都能恢复出源节点；同时Raptor Codes编解码时间负载度控制在多项式以内，以上特性决定了Raptor Codes在通信传输上的二位元消除通道(Binary Erasure Channel，BEC)的文件传输中有着广泛的应用。其编解码方案如下：

Raptor Codes编码方法在发送端首先发送输入节点，在输入节点发送完毕后再发送修复节点。该编码方法分为两个阶段。第一阶段：对于给定的K个输入节点向量C<C₁，C₂，...，C_K>产生L个中间节点，其中L和K的关系满足L＝K+S+H，其中的S和H分别代表码率为的LDPC编码以及码率为的Half码的预编码过程。通过将K个输入节点前补S+H个值为零的新节点，使其扩充成L个预编码节点。对于L个预编码节点乘以对应的一个L×L的编码生成矩阵，得到L个中间节点。这L个中间节点组成中间节点向量M<M₁，M₂，...，M_L>，即M＝G1_L×L×C，其中L×L的矩阵G1_L×L代表着LDPC、Half码与LT码的生成矩阵。第二阶段：在第一阶段编码完成的基础上，对于给定的N个修复节点产生一个N×L的LT编码矩阵G2_N×L，这里的N同时也代表着发送过程中的系统冗余，N/K即为编码冗余度。根据等式R＝G2_N×L×M使用产生的L个中间节点向量M乘以G2_N×L，产生发送端的N个修复节点向量R<R₁，R₂，...，R_N>，完成整个编码过程。

从上述编码过程可以看出，Raptor Codes在编码的时候需要通过K个源节点计算出L(L＞K)个中间节点，然后通过中间节点进行LT编码计算出修复节点。从中间节点生成公式M＝G1_L×L×C可知，每个中间节点的生成，实际上是通过矩阵G1_L×L中对应的行向量同源结点向量相乘所得，因此每个中间节点的生成需要u个不同的源结点进行异或计算得到，其中u为矩阵G1_L×L中对应的行向量非零列的个数。显然，生成L个中间节点计算量复杂度为O(L)，需要进行大量节点之间的异或操作。

采用Raptor Codes进行解码时，由于擦除信道不可避免的误码率和丢包率，因此有N＞N’、K＞K’，对于接收到的由N’个修复节点和K’个源节点构成的已知编码节点集合E’，生成(N’+K’)×L的修复矩阵A，其中A满足等式E′＝A_{(N′+K′)×L}×M，且N’+K’＞＝L。根据上式的变形$M=A_{(N^{\prime }+K^{\prime })\times L}^{-1}\times E^{\prime },$可以通过对矩阵A进行高斯消元法修复中间节点向量M<M₁，M₂，...M_L>。修复好中间节点M之后，根据等式$C={G1}_{L\times L}^{-1}\times M$可以还原所有的源码节点向量C。

从上述解码过程可以看出，解码时需要处理大矩阵A_{(N′+K′)×L}，对大矩阵运算，目前数学上能够证明的时间复杂度一般是O(n³)，同时空间复杂度是O(n²)，n为运算复杂度。

正是由于上述原因，使得Raptor Codes方法的时间复杂度和空间复杂度都较大，对硬件的要求也比较高，不利于提高计算速度，从而影响发送端的发送效率以及接收端的接收效率，提高了系统硬件成本和时间成本。

发明内容

本发明的技术解决问题是：克服现有技术的不足，提供了一种计算速率高、资源占用量小的用于二元擦除信道前向纠错的喷泉编解码方法。

本发明的技术解决方案是：一种用于二元擦除信道前向纠错的喷泉编解码方法，包括编码方法和解码方法，

编码方法为：采用编码关系式R＝Z_N×K×C进行编码，其中向量C<C₁，C₂，...，C_K>为K个输入节点的集合，矩阵Z_N×K为矩阵A_N×L的后K列，A_N×L＝G2_N×L×G1_L×L，矩阵G1_L×L和矩阵G2_N×L为RFC 5053中定义的生成矩阵，N为修复节点的个数，L＝K+S+H，S和H分别代表码率为的LDPC编码以及码率为的Half码的预编码过程；

解码方法为：对所述修复节点进行降度操作，将所述修复节点同所有与其相关的已接收的源节点进行异或操作，使得所述修复节点仅同丢失的源节点相关，修复节点的度d_i为第i个修复节中含有的源节点的个数；然后将所有降度后的修复节点的度向量组成矩阵N’×k的矩阵Z’，所述度向量为行向量，若修复节点包含第m个丢失源节点则该行向量的第m个元素为1，其余元素为0，0＜m＜k，N’为接收到的修复节点个数，k为丢失的源节点个数，采用解码关系式R′＝Z′_N′×k×C′恢复丢失的源节点，其中向量C’<C’₁，C’₂，...，C’_k>为所有丢失的源节点集合，向量R’<R’₁，R’₂，...，R’_N’>为降度之后的修复节点集合。

所述解码算法中根据解码关系式R′＝Z′_N′×k×C′计算恢复丢失的源节点的方法为Maximum-Likelihood解码算法。

所述解码算法中进行降度操作的修复节点为同任意丢失的源节点相关的修复节点，修复节点是否同源节点相关根据矩阵Z_N×K来判断，若Z_N×K中第i行、第j列为1，则说明第i个修复节点同第j个源节点相关。

本发明与现有技术相比的优点在于：

(1)本发明的编码算法在维持同传统Raptor Codes编码算法相同输出的同时，无需计算中间节点，直接通过生成矩阵计算校验节点，更加高效和简单；本发明的解码算法在维持传统Raptor Codes相同冗余率的同时，无需计算中间节点，且对修复节点进行降度之后组成的矩阵Z′_N′×k大小只同二元擦除信道(BEC)的丢包率同源节点数目的乘积线性相关，远远小于传统Raptor Codes解码时所要处理大小同源节点数据线性相关的矩阵Z_N×K，因此本发明的解码算法占用资源和所用时间要远小于传统Raptor Codes的解码算法，更加高效和简单；

(2)本发明在解码过程中根据解码关系式R′＝Z′_N′×k×C′计算恢复丢失的源节点的方法为Maximum-Likelihood解码算法，使得需要解码所需冗余率同信道的丢包率接近，最大程度减少冗余度；

(3)本发明在降度操作之前，先判断需要降度的修复节点是否同任意丢失源节点相关，可以进一步缩小所要处理的修复节点个数，减少计算量，提高解码速度。

附图说明

图1为本发明的编码算法实施流程图；

图2为本发明的解码算法实施流程图；

图3为本发明方法中编码矩阵G_L×L¹的结构图；

图4为本发明方法中编码矩阵G2_N×L的结构图；

图5为本发明方法中编码矩阵A的子矩阵结构图；

图6为本发明方法中编码矩阵Z’的结构图；

图7为本发明实施例中涉及到的DVB-S2单向链路的大文件分发系统结构图；

图8为本发明实施例中编码消耗时间测试数据对比图；

图9为本发明实施例中解码矩阵处理消耗时间测试数据对比图；

图10为本发明实施例中解码消耗时间测试数据对比图。

具体实施方式

通过对传统Raptor Codes编解码方法的研究，本发明提出了一种编码冗余量小，计算时间复杂度小的前向喷泉(fountain)纠错编码方法，在此称为Rapid Raptor Godes，包括：编码方案和解码方案，其流程如图1和图2所示。喷泉(fountain)编码是一种新型的编码理论，含义是解码端无须接收某个特定节点，而只需要接收的节点数量超过一定的阈值，则能以一定成功率正确解码。

需要说明的是，本发明中以下算法中提到的所有矩阵和矩阵运算都是基于伽罗华域的GF(2)矩阵和矩阵运算，在此域内，乘法运算用与运算代替，加法运算用异或运算代替。

Rapid Raptor Codes编码方案

如图1所示，在本发明中，仿照传统的Raptor Godes编解码方法，由K个给定的输入节点通过预先生成的矩阵G1_L×L生成中间节点向量M<M₁，M₂，...，M_L>，这里的L×L的矩阵G1_L×L代表着预编码过程中LDPC、Half码与LT码的生成矩阵。L和K的关系满足L＝K+S+H，其中的S和H分别代表着码率为的LDPC编码以及码率为的Half码的预编码过程。矩阵G1_L×L中第i行为1的列代表着相应位置上的输入节点参与了生成中间节点的异或操作。G1_L×L的组成结构如图3所示。其中矩阵G_LDPC，G_Half，G_LT分别代表RFC 5053中描述的LDPC、Half码以及LT码的生成矩阵，其生成算法在RFC 5053中有详细定义，I_S和I_H为S×S和H×H的单位阵。0_S×H为S×H的零矩阵。

本发明按照RFC 5053中的描述，采用RFC 5053中定义的LT编码算法LTEnc( )产生一个N×L的LT编码矩阵G2_N×L。矩阵G2_N×L中第i行为1的列代表着相应位置上的中间节点参与了生成第i个修复节点的异或操作。G2_N×L的组成结构如图4所示。

至此，矩阵G1_L×L和G2_N×L全部生成，本发明不再采用传统Raptor Codes方法中采用中间节点得到修复节点的方法，按照下式直接生成修复节点向量R<R₁，R₂，...，R_N>，

R＝G2_N×L×G1_L×L×C，在上式中，G2_N×L×G1_L×L表现了源节点与修复节点应满足的关系。在此记A_N×L＝G2_N×L×G1_L×L，矩阵A_N×L中同源结点向量C进行异或的列为后K列，因此取A_N×L的后K列构成矩阵Z_N×K，可得R＝Z_N×K×C，其中向量C<C₁，C₂，...，C_K>代表K个输入节点的集合。Z_N×K和A_N×L的矩阵关系如图5所示，Z_N×K即为A_N×L的后K列。

由上述过程可以看出，相对于传统的Raptor Codes编码方法，本发明的编码方法中省去了中间节点的复杂计算，直接计算修复节点与源节点满足的依赖关系，可以迅速的由源节点计算出修复节点，从而大幅度减小编码时间消耗，降低编码器对硬件的要求，提高数据发送速度。

Rapid Raptor Codes解码方案

由于在编码方案中省去了中间节点的计算环节，本发明在解码阶段中同样除去了中间节点的概念。

假设接收端收到K’个源节点和N’个修复节点，这里K’＜＝K，N’＜＝N。显然在二元擦除信道上丢失了k＝K-K’个源节点，丢失了n＝N-N’个修复节点。在解码过程中，将修复节点看作是同源节点相关，即在修复节点中需要记录下该修复节点是由哪些源节点异或而成的。其中第i个修复节中含有的源节点的个数记为d_i，称该修复节点的度为d_i(源自LT Codes的发明人Luby等人对修复节点的一种定义，如修复节点A由三个不同的源结点异或而成，则A的度为3)。所有修复节点的度向量集合为d＝(d₁，d₂，...d_N′)，而源节点的度认为是1。在这里，本发明引入BP(Back Propagation，神经网络的一种二元结构)算法中度的概念(源自LT Codes的发明人Luby等人对修复节点的一种逆编码操作，在本文中表示将修复节点同组成它本身的源结点进行异或运算)，若d中第i个元素d_i中包含有已接收到K’个源节点中的元素j，即修复节点d_i由第j个源结点异或而成，则将d_i对应的修复节点与第j号源节点进行异或，直到d中不含有K’个源节点中的元素。在本发明解码方法中，该部分算法称为降度算法，其相应的算法描述为：

1：repeat

2：接收到新节点s

3：     if s是修复节点then

4：     if isUseful(s)then

5：         put S into result-list R

6：     else

7：         丢弃s

8：else

9：     put S into check-list C

10：until没有新节点

11：for all r in R do

12：    for all c in C do

13：        if r包含c then

14：            remove c from r

15：        end if

16：    end for

17：end for

上面算法描述中，isuseful表示通过查询Z矩阵判断接收到的修复节点是否相关，如果相关，则对该修复节点组成的节点进行异或操作，以达到降度的效果。判断修复节点同源节点是否相关需要查询矩阵Z_N×K，若Z_N×K中，第i行，第j列为1，则说明第i个修复节点同第j个源节点相关。

通过上述计算，降度之后的修复节点向量R’<R’₁，R’₂，...，R’_N’>就是经过“降度”之后的修复节点的集合。由于降度之后的修复节点只同丢失的源结点相关，因此其中所有降度后修复节点的度集合d’可以看作是由丢失节点序号构成，对应的数据可以看作是丢失节点数据异或的结果。

取d’中所有度向量(所述度向量为行向量，若修复节点包含第m个丢失源节点则该行向量的第m个元素为1，其余元素为0，0＜m＜k)构成一个N’×k的小矩阵Z’，矩阵Z’的形式如图6所示。其中Z’的第i行为1的列代表着相应位置上丢失的源节点参与了生成修复节点的异或操作。记所有丢失的源节点集合为向量C’<C’₁，C’₂，...，C’_k>，显然，Z’矩阵满足等式R′＝Z′_N′×k×C′。

通过Maximum-Likelihood解码算法(最大似然解码算法)，根据上式，通过对Z’矩阵进行上三角化和单位化，可以解出丢失的源节点向量C’<C’₁，C’₂，...，C’_k>。即在解码时对Z’使用高斯消去法进行求解，从而计算出丢失的k＝(K-K’)个源节点，将计算出来的丢失源结点补充道源数据中，完成数据的修复工作，从而完成整个解码过程。在计算过程中所使用的高斯消元法的算法如下所示：

1：i＝1  //i为行坐标

2：j＝1   //j为列坐标

3：for i≤m do

4：     if A[i，i]！＝0 then

5：         for k＝i+1 to m do

6：             if A[k，i]＝＝1 then

7：                 swap row k and row i  //将第k行和第i行互换

8：                 swap m(k) and m(i) in B  //将m(k)和m(i)节点互换

9：                 break

10：        end if

11：        end for

12：    end if

13：    if k＝m then

14：        for k＝i+1 to n do

15：            if A[i，k]＝＝1 then

16：                swap column k and column i

17：                swap m’(k) and m’(i) in L

18：                break

19：            end if

20：        end for

21：    end if

22：    for k＝i+1 to m do

23：        if A[k，i]＝＝1 then

24：        row i exclusive-or row k

25：            m(k) exclusive-or m(i) in B//m(k)同m(i)异或

26：        end if

27：    end for

28：end for

29：for i＝m to 0 do

30：    for j＝i-1 to 0 do

31：        if A[j，i]＝＝1then

32：            row i exclusive-or row j

33：            m(i)exclusive-or m(j) in B

34：        end if

35：    end for

36：end for

37：copy the data from B to L

以上算法描述表示在对Z’小矩阵进行高斯消元的过程，对矩阵以及对节点的操作，实际上就是ML解码算法。

实施例

本实施例基于DVB-S2(一种卫星传输协议)单向链路的大文件分发系统对本发明方法进行了实现，该系统包括软件层和硬件层，主要分为发送服务器和接收服务器两个部分。其中发送服务器包括CRC校验、文件分块、RapidRaptor Codes编码器和组播UDP；接收服务器包括CRC校验、文件恢复、数据块组装、Rapid Raptor Codes解码器和UDP接收。系统结构如图7所示，在发送端，上层软件接收到输入内存的数据，通过文件分割和数据块初始化等操作完成对数据的录入。之后通过Rapid Raptor Codes编码器编码，将编码后的源数据和修复节点通过DVB-S2链路发送出去；在接收端，底层网卡设备在DVB-S2链路接收到源数据和修复节点，然后通过Rapid Raptor Codes解码器解码恢复出完整的源数据。

本发明的方法主要应用于软件层，在发送端先进行软件的数据读入和切割等初始化工作，在切割成编码数据块之后，通过Rapid Raptor Codes编码器进行编码，其中Rapid Raptor Codes软件实现基于X86体系结构计算机平台，在实际测试环境中，软件实现使用C语言实现，运行在Linux 2.6操作系统内核，计算机中央处理器为Intel(R)Pentium(R)CPU@2.33GHz。在实际测试中，本实施例选择了节点大小为16k，节点个数K＝1031的数据块。

在编码过程中，分别选择了冗余为1％，2％，5％，10％的情况，其同传统Raptor Codes编码时间消耗的测试数据对比结果如图8所示。图中，三角形节点曲线代表传统Raptor Codes编码时间消耗；圆点节点曲线代表Rapid Codes编码时间消耗。可以看到，对于传统Raptor Codes编码时间受冗余度影响较小，而对于Rapid Raptor Codes编码时间几乎同冗余度呈正比；且RapidRaptor Codes在编码时间上较Raptor codes少很多，几乎缩小了10～100倍，尤其是当冗余越小，差距越明显。

在解码过程，设置数据冗余率为20％，丢包率分别选取了1％，2％，5％，10％的情况。其同传统Raptor Codes解码处理矩阵的时间消耗的测试数据对比如图9所示，图中，三角形节点曲线代表传统Raptor Codes解码处理矩阵时间消耗；圆点节点曲线代表Rapid Codes解码处理矩阵时间消耗。由于矩阵本身的缩小，Rapid Raptor Codes的矩阵处理速度比传统Rapor Codes提高了40～1000倍，且速度的提高随着链路丢包率的降低而越显明显；两者最终的解码时间对比结果如图10所示，图中，三角形节点曲线代表传统RaptorCodes解码时间消耗；圆点节点曲线代表Rapid Codes解码时间消耗。RapidRaptor Codes的解码速度比传统Rapor Codes提高了7～150倍，且速度的提高随着链路丢包率的降低而越显明显。

从上述结果可以看出，本发明方法的解码速度和编码速度较传统RaptorCodes都有了极大的提高。因此本发明对无线通信编解码资源占用小，速度提高极大，减小了对硬件的要求，极大的降低了时间成本和硬件成本，可以采用比丢包率略大的冗余度快速完成二元擦除信道数据通信过程中的数据纠错。

本发明说明书中未作详细描述的内容属本领域技术人员的公知技术。