# Learned Provability Likelihood
for Tactical Search††thanks:  Supported by the Czech Science Foundation
project 20-06390Y

Thibault Gauthier Czech Technical University in Prague, Prague, Czech Republic
<EMAIL_ADDRESS>
###### Abstract

We present a method to estimate the provability of a mathematical formula. We
adapt the tactical theorem prover TacticToe to factor in these estimations.
Experiments over the HOL4 library show an increase in the number of theorems
re-proven by TacticToe thanks to this additional guidance. This amelioration
in performance together with concurrent updates to the TacticToe framework
lead to an improved user experience.

##  1 Introduction

We take inspiration from the instinct shown by mathematicians when attempting
to prove a theorem. An important choice to make in their situation is whether
to continue exploring a certain line of work or to switch to another approach
entirely. The quality of this decision is influenced greatly by one’s
experience with other proof attempts. Our aim is to integrate such feedback to
improve automation in interactive theorem provers (ITPs). In the majority of
ITPs, most proofs are build using tactics in a goal-oriented manner. A tactic
is a procedure that takes as input a goal $g$ (a sequent in HOL4) and returns
a list of goals whose conjunction implies $g$. We can classify HOL4 tactics
into four categories. Solvers attempts to prove the goal using general or
domain-specific knowledge (e.g. $\mathit{metis\\_tac}$ [11] for first-order
logic). Rewrite tactics modify subterms of a goal by applying rewrite rules
constructed from proven equalities, Induction tactics (e.g. $\mathit{Induct}$)
split the goal into multiple cases (typically a base case and an inductive
case). Kernel-level tactics (e.g. $\mathit{exist\\_tac}$) allow for more
refined control of the proof state. Given these tactics, it is possible to
create an automated prover that searches for the proof of a starting goal by
predicting suitable tactics for each intermediate goal. In the following, we
refer to such automation as a tactic-based automated theorem prover (ATP).
Multiple tactic-based ATPs have been developed in the course of the last five
years and are now one of the most effective [9, 5] general proof automation
available in an ITP. However, none of the tactic-based ATP so far take into
account the provability of the goals produced by each tactic. Therefore, in
this project, a tree neural network (TNN) is taught a function estimating the
provabilty of goals in HOL4 [15]. This value function produces feedback
signals called rewards that further guide the search algorithm of the tactic-
based ATP TacticToe [9].

#### Related Works

The most successful related tactic-based ATPs are Tactician [5] for Coq [4],
Pamper [13] for Isabelle/HOL [16], and HOList [3] for HOL Light [10]. The
Tactician is very user-friendly. In particular, it is the only one that can
record tactic calls on the fly. It uses the $k$-nearest neighbor algorithm for
tactic selection as TacticToe does. However, it does not predict argument
theorems independently of tactics. In Pamper, the policy predictors are
decision trees trained on top of human-engineered features. In HOList, the
prediction effort is concentrated on learning the policy for a few selected
tactics and their arguments (theorems) using deep reinforcement learning. A
related field of research is machine learning for first-order ATPs. The ENIGMA
[6] system for E prover gathers positive and negative clauses from successful
proof attempts. We use a similar technique to collect our training examples.
The ATP LeanCoP [12] has been trained via a reinforcement learning loop using
boosted random forest predictors. Its proof search relies on the same variant
of Monte Carlo Tree Search (MCTS) [14] as TacticToe. Nevertheless, it ignores
the goal selection issue and thus could benefit directly from the MCTS
adaptions proposed in this paper.

##  2 Monte Carlo Tree Search with Tactics

We integrate the learned provability estimator into the proof search of
TacticToe. Here is a brief summary of how the MCTS algorithm operates in the
context of tactic-based theorem proving. The algorithm starts with a list of
goals (typically a singleton) to be proven in a root node. In the selection
phase, it chooses a goal branch in the current output node and a tactic branch
(and possibly an argument branch) leading to the selection of an output node
containing the list of goals produced by the tactic. This process is repeated
until a leaf is reached. In the extension phase, the tactic $t$ selected in
the leaf is applied to its parent goal. In the case of a successful tactic
application, an output leaf is created containing the list of goals produced
by $t$. During the backup phase, a feedback signal is propagated from the
newly created leaf to the root. The gathered node rewards influence the next
selection phase. The three phases are repeated until the algorithm finds a
proof for each of the root goals, times out, or saturates. In the following,
we present the existing MCTS algorithm for TacticToe and describe ways to
improve the quality of the feedback mechanism. Figure 1 illustrates the effect
of one iteration of the improved MCTS loop on the search tree for our running
example.

$\vdash\forall n.\ 2\times\mathit{SUM}\ (n+1)\ I=n\times(n+1)$22 $\rightarrow$
23, 0.045 $\rightarrow$ 0.043$srw\\_tac\ []\ X$3, 0, 0.25$Induct$12
$\rightarrow$ 13, $8.7\times 10^{-7}\rightarrow 3.0\times 10^{-6}$, 0.5tactic
selection$asm\\_simp\\_tac\ arith\\_ss\ X$2, 0, 0.125$\vdash
2\times\mathit{SUM}\ (0+1)\ I=0\times(0+1)$6 $\rightarrow$ 7,
$0.049\rightarrow 0.18$goal selection$2\times\mathit{SUM}\ (n+1)\
I=n\times(n+1)$$\vdash 2\times\mathit{SUM}\ (\mathit{SUC}\ n+1)\
I=\mathit{SUC}\ n\times(\mathit{SUC}\ n+1)$6, $3.0\times
10^{-5}$$\mathit{rewrite\\_tac\ X}$$3\rightarrow 4$, $0.00021\rightarrow
0.23$, 0.5tactic selection$\mathit{srw\\_tac\ [arith\\_ss]\
[SUM\\_def,\ldots]}$2, 0.15, 0.25$[\mathit{numeral\\_distrib}]$3, $2.1\times
10^{-4}$, 0.5$[\mathit{MULT\\_CLAUSES}]$1 $\rightarrow$ 2, 0 $\rightarrow$
0.48, 0.25argument selection$\mathit{SUM}\ 1\ I=0$1, 0.29$2\times\mathit{SUM}\
1\ I=0$2, $3.1\times 10^{-4}$$2\times\mathit{SUM}\ (0+1)\ I=0$1, 0.95node
extension

Figure 1:  Iteration 22 of the value-guided MCTS loop on the goal
$\vdash\forall n.\ 2\times\mathit{SUM}\ (n+1)\ I=n\times(n+1)$. The term
$\mathit{SUM}\ n\ f$ stands for $\sum_{\\_}{x=0}^{x<n}f(x)$ and $I$ is the
identity function. Each node contains in the following order: the number of
visits with a possible update, the average of the rewards and the prior policy
for tactics (and arguments). The presence of an arrow after these numbers
indicates a backup update. The selection path is made bold and created nodes
are dotted. Saturated tactic (and argument) nodes and the subtree of the
inductive case are omitted. Tactics may contain the placeholder $X$ [9] to
indicate that an argument has to be provided. To avoid dividing by 0 in the
PUCT formula, all tactic (and argument) nodes are initialized with one visit
and a reward of 0. A proof is found after 427 iterations.

#### Selection Phase

Given a list of tactic $(t_{\\_}r)_{\\_}{1\leq r\leq n}$ with parent node $g$,
we can compute their PUCT [2] (Polynomial Upper Confidence Trees) score as
follows:

$PUCT(t_{\\_}r)=\mathit{AverageRewards}(t_{\\_}r)+c\times\mathit{Policy}(t_{\\_}r)\times\frac{\sqrt{\mathit{Visits}(t_{\\_}r)}}{\mathit{Visits}(g)}$

The tactic with the highest PUCT score is selected. The policy
$\mathit{Policy}$ is given by a nearest neighbor predictor trained from
supervised data consisting of goal-tactic pairs [9]. The value of
$\mathit{Policy}(t_{\\_}j)$ is experimentally chosen to be $0.5^{n+1}$ where
$n$ is the number of open tactic branches with parent node $g$ and higher
nearest neighbor score. At the start, the search is principally guided towards
nodes with higher policy. As the number of iterations increases, the search
tends to explore goals with higher reward averages more often. The exploration
coefficient $c$ decides how fast this transition happens. We choose $c$ to be
$2.0$ since this is a suitable value for guiding a goal-oriented first-order
ATP [12].

In this version of TacticToe, the theorems predicted by its nearest neighbor
algorithm are split. Given a list of predicted arguments
$x_{\\_}1,\ldots,x_{\\_}n$ and a tactic $t$ (except $\mathit{metis\\_tac}$)
that expects a list of theorems as argument, the tactic calls
$t[x_{\\_}1],\ldots,t[x_{\\_}n]$ are constructed instead of
$t[x_{\\_}1,\ldots,x_{\\_}n]$. This adds another branching layer to the tree
that functions exactly like the tactic selection layer. To simplify our
explanations in the rest of this paper, the branching occurring during
argument selection is considered to be part of tactic selection.

In previous developments of TacticToe and in other tactic-based ATPs, the
selected goal is always the first unproven goal of the output node. One issue
is that the rewards of an output node are exactly the rewards of its first
goal until it is proven. To factor the influence of other goals in the output
node rewards, each unproven goal branch now receives almost the same number of
visits. This is achieved by choosing at each iteration one of the least
visited unproven goal branches.

#### Backup Phase

There are three possible outcomes of the extension phase. If the tactic $t$
applied proves the parent goal $g$, $t$ receives a reward of 1. If $t$ fails
or induces a loop then $t$ receives a reward of 0. Otherwise, a new output
node is created and the value network is called on each of the goals. The
reward of the newly created leaf is computed by multiplying the inferred
values and backed up unchanged to $t$. Each tactic selection layer propagates
the reward of the selected tactic unchanged to its parent goal. To capture the
influence of multiple explored goal branches in the goal selection layer, we
back up the rewards through this layer in the following manner. Given a list
of goals $(g_{\\_}r)_{\\_}{1\leq r\leq n}$ composing an output node $p$ and a
selected goal $g_{\\_}i$, the reward for $p$ is given by:

$\mathit{Reward}_{\\_}k(p)=\mathit{Reward}_{\\_}k(g_{\\_}i)\times\prod_{\\_}{1\leq
r\leq n\ \wedge\ r\neq i}\mathit{AverageRewards}(g_{\\_}r)$

If a goal $g_{\\_}r$ is proven, the value of
$\mathit{AverageRewards}(g_{\\_}r)$ in the formula is overridden and set to 1.
This formula multiplies the reward of the goal $g_{\\_}i$ at iteration $k$ of
the search loop with the existing reward average $\mathit{AverageRewards}$ for
the other goals in $p$. Thus the feedback of different branches is merged
although only one branch is explored at each iteration of the loop. Overall,
$p$ receives a reward that is a lower bound estimation for its provability as
it assumes independence of its goals.

##  3 Learning Provability

