# Scalable Syndrome-based Neural Decoders for
Bit-Interleaved Coded Modulations

Gastón De Boni Rovella1 2, Meryem Benammar2, Tarik Benaddi3 , Hugo Meric4
1TéSA Laboratory, Toulouse, France
2ISAE-SUPAERO, Université de Toulouse, France
3Thales Alenia Space, Toulouse, France
4Centre National d’Études Spatiales, Toulouse, France
Email: {gaston.de-boni-rovella<EMAIL_ADDRESS>
###### Abstract

In this work, we introduce a framework that enables the use of Syndrome-Based
Neural Decoders (SBND) for high-order Bit-Interleaved Coded Modulations
(BICM). To this end, we extend the previous results on SBND, for which the
validity is limited to Binary Phase-Shift Keying (BPSK), by means of a
theoretical channel modeling of the bit Log-Likelihood Ratio (bit-LLR) induced
outputs. We implement the proposed SBND system for two polar codes $(64,32)$
and $(128,64)$, using a Recurrent Neural Network (RNN) and a Transformer-based
architecture. Both implementations are compared in Bit Error Rate (BER)
performance and computational complexity.

##  I Introduction

With the recent introduction of 5G and beyond technologies, the interest in
fast and reliable communication systems has increased in an unprecedented
manner. At the same time, the ever-growing computational power has given
machine learning a crucial role in future communication systems as a fast and
robust alternative to some classical physical layer solutions like channel
demodulation and decoding.

Early works in channel decoding [1, 2] promptly faced the curse of
dimensionality, where the space of valid codewords was too large for a common
Deep Neural Network (DNN) to explore and learn. To tackle this problem, two
main scalable alternatives were proposed: model-based solutions, that directly
exploit the structure of the code [3, 4, 5], and model-free solutions, that do
not depend on the code and allow the integration of more sophisticated machine
learning techniques [6, 7, 8]. Model-based solutions are often neural
extensions of the Belief Propagation (BP) algorithm that help tackle the
negative impact of short cycles in BP decoding. However, implementations for
semi-dense or dense codes, such as BCH or Polar codes [9], remain subpar.

A model-free approach, which we denote as Syndrome-Based Neural Decoder
(SBND), was introduced more recently by Bennatan et al. [6], and has since
been implemented using different deep learning techniques [7, 10, 8, 11]. The
main idea behind the SBND is to produce a symmetric decoder that does not
depend on the codeword and can thus be trained with a unique codeword.
Although this provides us with a very promising framework, these works rely
extensively on the properties of Binary Phase-Shift Keying (BPSK) and can be
easily extended to Quadrature Phase-Shift Keying (QPSK). However, in order to
allow for practical implementations, SBND has to be extended to higher-order
modulations such as $M$-Quadrature Amplitude Modulation (QAM) and $M$-Phase-
Shift Keying (PSK) for arbitrary $M$. In this work, we propose a decoder that
can be directly applied to such linear modulation techniques. More
particularly, we focus on Bit-Interleaved Coded Modulations (BICM) [12, 13]
which, unlike classical coded modulation schemes, present the advantages of
allowing the usage of any Forward Error Correction (FEC) code designed for
memoryless channels, and of being more robust to burst errors.

The main difference between higher-order modulations and BPSK/QPSK is that the
decoder is not directly fed with the channel output, but rather, with bit Log-
Likelihood Ratios (bit-LLR) produced by the soft demodulator. Hence, in order
to design an SBND for the BICM, we first start by characterizing the channel
induced by bit-LLRs for two common modulation schemes. Next, we propose an
SBND that extends that of [7, 10, 8, 11] to the case of high-order BICM.
Finally, we analyze the performance of two main architectures for the neural-
based decoders, namely, RNN-based and transformer-based, and compare their
respective complexities. Finally, Section V concludes the work.

The remainder of this work is organized as follows. Section II introduces the
system model and some preliminaries on channel modeling for BICM. In Section
III, we describe the proposed decoding framework. Then, Section IV presents
two possible implementations for the deep learning-based portion of the
decoder, compares experimentally their BER performances and analyzes their
complexity.

Notations: Capital italic letters (e.g. $X$ and $\boldsymbol{X}$) represent
random variables and vectors whereas Roman and bold letters (e.g. $x$ and
$\boldsymbol{x}$) denote their respective realizations. Matrices are
represented by non-italic capital letters (e.g. $\mathrm{H}$) and
$\mathrm{I}_{n}$ denotes the $n\times n$ identity matrix. The Hadamard product
between vectors is represented by $(.)$. Sets are denoted by calligraphic
letters $\mathcal{X}$, and for finite sets, $|\mathcal{X}|$ denotes the
cardinality. $P_{X}(x)$ (resp. $P_{X|Y}(x|y)$) represents the probability
distribution (resp. conditional) evaluated in $x$ (resp. $(x,y)$). Markov
chains are denoted $X\leftrightarrow Y\leftrightarrow Z$ to mean
$P_{Z|Y,X}=P_{Z|Y}$. $\mathds{P}$ (resp. $\mathds{1}$) denotes the generic
probability (resp. indicator) of an event. $[1:n]$ denotes the set of integers
from $1$ to $n$ and $\lfloor\cdot\rfloor$ represents the floor function. The
xor operation is noted $\oplus$.

##  II System model and preliminaries

###  II-A Bit-Interleaved Coded Modulations (BICM)

Figure 1: General system model.

Let us consider a BICM communication setting as depicted in Figure 1. In such
a setting, an input binary message $\boldsymbol{U}$ of $k$ bits, assumed to be
independent and uniformly distributed, is first mapped through an $(n,k)$
linear block FEC encoder into a codeword $\boldsymbol{C}$ of $n$ bits. Let us
denote the parity check matrix of this code as $\mathrm{H}$. Then, a perfectly
random interleaver $\Pi$, assumed to be known to the receiver as well,
shuffles the bits of $\boldsymbol{C}$ into an $n$-bit sequence
$\boldsymbol{\tilde{C}}$, which is then passed through a modulator. The
complex-valued constellation is denoted by $\mathcal{X}$ and is assumed to be
of order $m$ (i.e. $M=2^{m}$ states). The sequence of $n^{\prime}=n/m$ symbols
$\boldsymbol{X}$ is then fed to an Additive White Gaussian Noise (AGWN). Its
output can be modeled as

$\boldsymbol{Y}=\boldsymbol{X}+\boldsymbol{W},\ \text{s.t.}\
\boldsymbol{W}\overset{\text{i.i.d}}{\sim}\mathcal{CN}(\boldsymbol{0},\sigma^{2}\mathrm{I}_{n^{\prime}}).$
(1)

The demodulator, upon reception of the channel output $\boldsymbol{Y}$,
computes the bit-Log Likelihood Ratios (bit-LLR) associated with each bit $C$
given the corresponding received signal $Y$. The resulting bit-LLRs
$\boldsymbol{\tilde{L}}$ are then de-interleaved back to the original bit
order. Based on the obtained bit-LLRs $\boldsymbol{L}$, the FEC decoder
$g(\cdot)$ produces an estimate $\boldsymbol{\hat{u}}$ of the $k$ transmitted
bits given by $\boldsymbol{\hat{U}}=g(\boldsymbol{L})$.

In this work, we investigate the design of decoders that minimize the Bit-
Error Probability (BEP) defined by

$P_{e}(g)\triangleq\dfrac{1}{k}\sum_{i=1}^{k}\mathds{P}(\hat{U}_{i}\neq
U_{i}).$ (2)

###  II-B BICM equivalent channel models

The main advantage of the BICM communication setting, as opposed to standard
(non-interleaved) coded modulation schemes, is that a perfectly random
interleaver maps every bit in $\boldsymbol{C}$ evenly to each one of the $m$
bit positions in the constellation mapping. Hence, throughout the
transmission, all bits in the sequence $\boldsymbol{C}$ end up experiencing
the same channel, which is averaged out over all bit positions.

An equivalent channel model for BICM was introduced in [12] and is given in
Figure 2, where $P^{s}_{Y|C}$ denotes the effective channel distribution
experienced by a bit transmitted over a position $s$ in the constellation
mapping, $f^{s}(\cdot)$ denotes the bit-LLRs function (depending on the bit
position) and is given for all $y\in\mathds{C}$ and $s\in[1:m]$ by

$f^{s}(y)\triangleq\log\left(P^{s}_{Y|C}(y|0)\right)-\log\left(P^{s}_{Y|C}(y|1)\right),$
(3)

and the last operation is simply a decomposition into a hard decision
$L^{b}\triangleq\mathds{1}(L<0)$ and a reliability measure $|L|$.

Figure 2: BICM channel model extended to bit-LLRs.

In order to motivate our proposed decoder of Section III, we need to
characterize three channel distributions $P_{L^{b}|C}$. To this end, we will
recall the results on $P_{Y|C}$ and $P_{L|C}$, and extend them to model the
channel $P_{L^{b}|C}$.

####  II-B1 Channel distributions $P_{Y|C}$ and $P_{L|C}$

Let us recall the equivalent channel models as of the BICM in Figure 2.

######  Lemma 1 (BICM classical channel models [12, 13]).

An equivalent channel distribution of a classical BICM setting is given for
all $\boldsymbol{y}\in\mathds{C}^{n^{\prime}}$,
$\boldsymbol{l}\in\mathds{R}^{n}$, and $\boldsymbol{c}\in\\{0,1\\}^{n}$ by

$P_{\boldsymbol{Y}|\boldsymbol{C}}(\boldsymbol{y}|\boldsymbol{c})\text{=}\prod_{i=1}^{n}P_{Y|C}(y_{\lfloor\nicefrac{{i}}{{m}}\rfloor}|c_{i})\
,\
P_{\boldsymbol{L}|\boldsymbol{C}}(\boldsymbol{l}|\boldsymbol{c})\text{=}\prod_{i=1}^{n}P_{L|C}(l_{i}|c_{i})$

where, the distributions $P_{Y|C}$ and$P_{L|C}$ are given by

$\displaystyle P_{Y|C}(y|c)$ $\displaystyle=$
$\displaystyle\dfrac{1}{m|\mathcal{X}_{c}^{s}|}\sum_{s=1}^{m}\sum_{x\in\mathcal{X}_{c}^{s}}P_{Y|X}(y|x),$
(4) $\displaystyle P_{L|C}(l|c)$ $\displaystyle=$
$\displaystyle\dfrac{1}{m|\mathcal{X}_{c}^{s}|}\sum_{s=1}^{m}\sum_{x\in\mathcal{X}_{c}^{s}}P^{s}_{L|X}(l|x),$
(5)

and $\mathcal{X}_{c}^{s}$ is the set of symbols for which the $s$-th bit
equals $c$.

###### Proof.

The proofs can be found in [13, Section 3.4]. ∎

Note that the distributions $P^{s}_{L|X}$, for $s\in[1:m]$, can be easily
obtained for BPSK and QPSK modulations; however, they are very challenging to
obtain analytically for higher-order more generic modulation schemes. In this
work, we do not seek to characterize these distributions in a closed form, but
rather, will use them to derive an equivalent binary channel model for the
hard decisions on the bit-LLRs.

####  II-B2 Bit-LLRs binary channel distribution $P_{L^{b}|C}$

In order to motivate the structure of the decoder developed in this work, we
need to characterize the channel distribution $P_{L^{b}|C}$. To this end, let
us consider, for instance, the 16-QAM and 8-PSK constellations with Gray
labeling shown in Figures 5 and 6.

######  Theorem 1 (Bit-LLRs binary channel model).

For all $\boldsymbol{l}^{b},\boldsymbol{c}\in\\{0,1\\}^{n}$, the following
equation holds:

$P_{\boldsymbol{L}^{b}|\boldsymbol{C}}(\boldsymbol{l}^{b}|\boldsymbol{c})=\prod_{i=1}^{n}P_{L^{b}|C}(l^{b}_{i}|c_{i}).$
(6)

Besides, for the 8-PSK and 16-QAM under Gray labeling, the channel
$P_{L^{b}|C}$ can be approximated by

$\boldsymbol{L^{b}}=\boldsymbol{C}\oplus\boldsymbol{W}^{b}\ \text{ s.t. }\
\boldsymbol{W}^{b}\overset{\text{i.i.d}}{\sim}\text{Bern}(q),$ (7)

where $\boldsymbol{W}^{b}$ is independent of $\boldsymbol{C}$ and
$q\triangleq\dfrac{1}{m}\displaystyle\sum_{s=1}^{m}P^{s}_{L^{b}|C}(1|0)$.

###### Proof.

The proof is relegated to Appendix A. ∎

The present Theorem states that for the 8-PSK constellation under Gray
labeling, the channel $P_{L^{b}|C}$ is in fact a memoryless stationary Binary
Symmetric Channel (BSC), as described in (7). As for the 16-QAM channel, we
show that this channel model is valid for a wide range of Signal-to-Noise
Ratios (SNR), i.e., except for very low SNR. Although we prove this theorem
for only these two constellations, which are the most common in practice, the
result can be extended to M-PSK and M-QAM constellations following the same
lines of the proof.

##  III Proposed system: SBND for BICM

In what follows, we start by stating a result on Maximum A Posteriori (MAP)
decoding, then we review existing literature on SBND for the BPSK and QPSK
modulations and introduce our proposed solution.

###  III-A Decoding as a binary noise detection problem

The decoder architecture introduced in this section stems from a first result
on the equivalence between decoding and denoising. First, let us recall that,
given the channel model in Figure 1, the optimal decoding rule $g(\cdot)$ is
the MAP rule, and is given by

$\boldsymbol{\hat{u}}=g(\boldsymbol{l})\triangleq\underset{\boldsymbol{u}\in\\{0,1\\}^{k}}{\textrm{argmax}}P_{\boldsymbol{U}|\boldsymbol{L}}(\boldsymbol{u}|\boldsymbol{l}).$
(8)

Let us consider the result of Theorem 1 in (7), and let us define the pseudo-
inverse function of the FEC encoder as $p_{inv}(\cdot)$, i.e.,
$\boldsymbol{u}=p_{inv}(\boldsymbol{c})$. Then exploiting the linearity of
$p_{inv}(\cdot)$, we can show that there exists a binary noise sequence
$\boldsymbol{W}^{b}_{u}$ independent from $\boldsymbol{U}$ such that

$p_{inv}(\boldsymbol{L}^{b})=\boldsymbol{U}\oplus\boldsymbol{W}^{b}_{u}.$ (9)

Hence, we rewrite the MAP decoding rule as

$\underset{\boldsymbol{u}\in\\{0,1\\}^{k}}{\textrm{argmax}}P_{\boldsymbol{U}|\boldsymbol{L}}(\boldsymbol{u}|\boldsymbol{l})=p_{inv}(\boldsymbol{l}^{b})\oplus\underset{\boldsymbol{w}\in\\{0,1\\}^{k}}{\textrm{argmax}}P_{\boldsymbol{W}^{b}_{u}|\boldsymbol{L}}(\boldsymbol{w}|\boldsymbol{l}).$
(10)

Hence, MAP decoding of $\boldsymbol{U}$ amounts to MAP detection of the binary
noise –or bit-flip– sequence $\boldsymbol{W}^{b}_{u}$.

###  III-B Previous works on SBND for BPSK and QPSK modulations

Previous work from Bennatan et al. [6] proved that, under the assumption of a
BPSK modulation and an AWGN channel, there exists a noise sequence
$\boldsymbol{W}$ such that

$\displaystyle\boldsymbol{Y}=\boldsymbol{X}.\boldsymbol{W}\text{ and
}\boldsymbol{Y}^{b}=\boldsymbol{C}\oplus\boldsymbol{W}^{b},$ (11)

where $\boldsymbol{Y}^{b}$ and $\boldsymbol{W}^{b}$ denote the binary hard
decisions of $\boldsymbol{Y}$ and $\boldsymbol{W}$. From this, they showed
that the knowledge of the received signal’s module $|\boldsymbol{Y}|$ and the
hard-decision syndrome $\mathrm{H}\boldsymbol{Y}^{b}$ is enough to estimate
the codeword binary noise $\boldsymbol{W}^{b}$, i.e.,

$P_{\boldsymbol{W}^{b}|\boldsymbol{Y}}(\boldsymbol{w}^{b}|\boldsymbol{y})=P_{\boldsymbol{W}^{b}|\,|\boldsymbol{Y}|,\mathrm{H}\boldsymbol{Y}^{b}}(\boldsymbol{w}^{b}|\,|\boldsymbol{y}|,\mathrm{H}\boldsymbol{y}^{b}).$
(12)

Moreover, since $|\boldsymbol{Y}|=|\boldsymbol{W}|$ and
$\mathrm{H}\boldsymbol{Y}^{b}=\mathrm{H}\boldsymbol{W}^{b}$, the posterior
distribution $P_{\boldsymbol{W}^{b}|\boldsymbol{Y}}$ does not depend on the
transmitted codeword $\boldsymbol{C}$. Hence, we can train a neural network to
approximate this posterior using only one codeword, as long as the noise
$\boldsymbol{W}$ remains random.

In a previous work from the authors [11], the result of [6] was improved by
directly estimating the bit-flips on the information bits rather than on the
codewords, for both systematic and non-systematic codes. To this end, we
showed that there exists a binary noise sequence $\boldsymbol{W}^{b}_{u}$ such
that

$p_{inv}(\boldsymbol{Y}^{b})=\boldsymbol{U}\oplus\boldsymbol{W}^{b}_{u},$ (13)

and proved that the posterior can be written as

$P_{\boldsymbol{W}^{b}_{u}|\boldsymbol{Y}}(\boldsymbol{w}_{u}^{b}|\boldsymbol{y})=P_{\boldsymbol{W}^{b}_{u}|\,|\boldsymbol{Y}|,\mathrm{H}\boldsymbol{Y}^{b}}(\boldsymbol{w}_{u}^{b}|\,|\boldsymbol{y}|,\mathrm{H}\boldsymbol{y}^{b}).$
(14)

and is also independent of the message $\boldsymbol{U}$, which still allows
single codeword training.

The extension of all these results to QPSK modulation is straightforward. In
this work, we seek to generalize syndrome-based decoding to arbitrary higher-
order modulations when the decoder is fed with bit-LLRs rather than the
channel output.

###  III-C Proposed solution: SBND for BICM

In the following, we build on the results of [11] and on Theorem 1 to suggest
an SBND for higher-order modulations. We start by proving that
$|\boldsymbol{L}|$ and $\mathrm{H}\boldsymbol{L}^{b}$ are sufficient
statistics for the detection of $\boldsymbol{W}^{b}_{u}$.

######  Theorem 2 (Sufficient statistics).

Considering the problem setting and the result of Theorem 1, we have that

$P_{\boldsymbol{W}^{b}_{u}|\boldsymbol{L}}(\boldsymbol{w}_{u}^{b}|\boldsymbol{l})=P_{\boldsymbol{W}^{b}_{u}|\,|\boldsymbol{L}|,\mathrm{H}\boldsymbol{L}^{b}}(\boldsymbol{w}_{u}^{b}|\,|\boldsymbol{l}|,\mathrm{H}\boldsymbol{l}^{b}).$
(15)

###### Proof.

Proof is relegated to Appendix B ∎

This previous theorem allows us to state that
$|\boldsymbol{L}|,\mathrm{H}\boldsymbol{L}^{b}$ are sufficient to compute the
posterior distribution of $\boldsymbol{W}^{b}_{u}$. Hence, we suggest an
implementation of the SBND for higher-order modulations as shown in Figure 3.
Observe that, as opposed to the BPSK and QPSK cases, the reliabilities
$|\boldsymbol{L}|$ are not independent of the transmitted symbols, and thus,
one cannot train using only one codeword ($\boldsymbol{c}=\boldsymbol{0}$ for
instance). This imposes training over randomly generated codewords, in order
to ensure variability of the transmitted symbols.

Figure 3: Suggested SBND for higher-order modulations

##  IV Experiments

In this section, we briefly introduce two possible implementations of the bit-
flip estimator of Section III-C, test the proposed decoder with both
implementations, and compare both their performances and computational
complexities.

###  IV-A Possible architectures and training

Several DNN-based architectures can be considered for the bit-flip estimator.
Due to their favorable performances and substantial differences in terms of
complexity, the RNN estimator of [6] and the transformer-based estimator of
[7] were implemented, employing the message-wise approach of [11]. The main
difference between these architectures lies in the number of weights that
comprise each network and the number of operations needed to run each solution
(see Section IV-C). For a detailed description of these two solutions, refer
to [6, 7, 11].

Regarding the RNN-based estimator, it is a Gated Recurrent Unit (GRU)-based
RNN in which each GRU cell [14] is composed of $\alpha(2n-k)$ GRU units, with
$\alpha$ an arbitrary scaling parameter. The RNN consists of $d_{l}$ layers
–i.e. $d_{l}$ stacked GRU cells– and each unit performs $T$ time steps, with a
final dense layer with a linear activation that outputs
$\boldsymbol{\hat{w}}_{u}$ of size $k$. Training is carried out with a batch
size of $2^{12}$.

As for the transformer architecture, it is determined by three
hyperparameters: the embedding dimension $d_{e}$, the number of heads $d_{h}$
in the multi-head attention mechanism, and the number of encoder layers $N$
that are connected before the output dense layers. The large number of
operations performed in the forward pass of the transformer architecture
imposes a significantly smaller batch size, which is set to $2^{8}$.

Both architectures have a final output dense layer with a linear activation
that produces $\boldsymbol{\hat{w}}_{u}$, which is then thresholded to obtain
$\boldsymbol{\hat{w}}^{b}_{u}=\mathds{1}(\boldsymbol{\hat{w}}_{u}>0)$.
Training and testing were carried out using Google’s TensorFlow library [15]
and the Keras API [16], using the Adam optimizer [17] with a learning rate of
$\mu=10^{-3}$ and a binary cross-entropy loss function. For both systems,
codewords are generated using an AWGN of normalized SNR $E_{b}/N_{0}=5$dB.
Important parameters are reported in Table I.

RNN | $\alpha=5$ | $T=5$ | $d_{l}=5$ | batch size $=2^{12}$
---|---|---|---|---
Transformer | $d_{e}=128$ | $d_{h}=8$ | $N=10$ | batch size $=2^{8}$
TABLE I: Model and training parameters.

###  IV-B Results

Both of the considered architectures were applied to the decoding of two
rate-$\nicefrac{{1}}{{2}}$ polar codes, namely the $(128,64)$ and $(64,32)$
polar codes111The parity-check matrices were taken from the channel code
database in https://rptu.de/en/channel-codes.. An Ordered Statistics Decoding
(OSD) algorithm is also added as a near-optimal decoding benchmark, along with
an ML bound that records an error only when the OSD encounters a decoding
failure _and_ the obtained codeword has a higher probability than the
transmitted one.

The results are displayed in Figure 4. Regarding the $(64,32)$ polar code, the
RNN-based decoder presents a decoding performance that is very close to the
OSD, and surpasses the transformer architecture for all the considered
$E_{b}/N_{0}$. A similar conclusion can be drawn for the $(128,64)$ polar
code, except this time, the gap between the neural-based and near-optimal
solutions is more significant, especially for low-to-medium $E_{b}/N_{0}$
regions. It is worth mentioning that for the $(128,64)$ polar code, during
training, both solutions have seen at most $10^{-8}\%$ of valid codewords,
proving that the models are very much able to learn a proper decoding rule
only by seeing a very small fraction of the data.

In the next section, we analyze the complexity involved in each solution and
compare them accordingly.

Figure 4: Error rate studies for two rate $1/2$ polar codes: $(64,32)$ (left)
and $(128,64)$ (right).

###  IV-C Complexity analysis

In this section, we study the complexity of each of the RNN-based and
Transformer-based implementations of the decoder, both at the training and
inference.

As shown in [18], the number of parameters (or weights) in a GRU unit
–including biases, which were not included in the original work [14]– is equal
to $3(n_{o}^{2}+n_{i}n_{o}+n_{o})$, where $n_{i}$ and $n_{o}$ depict the
number of inputs and outputs, respectively. In the case of a dense layer, the
number of weights is given by $n_{i}n_{o}+n_{o}$. Applying these results to
the RNN architecture gives the expression for the total number of weights of
the RNN-based decoder for an $(n,k)$ linear code:

$\mathds{W}_{\text{RNN}}=3(2d_{l}-1)\alpha^{2}r^{2}+3(r+d_{l}+\nicefrac{{k}}{{3}})\alpha
r+k,$ (16)

where $r\triangleq 2n-k$ is the size of the input vector given by
$[\,|\boldsymbol{l}|,\textrm{H}\boldsymbol{l}^{b}\,]$. For the codes and
hyperparameters selected, the following approximation holds to within a
$0.5\%$ error margin,

$\mathds{W}_{\text{RNN}}\approx 3((2d_{l}-1)\alpha^{2}+\alpha)r^{2},$ (17)

yielding a total number of weights that increases as $\mathcal{O}(r^{2})$ for
a fixed network depth $d_{l}$ and scaling factor $\alpha$.

Regarding the transformer architecture, the number of weights is computed with
respect to the embedding dimension $d_{e}$, the input size $r$, and the number
of encoder layers $N$:

$\mathds{W}_{\text{T}}=12Nd_{e}^{2}+(13N+r+3)d_{e}+(r+1)k+1.$ (18)

Similarly to the previous case, an approximation can be made to within an
error margin of $2\%$ for both studied codes:

$\mathds{W}_{\text{T}}\approx 12Nd_{e}^{2}+13Nd_{e}.$ (19)

Let us observe that, for the block sizes considered, the dominant terms do not
contain the code parameters $(n,k)$, producing a network structure that does
not depend on the code size as strongly as the RNN architecture. Observe,
however, that there is a hidden dependence on the block length if we consider
that larger codes may require larger embedding spaces and potentially more
encoder layers. These values were kept the same throughout both
implementations and hence, the number of parameters was almost exactly the
same.

The final number of weights for each decoder is included in Fig. 4. The
transformer solution has a clear advantage in that the number of weights
remains essentially the same as the input size increases, due to the embedding
layer of fixed dimension $d_{e}\\!=\\!128$. However, the RNN is much more
shallow than the transformer: it is composed of $d_{l}\\!=\\!5$ recurrent
layers, whereas the transformer has the embedding layer, $N\\!=\\!10$ encoders
–each consisting of two batch normalization layers, an attention layer and a
dense layer– and two final dense layers with batch normalization.
Additionally, as shown in [19], each self-attention mechanism entails a
computational complexity of $\mathcal{O}(r^{2}d_{e})$, which significantly
increases the inference time with respect to the RNN. Over several tests, the
RNN decoded approximately $8$ times faster than the transformer for the
$(64,32)$ polar code and $25$ times faster for the $(128,64)$ code222It must
be factored in that empirical values are deeply reliant on the software
implementation, hardware characteristics, and its parallel computing
capabilities. Nonetheless, the obtained decoding latencies are consistent with
the expected results..

##  V Conclusion

In this work, we have introduced a complete framework for decoding linear
block codes under a BICM setting. For this purpose, we have deduced an
equivalent bit-LLR binary channel model for the 8-PSK and 16-QAM modulation
techniques. Next, an SBND for higher-order modulation is proposed, which takes
as input the bit-LLRs instead of the BPSK-modulated signal as previous works
[6, 7]. Finally, two possible architectures were implemented and compared,
both in terms of performance and computational complexity.

##  Appendix A Proof of Theorem 1

First, note that since that each $L^{b}$ is a deterministic function of $L$,
and given that $P_{\boldsymbol{L}|\boldsymbol{C}}$ is a memoryless channel,
then so is $P_{\boldsymbol{L}^{b}|\boldsymbol{C}}$, i.e., for all
$\boldsymbol{l}_{b},\boldsymbol{c}\in\\{0,1\\}^{n}$,
$P_{\boldsymbol{L}^{b}|\boldsymbol{C}}(\boldsymbol{l}^{b}|\boldsymbol{c})=\prod_{i=1}^{n}P_{L^{b}|C}(l^{b}_{i}|c_{i}).$

To proceed with the proof, we will first prove that
$P_{L^{b}|C}(0|0)=P_{L^{b}|C}(1|1)$. Consider the following result

$\displaystyle
P_{L^{b}|C}(0|0)=\dfrac{1}{m}\sum_{s=1}^{m}P_{L^{b}|C,S}(0|0,s)$ (20)
$\displaystyle\overset{(a)}{=}$
$\displaystyle\dfrac{1}{m|\mathcal{X}^{s}_{0}|}\sum_{s=1}^{m}\sum_{x\in\mathcal{X}^{s}_{0}}P_{L^{b}|X,S}(0|x,s)$
(21) $\displaystyle=$
$\displaystyle\dfrac{1}{m|\mathcal{X}^{s}_{0}|}\sum_{s=1}^{m}\sum_{x\in\mathcal{X}^{s}_{0}}\int_{\mathds{C}}P_{L^{b},Y|X,S}(0,y|x,s)dy$
(22) $\displaystyle\overset{(b)}{=}$
$\displaystyle\dfrac{1}{m|\mathcal{X}^{s}_{0}|}\sum_{s=1}^{m}\sum_{x\in\mathcal{X}^{s}_{0}}\int_{\mathcal{Y}_{0}^{s}}P_{Y|X,S}(y|x,s)dy$
(23) $\displaystyle\overset{(c)}{=}$
$\displaystyle\dfrac{1}{m|\mathcal{X}^{s}_{0}|}\sum_{s=1}^{m}\sum_{x\in\mathcal{X}^{s}_{0}}\int_{\mathcal{Y}_{0}^{s}}P_{Y|X}(y|x)dy,$
(24)

where we define the decision region
$\mathcal{Y}_{0}^{s}\triangleq\\{y\in\mathds{C},f^{s}(y)>0\\}$, and where
$(a)$ follows the unformity of the constellation, while $(b)$ follows from the
Markov chain $C\leftrightarrow(X,S)\leftrightarrow L^{b}$, and $(c)$ from the
Markov chain $S\leftrightarrow X\leftrightarrow Y$.

Next, we use a common simplification of the bit-LLRs, commonly known as
_approximate LLRs_ , to write that:

$\displaystyle l$ $\displaystyle=$
$\displaystyle\log\biggl{(}\sum_{x\in\mathcal{X}_{0}^{s}}P_{Y|X}(y|x)\biggr{)}\\!-\\!\log\biggl{(}\sum_{x\in\mathcal{X}_{1}^{s}}P_{Y|X}(y|x))\biggr{)}$
(25) $\displaystyle\approx$
$\displaystyle\log\left(\max_{x\in\mathcal{X}_{0}^{s}}P_{Y|X}(y|x)\right)-\log\left(\max_{x\in\mathcal{X}_{1}^{s}}P_{Y|X}(y|x)\right)$
(26) $\displaystyle=$
$\displaystyle\dfrac{1}{\sigma^{2}}\bigl{(}\min_{x\in\mathcal{X}_{1}^{s}}||y-x||^{2}-\min_{x\in\mathcal{X}_{0}^{s}}||y-x||^{2}\bigr{)}.$
(27)

