We introduce a new class of low-density parity-check (LDPC) codes constructed from a template called a protograph. The protograph serves as a blueprint for constructing LDPC codes of arbitrary size whose performance can be predicted by analyzing the protograph. We apply standard density evolution techniques to predict the performance of large protograph codes. Finally, we use a randomized search algorithm to find good protographs. I.
We introduce a new class of low-density parity-check (LDPC) codes constructed from a template called a protograph. The protograph serves as a blueprint for constructing LDPC codes of arbitrary size whose performance can be predicted by analyzing the protograph. We apply standard density evolution techniques to predict the performance of large protograph codes. Finally, we use a randomized search algorithm to find good protographs. I.
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.
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.
Irregular low-density parity-check (LDPC) codes constructed from small protographs are one of the most powerful LDPC codes. In this paper, we show that the performance of LDPC codes based on small protographs can be further improved by using different transmission energies for every variable node of the protograph. Thus, a protograph is now described by a set of variable nodes, a set of check nodes, edges connecting variable nodes and check nodes, and the transmission energy used for every variable node, which is called the energy distribution. We optimize the energy distribution of protographs by choosing the energy distribution with the highest threshold calculated with a generalization of the discretized density evolution. Furthermore, we show by simulations that the performance of long LDPC codes based on protographs can be improved as expected from the thresholds.
We consider the design of low-density parity-check (LDPC) codes for a given iterative decoder. While LDPC performance can be evaluated using simulation, density evolution (DE), or EXIT-chart analysis, selecting a parity-check matrix (PCM) remains a difficult combinatorial optimization problem. Existing approaches often rely on population-based search, random mutations, or genetic algorithms, which require careful tuning and incur high computational cost. Recent gradient descent (GD)-based methods optimize relaxed PCMs by differentiating through decoder simulations, but rely on noisy Monte Carlo estimates, line searches over soft matrix representations, and remain costly for long codes. Moreover, the loss is typically evaluated only at integer-valued PCMs. We focus on long protograph-based LDPC codes and propose a deterministic GD-based framework operating directly on a relaxed protograph representation. The loss is based on DE bit error rate (BER) and can be evaluated directly for relaxed protographs. To justify this relaxation, we associate the relaxed representation with an ensemble of binary PCMs and show that the proposed relaxed DE yields the ensemble-averaged DE performance. The resulting procedure supports standard GD optimization and achieves fast, reliable convergence through deterministic DE evaluation and informative gradients. Numerical results show that the optimized protographs outperform 5G LDPC codes with matching dimensions.
In this paper, a new class of low-density parity-check (LDPC) codes, named hybrid LDPC codes, is introduced. Hybrid LDPC codes are characterized by an irregular connectivity profile and heterogeneous orders of the symbols in the codeword. It is shown in particular that the class of hybrid LDPC codes can be asymptotically characterized and optimized using density evolution (DE) framework, and a technique to maximize the minimum distance of the code is presented. Numerical assessment of hybrid LDPC code performances is provided, by comparing them to protograph-based and multiedge-type (MET) LDPC codes. Hybrid LDPC codes are shown to allow to achieve an interesting tradeoff between good error-floor performance and good waterfall region with nonbinary coding techniques.
In this paper, we propose a new method to design low-density parity-check Hadamard (LDPC-Hadamard) codes, a type of ultimate-Shannon-limit approaching channel codes. The technique is based on applying Hadamard constraints to the check nodes in a generalized protograph-based LDPC code, followed by lifting the generalized protograph. We name the codes formed protograph-based LDPC Hadamard (PLDPC-Hadamard) codes. We also propose a modified Protograph Extrinsic Information Transfer (PEXIT) algorithm for analyzing and optimizing PLDPC-Hadamard code designs. The proposed algorithm further allows the analysis of PLDPC-Hadamard codes with degree-1 and/or punctured nodes. We find codes with decoding thresholds ranging from -1.53 dB to -1.42 dB. At a BER of 1e-5, the gaps of our codes to the ultimate-Shannon-limit range from 0.40 dB (for rate = 0.0494) to 0.16 dB (for rate = 0.003). Moreover, the error performance of our codes is comparable to that of the traditional LDPC-Hadamard codes. Finally, the BER performances of our codes after puncturing are simulated and compared.