Multi-Dimensional Codebooks for Multiple Access Schemes

Abstract

The sparse code multiple access (SCMA) scheme directly maps the incoming bits of several sources (users/streams) to complex multi-dimensional codewords selected from a specific predefined sparse codebook set. The codewords of all sources are then superimposed and exchanged. The shaping gain of the multi-dimensional constellation of SCMA leads to a better system performance. The decoder’s objective will be to separate the superimposed sparse codewords. Most existing works on SCMA decoders employ message passing algorithm (MPA) or one of its variations, or a combination of MPA and other methods. The system architecture is highlighted and its basic principles are presented. Then, an overview of main multi-dimensional constellations for SCMA systems will be provided. Afterwards, we will focus on how the SCMA codebooks are decoded and how their performance is evaluated and compared.

1. Introduction

The massive connectivity is one of the main requirements of the 5G telecommunication systems and beyond. One key to fulfill this objective is to allow several users to efficiently access the same resources (frequency band for example) simultaneously, this approach is called multiple access. Based on how the resources are shared among multiple users, two types of multiple access could be distinguished: orthogonal multiple access (OMA) and non-orthogonal multiple access (NOMA) [1].

A well-known OMA scheme is code-division multiple access (CDMA), the idea is to divide the symbol duration into a number of time slots or chips such that the spreading sequence associated to each user is chosen from a set of non sparse quasi-orthogonal ones. The overall transmitted sequence is the result of the superimposition of the symbols of all users which are spread over different chips. The number of served users is limited to the number of available quasi-orthogonal sequences, however, the orthogonality of sequences guarantees the simplicity of the receiver since a low complexity correlation operation is sufficient to detect the users’ symbols despite the inter-sequence interference.

The key difference between code-domain NOMA techniques and the CDMA is that the spreading sequences of the former are restricted to non-orthogonal low cross-correlation sparse sequences such that more spreading sequences of code can be used, and consequently more users can be served simultaneously. One code-domain NOMA scheme which had shown to achieve a promising link level performance is SCMA [2]. Traditional code-domain schemes map bits to a symbol which is selected from one-dimensional constellation before spreading this symbol over a given low-density spreading sequence, SCMA combines together the two steps which gives birth to the idea of multi-dimensional constellations. The capacity to directly map the bits to some sparse SCMA codewords belonging to multi-dimensional codebooks attracts a lot of attention.

In this Chapter, we will present the SCMA system architecture by presenting its basic principles and its signal model. Then, existing methods for SCMA codebook design will be reviewed. Finally, we will explain how SCMA signal can be detected at the receiver either using the traditional MPA or one among its variations.

2. SCMA system architecture

In the following subsections, multi-dimensional coding principles are presented before illustrating why SCMA can be employed to provide multiple access.

2.1 Basic principles of multi-dimensional constellations

The SCMA spreads its sequence in the frequency domain over $K$ subcarriers, these narrow frequency bands are also called resource elements (REs). For an uplink scenario, a base station (BS) serves simultaneously $J$ separate users. The user $j$, so-called also layer $j$, sends a $K-\text{dimensional}$ codeword, ${\mathbf{x}}_j^{\left(m\right)}$, which represents ${log}_2\left(M_j\right)$ data bits. Consequently, ${\mathbf{x}}_j^{\left(m\right)}$ must be chosen from a codebook, ${\mathit{C}}_j$, of size $M_j$ such that the multi-dimensional constellation, $\mathcal{C}=\left\{{\mathit{C}}_j,1\le j\le J\right\}$ is designed to facilitate the multiple access. Actually, the codewords of all users, ${\mathbf{x}}_j^{\left(m\right)},1\le j\le J$, are superimposed and exchanged over the $K$ REs. In fact, $\mathcal{C}$ collects the signatures of served users. In order to increase the number of connected users, the codewords are designed to be sparse, i.e. all their entries are zeros except for few ones, in other words, the number of non-zero entries, $N_j$, must be lesser than the length of the codewords, $K$, i.e. $N_j\ll K$. Hence, the $j^{\mathrm{th}}$ SCMA layer can be described by its codebook sparsity degree, $N_j$, and the whole SCMA system is characterized by

• $d_f$ which is defined by the maximum degree of user superposition on a given RE,

• $\lambda$ which denotes the overloading factor, $\lambda$ is calculated by the ratio of number of users to number of REs, i.e. $\lambda =\frac{J}{K}$.

However, we must highlight that all the $N_j$ non-zero entries of the codewords of ${\mathit{C}}_j$ are located in the same positions.

Based on the different parameters of SCMA system, especially, the size of codebook of each user, $M_j$, and its codebook sparsity degree $N_j$, we can distinguish two kinds of SCMA system architectures:

1. The regular SCMA where users are treated equally, i.e. all users employ a codebook of size $M$ and their signals are spread over $N$ REs,

2. The irregular SCMA, as its name indicates, is designed such that the codebooks are allocated differently according to the different needs of users [3].

Figure 1 presents an example of a regular SCMA system, obviously, we have $N_j=2,1\le j\le J$ and $M_j=4,1\le j\le J$. This system is characterized by $d_f=3$ and $\lambda =150\%$. In the rest of this chapter, a simple”SCMA” will refer implicitly to regular SCMA.

Figure 1.

The encoder of a regular SCMA system: The transmitted codeword is the superposition of the codeword of each user which is selected from its own codebook according to the ${log}_2\left(M\right)$ bit to be transmitted at each time frame.

The received vector for an uplink SCMA system is given by,