We explain here how a TNN can be trained to estimate the provability of a
goal. These estimates are to be used as rewards in our improved MCTS
algorithm. We choose a TNN as our machine learning model because it performs
well on arithmetic and propositional formulas [8] as well as on Diophantine
equations and combinators [7]. In our TNN, each HOL4 operator of arity $a$ has
a neural network associated with it modeling a function from
$\mathbb{R}^{a\times d}$ to $\mathbb{R}^{d}$, where $d$ is a globally fixed
embedding size. When $a=0$, the associated neural network is a trainable
embedding (vector in $\mathbb{R}^{d}$). Networks are composed in a manner that
reflects the tree structure of a given goal $g$. They gradually construct
embeddings for sub-trees of $g$. A head network models a function from
$\mathbb{R}^{d}$ to $\mathbb{R}$ targeting a provability estimation for $g$
from an embedding for $g$. Figure 2 shows part of the computation graph
produced by a TNN on the running example.

$n+1$$I$$\mathit{SUM}$$\mathit{SUM}\ (n+1)\ I$$2$$\times$$2\times\mathit{SUM}\
(n+1)\ I$$n\times(n+1)$$=$$2\times\mathit{SUM}\ (n+1)\ I=n\times(n+1)$

Figure 2: Computation of the embedding of $2\times\mathit{SUM}\ (n+1)\
I=n\times(n+1)$ by a TNN. To simplify the diagram, the computation of the
embeddings of $1$, $2$, $n+1$, $n\times(n+1)$ are not shown. Rectangles
represent embeddings and squares represent neural networks.

.

Until now, the value function of TacticToe was uniform. It gave a reward of 1
independently of the provability of the goal produced. Thus, the search was
guided solely by a policy trained from human-written proof scripts. The lack
of negative examples in these proofs makes this dataset unsuitable for
training the value function. That is why we extract training examples from
TacticToe searches instead. To do so, we collect search trees from the
successful proof attempts. The goal nodes extracted from these trees create
our training examples with proven goals labeled positively and other goals
negatively. In order to speed up the training process, we keep at most one
example for each goal with a preference for the positive ones. We also remove
examples with large goals ($\geq 80$ operators) and select the $600$ most
visited negative examples per proof attempt. From this dataset, we train a TNN
with embedding size ($d=16$) and one layer per operator. The training is
scheduled to take 100 epochs at a learning rate of 0.08 and the batch size is
increased regularly according to the sequence $[16,24,32,48,64]$. These
parameters were optimized by experimenting with a fifth of the HOL4 library.
There, the parameters used in [8] were gradually mutated to yield higher
accuracy on HOL4 goals.

##  4 Results

We experiment on the HOL4 library included in the HOL4 repository
111https://github.com/HOL-Theorem-Prover/HOL. This library contains 168
theories about mathematical and computer science concepts such as lists,
trees, probabilities, measures and integration. During the development of HOL4
library, the proof of a theorem is usually found as an argument of one of the
following functions: store_thm,maybe_thm, Store_thm,asm_store_thm,prove or
TAC_PROOF. We introduce a hook in these functions in order to evaluate
TacticToe on their argument goal as the library is built. In this way, only
tactics, theorems and simplification sets created before a goal $g$ is proven
are available to TacticToe when attempting to prove $g$. The code for this
experiment is available at this
commit22213fbff7b94bb1a5b51881a5aeee63ffc44d3be1. Replication instructions are
given in the file src/tactictoe/EVALUATION.

After an evaluation of TacticToe with a 30 seconds timeout over 15948 theorems
of the library resulting in 8812 successful searches, 188409 examples (34021
positives and 154388 negatives) are collected. Correcting for the imbalance
between the positive and negative examples by oversampling positive examples
did not seem to improve the overall performance when experimenting with a
small part of the library. Therefore, no balancing method is applied in this
full-scale experiment. The efficiency of the learning phase is then assessed
by splitting the examples into a training set (90%) and a test set (10%).
Following the training of the TNN, we measure an accuracy of 97.5% on the
training set and 84.7% on the test set. For the final evaluation, the TNN is
retrained on all examples.

The performance of value-guided TacticToe is compared with its default version
in Table 1. All changes to the proof search algorithm proposed in this paper
are included in both versions. The only difference between the two versions is
whether a uniform or trained value function gives the reward signal. Overall,
the results show a small increase in the number of theorems re-proven. Calls
to the TNN increase the node creation time from 3.7% to 13.3% of the total
search time. Such a small footprint could not have been achieved without a
Standard ML implementation of TNNs [8]. Thus, the positive impact of learning
is not severely dampened by the neural network overhead.

| TacticToe | $\textsf{TacticToe}_{\\_}{\mathit{TNN}}$ | Combined
---|---|---|---
Standard library (15948 theorems) | 8812 (138) | 8913 (239) | 9051
Table 1:  Number of theorems in the HOL4 standard library re-proven within 30
seconds. The number of theorems re-proven by one strategy but not by the other
is shown in parentheses.

###  4.1 Proofs

Among the 239 theorems solely proven by
$\textsf{TacticToe}_{\\_}{\mathit{TNN}}$, 30 of them belong to the theory
real_topology. Two such theorems with their tactical proof are analyzed here.
Compared to the previous version of TacticToe, the proofs are now
automatically printed with the preferred style of many HOL4 users. Tactics are
written in lowercase when possible and the tacticals >> (one goal), >|
(multiple goals) compose tactics in the final proof script.

The theorem $\vdash\forall a.\ \mathit{diameter}\ \\{a\\}=0$ is re-proven in
28.2 seconds. It states that the diameter of any singleton is equal to 0. The
diameter of a set of reals $s$ is by definition $0$ if $s$ is empty and
otherwise is the supremum $\\{\mathit{abs}(x-y)\ |\ x\in s\wedge y\in s\\}$.
The proof starts by rewriting the goal with the definition of
$\mathit{diameter}$, continues by distinguishing whether $s$ is empty or not
and proves each case by calling a first-order solver and a simplification
tactic with an appropriate lemma.

⬇

rewrite_tac [diameter] >> REPEAT strip_tac >>

COND_CASES_TAC >| [metis_tac [], srw_tac [] [REAL_SUP_UNIQUE]]

The theorem $\vdash\forall f\ s.\ (\mathit{linear}\ f\wedge\mathit{subspace}\
s)\Rightarrow\mathit{subspace}\ (\mathit{IMAGE}\ f\ s)$ is re-proven in 16.7
seconds. It states that the image of a subspace by a linear function is a
subspace. A subspace $s$ is a subset of $\mathbb{R}$ that satisfies three
conditions $0\in s$, $(x\in s\wedge y\in s)\Rightarrow x+y\in s$, and $\forall
c\in\mathbb{R}.\ x\in s\Rightarrow c\times x\in s$ . The proof consists of
rewriting the goal with this definition and then solving each of the three
cases by calling $\mathit{metis\\_tac}$ with suitable premises.

⬇

srw_tac [] [subspace] >|

[metis_tac [REAL_MUL_LZERO,linear],

first_assum (X_CHOOSE_TAC ‘‘B‘‘ o MATCH_MP (LINEAR_BOUNDED)) >>

pop_assum (mp_tac o Q.SPEC ‘x‘) >> metis_tac [LINEAR_ADD],

metis_tac [LINEAR_CMUL]]

##  5 Usage

To make TacticToe more attractive to new users, tactic-goal pairs from the
HOL4 library are prerecorded. Therefore, the users can now use TacticToe right
after building HOL4 without spending multiple hours recording the data
themselves (see HOL/src/tactictoe/README). Multiple new functions relying on
the TNN trained in this paper are implemented and available at the commit
mentioned in Section 4 . To run these functions, one first need to download
the file tnn_for_tactictoe from http://grid01.ciirc.cvut.cz/~thibault/ to a
desired location path_to_foo. The function ttt_tnn runs TacticToe
${}_{\\_}\mathit{TNN}$ on a chosen goal with the advice of a TNN imported by
mlTreeNeuralNetwork.readtnn. The following commands demonstrate how to execute
ttt_tnn in an interactive session:

    load "tacticToe"; open tacticToe;
    val tnn = mlTreeNeuralNetwork.read_tnn "path_to_foo";
    load "sum_numTheory"; open sum_numTheory; open arithmeticTheory;
    set_timeout 60.0;
    ttt_tnn tnn ([],``!n. 2 * SUM (n+1) I = n * (n+1) ``);

The function confidence_tnn returns the provability estimate of a goal as
computed by the TNN in 1 to 10 milliseconds. This might encourage the user to
call TacticToe ${}_{\\_}\mathit{TNN}$ if this value becomes high on an open
goal during a manual proof attempt.

The function suggest creates partial proofs from failed proof attempts. By
limiting the numbers of iterations of the MCTS loop to 22 (tttSearch.looplimit
:= SOME 22;), a call to ttt_tnn now fails on the running example but the
search tree is stored in the reference searchtree_glob. Executing
$\texttt{suggest}\ ();$ at this point returns the most promising partial proof
tree in searchtree_glob. To construct the tree, this function traverses down
the tree and selects the first proved tactic branch or the most visited open
tactic branch if no branch has been proved. A tactic built from this proof
tree can then be applied to the original goal and the user might continue
working on the produced open goals. The resulting partial proof suggested from
our failed attempt is:

⬇

Induct >| [rewrite_tac [numeralTheory.numeral_distrib] >> all_tac,

srw_tac [ARITH_ss] [MULT_CLAUSES,LEFT_ADD_DISTRIB] >> all_tac]

The depth of this advice may be controlled by updating the reference
tttSearch.suggest_depth. The function suggest can also be used in combination
with the original ttt function but the advice will be of lesser value as the
most promising proof branches are fixed by the policy and therefore the most
promising proof tree is gradually extended as the search tree grows. In
contrast, the decision on which path is most promising might be revised when
running ttt_tnn with higher timeouts.

##  6 Conclusion

Training a TNN on intermediate goals generated by TacticToe leads to the
creation of a goal provability estimator with good accuracy. Since a goal can
be split into multiple goals during tactic-based searches, we propose
improvements to the selection and backup phases of the underlying MCTS
algorithm in order to get more accurate feedback from the learned estimator.
Experiments on the full HOL4 library measure an increase in the success rate
of TacticToe and demonstrate the scalability of our approach. This resulted in
the creation of new tools for HOL4 users that leverage the advice given by the
estimator. In particular, TacticToe is now able to suggest how to start a
proof even when it fails to find one.

