Deep Learning for Decoding of Linear Codes A Syndrome-Based Approach

arXiv:1802.04741v1 [cs.IT] 13 Feb 2018

Amir Bennatan* , Yoni Choukroun* and Pavel Kisilev
Huawei Technologies Co.,
Email: {amir.bennatan, yoni.choukroun, pavel.kisilev}@huawei.com

Abstract— We present a novel framework for applying deep
neural networks (DNN) to soft decoding of linear codes at
arbitrary block lengths. Unlike other approaches, our framework
allows unconstrained DNN design, enabling the free application
of powerful designs that were developed in other contexts. Our
method is robust to overfitting that inhibits many competing
methods, which follows from the exponentially large number
of codewords required for their training. We achieve this by
transforming the channel output before feeding it to the network,
extracting only the syndrome of the hard decisions and the
channel output reliabilities. We prove analytically that this
approach does not involve any intrinsic performance penalty, and
guarantees the generalization of performance obtained during
training. Our best results are obtained using a recurrent neural
network (RNN) architecture combined with simple preprocessing
by permutation. We provide simulation results that demonstrate
performance that sometimes approaches that of the ordered
statistics decoding (OSD) algorithm.

I. I NTRODUCTION
Interest in applying neural networks to decoding has existed
since the 1980’s [6], [7], [8]. These early works, however, did
not have a substantial impact on the field due to the limitations
of the networks that were available at the time. More recently,
deep neural networks were studied in [4], [5], [2].
A major challenge facing applications of deep networks to
decoding is the avoidance of overfitting the codewords encountered during training. Specifically, training data is typically
produced by randomly selecting codewords and simulating
the channel transitions. Due to the large number of codewords
(exponential in the block length), it is impossible to account for
even a small fraction of them during training, leading to poor
generalization of the network to new codewords. This issue
was a major obstacle in [4], [5], constraining their networks
to very short block lengths.
Nachmani et al. [2], [3] proposed a deep learning framework which is modeled on the LDPC belief propagation (BP)
decoder, and is robust to overfitting. A drawback of their
design, however, is that to preserve symmetry, the design is
constrained to closely mimic the message-passing structure
of BP. Specifically, the connections between neurons are
controlled to resemble BP’s underlying Tanner graph, as are
the activations at neurons. This severely limits the freedom
available to the neural networks design, and precludes the
application of powerful architectures that have emerged in
recent years [15].
* Both authors contributed equally to this work.

In this paper, we present a method which overcomes this
drawback while maintaining the resilience to overfitting of [2].
Our framework allows unconstrained neural network design,
paving the way to the application of powerful neural network
designs that have emerged in recent years. Central to our
approach is a preprocessing step, which extracts from the
channel output only the reliabilities (absolute values), and
the syndrome of its hard decisions, and feeds them into the
neural network. The network’s output is later combined with
the channel output to produce an estimate of the transmitted
codeword.
Decoding methods that focus on the syndrome are well
known in literature on algebraic decoding (see e.g. [12][Sec.
3.2]). The approach decouples the estimation of the channel
noise from that of the transmitted codeword. In our context
of deep learning, its potential lies in the elimination of the
need to simulate codewords during training, thus overcoming
the overfitting problem. A few early works that used shallow
neural networks have employed syndromes (e.g. [6]). However, these works did not discuss its potential in terms of
overfitting, presumably because the problem was not as acute
in their relatively simple networks. Importantly, their approach
does not apply in cases where the channel includes reliabilities
(mentioned above).
Our approach in this paper extends syndrome decoding
to include channel reliabilities, and applies it to overcome
the overfitting issue mentioned above. We provide a rigorous
analysis which proves that our framework incurs no loss
in optimality, in terms of bit error rate (BER) and mean
square error (MSE). Our analysis utilizes some techniques
developed by Burshtein et al. [14], Wiechman and Sason [13]
and Richardson and Urbanke [11][Sec. 4.11].
Building on our analysis, we propose two deep neural
network architectures for decoding of linear codes. The first
is a vanilla multilayer network, and the second a moreelaborate recurrent neural network (RNN) based architecture.
We also develop a preprocessing technique (beyond the abovementioned computation of the syndrome and reliabilities),
which applies a permutation (an automorphism) to the decoder
input to facilitate the operation of the neural network. This
technique builds on ideas by Fossorier et al. [9], [10] and
Dimnik and Be’ery [17] but does not involve list decoding.
Finally, we provide simulation results for decoding of BCH
codes which for the case of BCH(63,45), demonstrate performance approaches that of the ordered statistics algorithm
(OSD) of [9], [10].