$$\mathbf{y}=\sum _{j=1}^J{\mathbf{H}}_j{\mathbf{x}}_j^{\left(m\right)}+\mathbf{n},$$E1

where $\mathbf{y}={\left(y_1,\cdots ,y_K\right)}^T$ and ${\mathbf{x}}_j^{\left(m\right)}={\left(x_{j,1}^{\left(m\right)},\cdots ,x_{j,K}^{\left(m\right)}\right)}^T$. Let us denote the channel gain of user $j$ on subcarrier $k$ by $h_{j,k}$, hence the matrix ${\mathbf{H}}_j$ is diagonal of dimension $K\times K$ where $h_{j,k},1\le k\le K$ are its diagonal entries. Finally, at the receiver, a zero-mean white circularly complex Gaussian noise, $\mathbf{n}$, with variance $N_0$ is added; i.e. $\mathbf{n}\sim \mathcal{CN}\left(0,N_0{\mathbf{I}}_K\right)$, where ${\mathbf{I}}_K$ is the identity matrix of size $K$.

3. SCMA codebook design

The design of SCMA codebook is usually based on several steps, a description of each one among them is given in this section. The idea is that the constellation function, associated with each user $j$ generates a constellation set with $M$ alphabets of length $N$. Then, the mapping matrix ${\mathbf{V}}_j$ maps the $N‐\text{dimensional}$ constellation points to SCMA codewords to form the codebook ${\mathit{C}}_j$.

3.1 Codebook design procedure

The description of a SCMA system begins by determining the locations of non-zero elements of user $j,1\le j\le J,$ via the vector ${\mathbf{f}}_{\mathrm{j}}$, for instance ${\mathbf{f}}_{\mathrm{j}}={\left[\mathrm{1,1,0,0}\right]}^T$ means that the user $j$ employs the first two subcarriers only to send his data, this can be also described using another matrix, ${\mathbf{V}}_j$, of dimension $K\times N$, given by,

$${\mathbf{V}}_j=\left[\begin{array}{cc}1& 0\\ 0& 1\\ 0& 0\\ 0& 0\end{array}\right]$$E2

where ${\mathbf{V}}_j$ is the mapping matrix of user $j$. Thus, the whole SCMA system is described by gathering the ${\mathbf{f}}_{\mathrm{j}}$ vectors in one matrix $\mathbf{F}$ of dimension $K\times J$ such that $\mathbf{F}=\left({\mathbf{f}}_1,\cdots ,{\mathbf{f}}_{\mathrm{J}}\right)$, $\mathbf{F}$ is called the factor graph matrix. The two matrices are related by ${\mathbf{f}}_j={\mathbf{V}}_j{\mathbf{V}}_j^T$.

The factor graph matrix that represents the system in Figure 1 is given by,

$$\mathbf{F}=\left[\begin{array}{cccccc}1& 1& 1& 0& 0& 0\\ 1& 0& 0& 1& 1& 0\\ 0& 1& 0& 1& 0& 1\\ 0& 0& 1& 0& 1& 1\end{array}\right]$$E3

and the factor graph itself is depicted in Figure 2 where every circle represents a user (so-called variable node) and every block represents a subcarrier (so-called function node).

Figure 2.

The matrix, $\mathbf{F}$, can be translated into a factor graph. The encoder of the SCMA system illustrated in Figure 1 is represented by this factor graph.

Thus, the matrix $\mathbf{F}$ is related to the codeword ${\mathbf{x}}_j^{\left(m\right)}$, in Eq. (1), by the fact that the structure of $\mathbf{F}$ defines where zeros are located in the codebook from which the codeword ${\mathbf{x}}_j^{\left(m\right)}$ is selected.

As to the SCMA codebook design, it is considered as a joint optimization problem which objective is to find both the optimum user-to-RE mapping matrices ${\mathcal{V}}^{\ast }$ and the optimum multi-dimensional constellation ${\mathcal{C}}^{\ast }$, hence, this problem can be defined as,

$${\mathcal{V}}^{\ast },{\mathcal{C}}^{\ast }=arg\underset{\mathcal{V},\mathcal{C}}{max}D\left(\varphi \left(\mathcal{V},\mathcal{C};J,M,N,K\right)\right)$$E4

where $D$ is a design criterion and $\varphi$ is the SCMA system as it was described above. However, the SCMA system must be designed under the assumption that $J$ users are simultaneously connected, that is the system is fully loaded. In this case, the number of users is equal to the number of possible $N$-combinations among the $K$ available REs, i.e. $J=\left(\begin{array}{c}K\\ N\end{array}\right)$. Hence, there is only one possible optimal mapping matrix solution.

Finding the optimum multi-dimensional constellation is still complex, one way to simplify this optimization problem is to divide it into several subproblems [4]. Hence, the multi-stage design of SCMA codebook is conducted in three main steps:

1. Firstly a constellation, ${\mathit{C}}_{\mathit{mc}}$, composed of $M$ words of size $N$ is designed, ${\mathit{C}}_{\mathit{mc}}$ is called the mother constellation,

2. The mother constellation is considered as a seed from which user-specific multi-dimensional constellations are generated, this requires to design user-specific transformation matrices, ${\mathbf{T}}_j$,

3. The combination of the above two steps gives a set of $J$ matrices of size $M\times N$, the mapping matrix is employed to generate, $\mathcal{C}$, the set of $J$ codebooks.

Taking into consideration the above-mentioned remarks, namely the uniqueness of the optimal solution for the mapping matrix and the multi-stage solution for the multi-dimensional constellation design, Eq. (3) can be rewritten as,

