基于变量节点串行策略的SCMA低复杂度译码研究

吉明明，郑建宏

（重庆邮电大学通信与信息工程学院，重庆 400065）

基于变量节点串行策略的SCMA低复杂度译码研究

吉明明，郑建宏

（重庆邮电大学通信与信息工程学院，重庆 400065）

稀疏码多址接入（SCMA）技术作为5G无线通信网络的一个竞争性的非正交多址方案，具有广阔的应用前景。但目前基于SCMA的上行链路均采用泛洪方案的消息传递算法（MPA）进行译码，无论是检测的复杂度还是收敛速度都不甚理想。提出一种改变信息更新策略的串行消息传递算法——S-MPA（serial MPA），按照变量节点的次序进行消息处理和传递，每一个变量节点同时进行校验消息的接收和变量消息的发送。理论和仿真结果表明，该算法不仅能保持良好的性能，而且也有较低的解码复杂度。

稀疏码多址接入；多用户检测；变量节点；串行消息传递

1 引言

伴随移动设备与物联网的迅速发展，无线通信网络的数据流也将成倍增长，5G移动通信需要有效地支持更加多样化的设备。所以，5G网络希望在业务和链接密度及高移动性等要求很高的场景中，能够支持更多的数据业务类型，提供更高的数据速率和超低的时延、海量链接以及更好的服务质量（quality of service，QoS）、更高的频谱效率（spectral efficiency，SE）或能量效率（energy efficiency，EE）等[1,2]。这必定给5G空中接口技术带来很多新的挑战，特别是多址接入领域，将遇到极大的挑战。

在过去的十几年中，很多学者已经对码分多址接入（code division multiple access，CDMA）的非正交技术进行了深入的研究，近年来低密度信号（low density signature，LDS）作为一种特别的CDMA技术被提出，用以解决5G标准海量连接的情况。随着LDS-CDMA多址技术发展，演变为性能更优的稀疏码多址接入（sparse code multiple access，SCMA）[3-9]，在 SCMA系统中，QAM（quadrature amplitude modulation）映射和LDS联合在一起，比特流直接映射到复数域的多维码本的码字，因此，LDS思想的提出可以更好地满足5G大量的连接需求[6,9]。然而，为了使SCMA成为5G空中接口中有竞争力的候选非正交接入方法[10,11]，有两个至关重要的问题，即设计优良的SCMA码本和高效的译码算法。在参考文献[9]中，提出了系统的码书设计方法和评估方法。所以本文专注于高效的多用户检测的译码算法。

基于LDS思想，SCMA系统将每一个用户的比特流映射到有限的子载波上，同时保证每一个资源块上的叠加用户数在一定范围内，这为上行链路实现低复杂度译码算法提供了可能。参考文献[12,13]针对SCMA扩频矩阵设计稀疏性的特点，最先提出了一种上行 SCMA系统用户检测算法——MPA（message passing algorithm）[4,14]，MPA算法具有接近最大后验概率的性能，但译码复杂度较高。参考文献[15]提出了一种MPA的改进算法——PM-based MPA（partial marginalization based MPA），在保证译码性能的条件下，降低译码算法的复杂度。综上所述，现有SCMA上行链路译码算法大都采用泛洪消息传递机制进行译码，即在每轮迭代过程中，首先所有的校验节点进行消息更新，并把更新的消息传回与之相连的变量节点，紧接着变量节点进行消息更新，并把更新的消息传给与之相连的校验节点，而对于码字的判决只能等到每轮迭代完成之后才能进行，译码的效率并非最佳。

针对上述译码算法的不足，本文基于变量节点的串行策略提出了一种低复杂度的上行SCMA系统的多用户算法，本文算法改变了传统MPA的信息更新策略，可以把已更新的消息用于当前的迭代计算中。

2 系统模型

2.1 上行SCMA系统概述

SCMA是一种码域的非正交多址接入技术。在SCMA系统中，调制和编码是联合在一起进行的，即SCMA编码器将经过信道编码的用户比特根据用户的码本（CodeBook）直接映射对应复数域码字（CodeWord），对于一个上行链路的SCMA通信系统，假定有J个用户，K个正交时频资源（J＞K），J个用户稀疏扩频到K个子载波，定义λ=J/K为其过载因子。例如，过载因子为1.5的6个用户、4个正交资源块的上行SCMA系统模型如图1所示。