Summarizing, our main contributions are:
1) A novel deep neural network training framework for
decoding, which is robust to overitting. It is based on the
extension of syndrome decoding that is described below.
2) An extension of syndrome decoding which accounts
for reliabilities. As with legacy syndrome decoding, we
define a generic framework, leaving room for a noiseestimation algorithm which is specified separately. We
provide analysis that proves that the framework involves
no loss of optimality, and that regardless of the noiseestimation algorithm, performance is invariant to the
transmitted codeword.
3) Two neural network designs for the noise-estimation algorithm, including an elaborate RNN-based architecture.
4) A simple preprocessing technique that applies permutations to boost the decoder’s performance.
Our work is organized as follows. In Sec. II we introduce
some notations and in Sec III we provide some bakground on
neural networks. In Sec. IV we describe our syndrome-based
framework and provide an analysis of it. In Sec. V we discuss
deep neural network architectures as well as preprocessing by
permutation. In Sec. VI we present simulation results. Sec. VII
concludes the paper.
II. N OTATIONS
We will often use the superscripts b and s (e.g., xb and xs ) to
denote binary values (i.e, over the alphabet {0, 1}) and bipolar
values (i.e., over {±1}), respectively. We define the mapping
from the binary to the bipolar alphabet, denoted bipolar(·), by
0 → 1, 1 → −1 and let bin(·) denote the inverse mapping.
Note that the following identity holds:
s

s

s

s

bin(x · y ) = bin(x ) ⊕ bin(y ),

s

s

∀x , y ∈ {±1}

(1)

where ⊕ denotes XOR. sign(x) and |x| denote the sign
and absolute value of any real-valued x, respectively, In
our analysis below, when applied to a vector, the operations
bipolar(·), bin(·), sign(·) and | · | are assumed to be applied
independently to each of the vector’s components.
III. B RIEF OVERVIEW OF D EEP N EURAL N ETWORKS
We now briefly describe the essentials of neural networks.
Our discussion is in no way comprehensive, and there are
many variations on the simple setup we describe. For an
elaborate discussion, see e.g. [15].

for an associated computational algorithm. The nodes are
called neurons and each performs (i.e., is associated with) a
simple computation on inputs to produce a single output. The
algorithm inputs are fed into the first-layer neurons, whose
outputs are fed as inputs into the next layer and so forth.
Finally, the outputs of the last layer neurons become the
algorithm output. Deep networks are simply neural networks
with many layers.
The inputs and output at each neuron are real-valued numbers. To compute its output, each neuron first computes an
affine function of its input (a weighted sum plus a bias). It then
applies a predefined activation function, which is typically
nonlinear (e.g., sigmoid or hyperbolic tangent), to render the
output.
The power of neural networks lies in their configurability.
Specifically, the weights and biases at each neuron are parameters which can be tailored to produce a diverse range
of computations. Typically, the network is configured by a
training procedure. This procedure relies on a sample dataset,
consisting of inputs, and in the case of supervised training, of
desired outputs (known as labels). There are several training
paradigms available, most of which are variations of gradient
descent.
Overfitting occurs typically when the training dataset is
insufficiently large or diverse to be representative of all valid
network inputs. The resulting network does not generalize well
to inputs that were not encountered in the training set.
IV. T HE P ROPOSED S YNDROME -BASED F RAMEWORK AND
ITS A NALYSIS
A. Framework Definition
We begin by briefly discussing the encoder. We assume
standard transmission that uses a linear code C. We let
m ∈ {0, 1}K denote the input message, which is mapped
to a codeword xb ∈ {0, 1}N (recall that the superscript b
denotes binary vectors). We assume that xb is mapped to a
bipolar vector x using the mapping defined in Sec. II, and x
is transmitted over the channel. We let y denote the channel
output. For convenience, we define m, xb , x and y to be
column vectors.
Decoder

𝐲𝒔
Channel
output

sign

bin

𝐲𝒃

𝐲
abs
Algorithm
inputs

|𝐲|

𝐻

𝐻𝐲 𝒃

Noise
estimation

F

Estimate
x

sign

𝐱

Algorithm
outputs

Fig. 2. Decoder framework. The final sign operation is omitted when the
system is designed to produce soft decisions. In Sec. V, we will implement
F using a neural network.
Layer 1

Fig. 1.

Layer 2

Layer 3

Layer 4

Layer 5

Illustration of a multi-layer neural network.

Fig. 1 depicts a simple multilayered neural network. The
network is a directed graph whose structure is the blueprint

Our decoder framework is depicted in Figure 2. The decoder’s main component is F, whose role is to estimate the
channel noise, and which we will later (Section V) implement
using a deep neural network. The discussion in this section,
however, applies to arbitrary F. The inputs to F are the

