基于Rtree的稀疏码多址接入系统的译码算法

Decoding Algorithm for Sparse Code Multiple Access System Based on Rtree

摘要: 在非正交多址接入(NOMA)技术中，稀疏码分多址接入(SCMA)由于码本的稀疏性，通常可以在接收端采用消息传递算法(MPA)实现多用户检测，但其计算复杂度依然较高。利用Rtree快速高效搜索的特点，提出了一种Rtree-MAP的SCMA译码算法。具体做法是将所有合成星座点生成多维Rtree空间数据结构，然后将接收信号利用Rtree快速检索得到发送端对应的用户数据信息。仿真表明，提出的Rtree-MAP译码算法在误码性能和译码速度上都优于MPA译码算法。

Abstract: In non-orthogonal multiple access (NOMA) technology, sparse code multiple access (SCMA) can usually use message passing algorithm (MPA) to achieve multi-user detection at the receiver due to the sparsity of the codebook, but its computational complexity is still high. A SCMA decoding algorithm for Rtree-MAP is proposed by taking advantage of the fast and efficient search of Rtree. The specific approach is to generate a multi-dimensional Rtree spatial data structure for all synthesized constellation points, and then use Rtree to quickly retrieve the user data information corresponding to the sending end from the received signal. Simulations show that the proposed Rtree-MAP decoding algorithm outperforms the MPA decoding algorithm in terms of both BER performance and decoding speed.

1. 引言

随着移动通信和物联网的快速发展，第五代通信技术(5G)已经正式商用，第六代移动通信 [1] [2] [3] (6G)已经展开了研究，6G要求更高的频谱效率和更大的系统容量，传统的正交多址接入(OMA)技术已经不能满足需求。NOMA [4] [5] 技术通过允许多用户在发送端共享同一频谱资源，能有效地提高系统吞吐量和接入用户数，被认为是未来无线通信系统的关键技术之一。

作为NOMA技术的一种，SCMA [6] 是利用码本的稀疏性来获得设备高接入量的一种多址接入技术。在发送端，每个用户将数据比特直接映射为SCMA码本中的多维码字，从而使多个用户可以承载在同一频谱资源上，系统容量得到大幅提升。接收端则接收各种用户叠加信号，可以利用多用户检测算法进行译码。

最大后验概率算法(Maximum-a-posteriori, MAP)作为SCMA系统中的最优的译码算法 [7] ，在实际应用中由于计算复杂度较高而难以实现。作为一种次优计算法，消息传递算法(Message Passing Algorithm, MPA)由于码本的稀疏性，可以有效地接近联合最优的性能，但其算法的计算复杂度依然很高。为了降低译码算法的计算复杂度，许多文献通过对MPA的改进和优化 [8] [9] [10] [11] [12] ，但大多数都是以牺牲误码性能来降低译码的计算复杂度。

为了保证MAP算法的最优译码性能和提高SCMA系统的译码速度，受到Rtree快速检索技术的启发，提出了一种Rtree快速检索的Rtree-MAP译码算法，该算法在保证不失MAP算法的译码性能的同时，能非常快速地完成SCMA系统的译码。

2. 系统模型

2.1. 上行SCMA通信系统

假定有一个资源数为K，每个用户占用的资源数为N (N < K)的上行SCMA通信系统，那么该通信系统支持的最大用户量 $J=C_K^N$ ，过载率 $\lambda =J/K$ 。在发送端，每个用户分配不同的码本，M为每个用户的码本容量，经过SCMA编码器编码，每个用户将 ${\text{log}}_2\left|M\right|$ 个比特数据流直接映射成自身对应的K维复值码字。

接收端接收到的信号是J个用户同时在K个资源块上的复值码字和噪声的叠加信号，即：

$y={\displaystyle \underset{j=1}{\overset{J}{\sum }}diag\left(h_j\right)x_j}+n$ (1)

式中， $x_j={\left[x_{1,j},x_{2,j},\cdots ,x_{K,j}\right]}^{\text{T}}$ 表示第j个用户发送的码字， $h_j={\left[h_{1,j},h_{2,j},\cdots ,h_{K,j}\right]}^{\text{T}}$ 表示第j个用户的信道衰落向量， $diag(·)$ 表示对角矩阵， $n={\left[n_1,n_2,\cdots ,n_K\right]}^{\text{T}}$ 表示信道噪声且满足 $n~cN\left(0,{\sigma }^{2}I\right)$ 。在第k个资源块上接收信号可以表示为

