1

BP-LED decoding algorithm for LDPC codes over
AWGN channels
Irina E. Bocharova1,2 , Boris D. Kudryashov1 , Vitaly Skachek2 ,
and Yauhen Yakimenka2
1
Department of Information Systems
St. Petersburg University of Information Technologies,
Mechanics and Optics
St. Petersburg 197101, Russia
Email: irinaboc@ut.ee, kudryashov boris@bk.ru

2

Institute of Computer Science
University of Tartu
Tartu 50409, Estonia
Email: { vitaly, yauhen } @ut.ee

arXiv:1705.09507v1 [] 26 May 2017

Abstract
A new method for low-complexity near-maximum-likelihood (ML) decoding of low-density parity-check
(LDPC) codes over the additive white Gaussian noise channel is presented. The proposed method termed beliefpropagation–list erasure decoding (BP-LED) is based on erasing carefully chosen unreliable bits performed in case
of BP decoding failure. A strategy of introducing erasures into the received vector and a new erasure decoding
algorithm are proposed. The new erasure decoding algorithm, called list erasure decoding, combines ML decoding
over the BEC with list decoding applied if the ML decoder fails to find a unique solution. The asymptotic exponent
of the average list size for random regular LDPC codes from the Gallager ensemble is analyzed. Furthermore, a
few examples of regular and irregular quasi-cyclic LDPC codes of short and moderate lengths are studied by
simulations and their performance is compared with the upper bound on the LDPC ensemble-average performance
and the upper bound on the average performance of random linear codes under ML decoding. A comparison with
the BP decoding performance of the WiMAX standard codes and performance of the near-ML BEAST decoding
are presented. The new algorithm is applied to decoding a short nonbinary LDPC code over the extension of the
binary Galois field. The obtained simulation results are compared to the upper bound on the ensemble-average
performance of the binary image of regular nonbinary LDPC codes.1

I. I NTRODUCTION
Since their rediscovery in 1995, low-density parity-check (LDPC) codes in conjunction with iterative decoding continue to attract attention of both researches and companies developing communication standards.
The main reason for this popularity of LDPC codes is their near-Shannon limit performance. Although
there exist asymptotic ensembles of LDPC codes approaching capacity under belief propagation (BP)
decoding, performance of finite length LDPC codes under BP decoding is inferior to their performance
under maximum-likelihood (ML) decoding. Moreover, the performance gap between ML and BP decoding
increases when signal-to-noise ratio (SNR) grows. Typically, LDPC codes under BP decoding suffer from
the so-called error floor phenomen, which is caused by both sub-optimality of the decoding algorithm
and by structural properties of the codes.
There exists a variety of techniques for lowering the error floors, and they are usually based on
identifying and removing specific structural configurations of the code Tanner graph called trapping
sets [2]. This can be done by modifying both the code parity-check matrix (without changing the code)
and the iterative decoding algorithm. For example, in [3], a list of trapping sets is computed and stored
in a look-up table. If the BP decoder fails, then a post-processing based on the list of known trapping
sets is performed. Techniques combining the trapping set detection with code shortening or bit-pinning
are presented in [4] and [5]. A technique based on eliminating small trapping sets by adding extra checks
to the code parity-check matrix is studied in [6]. A method for eliminating small trapping sets when
constructing an LDPC code is considered in [7]. The proposed method is applicable to both regular and
irregular LDPC codes.
1

Results of this work were partly published in [1]. This work is supported by the Norwegian-Estonian Research Cooperation Programme
through the grant EMP133.

2

Another approach for improving the performance of BP decoding stems from the information set
decoding. The most efficient methods for near-optimal decoding of linear codes are based on multiple
attempts for finding an error-free information set and subsequent reconstruction of a codeword by reencoding [8]–[10]. In [11] and [12], a post-processing in the form of bit-guessing is applied to the output
of the BP decoder in case of its failure. In particular, in [11], the bits that participate in the largest
number of unsatisfied checks are guessed, and BP decoding is repeated for each guessing attempt. An
improved algorithm for selecting the bits to be guessed is suggested in [12]. There, the post-processing
step is performed in stages. That technique leads to better than in [11] performance of near-ML decoding
at the cost of higher computational complexity. A method for decoding of nonbinary LDPC codes over
extensions of the binary Galois field based on the ordered statistics approach [10] is studied in [13].
Reconstruction of a codeword from a susbet of its symbols is equivalent to decoding over a binary
erasure channel (BEC). It was shown in [14] that ML decoding of an [n, k] LDPC code (where n is the
code length and k is the number of the information symbols) with ν = Θ(n) erasures is equivalent to
solving a system of linear equations of order ν, that is, it can be performed via the Gaussian elimination
with time complexity at most O(ν 3 ). By taking into account the sparsity of the parity-check matrix of
the codes, the complexity can be lowered to approximately O(ν 2 ) (see overview and analysis in [15] and
the references therein). Practically feasible algorithms with thorough complexity analysis can be found in
[16].
Low-complexity suboptimal decoding techniques for LDPC codes over a BEC are often based on the
following two approaches. In the first approach, redundant rows and columns are added to the original
code parity-check matrix (see, for example, [17], [18]). In the second approach, a post-processing is used
in case BP decoding fails [19]–[21].
The idea to reduce the problem of the decoding of an LDPC code over the AWGN channel to the
decoding of erasures has first appeared in [22]. In that work, BP decoding is followed by introducing artificial erasures and their subsequent decoding over the BEC, thus yielding a near-ML decoding algorithm.
The performance of the decoding algorithm in [22] strongly depends on the efficiency of the procedure
that converts the AWGN channel into the BEC or, in other words, the procedure for selecting the bits,
which are to be erased. The channel transformation can be considered successful only if non-erased bits
of the input vector are error-free.
In this paper, we propose a new decoding algorithm, which uses the ideas similar to [22] and [11],
but differs significantly both in a strategy for introducing erasures and in an erasure decoding algorithm.
A new list erasure decoding (LED) algorithm, which is applied to the result of the BP decoding in case
of its failure can, in principle, be combined with any type of soft decoding on the AWGN channel.
A distinguishing feature of the LED algorithm is an additional search step over a fixed size list of
unresolved bit positions which is applied if the ML decoder over the BEC fails to find a unique solution.
The proposed algorithm which we call BP-LED decoding is tested on the regular quasi-cyclic (QC) LDPC
code with optimized girth of the code Tanner graph [23] and on the irregular QC LDPC codes optimized
by using the technique in [24]. Both binary LDPC codes and binary images of nonbinary LDPC codes
are studied. Simulation results are presented. The comparison with the theoretical bounds on the ML
decoding performance is performed.
The rest of the paper is organized as follows. Some necessary definitions are given in Section II and
known bounds on the error probability of ML decoding are revisited in Section III. List-decoding algorithm
over the BEC is described in Section IV and its analysis for the Gallager ensemble of regular LDPC codes
is presented in Section V. Techniques for selecting bit positions to be erased are discussed in Section VI.
The near ML decoding procedure using LED is described in Section VII. The paper is concluded by the
discussion of the simulation results and their comparison with the bounds on the error probability of ML
decoding in Section VIII.