## References

  * [1]
  * [2] David Auger, Adrien Couëtoux & Olivier Teytaud (2013): _Continuous Upper Confidence Trees with Polynomial Exploration - Consistency_.  In: Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part I, pp. 194–209, 10.1007/978-3-642-40988-2_13.
  * [3] Kshitij Bansal, Sarah M. Loos, Markus N. Rabe, Christian Szegedy & Stewart Wilcox (2019): _HOList: An Environment for Machine Learning of Higher Order Logic Theorem Proving_.  In Kamalika Chaudhuri & Ruslan Salakhutdinov, editors: Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, Proceedings of Machine Learning Research 97, PMLR, pp. 454–463.  Available at http://proceedings.mlr.press/v97/bansal19a.html.
  * [4] Yves Bertot (2008): _A Short Presentation of Coq_.  In Otmane Ait Mohamed, César Muñoz & Sofiène Tahar, editors: Conference on Theorem Proving in Higher Order Logics (TPHOLs), LNCS 5170, Springer, pp. 12–16, 10.1007/978-3-540-71067-73.
  * [5] Lasse Blaauwbroek, Josef Urban & Herman Geuvers (2020): _The Tactician - A Seamless, Interactive Tactic Learner and Prover for Coq_.  In Christoph Benzmüller & Bruce R. Miller, editors: Intelligent Computer Mathematics - 13th International Conference, CICM 2020, Bertinoro, Italy, July 26-31, 2020, Proceedings, LNCS 12236, Springer, pp. 271–277, 10.1007/978-3-030-53518-6_17.
  * [6] Karel Chvalovský, Jan Jakubuv, Martin Suda & Josef Urban (2019): _ENIGMA-NG: Efficient Neural and Gradient-Boosted Inference Guidance for E_.  In: Automated Deduction - CADE 27 - 27th International Conference on Automated Deduction, Natal, Brazil, August 27-30, 2019, Proceedings, pp. 197–215, 10.1007/978-3-030-29436-6_12.
  * [7] Thibault Gauthier (2020): _Deep Reinforcement Learning for Synthesizing Functions in Higher-Order Logic_.  In Elvira Albert & Laura Kovács, editors: LPAR 2020: 23rd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Alicante, Spain, May 22-27, 2020, EPiC Series in Computing 73, EasyChair, pp. 230–248, 10.29007/7jmg.
  * [8] Thibault Gauthier (2020): _Tree Neural Networks in HOL4_.  In Christoph Benzmüller & Bruce R. Miller, editors: Intelligent Computer Mathematics - 13th International Conference, CICM 2020, Bertinoro, Italy, July 26-31, 2020, Proceedings, LNCS 12236, Springer, pp. 278–283, 10.1007/978-3-030-53518-6_18.
  * [9] Thibault Gauthier, Cezary Kaliszyk, Josef Urban, Ramana Kumar & Michael Norrish (2021): _TacticToe: Learning to Prove with Tactics_.  J. Autom. Reason. 65(2), pp. 257–286, 10.1007/s10817-020-09580-x.
  * [10] John Harrison (2009): _HOL Light: An Overview_.  In Stefan Berghofer, Tobias Nipkow, Christian Urban & Makarius Wenzel, editors: Conference on Theorem Proving in Higher Order Logics (TPHOLs), LNCS 5674, Springer, pp. 60–66, 10.1007/978-3-642-03359-94.
  * [11] Joe Hurd (2005): _System Description: The Metis Proof Tactic_.  In Carsten Schuermann Christoph Benzmueller, John Harrison, editor: Workshop on Empirically Successful Automated Reasoning in Higher-Order Logic (ESHOL), pp. 103–104.  Available at https://arxiv.org/pdf/cs/0601042.
  * [12] Cezary Kaliszyk, Josef Urban, Henryk Michalewski & Miroslav Olsák (2018): _Reinforcement Learning of Theorem Proving_.  In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi & Roman Garnett, editors: Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 8836–8847.  Available at https://proceedings.neurips.cc/paper/2018/hash/55acf8539596d25624059980986aaa78-Abstract.html.
  * [13] Yutaka Nagashima & Yilun He (2018): _PaMpeR: proof method recommendation system for Isabelle/HOL_.  In Marianne Huchard, Christian Kästner & Gordon Fraser, editors: Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering, ASE 2018, Montpellier, France, September 3-7, 2018, ACM, pp. 362–372, 10.1145/3238147.3238210.
  * [14] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel & Demis Hassabis (2017): _Mastering the game of Go without human knowledge_.  Nature 550, pp. 354–359, 10.1038/nature24270.
  * [15] Konrad Slind & Michael Norrish (2008): _A Brief Overview of HOL4_.  In Otmane Aït Mohamed, César A. Muñoz & Sofiène Tahar, editors: Conference on Theorem Proving in Higher Order Logics (TPHOLs), LNCS 5170, Springer, pp. 28–32, 10.1007/978-3-540-71067-76.
  * [16] Makarius Wenzel, Lawrence C. Paulson & Tobias Nipkow (2008): _The Isabelle Framework_.  In Otmane Aït Mohamed, César A. Muñoz & Sofiène Tahar, editors: Conference on Theorem Proving in Higher Order Logics (TPHOLs), LNCS 5170, Springer, pp. 33–38, 10.1007/978-3-540-71067-77.


# A Progressive Codebook Optimization Scheme for Sparse Code Multiple Access
in Downlink Channels

Tuofeng Lei, Qu Luo, Shuyan Ni, Shimiao Chen, Xin Song, and Pei Xiao Tuofeng
Lei, Shuyan Ni, Shimiao Chen is with the Space Engineering University, Beijing
101416, China. (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>14291002@bjtu.edu.cn).Pei Xiao is with the State Key Laboratory of ISN, Xidian
University, Xi’an, 710071, China. email<EMAIL_ADDRESS>Luo is with
the National Key Laboratory of Science and Technology on Communications,
University of Electronic Science and Technology of China, Chengdu 610054,
China. email<EMAIL_ADDRESS>Song is with the Academy of Military
Sciences, Beijing 100071, China. (e-mail: singlersx@163.com).

###### Abstract

Sparse code multiple access (SCMA) is a promising technique for enabling
massive connectivity and high spectrum efficiency in future machine-type
communication networks. However, its performance crucially depends on well-
designed multi-dimensional codebooks. In this paper, we propose a novel
progressive codebook optimization scheme that can achieve near-optimal
performance over downlink fading channels. By examining the pair-wise error
probability (PEP), we first derive the symbol error rate (SER) performance of
the sparse codebook in downlink channels, which is considered as the design
criterion for codebook optimization. Then, the benchmark constellation group
at a single resource element is optimized with a sequential quadratic
programming approach. Next, we propose a constellation group reconstruction
process to assign the sub-constellations in each resource element (RE)
progressively. For the current RE, the assignment of the sub-constellations is
designed by minimizing the error performance of the product distance of the
superimposed codewords in previous REs. The design process involves both
permutation and labeling of the sub-constellations in the benchmark
constellation group. Simulation results show that the proposed codebooks
exhibit significant performance gains over state-of-the-art codebooks in the
low signal-to-noise ratio (SNR) region over various downlink fading channels.

###### Index Terms:

Sparse code multiple access, symbol error rate, codebook design, progressive
codebook optimization

##  I Introduction

The ever-growing demand for higher data rates, enhanced spectral efficiency,
and massive connectivity has driven the rapid evolution of wireless
communication systems [1, 2]. To meet these stringent requirements, non-
orthogonal multiple access (NOMA) has emerged as a promising technology for
the future of wireless communication networks [3]. In contrast to traditional
orthogonal multiple access (OMA), NOMA enables multiple users to effectively
utilize the same resources in a non-orthogonal manner [4, 5]. Existing NOMA
methods are mainly categorized into power-domain [1] and code-domain NOMA [3].
This paper focuses on a representative code domain NOMA (CD-NOMA) scheme
called sparse code multiple access (SCMA), which has attracted significant
research attention due to its excellent performance and low receiver
complexity [6]. In SCMA, the incoming message bits of each user are directly
mapped to a multi-dimensional codeword chosen from a pre-defined codebook. The
codebook are intentionally designed with certain sparsity to effectively
reduce the decoding complexity of the message passing algorithm (MPA). In
addition, constellation shaping of multi-dimensional constellations leads to a
significant improvement in spectral efficiency when compared to other code-
domain NOMA schemes [7], such as low-density spreading code division multiple
access (LDS-CDMA) and low-density signature-orthogonal frequency division
multiplexing (LDS-OFDM).

###  I-A Related works

SCMA codebook design has been studied extensively in the past few years [8, 7,
9, 10, 11, 12, 13, 14, 15, 16]. The overall design goal is to find a class of
codebooks for low error rate or large spectral efficiency under different
channel conditions. Maximizing the minimum Euclidean distance of the
superimposed codewords (MED-SC) and the minimum product distance of the
superimposed codeword (MPD-SC) have been considered as the key performance
indicators in the additive white Gaussian noise (AWGN) channels and downlink
Rayleigh channels, respectively. To date, the AWGN codebook reported by Huang
[17] achieves the largest MED-SC, and the downlink Rayleigh codebook proposed
by Chen has better performance in comparison with existing codebooks [4],[18].
In [19], MCs with low-projection number were proposed for downlink AWGN
channels by maximizing the MED-SC.

Existing codebook design typically follows a multi-stage approach by first
constructing a mother constellation (MC), followed by certain user-specific
operators, such as phase rotation and permutation [15, 16], which are applied
to the MC to obtain codebooks for multiple users. The basic rationale behind
this approach is to improve the MED-SC and MPD-SC, thus achieving lower error
rate performance. Based on this approach, various MCs have been reported for
their flexibility and simplicity [14, 15, 16, 20, 21, 22, 23]. For example, in
[22], optimum MCs were designed by maximizing the MED-SC. In [23], the 3D MC
was investigated to improve the error performance by increasing available
dimensional information. In [14], the design criteria of the SCMA codebook for
the uplink Rician fading channels was investigated, and a mother constellation
based codebook was used to achieve better performance. Moreover, the author in
[24] studied the codebook design in Ricain fading channels, where a novel
class of low-projection SCMA codebooks for ultra-low decoding complexity was
developed. In [25], an uniquely decomposable constellation group based
codebook design approach was proposed to improve the error performance. In
[26], differential evolution optimization was adopted for minimizing the
symbol error rates (SER) of the SCMA system. In [4], near optimal SCMA
codebooks were proposed in both AWGN and Rayleigh fading channels. It should
be noted that the optimization of the best rotation angles and the calculation
of the Euclidean distance of the superimposed codewords in these works
generally incur high computation complexity.

###  I-B Motivations and Contributions

As pointed out in [4], the superimposed constellation at each RE also has a
great impact on the error rate performance. In general, the constellation at
each RE forms a constellation group. Since many existing codebooks choose
different MCs and rotation angles [20, 21, 22, 23, 25, 26, 19, 27, 28, 29],
the resultant constellation groups at each RE may also be different. For
example, the constellation groups can be formed by the Golden angle modulation
(GAM) constellation and star quadrature amplitude modulation (Star-QAM)
constellation in [27] and [28], respectively. However, the multi-stage
approach is generally considered a sub-optimal approach, as the superimposed
constellation depends crucially on the choice of MC and rotation angles. An
alternative and more ambitious approach is to directly design the superimposed
constellation at each RE with desirable characteristics instead of following a
multi-stage based approaches.

