一种基于联合矩阵短环消除的Raptor码编码方法

摘要

本发明公开了一种基于联合矩阵短环清除的Raptor码编码方法，主要针对联合矩阵中“1”的分布情况，进行Raptor码中的LT编码时只对联合矩阵中的短环进行消除，具体是进行Raptor码中的LT编码时每一列的“1”的位置生成都要提取相关列并对其进行检测，若随机选择的“1”的位置使得联合矩阵中产生了短环，则重新随机选择“1”的位置并继续检测，直到完成所有LT编码。本编码方法相比于现有方法提高了编码增益。

说明书

技术领域

本发明涉及数字信息传输技术领域，具体涉及一种基于联合矩阵短环消除的Raptor码编码方法。

背景技术

随着社会经济的快速发展，人类进入移动通信和互联网时代，个人通信的需求越来越高，不仅要求在“任何时间、任何地点与任何人”进行通话，而且要求通信技术“宽带化、实时化及多媒体化”；“编解码”技术作为通信技术中的重要组成部分，同样面临着更高的要求；为了能够在广播和多播中保证大量数据传输的可靠性，Luby等人于1998年提出了数字喷泉码的概念，这是一种基于删除信道的无码率的纠错码。其主要思想为：在发送端将原始数据分为任意数量K的编码分组，而接收方只要收到其中任意N个编码分组就可以高概率恢复原始数据，而无需知道所接收到的分组具体是哪些。一般情况下，N略大于K，同时我们定义译码开销ε＝Ν/K-1。

Luby在2002年首次提出了实用的可变码率数字喷泉码——LT(Luby Transform)码。LT码编译码复杂度不高且编码采用随机编码方式，从而能够满足不同用户的需求和变化的信道条件。但LT码存在译码成功恢复原始数据所需的运算量与原始数据长度k无法满足线性关系等局限性。为了改善LT码的局限性，Shakrollahi提出了一种性能更佳的数字喷泉码——Raptor码。Raptor码将一种性能良好的传统信道编码如LDPC码与LT码级联，从而提高了其译码效率。Raptor码编码时首先进行预编码，再对于预编码生成的中间码进行LT编码，如图2所示。而Raptor码译码时预编码的纠错能力可以辅助LT码译码，从而提高了译码性能，同时，引入预编码也使得Raptor码的编译码运算量与原始编码长度保持线性关系。

Raptor码中LT编码生成矩阵的短环消除一直是研究者们重点关注的问题，现有的有关Raptor码编码的短环消除算法都是针对LT编码生成矩阵中的短环而提出，或者是针对预编码矩阵中的短环。而Raptor码作为一种预编码与LT码结合的级联码，短环存在的矩阵不止于预编码或者LT码独立的矩阵，而可能同时会存在于其他矩阵中。因此，我们需要继续挖掘Raptor码的性能空间，提出一种性能更佳的Raptor码短环消除的编码方法。

发明内容

为了克服现有技术存在的缺点与不足，本发明提供一种基于联合矩阵短环消除的Raptor码编码方法。

本发明针对Raptor码编码中预编码的校验矩阵和LT码的生成矩阵结合而成的联合矩阵如图3所示，对联合矩阵中的短环进行消除。

如图3所示，本发明的关注点为联合矩阵中“1”的分布情况，进行Raptor码中的LT编码联合矩阵中的短环c进行消除，而不考虑预编码校验矩阵中的短环a和LE码生成矩阵G中的短环b,进行Raptor码中的LT编码时每一列的“1”的位置生成都要提取相关列并对其进行检测，若随机选择的“1”的位置使得联合矩阵中产生了短环，则重新随机选择“1”的位置并继续检测，直到完成所有LT编码。

本发明采用如下技术方案：

一种基于联合矩阵短环消除的Raptor码编码方法，包括如下步骤：

S1Raptor预编码，具体为对k个输入符号进行预编码，生成K个中间符号；

S2构建K行N列的全0矩阵G，根据度分布函数随机生成一个度d，d≥1，如果d＝1，则在矩阵G中的相应列随机选取一个位置写入“1”，重复S2，否则进入S3；

S3在矩阵G的第一列中随机选取一个位置写入“1”，并记录“1”的行位置为s₁；

S4构建预编码的校验矩阵H，并查找第s₁行中元素为“1”的所在列b₁，b₂，b_3…并存进数组R₁中；

S5在预编码的校验矩阵H查找第b₁，b₂，b_3…列中元素为“1”的所在行a₁，a₂，a_3…并存进数组R₂中；