absolute value |y| and the syndrome Hyb , where H is a parity
check matrix of the code C, yb is a vector of hard decisions,
yb = bin(sign(y)) where bin(·) is simply the inverse of the
above defined bipolar mapping. The multiplication by H is
modulo-2. The output of F is multiplied (componentwise) by
ys , which is the sign of y. Finally, when interested in hard
decisions, we take the sign of the results and define this to be
the estimate x̂. This final hard decision step (which is depicted
in Fig. 2) is omitted when the system is required to produce
soft decisions.
B. Binary-Input Symmetric-Output (BISO) Channels
Our analysis in the following section applies to a broad class
of channels known as binary-input symmetric-output (BISO)
channels. This class includes binary-input AWGN channels,
binary-symmetric channels (BSCs) and many others. Our
definition below follows Richarson et al. [1][Definition 1].
Definition 1. Consider a memoryless channel with input alphabet {±1}. The channel is BISO if its transition probability
function satisfies:
Pr[Y = y | X = 1] = Pr[Y = −y | X = −1],

(2)

for al y the channel output alphabet, where X and Y denote
the random channel input and output (respectively).
An important feature of BISO channels is that their random
transitions can be modeled by [1][proof of Lemma 1],
Y = X · Z̃,

(3)

where Z̃ is random noise which is independent of the transmitted X. The tilde in Z̃ serves to indicate that this is an
equivalent statistical model, which might differ from the true
physical one. To prove (3), we simply define Z̃ to be a random
variable distributed as Pr[Y | X = 1] and independent of X.
The validity now follows from (2).

Outline. In Part 1 we neglect implementation concerns, and
focus on realizations of F that try to optimally estimate
the multiplicative noise z̃ (see (3)). By (3), given y, such
estimation is equivalent to estimation of x. We argue that
the pair |y| and Hyb is a sufficient statistic for estimation
of z̃. To see this, observe that y is equivalent to the pair |y|
and sign(y). The latter term, in turn, is equivalent to the pair
Hyb and Ayb , where yb is as defined in Sec. II and A is
a pseudo-inverse of the code’s generator matrix G. By (1)
and (3), yb = xb ⊕z̃b and so Ayb is the sum of the transmitted
message m = Axb and Az̃ (the projection of z̃ onto the code
subspace). We argue that Ayb is independent of the noise and
thus irrelevant to its estimation. This follows because m is
independent of z̃, and we assume it to be uniformly distributed
within the message space {0, 1}K .
To prove Part 2 of the theorem, we allow F to be arbitrary
and show that the decoder’s output can be modeled as f (z̃) · x
for some vector-valued function f (·). Thus, its relationship
with x (which determines the BER and MSE) depends on the
noise z̃ alone. To see why this holds, first observe that the
inputs to F (and consequently, its outputs) are dependent on
the noise z̃ only. This follows because the syndrome Hyb
equals Hz̃b . This in turns follows from the relation yb =
xb ⊕ z̃b and the fact that xb is a codeword, and so Hxb = 0.
By (3) and the bipolarity of x, the absolute value |y| equals
|z̃|. It now follows that the output of F is dependent on z̃
alone. Multiplication by sign(y) (see Fig. 2) is equivalent to
multiplying by sign(z̃) · x (by (3)) and the result follows.
V. I MPLEMENTATION USING D EEP N EURAL N ETWORKS
Theorem 1 proves that our framework does not intrinsically
involve a loss of optimality. To realize its potential, we propose
efficient implementations of the function F. In this section,
we discuss deep neural network implementations as well as a
simple preprocessing technique that enables the networks to
achieve improved performance.
A. Deep Neural Network Architectures

C. Analysis
We now show that the decoder framework involves no
penalty in performance in terms of metrics mean-squared-error
(MSE) or bit error rate (BER). That is, the decoder can be
designed to achieve any one of them. Importantly, it addresses
the overfitting problem that was described in Sec. I.
Theorem 1. The follwing holds with respect to the framework
of Sec. IV-A, assuming communication over a BISO channel:
1) The framework incurs no intrinsic loss of optimality, in
the sense that with an appropriately designed F, the
decoder can achieve maximum a-posteriori (MAP) or
minimum MSE (MMSE) decoding.
2) For any choice of F, the decoder’s BER and MSE,
conditioned on transmission of any codeword x, are both
invariant to x.
We provide an outline of the proof here, and defer the details
to Appendix I.