3

II. P RELIMINARIES
Consider the Gallager ensemble of (J, K)-regular LDPC codes of length n and dimension k [25]. In
this ensemble, an r × n random parity-check matrix H that consists of J strips H i of width M = r/J
rows each, i = 1, 2, . . . , J, where r = n − k. All strips are random column permutations of the strip where
the jth row contains K ones in positions (j − 1)K + 1, (j − 1)K + 2, . . . , jK, for j = 1, 2, . . . , n/K.
Rate R = b/c QC LDPC codes are determined by a (c − b) × c polynomial parity-check matrix of their
parent convolutional code [26]


h11 (D)
h12 (D)
...
h1c (D)
 h21 (D)
h22 (D)
...
h2c (D) 

H(D) = 
(1)
.
.
..
.


..
..
..
.
h(c−b)1 (D) h(c−b)2 (D) . . . h(c−b)c (D)
where hij (D) is either zero or a monomial entry, that is, hij (D) ∈ {0, Dwij } with wij being a nonnegative
integer, wij ≤ µ, and µ = maxi,j {wij } is the syndrome memory. The polynomial matrix (1) can be
represented via the (c − b) × c degree matrix


w11
w12
...
w1c
 w21
w22
...
w2c 
W =
(2)
.
.
.. 
...
 ..
..
. 
w(c−b)1 w(c−b)2 . . . w(c−b)c
with entries wij at the positions of the monomials hij (D) = Dwij . We write wij = −1 for the positions
where hij (D) = 0. By tailbiting the parent convolutional code to length M > µ, we obtain the binary
parity-check matrix (see [26, Chapter 2])

 T
H0 HT
. . . HT
HT
0 ...
0
1
µ−1
µ
T
 0 HT HT
. . . HT
0 


0
1
µ−1 H µ . . .

 .
..
..
..
...
...
..


.
.
.
T


(3)
H = T
T
T
T 
H
0
.
.
.
0
H
H
.
.
.
H
0
1
µ−1 
 µ
 ..
..
..
..
..
..
.. 
..
.
 .
.
.
.
.
.
. 
HT
1

...

HT
µ

0

...

0

...

HT
0

of the [M c, M b] QC LDPC block code of length M c and dimension M b, where H i , i = 0, 1, . . . , µ, are
binary (c − b) × c matrices in the series expansion
H(D) = H 0 + H 1 D + · · · + H µ Dµ
and 0 is the all-zero matrix of size (c−b)×c. Further by 0 we denote the all-zero matrix of an appropriate
size. If each column of H(D) contains J nonzero elements, and each row contains K nonzero elements
the QC LDPC block code is (J, K)-regular. It is irregular otherwise.
Another form of the equivalent [M c, M b] binary QC LDPC block code can be obtained by replacing
the nonzero monomial elements of H(D) in (1) by the powers of the circulant M × M permutation
matrix P , whose rows are cyclic shifts by one position to the right of the rows of the identity matrix.
The polynomial parity-check matrix H(D) (1) can be interpreted as a (c − b) × c binary base matrix
B labeled by monomials, where the entry in B is one if and only if the corresponding entry of H(D)
is nonzero, i.e.
B = H(D)|D=1
By viewing H as a biadjacency matrix [27], we obtain a corresponding bipartite Tanner graph. The
girth g is the length of the shortest cycle in the Tanner graph.

4

III. T IGHTENED B OUNDS ON THE ML DECODING ERROR PROBABILITY
In what follows, we compare the performance of the new decoding algorithm with the performance
of ML decoding over an AWGN channel. While keeping that in mind, in this section we revisit known
bounds on the error probability of ML decoding over the AWGN channel.
By using technique in [28] we compute the exact spectrum coefficients for the Gallager ensembles of
binary regular LDPC codes and binary images of nonbinary regular LDPC codes. By substituting the
computed coefficients into the existing bounds on the error probability of ML decoding, we obtain new
bounds, which are tighter than the previously known counterparts.
1) Lower bound: Since 1959, the Shannon bound [29] is still the best known lower bound on the ML
decoding error probability for codes used over the AWGN channel in a wide range of rates and lengths
[30]. Computational aspects of this bound are studied in [31] (see also [30] for overview of the results
in this area). In the sequel, we use approximation in [32] of the Shannon bound [29] which gives values
indistinguishable from the values of the bound in [29] for the frame error rate (FER) performance below
0.1 over the AWGN channel.
Let n, R, and σ denote the code length, code rate and standard noise deviation for an AWGN channel,
respectively. We use notations and formulas in [29] for the cone half-angle θ ∈ [0, π], which corresponds
to the solid angle of an n-dimensional circular cone, and for the solid angle of the whole space
n−1 Z θ
2π n/2
2π 2
(sin φ)n−2 dφ, Ωn (π) =
,
Ωn (θ) = n−1
Γ(n/2)
Γ( 2 ) 0
respectively. For a given code of length n and cardinality 2nR , the parameter θ0 is selected as a solution
of the equation
Ωn (θ0 )
= 2−nR .
Ωn (π)
Then, for the FER Psh (n, R, σ), we use approximation in [32]

n
G
cos θ0
G sin θ0 exp − 2σ1 2 + 2σ
1
1
Psh (n, R, σ) ≈ √ · √
,
(4)
·
G
nπ
sin2 θ0 − cos θ0
1 + G2 sin θ0
σ

√
1
where G = 2σ
cos θ0 + cos2 θ0 + 4σ 2 .
2) Upper bound: The tangential sphere bound (TSB) (also known as the Poltyrev upper bound [33])
is based on Gallager’s bounding technique. Given a transmitted vector, the decoding FER is represented
in the form
Pe = Pr(e, r ∈ R) + Pr(e, r ∈
/ R)
= Pr(e, r ∈ R) + Pr(e|r ∈
/ R)Pr(r ∈
/ R)
≤ Pr(e, r ∈ R) + Pr(r ∈
/ R),

(5)

where e is a decoding error event, r is the received vector and R denotes the region, whose choice
significantly influences the tightness of the bound (5). The tightest bound in [33] uses a conical region
R. It combines the ideas of spherical approach [34], which considers a spherical regions R, and the
tangential bound [35], which decomposes the noise vector into the radial and tangential components. We
present here the Poltyrev bound [33] for completeness:
 2 )