$y_k={\displaystyle \underset{j\in {\epsilon }_k}{\sum }{h}_{k,j}{x}_{k,j}}+n_k$ (2)

其中 ${\epsilon }_k$ 表示占用资源块k的用户集合。

在SCMA系统接收端，假定已知接收信号y和关联信道衰落矩阵 $H=\left[h_1,h_2,\cdots ,h_J\right]$ ，那么可以联合最优MAP算法来检测用户发送的码字 $X=\left[x_1,x_2,\cdots ,x_J\right]$ ，如式：

$\hat{X}=\arg \underset{X\in \left({\times }_{j=1}^J\right){\chi }_j}{\max }\rho \left(X|y\right)$ (3)

式中， $\left({\times }_{j=1}^J\right){\chi }_j={\chi }_1\times {\chi }_2\times \cdots \times {\chi }_J$ 表示J个用户的码字组合集合。 ${\chi }_j=\left\{{\chi }_j^1,{\chi }_j^2,\cdots ,{\chi }_j^M\right\}$ 表示第j个用户的码本。MAP算法计算复杂度极高，需要对所有用户的所有码字组合全部进行搜索(若用户数为J，每个用户有M个码本，则需搜索次数为 $M^J$ )，可以看出MAP算法的计算复杂度随着用户数增加呈指数级增长，这在实际应用中是很难实现的。

2.2. MPA译码算法

MPA译码算法是一种次优多用户检测算法，利用二分因子图结构求解边缘概率。在MPA译码过程中，外信息通过因子图的边相互传递，在多次消息传递迭代后，通过计算所有用户的边缘概率分布来判断用户发送的码字。定义 $I_{j\to k}^t\left(x_j^m\right)$ 为第t次迭代中第j个用户在第k个资源块上发送码字 $x_j^m$ 的概率； $I_{k\to j}^t\left(x_j^m\right)$ 为第t次迭代中在第k个资源块上检测到第j个用户发送码字 $x_j^m$ 的概率。MPA算法过程如下：

Step1：初始化，假设用户发送的码字概率都相同，则有

$I_{j\to k}^0\left(x_j^m\right)=\frac{1}{M}\left(k\in {\varsigma }_j,j=1,\cdots ,J;m=1,\cdots ,M\right),$ (4)

其中， $x_j^m$ 表示用户j的第m个码字， ${\varsigma }_j$ 表示用户j占用资源的集合。

Step2：外信息相互传递更新

$I_{k\to j}^t\left(x_j^m\right)={\displaystyle \underset{~x_j^m}{\sum }\left\{\exp \left(-\frac{1}{2{\sigma }^2}{\Vert y_k-{\displaystyle \underset{j\in {\epsilon }_k}{\sum }{h}_{j,k}{x}_{j,k}}\Vert }^2\right)\times {\displaystyle \underset{l\in {\epsilon }_k/j}{\prod }{I}_{l\to k}^{t-1}\left(x_l^m\right)}\right\}},$ (5)

$I_{j\to k}^t\left(x_j^m\right)=normalize\left({\displaystyle \underset{c\in {\varsigma }_j/k}{\prod }{I}_{c\to j}^t}\left(x_j^m\right)\right),$ (6)

其中， ${\epsilon }_k/j$ 表示从用户集合 ${\epsilon }_k$ 中移除用户j， ${\varsigma }_j/k$ 表示从资源集合 ${\varsigma }_j$ 移除资源k。 $normalize(·)$ 表示归一化操作，即使得 ${\displaystyle \underset{m=1}{\overset{M}{\sum }}{I}_{j\to k}^t\left(x_j^m\right)}=1$ 。

Step3：重复Step2，当达到最大迭代次数T_max后停止外信息传递更新，计算各用户发送码字的概率：

$Q\left(x_j^m\right)={\displaystyle \underset{k\in {\varsigma }_j}{\prod }{I}_{k\to j}^{T_{\max }}}\left(x_j^m\right).$ (7)

估算出发送端每个用户发送码字概率后，再将各用户的LLR作为发送端每个用户发送的比特流。

$LL{R}_j^n=\log \left({\displaystyle \underset{x_j:b_{x_j}^n=1}{\sum }Q\left(x_j^m\right)}\right)-\log \left({\displaystyle \underset{x_j:b_{x_j}^n=0}{\sum }Q\left(x_j^m\right)}\right),$ (8)