We consider the following two architectures:
1) Vanilla Multi-Layer: With this architecture, the neural
network contains an array of fully-connected layers as
illustrated in Fig. 3. It closely resembles simple designs [15] with the exception that we feed the network
inputs into each of the layers, in addition to the output of
the previous layer (this idea is borrowed from the belief
propagation algorithm).
The network includes 11 fully-connected layers, roughly
equivalent to the 5 LDPC belief-propagation iterations
as in [2]. We use rectified linear unit (ReLU) nonlinear
activation functions [15]. Each of the first 10 layers
consists of the same number of nodes (6N for block
length N = 64 and 15N for block length N = 127).
The final fully-connected layer has N nodes and produces
the network output, using a hyperbolic tangent arctivation
function.
2) Recurrent Neural Network (RNN): With this architecture, we build a deep RNN by stacking multiple recurrent

…

𝐲,
𝐻𝐲 𝑏

𝐳
Network
output

Network
input

Output
layer
Layer 1

Fig. 3.

Layer 2

Layer 10

codeword. With each training batch, we generate a new set of
noise samples. While this procedure produced our best results,
an alternative approach which fixes the training noise and uses
other techniques (e.g., dropout) to overcome overfitting the
noise, is worth exploring.
With the RNN architecture, the network produces multiple
outputs (at each time-step) and we use the following loss
function:

An instance of the Vanilla multi-layer architecture.

L=

hidden states on top of each other [19] as illustrated
in Fig. 4. RNNs realize a design which is equivalent
to a multi-layer architecture by maintaining a network
hidden state (memory) which is updated via feedback
connections. Note that from a practical perspective, this
renders the network more memory-efficient. In many
applications, this structure is useful to enable temporal
processing, and stacking RNNs as in Fig. 4 enables
operation at different timescales. In our setting, this
interpretation does not apply, but we nonetheless continue
to refer to RNN layers as “time steps.” Stacking multiple
RNNs produces an effect that is similar to deepening the
network.
We use Gated Recurrent Unit (GRU) [20] cells which
have shown peformance similar to well-known long shortterm memory (LSTM) cells [21], but have less parameters
due to the lack of a reset gate, making them a faster inference alternative. We use the hyperbolic tangent nonlinear
activation functions, the networks posses 4 RNN stacks
(levels), the hidden state size is set to 5N and the RNN
performs 5 time steps.

T
N
1 X X T −t
γ
HCE (z̃is , ẑis (t)),
N t=1 i=1

where HCE is the cross-entropy function, z̃is is the sign of
component i of the multiplicative noise and where ẑis (t) the
network output corresponding to codebit i at RNN time step
(layer) t. γ < 1 a discount factor (in our simulations, we used
γ = 0.5). The loss for the vanilla architecture is a degenerate
version of the RNN one, with time steps and discount factors
removed.
B. Preprocessing by Permutation
The performance of the implementations described above
can further be improved by applying simple preprocessing and
postprocessing steps at the input and output of the decoder
(respectively). Our approach is depicted in Fig. 5. Preprocessing involves applying a permutation to the components
of the channel output vector, and postprocessing applies the
inverse permutation to the decoder output. The approach draws
on ideas from Fossorier et al. [9], [10] and Dimnik and
Be’ery [17]. Note that the approach deviates from these works
in that it does not involve computing a list of vectors.
Decoder

𝑧(1)

𝑧(2)

𝐺𝑅𝑈𝑛 (1)

𝐺𝑅𝑈𝑛 (2)

…

…

𝑧(𝑇)
…

Select
permutation

𝐺𝑅𝑈𝑛 (𝑇)



…



y
𝐺𝑅𝑈2 (1)

𝐺𝑅𝑈2 (2)

…

𝐺𝑅𝑈2 (𝑇)

𝐺𝑅𝑈1 (1)

𝐺𝑅𝑈1 (2)

…

𝐺𝑅𝑈1 (𝑇)

…

𝒚 , 𝐻𝒚

𝑏

Fig. 4.
Our implementation of stacked RNN layers where GRUi (t)
represents the i-th level cell at RNN time step (layer) t.

To train the networks, we simulate transmission of the allone codeword (assuming the bipolar alphabet, {±1}). We
also simulate the multiplicative noise z̃, which in the case
of an AWGN channel, is distributed as a mean-1 Gaussian
random variable. In our training for Sec. VI, we set Eb /N0 to
4 dB. This was selected arbitrarily, and could potentially be
improved. We use Google’s TensorFlow library and the Adam
optimizer [16]. Testing proceeds in the same lines, except that
we use randomly generated codewords rather than the all-one

Decoder
of
Fig. 2

-1

x^