$$\left\{{\mathbf{T}}_j^{\ast }\right\},{\mathit{C}}_{\mathit{mc}}^{\ast }=arg\underset{\left\{{\mathbf{T}}_j\right\},{\mathbf{C}}_{\mathit{mc}}}{max}D\left(\varphi \left({\mathcal{V}}^{\ast },\left\{{\mathbf{T}}_j{\mathit{C}}_{\mathit{mc}}\right\};J,M,N,K\right)\right)$$E5

such that the $j^{\mathrm{th}}$ codebook is calculated by,

$${\mathit{C}}_j={\mathbf{V}}_j^{\ast }{\mathbf{T}}_j^{\ast }{\mathit{C}}_{\mathit{mc}}^{\ast }.$$E6

In the following parts of this section, and inspired by the codebook design procedure illustrated in Figure 3, we present the major keys to design the mother constellation and the appropriate transformation operators.

Figure 3.

A block diagram that illustrates the different steps which are conducted to design a SCMA codebook.

3.2 Mother constellation design

The codebook of user $J$ must be composed of $M$ codewords since it encodes ${log}_2\left(M\right)$ bits, each codeword has $N$ non-zero elements. Hence, we start by designing a mother constellation matrix of $N$ rows and $M$ columns. Each row among the $N$ ones represents a dimension among the $N$ dimensions of the constellation. On the other hand, the $m^{\mathrm{th}}$ column is a multi-dimensional point among the $M$ multi-dimensional points of the constellation. The objective of the designing process is to guarantee a sufficiently good distance among all the points in the set $\mathcal{C}$, that is keeping the points of the multi-dimensional constellation sufficiently far from each others such that they can be separated and decoded at the receiver. Consequently, the mother constellation must own a good distance profile. However, this requires to define how the distance between two multi-dimensional points is measured, this fundamentally defines the criterion $D$ in eq. (4). Hereafter, the interested reader can find a list of the most employed distance definitions in the state of the art.

3.2.1 Euclidean distance

The Euclidean distance between two constellation points, ${\mathbf{x}}_i^{\left(u\right)}$ and ${\mathbf{x}}_j^{\left(m\right)}$, $1\le u\le M$, $1\le m\le M$, of user $i$ and $j$ respectively, $1\le i\le J$, $1\le j\le J$, is calculated by,

$${\mathrm{d}}_E\left({\mathbf{x}}_j^{\left(m\right)},{\mathbf{x}}_i^{\left(u\right)}\right)=\parallel {\mathbf{x}}_j^{\left(m\right)}-{\mathbf{x}}_i^{\left(u\right)}\parallel$$E7

A classic design criterion is the minimum Euclidean distance of a multi-dimensional constellation [5, 6], it is defined as,

$${\mathrm{d}}_E^{\left(min\right)}=\underset{\begin{array}{c}1\le u,m\le M\\ 1\le i,j\le J\end{array}}{min}\left\{d_E\left({\mathbf{x}}_j^{\left(m\right)},{\mathbf{x}}_i^{\left(u\right)}\right)\right\}$$E8

This criterion is more useful for evaluating the design of ${\mathit{C}}_{\mathit{mc}}$ when all users are observing the same fading channel coefficients over their REs.

3.2.2 Euclidean kissing number

The key here is to count the number of distinct constellation point pairs which are separated by an Euclidean distance which is equal to the minimum Euclidean distance between any two points of the multi-dimensional constellation.

3.2.3 Product distance

The product distance between two $N$-dimensional complex constellation points, ${\mathbf{x}}_j^{\left(m\right)}={\left(x_{j,1}^{\left(m\right)},\cdots ,x_{j,N}^{\left(m\right)}\right)}^T$ and ${\mathbf{x}}_i^{\left(u\right)}={\left(x_{i,1}^{\left(u\right)},\cdots ,x_{i,N}^{\left(u\right)}\right)}^T$, is expressed as,

$${\mathrm{d}}_P\left({\mathbf{x}}_j^{\left(m\right)},{\mathbf{x}}_i^{\left(u\right)}\right)=\prod _{\begin{array}{c}1\le n\le N\\ x_{j,n}^{\left(m\right)}\ne x_{i,n}^{\left(u\right)}\end{array}}\mid x_{j,n}^{\left(m\right)}-x_{i,n}^{\left(u\right)}\mid$$E9

The minimum product distance of a multi-dimensional constellation is given by,

$${\mathrm{d}}_P^{\left(min\right)}=\underset{\begin{array}{c}1\le u,m\le M\\ 1\le i,j\le J\end{array}}{min}\left\{d_P\left({\mathbf{x}}_j^{\left(m\right)},{\mathbf{x}}_i^{\left(u\right)}\right)\right\}$$E10

This criterion is preferred when evaluating the design of ${\mathit{C}}_{\mathit{mc}}$ in strong fading channel case, i.e., when channel coefficients over employed subcarriers are different.

3.2.4 Product kissing number

It is the number of distinct constellation point pairs with product distance equal to the minimum product distance.

To understand why SCMA performs well, the concept of shaping gain was introduced, the idea is to measure how the inherent shape of a multi-dimensional constellation, i.e. possessing additional dimensions in each constellation point or additional degrees of freedom, results in enhancing the distancing property of the SCMA constellation. We can assume that increasing the shaping gain means enhancing the overall system performance. The shaping gain is calculated by the ratio of the minimum distance between the points of multi-dimensional constellation to the minimum distance between the points of an one-dimensional one. The two constellations must have the same total power distributed on the same number of points. For instance, the authors in [5, 7] proposed 4-point two-dimensional mother constellation. The quadrature phase shift keying constellation is chosen as the reference one-dimensional constellation, the resulting shaping gain, which is calculated based on the Euclidean distance, is 1.25 dB.

