基于网格复杂度的LDPC码两阶段译码方法

摘要

本发明提供了一种基于网格复杂度的LDPC码两阶段译码方法，包括如下步骤：第一阶段译码，所述第一阶段译码在超LDPC码中采用第一阶段译码算法，得到超码码字，当超码码字满足校验结果时，则作为最终的译码输出码字；当超码码字不满足校验结果时，进行第二阶段译码；第二阶段译码，在原LDPC码中采用第二阶段译码算法，得到最终的译码输出码字。本发明有效的降低了在LDPC码存在短环情况下的译码错误概率，由于对于两阶段中各自使用的译码算法进行更改可以使用到其他线性码的译码中，所以本发明对线性码具有普适性。

说明书

技术领域

本发明属于通信技术领域，涉及通信数据传输中所用的LDPC码信道编码方案的一种新的高效译码算法，具体是一种基于网格复杂度的LDPC码两阶段译码方法。

技术背景

近年来，对高效可靠的数字传输和存储系统的需求日益增长。这种需求随着在商业、政府和军事领域面向数字信息的交换、处理和存储的大规模高速数据网的出现而变得更加迫切。如何保证这些数据准确快速的交换、处理是我们需要解决的问题。这其中的一种重要的方法就是在数据进入新到传输时先对所要传输的数据进行适当的编码，通过对索要传输的增加数据增加冗余信息，使得我们可以对数据传输中所产生的错误进行检测和纠正，这种技术被称为信道编码技术，随着越来越多的人研究信道编码技术，现在已经出现了许多高效的信道编码方案。

LDPC码就是众多性能优异的信道编码方案中的一种。随着3GPP最终选定LDPC码为5G中长码编码方案，LDPC码的高效性越来越受到研究者的重视，对于一套信道编码方案而言，能否找到一种有效的译码算法，即低时间复杂度和低译码错误概率，是该信道编码最终应用于实际的重要因素。

对于LDPC码而言，目前主流的译码算法有比特翻转译码算法、和积译码算法、最小和译码算法，其中和积译码算法是一类在码因子图上的译码算法，当因子图中不存在环的时候，它的译码错误概率是所有已知译码算法中最小的，但是当因子图中存在4元或者6元环时，会严重影响和积译码算法的译码错误概率，而到目前为止，还没有找到一种行之有效的方法来解决这个问题。

因此当LDPC码的因子图中存在4元或6元短环时，设计一种不受短环影响的高效译码算法具有极其重要的实际意义。

目前没有发现同本发明类似技术的说明或报道，也尚未收集到国内外类似的资料。

发明内容

为了降低在4元环和6元环存在时，LDPC码的译码错误概率，本发明提出了一种基于网格复杂度的LDPC码两阶段译码方法，该译码方法，适用于LDPC码的可靠高效的译码体系。该译码方法解决了传统和积译码算法的LDPC码因子图存在4元6元短环时，译码性能变坏的问题。同时针对不同的线性码，对该译码方法两阶段各自使用的译码算法进行针对性的变换后可以被应到相应线性码的译码中，即该译码方法具有极强的普遍适用性。

本发明是通过以下技术方案实现的。

本发明所提出的基于网格复杂度的LDPC码两阶段译码方法，包括如下步骤：

-第一阶段译码，所述第一阶段译码在超LDPC码中采用第一阶段译码算法，得到超码码字，当超码码字满足校验结果时，则作为最终的译码输出码字；当超码码字不满足校验结果时，进行第二阶段译码；

-第二阶段译码，在原LDPC码中采用第二阶段译码算法，得到最终的译码输出码字。

优选地，所述第一阶段译码算法采用和积译码算法，包括如下步骤：

将编码完成后的原LDPC码的校验矩阵中出现4元和6元短环的行全部删除，利用删除后的校验矩阵构造得到原LDPC码的超LDPC码，并用该超LDPC码的校验矩阵构造超因子图，对接收到的数据向量在超因子图上运用和积译码算法，在和积译码算法结束时，得到超码码字。

优选地，在进行和积译码算法时，每次迭代过程更新校验节点的状态信息和变量节点的状态信息，直到得到正确的超码码字或达到最大迭代次数时停止和积译码算法。

优选地，校验结果为：

设校验式s＝c′H^T，其中，c′为超码码字，H为原LDPC码的校验矩阵，T为矩阵转置；当s＝0，则超码码字为最终的译码输出码字；当s≠0时，则执行第二阶段译码。

优选地，所述第二阶段译码算法采用优先级算法，，包括如下步骤：

利用原LDPC码的校验矩阵构造一个码网格，并利用第一阶段译码中得到的超码码字，对接收到的数据向量在码网格上使用优先级算法。