Hence, we can write that for all $y\in\mathcal{C}$ and all $s$,

$l^{b}=\mathds{1}\bigl{(}\min_{x\in\mathcal{X}_{0}^{s}}||y-x||^{2}\geq\min_{x\in\mathcal{X}_{1}^{s}}||y-x||^{2}\bigr{)}.$
(28)

Let us then consider the 8-PSK constellation with Gray mapping of Figure 5.
Taking into account the simplification in (28), we give in Figure 5 the
decision regions $\mathcal{Y}_{0}^{s}$ for $s\in[1:3]$.

Figure 5: Decision regions of the 8-PSK constellation

Let us now consider the case $s=1$. We have that
$\mathcal{X}^{1}_{0}=(\mathcal{X}^{1}_{1})^{\star}$ and
$\mathcal{Y}^{1}_{0}=(\mathcal{Y}^{1}_{1})^{\star}$. Thus, by exploiting one
of the symmetries of the normal Gaussian probability distribution
$P_{Y|X}(y|x)=P_{Y|X}(y^{\star}|x^{\star})$, one can easily prove that

$\displaystyle\sum_{x\in\mathcal{X}^{1}_{0}}\int_{\mathcal{Y}_{0}^{1}}P_{Y|X}(y|x)dy=\sum_{x\in\mathcal{X}^{1}_{1}}\int_{\mathcal{Y}_{1}^{1}}P_{Y|X}(y|x)dy.$
(29)