Several new methods to design the SCMA mother constellation were proposed in the literature. In the following paragraphs, an overview of some interesting ones is presented, for each method the design criterion and the employed distance definition are highlighted.

The Euclidean distance will be intuitively the first to be used. One approach could be to fix a minimum Euclidean distance between any two points of the multi-dimensional constellation and to optimize another property, for instance the average constellation energy was minimized in [5], the resulting mother constellation is called the $M$-Beko. In [6], the authors proposed the $M$-Peng scheme which fixes the average energy and tries to maximize the minimum Euclidean distance between any two points of the alphabet.

Several research works aimed to reduce the number of superposing constellation points over each subcarrier or dimension as shown in Figure 4, however the users are distinct on other dimensions which will allow us to efficiently decode the codewords of each one among them [8, 9, 10, 11]. This type of mother constellation is described as a low-projection one since it virtually reduces the codebook size from $M$ into $M_p$ where $M_p$ is the size of the low-projected constellation. This leads to a further complexity reduction since the later is directly related to the effective codebook size, for instance, we can reduce the MPA complexity to $M_p^{d_f}$ instead of $M^{d_f}$. The low-projection approach is generally associated to the product distance criterion which has to be carefully adjusted to enhance the performance in the low signal-to-noise ratio (SNR) zone without compromising the performance in the high SNR one.

Figure 4.

Low-projection constellation: An example of QAM SCMA constellation points of size $M=4$ with two non-zero REs, labeled based on gray coding. First step rotates the constellations to ensure a maximum product distance between symbols which enhances the detection process. The second step could better reduce the complexity of the receiver since some constellation points collide over each RE, for instance the constellation points corresponding to $00$ and $11$ in the M-sized constellation collide over the first subcarrier, however, they have maximum distance over the second one which makes them separable using $M_p$-QAM constellation while $M_p\le M$.

The design of constellations or code dictionaries is well studied in the state-of-the-art, we can mention, for example, digital modulation, CDMA, channel and source coding. This rich literature inspired some designs of multi-dimensional constellations. For instance, the authors in [9] proposed the T $M$ QAM SCMA codebook whose design is based on the quadrature amplitude modulation (QAM). The idea is to design first two $N$-dimensional real constellations, then the $N$-dimensional complex constellation is conceived by applying a shuffling method on the Cartesian product of these $N$-dimensional real points. The optimization process is concluded by a rotation operation which aims at maximizing the minimum product distance of multi-dimensional constellation. The $M$ LQAM scheme in [10] is a hybrid one between the shuffling method and the low-projection constellation approach. All the above-presented mother constellation designs did not take into consideration the wireless channel characteristics. For instance, the research work in [12, 13] derived a design criterion from cutoff rate of MIMO systems when the channel is assumed to be Rayleigh fading, the conceived constellation for SCMA systems is called $M$-Bao. In fact, the $M$ multi-dimensional points of the T $M$ QAM, $M$ LQAM and $M$-Bao are based on the $M$ corners of a ${log}_2\left(M\right)$-dimensional hyper-cube. This inspired the authors in [14] to consider that the solution of the optimization problem in (4) is possible through an optimization of rotation angles of a hyper-cube, this method is denoted as $M$ HQAM. Analytical analysis showed that the complexity of MPA decoder is reduced from $M^{d_f}$ to ${\left({log}_2\left(M\right)\right)}^{d_f}$. Two examples of 2-dimensional mother constellations with 4-codewords are illustrated in Table 1 and Figure 5, we hope that this will help the reader to understand the structure of a mother constellation.

Codeword $m$	T4QAM		4LQAM
	$x_1^{\left(m\right)}$	$x_2^{\left(m\right)}$	$x_1^{\left(m\right)}$	$x_2^{\left(m\right)}$
1 (00)	$+\frac{3}{\sqrt{10}}$	$+\frac{1}{\sqrt{10}}$	$-\frac{\sqrt{2}}{2}$	$-\frac{\sqrt{2}}{2}i$
2 (01)	$-\frac{1}{\sqrt{10}}$	$+\frac{3}{\sqrt{10}}$	$-\frac{\sqrt{2}}{2}$	$+\frac{\sqrt{2}}{2}i$
3 (10)	$+\frac{1}{\sqrt{10}}$	$-\frac{3}{\sqrt{10}}$	$+\frac{\sqrt{2}}{2}$	$-\frac{\sqrt{2}}{2}i$
4 (11)	$-\frac{3}{\sqrt{10}}$	$-\frac{1}{\sqrt{10}}$	$+\frac{\sqrt{2}}{2}$	$+\frac{\sqrt{2}}{2}i$

Table 1.

This table presents T4QAM [9] and 4LQAM [10] mother constellations (4-codewords with 2 non-zeros dimensions) where $x_n^{\left(m\right)}$ belongs to dimension $n$, i.e. $x_n^{\left(m\right)}$ is the $n^{\mathrm{th}}$ entry of the $m^{\mathrm{th}}$ codeword $m$.

Figure 5.