4资源块代表4子载波，6路消息流扩展到这4个资源块，经过信道编码后的信息流经 SCMA编码器，并扩展到多个正交资源上。这6条消息流可以属于一个用户或几个用户。为简单起见，假设这6个消息属于6个用户。扩展叠加法是上面提到的非正交，在SC1资源块，覆盖UE1、UE3和UE5这3个用户。这样的叠加可使系统容纳海量用户。随着资源块数的增加，系统可以容纳更多的数据流和更高的系统过载。例如，在8个资源块中可能有24个用户的数据流，可以达到300%过载。

SCMA编码器将用户比特根据用户的码本直接映射对应复数域码字，即：

图1 上行SCMA系统模型

其中，χ是具有稀疏性复数向量，代表一个K维码字，且码字中只含有L（L＜K）个非零元；M是输入信号的种类，即码本的尺寸。若用C来代表一个L维的星座点向量，则输入信号比特到相应L维的星座点集C的关系可以由式（2）来确定：

SCMA编码器的编码函数可定义如下：

。例如，6个用户、4个正交资源块的上行SCMA系统模型因子图和映射矩阵的关系如图2所示。

为简单起见，假定所有用户的本地时间是同步的，则在SCMA上行链路终端收到的信号为所有用户发送信号的叠加，具体如式（4）所示：

图2 SCMA的因子图与矩阵的关系

由于码字是稀疏的，因此在时频资源 k处有较少的码字冲突。

2.2 原始MPA

消息传递算法是利用因子图模型解决概率推理问题的有效方法，特别适合应用在低密度的因子图中。由于SCMA传播稀疏性，复杂性接收器可以被限制在较低的范围内，以确保接收机使用消息传递算法（MPA）来检测消息，MPA用多个相对简单的迭代步骤来等效复杂的信号处理，各个步骤之间的运算以信息概率为基础，使软信息在因子图上尽可能无损失地进行传递，每一轮迭代过程分解为如下两个步骤。

步骤 1 更新所有校验节点 ck到变量节点uj传递的概率消息

步骤 2 更新所有变量节点uj到校验节点 ck传递的概率消息

第1次进行消息迭代更新时，因为没有先验的任何信息，因此所有信息均被等概率初始化为，其中M为码本尺寸。

在因子图中，变量节点可以通过如下规则进行更新：

其中，t表示迭代进行的次数，当迭代过程收敛或者达到预设的最大迭代次数后，每一个用户发送码字的的输出概率即发送符号的后验概率可以通过式（8）进行计算：

于是，发送信号的第 i个比特的软判决信息可以表示为：

3 串行译码算法

传统 MPA在每轮迭代中消息的更新处理都是并行的：首先校验节点同时处理和传送校验消息，紧接着变量节点同时处理和传送变量消息。在每次迭代中，无论是校验节点信息还是变量节点的信息计算都是利用上一轮迭代更新的结果，即本轮更新的信息会延迟传递。对于实际工程应用，这样的处理过程不仅会占用大量的硬件资源而且收敛性也并非最佳，为了加快MPA的收敛速度，本文将在同一次迭代更新中充分利用这些已更新的消息。

3.1 基于变量节点串行译码算法

针对上述译码算法的不足，本节提出一种基于变量节点串行消息传递的MPA，它能够在译码性能和复杂度保持良好的平衡。本算法依照串行策略对变量节点更新信息，一次迭代过程如图 3所示。该方法确保更新的消息在同一轮迭代中传输，提高了消息的收敛速度。

图3 本文算法的一次迭代过程

根据式（7）与式（8），可得：

基于变量节点串行策略的 MPA低复杂度译码算法的详细流程如下所示，这种串行策略按照变量节点的预定次序进行消息的更新和传递，确保已经更新的消息在本轮中马上得到传递，不同于原始 MPA并行策略，更新的消息在下一轮迭代中才能传输。这样的消息更新策略加快了消息的收敛速度，在较少迭代次数时，本文算法译码性能就能达到较好的效果。然而，由于串行更新策略，每次迭代所需的时间增加，将有一定程度的时延。

3.2 复杂度分析

SCMA多用户检测算法的复杂度主要花费在迭代过程信息更新与迭代次数上，为了统一比较算法效率，本文中所有算法的复杂度将以算法中所用到的乘法器的个数进行对比分析，见表1，其中 df代表作用在资源节点的用户数目，dv代表作用在用户节点的资源节点数量，m 与Rs代表PM-based MPA相关的参数。