Similar results can be proved for $s=2$ by noticing that
$\mathcal{X}^{2}_{0}=-\mathcal{X}^{2}_{1}$,$\mathcal{Y}^{2}_{0}=-\mathcal{Y}^{2}_{1}$
and using the property $P_{Y|X}(-y|-x)$. Finally, for $s=3$, note that
$\mathcal{X}^{3}_{0}=\mathcal{X}^{3}_{1}e^{j\pi/2}$ and
$\mathcal{Y}^{3}_{0}=\mathcal{Y}^{3}_{1}e^{j\pi/2}$ along with the symmetry
$P_{Y|X}(ye^{j\phi}|xe^{j\phi})=P_{Y|X}(y^{\star}|x^{\star})$ for all $\phi$
yields the same result as (29). Hence, recalling that
$|\mathcal{X}^{s}_{0}|=|\mathcal{X}^{s}_{1}|$, it follows that

$\displaystyle P_{L^{b}|C}(0|0)$ $\displaystyle=$
$\displaystyle\dfrac{1}{m|\mathcal{X}^{s}_{0}|}\sum_{s=1}^{m}\sum_{x\in\mathcal{X}^{s}_{0}}\int_{\mathcal{Y}_{0}^{s}}P_{Y|X}(y|x)dy$
(30) $\displaystyle=$
$\displaystyle\dfrac{1}{m|\mathcal{X}^{s}_{1}|}\sum_{s=1}^{m}\sum_{x\in\mathcal{X}^{s}_{1}}\int_{\mathcal{Y}_{1}^{s}}P_{Y|X}(y|x)dy$
(31) $\displaystyle=$ $\displaystyle P_{L^{b}|C}(1|1).$ (32)