Two examples of 2-dimensional mother constellations, namely T4QAM [9] and 4LQAM [10], each one is composed of 4-codewords: (a) the one-dimensional constellation of T4QAM as projected on the first dimension, (b) the one-dimensional constellation of T4QAM as projected on the second dimension, (c) the one-dimensional constellation of 4LQAM as projected on the first dimension and (d) the one-dimensional constellation of 4LQAM as projected on the second dimension.

Most of the above multi-dimensional constellations assume that the complex symbols can be randomly selected. Some propositions try to relax constraints on the research space by placing the constellation points of each dimension on multi-radius concentric rings [10, 15, 16, 17]. In [10], the symbols of each low-projection complex dimension are selected to form a $M$-point circular constellation, the $M$ CQAM is based on the signal space diversity for MIMO systems over Rayleigh fading channels and results in a complexity reduction from $M^{d_f}$ to ${\left(M-1\right)}^{d_f}$. The star-QAM constellation was proposed for digital modulation with the aim of being capable of flexibly adapting the ratios of multi-radius concentric rings. This approach was extended to multi-dimensional SCMA codebook design [15, 16]. The idea is to construct the first dimension of mother constellation from a star-QAM constellation of size $M$, afterwards, the following dimensions are deduced by applying some operations, for instance scaling and permuting, on the first dimension. The parameters of these operations are calculated through computer search which opens the door to designing constellations with large size and/or high dimension. An example of a constellation designed with this approach is represented in Figure 6. In [16], it was proposed to evaluate their proposition by directly applying the design criterion on the generated codewords of all users, contrary to other methods where it is only the mother constellation which was evaluated. The applied optimization criterion is the pairwise error probability between any two transmitted codewords ${\mathbf{x}}^{\left(1\right)},{\mathbf{x}}^{\left(2\right)}$ which is given by,

Figure 6.

A SCMA codebook of size $M=4$ and sparsity degree $N=2$ can be designed, for instance, based on a four-rings star-QAM mother constellation. Here, $\alpha$ and $\beta$ are 2 reel design parameters.

$$\mathbb{P}\left({\mathbf{x}}^{\left(1\right)},{\mathbf{x}}^{\left(2\right)}|\mathbf{H}\right)=Q\left(\sqrt{\frac{\parallel \mathbf{H}\left({\mathbf{x}}^{\left(1\right)}-{\mathbf{x}}^{\left(2\right)}\right){\parallel }^2}{2N_0}}\right).$$E11

where $\mathbf{H}$ is the uplink channel matrix of SCMA system as defined in Eq. (1).

In [17], each dimension of the mother constellation belongs to a ring such that the $M$ complex points forms a uniformly spaced phase shift keying (PSK) constellation. Several dimensions mean several PSK rings with different radius values, hence the multi-dimensional constellation is an amplitude and phase shift keying (APSK) constellation. In some applications, the PSK rings outperform square shaped QAM constellation since they provide a limited peak of power. The authors proposed a multi-stage optimization, the coded modulation capacity is employed as a design criterion for the first dimension of the mother constellation, then the other ones are optimized using permutations.

Once the mother constellation is designed, optimized and evaluated based on one of the above-presented design criteria, the applied transformations, which are used to generate the $J$ codebooks, must be designed to preserve the characteristics of the mother constellation.

3.3 Transformation operators design

The design procedure of SCMA codebooks was introduced in Figure 3. First, the $N\times M$ mother constellation, ${\mathit{C}}_{\mathit{mc}}$, is designed, then the sparse codebook of SCMA user $j$ is constructed by applying a set of operators, ${\mathbf{T}}_j$, on ${\mathit{C}}_{\mathit{mc}}$, and a mapping matrix, ${\mathbf{V}}_j$, as seen in eq. (5). Transforming a complex constellation can be conducted based on typical operations such as complex conjugate, rotation operator, interleaving and vector permutation. Several operators can be combined in some cases. Hence, the transformation operators must be chosen carefully such that the good characteristics of the mother constellation are conserved, their design was recently investigated [16, 17, 18, 20].

The Euclidean distance is widely employed as a design criteria of the mother constellation. However, preserving its distancing property is possible by applying unitary rotation matrices [5, 6, 7, 8, 9, 19]. In this case, it is possible to merge the mapping operation and the transformation one to mold a new transformed factor graph matrix, ${\mathbf{F}}_T$. An example of a transformed factor graph matrix is expressed as,

$${\mathbf{F}}_T=\left[\begin{array}{cccccc}0& {\phi }_1& {\phi }_2& 0& {\phi }_3& 0\\ {\phi }_2& 0& {\phi }_3& 0& 0& {\phi }_1\\ 0& {\phi }_2& 0& {\phi }_1& 0& {\phi }_3\\ {\phi }_1& 0& 0& {\phi }_3& {\phi }_2& 0\end{array}\right]$$E12

where ${\phi }_1=e^{j{\theta }_1},{\phi }_2=e^{j{\theta }_2}\text{and}{\phi }_3=e^{j{\theta }_3}$. Traditionally, ${\theta }_1=0,{\theta }_2=\frac{\pi }{3},\text{and}{\theta }_3=\frac{2\pi }{3}$. In this circumstance, the codebook of user 1, for instance, is calculated based on the following mapping and transformation matrices,

$$\begin{array}{l}{\mathbf{V}}_1=\left[\begin{array}{cc}0& 0\\ 1& 0\\ 0& 0\\ 0& 1\end{array}\right]\end{array}\text{and}\begin{array}{l}{\mathbf{T}}_1=\left[\begin{array}{cc}{e}^{j{\theta }_2}& 0\\ 0& e^{j{\theta }_1}\end{array}\right]\end{array}.$$