√ 
Z √n   ( X
x
rx
n
2
Pe ≤
f
Sw Θw (x) + 1 − χn−1
dx + Q
.
(6)
2
σ
σ
σ
−∞
w≤w
0

5

R∞
exp {−x2 /2} is the Gaussian probability density function, Q(x) = x f (x)dx,
 2

Z rx
y
rx − y 2
2
f
Θw (x) =
χn−2
dy ,
σ
σ2
βw (x)

 2 


r
x
r0 n
x
w
,
rx = r0 1 − √
w0 =
,
βw (x) = 1 − √
,
2
r0 + n
1 − w/n
n
n

Here f (x) =

√1
2π

Sw is the w-th spectrum coefficient of the code weight spectrum, n is the code length, and χ2n denotes
the probability density function of chi-squared distribution with n degrees of freedom.
Parameter r0 is a solution with respect to r of the equation

Z arccos µw (r)
X
√ Γ n−2
n−3
2 
sin
φ dφ = π ·
Sw
,
(7)
n−1
Γ
0
2
w : µw (r)<1
r
1
w
µw (r) = ·
.
r
1 − w/n
We note that in order to use the Poltyrev bound (6), one has to know the weight spectrum of the code.
In what follows, we use the exact coefficients of the average spectrum of the Gallager ensemble of
LDPC codes computed by the recurrent procedure presented in [28]. Let


H1
H =  ... 
HJ
be a parity-check matrix of an LDPC code randomly chosen from the Gallager ensemble. In our derivations
we use the generating function of a sequence of code weight enumerators. In a general case, the generating
function f (s) for a sequence of numbers a0 , a1 , .... is defined as follows:
f (s) =

∞
X

an s n ,

n=0

where s is a formal variable.
The generating function of the number of binary sequences x of weight w and length n satisfying the
equality
xH T
(8)
i = 0,
where i ∈ {1, 2, . . . , J}, is given by
G(s) =

n
X

Gn,w sw = g(s)

M

,

(9)

w=0

PK


where g(s) = i=0 gi s = (1 + s) + (1 − s)K /2, gi =
From (9), we obtain the recurrent relation
i

K

K
i



G1,i = gi , i = 0, 1, ..., K ,
K
X
Gj,w =
gi · Gj−1,w−i , j = 2, . . . , M,

if i is even, and gi = 0 otherwise.

(10)
w = 0, 1, . . . , jK .

(11)

i=0

The probability that (8) is valid for a random x of length n and weight w is equal to
p(w) =

Gn,w

n
w

(12)

6

for each of the matrices H i . The average number of codewords of length n and weight w is given by
 
 1−J
J
n
n
E{An,w } =
p(w) =
GJn,w ,
(13)
w
w
J
where p(w) is the probability that x satisfies (8) for all i = 1, 2, . . . , J simultaneously, and E{ · }
denotes the expected value of a random variable.
Similarly, average spectra for binary images of nonbinary LDPC codes over GF (2m ), m ≥ 2 can also
be computed via the generating function
G(s) = F (ρ) ρ=φ(s) ,
KM
X
F (ρ) =
Fw ρw = f (ρ)M ,

(14)
(15)

w=0


where f (ρ) = (1 + (q − 1)ρ)K + (q − 1)(1 − ρ)K /q (see [25, Chapter 5]) and
(1 + s)m − 1
,
q−1
i=1
 
1
m
=
q−1 i

ψ(s) =
ψi

m
X

ψi si =

(16)
(17)

(see [28] for details).
IV. L IST D ECODING OVER A BEC
Let H = (h1 , h2 , . . . , hn ) be an r × n parity-check matrix of a binary linear [n, k, dmin ] block code,
r = n − k, where hi denotes the i-th column of H. We use notation H I for the submatrix of H, whose
columns are indexed by the set I ⊆ {1, 2, ..., n}.
Consider a BEC with erasure probability ε > 0. The ML decoder corrects any pattern of ν erasures if
ν ≤ dmin − 1. If dmin ≤ ν ≤ n − k then the ML decoder can correct some erasure patterns. The number
of such correctable patterns depends on the code structure.
Let y = (y1 , y2 , . . . , yn ) be a received vector, where yi ∈ {0, 1, φ}, and the symbol φ represents erasures.
We denote by e = (e1 , e2 , . . . , en ) a binary vector, such that

1 if yi = φ
ei =
0 if yi ∈ {0, 1}
for all i = 1, 2, . . . , n. Let I(e) be a set of nonzero coordinates of e, |I(e)| = ν, and z = (z1 , z2 , ..., zν ) be
a vector of unknowns located in positions indexed by the set I(e). Let ỹ be the vector y with unknowns
zi in positions I(e).
Consider a system of linear equations ỹH T = 0 which can be reduced to
zH T
I(e) = s(e),

(18)

where s(e) = y I c (e) H T
I c (e) is a syndrome vector computed using non-erased positions of y and
I c (e) = {1, 2, . . . , n} \ I(e).
The solution of (18) is unique if ρ , rankH I(e) = ν, otherwise the full list L of candidate solutions
contains T = |L| = 2L elements, where L = ν − ρ.
If the code rate R approaches the BEC capacity C = 1 − ε, the typical number of erasures ν ≈ nε →
n(1 − R) = n − k. In that case, with high probability, the dimension L of the linear space of solutions
of (18) is positive.

7

0
1

1

0

ρ

ρ

HI(e) =
Iρ

1

1

A

1

ρA

ν
ρA
Fig. 1.

L=ν−ρ

Structure of the parity-check matrix after diagonalization and reordering of columns

If L > 0, by using Guassian elimination and column and row permutations, the submatrix H I(e) can be
represented in the form shown in Fig. 1. Here, by ρA we denote the rank of the system of linear equations
left after Gaussian elimination. It is easy to see that the first ρ − ρA positions are uniquely determined
and the other L + ρA positions satisfy ρA equations and cannot be determined uniquely. By assigning
arbitrarily values to L of these positions, we uniquely determine the remaining ρA positions. A set IAA
of the corresponding L columns of the submatrix A is called arbitrarily assigned (AA) positions.
Definition 1. List erasure decoder (LED) is a decoder for the BEC, which for a given input x with
ν erased positions, outputs a list L of codewords ĉ coinciding with the input word on all non-erased
coordinates.
A possible implementation of the LED is presented as Algorithm 1. In this algorithm, a row is called
a pivot if it is chosen to eliminate nonzero elements in other rows in a position which we call a leader.
The algorithm combines BP decoding over the erasure channel and the Gaussian elimination steps.
While there exists a row with one erasure, the BP decoding step is performed. If there are no rows with
one erasure, and there is a row which was not used as a pivot yet, the Gaussian elimination step with
respect to the leader is performed. Then, the algorithm switches back to the BP decoding step. These
alternating steps are performed until neither rows with one erasure nor unused pivots are left.
V. A NALYSIS OF THE LED ALGORITHM
As it is mentioned in Section II, we consider the Gallager ensemble of random (J, K)-regular LDPC
codes. A random r × n parity-check matrix which determines an (J, K)-regular LDPC code from this
ensemble can be represented in the following form:


H1
 H2 

H=
(19)
 ... 
HJ
where

1K 0K . . . 0K
 0K 1K . . . 0K 
H1 = 
.. . .
.. 
 ...
.
.
. 
0K 0K . . . 1K


(20)

8

Algorithm 1 LED algorithm for decoding of LDPC code on the BEC channel
Input: y = (y1 , · · · , yn ) ∈ {0, 1, φ}n .
Initialization:
IAA ← ∅;
I(e) ← {i : yi = φ} ;
ν ← |I(e)|;
s ← y I c (e) H T
I c (e) .
Step 1:
while there is a check j with one erased position yi do
yi ← sj ;
I(e) ← I(e)\{i};
ν ← ν − 1;
Update s;
if ν = 0 then goto Step 3;
end if
end while
Step 2:
if there is a check j with erasures not used as pivot then
Select a check j as a pivot;
Select yi = φ as a leader;
Gaussian elimination of row j:
Modify all checks which include position i;
Update s;
goto Step 1.
end if
Step 3: IAA ← I(e) , c ← y.
Step 4: Return c and IAA .
is of size M × n, M = r/J, aK = (a, a, ..., a) and all the matrices H i , i = 2, 3, . . . , J, are random
| {z }
K

permutations of the columns of H 1 .
In this section, we estimate the average size of the list L of candidate solutions in the system (18).
Denote by T a random variable, which represents this number of solutions. A set of solutions of
zH T
I(e) = 0

(21)

represents a coset of solutions of (18). Next we analyze (21) instead of (18) since all cosets have the
same number of solutions. Denote by H I(e),1 a submatrix of H I(e) of size M × ν consisting of its first
M = r/J rows. Next, we state the following lemma.
Lemma 1: Consider the Gallager ensemble of (J, K)-regular binary LDPC codes of length n and redundancy r = nJ/K  1 over the BEC with erasure probability ε > 0. Then, the conditional probability
that a row in H I(e),1 has zero weight given that there are ν  1 erasures and N0 < M rows have zero
K
weight does not grow with N0 and is upper-bounded by 1 − nν .
Proof. Let wi denote the weight of the i-th row of H I(e),1 , where i = 1, 2, ..., M . Then, the probability
p0 that the i-th row has zero weight given that ν > 0 erasures occurred can be estimated as

 
K
n−K
n−ν
n−ν
ν
K
p0 , Pr(wi = 0|ν) = n = n ≤
, i = 1, 2, ..., M.
(22)
n
ν
K

9

The conditional probability that N0 < M rows i1 , ..., iN0 of H I(e),1 have weight zero is given by:
Pr(wi1 = 0, ..., wiN0 = 0|ν) = Pr(wi1 = 0|ν)

N0
Y

i

Pr(wij = 0|wi1j−1 = 0, ν),

(23)

j=2
i

where wij−1
= (wi1 , wi2 , ..., wij−1 ).
1
It is easy to see that
Pr(wij =

i
0|wij−1
1

where the last transition is due to
 n−(j−1)K 
n−jK
ν
ν
 n−(j−2)K

n−(j−1)K
ν
ν


≤

n−jK
ν

n−(j−1)K
ν

= 0, ν) =

n − jK
n − (j − 2)K

ν

n−(j−1)K
ν

n−(j−2)K
ν





≤


= 1−

,

(24)

2K
n − (j − 2)K

ν
< 1.

We conclude that the probability in (24) does not grow when the number of conditions increases, that
is the following chain of inequalities holds
i

i

Pr(wij = 0|wij−1
= 0, ν) ≤ Pr(wij = 0|wij−2
= 0, ν) ≤ ... ≤ Pr(wij = 0|wi1 = 0, ν).
1
1
≤ Pr(wij = 0, ν) = p0 .

(25)


In what follows, we present the main theoretical result of this work.
Theorem 1: Consider the Gallager ensemble of (J, K)-regular binary LDPC codes of length n and
redundancy r = nJ/K  1 over the BEC with the erasure probability ε > 0. If there are ν  1
erasures, then the ensemble average list size in LED, E[T |ν], is upper-bounded by

r

ν K
ν−r
E [T |ν] ≤ 2
1+ 1−
.
n
Proof. Consider a random vector
T
s1 = zHI(e),1
.
i

Let Ij = {i1 , i2 , . . . , ij }, j ≤ M , be an arbitrary set of j indices. Denote by sij1 a subvector of j components
of the vector s indexed by Ij .
If ν erasures occurred, then the probability that the random vector z is a solution of the system
zH T
I(e),1 = 0 can be represented in the following form
Pr

T
zHI(e),1



= 0|ν = Pr(s1 = 0|ν) = Pr(si1 = 0|ν)

M
Y

i

Pr(sij = 0|sij−1
= 0, ν),
1

(26)

j=2
i

where sij−1
= (si1 , si2 , . . . , sij−1 ).
1
For the choice of a random vector z and a random parity-check matrix from the Gallager ensemble,
the probability of a zero syndrome component si is

1,
wi = 0
Pr(si = 0|wi , ν) =
,
(27)
1/2, wi > 0
where i ∈ {1, 2, . . . , M }. It follows from (27) that
Pr(si = 0|ν) = Pr(si = 0|wi = 0, ν)Pr(wi = 0|ν)
+ Pr(si = 0|ν, wi > 0)(1 − Pr(wi = 0|ν)).

(28)

10

By substituting (27) into (28), and by applying Lemma 1, we obtain
1+ 1−
1 + Pr(wi = 0|ν)
≤
Pr(si = 0|ν) =
2
2
In what follows, we show that


ν K
n

.

(29)

i

Pr(sij = 0|sij−1
= 0, ν) ≤ Pr(sij = 0|ν).
1
Consider the probability Pr(si = 0|sj = 0, ν), i, j ∈ {1, 2, . . . M }, i 6= j. By using the arguments
similar to those in (29), it is easy to obtain
1 + Pr(wi = 0|sj = 0, ν)
.
2
The conditional probability in the RHS of (30) can be represented as
Pr(si = 0|sj = 0, ν) =

Pr(wi = 0|sj = 0, ν) =

K
X

(30)

Pr(wi = 0|sj = 0, wj , ν)Pr(wj |sj = 0, ν)

wj =0

=

K
X

Pr(wi = 0|wj , ν)

wj =0

Pr(sj = 0|wj , ν)Pr(wj |ν)
.
Pr(sj = 0|ν)

(31)

Substitution of (27) into (31) yields
Pr(wi = 0|sj = 0, ν) =

Pr(wi = 0|wj = 0, ν)Pr(wj = 0|ν) +

PK

wj =0

Pr(wi = 0|wj , ν)Pr(wj |ν)

2Pr(sj = 0|ν)

. (32)

In (32), we took into account that Pr(wi = 0|sj = 0, wj , ν) = Pr(wi = 0|wj , ν).
Since Pr(wi = 0|ν) does not depend on i, from (32), by using Lemma 1 and (29), we obtain
Pr(wi = 0|sj = 0, ν) = Pr(wi = 0|ν)
≤ Pr(wi = 0|ν)

Pr(wi = 0|wj = 0, ν) + 1
2Pr(sj = 0|ν)

Pr(wi = 0|ν) + 1
= Pr(wi = 0|ν).
2Pr(sj = 0|ν)

From the last inequality and (30), we conclude that
Pr(si = 0|sj = 0, ν) ≤ Pr(si = 0|ν).
By using similar arguments it is easy to show that
Pr(sij =

i
0|sij−1
, ν)
1

1+ 1−
≤ Pr(sij = 0|ν) ≤
2


ν K
n

.

Then, from (26) we obtain


T
p1 , Pr zHI(e),1
= 0 ≤ Pr(sij = 0|ν)M ≤

1+ 1−


ν K
n

M

.
2M
Next, consider the submatrices H I(e),i , i = 2, 3, ..., J, consisting of rows (i − 1)M + 1, ..., iM ,
respectively. Recall that the strips are obtained by the independent random permutations. If ν erasures
occurred then the probability that a random vector z is a solution of the system zH T
I(e) = 0 is upperbounded as

K r
1 + 1 − nν
J
Pr(zH T
.
I(e) = 0|ν) ≤ p1 =
2r

11

TABLE I
E XAMPLE OF CRITICAL VALUES OF α = ν/r
Rate
(J, K)
α

1/5
(4,5)
0.9995

1/4
(3,4)
0.994

1/2
(4,8)
0.994

5/8
(3,8)
0.975

3/4
(3,12)
0.944

(4,16)
0.984

Notice that analogous to the derivations in [25] we ignore the fact that parity-checks of H I(e) are
linearly dependent. If ν is large enough (i.e. grows linearly with n) then a number of linearly dependent
rows in H I(e) is of order J and can be neglected.
Given that ν erasures occurred, we introduce a random variable χ(z) which is equal to 1 if z is a
solution of zH T
I(e) = 0, and is equal to 0 otherwise. More formally,

1, zH T
I(e) = 0
χ(z) =
.
0, zH T
I(e) 6= 0
Then, the average list size E[T |ν] (given that there are ν erasures) is equal to the average number of
vectors z which are solutions of zH T
I(e) = 0, namely

 r
ν K
1+ 1− n
X
X
ν
.
(33)
E[T |ν] =
E[χ(z)|ν] =
Pr(zH T
I(e) = 0|ν) ≤ 2
2r
z
z

Corollary 1: Denote by α = ν/r the normalized number of erasures. The asymptotic exponent of the list
size is determined by
E[L|ν]
log2 E[T |ν]
≤ lim
r→∞
r→∞
r
r

K !
J
≤ α − 1 + log2 1 + 1 − α
.
K

ϕ(α, J, K) =

lim

(34)

It is interesting to find a critical (largest) value of α, such that ϕ(α, J, K) = 0 or, in other words, to find
the relative number of erasures such that the average list size does not exceed 1.
We expect that for sparse matrices it holds α < 1. Examples of critical values of α for some code rates
R = 1 − J/K and for some values of K are shown in Table I. We can see that α is close to 1 even
for rather sparse parity-check matrices. This suggests that the allowable fraction of erasures ν/n can be
chosen close to 1 − R.
VI. C ONVERSION OF DECODING OVER AN AWGN CHANNEL INTO DECODING OVER A BEC
In [22], the main criteria for bits to be erased is the number of unsatisfied parity checks and low bit
reliability values. The authors present therein a set of thresholds which depend both on the code structure
and on the channel signal-to-noise ratio (SNR). The corresponding bit is erased if the number of unsatisfied
checks and the reliability value exceed the chosen thresholds.
We use a different strategy to transform the original problem of decoding over an AWGN channel
into a decoding problem over a BEC. By taking into account that only g/4 iterations of BP decoding
can be considered independent, we analyze bit reliability values obtained after g iterations. This allows
us to avoid overestimating the reliability values. An overview of various techniques for processing BP
reliability values for their further use in the near-ML decoding can be found in [13]. In our approach,
first we calculate the minimum absolute values of bit reliability values (over g iterations). Next, we sort
them in the increasing order. The L1 least reliable bits are erased.

12

After erasing the L1 least reliable bits, we introduce L2 additional erasures by using a set of masks
M = {Mi }i=1,...,N , where Mi ⊂ {1, 2, ..., n}, and |Mi | = L2 for i = 1, 2, . . . , N . We use pseudorandom pre-selected binary sequences of length 2L2 and weight L2 as masks. In our simulations we used
codewords of the first order Reed-Muller code [2m , m, 2m−1 ], m = log2 L2 + 1, as such masks. The masks
are applied to the next 2L2 least reliable entries (after L1 positions have already been erased). This step
in the algorithm is similar to the bit flipping step in the decoding algorithms such as [9], [10]. The choice
of the parameters L1 and L2 depends on the code length and the code rate. In our simulations, we have
chosen the total number of erasures L1 + L2 to be:
L1 + L2 = α(1 − R)n ,
where α ∈ [0.94, 1.07]. We found empirically that for the rate R ∈ {1/3, 1/2, 2/3}, for any code length,
we can choose 5 ≤ N ≤ 10 and L2 ∈ [0.15n, 0.18n].
The BP-LED decoding can also be applied to decoding of nonbinary LDPC codes over extensions of the
Galois fields. It was found experimentally that for the (2, 4)-regular LDPC code of length 16 over GF (28 )
(128 bits) constructed in [36], the choice α = 1.4 gives the best FER performance. In our experiments,
L2 was chosen to be 0.15n.
VII. LED- BASED ALGORITHM FOR AN AWGN CHANNEL
In this section, we show how the LED can be used for decoding of LDPC codes on an AWGN channel
with binary phase shift keying (BPSK) signaling. Let C = {cj }j=0,1,··· ,2k −1 be a binary [n, k, dmin ] LDPC
code. Assume that C is used with BPSK and coherent detection to communicate
over an AWGN channel.
√
The binary code symbol ci ∈ {0, 1} is mapped onto the signal vi = (2ci −1) Es , i = 1, 2, . . . , n, where Es
(j) (j)
(j)
is the signal energy. In the sequel we assume that Es = 1. Thus the codewords cj = (c1 , c2 , . . . , cn ),
(j) (j)
(j)
j = 0, 1, . . . , 2k − 1, are mapped onto bipolar sequences v j = (v1 , v2 , ..., vn ). Assume that v 0 is
transmitted. Then the discrete-time received signal is r = v 0 + n, where the noise vector n consists of
independent zero-mean Gaussian random variables with variance σ 2 = N0 /2. The SNR per information
bit is denoted by Eb /N0 = Es /(N0 R), where R = k/n is the code rate.
Assume that v = (v1 , v2 , ..., vn ) and r = (r1 , r2 , ..., rn ) are the transmitted and the received vectors,
respectively. Let Jmax ≤ 2L be the maximal number of allowed candidate solutions, and µ(·) be a decoding
metric. We use the Euclidean distance between the channel output r and 2c − 1 as the decoding metric
µ(c), where c is a candidate codeword. Alternatively, we can maximize the scalar product of r and 2c−1.
The new BP-LED decoding algorithm is presented as Algorithm 2.
In Algorithm 2, first, ν = L1 +L2 input symbols are erased (see below). Then LED is used for correcting
of ρ erasures and for making a list IAA of the AA positions.
The high-level idea of the proposed decoding algorithm is as follows. The algorithm consists of the
three main steps:
1) BP decoding.
2) In case of BP decoding failure, the unreliable positions are erased and LED is applied.
3) In case of the LED failure to find a unique solution, exhaustive search over a list of Jmax candidate
codewords is carried out.
These three steps are implemented as the following three subroutines in Algorithm 2.
• (v̂, x) = BPDECOD (r), where v̂ and x are vectors of hard decisions and of symbol reliabilities,
respectively, produced by the BP decoder. As it is mentioned above, in order to avoid overestimates
due to cycles in the Tanner graph, x is computed as the minimum of the absolute values of the
symbol reliabilities in the first g iterations.
• (c, IAA ) = LED(ξ), where ξ is a vector v with zeros on ν erased positions, and c is a vector of
hard decisions with erasures in L AA positions. Function LED is as discussed in Section IV.

