This chapter explores the design and performance of low-density parity-check (LDPC) codes which when combined with soft decision iterative decoding provide currently the best achievable performance in digital communication systems. The application of cyclotomic cosets, idempotents and Mattson–Solomon polynomials is shown to produce many new binary cyclic LDPC codes whose parity-check equations are orthogonal in each position. A key feature of this construction technique is the incremental approach to designing the minimum Hamming distance and the sparseness of the resulting parity-check matrix of the code. Binary cyclic LDPC codes are also constructed by considering idempotents in the Mattson–Solomon domain. It is shown that, for short algebraic LDPC codes, the myth of codes which have cycles of length 4 in their Tanner graph does not converge well with iterative decoding is not necessarily true. It is demonstrated that the cyclotomic coset-based construction can be easily extended to produce good non-binary algebraic LDPC codes. Good irregular LDPC codes may be constructed using the progressive edge-growth algorithm. Many new code results are presented showing the effects of choosing different degree distributions. Guidelines are given for designing the best codes. Methods of producing structured LDPC codes, such as those which have quasi-cyclic structure, are described. These are of interest to industry due to the simplification of the encoder and decoder. An example of such a construction to produce a (64800,48600) LDPC code, using a protograph, is presented along with performance results using iterative decoding. Better results are obtained with this code than the (64800,48600) LDPC code used in the DVB-S2 standard.
12.1 Background and Notation
LDPC codes are linear block codes whose parity-check matrix—as the name implies—is sparse. These codes can be iteratively decoded using the sum product [9] or equivalently the belief propagation [24] soft decision decoder. It has been shown, for example by Chung et al. [3], that for long block lengths, the performance of LDPC codes is close to the channel capacity. The theory of LDPC codes is related to a branch of mathematics called graph theory. Some basic definitions used in graph theory are briefly introduced as follows.
Definition 12.1
(Vertex, Edge, Adjacent and Incident) A graph, denoted by G(V, E), consists of an ordered set of vertices and edges.
Anzeige
(Vertex) A vertex is commonly drawn as a node or a dot. The set V(G) consists of vertices of G(V, E) and if v is a vertex of G(V, E), it is denoted as \(v\in V(G)\). The number of vertices of V(G) is denoted by |V(G)|.
(Edge) An edge (u, v) connects two vertices \(u\in V(G)\) and \(v\in V(G)\) and it is drawn as a line connecting vertices u and v. The set E(G) contains pairs of elements of V(G), i.e. \(\{(u,v)~|~u,v\in V(G)\}\).
(Adjacent and Incident) If \((u,v)\in E(G)\), then \(u\in V(G)\) and \(v\in V(G)\) are adjacent or neighbouring vertices of G(V, E). Similarly, the vertices u and v are incident with the edge (u, v).
Definition 12.2
(Degree) The degree of a vertex \(v\in V(G)\) is the number of edges that are incident with vertex v, i.e. the number of edges that are connected to vertex v.
Definition 12.3
(Bipartite or Tanner graph) Bipartite or Tanner graph G(V, E) consists of two disjoint sets of vertices, say \(V_v(G)\) and \(V_p(G)\), such that \(V(G) = V_v(G) \cup V_p(G)\), and every edge \((v_i,p_j)\in E(G)\), such that \(v_i\in V_v(G)\) and \(p_j \in V_p(G)\) for some integers i and j.
Fig. 12.1
Representations of a [16, 4, 4] LDPC code
×
Anzeige
An [n, k, d] LDPC code may be represented by a Tanner graph G(V, E). The parity-check matrix \(\varvec{H}\) of the LDPC code consists of \(|V_p(G)|=n-k\) rows and \(|V_v(G)|=n\) columns. The set of vertices \(V_v(G)\) and \(V_p(G)\) are called variable and parity-check vertices, respectively. Figure 12.1 shows the parity check and the corresponding Tanner graph of a [16, 4, 4] LDPC code. Let \(V_v(G) = (v_0,v_1,\ldots ,v_{n-1})\) and \(V_p(G) = (p_0,p_1,\ldots ,p_{n-k-1})\); we can see that for each \((v_i,p_j)\in E(G)\), the ith column and jth row of \(\varvec{H}\), \(H_{j,i} \ne 0\), for \(0 \le i \le {n-1}\) and \(0 \le j \le n-k-1\).
Definition 12.4
(Cycle) A cycle in a graph G(V, E) is a sequence of distinct vertices that starts and ends in the same vertex. For bipartite graph G(V, E), exactly half of these distinct vertices belong to \(V_v(G)\) and the remaining half belong to \(V_p(G)\).
Definition 12.5
(Girth and Local Girth) The girth of graph G(V, E) is the length of the shortest cycle in the graph G(V, E). The local girth of a vertex \(v\in V(G)\) is the length of shortest cycle that passes through vertex v.
The performance of a typical iteratively decodable code (e.g. an LDPC or turbo code) may be partitioned into three regions, namely erroneous, waterfall and error floor regions, see Fig. 12.2. The erroneous region occurs at low \(E_b/N_0\) values and is indicated by the inability of the iterative decoder to correctly decode almost all of the transmitted messages. As we increase the signal power, the error rate of the iterative decoder decreases rapidly—resembling a waterfall. The \(E_b/N_0\) value at which the waterfall region starts is commonly known as the convergence threshold in the literature. At higher \(E_b/N_0\) values, the error rate starts to flatten—introducing an error floor in the frame error rate (FER) curve.
Fig. 12.2
Waterfall and error regions of a typical LDPC code for the AWGN channel
×
In addition to this FER curve, the offset sphere packing lower bound and the probability of error based on the union bound argument as described in Chap. 1 are also plotted in Fig. 12.2. The sphere packing lower bound represents the region of attainable performance of a coding system. The performance to the left of this lower bound is not attainable, whereas that to the right may be achieved by some coding and decoding arrangements. The other curve is the union bound of the probability of error, which is dominated by the low Hamming weight codewords and the number of codewords of these Hamming weights. The larger the minimum Hamming distance of a code, the lower the union bound typically. For iteratively decodable codes which are not designed to maximise the minimum Hamming distance, the union bound intersects with the offset sphere packing lower bound at relatively low \(E_b/N_0\) values.
It may be seen that, with an ideal soft decision decoder, the performance of a coding system would follow the sphere packing lower bound and at higher \(E_b/N_0\) values, the performance floors due to the limitation of the minimum Hamming weight codewords. However, as depicted in Fig. 12.2, there is a relatively wide gap between the union bound and the error floor of a typical iteratively decodable code. This is an inherent behaviour of iteratively decodable codes and it is attributed to the weakness of the iterative decoder. There are other error events, which are not caused by the minimum Hamming weight codewords, that prevent the iterative decoder from reaching the union bound.
In terms of the construction technique, we may divide LDPC codes into two categories: random and algebraic LDPC codes. We may also classify LDPC codes into two categories depending on the structure of the parity-check matrix, namely regular and irregular codes—refer to Sect. 12.1.1 for the definition. Another attractive construction method that has been shown to offer capacity-achieving performance is non-binary construction.
12.1.1 Random Constructions
Gallager [8] introduced the \((n,\lambda ,\rho )\) LDPC codes where n represents the block length whilst the number of non-zeros per column and the number of non-zeros per row are represented by \(\lambda \) and \(\rho \), respectively.
The short notation \((\lambda ,\rho )\) is also commonly used to represent these LDPC codes. The coderate of the Gallager \((\lambda ,\rho )\) codes is given by
An example of the parity-check matrix of a Gallager \((\lambda ,\rho )\) LDPC code is shown in Fig. 12.1a. It is a [16, 4, 4] code with a \(\lambda \) of 3 and a \(\rho \) of 4. The parity-check matrix of the \((\lambda ,\rho )\) Gallager codes always have a fixed number of non-zeros per column and per row, and because of this property, this class of LDPC codes is termed regular LDPC codes. The performance of the Gallager LDPC codes in the waterfall region is not as satisfactory as that of turbo codes for the same block length and code rate. Many efforts have been devoted to improve the performance of the LDPC codes and one example that provides significant improvement is the introduction of the irregular LDPC codes by Luby et al. [18]. The irregular LDPC codes, as the name implies, do not have a fixed number of non-zeros per column or per row and thus the level of error protection varies over a codeword. The columns of a parity check matrix that have a higher number of non-zeros provide stronger error protection than those that have a lower number of non-zeros. Given an input block in iterative decoding, errors in the coordinates of this block, whose columns of the parity-check matrix have a larger number of non-zeros, will be corrected earlier, i.e. only a small number of iterations are required. In the subsequent iterations, the corrected values in these coordinates will then be utilised to correct errors in the remaining coordinates of the block.
Definition 12.6
(Degree Sequences) The polynomial \(\varLambda _{\lambda }(x) = \sum _{i\ge 1}\lambda _i x^i\) is called the symbol or variable degree sequence, where \(\lambda _i\) is the fraction of vertices of degree i. Similarly, \(\varLambda _{\rho }(x) = \sum _{i \ge 1}\rho _i x^i\) is the check degree sequence, where \(\rho _i\) is the fraction of vertices of degree i.
The degree sequences given in the above definition are usually known as vertex-oriented degree sequences. Another representations are edge-oriented degree sequences which consider the fraction of edges that are connected to a vertex of certain degree. Irregular LDPC codes are defined by these degree sequences and it is assumed that the degree sequences are vertex-oriented.
Example 12.1
An irregular LDPC code with the following degree sequences
has 50, 26, 17 and \(7\%\) of the columns with 2, 3, 5 and 10 ones per column, respectively, and 80 and \(20\%\) of the rows with 14 and 15 ones per row, respectively.
Various techniques have been proposed to design good degree distributions. Richardson et al. [27] used density evolution to determine the convergence threshold and to optimise the degree distributions. Chung et al. [4] simplified the density evolution approach using Gaussian approximation. With the optimised degree distributions, Chung et al. [3] showed that the bit error rate performance of a long block length (\(n=10^{7}\)) irregular LDPC code was within 0.04 dB away from the capacity limit for binary transmission over the AWGN channel, discussed in Chap. 1. This is within 0.18 dB of Shannon’s limit [30]. The density evolution and Gaussian approximation methods, which make use of the concentration theorem [28], can only be used to design the degree distributions for infinitely long LDPC codes. The concentration theorem states that the performance of cycle-free LDPC codes can be characterised by the average performance of the ensemble. The cycle-free assumption is only valid for infinitely long LDPC codes and cycles are inevitable for finite block-length LDPC codes. As may be expected, the performance of finite block-length LDPC codes with degree distributions derived based on the concentration theorem differs considerably from the ensemble performance. There are various techniques to design good finite block-length LDPC codes, for instance see [1, 2, 10, 33]. In particular, the work of Hu et al. [10] with the introduction of the progressive edge-growth (PEG) algorithm to construct both regular and irregular LDPC codes, that of Tian et al. [33] with the introduction of extrinsic message degree and recently, that of Richter et al. [29] which improves the original PEG algorithm by introducing some construction constraints to avoid certain cycles involving variable vertices of degree 3, have provided significant contributions to the construction of practical LDPC codes as well as the lowering of the inherent error floor of these codes.
12.1.2 Algebraic Constructions
In general, LDPC codes constructed algebraically have a regular structure in their parity-check matrix. The algebraic LDPC codes offer many advantages over randomly generated codes. Some of these advantages are
1.
The important property such as the minimum Hamming distance can be easily determined or in the worst case, lower and upper bounds may be mathematically derived. These bounds are generally more accurate than estimates for random codes.
2.
The minimum Hamming distance of algebraic LDPC codes is typically higher than that of random codes. Due to the higher minimum Hamming distance, algebraic codes are not that likely to suffer from an early error floor.
3.
The existence of a known structure in algebraic codes usually offers an attractive and simple encoding scheme. In the case of random codes, in order to carry out encoding, a Gaussian elimination process has to be carried out in the first place and the entire reduced echelon parity-check matrix has to be stored in the memory. Algebraically constructed codes such as cyclic or quasi-cyclic codes can be completely defined by polynomials. The encoding of cyclic or quasi-cyclic codes may be simply achieved using a linear-feedback shift-register circuit and the memory requirement is minimum. Various efficient techniques for encoding random LDPC codes have been proposed, see Ping et al. [26] for example, but none of these techniques simplifies the storage requirements. The simplicity of the encoder and decoder structure has led to many algebraically constructed LDPC codes being adopted as industry standards [5].
4.
Cyclic LDPC codes have n low Hamming weight parity-check equations and therefore, compared to random codes, these cyclic LDPC codes have k extra equations for the iterative decoder to iterate with and this leads to improved performance.
One of the earliest algebraic LDPC code constructions was introduced by Margulis [21] using the Ramanujan graphs. Lucas et al. [19] showed that the well-known different set cyclic (DSC) [36] and one-step majority-logic decodable (OSMLD) [17] codes have good performance under iterative decoding. The iterative soft decision decoder offers significant improvement over the conventional hard decision majority-logic decoder. Another class of algebraic codes is the class of the Euclidean and projective geometry codes which are discussed in detail by Kou et al. [16]. Other algebraic constructions include those that use combinatorial techniques [13‐15, 35].
It has been observed that in general, there is an inverse performance relationship between the minimum Hamming distance of the code and the convergence of the iterative decoder. Irregular codes converge well with iterative decoding, but the minimum Hamming distance is relatively poor. In contrast, algebraically constructed LDPC codes, which have high minimum Hamming distance, tend not to converge well with iterative decoding. Consequently, compared to the performance of irregular codes, algebraic LDPC codes may perform worse in the low SNR region and perform better in the high SNR region. This is attributed to the early error floor of the irregular codes. As will be shown later, for short block lengths (\(n < 350\)), cyclic algebraic LDPC codes offer some of the best performance available.
12.1.3 Non-binary Constructions
LDPC codes may be easily extended so that the symbols take values from the finite-field \(\mathbb {F}_{2^m}\) and Davey et al. [6] were the pioneers in this area. Given an LDPC code over \(\mathbb {F}_2\) with parity-check matrix \(\varvec{H}\), we may construct an LDPC code over \(\mathbb {F}_{2^m}\) for \(m \ge 2\) by simply replacing every non-zero element of \(\varvec{H}\) with any non-zero element of \(\mathbb {F}_{2^m}\) in a random or structured manner. Davey et al. [6] and Hu et al. [11] have shown that the performance of LDPC codes can be improved by going beyond the binary field. The non-binary LDPC codes have better convergence behaviour under iterative decoding. Using some irregular non-binary LDPC codes, whose parity-check matrices are derived by randomly replacing the non-zeros of the PEG-constructed irregular binary LDPC codes, Hu et al. [11] demonstrated that an additional coding gain of 0.25 dB was achieved. It may be regarded that the improved performance is attributable to the improved graph structure in the non-binary arrangement. Consider a cycle of length 6 in the Tanner graph of a binary LDPC code, which is represented as the following sequence of pairs of edges \(\{(v_0,p_0), (v_3,p_0), (v_3,p_2), (v_4,p_2), (v_4,p_1), (v_0,p_1)\}.\) If we replace the corresponding entries in the parity-check matrix with some non-zeros over \(\mathbb {F}_{2^m}\) for \(m \ge 2\), provided that these six entries are not all the same, the cycle length becomes longer than 6. According to McEliece et al. [22] and Etzion et al. [7], the non-convergence of the iterative decoder is caused by the existence of cycles in the Tanner graph representation of the code. Cycles, especially those of short lengths, introduce correlations of reliability information exchanged in iterative decoding. Since cycles are inevitable for finite block length codes, it is desirable to have LDPC codes with large girth.
The non-binary LDPC codes also offer an attractive matching for higher order modulation methods. The impact of increased complexity of the symbol-based iterative decoder can be moderated as the reliability information from the component codes may be efficiently evaluated using the frequency-domain dual-code decoder based on the Fast Walsh–Hadamard transform [6].
12.2 Algebraic LDPC Codes
Based on idempotents and cyclotomic cosets, see Chap. 4, a class of cyclic codes that is suitable for iterative decoding may be constructed. This class of cyclic codes falls into the class of one-step majority-logic decodable (OSMLD) codes whose parity-check polynomial is orthogonal on each bit position—implying the absence of a girth of 4 in the underlying Tanner graph, and the corresponding parity-check matrix is sparse, and thus can be used as LDPC codes.
Definition 12.7
(Binary Parity-Check Idempotent) Let \(\mathscr {M} \subseteq \mathscr {N}\) and let the polynomial \(u(x) \in T(x)\) be defined by
where \(e_s(x)\) is an idempotent. The polynomial u(x) is called a binary parity-check idempotent.
The binary parity-check idempotent u(x) can be used to describe an [n, k] cyclic code as discussed in Chap. 4. Since GCD\((u(x), x^n-1)=h(x)\), the polynomial \(\bar{u}(x)=x^{\deg (u(x))}u(x^{-1})\) and its n cyclic shifts \(\pmod { x^n-1}\) can be used to define the parity-check matrix of a binary cyclic code. In general, \(\mathrm {wt}_H(\bar{u}(x))\) is much lower than \(\mathrm {wt}_H(h(x))\), and therefore a low-density parity-check matrix can be derived from \(\bar{u}(x)\).
Let the parity-check polynomial \(\bar{u}(x) = x^{\bar{u}_0} + x^{\bar{u}_1} + \cdots + x^{\bar{u}_t}\) of weight \(t+1\). Since the code defined by \(\bar{u}(x)\) is cyclic, for each non-zero coefficient \(\bar{u}_i\) in \(\bar{u}(x)\), there are another t parity-check polynomials of weight \(t+1\), which also have a non-zero coefficient at position \(\bar{u}_i\). Furthermore, consider the set of these \(t+1\) polynomials that have a non-zero coefficient at position \(\bar{u}_i\), there is no more than one polynomial in the set that have a non-zero at position \(\bar{u}_j\) for some integer j. In other words, if we count the number of times the positions \(0,1,\ldots ,n-1\) appear in the exponents of the aforementioned set of \(t+1\) polynomials, we shall find that all positions except \(\bar{u}_i\) appear at most once. This set of \(t+1\) polynomials is said to be orthogonal on position \(\bar{u}_i\). The mathematical expression of this orthogonality is given in the following definition and lemma.
Definition 12.8
(Difference Enumerator Polynomial) Let the polynomial \(f(x) \in T(x)\). The difference enumerator of f(x), denoted as \(\mathscr {D}(f(x))\), is defined as
where it is assumed that \(\mathscr {D}(f(x))\) is a modulo \(x^n-1\) polynomial with coefficients taking values from \(\mathbb {R}\) (real coefficients).
Lemma 12.1
Let \(d_i\) for \(0 \le i \le n-1\) denote the coefficients of \(\mathscr {D}(\bar{u}(x))\). If \(d_i \in \{0,1\}\), for all \(i \in \{1,2,\ldots ,n-1\}\), the parity-check polynomial derived from \(\bar{u}(x)\) is orthogonal on each position in the n-tuple. Consequently,
(i)
the minimum distance of the resulting LDPC code is \(1+\mathrm {wt}_H(\bar{u}(x))\), and
(ii)
the underlying Tanner Graph has girth of at least 6.
Proof
(i) [25, Theorem 10.1] Let a codeword \(c(x)=c_0 + c_1x + \cdots + c_{n-1}x^{n-1}\) and \(c(x) \in T(x)\). For each non-zero bit position \(c_j\) of c(x), where \(j \in \{0,1,\ldots ,n-1\}\), there are \(\mathrm {wt}_H(u(x))\) parity-check equations orthogonal to position \(c_j\). Each of the parity-check equations must check another non-zero bit \(c_l\), where \(l \ne j\), so that the equation is satisfied. Clearly, \(\mathrm {wt}_H(c(x))\) must equal to \(1+\mathrm {wt}_H(u(x))\) and this is the minimum weight of all codewords.
(ii) The direct consequence of having orthogonal parity-check equations is the absence of cycles of length 4 in the Tanner Graphs. Let a, b and c, where \(a< b < c\), be three distinct coordinates in an n-tuple, since \(d_i\in \{0,1\}\) for \(1\le i\le n-1\), this implies that \(b-a \ne c-b\). We know that \(q(b-a) \pmod { n}\in \{1,2,\ldots ,n-1\}\) and thus, \(q(b-a) \pmod { n} \equiv (c-b)\) for some integer \(q\in \{1,2,\ldots ,n-1\}\). If we associate the integers a, b and c with some variable vertices in the Tanner graph, a cycle of length 6 is produced.
It can be deduced that the cyclic LDPC code with parity-check polynomial \(\bar{u}(x)\) is an OSMLD code if \(d_i \in \{0,1\}\), for all \(i \in \{1,2,\ldots ,n-1\}\) or a difference set cyclic (DSC) code if \(d_i=1\), for all \(i \in \{1,2,\ldots ,n-1\}\), where \(d_i\) is the coefficient of \(\mathscr {D}(\bar{u}(x))\).
In order to arrive at either OSMLD or DSC codes, the following design conditions are imposed on \(\bar{u}(x)\) and therefore, u(x):
There are \(\mathrm {wt}_H(u(x))\) polynomials of weight \(\mathrm {wt}_H(u(x))\) that are orthogonal on position j for some integer j. The number of distinct positions in this set of polynomials is \(\mathrm {wt}_H(u(x))\left( \mathrm {wt}_H(u(x))-1\right) \), and this number must be less than or equal to the total number of distinct integers between 1 and \(n-1\).
Condition 12.2
Following Definition 12.8, let \(W = \{i~|~d_i = 1,~1\le i \le n-1\}\), the cardinality of W must be equal to \(\mathrm {wt}_H(u(x))\left( \mathrm {wt}_H(u(x))-1\right) \).
Proof
The cyclic differences between the exponents of polynomial u(x) are given by \(\mathscr {D}\left( u(x)\right) =\sum _{i=0}^{n-1} d_ix^i\), where the coefficient \(d_i\) is the number of differences and the exponent i is the difference. The polynomial u(x) and some of its cyclic shifts are orthogonal on position 0 and this means that all of the cyclic differences between the exponents of u(x) (excluding zero) must be distinct, i.e. \(d_i\in \{0,1\}\) for \(1 \le i \ne n-1\). Since the weight of u(x) excluding \(x^0\) is \(\mathrm {wt}_H\left( u(x)\right) -1\) and there are \(\mathrm {wt}_H\left( u(x)\right) \) cyclic shifts of u(x) that are orthogonal to \(x^0\), the number of distinct exponents in the cyclic differences is \(\mathrm {wt}_H\left( u(x)\right) \left( \mathrm {wt}_H\left( u(x)\right) -1\right) =W\).
Condition 12.3
The exponents of u(x) must not contain a common factor of n, otherwise a degenerate code, a repetition of a shorter cyclic code, is the result.
Proof
If the exponents of u(x) contain a common factor of n, p with \(n=pr\), then factors of u(x) divide \(x^r-1\) and form a cyclic code of length r. Every codeword of the longer code is a repetition of the shorter cyclic code.
Condition 12.4
Following (12.1), unless \(\mathrm {wt}_H(e_s(x)) = 2\), the binary parity-check idempotent \(e_s(x)\) must not be self-reciprocal, i.e. \(e_s(x) \ne e_i\left( x^{-1}\right) \), for all \(i \in \mathscr {M}\).
Proof
The number of non-zero coefficients of \(\mathscr {D}(e_s(x))\) is equal to
For a self-reciprocal case, \(e_s(x)e_s\left( x^{-1}\right) =e_s^2(x) = e_s(x)\) with \(\mathrm {wt}_H(e_s(x))\) non-zero coefficients. Following Condition 12.1, the inequality
becomes equality if and only if \(\mathrm {wt}_H(e_s(x)) = 2\).
Condition 12.5
Following (12.1), u(x) must not contain \(e_s\left( x^{-1}\right) \), for all \(i \in \mathscr {M}\), unless \(e_s(x)\) is self-reciprocal.
Proof
If u(x) contains \(e_s\left( x^{-1}\right) \) for \(i \in \mathscr {M}\), then \(\mathscr {D}(u(x))\) will contain both \(e_s(x)e_s\left( x^{-1}\right) \) and \(e_s\left( x^{-1}\right) e_s(x)\), hence, some of the coefficients of \(\mathscr {D}(e_s(x))\), \(d_i\ne \{0,1\}\) for some integer i.
Although the above conditions seem overly restrictive, they turn out to be helpful in code construction. Codes may be designed in stage-by-stage by adding candidate idempotents to u(x), checking the above conditions at each stage.
In order to encode the cyclic LDPC codes constructed, there is no need to determine g(x). With \(\alpha \) defined as a primitive nth root of unity, it follows from Lemma 4.4 that \(u(\alpha ^i) \in \{0,1\}\) for \(0 \le i \le n-1\). Let \(\mathscr {J}=(j_0,j_1,\ldots ,j_{n-k-1})\) be a set of integers between 0 and \(n-1\), such that \(g(\alpha ^j)=0\), for all \(j \in \mathscr {J}\). Because u(x) does not contain \(\alpha ^j\) as its roots, it follows that \(u(\alpha ^j)=1\), for all \(j \in \mathscr {J}\). In \(\mathbb {F}_2\), \(1+u(\alpha ^j)=0\) and the polynomial \(1+u(x)=e_g(x)\), the generating idempotent of the code may be used to generate the codewords as an alternative to g(x).
The number of information symbols of the cyclic LDPC codes can be determined either from the number of roots of u(x) which are also roots of unity, i.e. \(n-\mathrm {wt}_H\left( U(z)\right) \), or from the degree of \((u(x),x^n-1)=h(x)\).
Example 12.2
Consider the design of a cyclic LDPC code of length 63. The cyclotomic coset modulo 63 is given in Example 4.2. Let u(x) be defined by \(C_9\), i.e. \(u(x)=e_9(x)=x^9(1+x^9+x^{27})\). \(\mathscr {D}(\bar{u}(x))\) indicates that the parity-check matrix defined by \(\bar{u}(x)\) has no cycles of length 4; however, following Condition 12.3, it is a degenerate code consisting of repetitions of codewords of length 7.
With \(u(x) = e_{23}(x) = x^{23}(1+x^6+x^{20}+x^{23}+x^{30}+x^{35})\), the resulting cyclic code is a [63, 31, 6] LDPC code which is non-degenerate and its underlying Tanner graph has girth of 6. This code can be further improved by adding \(e_{21}(x)\) to u(x). Despite \(e_{21}(x)\) being self-reciprocal, its weight is 2 satisfying Condition 12.4. Now, \(u(x)= x^{21}(1+x^2+x^8+x^{21}+x^{22}+x^{25}+x^{32}+x^{37})\), and it is a [63, 37, 9] cyclic LDPC code.
Based on the theory described above, an algorithm which exhaustively searches for all non-degenerate cyclic LDPC codes of length n which have orthogonal parity-check polynomials has been developed, and it is given in Algorithm 12.1.
×
Table 12.1 lists some example of codes obtained from Algorithm 12.1. Note that all codes with code rate less than 0.25 are excluded from the table and codes of longer lengths may also be constructed. We can also see that some of the codes in Table 12.1 have the same parameters as the Euclidean and projective geometry codes, which have been shown by Jin et al. [16] to perform well under iterative decoding.
A key feature of the cyclotomic coset-based construction is the ability to increment the minimum Hamming distance of a code by adding further weight from other idempotents and so steadily decrease the sparseness of the resulting parity-check matrix. Despite the construction method producing LDPC codes with no cycles of length 4, it is important to remark that codes that have cycles of length 4 in their parity-check matrices do not necessary have bad performance under iterative decoding, and a similar finding has been demonstrated by Tang et al. [31]. It has been observed that there are many cyclotomic coset-based LDPC codes that have this property, and the constraints in Algorithm 12.1 can be easily relaxed to allow the construction of cyclic LDPC codes with girth 4.
12.2.1 Mattson–Solomon Domain Construction of Binary Cyclic LDPC Codes
The [n, k, d] cyclic LDPC codes presented in Sect. 4.4 are constructed using the sum of idempotents, which are derived from the cyclotomic cosets modulo n, to define the parity-check matrix. A different insight into this construction technique may be obtained by working in the Mattson–Solomon domain.
Let n be a positive odd integer, \(\mathbb {F}_{2^m}\) be a splitting field for \(x^n-1\) over \(\mathbb {F}_2\), \(\alpha \) be a generator for \(\mathbb {F}_{2^m}\), and \(T_m(x)\) be a polynomial with maximum degree of \(n-1\) and coefficients in \(\mathbb {F}_{2^m}\). Similar to Sect. 4.4, the notation of T(x) is used as an alternative to \(T_1(x)\) and the variables x and z are used to distinguish the polynomials in the domain and codomain. Let the decomposition of \(z^n-1\) into irreducible polynomials over \(\mathbb {F}_2\) be contained in a set \(\mathscr {F}=\{f_1(z),f_2(z),\ldots ,f_t(z)\}\), i.e. \(\prod _{1 \le i \le t} f_i(z) = z^n-1\). For each \(f_i(z)\), there is a corresponding primitive idempotent, denoted as \(\theta _i(z)\), which can be obtained by [20]
Here \(u_1(x),u_2(x),\ldots ,u_t(x)\) are the binary idempotents whose Mattson–Solomon polynomials are \(\theta _1(z), \theta _2(z),\ldots ,\theta _t(z)\), respectively. Assume that \(\mathscr {I} \subseteq \{1,2,\ldots ,t\}\), let the binary polynomials \(u(x)=\sum _{\forall i\in \mathscr {I}} u_i(x)\), \(f(z) = \prod _{\forall i \in \mathscr {I}} f_i(z)\), and \(\theta (z) = \sum _{\forall i \in \mathscr {I}} \theta _i(z)\). It is apparent that, since \(u_i(x) = \text {MS}^{-1}\left( \theta _i(z)\right) \), \(u(x)=\text {MS}^{-1}\left( \theta (z)\right) \) and u(x) is an idempotent.1
Recall that u(x) is a low-weight binary idempotent whose reciprocal polynomial can be used to define the parity-check matrix of a cyclic LDPC code. The number of distinct nth roots of unity which are also roots of the idempotent u(x) determines the dimension of the resulting LDPC code. In this section, the design of cyclic LDPC codes is based on several important features of a code. These features, which are listed as follows, may be easily gleaned from the Mattson–Solomon polynomial of u(x) and the binary irreducible factors of \(z^n-1\).
1.
Weight of the idempotentu(x)
The weight of u(x) is the number of nth roots of unity which are zeros of f(z). Note that, \(f(\alpha ^i)=0\) if and only if \(\theta (\alpha ^i)=1\) since an idempotent takes only the values 0 and 1 over \(\mathbb {F}_{2^m}\). If u(x) is written as \(u_0 + u_ix + \cdots + u_{n-1}x^{n-1}\), following (11.2), we have
Therefore, \(u_i=1\) precisely when \(f(\alpha ^i)=0\), giving \(\mathrm {wt}_H(u(x))\) as the degree of the polynomial f(z).
2.
Number of zeros ofu(x)
Following (11.1), it is apparent that the number of zeros of u(x) which are roots of unity, which is also the dimension of the code k, is
$$\begin{aligned} \text {Number of zeros of }u(x)&= k = n-\mathrm {wt}_H\left( \theta (z)\right) . \end{aligned}$$
(12.4)
3.
Minimum Hamming distance bound
The lower bound of the minimum Hamming distance of a cyclic code, defined by idempotent u(x), is given by its BCH bound, which is determined by the number of consecutive powers of \(\alpha \), taken cyclically (mod n), which are roots of the generating idempotent \(e_g(x)=1+u(x)\). In the context of u(x), it is the same as the number of consecutive powers of \(\alpha \), taken cyclically (mod n), which are not roots of u(x). Therefore, it is the largest number of consecutive non-zero coefficients in \(\theta (z)\), taken cyclically (mod n).
The method of finding \(f_i(z)\) is well established and using the above information, a systematic search for idempotents of suitable weight may be developed. To be efficient, the search procedure has to start with an increasing order of \(\mathrm {wt}_H(u(x))\) and this requires rearrangement of the set \(\mathscr {F}\) such that \(\deg (f_i(z)) < \deg (f_i{i+1}(z))\) for all i. It is worth mentioning that it is not necessary to evaluate u(x) by taking the Mattson–Solomon polynomial of \(\theta (z)\), for each f(z) obtained. It is more efficient to obtain u(x) once the desired code criteria, listed above, are met.
For an exhaustive search, the complexity is of order \(\mathscr {O}\left( 2^{|\mathscr {F}|}\right) \). A search algorithm, see Algorithm 12.2, has been developed and it reduces the complexity considerably by targeting the search on the following key parameters. Note that this search algorithm, which is constructed in the Mattson–Solomon domain, is not constrained to find cyclic codes that have girth at least 6.
1.
Sparseness of the parity-check matrix
A necessary condition for the absence of cycles of length 4 is given by the inequality \(\mathrm {wt}_H(u(x)) \left( \mathrm {wt}_H(u(x))-1\right) \le n-1\). Since \(\mathrm {wt}_H(u(x)) = \deg (f(z))\), a reasonable bound is
In practise, this limit is extended to enable the finding of good cyclic LDPC codes which have girth of 4 in their underlying Tanner graph.
2.
Code rate
The code rate is directly proportional to the number of roots of u(x). If \(R_{min}\) represents the minimum desired code rate, then it follows from (12.4) that we can refine the search to consider the cases where
If the idempotent u(x) is orthogonal on each position, then the minimum Hamming distance of the resulting code defined by u(x) is equal to \(1+\mathrm {wt}_H(u(x))\). However, for cyclic codes with cycles of length 4, there is no direct method to determine their minimum Hamming distance and the BCH bound provides a lower bound to the minimum Hamming distance. Let d be the lowest desired minimum Hamming distance and \(r_\theta \) be the largest number of consecutive non-zero coefficients, taken cyclically, of \(\theta (z)\). If a cyclic code has \(r_\theta \) of d, then its minimum Hamming distance is at least \(1+d\). It follows that we can further refine the search with the constraint
In comparison to the construction method described in Sect. 4.4, we can see that the construction given in Sect. 4.4 starts from the idempotent u(x), whereas this section starts from the idempotent \(\theta (z)\), which is the Mattson–Solomon polynomial of u(x). Both construction methods are equivalent and the same cyclic LDPC codes are produced.
Some good cyclic LDPC codes with cycles of length 4 found using Algorithm 12.2, which may also be found using Algorithm 12.1, are tabulated in Table 12.2. A check based on Lemma 12.1 may be easily incorporated in Step 12 of Algorithm 12.2 to filter out cyclic codes whose Tanner graph has girth of 4.
Fig. 12.3
FER performance of some binary cyclic LDPC codes
×
Figure 12.3 demonstrates the FER performance of several cyclic LDPC codes found by Algorithm 12.2. It is assumed that binary antipodal signalling is employed and the iterative decoder uses the RVCM algorithm described by Papagiannis et al. [23]. The FER performance is compared against the sphere packing lower bound offset for binary transmission. We can see that the codes [127, 84, 10] and [127, 99, 7], despite having cycles of length 4, are around 0.3 dB from the offset sphere packing lower bound at \(10^{-4}\) FER. Figure 12.3c compares two LDPC codes of block size 255 and dimension 175, an algebraic code obtained by Algorithm 12.2 and an irregular code constructed using the PEG algorithm [10]. It can be seen that, in addition to having improved minimum Hamming distance, the cyclic LDPC code is 0.4 dB superior to the irregular code, and compared to the offset sphere packing lower bound, it is within 0.25 dB away at \(10^{-4}\) FER. The effect of the error floor is apparent in the FER performance of the [341, 205, 6] irregular LDPC code, as shown in Fig. 12.3d. The floor of this irregular code is largely attributed to minimum Hamming distance error events. Whilst this irregular code, at low SNR region, has better convergence than does the algebraic LDPC code of the same block length and dimension, the benefit of having higher minimum Hamming distance is obvious as the SNR increases. The [341, 205, 16] cyclic LDPC code is approximately 0.8 dB away from the offset sphere packing lower bound at \(10^{-4}\) FER.
It is clear that short block length (\(n\le 350\)) cyclic LDPC codes have outstanding performance and the gap to the offset sphere packing lower bound is relatively close. However, as the block length increases, the algebraic LDPC codes, although these code have large minimum Hamming distance, have a convergence issue, and the threshold to the waterfall region is at larger \(E_b/N_0\). The convergence problem arises because as the minimum Hamming distance increases, the weight of the idempotent u(x), which defines the parity-check matrix, also increases. In fact, if u(x) satisfies Lemma 12.1, we know that \(\mathrm {wt}_H(u(x))=d-1\), where d is the minimum Hamming distance of the code. Large values of \(\mathrm {wt}_H(u(x))\) result in a parity-check matrix that is not as sparse as that of a good irregular LDPC code of the same block length and dimension.
12.2.2 Non-Binary Extension of the Cyclotomic Coset-Based LDPC Codes
The code construction technique for the cyclotomic coset-based binary cyclic LDPC codes, which is discussed in Sect. 4.4, may be extended to non-binary fields. Similar to the binary case, the non-binary construction produces the dual-code idempotent which is used to define the parity-check matrix of the associated LDPC code.
Let m and \(m^\prime \) be positive integers with \(m~\mid ~m^\prime \), so that \(\mathbb {F}_{2^m}\) is a subfield of \(\mathbb {F}_{2^{m^\prime }}\). Let n be a positive odd integer and \(\mathbb {F}_{2^{m^\prime }}\) be the splitting field of \(x^n-1\) over \(\mathbb {F}_{2^m}\), so that \(n|2^{m^\prime }-1\). Let \(r=(2^{m^\prime }-1)/n\), \(l=(2^{m^\prime }-1)/(2^m-1)\), \(\alpha \) be a generator for \(\mathbb {F}_{2^{m^\prime }}\) and \(\beta \) be a generator of \(\mathbb {F}_{2^m}\), where \(\beta =\alpha ^l\). Let \(T_a(x)\) be the set of polynomials of degree at most \(n-1\) with coefficients in \(\mathbb {F}_{2^a}\). For the case of \(a=1\), we may denote \(T_1(x)\) by T(x) for convenience.
The Mattson–Solomon polynomial and its corresponding inverse, (11.1) and (11.2), respectively, may be redefined as
where \(a(x)\in T_{m^\prime }(x)\) and \(A(z)\in T_{m^\prime }(z)\).
Recall that a polynomial \(e(x)\in T_m(x)\) is termed an idempotent if the property \(e(x) = e(x)^2 \pmod { x^n-1}\) is satisfied. Note that \(e(x) \ne e(x^2) \pmod { x^n-1}\) unless \(m=1\). The following definition shows how to construct an idempotent for binary and non-binary polynomials.
Definition 12.9
(Cyclotomic Idempotent) Assume that \(\mathscr {N}\) be a set as defined in Sect. 4.4, let \(s\in \mathscr {N}\) and let \(C_{s,i}\) represent the \((i+1)\)th element of \(C_s\), the cyclotomic coset of \(s \pmod { n}\). Assume that the polynomial \(e_s(x) \in T_m(x)\) is given by
where \(|C_s|\) is the number of elements in \(C_s\). In order for \(e_s(x)\) to be an idempotent, its coefficients may be chosen in the following manner:
(i)
if \(m=1\), \(e_{C_{s,i}} = 1\),
(ii)
otherwise, \(e_{C_{s,i}}\) is defined recursively as follows:
The polynomial u(x) is an idempotent and it is called a parity-check idempotent.
As in Sect. 4.4, the parity-check idempotent u(x) is used to define the \(\mathbb {F}_{2^m}\) cyclic LDPC code over \(\mathbb {F}_{2^m}\), which may be denoted by \([n,k,d]_{2^m}\). The parity-check matrix consists of n cyclic shifts of \(x^{\deg (u(x))}u(x^{-1})\). For the non-binary case, the minimum Hamming distance d of the cyclic code is bounded by
where \(d_0\) is the maximum run of consecutive ones in \(U(z)=\text {MS}(u(x))\), taken cyclically mod n.
Based on the description given above, a procedure to construct a cyclic LDPC code over \(\mathbb {F}_{2^m}\) is as follows.
1.
For integers m and n, obtain the splitting field (\(\mathbb {F}_{2^{m^\prime }}\)) of \(x^n-1\) over \(\mathbb {F}_{2^m}\). Unless the condition of \(m~\mid ~m^\prime \) is satisfied, \(\mathbb {F}_{2^m}\) cyclic LDPC code of length n cannot be constructed.
2.
Generate the cyclotomic cosets modulo \(2^{m^\prime }-1\) denoted as \(C^\prime \).
3.
Derive a polynomial p(x) from \(C^\prime \) and let \(s \in \mathscr {N}\) be the smallest positive integer such that \(|C^\prime _s| = m\). The polynomial p(x) is the minimal polynomial of \(\alpha ^s\),
Construct all elements of \(\mathbb {F}_{2^m}\) using p(x) as the primitive polynomial.
4.
Let C be the cyclotomic cosets modulo n and let \(\mathscr {N}\) be a set containing the smallest number in each coset of C. Assume that there exists a non-empty set \(\mathscr {M} \subset \mathscr {N}\) and following Definition 12.10 construct the parity-check idempotent u(x). The coefficients of u(x) can be assigned following Definition 12.9.
5.
Generate the parity-check matrix of \(\mathscr {C}\) using the n cyclic shifts of \(x^{\deg (u(x))}u(x^{-1})\).
6.
Compute r and l, and then take the Mattson–Solomon polynomial of u(x) to produce U(z). Obtain the code dimension and the lower bound of the minimum Hamming distance from U(z).
Example 12.3
Consider the construction of a \(n=21\) cyclic LDPC code over \(\mathbb {F}_{2^6}\). The splitting field of \(x^{21}-1\) over \(\mathbb {F}_{2^6}\) is \(\mathbb {F}_{2^6}\), and this implies that \(m=m^\prime =6\), \(r=3\) and \(l=1\). Let C and \(C^\prime \) denote the cyclotomic cosets modulo n and \(2^{m^\prime }-1\), respectively. We know that \(|C^\prime _1| = 6\) and therefore the primitive polynomial p(x) has roots of \(\alpha ^j\), for all \(j \in C^\prime _1\), i.e. \(p(x)=1+x+x^6\). By letting \(1+\beta +\beta ^6=0\), all of the elements of \(\mathbb {F}_{2^6}\) can be defined. If u(x) is the parity-check idempotent generated by the sum of the cyclotomic idempotents defined by \(C_s\), where \(s\in \{\mathscr {M}:5,7,9\}\) and \(e_{C_{s,0}}\) for all \(s \in \mathscr {M}\) be \(\beta ^{23}\), 1 and 1, respectively,
\(^\dagger \)The minimum Hamming distance of the binary image which has been determined using the improved Zimmermann algorithm, Algorithm 5.1
Fig. 12.4
FER performance of some non-binary cyclic LDPC codes
Fig. 12.5
FER performance of algebraic and irregular LDPC codes of rate 0.6924 and code length 5461 bits
×
×
The following systematic search algorithm is based on summing each possible combination of the cyclotomic idempotents to search for all possible \(\mathbb {F}_{2^m}\) cyclic codes of a given length. As in Algorithm 12.2, the search algorithm targets the following key parameters:
1.
Sparseness of the resulting parity-check matrix Since the parity-check matrix is directly derived from u(x) which consists of the sum of the cyclotomic idempotents, only low-weight cyclotomic idempotents are of interest. Let \(W_{max}\) be the maximum \(\mathrm {wt}_H(u(x))\); then the search algorithm will only choose the cyclotomic idempotents whose sum has total weight less than or equal to \(W_{max}\).
2.
High code rate The number of roots of u(x) which are also roots of unity define the dimension of the resulting LDPC code. Let the integer \(k_{min}\) be defined as the minimum code dimension, and the cyclotomic idempotents that are of interest are those whose Mattson–Solomon polynomial has at least \(k_{min}\) zeros.
3.
High minimum Hamming distance Let the integer \(d^\prime \) be the smallest value of the minimum Hamming distance of the code. The sum of the cyclotomic idempotents should have at least \(d^\prime -1\) consecutive powers of \(\beta \) which are roots of unity but not roots of u(x).
Following Definition 12.10 and the Mattson–Solomon polynomial
it is possible to maximise the run of the consecutive ones in U(z) by varying the coefficients of \(e_s(x)\). It is therefore important that all possible non-zero values of \(e_{C_{s,0}}\) for all \(s\in \mathscr {M}\) are included to guarantee that codes with the highest possible minimum Hamming distance are found.
Table 12.3 outlines some examples of \([n,k,d]_{2^m}\) cyclic LDPC codes. The non-binary algebraic LDPC codes in this table perform well under iterative decoding as shown in Fig. 12.4 assuming binary antipodal signalling and the AWGN channel. The RVCM algorithm is employed in the iterative decoder. The FER performance of these non-binary codes is compared to the offset sphere packing lower bound in Fig. 12.4.
As mentioned in Sect. 12.1.2, there is an inverse relationship between the convergence of the iterative decoder and the minimum Hamming distance of a code. The algebraic LDPC codes, which have higher minimum Hamming distances compared to irregular LDPC codes, do not converge well at long block lengths. It appears that the best convergence at long code lengths can only be realised by irregular LDPC codes with good degree distributions. Figure 12.5 shows the performance of two LDPC codes of block length 5461 bits and code rate 0.6924; one is an irregular code constructed using the PEG algorithm and the other one is an algebraic code of minimum Hamming distance 43 based on cyclotomic coset and idempotent construction (see Table 12.1). These results are for the AWGN channel using binary antipodal signalling with a belief propagation iterative decoder featuring 100 iterations. We can see that at \(10^{-5}\) FER, the irregular PEG code is superior by approximately 1.6 dB compared to the algebraic cyclic LDPC code. However, for short code lengths, algebraic LDPC codes are superior. The codes have better performance and have simpler encoders than ad hoc designed LDPC codes.
12.3 Irregular LDPC Codes from Progressive Edge-Growth Construction
It is shown by Hu et al. [11] that LDPC codes obtained using the PEG construction method can perform better than other types of randomly constructed LDPC codes. The PEG algorithm adds edges to each vertex such that the local girth is maximised. The PEG algorithm considers only the variable degree sequence, and the check degree sequence is maintained to be as uniform as possible. In this section, the results of experimental constructions of irregular LDPC codes using the PEG algorithm are presented. Analysis on the effects of the vertex degree ordering and degree sequences have been carried out by means of computer simulations. All simulation results in this section, unless otherwise stated, were obtained using binary antipodal signalling with the belief propagation decoder using 100 iterations. Each simulation run was terminated after the decoder had produced 100 erroneous frames.
Fig. 12.6
Effect of vertex degree ordering in PEG algorithm
×
Figure 12.6 shows the FER performance of various [2048, 1024] irregular LDPC codes constructed using the PEG algorithm with different vertex degree orderings. These LDPC codes have variable degree sequence \(\varLambda _{\lambda }(x) = 0.475x^2 + 0.280x^3 + 0.035x^4 + 0.109x^5 + 0.101x^{15}\). Let \(\left( v_0,v_1,\ldots ,v_i,\ldots ,v_{n-1}\right) \) be a set of variable vertices of an LDPC code. Code 0 and Code 1 LDPC codes were constructed with an increasing vertex degree ordering, i.e. \(\deg (v_0) \le \deg (v_1) \le \cdots \le \deg (v_{n-1})\), whereas the remaining LDPC codes were constructed with random vertex degree ordering.
Figure 12.6 clearly shows that, unless the degree of the variable vertices is assigned in an increasing order, poor LDPC codes are obtained. In random degree ordering of half rate codes, it is very likely to encounter the situation where, as the construction approaches the end, there are some low-degree variable vertices that have no edge connected to them. Since almost all of the variable vertices would have already had edges connected to them, the low-degree variable vertices would not have many choice of edges to connect in order to maximise the local girth. It has been observed that, in many cases, these low-degree variable vertices are connected to each other, forming a cycle which involves all vertices, and the resulting LDPC codes often have a low minimum Hamming distance. If d variable vertices are connected to each other and a cycle of length 2d is formed, then the minimum Hamming distance of the resulting code is d because the sum of these d columns in the corresponding parity-check matrix \(\varvec{H}\) is \(\varvec{0}^{T}\).
In contrast, for the alternative construction which starts from an increasing degree of the variable vertices, edges are connected to the low-degree variable vertices earlier in the process. Short cycles, which involve the low-degree variable vertices and lead to low minimum Hamming distance, may be avoided by ensuring these low-degree variable vertices have edges connected to the parity-check vertices which are connected to high-degree variable vertices.
It can be expected that the PEG algorithm will almost certainly produce poor LDPC codes if the degree of the variable vertices is assigned in descending order. It is concluded that all PEG-based LDPC codes should be constructed with increasing variable vertex degree ordering.
Figure 12.7 shows the effect of low-degree variable vertices, especially \(\lambda _2\) and \(\lambda _3\), on the FER performance of various [512, 256] PEG-constructed irregular LDPC codes. Table 12.4 shows the variable degree sequences of the simulated irregular codes. Figure 12.7 indicates that, with the fraction of high-degree variable vertices kept constant, the low-degree variable vertices have influence over the convergence in the waterfall region. As the fraction of low-degree variable vertices is increased, the FER in the low signal-to-noise ratio (SNR) region improves. On the other hand, LDPC codes with a high fraction of low-degree variable vertices tend to have low minimum Hamming distance and as expected, these codes exhibit early error floors. This effect is clearly depicted by Code 7 and Code 8, which have the highest fraction of low-degree variable vertices among all the codes in Fig. 12.7. Of all of the codes, Code 6 and Code 24 appear to have the best performance.
Fig. 12.8
Effect of high-degree variable vertices
×
Figure 12.8 demonstrates the effect of high-degree variable vertices on the FER performance. These codes are rate 3 / 4 irregular LDPC codes of length 1024 bits with the same degree sequences, apart from their maximum variable vertex degree. One group has maximum degree of 8 and the other group has maximum degree of 12. From Fig. 12.8, it is clear that the LDPC codes with maximum variable vertex degree of 12 converge better under iterative decoding than those codes with maximum variable vertex degree of 8.
Fig. 12.9
Effect of varying low-degree variable vertices
Table 12.5
Variable degree sequences of LDPC codes in Fig. 12.9
Code
\(\lambda _1\)
\(\lambda _2\)
\(\lambda _3\)
\(\lambda _4\)
\(\lambda _5\)
\(\lambda _{12}\)
Code 0
0.000625
0.249375
0.644375
0.105625
Code 1
0.000625
0.249375
0.420000
0.224375
0.105625
Code 2
0.000625
0.249375
0.195000
0.449375
0.105625
Code 3
0.000625
0.249375
0.420000
0.224375
0.105625
Code 4
0.000625
0.249375
0.195000
0.449375
0.105625
Code 5
0.000625
0.249375
0.420000
0.111875
0.111875
0.106250
Code 6
0.000625
0.249375
0.195000
0.224375
0.224375
0.106250
Code 7
0.000625
0.249375
0.420000
0.224375
0.105625
Code 8
0.000625
0.249375
0.195000
0.449375
0.105625
Code 9
0.000625
0.249375
0.449375
0.195000
0.105625
Code 10
0.000625
0.249375
0.449375
0.097500
0.097500
0.105625
Code 11
0.000625
0.249375
0.449375
0.044375
0.150000
0.106250
Code 12
0.000625
0.249375
0.495000
0.150000
0.105000
Code 13
0.000625
0.249375
0.495000
0.075000
0.075000
0.105000
Code 14
0.000625
0.249375
0.495000
0.037500
0.111875
0.105625
Code 15
0.000625
0.249375
0.570000
0.075000
0.105000
Code 16
0.000625
0.249375
0.570000
0.037500
0.037500
0.105000
×
Fig. 12.10
Effect of varying high-degree variable vertices
Table 12.6
Variable degree sequences of LDPC codes in Fig. 12.10
Code
\(\lambda _3\)
\(\lambda _4\)
\(\lambda _5\)
\(\lambda _8\)
\(\lambda _9\)
\(\lambda _{10}\)
\(\lambda _{11}\)
\(\lambda _{12}\)
\(\lambda _{13}\)
\(\lambda _{14}\)
Code 0
0.420000
0.111875
0.111875
0.10625
Code 1
0.420000
0.111875
0.111875
0.10625
Code 2
0.420000
0.111875
0.111875
0.10625
Code 3
0.420000
0.111875
0.111875
0.10625
Code 4
0.420000
0.111875
0.111875
0.10625
Code 5
0.420000
0.111875
0.111875
0.10625
Code 6
0.420000
0.111875
0.111875
0.10625
Code 10
0.434375
0.111875
0.111875
0.091875
Code 11
0.449375
0.111875
0.111875
0.076875
Code 12
0.405000
0.111875
0.111875
0.121250
Code 13
0.390000
0.111875
0.111875
0.136250
Code 20
0.420000
0.127500
0.111875
0.090625
Code 21
0.420000
0.142500
0.111875
0.075625
Code 22
0.420000
0.097500
0.111875
0.120625
Code 23
0.420000
0.082500
0.111875
0.135625
Code 30
0.420000
0.111875
0.127500
0.090625
Code 31
0.420000
0.111875
0.142500
0.075625
Code 32
0.420000
0.111875
0.097500
0.120625
Code 33
0.420000
0.111875
0.082500
0.135625
Note that \(\lambda _1=0.000625\) and \(\lambda _2=0.249375\)
×
In a similar manner to Fig. 12.7, the effect of having various low-degree variable vertices is also demonstrated in Fig. 12.9. In this case, the LDPC codes are constructed to have the advantageous linear-time encoding complexity, where the parity symbols are commonly described as having a zigzag pattern [26]. In this case, \(\lambda _1\) and \(\lambda _2\) of these LDPC codes are fixed and the effect of varying \(\lambda _3\), \(\lambda _4\) and \(\lambda _5\) is investigated. The variable degree sequences of the LDPC codes under investigation, which are rate 3 / 4 codes of length 1600 bits, are depicted in Table 12.5. The results show that, as in the previous cases, these low-degree variable vertices contribute to the waterfall region of the FER curve. The contribution of \(\lambda _{i}\) is more significant than that of \(\lambda _{i+1}\) and this may be observed by comparing the FER curves of Code 1 with either Code 3 or Code 4, which has \(\lambda _3\) of 0.0. We can also see that Code 0, which has the most variable vertices of low degree, exhibits a high error floor.
In contrast to Fig. 12.9, Fig. 12.10 shows the effect of varying high-degree variable vertices. The LDPC codes considered here all have the same code rate and code length as those in Fig. 12.9 and their variable degree sequences are shown in Table 12.6. The results show that
The contribution of the high-degree variable vertices is in the high SNR region. Consider Code 10 to Code 33, those LDPC codes that have larger \(\lambda _{12}\) tend to be more resilient to errors in the high SNR region than those with smaller \(\lambda _{12}\). At \(E_b/N_o=3.0\) dB, Code 10, Code 11 and Code 12 are inferior to Code 13 and similarly, Code 23 and Code 33 have the best performance in their group.
Large values of maximum variable vertex degree may not always lead to improved FER performance. For example, Code 5 and Code 6 do not perform as well as Code 4 at \(E_b/N_o=3.0\) dB. This may be explained as follows. As the maximum variable vertex degree is increased, some of the variable vertices have many edges connected to them, in the other words the corresponding symbols are checked by many parity-check equations. This increases the chances of having unreliable information from some of these equations during iterative decoding. In addition, a larger maximum variable vertex degree also increases the number of short cycles in the underlying Tanner graph of the code. It was concluded also by McEliece et al. [22] and by Etzion et al. [7] that short cycles lead to negative contributions preventing the convergence of the iterative decoder.
12.4 Quasi-cyclic LDPC Codes and Protographs
Despite irregular LDPC codes having lower error rates than their regular counterparts, Luby et al. [18], the extra complexity of the encoder and decoder hardware structure, has made this class of LDPC codes unattractive from an industry point of view. In order to encode an irregular code which has a parity-check matrix \(\varvec{H}\), Gaussian elimination has to be done to transform this matrix into reduced echelon form. Irregular LDPC codes, as shown in Sect. 12.3, may also be constructed by constraining the \(n-k\) low-degree variable vertices of the Tanner graph to form a zigzag pattern, as pointed out by Ping et al. [26]. Translating these \(n-k\) variable vertices of the Tanner graph into matrix form, we have
The matrix \(\varvec{H}_p\) is non-singular and the columns of this matrix may be used as the coordinates of the parity-check bits of an LDPC code.
The use of zigzag parity checks does simplify the derivation of the encoder as the Gaussian elimination process is no longer necessary and encoding, assuming that
can be performed by calculating parity-check bits as follows:
Nevertheless, zigzag parity bit checks do not lead to a significant reduction in encoder storage space as the matrix \(\varvec{H}_u\) still needs to be stored. It is necessary to introduce additional structure in \(\varvec{H}_u\), such as using a quasi-cyclic property, to reduce significantly the storage requirements of the encoder.
12.4.1 Quasi-cyclic LDPC Codes
Quasi-cyclic codes have the property that each codeword is a m-sized cyclic shift of another codeword, where m is an integer. With this property simple feedback shift registers may be used for the encoder. This type of code is known as circulant codes defined by circulant polynomials and depending on the polynomials can have significant mathematical structure as described in Chap. 9. A circulant matrix is a square matrix where each row is a cyclic shift of the previous row and the first row is the cyclic shift of the last row. In addition, each column is also a cyclic shift of the previous column and the column weight is equal to the row weight.
A circulant matrix is defined by a polynomial r(x). If r(x) has degree \({<}{m}\), the corresponding circulant matrix is an \(m \times m\) square matrix. Let \(\varvec{R}\) be a circulant matrix defined by r(x), then \(\varvec{M}\) is of the form
where the polynomial in each row can be represented by an m-dimensional vector, which contains the coefficients of the corresponding polynomial. A quasi-cyclic code can be built from the concatenation of circulant matrices to define the generator or parity-check matrix.
Example 12.4
A quasi-cyclic code with defining polynomials \(r_1(x) = 1+x+x^3\) and \(r_2(x)=1+x^2+x^5\), where both polynomials have degree less than the maximum degree of 6, produces a parity-check matrix in the following form:
(Permutation Matrix) A permutation matrix is a type of circulant matrix where each row or column has weight of 1. A permutation matrix, which is denoted by \(\varvec{P}_{m,j}\), has \(r(x) = x^j \pmod { x^m-1}\) as the defining polynomial and it satisfies the property that \(\varvec{P}^2_{m,j} = \varvec{I}_m\), where \(\varvec{I}_m\) is an \(m \times m\) identity matrix.
Due to the sparseness of the permutation matrix, these are usually used to construct quasi-cyclic LDPC codes. The resulting LDPC codes produce a parity-check matrix in the following form:
From (12.12), we can see that there exists a \(s \times t\) matrix, denoted by \(\varvec{O}\), in \(\varvec{H}\). This matrix is called an offset matrix and it represents the exponent of r(x) in each permutation matrix, i.e.
where \(0 \le O_{i,j} \le m-1\), for \(0 \le i \le s-1\) and \(0 \le j \le t-1\). The permutation matrix \(\varvec{P}_{m,j}\) has m rows and m columns, and since the matrix \(\varvec{H}\) contains s and t of these matrices per row and column, respectively, the resulting code is a \([mt,m(t-s),d]\) quasi-cyclic LDPC code over \(\mathbb {F}_2\).
In general, some of the permutation matrices \(\varvec{P}_{i,j}\) in (12.12) may be zero matrices. In this case, the resulting quasi-cyclic LDPC code is irregular and \(O_{i,j}\) for which \(\varvec{P}_{i,j}=\varvec{O}\) may be ignored. If none of the permutation matrices in (12.12) is a zero matrix, the quasi-cyclic LDPC code defined by (12.12) is a (s, t) regular LDPC code.
12.4.2 Construction of Quasi-cyclic Codes Using a Protograph
A protograph is a miniature prototype Tanner graph of arbitrary size, which can be used to construct a larger Tanner graph by means of replicate and permute operations as discussed by Thorpe [32]. A protograph may also be considered as an \([n^\prime ,k^\prime ]\) linear code \(\mathscr {P}\) of small block length and dimension. A longer code may be obtained by expanding code \(\mathscr {P}\) by an integer factor Q so that the resulting code has parameter \([n=n^\prime Q, k=k^\prime Q]\) over the same field. A simplest way to expand code \(\mathscr {P}\) and also to impose structure in the resulting code is by replacing a non-zero element of the parity-check matrix of code \(\mathscr {P}\) with a \(Q \times Q\) permutation matrix, and a zero element with a \(Q \times Q\) zero matrix. As a consequence, the resulting code has a quasi-cyclic structure. The procedure is described in detail in the following example.
Example 12.5
Consider a code \(\mathscr {P}=[4,2]\) over \(\mathbb {F}_2\) as a protograph. The parity-check matrix of code \(\mathscr {P}\) is given by
(12.13)
Let the expansion factor \(Q=5\), the expanded code, which is a [20, 10] code, has a parity-check matrix given by
(12.14)
where the zero elements have been omitted. This protograph construction may also be described using the Tanner graph representation as shown in Fig. 12.11.
Fig. 12.11
Code construction using a protograph
×
Initially, the Tanner graph of code \(\mathscr {P}\) is replicated Q times. The edges of these replicated Tanner graphs are then permuted. The edges may be permuted in many ways and in this particular example, we want the permutation to produce a code which has quasi-cyclic structure. The edges shown in bold in Fig. 12.11 or equivalently the non-zeros shown in bold in (12.14) represent the code \(\mathscr {P}\).
The minimum Hamming distance of code \(\mathscr {P}\) is 2 and this may be seen from its parity-check matrix, (12.13), where the summation of two column vectors, those of \(v_1\) and \(v_3\), produces a zero vector. Since, in the expansion, only identity matrices are employed, the expanded code will have the same minimum Hamming distance as the protograph code. This is obvious from (12.14) where the summation of two column vectors, those of \(v_5\) and \(v_{15}\), produces a zero vector. In order to avoid the expanded code having low minimum Hamming distance, permutation matrices may be used instead and the parity-check matrix of the expanded code is given by (12.15).
(12.15)
The code defined by this parity-check matrix has minimum Hamming distance of 3. In addition, the cycle structure of the protograph is also preserved in the expanded code if only identity matrices are used for expansion. Since the protograph is such a small code, the variable vertex degree distribution required to design a good target code, which has much larger size than a protograph does, in general, causes many inevitable short cycles in the protograph. Using appropriate permutation matrices in the expansion, these short cycles may be avoided in the expanded code.
In the following, we describe a construction of a long quasi-cyclic LDPC code for application in satellite communications. The standard for digital video broadcasting (DVB), which is commonly known as DVB-S2, makes use of a concatenation of LDPC and BCH codes to protect the video stream. The parity-check matrices of DVB-S2 LDPC codes contain a zigzag matrix for the \(n-k\) parity coordinates and quasi-cyclic matrices on the remaining k coordinates. In the literature, the code with this structure is commonly known as the irregular repeat accumulate (IRA) code [12].
The code construction described below, using a protograph and greedy PEG expansion, is aimed at improving the performance compared to the rate 3 / 4 DVB-S2 LDPC code of block length 64800 bits. Let the [64800, 48600] LDPC code that we will construct be denoted by \(\mathscr {C}_1\). A protograph code, which has parameter [540, 405], is constructed using the PEG algorithm with a good variable vertex degree distributions obtained from Urbanke [34],
The constructed [540, 405] protograph code has a parity-check matrix \(\varvec{H}^\prime =[\varvec{H}^\prime _u \mid \varvec{H}^\prime _p]\) where \(\varvec{H}^\prime _p\) is a \(135 \times 135\) zigzag matrix, see (12.10), and \(\varvec{H}^\prime _u\) is an irregular matrix satisfying \(\varLambda _{\lambda _1}(x)\) above. In order to construct a [64800, 48600] LDPC code \(\mathscr {C}_1\), we need to expand the protograph code by a factor of \(Q=120\). In expanding the protograph code, we apply the greedy approach to construct the offset matrix \(\varvec{O}\) in order to obtain a Tanner graph for the [64800, 48600] LDPC code \(\mathscr {C}_1\), which has local girth maximised. This greedy approach examines all offset values, from 0 to \(Q-1\), and picks an offset that results in highest girth or if there is more than one choice, one of these is randomly chosen. A \(16200 \times 48600\) matrix \(\varvec{H}_u\) can be easily constructed by replacing a non-zero element at coordinate (i, j) in \(\varvec{H}^\prime _u\) with a permutation matrix \(\varvec{P}_{Q,O_{i,j}}\). The resulting LDPC code \(\mathscr {C}_1\) has a parity-check matrix given by \(\varvec{H}=[\varvec{H}_u \mid \varvec{H}_p]\), where, as before, \(\varvec{H}_p\) is given by (12.10).
In comparison, the rate 3 / 4 LDPC code of block length 64800 bits specified in the DVB-S2 standard takes a lower Q value, \(Q=45\). The protograph is a [1440, 1080] code which has the following variable vertex degree distributions
For convenience, we denote the DVB-S2 LDPC code by \(\mathscr {C}_2\).
Fig. 12.12
FER performance of the DVB-S2 and the designed [64800, 48600] LDPC codes
×
Figure 12.12 compares the FER performance of \(\mathscr {C}_1\) and \(\mathscr {C}_2\) using the belief propagation decoder with 100 iterations. Binary antipodal signalling and AWGN channel are assumed. Note that, although the outer concatenation of BCH code is not used, there is still no sign of an error floor at FER as low as \(10^{-6}\) which means that the BCH code is no longer required. It may be seen from Fig. 12.12 that the designed LDPC code, which at \(10^{-5}\) FER performs approximately 0.35 dB away from the sphere packing lower bound offset for binary transmission loss, is 0.1 dB better than the DVB-S2 code.
12.5 Summary
The application of cyclotomic cosets, idempotents and Mattson–Solomon polynomials has been shown to produce many binary cyclic LDPC codes whose parity-check equations are orthogonal in each position. Whilst some of these excellent cyclic codes have the same parameters as the known class of finite geometry codes, other codes are new. A key feature of this construction technique is the incremental approach to the minimum Hamming distance and the sparseness of the resulting parity-check matrix of the code. Binary cyclic LDPC codes may also be constructed by considering idempotents in the Mattson–Solomon domain. This approach has provided a different insight into the cyclotomic coset-based construction. It has also been shown that, for short algebraic LDPC codes, the myths of codes which have cycles of length 4 in their Tanner graph do not converge well with iterative decoding is not necessarily true. It has been demonstrated that the cyclotomic coset-based construction can be easily extended to produce good non-binary algebraic LDPC codes.
Good irregular LDPC codes may be constructed using the progressive edge-growth algorithm. This algorithm adds edges to the variable and check vertices in a way that maximises the local girth. Many code results have been presented showing the effects of choosing different degree distributions. Guidelines are given for designing the best codes.
Methods of producing structured LDPC codes, such as those which have quasi-cyclic structure, have been described. These are of interest to industry due to the simplification of the encoder and decoder. An example of such a construction to produce a (64800, 48600) LDPC code, using a protograph, has been presented along with performance results using iterative decoding. Better results are obtained with this code than the (64800, 48600) LDPC code used in the DVB-S2 standard.
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the book’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the book’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Since the Mattson–Solomon polynomial of a binary polynomial is an idempotent and vice-versa [20], the Mattson–Solomon polynomial of a binary idempotent is also a binary idempotent.
can be performed by calculating parity-check bits as follows:Nevertheless, zigzag parity bit checks do not lead to a significant reduction in encoder storage space as the matrix \(\varvec{H}_u\) still needs to be stored. It is necessary to introduce additional structure in \(\varvec{H}_u\), such as using a quasi-cyclic property, to reduce significantly the storage requirements of the encoder.
Let the expansion factor \(Q=5\), the expanded code, which is a [20, 10] code, has a parity-check matrix given by
where the zero elements have been omitted. This protograph construction may also be described using the Tanner graph representation as shown in Fig. 12.11.
The code defined by this parity-check matrix has minimum Hamming distance of 3. In addition, the cycle structure of the protograph is also preserved in the expanded code if only identity matrices are used for expansion. Since the protograph is such a small code, the variable vertex degree distribution required to design a good target code, which has much larger size than a protograph does, in general, causes many inevitable short cycles in the protograph. Using appropriate permutation matrices in the expansion, these short cycles may be avoided in the expanded code.