It is worth noting that not only non-zero entries in each row of ${\mathbf{F}}_T$ are different but also those in each column, this property is called the Latin criterion. This means that the power variation and dimensional dependency can be controlled at the same time without compromising the Euclidean distance profile of the multi-dimensional mother constellation [8, 19]. Figure 7 illustrates an example of SCMA system with 6 users ($J=6$), their codebooks of size 4 ($M=4$) are generated based on T4QAM mother constellation (which is described in Table 1) by employing unitary rotation matrices as described in eq. (11). This figure depicts how the constellation of each user is projected on each one between its associated two REs ($N=2$). More details on these codebooks are given in Appendix A.

Figure 7.

An example of SCMA system with 6 users ($J=6$), their codebooks of size 4 ($M=4$) are generated based on T4QAM mother constellation by applying unitary rotation matrices, as described in eq. (11). This figure depicts how the constellation of each user is projected on each one between its associated two REs ($N=2$).

Multi-user codebooks generation can be further refined by optimizing computer-designed rotation matrices instead of the unitary rotation ones [12]. Furthermore, if the communication channel is assumed to be known, its phases can be exploited to extract random rotation angles which are used to generate the codebooks from the mother constellation. The authors in [18] combined the SCMA design with a form of codebook encryption which can ensure the link with low complexity. The rotation operations are not the only ones that can be employed. In [20], the transformation operator is designed based on a permutation set which is optimized to improve the detection reliability of the first decoded user, this largely improves the performance of SCMA receiver. The proposed design criterion tries to maximize the sum of distances among codewords which are multiplexed on the same RE (sum of distances per dimension). The factor graph matrix, $\mathbf{F}$, defines the positions of non-zero elements of each user which are assumed to be fixed in the majority of SCMA designs as explained in subsection 3.1. One way to design transformation operator is to differentiate the non-zero locations according to the values of transmitted data bits which is considered as a permutation-based SCMA scheme [21]. This permutation approach does not suffer from a complexity overhead when compared to traditional one, however spectral efficiency does improve. This effort was extended by combining the matrix permutation and rotation operations to define the transformation operator as in [15, 16].

Nevertheless, the objective is to minimize the rate of wrongly detected bits which is also called bit error rate (BER). For a given codeword error rate the BER depends on how codewords are labeled, hence it is obvious that choosing the appropriate labeling is an another aspect to be studied. In [17], the labeling was optimized to adjust the slope of the extrinsic information transfer (EXIT) chart.

The influence of the codebook design on the performance of a SCMA system is confirmed through simulations. Figure 8 depicts the BER as a function of the SNR with different codebooks through Rayleigh fading channel. The star-QAM based SCMA design outperforms the other ones.

Figure 8.

BER as a function of SNR for SCMA system with different codebook designs: The number of orthogonal REs is 4, the number of users is 6, and the channel fading is assumed to be Rayleigh distributed.

4. SCMA decoder design

It is worth mentioning that the SCMA encoder and decoder are two blocks among other ones at, respectively, the transmitter and receiver as explained in the block diagram illustrated in Figure 9. At the receiver side, the SCMA codewords must be segregated or decoded, this operation is preceded by the OFDM demodulation and the channel estimation, and followed by the deinterleaving and channel decoding.

Figure 9.

This diagram illustrates the different essential blocks of the transmitter and receiver of SCMA system.

At the transmitter, the bit to codeword mapping for each user is followed by the superimposition of the $J$ mapped codewords which are selected from one of the above presented SCMA codebooks. At the receiver, the SCMA decoder aims to separate the superimposed codewords despite that several users are occupying the same REs as described by the factor graph matrix. Most existing mechanisms employed for SCMA decoders are based on MPA or one of its variations, or its combination with other methods. In this section, we will present the basics of SCMA decoding.

4.1 Message passing algorithm

4.1.1 Traditional MPA

MPA is an iterative method based on passing some messages among concerned nodes. The nodes are the users, which are also considered as the variables nodes (VNs), and the subcarrier (or REs), which are also considered as the function nodes (FNs), and the massages are the extrinsic information among nodes, this mechanism is illustrated in Figure 2. Tha idea is that each FN calculates its outgoing message to a given VN depending on the incoming messages received from the reminder of VNs. The later ones will play the reciprocal role, that is each VN will reply by sending a message which is computed based on the received messages from the rest of FNs. This exchange among all the edges, i.e. all VNs and all FNs, is repeated at each iteration. After a given number of iterations, the bits of each user are estimated through the log-likelihood-rates (LLRs) of each coded bit. The MPA method is shown in Algorithm 1 and is based on three main steps: initialization, iterative message passing along edges and decision making.

Algorithm 1: Message Passing Algorithm.

Input:$\mathbf{y},N_0,{\mathit{C}}_j,h_j,j=1,\cdots ,J,N_{\text{iter}}$.

Estimation of the bits which were transmitted by each user. Definitions.

Users are represented by VNs, subcarriers are represented by FNs,

$$\mathcal{U}\left(k\right)=\left\{\mathrm{all}\text{the}\mathrm{VNs}\text{which}\mathrm{are}\text{connected}\text{to}{\mathrm{FN}}_k\right\},k=1,\cdots ,K,$$

$$\mathcal{R}\left(j\right)=\left\{\mathrm{all}\text{the}\mathrm{FNs}\text{which}\mathrm{are}\text{connected}\text{to}{\mathrm{VN}}_j\right\},j=1,\cdots ,J.$$

