Recently, a new class of Low-Density Parity-Check (LDPC) codes constructed from a template was introduced. This kind of codes were called protograph codes. The protograph serves as a blueprint for constructing LDPC codes of arbitrary size whose performance can be predicted by analyzing the protograph. Protograph LDPC codes perform very well and suit for high-speed encoding and decoding. However, there are few researches on expansion and encoding algorithms for them. In this paper, using isomorphism between matrix ring and polynomial ring, we propose efficient quasi-cyclic expansion and encoding algorithms for protograph LDPC codes. Simulation results show that the protograph LDPC codes which were constructed by the algorithm proposed in this paper, outperform the best known unstructured irregular LDPC codes with the same maximum node degrees.
Recently, a new class of Low-Density Parity-Check (LDPC) codes constructed from a template was introduced. This kind of codes were called protograph codes. The protograph serves as a blueprint for constructing LDPC codes of arbitrary size whose performance can be predicted by analyzing the protograph. Protograph LDPC codes perform very well and suit for high-speed encoding and decoding. However, there are few researches on expansion and encoding algorithms for them. In this paper, using isomorphism between matrix ring and polynomial ring, we propose efficient quasi-cyclic expansion and encoding algorithms for protograph LDPC codes. Simulation results show that the protograph LDPC codes which were constructed by the algorithm proposed in this paper, outperform the best known unstructured irregular LDPC codes with the same maximum node degrees.
One of the important code of modern coding theory, the protograph LDPC code technology has been gained more and more attention due to its low encoding complexity, fast decoding speed, low BER, and simple optimization analysis process etc. the quasi-cyclic expansion algorithm of the protograph LDPC codes, named as PQCE algorithms, can complete the extension of protograph and eventually get the protograph LDPC codes. However, the existing PQCE algorithms may be with a low convergence rate, or exist many short cycles in the check matrix. To solve the above problem, a Quasi-cyclic expansion algorithm for protograph LDPC codes based on PEG and PH is proposed in this paper, referred as PEG-PH-PQCE algorithm. In the proposed algorithm, base matrix is acquired by PEG parallel edges elimination expansion algorithm during the first-step expansion of protograph. Then, the second-step expansion is completed, in which the initial index matrix is obtained by PEG quasi-cyclic expansion algorithm, and the check matrix is acquired by using the Hill Climbing algorithm to optimizing the initial index matrix. Simulation results demonstrate the effectiveness the validity of the proposed algorithm, such as, a small number of short cycles and high convergence rate, etc.
The masking matrix plays an important role in constructing new classes of regular and irregular quasi-cyclic low density parity check (QC-LDPC) codes. By coupling two identical graphs in a special way, we present a new structure of the masking matrix, whose Tanner graph can be seen as a protograph. From this perspective, we propose a Gaussian Approximation algorithm for protograph-based LDPC codes to analyze the asymptotic performance of this class of codes. It is shown that, although the proposed structure of the masking matrix has almost the same convergence threshold as the conventional one produced randomly by progressive edge growth (PEG) algorithm, the former converges faster than the latter. Simulation results illustrate that the QC-LDPC code constructed by the proposed structure of the masking matrix has about 0.2dB coding gains compared with the conventional one.
Channel coding is a key component of artificial communication systems, allowing reliable communication using unreliable channels. In the last decade, iteratively decoded channel codes have become or clearly will become standards in a wide range of applications where large amounts of information must be communicated using unreliable media. Of the class of iteratively decoded codes, Low-density parity check (LDPC) codes are arguably the simplest class to describe, and indeed were described more than four decades ago in 1963 by Robert Gallager. The current understanding of LDPC codes has progressed in several significant ways beyond what had been expressed by 1963 by Gallager. Importantly, irregular LDPC codes, whose parity check matrices do not have constant row and column sums, have been shown to significantly outperform their regular counterparts explicitly considered by Gallager. By 1999, researchers had defined a class of irregular ensembles, each characterized by a pair of polynomials. Along with this new class of ensemble, they defined an analytical technique, density evolution, that accurately predicted the channel coding performance of a typical code under iterative message-passing decoding. The pair of polynomials could be effectively be designed by optimizing the coefficients of the polynomial for density evolution threshold threshold. This thesis concerns a different class of ensembles, namely protograph ensembles. Protograph ensembles are characterized by a template graph called, intuitively, a protograph. The Tanner-graph representation of a code in the ensemble is a random lift of the protograph. Protograph-based codes have significant advantages over unstructured irregular codes in regard to implementation of their encoders and decoders. In the decoder, this structure can be used in at least two distinct ways to organize the computations defined by any message-passing algorithm. If, in addition to the protograph structure, circulant structure is imposed on each "section" of the matrix then a quasi-cyclic code results, bestowing even mores advantages, especially in the possible implementation of the encoder. A central difficulty in using protograph ensembles is finding a suitable protograph. Since graphs are discrete objects, there is no obvious correspondence to any optimization model using vectors of real numbers. Instead, the technique of simulated annealing has been applied with a remarkable degree of success. For example, on the AWGN channel, given a constraint on the node degrees, protograph ensembles can be found that achieve a threshold only half as far (measured in dB) from the Shannon limit as unstructured irregular ensembles. This simultaneously illustrates an inherent performance advantage of protograph codes over unstructured codes as well as the efficacy of simulated annealing as an optimization technique. A persistent problem which appears to be common in all codes optimized for density evolution threshold is that of error floors. On a superficial level, this is explained by the maxim that "There's no such thing as a free lunch." In some contexts, such as in codes designed for the erasure channel, the phenomenon can be explained on a much deeper level, though it is not clear why the phenomenon should persist so universally. Still, even without a detailed understanding the cause of this problem, there are techniques that can mitigate error floors. An important tool toward this end is weight enumerators, which are discussed in chapter 3. Codeword and stopping set enumerators can be efficiently computed if a certain (non-concave) function can be efficiently maximized. Protographs that are selected on the basis of their enumerators have shown some success in reducing error floors.
To obtain efficient and pragmatic channel codes high signal-to-noise ratios (SNRs), an optimized construction of short and high rate protograph quasi-cyclic (QC) low-density parity-check (LDPC) codes is presented. Based on an optimized protograph template, the code framework is firstly produced by the extensions of the variable nodes. By enlarging the dimension of the sub-matrices related to the protograph framework, the base quasi-cyclic (QC) matrix is generated with required code rate and length. Then, the elements in the base matrix are split with even smaller square sub-matrices of the same row and column weights. In this procedure, a progressive edge growth (PEG) algorithm is employed to find the optimized positions of the QC submatrices, which brings larger girth for better code performance. Also the circulant offsets in all QC sub-matrices are optimally searched by a QC improved approximated cycle extrinsic message degree (QCI-ACE) algorithm, which improves the relationship of the unavoidable loops in the code's Tanner graph and thus it improves the error floor. Simulation results show that the codes produced by the proposed method demonstrate quite good bit error rate (BER) performance. In addition, they exhibit good properties of high spectrum efficiency by the high code rate, as well as the low complexity by the short code length. Therefore, the proposed code construction can be efficiently applied in the design of short and high rate protograph QC-LDPC codes with high rate and rational complexity.
In this paper, a novel methodology for designing structured generalized low-density parity-check (G-LDPC) codes is presented. The proposed design results in quasi-cyclic G-LDPC codes for which efficient encoding is feasible through shift-register-based circuits. The structure imposed on the bipartite graphs, together with the choice of simple component codes, leads to a class of codes suitable for fast iterative decoding. A pragmatic approach to the construction of G-LDPC codes is proposed. The approach is based on the substitution of check nodes in the protograph of a low-density parity-check code with stronger nodes based, for instance, on Hamming codes. Such a design approach, which we call low-density parity-check (LDPC) code doping, leads to low-rate quasi-cyclic G-LDPC codes with excellent performance in both the error floor and waterfall regions on the additive white Gaussian noise channel.