Hence, for the 8-PSK, the channel $P_{L^{b}|C}$ is a binary symmetric channel,
with crossover probability $q$ given by

$q=P_{L^{b}|C}(1|0)=\dfrac{1}{m}\displaystyle\sum_{s=1}^{m}P^{s}_{L^{b}|C}(1|0).$
(33)

Concerning the 16 QAM, we represent in Figure 6 the decision regions
$\mathcal{Y}_{1}^{s}$ for $s\in[1:4]$.

Figure 6: Decision regions of the 16-QAM constellation

It can be easily seen that, for $s=1$ and $s=3$, using the symmetries of
$\mathcal{X}^{s}_{c}$ and of the Gaussian distribution, one can write that

$\displaystyle\sum_{x\in\mathcal{X}^{s}_{0}}\int_{\mathcal{Y}_{0}^{s}}P_{Y|X}(y|x)dy=\sum_{x\in\mathcal{X}^{s}_{1}}\int_{\mathcal{Y}_{1}^{s}}P_{Y|X}(y|x)dy.$
(34)

However, for $s=2$ and $s=4$, the previous equality does not hold in the sense
that the integration over $\mathcal{Y}_{1}^{s}$ entails a larger clipping of
the Gaussian distribution than the integration over $\mathcal{Y}_{0}^{s}$.
However, if the SNR is not too low, SNR $\geq 0$ dB for a normalized 16-QAM
constellation, one can show that both integrations yield the same probability.
The proof follows then similarly to the 8-PSK case. ∎

