IEICE TRANS. COMMUN., VOL.E105–B, NO.8 AUGUST 2022

894

INVITED SURVEY PAPERLDPC Codes for Communication Systems: Coding Theoretic
Perspective
Takayuki NOZAKI†,††a) , Member and Motohiko ISAKA†††b) , Senior Member

SUMMARY Low-density parity-check (LDPC) codes are widely usedin communication systems for their high error-correcting performance. Thissurvey introduces the elements of LDPC codes: decoding algorithms, code
construction, encoding algorithms, and several classes of LDPC codes.
key words: error-correcting code, low-density parity-check code1.

and non-binary LDPC codes (Sect. 9) since those classes
have good decoding performance and may be used in the
future. Section 10 provides parameters of LDPC codes usedin some communication standards. Finally, Sect. 11 summarizes the survey.

Introduction2.

Low-density parity-check (LDPC) codes [1], [2] are linear
codes defined by a sparse parity check matrix. The LDPC
codes are efficiently decoded with complexity O(n) by an
iterative decoding algorithm, e.g., sum-product algorithm.
The decoding error rates of well-designed LDPC codes approach the channel capacity under the sum-product algorithm [3]. Roughly speaking, LDPC codes have good decoding performance with small decoding complexity.
Nowadays, LDPC codes have been adopted by many
digital communication standards: IEEE 802.3 (10GBASET) [4], IEEE 802.11 (wifi) [5], IEEE 802.16 (WiMAX) [6],DVB-C2 [7], DVB-S2 [8], DVB-T2 [9], ATSC 3.0 [10],ISDB-S3 [11], CCSDS [12], and 5G New Radio [13].
This survey introduces the elements of LDPC codes andquasi-cyclic LDPC (QC-LDPC) codes, which are a classof LDPC codes used in modern communication systems.
Moreover, we briefly explain several classes of LDPC codes
which may be used in future communication systems.
Section 2 introduces the fundamentals of errorcorrecting codes, and the definition and properties of LDPC
codes. We explain the elements of LDPC codes: decoding algorithms (Sect. 3), construction (Sect. 4), and encoding algorithms (Sect. 5). Next, we describe two classes ofLDPC codes called protograph LDPC codes (Sect. 6) and
QC-LDPC codes (Sect. 7); QC-LDPC codes are adopted inmany digital communication standards and can be clearly
described in the context of protograph LDPC codes. Additionally, we explain spatially coupled LDPC codes (Sect. 8)
Manuscript received September 30, 2021.
Manuscript revised January 11, 2022.
Manuscript publicized February 10, 2022.
† The author is with Dept. of Informatics, College of Science,
Graduate School of Sciences and Technology for Innovation, Yamaguchi University, Yamaguchi-shi, 753-8512 Japan.
†† The author is with The Research Institute for Time Studies,
Yamaguchi University, Yamaguchi-shi, 753-8512 Japan.
††† The author is with the Dept. of Computer Science, Kwansei
Gakuin University, Sanda-shi, 669-1330 Japan.
a) E-mail: tnozaki@yamaguchi-u.ac.jpb) E-mail: isakam@kwansei.ac.jp
DOI: 10.1587/transcom.2021EBI0001

Preliminaries

Almost all the codes in practical use are linear codes overfinite fields Fq with q = 2m for a positive integer m. Binary
linear codes over F2 = {0, 1} are especially of interest, andthis survey focuses on them unless otherwise stated.
2.1

System Model, Channel Capacity and Coding

Suppose that an information vector that is represented byu = (u1, . . . , uk ) ∈ F2k is to be transferred from a sender
to a receiver. The encoder is usually an injective mappingfrom u to a codeword c = (c1, . . . , cn ) ∈ C, where C iscalled a code and is a subset of F2n . The codeword c may bedirectly transmitted to the channel, or as a modulated signal
sequence x = (x1, . . . , xn ) ∈ X, where we assume X = {±1}is a binary channel input alphabet. The rate of this coding
scheme is the number of information bits transferred perchannel use, and is defined as R = log2 2k /n = k/n.
The decoder determines the estimate for ĉ (equivalentlyû) for c (u) from the received vector y. Word error probability (WEP) is the probability that the estimate of ĉ does
not coincide with the original codeword c. Block-wise maximum a posteriori (MAP) decoding ĉ = arg maxc ∈ C P(c| y)minimizes WEP, and is equivalent to maximum-likelihood(ML) decoding ĉ = arg maxc ∈ C P( y |c) when codewords
follow the uniform distribution. Symbol error probability(SEP) (or bit error probability (BEP) for q = 2) is the probability of ĉi , ci averaged over all indices i = 1, . . . , n.
Minimum SEP is achieved by symbol-wise MAP decodingin which estimate of each symbol depends on the marginalized a posteriori
Í probability: ĉi = arg maxci ∈F2 P(ci | y) =arg maxa ∈F2 c ∈ C:ci =a P(c| y) for i = 1, . . . , n. However,these decoding criteria in general require exponentially large
computational cost in n, and more efficient approaches need
to be explored.
uc
encoderx
channelFig. 1y-decoder

Channel model.

Copyright © 2022 The Institute of Electronics, Information and Communication Engineersû or ĉ-

NOZAKI and ISAKA: LDPC CODES FOR COMMUNICATION SYSTEMS

Consider for simplicity a memoryless channel which
is characterized by the conditional probability distribution
PY |X of channel output Y given channel input X. It is
practically reasonable to assume that X follows the uniform
distribution on the channel input alphabet X. The inputconstrained capacity of a channel with respect to X is themutual information I(X; Y ), and is the supremum of achievable rate at which there exists a sequence of coding and decoding schemes with vanishing error probability [14]. Oneof the ultimate goals in coding theory is thus to explicitly
design encoder and decoder pair achieving or approaching
the capacity. For instance, on the binary erasure channel(BEC), each transmitted binary symbol is erased with probability p and it is received correctly otherwise. The capacity
is 1 − p, and accordingly reliable communication is possible
by properly designing codes of possibly large n if R < 1 − p.
On the binary-input additive white Gaussian noise channel (BI-AWGNC) in which Y = X + Z, X ∈ {±1}, andZ ∼ N (0, σ 2 ) is the Gaussian noise, reliable communicationof R = 1/2 is possible at Eb /N0 = 1/(2σ 2 R) > 0.2 (dB)
whereas BEP=10−5 is observed at 9.6 dB for the uncodedtransmission as will be seen in Sect. 2.4.
2.2

Linear Codes over Finite Field

An (n, k, dmin ) binary linear code C is defined as a kdimensional subspace of F2n , and each vector in C is called acodeword. Minimum distance dmin of C is the smallest Hamming distance between two distinct codewords in C, and isusually an important parameter with respect to error performance at low error rates. For linear codes, dmin is equal to
the smallest Hamming weight of any non-zero codewords.
For a given set of basis vectors {g1, . . . , gk } in C, where
gi = (gi,1, . . . , gi,n ), any codeword is their linear combination c = u1 g1 + · · · + uk gk , which can be regarded as an
encoding map from the information vector u to c. It is equivalently expressed as c = uG, where k × n matrix G = [gi, j ]is called a generator matrix of C. Note that encoding map is
not unique for a given linear code, and is called systematicwhen information symbols are in a codeword or c j = ui for
i = 1, . . . , k and some j ∈ {1, . . . , n}.
The dual code of C is defined as C ⊥ = {v : v cT = 0, c ∈C}, namely the set of all the vectors which are orthogonal toany codeword in C. This is indeed an (n − k)-dimensional
subspace of F2n with a set of basis vectors {h1, . . . , h n−k },where hi = (hi,1, . . . , hi,n ). An (n − k) × n matrix H = [hi, j ]is called a parity-check matrix of C, and GHT is a matrix ofall-zero elements by definition. It follows that designing alinear code C over F2 is reduced to specifying either G or H.
A vector v ∈ F2n is a codeword of C if and only if its
syndrome s = Hv T is an all-zero vector 0 = (0, · · · , 0). Eachparity-check equation hi cT = 0, i = 1, . . . , n − k for c ∈ C
represents a local constraint imposed on the code in the sensethat weighted sum of the symbols (exclusive-OR in the binarycase) in a codeword must be zero. Decoding for LDPC
codes in Sect. 3 iteratively performs computation on such
local constraints, aiming at determining codeword symbols

895

Fig. 2

An example of a Tanner graph.

