文摘

通知动态调度(IDS)策略的低密度奇偶校验(LDPC)解码显示性能优越在纠错和收敛速度,特别是基于可靠性的措施和残余信念传播(RBP)。然而,寻找最不可靠的变量节点和残余预先计算每个迭代所需的IDS-LDPC增加解码过程的复杂性变得更加连续,因此很难利用多核平台中可用的信号处理算法的并行性。为了克服这个问题,一个新的、低调度系统,称为分层附近的变量节点调度(LWNS)提出了。LWNS,每个变量节点通过交换内在信息更新所有相关的控制变量节点在移动到下一个变量节点更新。该调度策略的一个预处理步骤是固定的奇偶校验控制矩阵,而不是计算的残差值和最具影响力的变量节点的计算而不是最不可靠的指标。它还允许独立的坦纳图的并行处理支行确认和分组层。我们的模拟结果表明,LWNS BP有一个有吸引力的收敛速度和更好的纠错性能较低的复杂性相比以前的IDS解码器在高斯白噪声信道(AWGN)。

1。介绍

介绍了LDPC码的Gallager [1]自1962年以来,重新被麦凯和尼尔[21996年)。LDPC码已经引起了相当大的关注,因为他们优越的纠错能力信念传播解码(BP) (2]。BP译码是传统的重复执行的洪水调度(3),先后variable-to-check (V2C)和所有check-to-variable(式C2V)并行更新消息。

然而,收敛过程减慢,因为最新的更新信息是不可用的,直到下一次迭代。加速收敛,提高纠错性能,提出了顺序调度方法,预先确定的和固定的顺序更新。这个顺序调度策略不同于洪灾的当前迭代中最新的信息是可用的。重组(4- - - - - -6和分层7,8)安排两种变体的这一战略,并允许加快收敛的解码洪水调度的两倍。为了实现更快的收敛性能动态调度通知(IDS)介绍了策略,其中残留的信念传播(RBP)解码9,10]。的RBP用于LDPC译码Casado et al。9)被Elidan介绍后et al。112006年)。它由一个动态调整的消息更新,基于剩余价值定义为当前和旧消息值之间的差异。

顺序和洪水算法相比,RBP算法的收敛速度更快,但据报道,第一次迭代后的纠错能力不满意(9];这是因为主要计算资源分配或专注于一些节点和边的最大式C2V残余;然后合格RBP作为一个贪婪算法(9]。为了减少这种贪吃效应的RBP,节点明智RBP (NW RBP)算法引入了(10),所有式C2V消息的式C2V边缘连接到所选控制节点的最大残式C2V同时传播。