Fig. 5. Decoder with perprocessing and postprocessing components. Note
that in Appendix II we show that this decoder has an equivalent representation
which is a special case of Fig. 2.

Similar to [9], [10], our decoder selects the preprocessing
permutation so as to maximize the sum of the adjusted reliabilities of the first K components of the permuted channel output
vector. Borrowing an idea from [17], however, we confine our
permutations to subsets of the code’s automorphism group. We
assume that the parity check matrix, by which the syndrome in
Fig. 5 is computed, is arranged so that the last N −K columns
are diagonal and correspond to parity bits of the code.
We define the adjusted reliability of a channel component
yi , denoted R(yi ) by,
∆

R(y) = I(X; Y | |Y | = |y|).

(4)

well as the algorithm of [2]. However, a gap remains to the
OSD algorithm2 , which widens with Eb /N0 .
With respect to the number of codewords simulated, with
our algorithms, we simulated 105 codewords for each Eb /N0
point. With the OSD algorithm, we simulated 104 codewords
for each Eb /N0 point. With the BP algorithm we simulated
103 for each point.
The analysis of [2] also includes an mRRD framework,
into which their algorithm can be plugged to obtain superior
performance. While our algorithms can similarly be plugged
into that framework, our interest in this paper is in methods
whose primary components are neural networks.

1 Their

paper [3] does not include results for this case.

1

10

2

10

3

Belief propagation (BP)
Syndrome-based, vanilla
Syndrome-based, stacked RNN
Nachmani et al. best results
OSD, order 2
1.0

Fig. 6.

BER

VI. S IMULATION R ESULTS
Fig. 6 presents simulation results for communication with
the BCH(63,45) code over an AWGN channel. We simulated
our two architectures, namely syndrome-based vanilla and
stacked-RNN. Note that in this case, we did not simulate
permutations (Sec. V-B). Also plotted are results for the best
method of Nachmani et al. [2],[3], the belief propagation
(BP) algorithm, and for the ordered statistics decoding (OSD)
algorithm [10] of order 2 (for this algorithm we simulated
104 codewords for each Eb /N0 point). As can be seen from
the results, both our architectures substantially outperform the
BP algorithm. Our stacked-RNN architecture, like that of [3],
approaches the OSD algorithm very closely.
Fig. 7 presents results for the BCH(127,64) code. We
simulated our syndrome-based stacked RNN method, with and
without preprocessing. As can be seen, the preprocessing step
renders as a substantial benefit. Also plotted are results for
the BP and the OSD algorithms as well as the best results
of [2]1 . Both our methods outperform the BP algorithm as

10

BER

That is, R(y) equals the mutual information of random
variables X and Y , denoting the channel input and output,
respectively, conditioned on the event that the absolute value
|Y | equals |y|. X is uniformly distributed in {±1} and Y
is related to it via the channel transition probabilities. With
this definition, our permutation selection criterion is equivalent
to concentrating as much as possible of the channel capacity
within the first K channel output components.
Unlike [10], we borrow an idea from [17] and restrict
the set of allowed permutations to the code’s automorphism
group [18]. Permutations in this group have the property that
the permuted version of any codeword is guaranteed to be
a codeword as well. In our context, confinement to such
permutations ensures that the decoder input (the permuted
channel output) continues to obey the communication model,
namely being a noisy valid codeword. The decoder can thus
continue to rely on the code’s structure to decode.
When compared to framework of Fig. 2, the decoder of
Fig. 5 has the added benefit of knowing that the K first channel
outputs are consistently more reliable than the remaining
components. That is, the input exhibits additional structure
that the neural network can rely on.
In Appendix II we discuss permutations for BCH codes like
those we will use in Sec VI below, as well as efficient methods
for computing the optimal permutation. We also discuss formal
aspects related to applying the analysis of Sec. IV to the
framework of Fig. 5. Note that to achieve good results, the
added steps of Fig. 5 need to be included during training of
the neural network.
In Sec. VI we present simulation results for BCH(127,64)
codes with and without the above preprocessing method,
demonstrating the effectiveness of this approach. Note that
with the shorter block length BCH(63,45) codes, preprocessing was not necessary, and we obtained performance that
approaches the ordered statistics algorithm even without it.

2.0

2.5
Eb/No [dB]

3.0

3.5

4.0

BER results for a BCH (63,45) code.

10

1

10

2

10

3

10

4

10

5

Belief propagation (BP)
Nachmani et al. best results
Syndrome-based, stacked RNN, without preprocessing
Syndrome-based, stacked RNN, preprocessing
OSD, order 2
1

Fig. 7.

1.5

2

3

Eb/No [dB]

4

5

6

BER results for a BCH (127,64) code.