subject to the global constraint of all-zero syndrome.
The linear codes are also defined by bipartite graphs
called Tanner graphs. A Tanner graph G = (V ∪ C, E) consistsof two sets of nodes, namely the set V of variable nodes andthe set C of check nodes, and the set E of edges. Each parity
check matrix is defined from a Tanner graph; Set hi, j = 1
if and only if the i-th check node ci is adjacent to the j-thvariable node v j . The j-th variable node associates to thej-th symbol of a codeword. The i-th check node represents
the constraint given by the i-th row of parity check matrix,
i.e., hi cT = 0. The degree of a node is the number of edges
connecting to the node. The degree of the j-th variablenode (resp. i-th check node) equals the number of non-zeroelements in the j-th column (resp. i-th row).
Example 2.1: Figure 2 depicts an example of a Tannergraph. The circles (resp. squares) in Fig. 2 represent the variable (resp. check) nodes. The corresponding parity checkmatrix is
1
©
­1
­
­0
«0

1
0
1
0

0
1
0
1

0
0
1
1

1
0
1
1

0
ª
1®
®.
1®
1¬

Linear codes, a tiny subset of all possible codes over F2n ,greatly facilitate the code description through G or H which
also enables encoding by linear operation. On the other hand,
decoding for general linear codes still require exponentiallylarge computational cost in n at least when (near-)optimum
performance is pursued. Accordingly, particular (class of)linear codes with certain structure for efficient decoding havebeen studied as outlined in Sect. 2.4. In this sense, the impact
of LDPC codes (and turbo codes in Sect. 2.4.2) was moresignificant with respect to decoding whose complexity isbasically linear in n.
2.3

Definition of LDPC CodeAn LDPC code is defined by a sparse parity check matrix
H ∈ F(n−k)×n
as follows:q
C = {c ∈ Fqn : HcT = 0T }.
It is called a binary (resp. non-binary) LDPC code if q = 2(resp. q > 2). Except in Sect. 9, we only consider the binary
LDPC codes.
The (c, d)-regular LDPC codes are defined by the Tanner graphs such that every variable node has degree c and every check node has degree d. The irregular LDPC codes aredefined by the Tanner graphs of which degrees of nodes are

IEICE TRANS. COMMUN., VOL.E105–B, NO.8 AUGUST 2022

896

chosen according to a pair
Í of degree distributions.
Í The degree distribution λ(x) = i λi x i−1 (resp. ρ(x) = i ρi x i−1 )characterizes the degrees of variable (resp. check) nodes,
where λi (resp. ρi ) denotes the fraction of edges connecting
to the variable (resp. check) nodes of degree i. For example,
the degree distribution pair of the code in Example 2.1 isλ(x) = 47 x + 37 x 2 and ρ(x) = 37 x 2 + 47 x 3 .
2.4

LDPC and Other Codes

In this subsection, some important codes in coding theory
and its practice are reviewed partly with a purpose of addressing the properties of LDPC codes.
2.4.1

BCH and Reed-Solomon Codes

The proof for direct part of the channel coding theorem
was not constructive and relies on the notion of random
coding [14], which unfortunately requires prohibitively large
decoding complexity for large n. Algebraic coding theory[15] was intensively studied for the first few decades as itallows efficient encoding and decoding based on the inherent
structure, including binary BCH codes, Reed-Solomon (RS)codes over Fq , as well as Reed-Muller (RM) codes. In
particular, RS codes have been used in optical discs andmany other applications.
BCH and RS codes ensure large dmin for given n and kwhen code length is limited, and are advantageous in termsof error probability in such a scenario when ML decoding
is performed [16]. However, algorithms based on the algebraic structure are mostly hard-decision bounded-distancedecoding in which received signals are quantized to symbols in Fq at decoder input and corrects up to b(dmin − 1)/2c
symbol errors. Efficient near-ML decoding has not been
available for large n especially for soft-decision decoding on
continuous-output channels.
Binary BCH codes are used as outer code for concatenation with inner LDPC code in recent broadcasting systems[7]–[11]. The role of the outer code is in handling residual
errors at the output of LDPC decoder, and is effective when
the latter suffers from relatively low weight error events inthe error floor region to be mentioned below.
The sum-product algorithm for LDPC codes in Sect. 3.1
performs poorly when it is applied to BCH codes as theparity-check matrices are not sparse. Neural belief propagation (BP) decoding is recently proposed to alleviate thisproblem by training weights incorporated in the decoding
formula on the neural network obtained by unrolling theTanner graph [17].
2.4.2Turbo Codes

It was just before the rediscovery of LDPC codes [18] whenefficiently decodable near-capacity coding scheme called
turbo codes was proposed in 1993 [19], and it has been subsequently used in third and fourth mobile communication
systems [20]. These codes are distinct from conventional

Fig. 3 Bit error rate of uncoded transmission, (32,16,8) RM code,(128,64,22) extended BCH code, R = 1/2 turbo code of n = 4000, 20000,(2, 4)-regular LDPC code of n = 500, 2500 over F28 (4000 and 20000 bitslong) over the BI-AWGNC.

schemes in that (i) simple codes are combined in a pseudorandom manner, and (ii) low-complexity iterative decoding
is available even for large block lengths [21]. Indeed, turbo
codes are parallel concatenation of two convolutional encoders, while LDPC codes can be regarded as consisting ofrepetition and single-parity check codes.
Figure 3 shows what coding theory encountered in themid 1990’s: bit error rate (BER) of (32, 16, 8) RM code,(128, 64, 22) extended BCH code both with near-ML decoding [22], R = 1/2 turbo codes of n = 4000 and n = 20000,(2, 4)-regular LDPC code over F28 of n = 500 and 2500
(corresponding to 4000 and 20000 bits long, respectively)
are presented together with the Shannon limit (capacity) for
R = 1/2 and BEP of uncoded transmission, all over the
BI-AWGNC.
Error probability of both turbo and LDPC codes under iterative decoding typically exhibits the following two
regions: waterfall region in which error probability drops
at certain channel parameter (Eb /N0 in the case of Fig. 3),
more sharply for larger block length n, and is a direct consequence of the behavior of iterative decoding; error floor
region in which error probability decreases more slowly andis observed when near-optimum decoding for the code isachieved by iterative decoder. In addition, decoding failure
due to certain topology in a Tanner graph may cause the error
floor for LDPC codes as stated in Sect. 4.
The error floor observed for BER of the turbo code
in Fig. 3 is due to small dmin , and it performs poorly withrespect to WEP. In contrast, dmin of LDPC codes tend to belarger and typical minimum distance of regular LDPC codes
grows linearly in n [2].
The underlying principle of decoding is shared bythese codes, and is an instance of more general framework of the sum-product algorithm [23]. Symbol-wise
MAP decoding is essentially performed at each decoder
associated with the two component
We may writeÎcodes.
nP(c| y) ∝ P( y |c)P(c) = P( y |c) i=1
P(ci ), where independence of the codeword symbols is assumed. The a priori

NOZAKI and ISAKA: LDPC CODES FOR COMMUNICATION SYSTEMS

probability P(ci ) for the symbol ci is provided as extrinsic
information from the other decoder, which in turn performs
symbol-wise MAP decoding but setting the a priori probability of the corresponding symbol as 0.5 [24]. This exchange of
extrinsic information between two decoders is iterated until
it finds a codeword or up to predefined number of iterations.
Decoding for LDPC codes in Sect. 3 follows a similar line
at variable nodes (repetition codes) and check nodes (single
parity-check codes) on a Tanner graph.
2.4.3

Polar and RM Codes

Polar codes proposed by Arikan are provably capacityachieving for binary-input symmetric discrete channels [25].
Rows of generator matrix G for polar codes of length⊗mn = 2m are subset
 of those in the Kronecker product F
1 0
of F =. In the successive cancellation (SC) de1 1
coder, the decision for each symbol in the information vector
u is made in order under the assumption that the alreadydecoded estimate is correct. By a proper choice of G anddecoding order, virtual k = nR channels associated with information symbols tend toward noise-free and thus resultsin capacity-achieving performance for asymptotically largen [26]. However, decrease of error probability in n is rather
slow under SC decoding. CRC-assisted list decoding was
proposed to overcome this problem in [27], and polar codes
are consequently competitive with LDPC codes even forpractical range of n. Together with such progress, polar
codes are deployed for the control channel in 5G New Radio[13]. BP decoding in Sect. 3.1 are also discussed for polar
codes in [28] and subsequent works.
We note that RM codes attract renewed interests motivated by the success of polar codes, as generator matrices
of RM codes with n = 2m consist of the rows of k largest
weights in F ⊗m . Recent results include the proof of optimality on the BEC [29] and near-ML performance with SC
or BP decoding for n = 128 RM codes by parallel decoding
based on automorphism group of the code [30].
3.