Driven by this rationale, we propose to directly design the superimposed
constellation at a single RE, where the multiple constellations that lead to
the superimposed constellation are referred to as the benchmark constellation
group. Subsequently, we suggest a reconstruction process by progressively
assigning the benchmark constellation group to each RE. At each step, the
assignment of the benchmark constellation group for the current RE is
determined by minimizing the error performance of the product distance among
superimposed codewords from previous REs. Moreover, unlike many existing SCMA
papers that focus on codebook design for AWGN and Rayleigh fading channels, we
design SCMA codebooks for Rician and Nakagami-$m$ fading channels, which are
prevalent in practical networks. The major contributions of the paper are
summarized as follows:

  * •

We derive the SER performance of SCMA systems over different fading channels
by analyzing the pair-wise error probability (PEP). The related properties and
codebook design criteria in each fading channel are also investigated and
analyzed.

  * •

We propose a novel progressive codebook optimization scheme based on a
benchmark constellation group. Specifically, we optimize the benchmark
constellation group at a single RE using a sequential quadratic programming
(SQP) approach. Next, we introduce a constellation group reconstruction
process to progressively assign the sub-constellations of the benchmark
constellation group in each RE.

  * •

We conduct extensive simulation results to demonstrate the superiority of the
proposed codebooks over different fading channels. The proposed codebook
exhibits the notable improvements in terms of error performance under lower
SNRs over the existing near optimal codebooks.

###  I-C Organization

The remainder of this paper is organized as follows: Section ii@ introduces
the model of the downlink SCMA system. Section iii@ provides the SER formula
of the sparse multidimensional constellation under different fading channels.
The detailed construction procedures of the codebooks are presented in Section
<EMAIL_ADDRESS>Then, in Section v@, simulation results are provided to show the SER
performance of the proposed codebooks. Finally, Section vi@ concludes the
paper.

###  I-D Notations

$\mathbb{C}^{k\times n}$ and $\mathbb{B}^{k\times n}$ denote the $(k\times
n)$-dimensional complex and binary matrix spaces, respectively. Scalars,
vectors and matrices are distinguished by normal, lowercase bold and uppercase
bold fonts. ${\mathrm{|}}\cdot{\mathrm{|}}$ and
${\mathrm{||}}\cdot{\mathrm{||}}$ denote the absolute value, and the
$\mathcal{\ell}_{2}-\mathrm{norm}$, respectively.
$\mathcal{CN}\left(0,1\right)$ denotes complex Gaussian distribution with
zero-mean and unit-variance.

##  II  SCMA Communication Model

Figure 1: An example of SCMA mapping process.

We consider a $K\times L$ SCMA system, where $L$ users communicate over $K$
REs for multiple access. The overloading factor of SCMA system is defined by
$\xi=L/K>100\%$, which indicates that the number of users that concurrently
communicate is larger than the total number of orthogonal resources. Each user
is assigned with a unique codebook, denoted by
${\mathcal{X}}_{l}=\left\\{\mathbf{x}_{l,1},\mathbf{x}_{l,2},\ldots,\mathbf{x}_{l,M}\right\\}\in\mathbb{C}^{K\times
M},l\in\\{1,2,\ldots,L\\}$, consisting of $M$ codewords with a dimension of
$K$. During transmissions, each user maps $\log_{2}\left(M\right)$ binary bits
to a length-$K$ codeword $\mathbf{x}_{l}$ drawn from the ${\mathcal{X}}_{l}$.
The SCMA mapping process can be written as

$\begin{matrix}{{f}_{l}}:{{\mathsf{\mathbb{B}}}^{lo{{g}_{2}}M\times
1}}\to{{\mathcal{X}}_{l}},&\text{i}\text{.e}.,{{\mathbf{x}}_{l}}={{f}_{l}}\\\
\end{matrix}\left({{\mathbf{b}}_{l}}\right),\ $ (1)

where ${{\mathbf{b}}_{l}}\in{{\mathsf{\mathbb{B}}}^{lo{{g}_{2}}M\times 1}}$
denotes the bits data of the $l\text{th}$ user, $M$ represents the codebook
size, and
${{\mathbf{x}}_{l}}={{\left[{{x}_{1,l}},{{x}_{2,l}},\cdots,{{x}_{K,l}}\right]}^{T}}$
denotes the transmitted codewords in the $l\text{th}$ user’s codebook
${{\mathcal{X}}_{l}}$, and ${{x}_{k,l}}$ is the transmitted codeword of the
$l\text{th}$ user at the $k\text{th}$ RE. Fig. 1 shows an example of the SCMA
mapping process.

The $K$-dimensional codewords are sparse vectors with $d_{v}$ non-zero
elements. The sparse structure of the $L$ codebooks can be represented by an
indicator matrix $\mathbf{F}\in\mathbb{B}^{K\times L}$. An element of
${\bf{F}}$ is defined as ${f_{k,l}}$ which takes the value of $1$ if and only
if the $k$th RE is occupied by the $l$ user, and $0$ otherwise. The indicator
matrix is constructed by the progressive edge-growth (PEG) algorithm to attain
large girths [23]. For the SCMA system with $K=4$, $L=6$ and $d_{v}=2$, the
indicator matrix is given as

$\textbf{F}=\left[\begin{matrix}0&1&1&0&1&0\\\ 0&1&0&1&0&1\\\ 1&0&1&0&0&1\\\
1&0&0&1&1&0\\\ \end{matrix}\right],$ (2)

where the corresponding factor graph representation is shown in Fig. 2. We
further define the set $\phi_{k}=\\{l:{f}_{k,l}=1\\}$ consisting of all the
users colliding over RE $k$ and the number of users collides over a RE is
given as $d_{f}=|\phi_{k}|$.

Denote ${{h}_{k}}$ by the channel coefficient at the $k\text{th}$ RE, the
received signal at the $k\text{th}$ RE can be written as

$\begin{matrix}{{y}_{k}}={{h}_{k}}\sum\limits_{l=1}^{L}{{{x}_{k,l}}+{{z}_{k}},}&{{x}_{k,l}}\in{{\mathcal{X}}_{l}}\\\
\end{matrix},$ (3)

Figure 2: The factor graph representation of the indicator matrix.

where ${{z}_{k}}$ denotes the additive white Gaussian noise at the
$k\text{th}$ RE that obeys complex circularly symmetric Gaussian random
variables $\mathcal{C}\mathcal{N}\left(0,{{N}_{0}}\right)$.

##  III Error Performance of the Sparse Codebook in Different Fading Channels

In downlink SCMA systems, users’ data are first superimposed at the base
station side, which constitutes the superimposed constellation
${{\mathcal{X}}_{\text{sup}}}$ with size of $K\times M^{L}$. Denote
$\mathbf{c}=\sum_{l=1}^{L}\mathbf{x}_{l}\in{{\mathcal{X}}_{\text{sup}}}$ as
the transmitted superimposed codeword of $L$ users. Assume the codeword is
erroneously decoded as $\mathbf{c}_{j}$ when $\mathbf{c}_{i}$ is transmitted,
where $\mathbf{c}_{i}\neq\mathbf{c}_{j}$. Then, the conditional PEP between be
two distinct codewords $\mathbf{c}_{i}$ and $\mathbf{c}_{j}$ can be calculated
by

$\Pr\left(\left.{{\mathbf{c}}_{i}}\to{{\mathbf{c}}_{j}}\right|\mathbf{h}\right)=Q\left(\sqrt{\frac{{{E}_{s}}}{2{{N}_{0}}}d_{\text{sup}}^{2}\left({{\mathbf{c}}_{i}},{{\mathbf{c}}_{j}}\right)}\right),$
(4)

where
$Q\left(x\right)={1}/{\sqrt{2\pi}}\;\int_{x}^{\infty}{\exp\left(-{{{t}^{2}}}/{2}\;\right)dt}$
denotes the $Q$-function [30],
$\mathbf{h}=[{{h}_{1}},{{h}_{2}}\ldots,{{h}_{K}}]$ denotes the channel
coefficient vector, and
$d_{\text{sup}}^{2}\left({{\mathbf{c}}_{i}},{{\mathbf{c}}_{j}}\right)$ denotes
the Euclidean distance between the superimposed codewords which takes the
following expression

$d_{\text{sup}}^{2}\left({{\mathbf{c}}_{i}},{{\mathbf{c}}_{j}}\right)=\sum\limits_{k=1}^{K}{{{\left|{{h}_{k,l}}\left({{c}_{k,i}}-{{c}_{k,j}}\right)\right|}^{2}}},$
(5)

where ${{c}_{k,i}}=\sum\nolimits_{l=1}^{L}{{{x}_{k,l}}}$ is the $i\text{th}$
superimposed codeword at the $k\text{th}$ RE, and ${h}_{k,l}$ represents the
channel coefficients of the $l\text{th}$ user at the $k\text{th}$ RE. Then,
following the Chernoff bound [30], the conditional PEP can be expressed as

$\Pr\left(\left.{{\mathbf{c}}_{i}}\to{{\mathbf{c}}_{j}}\right|\mathbf{h}\right)\leq\frac{1}{2}\exp\left(-\frac{{{E}_{s}}}{4{{N}_{0}}}d_{\text{sup}}^{2}\left({{\mathbf{c}}_{i}},{{\mathbf{c}}_{j}}\right)\right).$
(6)

With the aid of the MGF, the PEP of the superimposed codewords can be easily
obtained. Denote the instantaneous SNR as
$\gamma={{\left|{{h}_{k}}\right|}^{2}}\left({{{E}_{s}}}/{{{N}_{0}}}\;\right)$,
and the average SNR as $\bar{\gamma}=\mathbb{E}\left[\gamma\right]$, where
$\bar{\gamma}$ is the mean square of the instantaneous SNR. Thus, the MGF
associated with the instantaneous SNR is defined as [31]

${{\mathcal{M}}_{\gamma}}\left(s\right)=\int_{0}^{\infty}{p\left(\gamma\right)}{{e}^{s\gamma}}d\gamma,$
(7)

where $p\left(\gamma\right)$ is the PDF of the $\gamma$. The unconditional PEP
can be obtained by averaging over the channel distribution

$\displaystyle\mathrm{Pr}\left(\mathbf{c}_{i}\right.\to\mathbf{c}_{j})=\mathbb{E}_{\mathbf{h}}\left\\{\Pr\left(\left.{{\mathbf{c}}_{i}}\to{{\mathbf{c}}_{j}}\right|\mathbf{h}\right)\right\\}$
(8)
$\displaystyle\leq\frac{1}{2}\int_{0}^{\infty}\exp\left(-\frac{E_{s}}{4N_{0}}\sum_{k=1}^{K}\Bigl{|}h_{k,l}\bigl{(}c_{k,i}-c_{k,j}\bigr{)}\Bigr{|}^{2}\right)p(h){d}h,$
$\displaystyle\leq\frac{1}{2}\prod_{k=1}^{K}\mathcal{M}_{\gamma}(-s_{k}),$