2 Note that for E /N of 4 dB or higher, we encountered no OSD errors
0
b
for BCH(127,64), in our simulations.

VII. C ONCLUSION
Our work in this paper presents a promising new framework
for the application of deep learning to error correction coding.
An important benefit of our design is the elimination of the
problem of overfitting to the training codeword set, which was
experienced by [4], [5]. We achieve this by using syndrome
decoding, and by extending it to account for soft channel
reliabilities. Our approach enables the neural network to focus
on the estimating the noise alone, rather than the transmitted
codeword.
It is interesting to compare our framework to that of
Nachmani et al. [2]. While their approach also resolves the
overfitting problem and achieves impressive simulation results,
it is heavily constrained to follow the structure of the LDPC
belief-propagation decoding algorithm. By contrast, our framework allows the unconstrained design of the neural network,
and our architectures are free to draw from the rich experience
that has emerged in recent years on neural network design.
Our simulation results demonstrate that our framework can
be applied to achieve strong performance that approaches
OSD. Further research will examine additional neural network architectures (beyond the RNN-based) and preprocessing
methods, to improve our performance further. It will also
consider the questions of latency and complexity.
We hope that research in these lines will produce powerful
algorithms and have a substantial impact on error correction
coding, rivaling the dramatic effect of deep learning on other
fields.
A PPENDIX I
P ROOF OF T HEOREM 1
In this section we provide the rigorous details of the proof,
whose outline was provided in Sec IV-C.
We begin with the following lemma.
Lemma 1. The following two claims hold with respect to the
framework of Sec. IV-A:
1) There exists a matrix A with dimensions K × N , such
that Axb = m for all m and xb defined as in Sec. IV-A
(recall that m and xb are both column vectors).
2) Let B be a matrix obtained by concatenating the rows of
H and A (i.e, B = [H T , AT ]T ). Then B has full column
rank, and is thus injective (one-to-one)
Note that in this lemma, we allow H to contain redundant,
linear dependent rows, as long as its rank remains N − K.
While we have not used such matrices in our work, the extra
redundant rows could in theory be helpful in the design of
effective neural networks for F.
Proof of Lemma 1. Part 1 of the lemma follows simply from
the properties of the generator matrix of the code C, denoted
here G. This matrix has full column-rank and dimensions N ×
K and satisfies xb = Gm. Thus, we can define A to be its
left-inverse, and Part 1 of the lemma follows.
To prove Part 2 of the lemma, we first observe that we
can assume without loss of generality the matrix H has
full row-rank. This is because by removing redundant (linear

dependent) rows from H we can obtain a full-rank paritycheck matrix, and such removal cannot affect the rank of the
corresponding B. Let D be a right-inverse of the matrix H,
whose existence follows from the fact that H has full rowrank. D has dimensions N × N − K. Consider the matrix
[G, D] (obtained by concatenating the columns of G and D).
 



H 
HG HD
B · [G, D] =
· G D =
A
AG AD


0 IN −K
=
,
IK
AD
where IK and IN −K denote the identity matrices of dimensions K and N − K, respectively. The equality HG = 0
follows from the orthogonality of the generator and parity
matrices, and equalities HD = IN −K , AG = IK follow from
the definitions above of A and D. The resulting matrix has
rank N , and thus B cannot have rank less than N .
We now proceed to prove Part 1 of the theorem. We use
the following notation: Vector are denoted by boldface (e.g.,
x) and scalars by normalface (e.g., x). Random variables are
upper-cased (X) and their instantiations lower-cased (x).
We use the notation of Fig. 2, replacing lowercase with
uppercase wherever we need to denote random variables.
Accordingly, we let X and Y denote random variables corresponding to the channel input and output (respectively). y
is the realized channel output observed at the decoder and
x ∈ {±1} an arbitrary value.
Consider the string of equations ending in (5). In (a), Yis is a
random variable defined as yis (Fig. 2) and equality Yis = yis
follows from the condition Y = y. In (b), we have relied
∆
on (3) to replace Z̃is = Xi · Yis , where Z̃is = sign(Z̃i ). In
∆
(c), |Y| is the absolute value of Y and Ys = sign(Y). In
(d), we have relied on (3) and the bipolarity of X to obtain
|Z̃| = |Y|. We have also defined and Yb and yb as in Fig. 2.
In (e), the matrix B was defined as in Lemma 1 and equality
follows by the fact that B is injective. In (f ), we have used the
definition B = [H T , AT ]T where A is as defined in Lemma 1.
In (g), we have decomposed Yb = Xb ⊕ Z̃b . This follows
from (1) and (3). In (h), we have relied on HXb = 0 which
follows from the fact that Xb is a valid codeword. We have
also replaced AXb = M, where M is the random message
(see Fig. 2), following
i Finally, in (i) we have made
h Lemma 1.
the observation that M ⊕ AZ̃b is independent of Z̃ and can
therefore be omitted from the condition. This follows because
M, being the transmitted message, is uniformly distributed in
{0, 1}K (see Sec. IV-A) and independent of AZ̃b (and Z̃).
The proof now follows from (5). To obtain the MAP
decision for Xi given y we can define the components of
N
F as follows, for s ∈ {0, 1}N −K and a ∈ R+ .
n
o
∆
Fi (a, s) = argmax Pr[Z̃is = z̃ | |Z̃| = a, H Z̃b = s]
z̃∈{±1}