优选地，运用优先级算法时，先构造一个代价函数，该代价函数包括两部分，一部分为优先级算法找到的从初始结点到当前节点最小路径，另一部分为从当前节点到目标节点最小路径的预测；对于每一个访问节点，计算该访问节点的代价函数，并从该访问节点的代价函数中选择具有最小代价函数值的节点，直到搜寻到目标节点时结束优先级算法；在完成第二阶段译码算法之后，将得到最终的译码输出码字。

优选地，第二阶段译码中得到的最终的译码输出码字为最大似然码字。

与现有技术相比，本发明具有如下有益效果：

1、本发明提供的基于网格复杂度的LDPC码两阶段译码方法，是一种适用于LDPC码的可靠高效的译码体系，采用两阶段混合设计，以此保证译码算法的最优性；

2、本发明可以灵活的变换两个阶段中各自使用的译码算法，并将两阶段译码算法运用于其他线性码的译码中；

3、本发明降低了在4元环和6元环存在时，LDPC码的译码错误概率；

4、本发明具有极强的普遍适用性。

附图说明

图1为原LDPC码校验矩阵与超LDPC码校验矩阵，其中，(a)为原LDPC码，该原LDPC码为(3，3)规则LDPC码，(b)为超LDPC码，该超LDPC码为非规则LDPC码；

图2为超LDPC码的超因子图；

图3为第一阶段和积译码算法校验节点与变量节点消息更新(传递)说明图；

图4为第二阶段优先级译码算法流程图。

具体实施方式

下面对本发明的实施例作详细说明：本实施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程。应当指出的是，对本领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进，这些都属于本发明的保护范围。

本实施例提供的基于网格复杂度的LDPC码两阶段译码方法，包括如下步骤：

-第一阶段译码，所述第一阶段译码在超LDPC码中采用第一阶段译码算法，得到超码码字，当超码码字满足校验结果时，则作为最终的译码输出码字；当超码码字不满足校验结果时，进行第二阶段译码；

-第二阶段译码，在原LDPC码中采用第二阶段译码算法，得到最终的译码输出码字。

进一步地，第一阶段译码，采用和积译码算法。对于编码完成后的原LDPC码C和接收到的数据向量r，首先将原LDPC码C的校验矩阵中出现4元和6元短环的行全部删除，利用删除后的校验矩阵构造可以得到原LDPC码的一个超LDPC码，并用该超LDPC码的校验矩阵构造超因子图，对接收到的数据向量r在超因子图上运用和积译码算法；在进行和积译码算法时，每次迭代过程更新校验节点的状态信息和变量节点的状态信息，直到得到正确的超码字或达到最大迭代次数时停止和积译码算法，在该阶段结束时，可以得到一个超码字c′属于超码，判断这个超码码字是否满足校验结果；当不满足校验结果时，利用这个超码码字进行第二阶段译码。

进一步地，第二阶段译码，采用优先级算法。将原LDPC译码看成图上最短路径搜寻问题，用原LDPC码的校验矩阵构造一个码网格，在码网格上使用优先级算法，运用优先级算法时先构造一个代价函数，该代价函数包括两部分，一部分为优先级算法找到的从初始结点到当前节点最小路径，另一部分为从当前节点到目标节点最小路径的预测；对于每一个访问节点，计算它们的代价函数，并从中选择具有最小代价函数值的节点，直到算法搜寻到目标节点时结束译码算法；在完成第二阶段译码算法之后，得到一个最终的译码输出码字c。

由于本实施例提供的基于网格复杂度的LDPC码两阶段译码方法分为两个阶段译码，第一阶段在超LDPC码的因子图上优选使用和积译码算法，第二阶段是在原LDPC码的码网格图上优选使用优先级译码算法，对于第一阶段译码算法复杂度，可以利用已知的结论得到，对于第二阶段译码算法的时间复杂度，因为对于网格图上的译码算法，其译码算法的时间复杂度与网格的结构复杂度有直接的关系，而对于同一个LDPC码而言，经过不同的列置换所得到的码网格图的结构有很大的差异，此处利用子码与超码网格复杂度之间的关系来得到第二阶段译码算法的时间复杂度。

下面结合流程图对本发明的实施步骤做简要说明：

如图1所示：

第一阶段译码：

步骤S1：删除原LDPC码因子图中出现4元环(或6元环)的相应校验矩阵H的行，用剩余的校验矩阵H′构造超因子图T。

步骤S2：在超因子图T上使用和积译码算法：

用N(j)表示与校验式c_j相连的所有比特分量集合，M(i)表示所有与变量比特v_i相连的校验方程集合。M(i)/j表示集合M(i)中除去校验方程j后，剩余校验方程组成的集合，N(i)/j表示集合N(i)中除去变量比特vi后，剩余变量比特组成的集合。令表示在集合M(i)/j中所有校验节点状态已知的情况下，变量比特v_i＝a成立的概率，表示在集合N(i)/j中所有变量节点状态已知，且v_i＝a的情况下，校验和式c_j成立的概率。接下来引入对数度量：

同时定义对数域中的消息更新方程为：