表1 不同MPA所需乘法器数目

4 仿真结果与分析

为了验证本文算法性能，对原始 MPA和PM-based MPA与本文算法在相同条件下进行了仿真比较，同时在信道中引入加性高斯白噪声，仿真时SCMA系统的参数为K=4，J=6，M=4，

4.1 收敛速度

图4显示了本文算法S-MPA、原始MPA和PM-based MPA的BER性能与迭代次数的关系。由图4可知，对于同一迭代次数，PM-based MPA的BER性能远差于本文算法和原始MPA，并且本文算法S-MPA经过少数次的迭代，BER性能几乎达到其译码的最佳水平。可见，基于变量节点的串行消息传递机制，使得节点消息的更新与传递结合起来，加快了译码的收敛速度，即使经过少数几次迭代便能取得在并行策略下多次迭代才能达到的误码性能。迭代次数达到一定条件后，本文算法与原始MPA在BER性能上的差距越来越小，最终译码性能达到稳定，但在实际的应用中兼顾硬件资源开销，使得这种以消息传递为基础的译码的迭代次数不能取得很大，更能体现本文串行策略的优势。

4.2 BER性能

图5给出了本文算法S-MPA、原始MPA与PM-based MPA在不同信噪比条件下BER性能与迭代次数的关系曲线，可以看到，随着信噪比的增大，BER性能有了明显的改善。从图 5可以得到，对于相同的迭代次数，本文算法的译码性能都优于原始MPA，在Eb/N0=10 dB时，2次迭代原始MPA的BER值为6.1× 10-3，而本文算法 2次迭代的 BER 值为2.4× 10-3。在BER=1.0× 10-3时，本文算法2次迭代的BER性能优于 6次迭代的 PM-based MPA，并且伴有0.65 dB的增益。

图4 各种算法的收敛速度

图5 各种算法的BER性能对比

4.3 复杂度对比

为分析算法效率，对几种算法收敛时使用的乘法器的数目进行了比较，结合第 4.2节分析，在时本文算法S-MPA 2次迭代的性能和原始MPA和PM-based MPA6次迭代的性能几乎等效，涉及的乘法器个数分别为 10 944、32 256、26 208。与原始MPA相比，本文算法节省了66.1%的乘法器。并且，相对于 PM-based MPA算法，不仅节约了58.3%的乘法器，而且在译码性能方面也有不错的增益。因此，该算法可以提供一个良好的BER性能和复杂性之间的平衡。

为分析译码时间，对原始MPA与本文算法在相同条件下的译码时间进行了对比，如图6所示，由于本文算法采用串行更新策略，每次迭代所需的时间增加，但相对于性能的提升，这点时延在接受范围之内。

图6 本文算法与原始MPA译码时间对比

5 结束语

本文基于上行SCMA通信链路系统，以因子图中的变量节点消息串行更新为基础，提出了一种加快译码收敛速度的多用户检测算法。相对于原始MPA与PM-based MPA，本文算法在不增加译码复杂度的基础上，改善了译码的性能。因此，本文算法是一种具有很高的实用价值的SCMA多用户检测算法。本文对MPA信号检测技术的研究只局限于信道条件已知的高斯信道以及终端处于静止状态的情况，但在实际应用场景中，多变的信道环境和运动的终端都会对系统性能产生较大的影响。因此，针对不同应用场景和不同状态的终端，研究切合实际的SCMA技术解决方案，将是非常有价值的研究方向。

[1] BHUSHAN N, LI J, MALLADI D, et al. Network densification: the dominant theme for wireless evolution into 5G[J]. IEEE Communications Magazine, 2014, 52(2): 82-89.

[2] ROWELL C, HAN S. Toward green and soft: a 5G perspective[J]. IEEE Communications Magazine, 2014, 52(2): 66-73.

[3] DAI L, WANG B, YUAN Y, et al. Non-orthogonal multiple access for 5G: solutions, challenges, opportunities, and future research trends[J]. IEEE Communications Magazine, 2015, 53(9): 74-81.

[4] HOSHYAR R, WATHAN F P, TAFAZOLLI R. Novel low-density signature for synchronous CDMA systems over AWGN channel[J]. IEEE Transactions on Signal Processing, 2008, 56(4): 1616-1626.