By (5), we now have MAP(Xi ) = yis Fi (|y|, Hyb ). Similarly,
to obtain the MMSE estimate for Xi , we can define:
∆

Fi (a, s) = E[Z̃is | |Z̃| = a, H Z̃b = s]

Pr[Xi = x | Y = y]

(a)

=

Pr[Xi · Yis = xyis | Y = y]

(b)

=

Pr[Z̃is = xyis | Y = y]

(c)

=

Pr[Z̃is = xyis | |Y| = |y|, Ys = ys ]

(d)

=

Pr[Z̃is = xyis | |Z̃| = |y|, Yb = yb ]

(e)

=

Pr[Z̃is = xyis | |Z̃| = |y|, BYb = Byb ]

(f )

=

Pr[Z̃is = xyis | |Z̃| = |y|, HYb = Hyb , AYb = Ayb ]

(g)

=

Pr[Z̃is = xyis | |Z̃| = |y|, H[Xb ⊕ Z̃b ] = Hyb , A[Xb ⊕ Z̃b ] = Ayb ]

(h)

=

Pr[Z̃is = xyis | |Z̃| = |y|, H Z̃b = Hyb , M ⊕ AZ̃b = Ayb ]

(i)

Pr[Z̃is = xyis | |Z̃| = |y|, H Z̃b = Hyb ]

=

Recall from Fig. 2 that in this case the decoder is configured
to produce soft decisions and so the final sign operation is
omitted (see Fig. 2). This concludes the proof of Part 1 of the
theorem.
Turning to Part 2, in Sec IV-C we proved that the decoder’s
output can always be modeled as f (z̃) · x for some vectorvalued function f (·). With respect to the BER metric, the
indices where the vectors f (z̃) · x and x diverge coincide with
the indices where f (z̃) equals -1, and thus are independent of
x. With respect to the MSE metric (recall that in this case,
the sign operation in Fig. 2 is omitted), we have MSE =
kf (z̃)·x−xk2 = kf (z̃)−1k2 and thus the error is independent
of x.
A PPENDIX II
AUTOMORPHISMS OF BCH CODES
In this section, we discuss automorphisms of primitive
narrow-sense binary BCH codes codes [18], which include
the codes used in Sec VI.
With the above codes, the blocklength N equals 2m − 1
for some positive integer m. Codewords are binary vectors
c = [c0 , ..., cN −1 ] (i.e., defined over indices i = 0, ..., N − 1).
Permutations are bijective functions π : {0, ..., N − 1} →
{0, ..., N − 1}. Given a codeword c and a permutation π, we
define the corresponding permuted codeword cπ by cπi = cπ(i) .
The automorphism group of the above-mentioned BCH
codes includes [18] [pp. 233] permutations of the form:
πk,l (i) = 2k i + l

mod N

where k ∈ {0, ...m − 1} and l ∈ {0, ..., N − 1}. The inverse
−1
permutation πk,l
can be shown to equals πs,t shere s = m − k
mod m and t = −2s · l mod N .
We now address the question of efficiently finding the
optimal permutation πk,l in the sense of Sec. V-B, i.e., the
permutation that maximizes the sum of adjusted reliabilities
(see (4)) over the first K components of the permuted codeword. For fixed k = 0, the set of permutations π0,l (i), l =
0, ..., N − 1 coincides with the set of cyclic permutations.
Finding the optimal cyclic permutation can efficiently be
achieved by computing the cumulative sum of the adjusted
reliabilities. The case of arbitrary k is adressed by observing
that πk,l (i) = π0,l (πk,0 (i)). The optimal permutation can

(5)