where ${{s}_{k}}={{{\left|{{c}_{k,i}}-{{c}_{k,j}}\right|}^{2}}}/{4}\;$. The
average SER can be written as [32]

${{P}_{e}}\leq\frac{1}{{{M}^{L}}}\sum\limits_{{\mathbf{c}_{i}}\in{{\mathcal{X}}_{\text{sup}}}}{\sum\limits_{{\mathbf{c}_{j}}\in{{\mathcal{X}}_{\text{sup}}}\backslash\left\\{{\mathbf{c}_{i}}\right\\}}{\frac{1}{2}\prod\limits_{k=1}^{K}{{{\mathcal{M}}_{\gamma}}\left(-{{s}_{k}}\right)}.}}$
(9)

In the following sections, we derive the average SER of SCMA over different
fading channels based on (9).

###  III-A Rayleigh Fading Channel

The Rayleigh channel model is suitable for characterizing the urban
environment with dense buildings but no direct exposure. The distribution of
Rayleigh fading is the ${{\ell}_{2}}$ norm of two zero-mean independent
Gaussian random variables, and the PDF of the Rayleigh distribution can be
written as

$p\left(z\right)=\begin{matrix}\frac{z}{\sigma_{Ra}^{2}}\exp\left(-\frac{{{z}^{2}}}{2\sigma_{Ra}^{2}}\right),&z>0\\\
\end{matrix},$ (10)

where $\sigma_{Ra}^{2}$ is the scatter component of the Rayleigh distribution,
the mean square of the Rayleigh distribution is given by
$\mathbb{E}\left[{{z}^{2}}\right]=2\sigma_{Ra}^{2}$ [33], and the MGF of the
instantaneous SNR $\gamma$ is [31]

$\begin{matrix}{{\mathcal{M}}_{\gamma}}\left(-s\right)=\frac{1}{1+s\bar{\gamma}},&s>0\\\
\end{matrix}.$ (11)

The PEP of the superimposed codeword in the Rayleigh fading channel can be
calculated as

$\Pr\left({{\mathbf{c}}_{i}}\to{{\mathbf{c}}_{j}}\right)\leq\frac{1}{2}{{\prod\limits_{k=1}^{K}{\left(1+\frac{2\sigma_{Ra}^{2}{{E}_{s}}}{4{{N}_{0}}}{{\left|{{c}_{k,i}}-{{c}_{k,j}}\right|}^{2}}\right)}}^{-1}}.$
(12)

At high SNRs with a large scatter component $\sigma_{Ra}^{2}$, it can be
observed that maximizing the product distance of the superimposed codewords
${{d}_{p}}=\prod\nolimits_{k=1}^{K}{{{\left|{{c}_{k,i}}-{{c}_{k,j}}\right|}^{2}}}$
helps improve error performance. In the low SNR region with a small scatter
component $\sigma_{Ra}^{2}$, the Euclidean distance of the superimposed
codeword
${{d}_{e}}=\sum\nolimits_{k=1}^{K}{{{\left|{{c}_{k,i}}-{{c}_{k,j}}\right|}^{2}}}$
also helps improve error performance.

###  III-B Rician Fading Channel

The Rician fading model is used to characterize channels with direct line-of-
sight (LoS) waves. The distribution of the Rician fading can be modeled as the
${{\ell}_{2}}$ norm of two non-zero mean independent Gaussian random variables
and the PDF of the Rician distribution is given by [24]

$p\left(z\right)=\begin{matrix}\frac{z}{\sigma_{Ri}^{2}}{{I}_{0}}\left(\frac{uz}{\sigma_{Ri}^{2}}\right)\exp\left(-\frac{{{z}^{2}}+{{u}^{2}}}{2\sigma_{Ri}^{2}}\right),&z>0\\\
\end{matrix},$ (13)

where $u$ and $\sigma_{Ri}^{2}$ are the LoS and the scatter components
respectively, $\mathcal{K}={{{u}^{2}}}/{2\sigma_{Ri}^{2}}\;$ is defined as the
Rician factor, and ${{I}_{0}}$ is the modified Bessel function of the first
kind. The mean square of the Rician distribution can be calculated as
$\mathbb{E}\left[{{z}^{2}}\right]=2\sigma_{Ri}^{2}\left(1+\mathcal{K}\right)$
[33], and the MGF of the instantaneous SNR $\gamma$ in the Rician distribution
is given by [31]

$\begin{matrix}{{\mathcal{M}}_{\gamma}}\left(-s\right)=\frac{1+\mathcal{K}}{1+\mathcal{K}+s\bar{\gamma}}\exp\left(-\frac{\mathcal{K}s\bar{\gamma}}{1+\mathcal{K}+s\bar{\gamma}}\right),&s>0\\\
\end{matrix}.$ (14)

Then, the PEP of the superimposed codeword in the Rician fading channel can be
calculated

$\displaystyle\operatorname*{Pr}(\mathbf{c}_{i}\to\mathbf{c}_{j})$
$\displaystyle\leq\frac{1}{2}\prod_{k=1}^{K}\frac{1}{1+\frac{2\sigma_{Ri}^{2}E_{s}}{4N_{0}}\big{|}c_{k,i}-c_{k,j}\big{|}^{2}}$
(15)
$\displaystyle\times\exp\left(-\frac{\mathcal{K}\frac{2\sigma_{Ri}^{2}E_{s}}{4N_{0}}\big{|}c_{k,i}-c_{k,j}\big{|}^{2}}{1+\frac{2\sigma_{Ri}^{2}E_{s}}{4N_{0}}\big{|}c_{k,i}-c_{k,j}\big{|}^{2}}\right),$

where we define the PEP of the scatter component and the LoS component
respectively as

${{\Pr}_{\text{scatter}}}=\prod\limits_{k=1}^{K}{\frac{1}{1+\frac{2\sigma_{Ri}^{2}{{E}_{s}}}{4{{N}_{0}}}{{\left|{{c}_{k,i}}-{{c}_{k,j}}\right|}^{2}}}},$
(16)

${{\Pr}_{\text{LoS}}}=\prod\limits_{k=1}^{K}{\exp\left(-\frac{\mathcal{K}\frac{2\sigma_{Ri}^{2}{{E}_{s}}}{4{{N}_{0}}}{{\left|{{c}_{k,i}}-{{c}_{k,j}}\right|}^{2}}}{1+\frac{2\sigma_{Ri}^{2}{{E}_{s}}}{4{{N}_{0}}}{{\left|{{c}_{k,i}}-{{c}_{k,j}}\right|}^{2}}}\right)}.$
(17)

Compared with the PEP in Rayleigh fading channel [29, 18], SCMA achieves
better error performance in the Rician fading channel from the LoS component
${{\Pr}_{\text{LoS}}}$. When the SNR and the scatter component
$\sigma_{Ri}^{2}$ is sufficiently large, the PEP for the Rician fading channel
can be simplified as

$\Pr\left({{\mathbf{c}}_{i}}\to{{\mathbf{c}}_{j}}\right)\leq\frac{1}{2}\prod\limits_{k=1}^{K}{{{\left(\frac{2\sigma_{Ri}^{2}{{E}_{s}}}{4{{N}_{0}}}{{\left|{{c}_{k,i}}-{{c}_{k,j}}\right|}^{2}}\right)}^{-1}}\exp\left(-\mathcal{K}\right)}.$
(18)

Meanwhile, it can be observed that maximizing the product distance of the
superimposed codewords, $d_{p}$, is a crucial factor for the performance of
the Rician fading channel. While in lower SNR with a larger Rician factor
$\mathcal{K}$ (a small scatter component $\sigma_{Ri}^{2}$ or a larger LoS
component $u$), observing from the LoS component ${{\Pr}_{\text{LoS}}}$ in
(17), we can find that maximizing the Euclidean distance of the superimposed
codeword ${{d}_{e}}$ also helps improve the performance.

###  III-C Nakagami-$m$ Fading Channel

Nakagami-$m$ is a multipath channel model that can better control the degree
of fading. Moreover, the Nakagami-$m$ distribution can be considered as the
square root of the sum of squares of $2m$ independent zero mean Gaussian
variates [34]. When the Nakagami-$m$ fading parameter $m$ is 1, the
Nakagami-$m$ model is reduced to the Rayleigh model. The PDF of the
Nakagami-$m$ fading model can be expressed as

$p\left(z\right)=\begin{matrix}\frac{2}{\Gamma\left(m\right)}{{\left(\frac{m}{\text{
}\\!\\!\Omega\\!\\!\text{
}}\right)}^{m}}{{z}^{2m-1}}\exp\left(-\frac{m{{z}^{2}}}{\text{
}\\!\\!\Omega\\!\\!\text{ }}\right),&z>0\\\ \end{matrix},$ (19)

where $\text{ }\\!\\!\Omega\\!\\!\text{ }$ is the scale parameter, $m$ is the
Nakagami-$m$ fading parameter, which has the range of $m\geq 0.5$, and
$\Gamma\left(m\right)$ is the gamma function which can be written as

$\Gamma\left(m\right)=\int_{0}^{\infty}{{{t}^{m-1}}{{e}^{-t}}}dt.$ (20)

The mean square of the Nakagami-$m$ distribution can be calculated as
$\mathbb{E}\left[{{z}^{2}}\right]=\text{ }\\!\\!\Omega\\!\\!\text{ }\text{}$
[33], and the MGF of the instantaneous SNR $\gamma$ in the Nakagami-$m$ fading
channel is given by [31]

$\begin{matrix}{{\mathcal{M}}_{\gamma}}\left(-s\right)={{\left(1+\frac{s\bar{\gamma}}{m}\right)}^{-m}},&s>0\\\
\end{matrix}.$ (21)

The PEP of the superimposed codeword in the Nakagami-$m$ fading channel can be
written as

$\Pr\left({{\mathbf{c}}_{i}}\to{{\mathbf{c}}_{j}}\right)\leq\frac{1}{2}{{\prod\limits_{k=1}^{K}{\left(1+\frac{\text{
}\\!\\!\Omega\\!\\!\text{
}\frac{{{E}_{s}}}{4{{N}_{0}}}{{\left|{{c}_{k,i}}-{{c}_{k,j}}\right|}^{2}}}{m}\right)}}^{-m}},$
(22)

where one can see that maximizing the product distance of the superimposed
codewords ${{d}_{p}}$ helps improve the error performance only when the ratio
of the ${\text{ }\\!\\!\Omega\\!\\!\text{ }}/{m}\;$ and the SNR are large.
While in the low SNR region or the ratio of the ${\text{
}\\!\\!\Omega\\!\\!\text{ }}/{m}\;$ is small, maximizing the Euclidean
distance of the superimposed codeword ${{d}_{e}}$ can improve the error rate
performance.

##  IV The Proposed Progressive Codebook Optimization Scheme

This section presents the detailed design of the proposed progressive codebook
optimization scheme. First, the SER of the SCMA is adopted as the design
criteria to obtain the near optimal codebook. Then, a progressive codebook
optimization scheme is proposed for different channel models.