13

•

cj = CANDIDATE(c, IAA , j). This subroutine generates the j-th candidate codeword from the full
list of solutions of (18). This is done by constructing a list W of Jmax binary words of length
L = |IAA | = log2 |L| ordered according to the ascending order of their weights. Then, the j-th
candidate is obtained by flipping AA bits in positions determined by the ones of the j-th element in
W.

Algorithm 2 Algorithm for decoding of LDPC code on the AWGN channel
Input: the vector of LLRs r = (r1 , . . . , rn ) ∈ Rn .
Let µopt ← ∞.
Step 1:
(v̂, x) = BPDECOD(r); ĉ = (v̂ + 1)/2;
if ĉH T = 0 then goto Step 6;
end if
Step 2:
ξ ← v̂ with zeros on L1 least reliable positions in x.
for i = 1 to N do
Step 3:
Use mask Mi to erase L2 non-erased positions
in ξ.
Step 4:
(c, IAA ) ← LED(ξ);
Initialize AA positions in c0 by hard decisions
from r.
Step 5:
for j = 1 to Jmax do
Compute codeword c0 from c and cj−1 ;
if µ(c0 ) < µopt then let ĉ ← c0 ; µopt ← µ(c0 );
end if
Generate next candidate cj = CANDIDATE(c, IAA , j);
end for
end for
Step 6: Return ĉ.