根据不同的消息选择和更新策略,一些动态解码算法已报告。变量来检查(VC) RBP [12)的优先级消息更新给V2C消息最高的残留物;VC-RBP已经有较低的计算的优势但纠错性能不如RBP,因为有些沉默的变量节点和一个最小V2C残余从未在解码过程中作出贡献。然后,一个沉默的变量node-free (SVNF) RBP [13)提出了在每个变量节点有机会贡献其内在的消息在整个边缘的最大式C2V残留。SVNF的优点有更快的收敛速度比RBP但较高的计算复杂度。动态无声变量node-free调度(D-SVNFS)算法在同一篇论文中(13)是指SVNF调度,但允许动态序列变量节点的参与,这也进一步提高了收敛速度和需要更多的计算来确定下一个变量节点更新。禁忌搜索动态调度(tsd) [14算法记住一些变量节点暂时存储在一个禁忌列表根据剩余;存储的变量节点从而不能更新,直到他们移出列表后很少的迭代次数。这个过程更新订单导致明显减少贪吃的效果,但它仍然存在保持一个贫穷的纠错能力在第一次迭代。同时,为了解决这个贪吃的限制,剩余decaying-based残余信念传播(RD RBP) [15提出了。在该算法中,式C2V剩余工资的价值将逐渐衰变根据更新发生相应的式C2V消息。因此,每条边有机会被选中在解码过程中,从而减轻IDS贪吃。

2。相关工作

接近甚至超越RBP算法的性能,基于剩余信息的一些动态解码算法和其他的选择标准也被提出(16- - - - - -18]。RM (RBP) [16),可靠性指标是用来定义的优先级消息更新。首先,不满意的数量为每个变量节点计算奇偶校验方程;然后,所有变量节点分为两组根据是否满足奇偶校验方程的数量等于它的最大价值。设置包括变量节点的最大价值是最不可靠的一组变量节点;最可靠的变量节点参与在印度河流域文明RBP算法(第二集。17),消息的优先级更新是最不稳定的变量节点,给变量节点合格不稳定的迹象之前和之后一个更新是逆转,和稳定性指标计算提高计算。在OV RBP [18),稳定性指标基础上的数量不满足每个变量节点的奇偶校验方程用于选择调度秩序;最不稳定的变量节点的大量不满足奇偶校验方程更新。

这些新动态解码算法显示出显著的性能比之前RBP艺术当考虑BER收敛速度。然而两个主要缺点依然存在。首先,贪吃坚持即使它影响减少,因为变量节点选择根据他们的度量和剩余价值,因此,所有变量节点没有相同的被选择的机会。第二,动态搜索最不稳定或/和不可靠的变量节点,和剩余计算每个迭代所需的IDS LDPC译码增加解码的复杂性,然后使解码过程更加连续。

为了减少解码复杂度,提高收敛速度,并允许解码的并行处理,我们建议在这个工作分层节点调度算法(LWNS)附近的变量,每个变量节点是被迫做出贡献的内在信息每次更新后没有剩余价值计算,也最不可靠的变量节点搜索计算。

解码的时间表是固定的,由预处理的第一步,执行在解码过程中,奇偶校验控制矩阵。预处理阶段的目的是确定为每个变量节点的子图连接和有影响力的度量的连接的数量。这一步是紧随其后的是分类并行的子图根据影响力度量和最后分组并行子图在层允许解码过程的并行化。测试该算法在quasicyclic不规则LDPC码(576、288),(576144),(1152、576)和(2304、1152)构建基于IEEE 802.16 e标准,在高斯白噪声信道(AWGN)下,和我们的仿真结果表明,该LWNS达到更好的收敛速度的速度和纠错性能比印度河流域文明RBP和OV RBP。

剩下的纸是组织如下。部分2回顾了LLR BP, RBP,印度河流域文明RBP和OV RBP算法。部分3介绍了提出LWNS BP译码算法。部分4比较了纠错性能、收敛速度,提出的两个算法的复杂性与以前的作品。最后,部分5总结了纸。

3所示。基本的解码方法,算法

3.1。LLR BP对LDPC码解码

一个二进制LDPC码可以使用坦纳图进行描述变量和控制节点如图1,在那里表示th变量节点和表示控制节点。当英国石油公司LLR解码LDPC译码算法,式C2V消息传播的来在零初始化和V2C消息吗从v传播_jc_我初始化如下:

在哪里表示的频道信息th变量节点和表示th代码。

每次初始化后,更新式C2V消息根据生成

在哪里表示连接到相邻的变量节点检查节点 ,不含变量节点 。

V2C的更新消息计算为 在哪里表示连接到邻近的检查节点变量节点 ,除了检查节点 。

更新后的生成和传播V2C和式C2V消息,一个艰难的决定变量节点是基于新的LLR值计算的

在哪里表示所有的相邻节点检查变量节点相连 。

消息传播在解码过程中不会停止,直到所有检查是否满足方程或预定义的最大迭代次数。

3.2。调度策略LDPC译码

洪水调度LLR BP算法是最简单的,首先使用方程(式C2V消息更新2),然后更新所有V2C消息使用方程(3)。因此,新生成的信息在当前的迭代只能用于下一次迭代。这略有不同的顺序调度算法可以生成新的信息,并立即使用在相同的迭代。

在这两种情况下,消息更新按照预定义的顺序。

相反,IDS动态调整订单的消息更新。第一个RBP id算法确定消息的顺序更新基于式C2V残留。式C2V残余被定义为的大小区别式C2V之前和之后的一个更新的消息。式C2V剩余可以定义(8]

在哪里是下一个更新的预先计算式C2V消息。正如上面提到的,该算法仅更新式C2V边缘的最大残余式C2V消息。

因此,初的解码过程,计算式C2V所有消息以识别式C2V边缘候选人更新。

首先,最大的预算式C2V消息式C2V剩余变量节点传播;然后,V2C消息更新和传播到邻国检查节点。检查节点接收新的V2C消息价值实现预算式C2V消息和剩余价值。最后,剩余的式C2V消息目前更新设置为0,和式C2V消息最大残余被选中下一个更新。

在印度河流域文明RBP算法(17),变量节点分为两组形成的稳定或不稳定的节点。

后确定最不稳定的变量节点,选中的消息的更新是基于RBP执行的过程。

此外,这种不稳定性指标,OV RBP算法(18)调度策略看着不满意的数量奇偶校验方程,定义为每个变量节点

在哪里表示奇偶校验节点的结果 。越检查方程不验证给定的变量节点,它被认为是一个不可靠的变量节点越多。因此,每组不稳定或稳定的变量节点分为基于是否另外两集等于它的最大价值。

在选择最不稳定的变量节点的最大数量不满足奇偶校验方程,基于执行选中的消息的更新RBP。

主要的计算资源分配专门为节点和边的最大价值度量和残余;因此,贪吃影响仍然发生。

所有判断标准见上图和残余预先计算中执行每个解码迭代生成额外的计算,从而大大增加解码的复杂性。

4所示。提出LWNS算法

为了降低贪吃影响和降低译码复杂度,更好的误码率收敛性能,介绍了分层附近的变量节点调度(LWNS)适用于古典LLR BP算法。

不同的动态RBP调度算法相比,在LWNS,所有变量节点将更新相同的机会,但处理的顺序被定义为一个奇偶校验矩阵预处理之外执行解码序列来定义一个固定的顺序安排。

4.1。子图附近的变量节点

LWNS,每个变量节点更新的密切关注和所有变量节点交换内在信息吗连接到变量节点通过所有检查节点连接到 ,除了变量节点 。这组变量节点的本地的变量节点表示并指出 。

图2显示每个变量节点的子图更新操作。其目的是每个变量节点的过程 ,密切的子图;通过这种方式,最新更新的信息直接相关期间是可用的更新,从而使解码的快速收敛。

图3提出了奇偶校验矩阵的一个例子(a)及其相关检查方程(b);变量节点通过交换中密切内在信息检查更新方程 , ,和和附近的变量节点 。

4.2。最具影响力的变量节点指标

每个变量节点生成自己的子图;因此,子图的数量等于数量变量节点。

定义子图更新订单,我们使用最具影响力的变量节点度量概念而不是不稳定的变量节点指标。

考虑到邻居的一个变量节点越多,就变得越的影响。

为每个变量节点 ,我们计算的影响指标之间的边的数量及其附近的设置:

在哪里表示检查节点总数与变量节点和表示变量节点的总数与检查节点 。这个指标是计算在解码处理。

当一个变量节点连接到一个附近的节点通过两个独立的控制节点和 ,的价值增加,但变量节点不能有这么大的影响,因为消息在一个封闭的振荡周期。

通常是这样对应的周期长度为4的矩阵 ,如图4。周期的长度定义为数量的交叉边缘退出并返回一个节点没有经过相同的边缘。这种情况下移动通过消除边缘造成周期4 (19]。

解码过程中执行度量值的降序排列的影响。

图5显示了解码过程遵循LWNS算法采用每个变量节点 ,降序排列的分类指标的影响。在第一步中,使用方程(2),的消息从检查节点在哪里 附近的所有变量节点 通过考虑到变量生成节点和传播到所有附近的变量节点 。在第二步中,使用方程(4),的LLR值附近的变量节点计算,使用方程(3),所有V2C从附近的变量节点更新消息检查所有节点邻居的, 。在一分之二的步骤中,附近的变量节点考虑在更新的LLR值变量节点 。

然后,在步骤3中,使用方程(2),的消息从检查节点在哪里 变量节点通过考虑到所有附近的变量节点生成和传播到变量节点 。在最后,LLR值的变量节点计算使用方程(4)。这样,变量节点考虑在更新的LLR值附近的所有变量节点 。

详细的解码过程LWNS算法的伪代码描述算法1。

5。提出了分层并行体系结构

并行体系结构,以避免数据依赖关系在解码过程中并行内存访问。

变量节点的依赖来自的奇偶校验矩阵H和调度策略。

我们定义平行LWNS调度策略作为LWNS策略,而不是只更新变量节点影响最大的指标,k变量节点同时更新。

因此,并行处理是允许的变量节点如果他们本地的设置不分享任何变量节点;否则,

对于所有变量节点,我们定义两个变量:“平行”和“本地的。“变量节点满足方程(8)是平行的和有相同的“平行”价值。“本地的”值设置为一个标记,这个变量节点已经属于另一个变量节点的本地的。

图6显示了这些变量的值的变量节点是否通过附近的节点连接。在图6(一)变量节点和v_j是平行的,所以这两个变量的“平行”变量节点设置列的值 ,和他们的“本地的”变量设置为1,表示该变量节点已被覆盖。相反,在图6 (b)变量节点和有关他们本地的变量节点 ;在这种情况下,和是依赖的,所以“平行”和“本地的”变量将不会改变。

因此,所有变量节点分为平行子图;详细的平行变量节点矩阵预处理算法的伪代码描述2。

平行变量节点将同时更新。为了同步并行流程,避免等待时间,平行变量节点必须有相同的计算复杂度,以确保同时并行处理结束,继续下一个系列。的变量节点有相同的影响力指标同时更新。

6。绩效评估

为了评估该LWNS算法的译码性能,与其他顺序算法进行比较,包括洪水(3),水平调整(5],IDS IVC-RBP [17],VO-RBP [18)算法。

大量的模拟是用来获得的解码性能提出LWNS算法,数以百万计的活动框架在CNRST / HPC-MARWAN平台(20.]。这些算法的计算复杂性评估根据计算需要的数量每个解码步骤。AWGN信道上的所有模拟执行BPSK调制。 指定使用的代码模拟,是块长度表示数量的奇偶校验位。我们使用了代码(576、288),(576144),(1152、576),(2304,1152)quasicyclic不规则的LDPC码构造基于IEEE 802.16 e标准(21]。

高效的内存奇偶校验矩阵的优化提出了(22,23)是用来减少内存需求。

6.1。纠错性能

数据7(一)- - - - - -7 (d)显示了误比特率(BER)和误帧率(带)的LDPC码的译码算法编码率 ,分别为576和1152块的长度。

很明显,误差校正算法的性能比其他的要好。可以观察到,保留了性能优势随着信噪比的增加达到 当 dB 576块长度 当 dB 1152块长度。

数据7 (e)和7 (f)交易,分别与误码率和带表演不规则quasicyclic 576 LDPC码的编码速率 ;提出LWNS算法显示最好的误码率相比OVRBP算法。之间的 dB和3.5 dB,增益大于0.25 dB, dB非常低的误码率达到8.10⁷。

在表1,比较OVRBP [18)算法的误码率、带和解码迭代的平均数字提出了。可以看出,提出的数量和带表演LWNS算法改进解码迭代相同的号码。

评估拟议的LWNS算法性能与长度代码块,块长度的数量和带表演576年,1152年和2304年与相同的一系列信号的鼻子比( )模拟图和报告8,

它可以清楚地观察到LWNS解码算法性能越来越有吸引力随着分组码的长度增加,数量和带难以达到 和10^6,分别的时候 德国联邦铁路(dB);换句话说,138 mbit ( 位),只有一点是错误的。

为了证明该算法收敛更快,数据9和10显示了误码性能与迭代次数(576、288)LDPC码 dB, (576、144) LDPC码 dB。他们两人的模拟表明,拟议中的LWSN算法收敛速度比任何其他在大约15迭代算法。换句话说,LWSN不仅具有更好的纠错性能还具有更快的收敛速度。

贪吃影响OVRBP算法显示的数字9和10前五后和纠错性能迭代据报道很低。相比之下,拟议中的LWNS算法的误码与增加迭代的数量增长,15个迭代后达到一个稳定值,3.10⁶在 数据库,而不是3.10⁵OVRBP算法实例,使用最快速的算法进行比较。

6.2。复杂性分析

在本节中,我们评估了该算法的译码复杂度的式C2V和V2C更新所需的数量在每个解码迭代。

一些残余解码算法,计算是必要的更新。这部分添加到的precomputational复杂性式C2V计算。此外,如果一个算法需要找到最不稳定的变量节点在所有变量节点,一定数量的搜索计算是必需的。

这种复杂性是每次迭代的LDPC译码固有的,其中一个迭代的过程意味着选择和更新坦纳图中所有边。边的总数在整个坦纳图 ,在哪里和表示检查节点的平均度和变量节点,分别。

表2提出了更新该算法的计算复杂性,由V2C更新的数量,式C2V更新步骤如图5。

为每个变量节点 ,在步骤1中,有 计算式C2V消息来更新本地的变量节点,然后在步骤2中,这些本地的变量节点计算 V2C消息更新检查节点连接到它们。在步骤3中,更新检查节点生成和传播式C2V用于更新变量节点 ;最后,在步骤4中,变量的LLR值节点更新和V2C消息传播到检查节点连接 。

因此,对于每个LWSN迭代,所需数量的V2C式C2V更新 。

在表3更新的复杂性,不同的解码算法。LWSN算法取代计算的剩余价值,最不可靠的变量的计算更新一个预处理步骤不包括在解码处理。

因为所需的搜索计算确定最不稳定的变量节点在每个迭代中,IVRBP的复杂性和OVRBP算法可以表示为和 ,分别,而LWNS算法的复杂性 。

提出LWSN算法相比明显降低复杂性IDS IVRBP和OVRBP算法。

此外,提出LWNS算法可以并行的方式,通过更新变量节点层。每组变量节点相同的变量标签的“平行”所示更新算法1并行的方式。

因此,高度可以减少复杂性取决于多核平台,采用并行性的水平。

7所示。结论

在本文中,我们提出一个创新的分层算法,LWNS,为了降低译码复杂度相同的id算法获得的性能。LWNS算法,所有变量节点加入到更新处理同样的机会,克服贪婪的id。不可靠的信息的搜索和剩余计算矩阵所取代预处理。该算法实现了更好的误码率,带性能和收敛速度;数量和带难以到达 和10⁶分别的时候 dB和复杂性降低 。此外,可以大大降低LWSN算法的复杂性在并行化的平台是可能的。我们的仿真结果和分析表明,该算法的行为比其他算法在文献中报道时考虑到方方面面,收敛速度,和解码复杂度。

数据可用性

没有数据被用来支持本研究。

的利益冲突

作者宣称没有利益冲突。

确认

这项研究是通过计算资源支持HPC-MARWAN (http://www.marwan.ma/hpc)提供的国家科学和技术研究中心(CNRST),拉巴特摩洛哥。