Decoding of LDPC Codes

We start with decoding for LDPC codes due to its importanceas mentioned in Sect. 2.2, and introduce encoding as well as
code designs in later sections.
Basically, LDPC codes are decoded by a message passing algorithm, which is a class of iterative algorithms. The
message passing algorithms work on the Tanner graphs of
LDPC codes. In the message passing algorithms, messages
are calculated on the nodes and conveyed by edges. Eachmessage represents an estimation of the bit of the associatedvariable node.
This section mainly describes two message passingalgorithms, called sum-product (SP) algorithm and bitflipping (BF) algorithm, both introduced by Gallager [1].
This section also provides some improved or simplified versions of the SP algorithm in Sect. 3.3. The SP and BF al-

897

gorithms have decoding complexity of O(n), which is muchsmaller than that of ML decoding or MAP decoding. Moreover, both algorithms are parallel, i.e., each node calculates
outgoing messages independently of each other.
Let Nv (i) (resp. Nc (i)) be the set of indices of the check(resp. variable) nodes which is adjacent to the i-th variable (resp. check) node, i.e., Nv (i) := { j : h j,i = 1} (resp.
Nc (i) := { j : hi, j = 1}). We write µ j→i for the message
from the j-th variable node to the i-th check node and ν j←i
for the message from the i-th check node to the j-th variable
node.
3.1

Sum-Product Algorithm