##  Appendix B Proof of Theorem 2

Let us start with two properties of an $(n,k)$ block code. i) The pseudo-
inverse of a code $p_{inv}(\cdot)$ is defined by a $k\times n$ matrix
$\mathrm{A}$ such that $\mathrm{A}\boldsymbol{c}=\boldsymbol{u}$; ii) the
matrix $\mathrm{B}=[\mathrm{H}^{T},\mathrm{A}^{T}]$, where $\mathrm{H}$ is the
parity matrix of the code, is full rank, thus, invertible.

Next, we can write for $\boldsymbol{w}^{b}_{u}\in\\{0,1\\}^{k}$ and
$\boldsymbol{l}\in\mathds{R}^{n}$

$\displaystyle
P_{\boldsymbol{W}_{u}^{b}|\boldsymbol{L}}(\boldsymbol{w}^{b}_{u}|\boldsymbol{l})$
$\displaystyle=$ $\displaystyle
P_{\boldsymbol{W}^{b}_{u}|\,|\boldsymbol{L}|,\boldsymbol{L}^{b}}(\boldsymbol{w}_{u}^{b}|\,|\boldsymbol{l}|,\boldsymbol{l}^{b})$
(35) $\displaystyle=$ $\displaystyle
P_{\boldsymbol{W}^{b}_{u}|\,|\boldsymbol{L}|,\mathrm{H}\boldsymbol{L}^{b},\mathrm{A}\boldsymbol{L}^{b}}(\boldsymbol{w}_{u}^{b}|\,|\boldsymbol{l}|,\mathrm{H}\boldsymbol{l}^{b},\mathrm{A}\boldsymbol{l}^{b}),\quad$
(36)