VIII. D ISCUSSION AND S IMULATION RESULTS
In this section, we compare experimentally the FER performance of BP decoding (with 50 decoding
iterations) with that of the BP-LED decoding. We also compare the experimental results with the tightened
theoretical upper bounds for binary random linear codes and for the Gallager ensembles of binary reqular
LDPC codes and binary images of nonbinary regular LDPC codes under ML decoding. Specifically, we
simulate the rate R = 1/2, 1/3, and 2/3 binary irregular LDPC codes of length n = 576 and the rate
R = 1/2 binary (4, 8)-regular LDPC code of length n = 96. We also simulate the LED-based decoding
for the rate R = 1/2 nonbinary LDPC code of length n = 16 over GF (28 ) [36] and compare its
performance with the FER performance of the generalized BP decoding [37] of the same code, and with
the corresponding theoretical upper and lower bounds.
The experimental results are shown in Fig. 6. While simulating the BP- LED decoding for nonbinary
codes over extensions of the binary field we recomputed probabilities of bit values via probabilities of
symbol values of GF(q), q = 2m , as follows

14

Pr(bi,j = 0) =

X

Pr(bi = λ),

j = 1, 2, ..., m ,

λ∈GF(q) : bi,j =0

Pr(bi,j = 1) = 1 − Pr(bi,j = 0) ,
where Pr(bi = λ) is the probability of the q-ary symbol bi to be equal λ, Pr(bi,j = l), l ∈ {0, 1},
j = 1, 2 . . . , m, is the probability that the j-th bit in the binary representation of bi is equal to l, and
bi = (bi,1 , ..., bi,m ) is the binary representation of bi .
All parity-check matrices of the simulated binary irregular LDPC codes were constructed by using the
optimization technique in [24]. The parity-check matrix of the (4, 8)-binary regular code was obtained
by reducing modulo 6 the degree matrix of the double Hamming LDPC code in [23]. In order to show
that the chosen codes are on a par with the best LDPC codes used in communication standards, the FER
performance of BP decoding for the standard WiMAX codes of rates R = 1/2 and R = 2/3 is presented
in Figs. 2 and 3. To facilitate the low complexity encoding, the degree matrices of all simulated codes
of length n = 576 have the so-called bi-diagonal form. The FER performance of the n = 96 LDPC code
was compared with the FER performance of near-ML BEAST-decoding [38].
In the simulations of the binary LDPC codes, the parameters α and β were optimized over the range
[0.94, 1.07] and [0.15, 0.18], respectively. Among the α(1−R)n erased positions, (α(1−R)−β)n positions
were selected according to the reliabilities, estimated by the BP decoding, and βn positions were selected
pseudo-randomly from the next 2β less reliable positions. Two values of the sizes of the pseudo-random
sets, N = 5 and N = 10, as well as two values of the list sizes, 28 and 216 , were simulated. All the
simulations were run until at least 100 LED-decoding block errors occurred. It turns out that for all codes,
except for the rate R = 2/3 irregular LDPC code, two sets of parameters: N = 5 and the list size 216 ;
N = 10 and the list size 28 ,— provide approximately the same coding gain of the LED-based algorithm
with respect to the BP decoding. For the rate R = 2/3 code, the LED-based algorithm with a larger list
size yields a slightly lower FER. In nonbinary case, the parameter α = 1.4 is selected, the number of
trials is N = 10 and the list size is 28 .
In order to compare the FER performance of the BP-LED decoding of both regular and irregular LDPC
codes with the FER performance of ML decoding, in Figs. 2–5 we present an upper bound (6) computed
for both the random linear codes and for the (J, K)-regular LDPC codes from the Gallager ensemble.
In case of irregular LDPC codes, the upper bound is computed for the parameters J and K chosen to
be equal to the average number of ones in columns and rows of the parity-check matrix, respectively.
The Shannon lower bound (4) is presented in the same figures as well. From the presented results, we
conclude that the coding gain is higher for the regular code than for the optimized irregular LDPC codes.
We also observe that for binary codes the coding gain grows with Eb /N0 . For higher rates, the FER
performance of the LED-based algorithm is closer to the corresponding upper bound on ML decoding
performance than for lower rates. It is easy to see that the coding gain compared to the FER performance
of BP decoding for the rate R = 1/2 WiMAX code is significant. However, the rate R = 2/3 WiMAX
code has the same FER performance as the optimized LDPC code. For the (4, 8)-regular LDPC code of
length n = 96, the coding gain of the new algorithm with respect to the BP decoding is approximately
two times smaller than the coding gain obtained by the near-ML BEAST decoding. In nonbinary case,
the coding gain does not grow with Eb /N0 . Such behavior of the FER performance can be explained by
using LED in combination with generalized BP decoding which is superior to conventional BP decoding.
Higher efficiency of generalized BP decoding reduces the gap in the FER performance of ML and BP
decoding. As a result near-ML decoding provides a smaller coding gain than that for the binary LDPC
codes.
The analysis of computational complexity of Steps 4 and 5 of Algorithm 2 is presented in [1]. Although
for a general linear code, the computational complexity of Step 4 would be a cubic function of the code
length n, the empirically observed average decoding time for LDPC codes grows near-linearly with the