Step 1: Initialization.

Initially, each user expects to equally receive any codeword among the $M$ ones:

$$V_{j\to k}^0\left({\mathbf{x}}_j^{\left(m\right)}\right)=\mathbb{P}\left({\mathbf{x}}_j^{\left(m\right)}\right)=\frac{1}{M},j=1,\cdots ,J,k\in \mathcal{R}\left(j\right)$$

Step 2: Extrinsic information exchange among VNs and FNs

$$t\le N_{\text{iter}}$$

1. The message to be sent from ${\mathrm{FN}}_k,k=1,\cdots ,K,$ to ${\mathrm{VN}}_j,j\in \mathcal{U}\left(k\right)$, for each codeword ${\mathbf{x}}_j^{\left(m\right)}\in {\mathit{C}}_j,m=1,\cdots ,M$, is computed by,

   $$U_{k\to j}^t\left({\mathbf{x}}_j^{\left(m\right)}\right)=\sum _{{\mathbf{x}}_i^{\left(m\right)}\mid i\in \mathcal{U}\left(k\right)\backslash j}exp\left\{-\frac{1}{N_0}\parallel y_k-\sum _j{h}_{j,k}{x}_{j,k}^{\left(m\right)}{\parallel }^2\right\}\prod _{i\in \mathcal{U}\left(k\right)\backslash j}{V}_{i\to k}^{t-1}\left({\mathbf{x}}_i^{\left(m\right)}\right)$$

2. The message to be sent from ${\mathrm{VN}}_j,j=1,\cdots ,J$ to ${\mathrm{FN}}_k,k\in \mathcal{R}\left(j\right)$, for each codeword ${\mathbf{x}}_j^{\left(m\right)}\in {\mathit{C}}_j,m=1,\cdots ,M$, is calculated as,

$$V_{j\to k}^t\left({\mathbf{x}}_j^{\left(m\right)}\right)=\frac{{\prod }_{i\in \mathcal{R}\left(j\right)\backslash k}{U}_{i\to j}^{t-1}\left({\mathbf{x}}_j^{\left(m\right)}\right)}{{\sum }_{{\mathbf{x}}_j^{\left(l\right)}\in {\mathbf{C}}_j}{\prod }_{i\in \mathcal{R}\left(j\right)\backslash k}{U}_{i\to j}^{t-1}\left({\mathbf{x}}_j^{\left(l\right)}\right)}.$$

It is essential to normalize this message in order to guarantee the numerical stability of MPA.

Step 3: Received bits estimation

1. The posteriori probability of each codeword for each user is represented by,

   $$\mathbb{P}\left({\mathbf{x}}_j^{\left(m\right)}\right)=\prod _{k\in \mathcal{R}\left(j\right)}{U}_{k\to j}^{N_{\text{iter}}}\left({\mathbf{x}}_j^{\left(m\right)}\right),m=1,\cdots ,M,j=1,\cdots ,J.$$

2. Log-Likelihood-Rate for each coded bit, $b_i,1\le i\le {log}_2\left(M\right)$, is given by,

   $$\mathrm{LLR}\left(b_i\right)=log\left(\frac{\mathbb{P}\left(b_i=0\right)}{\mathbb{P}\left(b_i=1\right)}\right)=log\left(\frac{{\sum }_{\left\{{\mathbf{x}}_j^{\left(m\right)}\in {\mathbf{C}}_j|b_i=0\right\}}\mathbb{P}\left({\mathbf{x}}_j^{\left(m\right)}\right)}{{\sum }_{\left\{{\mathbf{x}}_j^{\left(m\right)}\in {\mathbf{C}}_j|b_i=1\right\}}\mathbb{P}\left({\mathbf{x}}_j^{\left(m\right)}\right)}\right)$$