###  IV-A The Optimization of the Benchmark Constellation Group

Denote $\mathcal{A}_{0}\in\mathbb{C}^{M\times 1}$ as the benchmark
constellation. In existing SCMA works, $\mathcal{A}_{0}$ is employed to design
the multi-dimensional codebooks for different users. Specifically, the non-
zero dimensions of the $l$th user’s codebook can be generated by applying the
user-specific operators, such as phase rotation, to $\mathcal{A}_{0}$. Owning
to the sparsity of the factor graph matrix, the number of users superimposed
on one RE, denoted by ${{d}_{f}}$, is less than the number of users.
Therefore, ${{d}_{f}}$ distinct rotation angles are sufficient to distinguish
the superimposed codewords. The codebooks for the $L$ users can be represented
by the signature matrix $\mathbf{S}_{K\times L}$. For example, the following
signature matrix can be employed for efficient codebook construction

$\small{{\mathbf{S}}_{4\times
6}}=\left[\begin{matrix}0&\mathcal{A}_{0}e^{j\theta_{3}}&\mathcal{A}_{0}e^{j\theta_{1}}&0&\mathcal{A}_{0}e^{j\theta_{2}}&0\\\
\mathcal{A}_{0}e^{j\theta_{2}}&0&\mathcal{A}_{0}e^{j\theta_{3}}&0&0&\mathcal{A}_{0}e^{j\theta_{1}}\\\
0&\mathcal{A}_{0}e^{j\theta_{2}}&0&\mathcal{A}_{0}e^{j\theta_{1}}&0&\mathcal{A}_{0}e^{j\theta_{3}}\\\
\mathcal{A}_{0}e^{j\theta_{1}}&0&0&\mathcal{A}_{0}e^{j\theta_{2}}&\mathcal{A}_{0}e^{j\theta_{3}}&0\\\
\end{matrix}\right].$ (23)

Based on (23), the superimposed constellation on a RE can be obtained by

$\displaystyle{\mathcal{F}}_{\text{sup}}=\Big{\\{}$ $\displaystyle
a_{0}^{(1)}e^{j\theta_{1}}+a_{0}^{(2)}e^{j\theta_{2}}+\ldots+a_{0}^{(d_{f})}e^{j\theta_{d_{f}}}$
(24) $\displaystyle\quad\quad\quad\quad|\forall
a_{0}^{(v)}\in\mathcal{A}_{0},v=1,2,\ldots,d_{f}\Big{\\}}.$

The superimposed constellation at each RE, i.e.,
${\mathcal{F}}_{\text{sup}}\in\mathbb{C}^{M^{d_{f}}\times 1}$, has a
significant impact on the error rate performance. In addition, it is noted
that the $d_{f}$ constellations at each RE are the same, i.e.,
$\mathcal{F}=\left\\{\mathcal{A}_{0}{{e}^{j{{\theta}_{1}}}},\mathcal{A}_{0}{{e}^{j{{\theta}_{2}}}},\ldots,\mathcal{A}_{0}{{e}^{j{{\theta}_{d_{f}}}}}\right\\}$,
which is referred to as the benchmark constellation group. However, the
resultant constellations group $\mathcal{F}$ may not achieve the best error
performance in different fading channels as the superimposed constellation
${\mathcal{F}}_{\text{sup}}$ relies heavily on the choice of $\mathcal{A}_{0}$
and the rotation angles. Hence, a jointly optimization scheme is proposed to
generate the constellation group $\mathcal{F}$. Specifically, different from
the above discussed scheme, where $\mathcal{F}$ is obtained by rotating a
basic benchmark constellation $\mathcal{A}_{0}$, we propose to directly design
$\mathcal{F}=\left\\{{{\mathcal{A}}_{1}},{{\mathcal{A}}_{2}},\cdots,{{\mathcal{A}}_{{{d}_{f}}}}\right\\}$.
Define the elements in ${{\mathcal{A}}_{v}}$ as
${{\mathcal{A}}_{v}}=\\{a_{v,1},a_{v,2},\ldots,a_{v,M}\\}$. According to the
transmission model in the downlink fading channels, the constellation group
$\mathcal{F}$ can be formulated as an optimization problem to minimize the SER
of the superimposed constellation

$\begin{matrix}\left\\{{{\mathcal{A}}_{1}},{{\mathcal{A}}_{2}},\cdots,{{\mathcal{A}}_{{{d}_{f}}}}\right\\}=\underset{0\leq{{r}_{v,m}}\leq
1,0\leq{{\theta}_{v,m}}\leq 2\pi}{\mathop{\arg\min}}\,{{P}_{b}},\\\ \\\
s.t.\begin{cases}{{P}_{b}}={\frac{1}{{M}^{{{d}_{f}}}}}\sum\limits_{{{c}_{i}}\in{\mathcal{F}}_{\text{sup}}}{\sum\limits_{{{c}_{j}}\in{\mathcal{F}}_{\text{sup}}\backslash\left\\{{{c}_{i}}\right\\}}{}}{{\left(1+\frac{2\sigma_{Ra}^{2}{{E}_{s}}}{4{{N}_{0}}}{{\left|{{c}_{i}}-{{c}_{j}}\right|}^{2}}\right)}^{-1}},\\\\[6.0pt]
{{\mathcal{A}}_{v}}=\\{a_{v,1},a_{v,2},\ldots,a_{v,M}\\},\\\\[6.0pt]
{{a}_{v,m}}={{r}_{v,m}}{{e}^{j{{\theta}_{v,m}}}},\\\\[6.0pt]
\mathcal{F}_{\text{sup}}=\left\\{\sum\limits_{v=1}^{{{d}_{f}}}{{{a}_{v}}}|\;\forall{a}_{v}\in{{\mathcal{A}}_{v}}\right\\},\\\\[6.0pt]
1\leq i\leq{{M}^{{{d}_{f}}}},1\leq v\leq d_{f},1\leq m\leq M&\end{cases}\\\
\end{matrix}$ (25)

where ${{P}_{b}}$ represents the SER of the superimposed codewords in the
benchmark constellation group $\mathcal{F}$ under Rayleigh fading channel, and
the SER can also be replaced for other fading channels. ${c}_{i}$ and
${c}_{j}$ are two different superimposed codewords in
${\mathcal{F}}_{\text{sup}}$ where $i\neq j$, and $r_{v,m}$ and
${\theta_{v,m}}$ are the module and phase angle of the codewords $a_{v,m}$.
Here, the SQP approach is adopted to solve the optimization problem.

(a)

(b)

Figure 3: Comparisons of the constellation group and superimposed codewords
constellation of the proposed codebook and the codebook in [4].

Example 1: Fig. 3 shows an example of the benchmark constellation group
$\mathcal{F}$ and the corresponding superimposed constellation
${\mathcal{F}}_{\text{sup}}$ of the proposed scheme and the existing scheme
in[4]. In [4], the benchmark constellation group, as shown in Fig. 3(a), is
superimposed with $d_{f}$ QPSK constellations with certain rotations. In
contrast, the benchmark constellation group generated by the proposed scheme
is not confined to the rotation of a specific benchmark constellation
$\mathcal{A}_{0}$. In addition, the proposed scheme achieves larger minimum
Euclidean distance of the superimposed constellation, which is defined as

$\small{\mathcal{F}}^{\text{min}}_{\text{sup}}\triangleq\underset{{{c}_{i}}\in{\mathcal{F}}_{\text{sup}},{{c}_{j}}\in{\mathcal{F}}_{\text{sup}}\backslash\left\\{{{c}_{i}}\right\\}}{\min}|c_{i}-c_{j}|^{2}.$
(26)

###  IV-B Reconstruction of the Constellation Group

Algorithm 1 The Progressive Codebook Optimization Scheme.

Input: REs $K$, users $L$, degree of user nodes $d_{v}$, degree of REs nodes
$d_{f}$ , codebook size $M$.

Return: The factor graph matrix $\mathbf{F}$ through PEG.

Optimize:

$\mathcal{F}\leftarrow$ Optimize (25) through SQP.

${{\mathcal{F}}_{1}}\leftarrow$ Assign $\mathcal{F}$ randomly in the first RE.

for $k=2$ to $K$ do

${{\mathcal{F}}_{k}}\leftarrow$ Optimize $\text{ perms }(\cdot)$ and
${\mathbf{P}_{k,\phi_{k}^{v}}}$ in (27).

end for

Output: The optimized multi-dimensional constellation.

Figure 4: An example of the multi-dimensional constellation generated by
reconstructing the benchmark constellation group.

After the benchmark constellation group $\mathcal{F}$ is obtained, the multi-
dimensional constellation for different users can be obtained by placing the
sub-constellations of $\mathcal{F}$ in the factor graph matrix to minimize the
average SER of the superimposed codewords. The non-zero constellation group at
the first RE is trivial, which can be set the same as the optimized result
$\mathcal{F}_{1}=\mathcal{F}$. However, when $k\geq 2$, there are ${{d}_{f}}!$
possible combinational results of assigning the sub-constellations of
$\mathcal{F}$ to the activate users in each RE, where the activate users
$f_{k,l}=1$ can be found through the indicator matrix F. As $d_{f}$ generally
is a small value, we adopt the ergodic search method to obtain the best
result. Besides, the labeling sequence of each sub-constellation
${{\mathcal{A}}_{i}}$ in $\mathcal{F}$ is reordered to maximize the coding
gains of the codebook [14], where the ergodic search method is employed to
achieve the best result . Finally, the problem of reconstructing the benchmark
constellation group $\mathcal{F}$ in the $k\text{th}$ RE can be formulated as
an optimization problem to minimize the SER of the superimposed codewords in
previous $k$ REs. Denote the reconstructed constellation group in the
$k\text{th}$ RE as
${\mathcal{F}}_{k}=\left\\{{{\mathcal{S}}_{k,\phi_{k}^{1}}},{{\mathcal{S}}_{k,\phi_{k}^{2}}},\cdots,{{\mathcal{S}}_{k,\phi_{k}^{d_{f}}}}\right\\}$,
where ${{\mathcal{S}}_{k,\phi_{k}^{v}}}$ denotes the reconstructed
constellation for the $\phi_{k}^{v}$th user at the $k$th RE, and
$\phi_{k}^{v}$ denotes the active user index in the $k$th RE. For example, for
the first RE, i.e. $k=1$, we have $\phi_{1}=[2,3,5]$ and $\phi_{1}^{1}=2$.
Namely, ${{\mathcal{S}}_{1,\phi_{1}^{1}}}$ is assigned for the second user at
the first RE. In Rayleigh fading channels, the design of reconstructed
constellation group ${\mathcal{F}}_{k}$ is formulated as