15

100
Shannon bound
Random code
LDPC (4,8)-regular
BP
BP-LED
BP Wimax code

10-1

FER

10-2

10-3

10-4

10-5

10-6

1

1.2

1.4

1.6

1.8

2

2.2

2.4

2.6

2.8

3

E b /N0 , dB
Fig. 2. Bounds and FER performance for BP and near-ML decoding of R = 1/2 irregular LDPC codes of length n = 576, where the
following notations are used: “Shannon bound” denotes the bound (4), “Random code” denotes the bound (6) computed for ensemble of
linear codes, “LDPC (4,8)-regular” denotes the bound (6) computed for the Gallager ensemble of the (4,8)-regular LDPC codes.

code length. The computational complexity of Step 5 is proportional to the list dimension L, that is, it
grows linearly with the code length as well.
Although complexity grows near-linearly, the algorithm loses efficiency for large n since a typical
number L of AA positions grows as well. To maintain the decoding efficiency, parameters N and Jmax
should also be increased, which leads to impractically high computational time for lengths above 2000.
IX. C ONCLUSION
A new algorithm for near-ML decoding of LDPC codes over the AWGN channel is proposed and
analyzed. The new algorithm as well as BP decoding are simulated for both the regular and irregular
binary QC LDPC codes of several rates and for the binary image of a short nonbinary LDPC code over
the extension of the binary Galois field. The FER performance for binary and nonbinary LDPC codes is
compared to the improved union-type upper bound on the error probability based on precise coefficients
of the average spectra for the Gallager ensembles of binary regular LDPC codes and binary images
of nonbinary regular LDPC codes, respectively. The coding gain of the new decoding algorithm strongly
depends on the communication scenario. Decoding performance close to the performance of ML decoding
is demonstrated for the high rate LDPC codes as well as for the short length LDPC codes.
R EFERENCES
[1] I. E. Bocharova, B. D. Kudryashov, V. Skachek, and Y. Yakimenka, “Low complexity algorithm approaching the ML decoding of
binary LDPC codes,” in IEEE Int. Symp. on Inform. Theory (ISIT), 2016, pp. 2704–2708.
[2] T. Richardson, “Error floors of LDPC codes,” in 41st Allerton Conf. on Communication, Control and Computing, 2003.
[3] E. Cavus and B. Daneshrad, “A performance improvement and error floor avoidance technique for belief propagation decoding of
LDPC codes,” in IEEE 16th Int. Symp. on Personal, Indoor and Mobile Radio Commun. (PIMRC), vol. 4, 2005, pp. 2386–2390.
[4] Y. Han and W. E. Ryan, “Low-floor decoders for LDPC codes,” IEEE Trans. Commun., vol. 57, no. 6, pp. 1663–1673, 2009.
[5] Y. Zhang and W. E. Ryan, “Toward low LDPC-code floors: a case study,” IEEE Trans. Commun., vol. 57, no. 6, pp. 1566–1573, 2009.