S2.1.对校验节点计算更新方程：

对于每一个校验节点j以及与它相连的变量节点i∈N(j)，

S2.2.对变量节点计算更新方程：

对于每一个变量节点i以及与它相连的校验节点j∈M(i)，

λ_i→j(q_ij)＝Λ(x_i)+{∑_j′∈M(i)jΛ_j′→i(r_ji)}

S2.3.尝试译码，

计算变量节点判别式

λ(x_i)＝L(x_i)+{∑_j′∈M(i)Λ_j→i(r_ji)}

将对应的数据比特x_i进行译码，

步骤S3：译码输出第一阶段码字c′。

步骤S4：计算校验式s＝c′H^T，若s＝0则输出码字c′为最终译码结果。若s≠0则执行步骤s1。

第二阶段译码：

如图2所示：

步骤s1：利用原LDPC码的校验矩阵构造码字网格图G。

步骤s2：在原LDPC码网格G上使用优先级算法：

将接收到的向量r＝(r₁，r₂，...，r_n)，将其变为φ＝(φ₁，φ₂，...，φ_n)，其中，

同时将φ＝(φ₁，φ₂，...，φ_n)中各个元素按照绝对值从大到小排列得到置换后的向量为φ′＝(φ₁′，φ₂′，...，φ_n′)。为了使用优先级算法，需要建立代价函数f，对于算法进行中的任意一个访问节点m，其代价函数有两部分组成，即f(m)＝g(m)+h(m)，其中g(m)表示从初始节点到节点m的最小代价，h(m)从节点m到目标节点的最小代价。

对于在网格图第1层的任意访问节点m，定义g(m)为：

其中表示算法所找到的到节点m的最短路径P_m′的标签。

对于h(m)利用LDPC码的性质来构造：

令m表示在第1层的节点，且表示由算法找到的从初始节点到m的最短路径P_m′的标签，建立一个集合，

其中，d_H(v，c′)表示向量v与第一阶段译码输出码字c′之间的汉明距离，集合表示码字集合中所有码字所具有的不同的汉明重量，表示所有属于超LDPC码而不属于原LDPC码C的码字集合，HW(v)表示向量v的汉明重量。

则构造h(m)为，

s2.1.建立一个OPEN表格，将网格G的起始节点s_-1加入到OPEN中。

s2.2.创建一个CLOSED表格，且初始化为空。

s2.3.将OPEN中具有最小代价函数值f，且没有在CLOSED中出现过的节点m加入到CLOSED中，并将该节点从OPEN中删除。

s2.4.将节点m的所有之前未出现在OPEN中的子节点加入到OPEN中，并计算这些子节点的代价函数f的值。

s2.5.如果节点m是目标节点，则译码成功。

步骤s3：输出第二阶段译码码字并将其作为译码算法的最终译码结果c。

在本实施例中，

第一阶段译码：在超LDPC码中优先使用和积译码算法。

第二阶段译码，在原LDPC码上优先使用优先级算法。

采用两阶段混合设计，以此保证译码算法的最优性。

可以灵活的变换两个阶段中各自使用的译码算法，并将该算法运用于其他线性码的译码中。

在第一阶段译码中，删除原LDPC码校验矩阵中使得因子图出现4元或6元短环的行，用删除后的校验矩阵构造超因子图，并在超因子图上使用和积译码算法。

在第二阶段译码中，对原LDPC码的网格图上使用优先级算法。

第二阶段译码中得到的最终的译码输出码字是最大似然码字。

对于LDPC码进行译码时，可以将第一阶段的和积译码算法变换为其他适合于LDPC码的高效译码算法，例如线性规划译码算法(Linear Programming decoding algorithm)、最小和译码算法(Min-sum algorithm)。同时可以将第二阶段的优先级译码算法变换为其他复杂度低易于实现的译码算法，例如列表译码算法(List decoding algorithm)。

可以利用变换前或变换后的两阶段译码算法对其他已有的线性信道编码方案进行译码。

本实施例提供的基于网格复杂度的LDPC码两阶段译码方法，是针对5G长码编码方案的LDPC码的一种高效的译码算法，有效的降低了LDPC码的译码错误概率。首先删除原LDPC码校验矩阵中产生4元和6元短环的行，得到一套超LDPC码，对接收到的信息比特在超LDPC码的因子图中使用和积译码算法进行译码。之后对于不满足校验方程的码字进行第二阶段译码，利用LDPC码的校验矩阵构造码网格图，并在该码网格图上使用优先级算法。本实施例有效的降低了在LDPC码存在短环情况下的译码错误概率，由于对于两阶段中各自使用的译码算法进行更改可以使用到其他线性码的译码中，所以本实施例对线性码具有普适性。

以上对本发明的具体实施例进行了描述。需要理解的是，本发明并不局限于上述特定实施方式，本领域技术人员可以在权利要求的范围内做出各种变形或修改，这并不影响本发明的实质内容。