The SP algorithm is also referred to as the belief propagation(BP) algorithm. This algorithm is a soft-decision decoding
algorithm for the LDPC codes.
Suppose that a codeword c is modulated to a signal
sequence x ∈ {±1} n , where(+1, if ci = 0,xi =−1, if ci = 1.
Assume signal sequences are transmitted over the memoryless binary-input output-symmetric channel, whose channeltransition probability satisfies
PY |X ( y | x) =n
Ö

PY |X (yi |xi ),t=1

PY |X (y| + 1) = PY |X (−y| − 1).
For a channel transition probability PY |X (y|x), we define thelog-likelihood ratio (LLR) asl(y) := log

PY |X (y| + 1).
PY |X (y| − 1)(1)Note that l(y) := ∞ if PY |X (y| − 1) = 0, and l(y) := −∞ if
PY |X (y| + 1) = 0.
In the SP algorithm, each message takes a value in R ∪{±∞} and represents an estimation of the associate variablenode. Roughly speaking, the sign of a message gives theestimated symbol value of x, and the absolute value of amessage shows reliability of the estimation. Algorithm 1
gives the details. A toy example of the SP algorithm is in[31, pp.118–119].
3.2

Bit-Flipping Algorithm

The bit-flipping (BF) algorithm is a hard-decision message
passing algorithm, in which each message takes a value in F2 .
The BF algorithm is regarded as a quantized SP algorithm,
and hence has a lower time/space complexity but has a higher
decoding error rate than the SP algorithm.
The BF algorithm has many variations. Hence, we
introduce a typical BF algorithm in this survey. Denotethe degree of the i-th variable node, by deg(vi ). For each

IEICE TRANS. COMMUN., VOL.E105–B, NO.8 AUGUST 2022

898

Algorithm 1 Sum-Product Algorithm

Algorithm 2 Bit-Flipping Algorithm

Input Channel output y = (y1 , y2 , . . . , yn )Output Estimated codeword ĉ = (ĉ1 , ĉ2 , . . . , ĉn )Initialization For each i, the i-th check node emits ν j←i = 0 (j ∈ Nc (i)).
Decision For each j, the j-th variable node calculatesÍξ j = l(y j ) + k ∈Nv ( j)ν j←k ,(0, if ξ j > 0,ĉ j =
1, if ξ j < 0.

Input Channel output y = (y1 , y2 , . . . , yn )Output Estimated codeword ĉ = (ĉ1 , ĉ2 , . . . , ĉn )Initialization Set decoding round t as 0. For each j, the j-th variable nodestores(0, if PY | X (y j | + 1) > PY | X (y j | − 1),sj =1, if PY | X (y j | + 1) < PY | X (y j | − 1).

In the case of ξ j = 0, we need to use some tie-break rule, e.g.,
set 0 with probability 1/2 and 1 with probability 1/2. If ĉ satisfies
Hĉ T = 0T , the algorithm outputs ĉ and stops.
Variable Node Calculation For each j, the j-th variable node calculatesµ j→i (i ∈ Nv (j)) as follows:Íµ j→i = l(y j ) + k ∈Nv ( j)\{i} ν j←k
Check Node Calculation For each i, the i-th check node calculates ν j←i(j ∈ Nc (i)) as follows:Îν j←i = 2 tanh−1 k ∈Nc (i)\{ j } tanh(µk→i /2) ,exp(2x)−1

where tanh(x) := exp(2x)+1 and tanh−1 (x) = 12 ln 1+x
1−x . Go back to
the decision step.

position i of variable node and each decoding round t, set
two thresholds bi,t , di,t , where (deg(vi ) − 1)/2 < bi,t ≤deg(vi ) − 1 and deg(vi )/2 < di,t ≤ deg(vi )† .
Algorithm 2 gives the details. Note that the check nodecalculation satisfies the following
property; If the check nodeÍconstraint is satisfied, i.e., k ∈Nc (i) µk→i = 0, ν j←i = µ j→iholds; Otherwise, ν j←i , µ j→i holds. In other words, themessages from the check nodes represent whether the checkconstraints are satisfied. The variable node calculation istransformed as follows:
1 + s j , if | {k ∈ Nv (j) \ {i } : ν j←k , s j } | ≥ b j , t ,µ j→i =
sj ,Otherwise.

In words, the variable nodes flip their values if they receive
many unsatisfied messages.
Careful design of flipping rules in the BF algorithm
narrows the performance gap with the SP algorithm. The
weighted BF algorithm [32] was proposed for decreasing
the decoding error rate of the BF algorithm. Wu et al. [33]showed that the weighted BF algorithm is a simplificationof the min-sum algorithm (given in Sect. 3.3.2). Wadayama
et al. [34] proposed the gradient descent BF (GDBF) algorithm, which has a higher decoding performance than theweighted BF algorithm. This algorithm decides the flipping
rule from the gradient descent for a non-convex optimization problem derived from a decoding problem. Moreover,Wadayama et al. [34] modified the GDBF algorithm with asmall noise factor to escape from local optimum points of
the optimization problem. Recently, Savin [35] proposed
the GDBF algorithm with momentum by considering thepast updates.
† A simple BF algorithm adopts b

deg(vi ) for all t.

i,t = deg(vi ) − 1 and di,t =The i-th variable node emits the storing value to all the neighboring
check nodes, i.e., µ j→i = s j (i ∈ Nv (j)).
Check Node Calculation Increment t by 1. For each i, the i-th checknode outputs messagesÍν j←i = k ∈Nc (i)\{ j } µk→i .
Decision For each j, the j-th variable node calculates


0,



ĉ j = 1,


sj ,


if | {k ∈ Nv (j) : ν j←k = 0} | ≥ d j , t ,if | {k ∈ Nv (j) : ν j←k = 1} | ≥ d j , t ,Otherwise.

If ĉ satisfies Hĉ T = 0T , the algorithm outputs ĉ and stops.
Variable Node Calculation For each j, the j-th variable node outputs
messages


0,



µ j→i = 1,


sj ,


if | {k ∈ Nv (j) \ {i } : ν j←k = 0} | ≥ b j , t ,if | {k ∈ Nv (j) \ {i } : ν j←k = 1} | ≥ b j , t ,Otherwise.

Go back to check node calculation.

3.3

Other Decoding Algorithms

3.3.1

Fast Convergence Algorithms

The original BP algorithm is parallel, i.e., it simultaneously
exchanges all variable-to-check messages and all check-tovariable messages. Hence, the original BP algorithm iscalled flooding schedule. As serial schedule algorithms, layered BP [36] and shuffled BP [37] algorithms are proposedto speed up the convergence, i.e., to reduce number of iterations for decoding. The convergence speed depends on
the update order of messages. Lee and Ueng [38] proposed
BP scheduling based on maximum mutual-information, andAslam et al. [39] presented the informed fixed scheduling.
3.3.2

Low Complexity Algorithms: Min-Sum Algorithm

The SP algorithm requires large computational complexity
by tanh(x) and tanh−1 (x) in the check nodes calculation.
Fossorier et al. [40] proposed the min-sum algorithm, which
realizes the check node calculation by:Îν j←i =
min | µk→i | ,k ∈Nc (i)\{ j } sign(µk→i )k ∈Nc (i)\{ j }

where



 1,

sign(x) := 0,


 −1,


x > 0,
x = 0,
x < 0.

NOZAKI and ISAKA: LDPC CODES FOR COMMUNICATION SYSTEMS

Namely, outgoing message ν j←i is simply the incoming
message with the smallest absolute value at the i-th checknode (except the one from j-th variable node), while thesign of ν j←i remains the same as that in the SP algorithm.
Complexity reduction by eliminating tanh(·) computationis achieved at the cost of some performance degradation
which is caused by the greater value of |ν j←i | than that in
the SP algorithm. To remedy this loss, modifications to
min-sum algorithm were proposed by Chen et al. in [41]and the references therein. Normalized min-sum algorithm
scales the message by multiplying ν j←i by a constant 0 <α < 1. Offset min-sum algorithm alternatively subtracts a
constant β > 0 so that the magnitude of ν j←i is replaced bymax{mink ∈Nc (i)\{ j } | µk→i | − β, 0}.
Other low complexity algorithms are summarized in[42, Sect. 5.5].
3.3.3

Quantization

In the hardware implementation, floating-point numbers forthe messages require large space of circuit and power consumption. Hence, the quantization of messages is an important topic. An extreme example of a quantized (or finite
alphabet) iterative decoding algorithm is bit-flipping, whichuses one-bit messages.
Elaborate non-uniform quantization has better decoding
error rates than the uniform quantization (e.g., see [43]). Lee
et al. [43] designed the message quantization for the sumproduct algorithm based on the mutual information. Chenet al. [41] gave the quantized offset/normalized min-sum
algorithm. For the binary symmetric channel, Planjery et al.
[44] proposed a finite alphabet iterative decoding algorithm,
which is not a mimic of the SP decoding algorithm, andshowed that the algorithm has a lower error floor than the SP
algorithm.
4.

Construction of LDPC Codes

In the construction of LDPC codes, initially, we should improve the decoding error rates in the waterfall region. Next,
we lower the decoding error rates in the error floor region.
Each channel model is characterized by some channel
parameters, e.g., the channel parameter of the BEC is thechannel erasure probability p. For simplicity, we assume
that a channel model characterized by a single parameter.
Then, there exists a supremum of the channel parametersuch that the bit decoding error rate goes to 0 as the code
length tends to infinity [1]–[3]. This supremum is called
decoding threshold [3].
To improve the performance in the waterfall region, we
should optimize the macro-structure of the LDPC code, e.g.,
the pair of degree distribution for the irregular LDPC codes.
For the optimization of the macro-structure, we search a code
ensemble† with a good decoding threshold. The decoding† Roughly speaking, a code ensemble is a set of codes.

For
example, the (3, 6)-regular LDPC code ensemble is the set of all(3, 6)-regular LDPC codes.

899

thresholds are determined by an asymptotic analysis technique called density evolution [3] or its approximation called
extrinsic information transfer (EXIT) chart [45]. The decoding error rates in the waterfall regions are also estimated bya finite-length analysis technique called finite-length scaling[46]–[49] for the several code ensembles and channel models. The macro-structure is typically optimized via linear
programming or differential evolution.
To lower the error floor region, we should optimize themicro-structure of the LDPC code, i.e., the local structure of
the Tanner graph: small cycles, approximate cycle extrinsic
message degree (ACE) [50], stopping sets [51], and trapping
sets [52]. We should remove such local structures to lower
the error floor. Hu et al. [53] proposed progressive edge
growth (PEG), a greedy algorithm to construct a Tannergraph without small cycles. This algorithm is extended toremoving small ACE [54], small stopping sets [55], and small
trapping sets [56]. He et al. [57] proposed an improved PEG
algorithm called multi-edge metric-constrained PEG.
5.

Encoding of LDPC Codes

One might think that encoding of LDPC codes is easy byusing its generator matrix. However, even if the parity checkmatrix is sparse, corresponding generator matrices are not always sparse. Hence, the encoding algorithm using generator
matrices requires O(n2 ) complexity in general.
There are two approaches to reduce the encoding complexity for LDPC codes: (i) considering an efficient encoding algorithm for arbitrary LDPC codes and (ii) designingefficiently encodable LDPC codes.
5.1

Efficient Encoding Algorithms

Suppose encoding is systematic in the narrow sense, i.e., thecodeword c is split into the information part u and the parity
part p as c = (u | p). Moreover, suppose the parity checkmatrix is full rank, i.e., rank(H) = n − k.
Encoding algorithms for LDPC codes are divided into
two stages: preprocessing stage and encoding stage. The
preprocessing stage transforms the parity check matrix H
into a systematic form Hsys = (HI | HP ) by arranging thecolumns and rows†† , where HI is an (n− k)× k matrix and HP
is an (n − k) × (n − k) non-singular matrix. Since HcT = 0T
holds, we have
HP pT = −HI uT .

(2)

The encoding stage generates the codeword c corresponding
to a message u by solving Eq. (2). For reducing the encoding complexity, HP should have a form such that Eq. (2) isefficiently solved.
†† To keep decoding performance of the code and the sparsityof the parity check matrix, the preprocessing stage transforms H
only by arranging the columns and rows, i.e., row and column
permutations.

IEICE TRANS. COMMUN., VOL.E105–B, NO.8 AUGUST 2022

900

properties and performance are compared in [62].
5.2

Fig. 4

5.1.1

An approximate triangular matrix. Black dots represents 1.

Encoding Algorithm Based on Approximate Triangular Matrix

Richardson and Urbanke [51] proposed the first efficient encoding algorithm. The preprocessing stage transforms H
into approximate triangular matrix, described as:HI,u T C
HATM =,
HI,l D E




HI,u
T C
, T is an (n − k − g) ×
where HI =, HP =
HI,l
D E(n − k − g) upper triangular matrix, and the sizes of othermatrices are determined accordingly by the size of T. DefineΦ := (E − DT−1 C) and store Φ−1 . Figure 4 illustrates anapproximate triangular matrix. We see that the right of thismatrix is approximate triangular.
We split parity part p into ( p1 | p2 ), where p1 and p2
are of length n − k − g and g, respectively. The encoding
stage is described as follows:

Linear-Time Encodable LDPC Codes

Repeat accumulate (RA) [63] codes and irregular repeat
accumulate (IRA) codes [64] are known as sub-classes ofLDPC codes with a fast encoding structure. Accumulate
repeat accumulate (ARA) codes [65] are also fast encodable LDPC and can be viewed as precoded IRA codes.
Those codes are known to be represented by protographs[66] (Sect. 6) but suffer from high error floors.
Quasi-cyclic LDPC (QC-LDPC) codes (Sect. 7) are efficiently encodable by shift-register-adder-accumulator circuits [67].
6.

Protograph LDPC Codes

1. Compute pT2 = Φ−1 (DT−1 HI,u −HI,l )uT . Here, the details of this step are follows; (i) Calculate aT1 = HI,u uT ;(ii) Solve a2 by backward substitution TaT2 = aT1 ;(iii) Set aT3 = DaT2 and bT = HI,l uT ; (iv) Calculate
pT2 = Φ−1 (aT3 − bT ).

Protograph LDPC codes [66] are a sub-class of LDPC codes,
more precisely a sub-class of multi-edge type LDPC codes[68]. Some protograph LDPC codes, e.g., ARA codes, areencodable in O(n) [63]–[65], [69]. Moreover, well-designed
protograph LDPC codes, e.g., accumulate repeat jaggedaccumulate (ARJA) codes [69], [70], has a good decoding
performance in both waterfall and error floor regions.
A protograph is a Tanner graph (V ∪ C, E) with a relativesmall number of nodes, where parallel edges are allowed.
The adjacency matrix for a protograph is called a base matrix
B = (bi, j ), where bi, j is a number of edges between ci andv j . A copy-and-permute operation to protograph provides
larger derived graphs. This operation copies the protograph
N times and permutates the edges within each bundle, a setof edges generated from the same edge of the protograph.
The derived graph becomes the Tanner graph of a protograph
LDPC code. In other interpretation, we get a parity checkmatrix of a protograph LDPC code by replacing the (i, j)-thentry of the base matrix into the sum of bi, j random N × N
permutation matrices for each (i, j).

2. Solve p1 by backward substitution; TpT1 = −CpT2 −HI,u uT .

Example 6.1: Figure 5(a) depicts the protograph with abase matrix

Note that the backward substitution to sparse triangular matrix requires O(n) complexity. Since the Φ−1 is dense g × g
matrix in general, the multiplication in step 1-(iv) requiresO(g 2 ). It is known [51] that g is proportional to n but smallenough. Hence, the encoding complexity of this algorithmis O(n + g 2 ).
5.1.2

Other Encoding Algorithms

The following algorithms are proposed to reduce the timecomplexity or encoding time. Kaji [58] considered an
encoding algorithm based on LU-factorization. Shibuya[59] proposed an encoding algorithm based on the blocktriangularization via Dulmage-Mendelsohn decomposition.
Nozaki [60] presented a parallel encoding algorithm based onblock-diagonalization. Iketo and Nozaki [61], [62] proposedan encoding algorithm based on block-triangularization. The

2
©
­1
«0

1
1
1

0
1
1

0
ª
0® .
1¬

By copying four times, we get Fig. 5(b). By permutating eachbundle in Fig. 5(b), we obtain a derived graph as in Fig. 5(c).
The parity check matrix corresponding to the derived graphin Fig. 5(c) is
1
© 0
­
­ 1
­
­ 0
­
­ 0
­
­ 1
­ 0
­
­ 0
­
­ 0
­
­ 0
­
­ 0
« 0

0
1
1
0
1
0
0
0
0
0
0
0

0
1
0
1
0
0
1
0
0
0
0
0

1
0
0
1
0
0
0
1
0
0
0
0

1
0
0
0
0
0
0
1
1
0
0
0

0
0
0
1
0
1
0
0
0
0
1
0

0
1
0
0
0
0
1
0
0
1
0
0

0
0
1
0
1
0
0
0
0
0
0
1

0
0
0
0
1
0
0
0
1
0
0
0

0
0
0
0
0
0
1
0
0
0
0
1

0
0
0
0
0
1
0
0
0
0
1
0

0
0
0
0
0
0
0
1
0
1
0
0

0
0
0
0
0
0
0
0
1
0
0
0

0
0
0
0
0
0
0
0
0
1
0
0

0
0
0
0
0
0
0
0
0
0
1
0

0
0 ª®
0 ®®
0 ®®
0 ®
®
0 ®
.
0 ®®
0 ®®
0 ®®
0 ®®
0 ®
1 ¬

We see that each 4 × 4 sub-matrix of this parity check matrix

NOZAKI and ISAKA: LDPC CODES FOR COMMUNICATION SYSTEMS

Fig. 5

Protograph and a derived graph.

901

Now, let us consider the encoding process of the AR3A
code. Let xi,t be the bit stored in vi,t , for i = 1, 2, . . . , 5
and t = 1, 2, . . . , N. Suppose c1,i is adjacent to v2,π(i) .
Firstly, assign 2N information bits to the variable nodes
v1,1, v1,2, . . . , v1, N , v2,1, . . . , v2, N . Secondly, calculate thebits in v3,1, v3,2, . . . , v3, N . Decide the bit in v3,1 by the constraint of c1,1 ; x3,1 = (x1,1 + x2,π(1) ). Next, compute the bit inv3,2 by c1,2 ; x3,2 = (x1,2 + x2,π(2) ) + x3,1 . Similarly, calculate
the bits in v3,3, v3,4, . . . , v3, N by x3,t = (x1,t + x2,π(t) )+ x3,t−1(t = 3, 4, . . . , N). Thirdly, calculate the 2N parity bits,i.e., the bits in v4,1, v4,2, . . . , v4, N , v5,1, . . . , v5, N . Decide
the bit in v4,1 by the constraint of c2,1 . Next, computethe bit in v5,1 by c3,1 . Similarly, calculate the bits in
v4,2, v5,2, v4,3, . . . , v5, N .
Since the bits in v3,1, v3,2, . . . , v3, N are not transmitted,
the number of transmitted bits are 4N. Hence, the code rateis 1/2.
Most high performance protograph LDPC codes contain the punctured variable nodes. However, punctured variable nodes require many decoding iterations. Uchikawa [71]designed high performance protograph LDPC codes without
punctured nodes.
For more information of the protograph LDPC codes,
see [72].
7.

Fig. 6

Protograph and derived graph for AR3A code with rate 1/2.

is equal to the sum of permutation matrices.
Many existing protograph codes have punctured (i.e.,
untransmitted) variable nodes for increasing the code rate
and the decoding threshold. Those variable nodes are decoded in a similar way to the erased symbol on the BEC. The
following example explains the punctured variable nodes andencoding process of a protograph LDPC code.
Example 6.2: The AR3A code, a type of ARA code, isa classical linear-time encodable protograph LDPC code.
Figure 6(a) depicts the protograph of the AR3A code with
rate 1/2. The white variable node (v3 ) represents punctured
node. The information (resp. parity) part corresponds tov1, v2 (resp. v4, v5 ).
Figure 6(b) displays the derived graph for the AR3A
code with rate 1/2. Here, N stands for the number of copies,and Π represents an edge permutation. The N copies of thenode vi (resp. c j ) are denoted by vi,1, vi,2, . . . , vi, N (resp.
c j,1, c j,2, . . . , c j, N ). In the bundle (v3, c1 ), v3,t is adjacentto c1,t and c1,t+1 for t = 1, 2, . . . , N − 1. Note that thenodes c1,1 and v3, N are not connected. Such structure iscalled an accumulator. The bundles between c2, c3 andv4, v5 are also an accumulator. As mentioned below, theaccumulator provides an efficient encoding algorithm for
protograph LDPC codes.

Quasi-Cyclic LDPC Codes

Quasi-cyclic (QC) LDPC codes [73] are a special case of
protograph LDPC code. QC-LDPC codes have advantages
in hardware implementation of the encoder [67] and thedecoder. Hence, most of standards (e.g., [5], [6], [13]) adopt
QC-LDPC codes.
Define an N × N cyclic permutation matrix P as
0©
­1­
P = ­­0
­ ..
­.
«0

0
0
1
..
.

···
···
···
..
.

0
0
0
..
.

0

···

1

1
ª
0®
0®® .
.. ®®
.®
0¬

For a vector v, v(Pi )T stands left circular shift of v by ipositions. Note that every cyclic permutation matrix is represented by Pi with some i.
The quasi-cyclic codes are defined by the null spaceof parity check matrices H = [Ai, j ], where each sub-matrix
Ai, j is circulant, i.e., the sum of cyclic permutation matrices.
The quasi-cyclic code is QC-LDPC if the parity check matrix
is sparse. In the terminology of protograph LDPC code,a parity check matrix of a QC-LDPC code is derived byreplacing the (i, j)-th entry of a base matrix into the sum ofbi, j random N × N cyclic permutation matrix for each (i, j).
Hence, QC-LDPC codes are special cases of protograph
LDPC codes.
The generator matrices of QC-LDPC codes are also
represented by block matrices with circulant matrices. Recall that the multiplication of a cyclic permutation matrix

IEICE TRANS. COMMUN., VOL.E105–B, NO.8 AUGUST 2022

902

and a vector v is a circular shift of v. Hence, the encoder of
QC-LDPC codes is implemented by shift resisters [67]. Panteleev [74] proposed a fast encoding algorithm for QC-LDPC
codes based on the Chinese remainder theorem.
The circulant matrices are also suitable for the hardware
implementation of decoders, e.g., a high-throughput FPGAbased decoder shown in [75]. The construction and details
for QC-LDPC codes are summarized in [42].
8.

Fig. 7

Copies of protograph for (3, 6)-regular LDPC code.

Spatially Coupled LDPC Codes

Spatially coupled LDPC (SC-LDPC) codes [76] or LDPC
convolutional codes [77] are a sub-class of protograph LDPC
codes. This code is constructed by coupling protograph
LDPC codes. In this section, we explain the SC-LDPC
codes based on protographs.
Let B be the base matrix of a protograph LDPC code,
which is called an un-coupled LDPC code for distinction
from an SC-LDPC code. Recall that each entry of the basematrix is an integer. Split B into w parts B1, B2, . . . , Bw
as B = B1 + B2 + · · · + Bw . Make the base matrix of the
SC-LDPC code as follows:
B0
©B
­ 1
­ .
­ ..
­
­
­
­B w
­
­
­
­
«O

O
B0
..
.
Bw−1
Bw

ª
®
. . ®®
.®
. . ®®
.®
. . ®®
.®
®
..
.¬

By copy-and-permutation operation, we obtain a paritycheck matrix of SC-LDPC code.
Example 8.1: This example gives an SC-LDPC code constructed from the (3, 6)-regular un-coupled LDPC code. Thebase matrix
code is given
 of (3, 6)-regular un-coupled LDPC
by 3 3 . Set B1 = B2 = B3 = 1 1 . Then, we obtain
the base matrix of the SC-LDPC code as follows:
1 1
O©
­1 1 1 1 . . .
­­.
­­1 1 1 1 . .
­.
­1 1 ..
­
­
..
.
« O

ª
®
®
®
®
®.
®
®
®
®
¬

Now, let us construct the protograph of the SC-LDPC
code. Firstly, we make protograph of (3, 6)-regularLDPCcode, i.e., the code with the base matrix 3 3 . Secondly,
we make (2L + 1) copies of the base graph as shown in
Fig. 7. In Fig. 7, each label below the base graphs represents
its position. Thirdly, spreading edges of variable nodes to theneighboring check nodes as in Fig. 8, i.e., the variable nodes
in the i-th position adjacent to the check nodes in the (i−1)-th,i-th, and (i + 1)-th positions. The resulting graph is the baseFig. 8

Protograph of SC-LDPC code.

graph of the SC-LDPC code. Finally, we obtain a Tannergraph of the SC-LDPC code by the copy-and-permutation
operation to the base graph.
From Fig. 8, we see that there exist check nodes withsmall degrees in both ends of the base graph of the SCLDPC code. Such check nodes degrade the code rate of the
SC-LDPC code, i.e., an SC-LDPC code has a lower code
rate than the un-coupled LDPC code. However, this loss is
negligible if L is large enough.
The check nodes with small degrees provide reliable
messages in the BP decoding algorithm. Hence, BP decoding propagates reliable messages from the both ends of
the Tanner graph for the SC-LDPC code. As BP decoding
proceeds, reliable messages reach the middle of the Tannergraph and recover the transmitted word. In other words, atthe start of BP decoding, the messages in the middle of theTanner graph may go to waste.
By using this property, the windowed decoding algorithm [78] is proposed to reduce the decoding complexity.
In this algorithm, the messages are calculated only at thenodes in a range of positions, called decoding window. At
the start of decoding, the decoding window is set in the left
end of the Tanner graph of the SC-LDPC code. As the decoding proceeds, the decoding window moves to the right-handside of the Tanner graph.
Kudekar et al. [79] proved that the BP decoding threshold of the SC-LDPC code equals the MAP decoding threshold of the un-coupled LDPC code. This phenomenon iscalled threshold saturation. In particular, if the un-coupledLDPC code achieves the channel capacity under MAP decoding, the corresponding SC-LDPC code also achieves it
under BP decoding. Summarizing above, well-designed SCLDPC codes have good decoding performance in very large
code length.
9.

Non-Binary LDPC Codes

Each symbol in the finite field F2m of order 2m is represented
by m bits. Hence, for a code over F2m , the codewords of

NOZAKI and ISAKA: LDPC CODES FOR COMMUNICATION SYSTEMS

symbol length n/m have n bit code length.
In this section, we focus on the non-binary LDPC (NBLDPC) codes defined over Fq , where q = 2m > 2. A
fundamental decoding algorithm for the NB-LDPC codes
over Fq is a q-ary SP algorithm [80], a generalization of the
SP algorithm given in Sect. 3.1. Davey and MacKay [80]reported that an NB-LDPC code outperforms binary one bycomparing the decoding error rates for the regular LDPC
codes over F2, F4 , and F8 with the same bit code length.
Hu et al. [53] optimized the degree distribution pair for theirregular binary and non-binary LDPC codes. As a result,they showed that (2, dc )-regular LDPC code has the best
performance for q ≥ 64 and the optimized NB-LDPC codes
have lower decoding error rates than binary one for short
bit code length (n = 1008). Coşkun et al. [81] reported
that NB-LDPC code has a lower decoding error rate than thepolar code with CRC-assisted list decoding for n ≥ 1024.
Based on these observations, promising applications of NBLDPC codes include communication systems with limited
code length (n ≥ 1000).
In the q-ary SP algorithm [80], each message is represented in a vector of length q. Due to the length of themessage vector, the q-ary SP algorithm requires large spacecomplexity. Moreover, the q-ary SP algorithm requires large
time complexity in the check node calculation. Hence, many
low-complexity decoding algorithms are proposed for the
NB-LDPC codes, e.g., extended min-sum algorithm [82],bit-reliability based majority logic decoding algorithm [83],and multiple-votes symbol-flipping algorithm [84]. Nowadays, deep-learning based decoding algorithm [85] is investigated.
For more information of the NB-LDPC codes, see [86],
[87].
10.

Practical Use in Communication Systems

This section briefly introduces LDPC codes used in somecommunication system standards.
The IEEE802.11 (wifi) [5] adopts four different QCLDPC codes with rate 1/2, 5/8, 3/4 and 13/16. All QCLDPC codes are of length 672 and use a circulant matrix ofsize 42.
The IEEE802.16 (WiMAX) [6] employs QC-LDPC
code with rates 1/2, 2/3, 3/4 and 5/6. In each rate, we canchoose a pair of code length and circulant matrix size from
(96i, 4i) for i = 6, 7, 8, . . . , 24. Hence, the maximum code
length is 2304.
The 5G NR [13] adopts two type QC-LDPC codes,
called base graph 1 and base graph 2, for the error-correcting
codes in the data channels. The base graph 1 (resp. 2) isdefined by 46 × 68 (resp. 42 × 52) base matrix. The circulant
matrix size is adjusted by the payload length. The maximum
code length is 8448 (resp. 3840) for the base graph 1 (resp.
2). The rate is adjusted by selecting untransmitted bits. For
more information about the LDPC codes adopted to 5G NR,
see [88].
Concatenation of long BCH and LDPC codes is em-

903

ployed in recent broadcasting systems [7]–[11]. For example, LDPC (IRA) codes of lengths 16200 and 64800 witheleven code rates ranging from 1/4 to 9/10 are supported
based on base matrix of size N = 360 in DVB-S2 [8]. A
BCH code capable of correcting up to t bit errors is used foreach set of code length and rate, and t is 12 in most cases.
For rate-1/2 LDPC code of length 64800, input and output
of BCH encoder is 32208 and 32400 bits long, respectively,
and the overall code rate of the concatenated code is 0.497.
11.

Conclusions

This survey has given the definition, decoding algorithm,
encoding algorithm, and construction technique of LDPC
codes. We also have introduced QC-LDPC code, which has
been adopted by various communication standards. Moreover, we have explained several high performance LDPC
codes: protograph LDPC codes, SC-LDPC codes, and NBLDPC codes.
References[1] R. Gallager, “Low-density parity-check codes,” IRE Trans. Inf. Theory, vol.8, no.1, pp.21–28, Jan. 1962.
[2] R. Gallager, Low-Density Parity-Check Codes, Research Monographseries, MIT Press, 1963.
[3] T.J. Richardson and R.L. Urbanke, “The capacity of low-density
parity-check codes under message-passing decoding,” IEEE Trans.
Inf. Theory, vol.47, no.2, pp.599–618, 2001.
[4] “IEEE standard for ethernet,” IEEE Std 802.3-2015 (Revision ofIEEE Std 802.3-2012), pp.1–4017, March 2016.
[5] “IEEE standard for information technology–telecommunications andinformation exchange between systems local and metropolitan area
networks–specific requirements - part 11: Wireless LAN medium
access control (MAC) and physical layer (PHY) specifications,” IEEE
Std 802.11-2016 (Revision of IEEE Std 802.11-2012), pp.1–3534,
Dec. 2016.
[6] “IEEE standard for air interface for broadband wireless access systems,” IEEE Std 802.16-2012 (Revision of IEEE Std 802.16-2009),
pp.1–2542, Aug. 2012.
[7] “Frame structure channel coding and modulation for a second generation digital transmission system for cable systems (DVB-C2),” DVB
Standards, Oct. 2015.
[8] “Second generation framing structure, channel coding and modulation systems for broadcasting, interactive services, news gatheringand other broadband satellite applications; part 1 (DVB-S2),” DVB
Standards, Nov. 2014.
[9] “Frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2),”
DVB Standards, July 2015.
[10] A.T.S. Committee, “Atsc standard: Physical layer protocol,” Doc.
A/322, 2017.
[11] Association of Radio Industries and Businesses, “Transmission system for advanced wide band digital satellite broadcasting (isdb-s3),”
ARIB STD-B44 version 2.1, 2016.
[12] “CCSDS 211.0-b-5; recommendation for space data system standards,” CCSDS, Dec. 2013.
[13] “5G; NR; multiplexing and channel coding,” 3GPP TS 38.212 version
15.2.0 Release 15, 2018.
[14] C. Shannon, “A mathematical theory of communication,” Bell Syst.
Tech. J., vol.27, no.10, pp.379–423, 623–656, Oct. 1948.
[15] E.R. Berlekamp, Algebraic Coding Theory, Argen Park Press, 1968.
[16] G. Liva, L. Gaudio, T. Ninacs, and T. Jerkovits, “Code design for904
short blocks: A survey,” European Conf. on Networks and Communications (EuCNC), 2016.
[17] E. Nachmani, E. Marciano, L. Lugosch, W.J. Gross, D. Burstein, and
Y. Be’ery, “Deep learning methods for improved decoding of linear
codes,” IEEE Sel. Top. Signal Process., vol.12, no.1, pp.119–131,
Feb. 2018.
[18] D.J.C. MacKay and R.M. Neal, “Near Shannon limit performanceof low density parity check codes,” Electron. Lett., vol.32, no.18,
pp.1645–1646, 1996.
[19] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit
error-correcting coding: Turbo codes,” Proc. Int. Conf. Commun.
(ICC1993), pp.1064–1070, May 1993.
[20] “LTE; multiplexing and channel coding,” 3GPP TS 36.212 version
12.4.0 Release 12, 2015.
[21] D.J.C. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge Univ. Press, 2003.
[22] M.P.C. Fossorier and S. Lin, “Soft-decision decoding of linear block
codes based on ordered statistics,” IEEE Trans. Inf. Theory, vol.41,
no.5, pp.1379–1396, Sept. 1995.
[23] F.R. Kschischang, B.J. Frey, and H.-A. Loeliger, “Factor graphs andthe sum-product algorithm,” IEEE Trans. Inf. Theory, vol.47, no.2,
pp.498–519, Feb. 2001.
[24] J. Hagenauer, E. Offer, and L. Papke, “Iterative decoding of binary
block and convolutional codes,” IEEE Trans. Inf. Theory, vol.42,
no.2, pp.429–445, March 1996.
[25] E. Arikan, “Channel polarization: A method for constructing
capacity-achieving codes for symmetric binary-input memorylesschannels,” IEEE Trans. Inf. Theory, vol.55, no.7, pp.3051–3073,
June 2009.
[26] E. Şaşoğlu, Polarization and Polar Codes, Found. Trends Commun.
Inform. Theory, Now Publishers, 2012.
[27] I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Trans. Inf.
Theory, vol.61, no.5, pp.2213–2226, May 2015.
[28] E. Arikan, “Polar code: A pipelined implementations,” Proc. 4th
ISBM, pp.11–14, July 2010.
[29] S. Kudekar, M. Mondelli, H.D. Pfister, E. Şaşoğlu, and R. Urbanke,“Reed-Muller codes achieve capatity on erasure channels,” IEEE
Trans. Inf. Theory, vol.63, no.7, pp.4298–4316, July 2017.
[30] M. Geiselhart, A. Elkelesh, M. Ebada, S. Cammerer, and S. t. Brink,“Automorphism ensemble decoding of Reed–Muller codes,” IEEE
Trans. Commun., vol.69, no.10, pp.6424–6438, 2021.
[31] T. Richardson and R. Urbanke, Modern Coding Theory, Cambridge
University Press, 2008.
[32] Y. Kou, S. Lin, and M.P.C. Fossorier, “Low-density parity-check
codes based on finite geometries: A rediscovery and new results,”
IEEE Trans. Inf. Theory, vol.47, no.7, pp.2711–2736, Nov 2001.
[33] X. Wu, C. Ling, M. Jiang, E. Xu, C. Zhao, and X. You, “New insights
into weighted bit-flipping decoding,” IEEE Trans. Commun., vol.57,
no.8, pp.2177–2180, Aug. 2009.
[34] T. Wadayama, K. Nakamura, M. Yagita, Y. Funahashi, S. Usami, and
I. Takumi, “Gradient descent bit flipping algorithms for decoding
LDPC codes,” IEEE Trans. Commun., vol.58, no.6, pp.1610–1614,
June 2010.
[35] V. Savin, “Gradient descent bit-flip decoding with momentum,”2021-11th International Symposium on Topics in Coding (ISTC),
IEEE, 2021.
[36] D. Hocevar, “A reduced complexity decoder architecture via layered
decoding of LDPC codes,” IEEE Workshop on Signal Processing
Systems (SIPS), 2004, pp.107–112, Oct. 2004.
[37] J. Zhang and M.P.C. Fossorier, “Shuffled iterative decoding,” IEEE
Trans. Commun., vol.53, no.2, pp.209–213, Feb. 2005.
[38] H.C. Lee and Y.L. Ueng, “LDPC decoding scheduling for fasterconvergence and lower error floor,” IEEE Trans. Commun., vol.62,
no.9, pp.3104–3113, Sept. 2014.
[39] C.A. Aslam, Y.L. Guan, K. Cai, and G. Han, “Informed fixed scheduling for faster convergence of shuffled belief-propagation decoding,”
IEEE Commun. Lett., vol.21, no.1, pp.32–35, Jan. 2017.

IEICE TRANS. COMMUN., VOL.E105–B, NO.8 AUGUST 2022

[40] M.P.C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity
iterative decoding of low-density parity check codes based on belief
propagation,” IEEE Trans. Commun., vol.47, no.5, pp.673–680, May
1999.
[41] J. Chen, A. Dholakia, E. Eleftheriou, M.P.C. Fossorier, and X.-Y.
Hu, “Reduced-complexity decoding of LDPC codes,” IEEE Trans.
Commun., vol.53, no.8, pp.1288–1299, Aug. 2005.
[42] W. Ryan and S. Lin, Channel Codes: Classical and Modern, Cambridge University Press, 2009.
[43] J.K.S. Lee and J. Thorpe, “Memory-efficient decoding of LDPC
codes,” Proc. IEEE Int. Symp. Inf. Theory (ISIT), pp.459–463, Sept.
2005.
[44] S.K. Planjery, D. Declercq, L. Danjean, and B. Vasic, “Finite alphabet
iterative decoders part I: Decoding beyond belief propagation on thebinary symmetric channel,” IEEE Trans. Commun., vol.61, no.10,
pp.4033–4045, Oct. 2013.
[45] S. Ten Brink, “Convergence of iterative decoding,” Electron. Lett.,vol.35, no.10, pp.806–808, 1999.
[46] A. Amraoui, “Asymptotic and finite-length optimization of LDPC
codes,” Ph.D. dissertation, EPFL, 2006.
[47] A. Amraoui, A. Montanari, T. Richardson, and R. Urbanke, “Finitelength scaling for iteratively decoded LDPC ensembles,” IEEE Trans.
Inf. Theory, vol.55, no.2, pp.473–498, 2009.
[48] J. Ezri, A. Montanari, S. Oh, and R. Urbanke, “The slope scaling
parameter for general channels, decoders, and ensembles,” 2008
IEEE International Symposium on Information Theory, pp.1443–
1447, July 2008.
[49] P.M. Olmos and R.L. Urbanke, “A scaling law to predict the finitelength performance of spatially-coupled LDPC codes,” IEEE Trans.
Inf. Theory, vol.61, no.6, pp.3164–3184, June 2015.
[50] T. Tian, C.R. Jones, J.D. Villasenor, and R.D. Wesel, “Selective
avoidance of cycles in irregular LDPC code construction,” IEEE
Trans. Commun., vol.52, no.8, pp.1242–1247, Aug. 2004.
[51] T.J. Richardson and R.L. Urbanke, “Efficient encoding of low-density
parity-check codes,” IEEE Trans. Inf. Theory, vol.47, no.2, pp.638–
656, Feb. 2001.
[52] S.K. Chilappagari, S. Sankaranarayanan, and B. Vasic, “Error floorsof LDPC codes on the binary symmetric channel,” Proc. IEEE Int.
Conf. Commun. (ICC2006), vol.3, pp.1089–1094, June 2006.
[53] X.-Y. Hu, E. Eleftheriou, and D.M. Arnold, “Regular and irregularprogressive edge-growth Tanner graphs,” IEEE Trans. Inf. Theory,
vol.51, no.1, pp.386–398, Jan. 2005.
[54] H. Xiao and A.H. Banihashemi, “Improved progressive-edge-growth(PEG) construction of irregular LDPC codes,” IEEE Commun. Lett.,vol.8, no.12, pp.715–717, Dec. 2004.
[55] G. Richter and A. Hof, “On a construction method of irregular LDPC
codes without small stopping sets,” Proc. IEEE Int. Conf. Commun.
(ICC2006), vol.3, pp.1119–1124, June 2006.
[56] M. Diouf, D. Declercq, S. Ouya, and B. Vasic, “A PEG-like LDPC
code design avoiding short trapping sets,” Proc. IEEE Int. Symp. Inf.
Theory (ISIT), pp.1079–1083, June 2015.
[57] X. He, L. Zhou, and J. Du, “A new multi-edge metric-constrained
PEG algorithm for designing binary LDPC code with improved
cycle-structure,” IEEE Trans. Commun., vol.66, no.1, pp.14–25, Jan.
2018.
[58] Y. Kaji, “Encoding LDPC codes using the triangular factorization,”
IEICE Trans. Fundamentals, vol.E89-A, no.10, pp.2510–2518, Oct.
2006.
[59] T. Shibuya, “Block-triangularization of parity check matrices for
efficient encoding of linear codes,” Proc. IEEE Int. Symp. Inf. Theory(ISIT), pp.533–537, IEEE, 2011.
[60] T. Nozaki, “Parallel encoding algorithm for LDPC codes based onblock-diagonalization,” Proc. IEEE Int. Symp. Inf. Theory (ISIT),
pp.1911–1915, IEEE, 2015.
[61] Y. Iketo and T. Nozaki, “Encoding algorithm of binary and nonbinary irregular LDPC codes via block triangular matrices with low
weight diagonal submatrices,” 2020 International Symposium on In-

NOZAKI and ISAKA: LDPC CODES FOR COMMUNICATION SYSTEMS

formation Theory and Its Applications (ISITA), pp.225–229, IEEE,
2020.
[62] Y. Iketo and T. Nozaki, “Efficient encoding algorithm of binary andnon-binary LDPC codes using block triangulation,” arXiv preprint
arXiv:2103.01560, 2021.
[63] D. Divsalar, H. Jin, and R.J. McEliece, “Coding theorems for “Turbolike” codes,” Proc. Annu. Allerton Conf. Commun., Control, Comput., pp.201–210, vol.36, 1998.
[64] H. Jin, A. Khandekar, and R. McEliece, “Irregular repeat-accumulate
codes,” Proc. 2nd Int. Symp. Turbo codes and related topics, Citeseer,pp.1–8, 2000.
[65] A. Abbasfar, D. Divsalar, and K. Yao, “Accumulate-repeataccumulate codes,” IEEE Trans. Commun., vol.55, no.4, pp.692–
702, April 2007.
[66] J. Thorpe, “Low-density parity-check (LDPC) codes constructedfrom protographs,” IPN progress report, vol.42, no.154, pp.42–154,
2003.
[67] Z. Li, L. Chen, L. Zeng, S. Lin, and W.H. Fong, “Efficient encoding of
quasi-cyclic low-density parity-check codes,” IEEE Trans. Commun.,vol.54, no.1, pp.71–81, Jan. 2006.
[68] T. Richardson and R. Urbanke, “Multi-edge type LDPC codes,”Workshop honoring Prof. Bob McEliece on his 60th birthday, California Institute of Technology, Pasadena, California, pp.24–25, 2002.
[69] D. Divsalar, S. Dolinar, C.R. Jones, and K. Andrews, “Capacityapproaching protograph codes,” IEEE J. Sel. Areas Commun., vol.27,
no.6, pp.876–888, 2009.
[70] D. Divsalar, C. Jones, S. Dolinar, and J. Thorpe, “Protograph based
LDPC codes with minimum distance linearly growing with block
size,” Proc. IEEE Global Telecommun. Conf., vol.3, pp.1152–1156,
IEEE, 2005.
[71] H. Uchikawa, “Design of non-precoded protograph-based LDPC
codes,” Proc. IEEE Int. Symp. Inf. Theory (ISIT), pp.2779–2783,
IEEE, 2014.
[72] Y. Fang, G. Bi, Y.L. Guan, and F.C. Lau, “A survey on protograph
LDPC codes and their applications,” IEEE Commun. Surveys Tuts.,
vol.17, no.4, pp.1989–2016, 2015.
[73] M.P.C. Fossorier, “Quasi-cyclic low-density parity-check codes fromcirculant permutation matrices,” IEEE Trans. Inf. Theory, vol.50,
no.8, pp.1788–1793, Aug. 2004.
[74] P. Panteleev, “Fast systematic encoding of quasi-cyclic codes using
the chinese remainder theorem,” Proc. IEEE Int. Symp. Inf. Theory(ISIT), pp.1916–1920, June 2015.
[75] S. Mhaske, H. Kee, T. Ly, A. Aziz, and P. Spasojevic, “Highthroughput FPGA-based QC-LDPC decoder architecture,” Proc.
IEEE Veh. Technol. Conf, pp.1–5, Sept. 2015.
[76] S. Kudekar, T.J. Richardson, and R.L. Urbanke, “Threshold saturation via spatial coupling: Why convolutional LDPC ensembles
perform so well over the BEC,” IEEE Trans. Inf. Theory, vol.57,
no.2, pp.803–834, Feb. 2011.
[77] A.J. Felstrom and K. Zigangirov, “Time-varying periodic convolutional codes with low-density parity-check matrix,” IEEE Trans. Inf.
Theory, vol.45, no.6, pp.2181–2191, Sept. 1999.
[78] A.R. Iyengar, M. Papaleo, P.H. Siegel, J.K. Wolf, A. Vanelli-Coralli,
and G.E. Corazza, “Windowed decoding of protograph-based LDPC
convolutional codes over erasure channels,” IEEE Trans. Inf. Theory,
vol.58, no.4, pp.2303–2320, April 2012.
[79] S. Kudekar, T. Richardson, and R.L. Urbanke, “Spatially coupled
ensembles universally achieve capacity under belief propagation,”
IEEE Trans. Inf. Theory, vol.59, no.12, pp.7761–7813, Dec. 2013.
[80] M.C. Davey and D. MacKay, “Low-density parity check codes over
GF(q),” IEEE Commun. Lett., vol.2, no.6, pp.165–167, June 1998.
[81] M.C. Coşkun, G. Durisi, T. Jerkovits, G. Liva, W. Ryan, B. Stein, and
F. Steiner, “Efficient error-correcting codes in the short blocklength
regime,” Physical Communication, vol.34, pp.66–79, 2019.
[82] D. Declercq and M. Fossorier, “Decoding algorithms for nonbinary
LDPC codes over GF(q),” IEEE Trans. Commun., vol.55, no.4,
pp.633–643, April 2007.

905[83] Q. Huang, M. Zhang, Z. Wang, and L. Wang, “Bit-reliability based
low-complexity decoding algorithms for non-binary LDPC codes,”IEEE Trans. Commun., vol.62, no.12, pp.4230–4240, 2014.
[84] F. Garcia-Herrero, D. Declercq, and J. Valls, “Non-binary LDPC decoder based on symbol flipping with multiple votes,” IEEE Commun.
Lett., vol.18, no.5, pp.749–752, May 2014.
[85] T. Watanabe, T. Ohseki, and K. Yamazaki, “Deep learning-based bit
reliability based decoding for non-binary LDPC codes,” Proc. IEEE
Int. Symp. Inf. Theory (ISIT), pp.1451–1456, IEEE, 2021.
[86] I.B. Djordjevic, “On advanced FEC and coded modulation for ultrahigh-speed optical transmission,” IEEE Commun. Surveys Tuts.,
vol.18, no.3, pp.1920–1951, thirdquarter 2016.
[87] O. Ferraz, S. Subramaniyan, R. Chinthalaa, J. Andrade, J.R. Cavallaro, S.K. Nandy, V. Silva, X. Zhang, M. Purnaprajna, and G. Falcao, “A survey on high-throughput non-binary LDPC decoders:
ASIC, FPGA and GPU architectures,” IEEE Commun. Surveys Tuts.,
vol.24, no.1, pp.524–556, 2022.
[88] T. Richardson and S. Kudekar, “Design of low-density parity check
codes for 5G new radio,” IEEE Commun. Mag., vol.56, no.3, pp.28–
34, March 2018.

Takayuki Nozaki
received the B.E., M.E.,
and Ph.D. degrees from Tokyo Institute of Technology in 2008, 2010, and 2012, respectively.
He is currently an associate professor at Yamaguchi University. His research interests include
error-correcting codes and coding theory. He received the Best Paper Award from the IEICE ofJapan in 2018. He is a member of IEEE, ACM,
AMS, and IPSJ.

Motohiko Isaka
received the B.E., M.E.,
and Ph.D. degrees all in electrical engineeringfrom the University of Tokyo, Tokyo, Japan, in
1994, 1996, and 1999, respectively. He is currently with Dept. of Computer Science, Kwansei
Gakuin University, Sanda, Japan, working on
coding techniques.