SCMA 场景下的极化码编解码方案改进研究

朱 旋,王 钢

(哈尔滨工业大学 电子与信息工程学院,黑龙江 哈尔滨 150001)

0 引言

如今,高效的频谱利用、大规模的连接和超高速数据传输的应用场景越来越多,将来,万物互联的物联网、高速移动的增强移动通信以及超高密度的用户吞吐将会成为移动通信更加重要的应用场景。 多址接入技术能提高网络连接数量和频谱利用率,优越的编码技术能提升误码率性能和通信质量。 极化码具有较低的编译码复杂度,同时能达到较高的通信质量[1],稀疏码分多址接入(Sparse Code Division Multiple Access,SCMA)通过用户之间的非正交复用频域资源提高频谱利用率。 在先前的SCMA 场景下与极化码的联合系统中,极化码的译码方式有 SCL硬判决和置信传播软信息迭代2 种思路。 基于CRC-SCL 的硬判决方式,先译码得到码字信息再反馈到SCMA 的MPA 用户检测器,从MPA 的函数节点中依次删除已译出的码字;基于CA-SCL 硬判决反馈的联合接收机能获得很好的误码率性能,但是接收机延时非常大。 置信传播软信息迭代的系统将MPA 用户检测的因子图与极化码译码的因子图联合,在联合因子图中并行传递软信息,并行译码结构能有效降低接收时延,但是计算复杂度较大,同时性能不如CRC-SCL 的反馈硬判决联合接收机[2]。

在SCMA 场景下,极化码的几种译码方式各有利弊：SCL 译码具有良好的译码误码率性能,同时译码时延较大;BP 译码算法由于采用并行译码,因而大幅度降低了译码时延,但误码率性能较差;SCAN算法与BP 译码都是采用并行置信传播算法,但SCAN 算法收敛速度更快、误码率性能更好。 本文首先研究SCAN 译码算法的改进方式,通过改进信息更新的方式和剪枝译码树,在译码性能几乎不变的情况下,降低译码复杂度和译码时延,为联合检测译码算法提供良好的译码方式。 本文改进了联合检测译码算法(Joint Iterative Detection and decoding algorithm,JIDD),在接收机采用外循环迭代的结构,将用户检测的MPA 因子图和SCAN 因子图联合,参照其他联合系统引入了阻尼系数,仿真分析了不同阻尼方式以及阻尼系数设置不同数值时对于系统性能的影响,选取最优的阻尼方式和最优阻尼值。 仿真分析了本文提出的联合系统与原有联合系统的误码率性能和译码复杂度与时延方面的差异。

1 简化的左信息更新方法

1.1 软信息更新的原理

极化码的译码算法中,连续消除译码(SC)和连续消除列表译码(SCL)都是依次硬判决的串行译码方式,在SC 以及SCL 的硬判决译码时,计算各个节点的LLR 和硬比特信息利用了以下2 个假设[3]：

① 译u0时,译码器计算概率值W(| u0)时,假设u1～uN-1等概率为0 和1;

② 译ui时,计算概率值W(,ui-1| ui) 时,假设u0～ui-1是确定值。

假设①成立的条件是发送端发送信号为等概率发送,并且信道的信噪比很高,假设②成立的条件是此前的译码过程中没有错误译码,如果出现错误译码比特,那么很容易造成错误传播[4]。 基于以上2 个缺点,可以用软信息代替硬判决,依次来改善LLR 的估值。

如图1 所示,在接收端研究u0,u1时,假设可以从其他信道获得u0, u1的软信息z0, z1;假设zi：i ∈{0,1} 是B-DMC 信道Pi的软信息输出,信道Pi的转移概率Pi(zi,ui)：ui∈{0,1} 与yi相互独立,如果zi在接收端估计u0,u1之前可以得到,那么SCAN 译码器对于ui的对数似然比的计算可以表示为：

图1 软信息影响模型示意图Fig.1 Soft information impact model

1.2 简化左信息的更新算法

