In practical LDPC design one is invariably interested in achieving the best possible performance. Although we have used the framework of irregular low-density parity-check (LDPC) ensembles throughout this book, the notion of “irregularity” we have employed is not the most general possible and the best performing structures are not properly captured in that framework. We start by presenting in Section 7.1 a generalization of irregular LDPC ensembles called multi-edge-type LDPC ensembles . In principle, any of the ensembles suggested to date can be represented in this form and we demonstrate this discussing a few examples. In Section 7.2 we review the theory surrounding these ensembles. It is largely the same as for the standard irregular case, which is why we have avoided using this more complex notion so far. The multi-edge-type generalization enjoys several advantages. With multi-edge-type LDPC codes one can achieve better performance at lower complexity. The generalization is especially useful under extreme conditions where standard irregular LDPC codes do not fare so well. Examples of these conditions include very low code rates, high rate codes that target very low bit error rates, and codes used in conjunction with turbo equalization schemes. We discuss in Section 7.3 an alternative and complementary way of describing structured ensembles. These ensembles are the result of lifting a very small graph to a large graph by first replicating the structure of the small graph a large number of times and then by choosing the connections between these copies in a random way.
In practical LDPC design one is invariably interested in achieving the best possible performance. Although we have used the framework of irregular low-density parity-check (LDPC) ensembles throughout this book, the notion of “irregularity” we have employed is not the most general possible and the best performing structures are not properly captured in that framework. We start by presenting in Section 7.1 a generalization of irregular LDPC ensembles called multi-edge-type LDPC ensembles . In principle, any of the ensembles suggested to date can be represented in this form and we demonstrate this discussing a few examples. In Section 7.2 we review the theory surrounding these ensembles. It is largely the same as for the standard irregular case, which is why we have avoided using this more complex notion so far. The multi-edge-type generalization enjoys several advantages. With multi-edge-type LDPC codes one can achieve better performance at lower complexity. The generalization is especially useful under extreme conditions where standard irregular LDPC codes do not fare so well. Examples of these conditions include very low code rates, high rate codes that target very low bit error rates, and codes used in conjunction with turbo equalization schemes. We discuss in Section 7.3 an alternative and complementary way of describing structured ensembles. These ensembles are the result of lifting a very small graph to a large graph by first replicating the structure of the small graph a large number of times and then by choosing the connections between these copies in a random way.
Low-density parity-check (LDPC) codes have been shown to have good error correcting performance approaching Shannon’s limit. Good error correcting performance enables efficient and reliable communication. However, a LDPC code decoding algorithm needs to be executed efficiently to meet cost, time, power and bandwidth requirements of target applications. The constructed codes should also meet error rate performance requirements of those applications. Since their rediscovery, there has been much research work on LDPC code construction and implementation. LDPC codes can be designed over a wide space with parameters such as girth, rate and length. There is no unique method of constructing LDPC codes. Existing construction methods are limited in some way in producing good error correcting performing and easily implementable codes for a given rate and length. There is a need to develop methods of constructing codes over a wide range of rates and lengths with good performance and ease of hardware implementability. LDPC code hardware design and implementation depend on the structure of target LDPC code and is also as varied as LDPC matrix designs and constructions. There are several factors to be considered including decoding algorithm computations,processing nodes interconnection network, number of processing nodes, amount of memory, number of quantization bits and decoding delay. All of these issues can be handled in several different ways. \nThis thesis is about construction of LDPC codes and their hardware implementation. LDPC code construction and implementation issues mentioned above are too many to be addressed in one thesis. The main contribution of this thesis is the development of LDPC code construction methods for some classes of structured LDPC codes and techniques for reducing decoding time. We introduce two main methods for constructing structured codes. In the first method, column-weight two LDPC codes are derived from distance graphs. A wide range of girths, rates and lengths are obtained compared to existing methods. The performance and implementation complexity of obtained codes depends on the structure of their corresponding distance graphs. In the second method, a search algorithm based on bit-filing and progressive-edge growth algorithms is introduced for constructing quasi-cyclic LDPC codes. The algorithm can be used to form a distance or Tanner graph of a code. This method could also obtain codes over a wide range of parameters. Cycles of length four are avoided by observing the row-column constraint. \nRow-column connections observing this condition are searched sequentially or randomly. Although the girth conditions are not sufficient beyond six, larger girths codes were easily obtained especially at low rates. The advantage of this algorithm compared to other methods is its flexibility. It could be used to construct codes for a given rate and length with girths of at least six for any sub-matrix configuration or rearrangement. The code size is also easily varied by increasing or decreasing sub-matrix size. Codes obtained using a sequential search criteria show poor performance at low girths (6 and 8) while random searches result in good performing codes. \nQuasi-cyclic codes could be implemented in a variety of decoder architectures. One of the many options is the choice of processing nodes interconnect. We show how quasi-cyclic codes processing could be scheduled through a multistage network. Although these net-works have more delay than other modes of communication, they offer more flexibility at a reasonable cost. Banyan and Benes networks are suggested as the most suitable networks. \nDecoding delay is also one of several issues considered in decoder design and implementation. In this thesis, we overlap check and variable node computations to reduce decoding time. Three techniques are discussed, two of which are introduced in this thesis. The techniques are code matrix permutation, matrix space restriction and sub-matrix row-column scheduling. Matrix permutation rearranges the parity-check matrix such that rows and columns that do not have connections in common are separated. This techniques can be applied to any matrix. Its effectiveness largely depends on the structure of the code. We show that its success also depends on the size of row and column weights. Matrix space restriction is another technique that can be applied to any code and has fixed reduction in time or amount of overlap. Its success depends on the amount of restriction and may be traded with performance loss. The third technique already suggested in literature relies on the internal cyclic structure of sub-matrices to achieve overlapping. The technique is limited to LDPC code matrices in which the number of sub-matrices is equal to row and column weights. We show that it can be applied to other codes with a lager number of sub-matrices than code weights. However, in this case maximum overlap is not guaranteed. We calculate the lower bound on the amount of overlapping. Overlapping could be applied to any sub-matrix configuration of quasi-cyclic codes by arbitrarily choosing \nthe starting rows for processing. Overlapping decoding time depends on inter-iteration waiting times. We show that there are upper bounds on waiting times which depend on the code weights. Waiting times could be further reduced by restricting shifts in identity sub-matrices or using smaller sub-matrices. This overlapping technique can reduce the decoding time by up to 50% compared to conventional message and computation scheduling. \nTechniques of matrix permutation and space restriction results in decoder architectures that are flexible in LDPC code design in terms of code weights and size. This is due to the fact that with these techniques, rows and columns are processed in sequential order to achieve overlapping. However, in the existing technique, all sub-matrices have to be processed in parallel to achieve overlapping. Parallel processing of all code sub-matrices requires the architecture to have the number of processing units at least equal to the number sub-matrices. Processing units and memory space should therefore be distributed among the sub-matrices according to the sub-matrices arrangement. This leads to high complexity or inflexibility in the decoder architecture. We propose a simple, programmable and high throughput decoder architecture based on matrix permutation and space restriction techniques.
We construct lattices with high coding gains based on nested low-density parity-check (LDPC) codes by Construction D′.We generalize the LDPC lattices [1] to have irregular degrees and call them irregular LDPC lattices. To construct good irregular LDPC lattices, we optimize the degree distributions by using density evolution and a modified sequential quadratic programming (SQP) and show our optimized irregular LDPC lattice has a threshold 0.48dB from the capacity, which is about 0.6dB better than the regular one in [1]. To construct a Tanner graph corresponding to LDPC lattices, we generalize the progressive-edge growth (PEG) algorithm and show a lower bound on the girth of the graph. Simulation is performed using the sum-product algorithm. Also, we compare the performance of joint decoding and multi-stage decoding [2] and show the advantage of joint decoding.
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.
Introduction The construction of binary low-density parity-check (LDPC) codes simply involves replacing a small number of the values in an all-zeros matrix by 1s in such a way that the rows and columns have the required degree distribution. In many cases, randomly allocating the entries in H will produce a reasonable LDPC code. However, the construction of H can affect the performance of the sum–product decoder, significantly so for some codes, and also the implementation complexity of the code. While there is no one recipe for a “good” LDPC code, there are a number of principles that inform the code designer. The first obvious decisions are which degree distribution to choose and how to construct the matrix with the chosen degrees, i.e. pseudo-randomly or with some sort of structure. Whichever construction is chosen, the features to consider include the girth of the Tanner graph and the minimum distance of the code. In this chapter we will discuss those properties of an LDPC code that affect its iterative decoding performance and then present the common construction methods used to produce codes with the preferred properties. Following common practice in the field we will call the selection of the degree distributions for an LDPC code code design and the methods to assign the locations in the parity-check matrix for the 1 entries code construction .
Multi-edge type LDPC codes are introduced by Richardson and Urbanke, and they show examples of their ensembles have better performance than other known ensembles. Orlitsky et al. derived the condition for irregular LDPC code ensembles with small linear weight codewords exponentially decreasing in code length. Nakasendo et al. derived the condition in which code ensembles have exponentially decreasing small linear weight codewords for two-edge type LDPC code ensembles which is simple example of multi-edge type LDPC code ensembles. Our conclusion is the same as that of Nakasendo et al., and although Nakasendopsilas method is difficult to apply to more than three edge-types, there is a possibility that our method using Hayman approximation as Di et al. do derives the condition for multi-edge type LDPC codes ensembles.