16

100

10-1

FER

10-2

10-3

Shannon bound
Random code
LDPC (3,9)-regular
BP

10-4

BP-LED, list size=2 8
BP Wimax code
BP-LED, list size=2 16

1

1.2

1.4

1.6

1.8

2

2.2

2.4

2.6

2.8

3

E b /N0 , dB
Fig. 3. Bounds and FER performance for BP and near-ML decoding of R = 2/3 irregular LDPC codes of length n = 576, where the
following notations are used: “Shannon bound” denotes the bound (4), “Random code” denotes the bound (6) computed for ensemble of
linear codes, “LDPC (3,9)-regular” denotes the bound (6) computed for the Gallager ensemble of the (3,9)-regular LDPC codes.

100
Shannon bound
Random code
LDPC (4,6)-regular
BP
BP-LED

10-1

FER

10-2

10-3

10-4

0

0.5

1

1.5

2

2.5

E b /N0 , dB
Fig. 4. Bounds and FER performance for BP and near-ML decoding of R = 1/3 irregular LDPC codes of length n = 576, where the
following notations are used: “Shannon bound” denotes the bound (4), “Random code” denotes the bound (6) computed for ensemble of
linear codes, “LDPC (4,6)-regular” denotes the bound (6) computed for the Gallager ensemble of the (4,6)-regular LDPC codes.

17

FER

10-1

10-2

Shannon bound
Random code
LDPC (4,8)-regular
BP
BP-LED
BEAST-decoding

10-3

10-4

1

1.2

1.4

1.6

1.8

2

2.2

2.4

2.6

2.8

3

E b /N0 , dB
Fig. 5. Bounds and FER performance for BP and near-ML decoding of R = 1/2 (4, 8)-regular LDPC codes of length n = 96, where the
following notations are used: “Shannon bound” denotes the bound (4), “Random code” denotes the bound (6) computed for ensemble of
linear codes, “LDPC (4,8)-regular” denotes the bound (6) computed for the Gallager ensemble of the (4,8)-regular LDPC codes.

100
Shannon bound
Random code
NB LDPC (2,4)-regular
BP
BP-LED

10-1

FER

10-2

10-3

10-4

0.5

1

1.5

2

2.5

3

3.5

E b /N0 , dB
Fig. 6. Bounds and FER performance for BP and near-ML decoding of R = 1/2 nonbinary LDPC code of length n = 16 over GF (28 )
[36], where the following notations are used: “Shannon bound” denotes the bound (4), “Random code” denotes the bound (6) computed for
ensemble of linear codes, “ NB LDPC (2,4)-regular” denotes the bound (6) computed for the Gallager ensemble of binary images of the
(2,4)-regular NB LDPC codes.

18