生成因子图的软信息B 的步骤如下。 首先,SCAN 译码器初始化第n 列所有节点的左信息L 为信道的对数似然值LLR,初始化第1 列中固定位所对应的节点软信息B 为∞,初始化第1 列中信息为所对应的节点软信息B 为0,在第1 次迭代时,由于没有关于源信息的信息,因此假设这些信息都是等概的,除了第1 列的节点外,矩阵B 中其他节点均初始化为0[5]。 图2 为软信息传递示意图,在因子图中传递的信息的计算,经理论推导,在单位因子图中概率值满足以下关系,其中函数f(a,b)= ab,即为[6]：

图2 SCAN 算法单位因子图概率传递示意图Fig.2 SCAN algorithm unit factor graph probability transfer diagram

在因子图中的迭代译码过程中,一个单位因子图总共传递4 个信息,依次为,向左传递LLR 值更新L 矩阵,向右传递R 值更新R 矩阵。 在第1 次迭代过程中,只有第1 列的R 矩阵包含软信息,其他列均初始化为0,因此第1次迭代计算时只需要考虑第1 列的;在第2 次及之后的迭代中,除了第1 列以外,都是由上一次迭代得到的算出的,因此不用考虑,可以将移除,即：

改进后的左信息更新方式如图3 所示。

图3 左信息更新机制示意图Fig.3 Left information update mechanism

1.3 剪枝译码算法

剪切译码树的思路可以从保存冻结比特图样的冻结向量来入手,用冻结向量F(Frozen)来表示不含有任何有用信息冻结比特,也就是“rate-0”比特,用冻结向量I(Information)来表示信息比特,也就是“rate-1”比特。 当一个节点的左右子节点的冻结图样为FF 时,那么这个节点也是一个“Rate-0”节点,如果节点的冻结图样为FI 或者IF 时,那么此节点不是“Rate-1”或者“Rate-0”节点,但是信息传递时的计算同样可以简化,如果此节点的冻结图样为II,那么信息更新方式不变。

设置一个标记矩阵用来储存每个节点的冻结图样,当这个节点的所有子节点都是冻结比特时,设置该节点的标记值为0;当这个节点的所有子节点都是信息比特时,设置标记值为2;如果一个节点的子节点中,只有一个信息比特、其余全是冻结比特,设置这个节点的标记值为1;如果节点的子节点不存在以上3 种特征,那么设置标记矩阵中相应的点的值为3。 按照这样的规则就可以将节点树标记完成,如图4 所示,节点中的数字为节点序号,节点下面的数字为标记值。

图4 标记矩阵在译码树中传递示意图Fig.4 Tag matrix passing in the decoding tree

通过以上方法即可实现节点的分类,可以分为4 类节点,其中标志矩阵值为0,1 的节点的矩阵B信息更新都可以通过简化的算法进行计算,从而简化译码算法的复杂度。 如果节点的标志矩阵值为0,那么直接设置

如果节点的标志矩阵值为1,那么可以类比rep 节点的计算方法,如果这个节点的包含的左信息个数为T,那么

通过以上的节点分类算法,将节点区分为可以简化更新信息的节点和不可简化的节点,就可以在信息更新过程中省去一些不必要的计算,从而降低算法的计算复杂度。 剪枝译码算法的复杂度降低比例与编码的码率、码字的冻结图样有关,由于剪枝译码算法的根本原理是降低“Rate-0”节点的计算复杂度,因此码率越低、冻结比特越多,那么复杂度降低幅度越大[7]。

1.4 复杂度分析

1.4.1 简化左信息更新的复杂度分析

简化的软信息更新方式主要降低了软信息更新过程中的存储复杂度。 SCAN 算法将N 个对数似然比信息分成2i组,这N/2i个LLR 值并行更新,但是与其他列和组的LLR 不同时更新,对于第t 层译码树需要存储的信息数为2n-t-1个,因此储存左信息的单元总数为=N - 1 个,储存右信息同样需要N - 1 个储存单元,SCAN 译码中所有节点都需要储存右子节点的信息用于下一次迭代计算使用,需要的存储单元为nN/2,同时还需要2N 个单元用于储存输入信息和输出信息,因此SCAN 算法需要的存储单元个数为4N - 2 +log2N。

从图5 中可以看出,简化的左信息更新方式对于N=256,N=1 024 的极化码分别能降低37.6%,44.6%的存储资源占用数,码长越长存储资源的占用数下降比例越大。