3. Finally, the value of each LLR is employed to decide on the corresponding bit as following,

   $${\widehat{b}}_i=\left\{\begin{array}{c}1\text{if}\mathrm{LLR}\left(b_i\right)\le 0\\ 0\text{otherwise}.\end{array}\right.$$

4.1.2 Variations of MPA

Despite being a referent decoder for SCMA, the complexity evaluation of MPA reveals that it relies on a large number of exponential calculus which are of high complexity. With the challenge to reduce this complexity and to fit with critical requirements of future wireless networks, several variations of MPA were proposed, among them we present here, the Max-Log-MPA and Log-MPA methods [22].

$⊛$Max-Log-MPA: It is a simplified version of MPA based on a mathematical simplification which approximates the logarithm of a sum of exponential operations into a maximum operation. The key purpose is to move the iterative decoding process into logarithmic domain which eliminates the exponential terms in MPA by employing the simplified formula of Jacobean logarithm,

$$log\left(exp\left(a_1\right)+\dots +exp\left(a_n\right)\right)\approx max\left(a_1,\dots ,a_n\right)$$E13

Thus, passing numerous messages from FNs to VNs, and vice versa, will be very less expensive in term of complexity. Based on (12), the expression of $\mathrm{LLR}\left(b_i\right)$ presented in Algorithm 1 is modified as follows,

$$\mathrm{LLR}\left(b_i\right)=\underset{\left\{{\mathbf{x}}_j^{\left(m\right)}\in {\mathbf{C}}_j|b_i=0\right\}}{max}\left(log\left(\mathbb{P}\left({\mathbf{x}}_j^{\left(m\right)}\right)\right)\right)-\underset{\left\{{\mathbf{x}}_j^{\left(m\right)}\in {\mathbf{C}}_j|b_i=1\right\}}{max}\left(log\left(\mathbb{P}\left({\mathbf{x}}_j^{\left(m\right)}\right)\right)\right)$$E14

$⊛$Log-MPA: The approximation of the Jacobean logarithm formula as presented in (12) makes the Max-Log-MPA a sub-optimal solution and results in a performance degradation. To mitigate this issue, a correction term was added by using another Jacobean logarithm formula. The adopted approximation is given by,

$$log\left(exp\left(a_1\right)+\dots +exp\left(a_n\right)\right)=a_j+log\left(1+\sum _{i\in \left\{1\dots n\right\}\backslash j}exp\left(-|a_j-a_i|\right)\right)$$E15

where $a_j=max\left(a_1,\dots ,a_n\right)$. Hence, the LLRs are further updated to be as below, rather than as in (13),

$$\begin{array}{l}\mathrm{LLR}\left(b_i\right)=\left[\underset{\left\{{\mathbf{x}}_j^{\left(m\right)}\in {\mathbf{C}}_j|b_i=0\right\}}{max}\left(log\left(\mathbb{P}\left({\mathbf{x}}_j^{\left(m\right)}\right)\right)\right)+\right.\\ log\left.\left(1+\sum _{m^{\prime }\in \left\{1\dots M\right\}\backslash m}exp\left(-|log\left(\mathbb{P}\left({\mathbf{x}}_j^{\left(m\right)}\right)\right)-log\left(\mathbb{P}\left({\mathbf{x}}_j^{\left(m^{\prime }\right)}\right)\right)|\right)\right)\right]\\ -\left[\underset{\left\{{\mathbf{x}}_j^{\left(m\right)}\in {\mathbf{C}}_j|b_i=1\right\}}{max}\left(log\left(\mathbb{P}\left({\mathbf{x}}_j^{\left(m\right)}\right)\right)\right)+\right.\\ \left.\log \left(1+\sum _{m^{\prime }\in \left\{1\dots M\right\}\backslash m}exp\left(-|log\left(\mathbb{P}\left({\mathbf{x}}_j^{\left(m\right)}\right)\right)-log\left(\mathbb{P}\left({\mathbf{x}}_j^{\left(m^{\prime }\right)}\right)\right)|\right)\right)\right]\end{array}$$E16

The performance of the above-presented variations of MPA, namely MPA, Log-MPA and Max-Log-MPA, were evaluated, Figure 10 depicts the BER as a function of SNR through Rayleigh fading channel. The results show that the performance of Log-MPA is near-optimum when compared to that of MPA. The same is not valid for Max-Log-MPA, this can be explained by the correction term that was added to Log-MPA which obviously results in a performance compensation. On the other hand, the performance degradation of Log-MPA and Max-Log-MPA, due to the approximation used for each method, can be neglected in the high SNR zone. However, the Max-Log-MPA is still useful since it requires less computational effort when compared to Log-MPA which is still sufficiently complex to be considered challenging for energy-sensitive applications. It worth mentioning that reducing the computation complexity of the above-mentioned decoding methods is possible though reducing the value of $d_f$ at the expense of largely constraining the codebook design.

Figure 10.

BER as a function of SNR of MPA, log-MPA and MAX-log-MPA variations: The number of orthogonal REs is 4, the number of users is 6, and the channel fading is assumed to be Rayleigh distributed.

Generally speaking, the complexity of MPA is intimately depending on the number of iterations which is usually one of its fixed parameters. This is not ideal since, on one hand, increasing the number of iterations will considerably increase the complexity, and on the other hand, not sufficiently iterating will lead to performance degradation. Hence, finding the near-optimal number of iterations is very useful. The performance of MPA as a function of SNR for different number of iterations is shown in Figure 11 when the channel is assumed to be Gaussian or Rayleigh distributed. It is observed that the BER is lesser when the number of iterations increases under the two channel assumptions, nevertheless, beyond a certain limit, the performance improvement hits an upper bound. The same conclusions are valid for Log-MPA and Max-Log-MPA as reported in [22]. Therefore, a good compromise is to set the number of iterations to 4. Another approach is to supervise the convergence rate such that the number of iterations can be adjusted accordingly, the flexible number of iterations can be powerful when the convergence rate is efficiently measured.

Figure 11.

Evaluation of the number of iterations on MPA performance: The number of orthogonal REs is 4, the number of users is 6, and the channel fading is assumed to be AWGN and Rayleigh distributed.

5. Conclusions

In this Chapter, we presented the structure and basic principles of SCMA. Then, SCMA encoder and decoder designs were reviewed through their most known techniques. A simulations-based comparison among different existing approaches for codebook design as well as for signal decoding was conducted.

To better illustrates SCMA mapping, a numerical example of complete SCMA codebooks, as depicted in Figures 5 and 7, is provided in the following (Figure 12).

Figure 12.

The 2-dimensional codebooks with 4-codewords, generated for $J=6\mathit{\text{users}}$, as described in Figure 7.

Nomenclature

BER	Bit error rate
BS	Base station
CDMA	Code-division multiple access
EXIT	Extrinsic information transfer
FN	Function node
LLR	Log-likelihood-rate
MPA	Message passing algorithm
NOMA	Non-orthogonal multiple access
OMA	Orthogonal multiple access
PSK	Phase shift keying
QAM	Quadrature amplitude modulation
RE	Resource elements
SCMA	Sparse code multiple access
SNR	Signal-to-noise ratio
VN	Variables node