[6] M. Jianjun, J. Xiaopeng, L. Jianguang, and S. Rong, “Parity-check matrix extension to lower the error floors of irregular LDPC codes,”
IEICE Trans. on Commun., vol. 94, no. 6, pp. 1725–1727, 2011.
[7] R. Asvadi, A. H. Banihashemi, and M. Ahmadian-Attari, “Lowering the error floor of LDPC codes using cyclic liftings,” IEEE Trans.
Inform. Theory, vol. 57, no. 4, pp. 2213–2224, 2011.
[8] E. Prange, “The use of information sets in decoding cyclic codes,” IRE Trans. Inform. Theory, vol. 8, no. 5, pp. 5–9, 1962.
[9] A. Valembois and M. Fossorier, “Box and match techniques applied to soft-decision decoding,” IEEE Trans. Inform. Theory, vol. 50,
no. 5, pp. 796–810, 2004.
[10] M. P. Fossorier and S. Lin, “Soft-decision decoding of linear block codes based on ordered statistics,” IEEE Trans. Inform. Theory,
vol. 41, no. 5, pp. 1379–1396, 1995.
[11] H. Pishro-Nik and F. Fekri, “Results on punctured low-density parity-check codes and improved iterative decoding techniques,” IEEE
Trans. Inform. Theory, vol. 53, no. 2, pp. 599–614, 2007.
[12] N. Varnica, M. P. Fossorier, and A. Kavcic, “Augmented belief propagation decoding of low-density parity check codes,” IEEE Trans.
Commun., vol. 55, no. 7, pp. 1308–1317, 2007.
[13] M. Baldi, F. Chiaraluce, N. Maturo, G. Liva, and E. Paolini, “A hybrid decoding scheme for short non-binary LDPC codes,” IEEE
Commun. Lett., vol. 18, no. 12, pp. 2093–2096, 2014.
[14] V. V. Zyablov and M. S. Pinsker, “Decoding complexity of low-density codes for transmission in a channel with erasures,” Problemy
Peredachi Informatsii, vol. 10, no. 1, pp. 15–28, 1974.
[15] D. Burshtein and G. Miller, “An efficient maximum-likelihood decoding of LDPC codes over the binary erasure channel,” IEEE Trans.
Inform. Theory, vol. 50, no. 11, pp. 2837–2844, 2004.
[16] E. Paolini, G. Liva, B. Matuz, and M. Chiani, “Maximum likelihood erasure decoding of LDPC codes: Pivoting algorithms and code
design,” IEEE Trans. Commun., vol. 60, no. 11, pp. 3209–3220, 2012.
[17] S. Sankaranarayanan and B. Vasic, “Iterative decoding of linear block codes: A parity-check orthogonalization approach,” IEEE Trans.
Inform. Theory, vol. 51, no. 9, pp. 3347–3353, 2005.
[18] N. Kobayashi, T. Matsushima, and S. Hirasawa, “Transformation of a parity-check matrix for a message-passing algorithm over the
BEC,” IEICE Trans. on Fundamentals of Electron., Commun. and Computer sciences, vol. 89, no. 5, pp. 1299–1306, 2006.
[19] H. Pishro-Nik and F. Fekri, “On decoding of low-density parity-check codes over the binary erasure channel,” IEEE Trans. Inform.
Theory, vol. 50, no. 3, pp. 439–454, 2004.
[20] G. Hosoya, T. Matsushima, and S. Hirasawa, “A decoding method of low-density parity-check codes over the binary erasure channel,”
in Proc. 27th Symposium on Information Theory and its Applications (SITA2004), 2004, pp. 263–266.
[21] P. M. Olmos, J. J. Murillo-Fuentes, and F. Pérez-Cruz, “Tree-structure expectation propagation for decoding LDPC codes over binary
erasure channels,” in IEEE Int. Symp. on Inform. Theory (ISIT), 2010, pp. 799–803.
[22] Y. Fang, J. Zhang, L. Wang, and F. Lau, “BP-Maxwell decoding algorithm for LDPC codes over AWGN channels,” in 6th Int.
Conference on Wireless Communications, Networking and Mobile Computing (WiCOM), 2010, pp. 1–4.
[23] I. E. Bocharova, F. Hug, R. Johannesson, and B. D. Kudryashov, “Double-Hamming based QC LDPC codes with large minimum
distance,” in IEEE Int. Symp. on Inform. Theory (ISIT), 2011, pp. 923–927.
[24] I. Bocharova, B. Kudryashov, and R. Johannesson, “Searching for binary and nonbinary block and convolutional LDPC codes,” IEEE
Trans. Inform. Theory, vol. 62, no. 1, pp. 163–183, Jan. 2016.
[25] R. G. Gallager, Low-density parity-check codes. M.I.T. Press: Cambridge, MA, 1963.
[26] R. Johannesson and K. S. Zigangirov, Fundamentals of convolutional coding. John Wiley & Sons, 2015.
[27] A. S. Asratian, T. M. J. Denley, and R. Haggkvist, Bipartite graphs and their applications. Cambridge University Press: Cambridge,
U.K, 1998.
[28] I. E. Bocharova, B. D. Kudryashov, V. Skachek, and Y. Yakimenka, “Average spectra for ensembles of LDPC codes and their
applications,” in IEEE Int. Symp. on Inform. Theory (ISIT), 2017, accepted for publication.
[29] C. E. Shannon, “Probability of error for optimal codes in a Gaussian channel,” Bell System Technical Journal, vol. 38, no. 3, pp.
611–656, 1959.
[30] I. Sason and S. Shamai, Performance analysis of linear codes under maximum-likelihood decoding: A tutorial. Now Publishers Inc,
2006.
[31] A. Valembois and M. P. Fossorier, “Sphere-packing bounds revisited for moderate block lengths,” IEEE Trans. Inform. Theory, vol. 50,
no. 12, pp. 2998–3014, 2004.
[32] J. J. Boutros and K. Patel. (2006) Performance of optimal codes at finite length. [Online]. Available: http://www.josephboutros.org/
publications/
[33] G. Poltyrev, “Bounds on the decoding error probability of binary linear codes via their spectra,” IEEE Trans. Inform. Theory, vol. 40,
no. 4, pp. 1284–1292, 1994.
[34] B. Hughes, “On the error probability of signals in additive white Gaussian noise,” IEEE Trans. Inform. Theory, vol. 37, no. 1, pp.
151–155, 1991.
[35] E. R. Berlekamp, “The technology of error-correcting codes,” Proc. of the IEEE, vol. 68, no. 5, pp. 564–593, 1980.
[36] B.-Y. Chang, D. Divsalar, and L. Dolecek, “Non-binary protograph-based LDPC codes for short block-lengths,” in IEEE Inform. Theory
Workshop (ITW), 2012, pp. 282–286.
[37] M. C. Davey and D. MacKay, “Low-density parity check codes over GF(q),” IEEE Commun. Lett., vol. 2, no. 6, pp. 165–167, 1998.
[38] I. E. Bocharova, M. Handlery, R. Johannesson, and B. D. Kudryashov, “A BEAST for Prowling in Trees,” IEEE Trans. Inform. Theory,
vol. 50, no. 6, pp. 1295–1302, Jun. 2004.