其中， $n=\mathrm{l},2,\cdots ,{\log }_{2}M$ ，比特数据流中的第n个比特 $b_{x_j}^n$ 表示用户j发送的对应码字 $x_j$ 。式(7)和式(8)可简化为：

${\hat{X}}_j=\arg \underset{x_j^m}{\max }\left({\displaystyle \underset{k\in {\varsigma }_j}{\prod }{I}_{k\to j}^{T_{\max }}}\left(x_j^m\right)\right).$ (9)

3. 基于Rtree的SCMA译码算法

3.1. Rtree介绍

Rtree是1984年由Antonin Guttman提出的，用于访问由二维或更高维区域对象构成的空间数据结构，可以用来处理多维数据 [13] 。Rtree是BTree在高维空间的一种扩展，在Rtree中有两类结点：叶子结点和非叶子结点。每一个结点由许多索引项构成，实际数据对象的最小外接矩形(注：“矩形”可以扩展到高维空间)存储在叶子节点中。

Rtree是运用了空间分割理念的平衡树，采用了最小边界矩形(MBR, Minimal Bounding Rectangle)的方法，从叶子结点开始用矩形框出数据点的空间，结点离根结点越近，框住的矩形空间就越大，图1为一个二维R树的空间结构。RTree在检索的时候，先检索这些MBR，再检索命中的MBR中的节点。这样的好处是：一则可以避免遍历所有节点，从而提高检索速度；二则可以并行处理，进而节约检索MBR的时间。

一棵Rtree满足如下的性质 [13] ：

1) RTree是n叉平衡树，所有叶子结点都位于同一层。

2) 每个结点对应一个矩形。

3) 叶子结点包含一个小于等于n的数据点，它对应的矩阵是全部数据点的外包矩形。

Figure 1. The spatial structure of a two-dimensional R-tree

图1. 一个二维R树的空间结构

3.2. SCMA系统的Rtree-MAP译码算法

在SCMA系统中，用户比特流信息直接映射为多维复数码字，所以合成星座和接收SCMA系统的信号均为复值数列。为适应Rtree的数据结构特征，需将合成星座和接收信号的复值序列转化为实数矩阵；其次利用码本的合成星座构成的实数矩阵生成Rtree的树状空间数据结构；然后通过接收端的接收信号(接收信号需转化为实数序列)查找Rtree中最符合MBR的节点索引，最后通过查找出的节点索引后通过映射还原，即可得到用户在发送端发送的比特信息。Rtree-MAP译码算法主要有以下步骤：

1) 构造合成星座Rtree：首先考虑发送端发送的码字 $X=\left[x_1,x_2,\cdots ,x_J\right]$ 的所有的可能性，不考虑码本的稀疏性，则每个资源块上有 $M^J$ 个合成星座点 $\left({\times }_{j=1}^J\right){\chi }_j^k$ ，其次考虑到每个合成星座点都是一个复数，为了适用于多维Rtree的空间结构，需将合成星座的复数矩阵 $A_c$ 转化为合成星座实数矩阵A，

$A_c={\left[\begin{array}{cccc}{\chi }_{1,1}^1\times {\chi }_{1,2}^1\times \cdots \times {\chi }_{1,J}^1& {\chi }_{2,1}^1\times {\chi }_{2,2}^1\times \cdots \times {\chi }_{2,J}^1& \cdots & {\chi }_{K,1}^1\times {\chi }_{K,2}^1\times \cdots \times {\chi }_{K,J}^1\\ {\chi }_{1,1}^1\times {\chi }_{1,2}^1\times \cdots \times {\chi }_{1,J}^2& {\chi }_{2,1}^1\times {\chi }_{2,2}^1\times \cdots \times {\chi }_{2,J}^2& \cdots & {\chi }_{K,1}^1\times {\chi }_{K,2}^1\times \cdots \times {\chi }_{K,J}^2\\ ⋮& ⋮& \ddots & ⋮\\ {\chi }_{1,1}^M\times {\chi }_{1,2}^M\times \cdots \times {\chi }_{1,J}^M& {\chi }_{2,1}^M\times {\chi }_{2,2}^M\times \cdots \times {\chi }_{2,J}^M& \cdots & {\chi }_{K,1}^M\times {\chi }_{K,2}^M\times \cdots \times {\chi }_{K,J}^M\end{array}\right]}_{K\times M^J}$ (10)

$A={\left[Re\left(A_c\right),Im\left(A_c\right)\right]}_{2K\times M^J}$ (11)