$\displaystyle\begin{array}[]{l}{\mathcal{F}}_{k}=\underset{\text{ perms
}(\cdot),\mathbf{P}_{k,l}}{\arg\min}\\\
\sum\limits_{c_{k,i}\in{\mathcal{F}}_{\text{sup}}^{k}}\sum\limits_{\begin{subarray}{c}c_{k,j}\in{\mathcal{F}}_{\text{sup}}^{k}\\\
\backslash\left\\{c_{k,i}\right\\}\end{subarray}}\prod\limits_{n=1}^{k}\left(1+\frac{2\sigma_{Ra}^{2}E_{s}}{4N_{0}}\left|c_{n,i}-c_{n,j}\right|^{2}\right)^{-1},\\\
\\\
s.t.=\left\\{\begin{array}[]{l}\left\\{{{\mathcal{S}}_{k,\phi_{k}^{1}}},{{\mathcal{S}}_{k,\phi_{k}^{2}}},\cdots,{{\mathcal{S}}_{k,\phi_{k}^{d_{f}}}}\right\\}={\rm{perms}}\\\
\left({\left\\{{{{\cal A}_{1}}{{\bf{P}}_{k,1}}},{{{\cal
A}_{2}}{{\bf{P}}_{k,2}}},\ldots,{{{\cal
A}_{{d_{f}}}}{{\bf{P}}_{k,d_{f}}}}\right\\}}\right),\\\ \\\
\mathcal{F}_{\text{sup}}^{k}=\left\\{\sum\limits_{v=1}^{{d_{f}}}{{{s}_{k,v}}}|\;\forall{s}_{k,v}\in{{\mathcal{S}}_{k,\phi_{k}^{v}}}\right\\},\\\
\\\ 2\leq k\leq K,1\leq v\leq d_{f},\end{array}\right.\end{array}$ (27)

where ${\mathcal{F}}_{\text{sup}}^{k}$ denotes the superimposed constellation
at the $k\text{th}$ RE,
${{\mathcal{S}}_{k,\phi_{k}^{v}}}\in\mathbb{C}^{M\times 1}$ represents the
constellation of the $\phi_{k}^{v}\text{th}$ user in the $k\text{th}$ RE, and
the constellations of the inactivate users $f_{k,l}=0$ who does not perform
transmission in the $k$th RE is set to 0 with $M$ zero elements,
$\text{perms}\left(\cdot\right)$ denotes the permutation function for
generating all possible combinations of the constellation group, and the
binary matrix ${\mathbf{P}_{k,v}}$ denotes permutation matrix that reorders
the labelling sequence of a constellation. Specifically, ${\mathbf{P}_{k,v}}$
is defined as ${\mathbf{P}_{k,v}}=\left\\{p_{m,n}\right\\}^{M\times M}$, where
$p_{m,n}\in\\{0,1\\}$ and $p_{m,n}=1$ denotes the $m$th codeword is labeled
with decimal $n$. There are $M!$ permutation (labeling) options for an $M$-ary
constellation. Hence, for large modulation order $M$, the complexity of
exhaustive search is prohibitively high. The binary switching algorithm
employed in [24] can be utlized to find the labeling solution with a
reasonable complexity. Finally, the detail design of the proposed codebook is
summarized in Algorithm 1.

Example 2: We now present an example to illustrate the proposed constellation
reconstruction process. Specifically, consider the benchmark constellation
group presented in Fig. 3, the constructed codebook for different users is
given as follows

$\displaystyle\begin{matrix}{\mathcal{X}}\\\ \end{matrix}$
$\displaystyle=\left[\begin{matrix}\textbf{0}&{{\mathcal{S}}_{1,2}}&{{\mathcal{S}}_{1,3}}&\textbf{0}&{{\mathcal{S}}_{1,5}}&\textbf{0}\\\
\textbf{0}&{{\mathcal{S}}_{2,2}}&\textbf{0}&{{\mathcal{S}}_{2,4}}&\textbf{0}&{{\mathcal{S}}_{2,6}}\\\
{{\mathcal{S}}_{3,1}}&\textbf{0}&{{\mathcal{S}}_{3,3}}&\textbf{0}&\textbf{0}&{{\mathcal{S}}_{3,6}}\\\
{{\mathcal{S}}_{4,1}}&\textbf{0}&\textbf{0}&{{\mathcal{S}}_{4,4}}&{{\mathcal{S}}_{4,5}}&\textbf{0}\\\
\end{matrix}\right],$ (28)
$\displaystyle=\left[\begin{matrix}\textbf{0}&{{{\cal
A}_{1}}{{\bf{P}}_{1,1}}}&{{{\cal A}_{2}}{{\bf{P}}_{1,2}}}&\textbf{0}&{{{\cal
A}_{3}}{{\bf{P}}_{1,3}}}&\textbf{0}\\\ \textbf{0}&{{{\cal
A}_{3}}{{\bf{P}}_{2,3}}}&\textbf{0}&{{{\cal
A}_{1}}{{\bf{P}}_{2,1}}}&\textbf{0}&{{{\cal A}_{2}}{{\bf{P}}_{2,2}}}\\\
{{{\cal A}_{2}}{{\bf{P}}_{3,2}}}&\textbf{0}&{{{\cal
A}_{1}}{{\bf{P}}_{3,1}}}&\textbf{0}&\textbf{0}&{{{\cal
A}_{3}}{{\bf{P}}_{3,3}}}\\\ {{{\cal
A}_{3}}{{\bf{P}}_{4,3}}}&\textbf{0}&\textbf{0}&{{{\cal
A}_{1}}{{\bf{P}}_{4,1}}}&{{{\cal A}_{2}}{{\bf{P}}_{4,2}}}&\textbf{0}\\\
\end{matrix}\right],$

where the corresponding constellations are also illustrated in Fig. 4. The row
represents the RE and the column denotes the user. In (28), the permuted
${\cal A}_{2}$ and ${\cal A}_{3}$ are assigned for the first user, and the
codebook for the remaining users can also be generated similarly based on
(28). In addition, it can be observed from Fig. 4 that the multi-dimensional
constellation of each user is not restricted to the operation of a specific
benchmark constellation. For example, the constellation of users $2$ and $3$
on the first RE is different from user $5$. In addition, the permutation
function of the constellation and the relabeling sequence of the constellation
can be noticed to increase the coding gains of the codebook.

##  V Simulation Results

Figure 5: The performance comparisons between the proposed codebooks and
Chen’s codebook [4] in Rayleigh fading channels.

Figure 6: The SER performance of the proposed codebooks and Chen’s codebook
[4] in different Rayleigh fading parameters.

In this section, we present the SER performance of the proposed SCMA codebooks
in comparison with the one introduced in [4], which has been verified to yield
good error performance in downlink Rayleigh channels [23], [18]. Then,
simulation results are provided to demonstrate that the codebooks designed by
progressively minimizing the SER of product distance of the superimposed
codewords outperform the benchmark codebook [4] under different downlink
fading channels at lower SNRs.

###  V-A Error Perforamnce in Rayleigh Channel

Fig. 6 illustrates the SER performance of the codebooks in Rayleigh fading
channels with different scatter components $\sigma_{Ra}^{2}$, where the single
user bounds are obtained by calculating the average SER of the mother
constellation of each user. It can be observed that the performance of the
SCMA codebooks approaches the single-user error performance at higher SNRs,
indicating a gradual mitigation of interference among users. Since maximizing
the product distance of the superimposed codewords ${{d}_{p}}$ is crucial only
when the values of SNR and $\sigma_{Ra}^{2}$ are large, we can observe from
Fig. 6 that the proposed codebooks outperform Chen’s codebook [4] at low SNRs.
Specifically, the proposed codebook achieves about $0.3$ dB gains over Chen’s
codebook at SER = $10^{-2}$ when the scatter component $\sigma_{Ra}^{2}=0.2$.

Fig. 6 presents the SER of the codebooks with different values of the scatter
component $\sigma_{Ra}^{2}$ under various SNRs. As evidenced by Fig. 6, better
SER performance can be achieved with the increase of the scatter component
$\sigma_{Ra}^{2}$. In addition, Fig. 6 also demonstrates that the proposed
codebooks obtained by minimizing the SER of the SCMA achieve better error
performance than Chen’s codebook under lower SNRs and scatter components
$\sigma_{Ra}^{2}$.

###  V-B Error Performance in Rician Channel

Fig. 8 compares the SER performance of the proposed codebook and Chen’s
codebook under Rician fading channels with various scatter component
$\sigma_{Ri}^{2}$. At low SNRs, the Euclidean distance of the superimposed
codewords ${{d}_{e}}$ is one of important factors affecting the error
performance. Consequently, a gain of around $0.2$ dB can be observed when
compared with Chen’s codebook. However, in the case of higher SNRs, the
proposed codebooks achieve the same SER performance as Chen’s codebook. This
is because the key factor affecting the SER performance at higher SNRs is
maximized product distance of the superimposed codewords ${{d}_{p}}$.

Fig. 8 presents the SER of the proposed codebooks under different LoS
components $u$. In the case of a small value of $u$, i.e., $u=0.1$, the
proposed codebook achieves the same SER performance as Chen’s codebook [4] at
a higher SNR, while a slightly better error performance can be observed at
lower SNRs. As $u$ increases, i.e., when the LoS dominates, the proposed
codebooks achieve better SER performance than Chen’s codebook [4].
Specifically, about $0.3$ dB gain can be observed at SER = $10^{-4}$ for the
LoS component $u=2.0$. This is because the design criteria of maximizing the
Euclidean distance of the superimposed codewords ${{d}_{e}}$ is also a crucial
factor influencing the error performance of SCMA under a larger LoS component
$u$. Moreover, as the LoS component $u$ increases, the Rician factor becomes
larger, resulting in better error performance that can be achieved from the
LoS component ${{\Pr}_{\text{LoS}}}$.

Figure 7: The SER performance of the proposed codebooks and Chen’s codebook
[4] in the Rician fading channel under various scatter components
$\sigma_{Ri}^{2}$ where the LoS component $u=0.2$.

Figure 8: The SER performance of the proposed codebooks and Chen’s codebook
[4] in the Rician fading channel under various LoS components $u$ where the
scatter component $\sigma_{Ri}^{2}=0.5$.

###  V-C Error Performance in Nakagami-$m$ Channel

Figure 9: The SER performance of the proposed codebooks and Chen’s codebook
[4] in Nakagami-$m$ fading channel under various Nakagami-$m$ fading
parameters $m$ where the scale parameter is $\text{ }\\!\\!\Omega\\!\\!\text{
}=1$.

Figure 10: The SER performance of the proposed codebooks and Chen’s codebook
[4] in Nakagami-$m$ fading channel under various scale parameters $\text{
}\\!\\!\Omega\\!\\!\text{ }$ where the Nakagami-$m$ fading parameters is
$m=1.5$.

Fig. 10 and Fig. 10 compare the SER performance of the proposed codebook and
Chen’s codebook under different Nakagami-$m$ fading channels. As can been seen
from Fig. 10, the proposed codebook outperforms Chen’s codebook [4] at low
SNRs. For the Nakagami-$m$ fading channels with $m=1$, which corresponds to
the Rayleigh fading channel, the proposed codebooks achieve the same SER
performance as Chen’s codebook [4] at higher SNRs. As $m$ increases, the ratio
of the ${\text{ }\\!\\!\Omega\\!\\!\text{ }}/{m}\;$ decreases. Therefore,
maximizing the Euclidean distance of the superimposed codeword ${{d}_{e}}$ can
help improve the SER performance. When the Nakagami-$m$ fading parameters are
$m=1$ and $m=1.5$, the proposed codebooks achieve approximately 0.1 dB and 0.2
dB over Chen’s codebook at SER = $10^{-3}$.

Fig. 10 compares the SER performance of different codebooks under various
scale parameters $\text{ }\\!\\!\Omega\\!\\!\text{ }$. It can be seen that as
$\text{ }\\!\\!\Omega\\!\\!\text{ }$ increases , the error performance of the
SCMA improves. Moreover, the increased ratio of ${\text{
}\\!\\!\Omega\\!\\!\text{ }}/{m}\;$ indicates that the key performance
indicator lies in maximizing the product distance of the superimposed
codewords ${{d}_{p}}$. Thus, the proposed codebooks exhibit a comparable SER
performance to Chen’s codebook with the increase of the scale parameters
$\text{ }\\!\\!\Omega\\!\\!\text{ }$ at high SNRs. However, in lower SNRs,
around $0.3$ dB gain is observed for the proposed codebook at SER = $10^{-3}$.

##  VI Conclusion

In this paper, we have proposed a progressive codebook optimization scheme for
downlink SCMA systems over fading channels. Utilizing the MGF, we have derived
a simplified SER model of SCMA under various channel conditions. This model
serves as the design criterion for optimizing the codebook. Subsequently, we
have optimized the benchmark constellation group at a single RE using a SQP
approach. Additionally, we have introduced a constellation group
reconstruction to progressively assign the benchmark constellation group in
each RE. For the current RE, the assignment of sub-constellations was designed
by minimizing the error performance of the product distance of superimposed
codewords from previous REs. Finally, extensive simulation results have been
conducted to demonstrate the superiority of the proposed codebooks at low SNRs
in comparison to the benchmark codebooks over different fading channels.

## References

  * [1] Y. Liu, S. Zhang, X. Mu, Z. Ding, R. Schober, N. Al-Dhahir, E. Hossain, and X. Shen, “Evolution of NOMA toward next generation multiple access (NGMA) for 6G,” _IEEE J. Sel. Areas Commun._ , vol. 40, no. 4, pp. 1037–1071, 2022.
  * [2] M. Elbayoumi, M. Kamel, W. Hamouda, and A. Youssef, “NOMA-assisted machine-type communications in UDN: State-of-the-art and challenges,” _IEEE Commun. Surv. & Tutor._, vol. 22, no. 2, pp. 1276–1304, 2020.
  * [3] Q. Luo, P. Gao, Z. Liu, L. Xiao, Z. Mheich, P. Xiao, and A. Maaref, “An error rate comparison of power domain non-orthogonal multiple access and sparse code multiple access,” _IEEE Open J. Commun. Society_ , vol. 2, pp. 500–511, 2021.
  * [4] Y.-M. Chen and J.-W. Chen, “On the design of near-optimal sparse code multiple access codebooks,” _IEEE Trans. Commun._ , vol. 68, no. 5, pp. 2950–2962, 2020.
  * [5] M. Vameghestahbanati, I. D. Marsland, R. H. Gohary, and H. Yanikomeroglu, “Multidimensional constellations for uplink SCMA systems—A comparative study,” _IEEE Commun. Surveys Tutor._ , vol. 21, no. 3, pp. 2169–2194, 2019\.
  * [6] Q. Luo, Z. Liu, G. Chen, Y. Ma, and P. Xiao, “A novel multitask learning empowered codebook design for downlink SCMA networks,” _IEEE Wireless Commun. Lett._ , vol. 11, no. 6, pp. 1268–1272, 2022.
  * [7] Y.-M. Chen, Y.-C. Hsu, M.-C. Wu, R. Singh, and Y.-C. Chang, “On near-optimal codebook and receiver designs for MIMO-SCMA schemes,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 12, pp. 10 724–10 738, 2022.
  * [8] Q. Wang and G. Ren, “A partial Gaussian tree approximation (PGTA) detector for random multiple access oriented scma uplink with codebook collisions,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 4, pp. 2295–2308, 2021.
  * [9] F. Tekçe, U. E. Ayten, and L. Durak-Ata, “SCMA system design with index modulation via codebook assignment,” _IEEE Trans. Veh. Technol._ , vol. 70, no. 2, pp. 1699–1708, 2021.
  * [10] H. Yaoyue, P. Zhiwen, L. Nan, and Y. Xiaohu, “Multidimensional constellation design for spatial modulated SCMA systems,” _IEEE Trans. Veh. Technol._ , vol. 70, no. 9, pp. 8795–8810, 2021.
  * [11] J. Bao, Z. Ma, M. Xiao, T. A. Tsiftsis, and Z. Zhu, “Bit-interleaved coded SCMA with iterative multiuser detection: Multidimensional constellations design,” _IEEE Trans. Commun._ , vol. 66, no. 11, pp. 5292–5304, 2018.
  * [12] C. Jiang, Y. Wang, P. Cheng, and W. Xiang, “A low-complexity codebook optimization scheme for sparse code multiple access,” _IEEE Trans. Commun._ , vol. 70, no. 4, pp. 2451–2463, 2022.
  * [13] Z. Liu and L.-L. Yang, “Sparse or dense: A comparative study of code-domain NOMA systems,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 8, pp. 4768–4780, 2021.
  * [14] T. Lei, S. Ni, N. Cheng, S. Chen, and X. Song, “SCMA codebook for uplink rician fading channels,” _IEEE Commun. Lett._ , vol. 27, no. 2, pp. 527–531, 2023.
  * [15] M. Taherzadeh, H. Nikopour, A. Bayesteh, and H. Baligh, “SCMA codebook design,” in _IEEE Veh Technol Conf (VTC2014-Fall), Vancouver, BC, Canada,_ , 2014, pp. 1–5.
  * [16] H. Nikopour, E. Yi, A. Bayesteh, K. Au, M. Hawryluck, H. Baligh, and J. Ma, “SCMA for downlink multiple access of 5g wireless networks,” in _IEEE Global Commun. Conf., GLOBECOM, Austin, TX, USA_ , 2014, pp. 3940–3945.
  * [17] C. Huang, B. Su, T. Lin, and Y. Huang, “Downlink SCMA codebook design with low error rate by maximizing minimum Euclidean distance of superimposed codewords,” _IEEE Trans. Veh. Technol._ , vol. 71, no. 5, pp. 5231–5245, 2022.
  * [18] V. Vikas, A. Rajesh, K. Deka, and S. Sharma, “A comprehensive technique to design SCMA codebooks,” _IEEE Commun. Lett._ , vol. 26, no. 8, pp. 1735–1739, 2022.
  * [19] Y. Zheng, J. Xin, H. Wang, S. Zhang, and Y. Qiao, “A low-complexity codebook design scheme for SCMA systems over an AWGN channel,” _IEEE Trans. Veh. Technol._ , vol. 71, no. 8, pp. 8675–8688, 2022.
  * [20] L. Li, Z. Ma, P. Z. Fan, and L. Hanzo, “High-dimensional codebook design for the SCMA downlink,” _IEEE Trans. Veh. Technol._ , vol. 67, no. 10, pp. 10 118–10 122, 2018.
  * [21] L. Tian, J. Zhong, M. Zhao, and L. Wen, “A suboptimal algorithm for SCMA codebook design over uplink rayleigh fading channels,” in _in Proc. IEEE 87th Veh. Technol. Conf. (VTC Spring)_ , Jun. 2018, pp. 1–5.
  * [22] M. Alam and Q. Zhang, “Designing optimum mother constellation and codebooks for SCMA,” in _2017 IEEE International Conference on Communications (ICC)_ , 2017, pp. 1–6.
  * [23] T. Lei, S. Ni, N. Cheng, S. Chen, and X. Song, “A novel scheme for the construction of the SCMA codebook,” _IEEE Access_ , vol. 10, pp. 100 987–100 998, 2022.
  * [24] Q. Luo, Z. Liu, G. Chen, P. Xiao, Y. Ma, and A. Maaref, “A design of low-projection SCMA codebooks for ultra-low decoding complexity in downlink IoT networks,” _IEEE Trans. Wireless Commun._ , vol. 22, no. 10, pp. 6608–6623, 2023.
  * [25] X. Zhang, D. Zhang, L. Yang, G. Han, H.-H. Chen, and D. Zhang, “SCMA codebook design based on uniquely decomposable constellation groups,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 8, pp. 4828–4842, 2021.
  * [26] K. Deka, M. Priyadarsini, S. Sharma, and B. Beferull-Lozano, “Design of SCMA codebooks using differential evolution,” in _2020 IEEE International Conference on Communications Workshops (ICC Workshops), Dublin, Ireland_ , 2020, pp. 1–7.
  * [27] Z. Mheich, L. Wen, P. Xiao, and A. Maaref, “Design of SCMA codebooks based on golden angle modulation,” _IEEE Trans. Veh. Technol._ , vol. 68, no. 2, pp. 1501–1509, 2019.
  * [28] L. Yu, P. Fan, D. Cai, and Z. Ma, “Design and analysis of SCMA codebook based on Star-Qam signaling constellations,” _IEEE Trans. Veh. Technol._ , vol. 67, no. 11, pp. 10 543–10 553, 2018.
  * [29] X. Li, Z. Gao, Y. Gui, Z. Liu, P. Xiao, and L. Yu, “Design of power-imbalanced SCMA codebook,” _IEEE Trans. Veh. Technol._ , vol. 71, no. 2, pp. 2140–2145, 2022.
  * [30] J. Yuan, Z. Chen, B. Vucetic, and W. Firmanto, “Performance and design of space-time coding in fading channels,” _IEEE Trans. Wireless Commun._ , vol. 51, no. 12, pp. 1991–1996, 2003.
  * [31] M. Simon and M. Alouini, _Digital communication over fading channels, Hoboken, New Jersey, USA: IEEE_. John Wiley & Sons, Inc, 2005.
  * [32] Q. Luo, Z. Liu, G. Chen, and P. Xiao, “Enhancing signal space diversity for SCMA over Rayleigh fading channels,” _IEEE Trans. Wireless Commun._ , pp. 1–1, 2023.
  * [33] G. John and S. M. Proakis, _Digital Communications, New York, NY, USA: 772,_. McGraw-Hill, 2008.
  * [34] G. Karagiannidis, D. Zogas, and S. Kotsopoulos, “On the multivariate Nakagami-m distribution with exponential correlation,” _IEEE Trans. Commun._ , vol. 51, no. 8, pp. 1240–1244, 2003.