where we have used the fact that $\mathrm{B}=[\mathrm{H}^{T},\mathrm{A}^{T}]$
is invertible. Next, recalling the result of Theorem 1 in (7), we have that

$\mathrm{A}\boldsymbol{L}^{b}=\mathrm{A}\boldsymbol{C}\oplus\boldsymbol{W}^{b}_{u}=\boldsymbol{U}\oplus\boldsymbol{W}^{b}_{u}.$
(37)

Since, $\boldsymbol{U}$ is i.i.d following a Bern$(0.5)$ distribution, and
since $\boldsymbol{W}^{b}_{u}$ is independent of $\boldsymbol{U}$, then
$A\boldsymbol{L}^{b}$ is Bern$(0.5)$ and is independent of
$\boldsymbol{W}^{b}_{u}$. Hence, it follows that

$P_{\boldsymbol{W}^{b}_{u}||\boldsymbol{L}|,\mathrm{H}\boldsymbol{L}^{b},\mathrm{A}\boldsymbol{L}^{b}}(\boldsymbol{w}_{u}^{b}||\boldsymbol{l}|,\mathrm{H}\boldsymbol{l}^{b},\mathrm{A}\boldsymbol{l}^{b})\text{=}P_{\boldsymbol{W}^{b}_{u}||\boldsymbol{L}|,\mathrm{H}\boldsymbol{L}^{b}}(\boldsymbol{w}_{u}^{b}||\boldsymbol{l}|,\\!\mathrm{H}\boldsymbol{l}^{b})$