S6在矩阵G的第一列中随机选取第二个行位置s₂，并将s₂与R₂中a₁，a₂，a_3…进行比较，如果s₂与a₁，a₂，a_3…其中一个相等，则重复S6；

如果s₂与a₁，a₂，a_3…任何一个都不相等，则在矩阵G的第一列中第s₂行写入“1”，进入S7；

S7重复S4-S6，将剩下的d-2个“1”都写入矩阵G的第一列上；

S8重复步骤S2-S6，将剩下的N-1列对应的位置上写入“1”。

所述校验矩阵H具有M行K列，其中M＝K-k，k表示信息比特的长度，K表示码字长度即中间符号的个数。

所述数组R₁为连续存储数组，每次执行S4则R₁刷新一次；所述的数组R₂为连续存储数组，每完成一列的“1”写入R₂刷新一次。

Raptor编码方法首先对k个输入符号进行预编码，生成K个中间符号，再将生成的中间符号经过LT编码后生成长度为N的Raptor；

联合矩阵具体为Raptor码编码中预编码的校验矩阵H和LT码生成的矩阵G结合而成的联合矩阵。

所述度分布函数为泊松度分布函数。

短环为长度是4的短环。

本发明的工作原理：

Raptor码编码矩阵中类似于4环等短环的存在导致译码时从一个节点传出的信息经过短环后又回到原节点，破坏了节点之间信息传递的独立性，最终导致编译码性能的下降。通过Raptor码编码过程中对短环的消除可以大大提升编译码性能。现有的有关Raptor码编码的短环消除算法都是针对LT编码生成矩阵G中的短环如图3中的短环b而提出，或者是针对预编码矩阵H中的短环(如图3中的短环a。而Raptor码作为一种预编码与LT码结合的级联码，短环存在的矩阵不止于预编码或者LT码独立的矩阵，同时存在于Raptor码编码中预编码的校验矩阵和LT码的生成矩阵结合而成的联合矩阵中如图3中的短环c。本发明针对Raptor码编码中联合矩阵中的短环，对联合矩阵中的短环进行消除，进行Raptor码中的LT编码，从而进一步提高了Raptor码的性能。

本发明的有益效果：

(1)该编码算法相比于原算法(无短环消除)提升了0.5～1.5dB的编码增益，对规则码、非规则码，长码、短码均有效果。

(2)该发明的核心是针对联合矩阵的短环检测方法，计算复杂度不高，硬件实现方便。

附图说明

图1为本发明的工作流程图；

图2为本发明中Raptor码编码过程示意图；

图3为本发明中Raptor码的联合矩阵中短环分布示意图；

图4为本发明的仿真验证图：以码率50％的(1008,504)非规则LDPC码作为Raptor码预编码时误块率对比示意图；

图5为本发明的仿真验证图：以码率为90％的(1000,900)规则LDPC码作为Raptor码预编码时误块率对比示意图；

图6为本发明的仿真验证图：以码率为95％的(5000,4750)规则LDPC码作为Raptor码预编码时误块率对比示意图；

图7为本发明的仿真验证图：以码率为90％的(5000,4500)非规则LDPC码作为Raptor码预编码时误块率对比示意图。

具体实施方式

下面结合实施例及附图，对本发明作进一步地详细说明，但本发明的实施方式不限于此。

实施例

如图1-图3所示，一种基于联合矩阵短环消除的Raptor码编码方法，所述Raptor码编码方法过程中预编码选用(K，k)LDPC码，其中K表示码字长度，k表示信息比特长度，码率R＝k/K。设定H是LDPC码的校验矩阵，即由0和1构成的M行N列的矩阵，其中M＝K-k，同时设定LT编码后生成长度为N的Raptor码编码输出符号。

本发明中的联合矩阵是指Raptor码编码中预编码的校验矩阵H和LT码生成的矩阵G结合而成的联合矩阵。

LT码的生成矩阵是一个稀疏矩阵，即矩阵中的“1”的数量远小于“0”的数目，矩阵中的每一列的“1”的数量表示生成一个码字所需要的原始数据包的数目，其数目称为度(Degree)，度所服从的概率函数称为度分布函数，常用的有理想孤波分布、鲁棒孤波分布和泊松度分布等等，生成矩阵中“1”的位置表示选取哪些原始数据包进行异或操作。LT码编码过程就是根据度分布函数产生一个度数d，然后完全随机地从长度为k的原始数据包中选出其中d个进行异或运算产生一个生成码字，如此循环。故LT码的生成矩阵的结构直接影响LT码的性能。若生成矩阵中有四个位置的“1”两两位于相同行不同列或相同列不同行，则这四个“1”构成了一个长度为4的短环如图3中的短环b。类似于4环等短环的存在导致译码时从一个节点传出的信息经过短环后又回到原节点，破坏了节点之间信息传递的独立性，最终导致编译码性能的下降。

根据现有的Raptor码编码方法，本实施例中我们选用泊松度分布函数，具体的短环消除方法，包括如下步骤：

S1Raptor预编码，具体为对k个输入符号进行预编码，生成K个中间符号；

S2构建K行N列的全0矩阵G，根据度分布函数随机生成一个度d，d≥1，如果d＝1，则在矩阵G中的相应列随机选取一个位置写入“1”，重复S2，否则进入S3；

S3在矩阵G的第一列中随机选取一个位置写入“1”，并记录“1”的行位置为s₁；

S4构建预编码的校验矩阵H，并查找第s₁行中元素为“1”的所在列b₁，b₂，b_3…并存进数组R₁中；

S5在预编码的校验矩阵H查找第b₁，b₂，b_3…列中元素为“1”的所在行a₁，a₂，a_3…并存进数组R₂中；

S6在矩阵G的第一列中随机选取第二个行位置s₂，并将s₂与R₂中a₁，a₂，a_3…进行比较，如果s₂与a₁，a₂，a_3…其中一个存储的行位置相等，则重复S6；

如果s₂与a₁，a₂，a_3…任何一个都不相等，则在矩阵G的第一列中第s₂行写入“1”，进入S7；

S7重复S4-S6，将剩下的d-2个“1”都写入矩阵G的第一列上；

S8重复步骤S2-S6，将剩下的N-1列对应的位置上写入“1”。

所述数组R₁为连续存储数组，每次执行S4则R₁刷新一次；所述的数组R₂为连续存储数组，每完成一列的“1”写入R₂刷新一次。

由于环存在的矩阵不止于预编码或者LT码独立的矩阵，同时存在于Raptor码编码中预编码的校验矩阵H和LT码的生成矩阵G结合而成的联合矩阵中(如图3)，所以我们可以通过对Raptor码编码中联合矩阵中的短环进行消除，进行Raptor码中的LT编码，提高Raptor码的性能。

在高斯白噪声(AWGN)信道及BPSK调制的情况下，采用Raptor码的BP全局迭代译码算法。以码率50％的(1008,504)非规则LDPC码、码率为90％的(1000,900)规则LDPC码、码率为95％的(5000,4750)规则LDPC码、码率为90％的(5000,4500)非规则LDPC码作为Raptor码预编码为例，对比原算法与本发明提出的新算法——基于联合矩阵短环消除的Raptor码编码算法的性能。

在本发明的仿真实验中，经过短环消除的输出符号所对应的度已经经过一定选择和优化，这使得Raptor码的最终性能达到更佳。

(1)如图4所示：对于以码率50％的(1008,504)非规则LDPC码作为Raptor码预编码，编码后Raptor码的码率设置为1/3，在误块率为10^-1附近，虽然采用码率较低的预编码存在错误平台，但加入联合矩阵短环消除算法相比原算法仍有0.5dB增益，性能提升比较明显。

(2)如图5所示：对于以码率为90％的(1000,900)规则LDPC码作为Raptor码预编码，编码后Raptor码的码率设置为2/3，采用码率高的预编码，随着信噪比的增加，误块率迅速下降。在误块率为10^-3附近，加入联合矩阵短环消除算法相比原算法有1.5dB增益，性能得到大幅度提升。

(3)如图6所示：对于以码率为95％的(5000,4750)规则LDPC码作为Raptor码预编码，编码后Raptor码的码率设置为2/3，对于长码来说，Raptor码的性能比较良好。在误块率为10^-3附近，加入联合矩阵短环消除算法相比原算法有0.3dB增益，性能一定程度的提升。

(4)如图7所示：对于以码率为90％的(5000,4500)非规则LDPC码作为Raptor码预编码，编码后Raptor码的码率设置为2/3，对于预编码采用非规则的长码来说，Raptor码的性能良好。在误块率为10^-3附近，加入联合矩阵短环消除算法相比原算法有0.5dB增益，性能提升比较明显。

从仿真结果可以看出，当采用不同码率的，规则或非规则的长、短预编码时，该编码算法相比于原算法(无短环消除)提升了0.5～1.5dB的编码增益，当采用高码率码作为预编码时性能提升比较明显。该发明的核心是针对联合矩阵的短环检测方法，计算复杂度不高，硬件实现方便。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受所述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。