[5] BEEK J V D, POPOVIC B M. Multiple access with low-density signatures[C]//IEEE Global Telecommunications Conference, January 26-28, 2009, London, UK. New Jersey: IEEE Press, 2009: 1-6.

[6] NIKOPOUR H, BALIGH H. Sparse code multiple access[C]// IEEE International Symposium on Personal Indoor and Mobile Radio Communications, September 8-11, 2013, London, UK. New Jersey: IEEE Press, 2013: 332-336.

[7] AU K, ZHANG L, NIKOPOUR H, et al. Uplink contention based SCMA for 5G radio access[C]//IEEE GLOBECOM Workshops, December 8-12, 2014, Austin, TX, USA. New Jersey: IEEE Press, 2014: 900-905.

[8] ZHANG S, XU X, LU L, et al. Sparse code multiple access: an energy efficient uplink approach for 5G wireless systems[C]//IEEE Global Communications Conference, December 8-12, Austin, TX, USA. New Jersey: IEEE Press, 2014: 4782-4787.

[9] TAHERZADEH M, NIKOPOUR H, BAYESTEH A, et al. SCMA codebook design[C]//IEEE Vehicular Technology Conference, September 14-17, 2014, Vancouver, Canada. New Jer-sey: IEEE Press, 2014: 1-5.

[10] 毕奇, 梁林, 杨姗, 等. 面向 5G 的非正交多址接入技术[J].电信科学, 2015, 31(5): 14-21. BI Q, LIANG L, YANG S, et al. Non-orthogonal multiple access technology for 5G systems[J]. Telecommunications Science, 2015, 31(5): 14-21.

[11] 马国玉, 艾渤, 胡显安, 等. 5G过载零星传输系统中的多用户检测技术性能分析[J]. 电信科学, 2016, 32(8): 39-45. MA G Y, AI B, HU X A, et al. Performance analysis of multi-user detection of 5G overloaded sporadic system[J]. Telecommunications Science, 2016, 32(8): 39-45.

[12] WANG B, WANG K, LU Z, et al. Comparison study of non-orthogonal multiple access schemes for 5G[C]// IEEE International Symposium on Broadband Multimedia Systems and Broadcasting, June 17-19, 2015, Ghent, Belgium. New Jersey: IEEE Press, 2015: 1-5.

[13] WU Y, ZHANG S, CHEN Y. Iterative multiuser receiver in sparse code multiple access systems[C]//ICC IEEE International Conference on Communications, June 8-12, 2015, London, UK. New Jersey: IEEE Press, 2015: 2918-2923.

[14] KSCHISCHANG F R, FREY B J, LOELIGER H A. Factor graphs and the sum-product algorithm[J]. IEEE Transactions on Information Theory, 2001, 47(2): 498-519.

[15] MU H, MA Z, ALHAJI M, et al. A fixed low complexity message pass detector for up-link SCMA system[J]. IEEE Wireless Communications Letters, 2015, 4(6): 585-588.

Research on low complexity decoding for SCMA based on serial strategies of variable node

JI Mingming, ZHENG Jianhong
School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

Sparse code multiple access technology, as a competitive non orthogonal multiple access scheme for the fifth generation wireless communication network, has a broad application prospect. However, current SCMA uplink use the flooding scheme of message passing algorithm for decoding, both the detection complexity and convergence properties are not ideal. A serial message passing algorithm which changed the information updating strategy was proposed, which performed message processing and deliveried according to the order of the variable nodes. Each of variable node simultaneously performed the reception of the verification message and the transmission of the variable message. The theoretical and simulation results show that the proposed algorithm not only maintains good performance, but also has low decoding complexity.

sparse code multiple access, multiuser detection, variable node, serial message passing

The National Science and Technology Major Project of China (No.2016ZX03002010-003)

TN929

：A

10.11959/j.issn.1000-0801.2017226

吉明明（1992-），男，重庆邮电大学通信与信息工程学院硕士生，主要研究方向为5G关键技术——新型多址技术SCMA。

郑建宏（1961-），男，重庆邮电大学通信与信息工程学院教授，主要研究方向为新一代宽带移动通信协议及系统应用。

2017-03-15；

：2017-07-16

国家科技重大专项基金资助项目（No.2016ZX03002010-003）