得到Rtree构造矩阵A后，利用Rtree的生成方法创建一个2K维Rtree。此时构造的Rtree中MBR的维度为2K，叶子节点的个数为 $M^J$ 。

2) 对用户进行译码：当接收端得到信号y后，还原各资源块上的接收信号序列 $y_s$ ，

$y_s={\left[y_1,y_2,\cdots ,y_K\right]}_{K\times 1}$ (12)

为了适应2K维Rtree的需要，将信号序列 $y_s$ 各资源块上的复值序列转化为多维Rtree的MBR查询节点序列 ${\hat{y}}_s$ ，

${\hat{y}}_s={\left[Re\left(y\right),Im\left(y\right)\right]}_{2K\times 1}$ (13)

当有了合成星座Rtree后和查询节点 ${\hat{y}}_s$ ，即可利用索引搜索方法 [14] 查找Rtree的中离 ${\hat{y}}_s$ 最近的叶子结点索引Index，最后将叶子结点索引Index映射为用户在发送端发送的比特信息，即完成SCMA系统的译码。

Rtree-MAP译码算法伪代码如下：

4. 仿真结果与讨论

利用MATLAB仿真分析，采用的是AWGN信道的SCMA系统信道模型，文献 [15] 提出的码本，码本大小包含两种，分别是码本大小为J = 6，K = 4，M = 2的码本和J = 10，K = 5，M = 2的码本。对比Rtree-MAP算法和MPA算法的误码性能和计算复杂度。

4.1. 性能分析

图2为Rtree-MAP算法和MPA算法(迭代6次)的译码性能对比，可以看出，码本大小为J = 6，K = 4，M = 2的码本在当SNR > 4时，Rtree-MAP算法误码性能要高于MPA算法，当SNR ≤ 4时，Rtree-MAP算法误码性能和MPA算法几乎相当；码本大小为J = 10，K = 5，M = 2的码本在整体上的误码性能都要由于MPA算法。可以看出，在相同的码本下，提出的Rtree-MAP算法BER性能对比，要优于MPA算法。这是因为Rtree-MAP算法是基于最优MAP算法的一种快速检索方法，能够获得较好的误码性能。

Figure 2. Comparison of decoding performance between Rtree-MAP algorithm and MPA algorithm

图2. Rtree-MAP算法和MPA算法的译码性能对比

4.2. 复杂度分析

MPA的算法的包括消息传递更新和码字检验这两个部分，而消息传递更新部分是MPA算法计算复杂度的主要体现。MAP译码算法则需要每次遍历整个合成星座点。Rtree-MAP译码算法在译码之初，将所有合成星座构造出一个Rtree的数据结构，在以后的搜索过程中，只需要对Rtree进行搜索即可。由于Rtree是一种自平衡查找树，其 $M^J$ 个叶子节点构成的Rtree高度始终小于 $O\left(J{\log }_{2}M\right)$ ，这使得Rtree的所有查找次数都在 $O\left(J{\log }_{2}M\right)$ 内，则Rtree-MAP算法的时间复杂度为 $O\left(J{\log }_{2}M\right)$ 。Rtree-MAP译码算法和MAP算法、MPA算法的时间复杂度对比情况见表1。

图3为Rtree-MAP算法和MPA算法的在不同码本大小下的译码时间对比，可以看出，Rtree-MAP算法相较于MPA算法，能大幅度提高SCMA系统的译码速度。当码本大小为J = 6，K = 4，M = 2的码本时，Rtree-MAP算法的译码时间大约是MPA算法译码时间的1/280，码本大小为J = 10，K = 5，M = 2的码本时，Rtree-MAP算法的译码时间大约是MPA算法译码时间的1/72，这是因为Rtree-MAP算法的大部分时间用在构建Rtree的过程中，当码本增大时，构建Rtree的过程所花的时间会相应增加。

Table 1. Comparison of time complexity of different SCMA decoding algorithms

表1. 不同SCMA译码算法的时间复杂度对比

Figure 3. Comparison of decoding time between Rtree-MAP algorithm and MPA algorithm

图3. Rtree-MAP算法和MPA算法的译码时间对比

5. 总结

为了降低SCMA通信系统中多用户检测算法的误码性能和计算复杂度，利用Rtree快速高效搜索的特点，提出了一种Rtree-MAP的SCMA系统译码检测算法。和MPA算法相比，该算法没有迭代的消息传递更新过程，在保持MAP误码性能的同时，译码速度得到了大幅度的提升。该算法在SCMA系统中实现海量连接并降低硬件实现的复杂度上具有较高的应用价值。