1.4.2 剪枝译码的复杂度分析

剪枝译码算法将SCAN 译码过程中的一部分译码树直接剪枝,Rate-0 节点直接剪枝,可以认为计算量为0;rep 节点使用简化算法,用加法运算来取代运算,省略了一次乘法运算。 在译码过程中,用运算次数来近似表示译码过程中的计算复杂度。

图4 中,剪枝前每个节点与子节点之间都有1 次左信息更新和1 次右信息更新,译码树总共有28 个信息更新操作,每个信息更新包括1 次运算和2 次加法;剪枝后,剩下14 次完整的信息更新和3 次rep 节点更新;用运算次数来近似计算复杂度,图4 的译码树剪枝后计算复杂度降低了50%左右。

图4 中分析的码长为8,5 位信息位,也就是码率为5/8。 一般情况下,码率为0.5 时,计算复杂度能降低50%～60%,根据冻结图样的不同,剪枝后的译码树也有差异。

2 简化的联合检测译码算法

联合检测译码算法的框架如图6 所示。 与传统的级联系统相比,联合检测译码算法利用极化码译码后输出的软信息,循环反馈到SCMA 用户检测器,以更精准的似然比信息作为输入来检测各个用户的信息。

图6 联合检测译码算法的框架图Fig.6 Joint detection and decoding algorithm framework

2.1 JIDD 的实现

JIDD 系统中的消息传递算法(MPA)与SCMA系统单独的消息传递有一些不同,JIDD 系统中MPA算法包括函数节点更新、先验信息更新和变量节点更新3 个主要步骤[8]。