be achieved by first applying the permutation πk,0 and then
repeating the above procedure for cyclic codes. Finally, the
optimal permutation across all k is computed by combining the
above results for each individual k = 0, ..., m−1. With respect
to computation latency, we note that the cumulative sum can
be computed in logarithmic time by recursively splitting the
range 0, ..., N − 1.
Strictly speaking, the decoder of Fig. 5 violates the framework of Sec. IV, because the preprocessing and postprocessing
steps are not included in that framework. In the case of
BCH codes, however, this formal obstacle is easily overcome
by removing the two steps and redefining F to compensate.
Specifically, the preprocessing permutation can equivalently
be realized within F by permuting the vector |y| and manipulating the syndrome using identities detailed in [18]. The
selection of the optimal permutation (which depends only
on |y|) and the postprocessing step can be redefined to be
included in F. The results of Sec. IV (particularly, resilience
to overfitting) thus carry over to our setting.
R EFERENCES
[1] T. Richardson and R. Urbanke, “The capacity of low-density paritycheck codes under message-passing decoding,” IEEE Trans. Inf. Theory,
vol. 47, pp. 599–618, Feb. 2001.
[2] E. Nachmani, E. Marciano, L. Lugosch, Loren, W.J. Gross, D. Burshtein
and Y. Be’ery, “ Deep learning methods for improved decoding of linear
codes,” arXiv:1706.07043, 2017
[3] E. Nachmani, Y. Bachar, E. Marciano, D. Burshtein and Y. Be’ery
“Near Maximum Likelihood Decoding with Deep Learning,” Int. Zurich
Seminar on Inf. and Comm., 2018
[4] T. J. O’Shea and J. Hoydis, “An introduction to machine learning
communications systems,” arXiv:1702.00832, 2017.
[5] T. Gruber, S. Cammerer, J. Hoydis, and S. t. Brink, “On deep learningbased channel decoding,” 51st Annual Conference on Inf. Sciences and
Systems (CISS), 2017.
[6] L. G. Tallini and P. Cull, “Neural nets for decoding error-correcting
codes,” Proc. IEEE Tech. Applicat. Conf. and Workshops Northcon95,
pp. 89–94, Oct. 1995.
[7] J.-L. Wu, Y.-H. Tseng, and Y.-M. Huang, “Neural network decoders for
linear block codes,” Int. Journ. of Computational Engineering Science,
vol. 3, no. 3, pp. 235–255, 2002.
[8] J. Bruck and M. Blaum, “Neural networks, error-correcting codes, and
polynomials over the binary n-cube.” IEEE Trans. Inf. Theory vol. 35(5),
pp. 976–987, 1989.
[9] M.P. Fossorier, S. Lin and J. Snyders. “Reliability-based syndrome
decoding of linear block codes.” IEEE Trans. Inf. Theory vol. 44(1)
pp. 388–398, Jan. 1998.

[10] M.P. Fossorier and S. Lin, “Soft-decision decoding of linear block codes
based on ordered statistics.” IEEE Trans. Inf. Theory, vol. 41(5), 1379–
1396, Sep. 1995.
[11] T. Richardson and R. Urbanke, “Modern coding theory,” Cambridge
university press. (2008)
[12] S. Lin and D. J. Costello. “Error control coding,” 2nd edition, Prentice
Hall, 2004.
[13] G. Wiechman and I. Sason, I., “Parity-check density versus performance
of binary linear block codes: New bounds and applications,” IEEE Trans.
Inf. Theory vol. 53(2), pp. 550–579, Jan. 2007.
[14] D. Burshtein, M. Krivelevich, S. Litsyn, S. and G. Miller, “Upper bounds
on the rate of LDPC codes,”. IEEE Trans. Inf. Theory vol. 48(9), pp.
2437–2449, Sep. 2002.
[15] I. Goodfellow, Y. Bengio, and A. Courville, “Deep learning.” MIT press,
2016.
[16] D. Kingma and J. Ba, “Adam: A method for stochastic optimization.”
arXiv preprint arXiv:1412.6980. Dec. 2014.
[17] I. Dimnik and Y. Be’ery, “Improved random redundant iterative HDPC
decoding.” IEEE Trans. Commu., 57(7), July 2009.
[18] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting
Codes. North-Holland, 1978.
[19] A. Graves, M. Abdel-rahman and G. Hinton, “Speech recognition
with deep recurrent neural networks” IEEE international conference on
acoustics, speech and signal processing (icassp) 2013.
[20] K. Cho, B. Van Merriënboer, C. Gulcehre , D. Bahdanau, F. Bougares
,H. Schwenk and Y. Bengio G. Hinton, “Learning phrase representations
using RNN encoder-decoder for statistical machine translation” arXiv
preprint arXiv:1406.1078 2014.
[21] S. Hochreiter and J. Schmidhuber, “Long short-term memory” Neural
computation 1997.