which completes the proof. ∎

## References

  * [1] T. Gruber, S. Cammerer, J. Hoydis, and S. ten Brink, “On Deep Learning-Based Channel Decoding,” in _2017 51st Annual Conference on Information Sciences and Systems (CISS)_. IEEE, mar 2017.
  * [2] T. O’Shea and J. Hoydis, “An Introduction to Deep Learning for the Physical Layer,” _IEEE Transactions on Cognitive Communications and Networking_ , vol. 3, no. 4, pp. 563–575, dec 2017.
  * [3] E. Nachmani, Y. Be'ery, and D. Burshtein, “Learning to Decode Linear Codes Using Deep Learning,” in _2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, sep 2016.
  * [4] E. Nachmani and L. Wolf, “Autoregressive Belief Propagation for Decoding Block Codes,” 2021.
  * [5] W. Xu, Z. Wu, Y.-L. Ueng, X. You, and C. Zhang, “Improved Polar Decoder Based on Deep Learning,” in _2017 IEEE International Workshop on Signal Processing Systems (SiPS)_. IEEE, oct 2017.
  * [6] A. Bennatan, Y. Choukroun, and P. Kisilev, “Deep Learning for Decoding of Linear Codes - A Syndrome-Based Approach,” 2018.
  * [7] Y. Choukroun and L. Wolf, “Error Correction Code Transformer,” 2022.
  * [8] L. Lugosch and W. J. Gross, “Learning from the Syndrome,” in _2018 52nd Asilomar Conference on Signals, Systems, and Computers_. IEEE, oct 2018.
  * [9] E. Arikan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels,” _IEEE Transactions on Information Theory_ , vol. 55, no. 7, pp. 3051–3073, jul 2009.
  * [10] A. Caciularu, N. Raviv, T. Raviv, J. Goldberger, and Y. Be’ery, “perm2vec: Attentive Graph Permutation Selection for Decoding of Error Correction Codes,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 1, pp. 79–88, 2021.
  * [11] G. De Boni Rovella and M. Benammar, “Improved Syndrome-based Neural Decoder for Linear Block Codes,” in _2023 IEEE Global Communications Conference_ , 2023, pp. 5689–5694.
  * [12] G. Caire, G. Taricco, and E. Biglieri, “Bit-interleaved coded modulation,” _IEEE Transactions on Information Theory_ , vol. 44, no. 3, pp. 927–946, 1998.
  * [13] A. Alvarado, _On bit-interleaved coded modulation with QAM constellations_. Chalmers Tekniska Hogskola (Sweden), 2008.
  * [14] K. Cho, B. Merrienboer, C. Gulcehre, F. Bougares, H. Schwenk, and Y. Bengio, “Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation,” 06 2014.
  * [15] M. A. et al., “TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems,” 2015, software available from tensorflow.org. [Online]. Available: https://www.tensorflow.org/
  * [16] F. Chollet _et al._ , “Keras,” 2015. [Online]. Available: https://keras.io
  * [17] D. P. Kingma and J. Ba, “Adam: A Method for Stochastic Optimization,” 2014.
  * [18] R. Dey and F. M. Salem, “Gate-variants of Gated Recurrent Unit (GRU) neural networks,” in _2017 IEEE 60th International Midwest Symposium on Circuits and Systems (MWSCAS)_ , 2017, pp. 1597–1600.
  * [19] A. Vaswani _et al._ , “Attention is All you Need,” in _Advances in Neural Information Processing Systems_ , vol. 30. Curran Associates, Inc., 2017.