为了描述联合检测译码算法方便先定义符号,从函数节点fj到变量节点vi的信息和从vi到fj的信息分别表示为) ,) ,集合p ∈{}表示与vi相连的FN 的集合,集合p ∈{} 表示与函数节点fj相连的VN 的集合, p ∈{j} , p ∈{i} 分别表示排除了函数节点fj的集合p ∈{}和排除了变量节点vi的集合p ∈{} ,SCMA 第i个用户的第l 个码字的先验概率为P(。

(1) 函数节点更新

当接收机接收到信道信息后,SCMA 用户检测器的函数节点将会更新它的信息并且传递给相邻的变量节点[9]。 从函数节点传递到相邻的变量节点的信息可以表示为：

计算出符号对应的外部信息后,SCMA 检测器通过映射关系进行计算并转换为对数似然比的形式,作为极化码译码器输入信息,因此需要分别计算反映射后为0 和为1 各自的似然比,最后将SCMA用户检测器的输出的对数似然比信息进行解交织,即可作为极化码译码器的先验信息：

(2) 先验信息的更新过程

当SCMA 用户检测器的输出的对数似然比信息解交织得到译码器的先验信息后,极化码译码器将会计算并且输出码字的似然比信息作为外部信息,这个信息将继续转化为SCMA 检测器的先验信息[10]。

极化码在因子图中进行信息更新,在因子图中传递2 个LLR 信息,当左信息到达因子图左侧,右信息到达因子图右侧时,一次译码迭代完成,译码器输出的外部信息再次通过交织器,作为SCMA 检测器的先验信息,表示为：

在具体实现中,由于极化码输出的软信息输出不是很稳定,因此需要加一个阻尼系数,具体的阻尼机制以及阻尼系数的选取将在下一节详细论述。 在得到SCMA 检测器的先验对数似然比信息后,将它转换为概率域的信息并且重新映射到SCMA 符号信息,表示为：

(3)变量节点的信息更新

当变量节点接收到符号的先验信息时,变量节点将更新它们的信息并且向与之相邻的函数节点更新,从变量节点到函数节点的信息传递可以表示为：

即可完成在MPA 用户检测器内部的信息传递,到此依次循环迭代完成。 在MPA 的函数节点更新后,MPA 的内部信息又传递给极化码译码器,又开始下一次循环[11]。

2.2 阻尼机制的选取

MPA 接收机对错误信息很敏感,如果软信息中存在错误译码信息,那么很容易引起SCMA 检测器的错误检测,以至于一次次迭代下去,因此需要适当压缩极化码译码的输出信息。 在译码器输出的软信息到MPA 检测器的先验信息的转换过程中,可以通过设置一个阻尼系数的方式来压缩软信息,在压缩译码器软信息输出的同时,降低软信息之间的相关性。

根据文献[12-15],将译码器输出的软信息转换成为用户检测器的先验信息过程,性能较为优越的引入阻尼因子的方式有3 种,分别为：

通过控制变量的仿真来对比2 种阻尼方式的性能差异,从而选取最优的阻尼方式。 极化码码长为256,用户数为6,码率为1/2,SCMA 子载波数为4,码本选择文献[16],每个码本中的码字个数为4,调制方式为BPSK,信道为AWGN。

分别采用3 种阻尼方式时,不同阻尼系数对应的误码率性能曲线如图7～图9 所示。

图8 阻尼机制2 的性能曲线Fig.8 Damping mechanism 2 performance curve

图9 阻尼机制3 的性能曲线Fig.9 Damping mechanism 3 performance curve

从性能曲线中可以看出,采用第1 种阻尼机制时,α 值为0.6 对应的性能最好;采用第2 种阻尼机制在低信噪比时α 值为1.2 性能最好,高信噪比时α 值为0.6 性能最好;采用第3 种阻尼机制时,α 值为0.6 的误码率性能最好。

如图10 所示,将误码率性能最好的3 条曲线进行对比可以看出,当信噪比较低时,第1 种和第3 种阻尼机制误码率性能更好;当信噪比较高时,第3 种阻尼机制的性能明显优于其他2 种;在误码率为10-3附近时,第3 种机制比其他2 种好0. 2 dB 左右;当信噪比继续增大时,第3 种阻尼机制的性能优势将更明显。 同时仿真了N=1 024 时其他条件不变的情况,同样是第3 种阻尼机制为最优,从而确定最优阻尼机制为第3 种阻尼方式。

图10 3 种阻尼机制的最优性能曲线对比Fig.10 Comparison of optimal performance curves of three damping mechanisms

3 仿真分析

3.1 简化SCAN 译码算法性能分析

简化的SCAN(SSCAN)算法省去了一部分不必要的更新节点,减少了计算复杂度和存储单元的占用数,理论上对误码率性能没有影响。 为了验证理论的正确性,仿真对比了SSCAN 算法与传统SCAN算法的性能差异。

图11 为N=1 024 的SSCAN 与SCAN 算法性能比较仿真图,码率为1/2,调制方式为BPSK,信道为AWGN 信道,码字构造的方式采用高斯近似法。

由仿真结果可以看出,N=1 024 的情况下简化后的SCAN 算法与标准SCAN 算法性能一致,同样的方法验证得出N 为128,256,2 048 时仿真结果与N 为1 024 相同,曲线几乎完全重合,说明在降低了译码复杂度的情况下,译码性能没有降低,与原SCAN 算法误码率性能一致。

图11 简化SCAN 算法标准SCAN 性能比较(N=1 024)Fig.11 Simplified SCAN algorithm compared with standard SCAN algorithm(N=1 024)

3.2 改进的联合检测译码算法性能分析

原有的联合系统有2 种思路：硬判决反馈和软信息迭代。 硬判决反馈由于采用性能极好的CRC-SCL译码算法,能够达到很好的误码率性能;本文的联合系统采用简化的联合检测译码算法(Simplified-JIDD),基于软信息迭代的系统进行改进,采用改进的SCAN 译码算法降低计算复杂度,同时引入阻尼机制提升误码率性能。

3.2.1 SJIDD 与JIDD 性能分析

与原有的JIDD 相比,SJIDD 采用简化的SCAN译码算法,只进行外循环迭代省去内循环结构,并且引入了阻尼机制。 分别讨论简化的外循环结构与内外双循环结构的性能差异,以及阻尼机制对于系统的影响。

为了验证简化后的算法与原算法性能是否一致,本文进行了仿真对比。 首先仿真比较了提出的单外循环与内外双循环结构的接收机性能差异。 仿真参数极化码码长为256,用户数为6,码率为1/2,SCMA子载波数为4,每个码本中的码字个数为4,调制方式为BPSK,信道为AWGN。 仿真结果如图12 所示,可以看出当去掉内循环结构后,联合接收机的性能与内外双循环的结构的误码率性能一致,在降低译码时延和复杂度的情况下,系统性能没有降低。

为了验证阻尼机制在软信息输出转换中对于系统误码率性能的提升,对无阻尼直接输出的联合迭代系统和阻尼系统进行对比,其中仿真参数中码长N=1 024,其他参数与图12 仿真参数一致。

如图13 所示,加入阻尼机制的系统大约比无阻尼系统提升了0.7 ～0.9 dB 的误码率性能,在计算复杂度几乎没有增加的情况下,系统性能提升幅度很大。

图12 内外双循环与外循环结构性能对比曲线Fig.12 Performance comparison between double loop structure and outer loop structure

图13 无阻尼与阻尼系统性能对比曲线Fig.13 Performance comparison between undamped and damped systems

3.2.2 SJIDD 与硬判决反馈系统的性能分析

基于SCMA 场景研究的与极化码的联合接收机,文献[17]提出了一种基于反馈硬判决的迭代检测译码算法,在联合接收机中,首先将接收信号送到独立的SCMA 用户检测器中,采用MPA 消息传递算法,在因子图中迭代输出用户的码字最大似然比(LLR),将码字的LLR 送入极化码的CRC-aided-SCL 译码器,解码器判决得出信息码字,利用解码得到的信息序列重建该用户的消息序列反馈到SCMA检测器中,更新资源节点接收到的信号,在因子图中移除相连的变量节点和关联边,依次迭代。 这种反馈硬判决的译码方式采用误码率性能最好的CASCL 译码算法,译码得到硬判决信息后再进行码字重构,然后反馈到MPA 用户检测器进行用户检测。

为了比较本文中SJIDD 与硬判决反馈的联合系统的性能差异,进行仿真分析。 仿真参数极化码码长为1 024,码率为1/2,SCMA 子载波数为4,用户数为6,每个码本中的码字个数为4,调制方式为BPSK,信道为AWGN,采用第3 种阻尼机制,阻尼系数为0.6,CA-SCL-JDD 采用保留32 条路径的SCL译码算法。 仿真结果如图14 所示。

图14 SCL 硬判决反馈接收机与软信息JIDD 接收机性能曲线Fig.14 Performance comparison between SCL hard decision feedback receiver and JIDD soft information receiver

可以看出,基于SCL 硬判决反馈的接收机,因为保存了多条可能路径,配合CRC 循环冗余校验可以有效降低极化码的误码率,从而降低联合接收机的译码误码率。 但是SCL 算法保存了多条可能路径,其计算复杂度和存储复杂度很高,而本文的SJIDD 采用并行的SCAN 译码算法,同时省略内循环直接进行外循环迭代,因此译码时延与CA-SCLJDD 的算法时延降低很大幅度,与保留路径数为32的CASCL-JDD 相比,本文的SJIDD 算法译码时延降至原来的1/5 ～1/8。 从性能曲线可以看出,JIDD的性能与反馈硬判决的SCL-JDD 性能差距不大,相差0.7 dB 左右。

4 结束语

本文提出2 种对SCAN 译码算法的改进方式,分别是简化的左信息更新方式和剪枝译码树算法,基于这2 种改进的信息更新算法,提出一种低复杂度的SSCAN 算法。 简化的左信息更新方式对于N=256,N= 1 024 的极化码分别能降低37. 6%,44.6%的存储资源占用数目;剪枝译码算法在码率为0.5 时,能降低50%左右的计算复杂度。 其次,在SCMA 场景下,提出了一种新的联合检测译码算法,并将简化的极化码SCAN 译码算法应用到联合接收机中,引入阻尼机制,选取了最优的阻尼机制以及最优阻尼系数。 仿真结果显示,采用外迭代的接收机性能与内外双循环迭代的接收机性能相同,采用阻尼机制的联合接收机性能比无阻尼的接收机性能高0.8 dB 左右,SJIDD 的误帧率性能比保留宽度为32的SCL-JDD 差0.7 dB 左右。