Type II and III low-density parity-check codes (QC-LDPC) codes have been shown to have better minimum distance compared to Type I QC-LDPC codes. This article presents a highly flexible method for constructing high-girth type II and III QC-LDPC codes. The proposed algorithm establishes constraints to be observed in creating a bipartite graph of a given girth. The algorithm is by far more flexible in constructing a wide range (rates and lengths) of type II and III QC-LDPC codes compared to existing methods. Although the proposed algorithm uses a search approach to construct codes, it generally successfully constructs a code even at low code lengths. Constructed codes show better bit error rate performances compared to type I codes as expected.
Type II and III low-density parity-check codes (QC-LDPC) codes have been shown to have better minimum distance compared to Type I QC-LDPC codes. This article presents a highly flexible method for constructing high-girth type II and III QC-LDPC codes. The proposed algorithm establishes constraints to be observed in creating a bipartite graph of a given girth. The algorithm is by far more flexible in constructing a wide range (rates and lengths) of type II and III QC-LDPC codes compared to existing methods. Although the proposed algorithm uses a search approach to construct codes, it generally successfully constructs a code even at low code lengths. Constructed codes show better bit error rate performances compared to type I codes as expected.
This article presents a highly flexible method for constructing high-girth quasi-cyclic low-density parity-check (QC-LDPC) codes. The proposed algorithm constructs a Tanner graph formed by connecting groups of rows (check nodes) and columns (variable nodes) of the constructed code. To obtain a sub-matrix structure, rows and columns are divided into groups of equal sizes. Rows and columns in a group are connected in their numerical (positional) order to obtain a cyclic structure. Connected rows and columns must satisfy the desired minimum cycle length. We present conditions that guarantee desired girths. The proposed algorithm is by far more flexible in constructing a wide range (rates and lengths) of regular and irregular QC-LDPC codes compared to existing methods. The algorithm, which has linear complexity with respect to the number of rows or columns, provides an easy and fast way to construct QC-LDPC codes. Constructed codes show good bit error rate performances.
In this paper, we consider the constructions of type-II quasi-cyclic (QC) low-density parity-check (LDPC) codes with girth eight from a Sidon sequence. We first derive the necessary and sufficient conditions guaranteeing a girth-eight type-II QC-LDPC code. By combining these conditions with the concept of the Sidon sequence, three classes of type-II QC-LDPC codes are subsequently proposed with girth eight. To the best of our knowledge, the second and the third classes we proposed are the first series of systematic and algebraic constructions for the girth-eight type-II QC-LDPC codes that have rates being greater than a half and, at the same time, have distance upper bounds being not limited to 12. Via simulations, we show the promising performance of the proposed type-II QC-LDPC codes with girth eight. In addition, a set of general bounds and explicit/random constructions without using a Sidon sequence are also presented for the type-II QC-LDPC codes with girth six or eight. We observe that the proposed codes perform better than or equally well as the random QC-LDPC codes from PEG and quadr.-congr. methods, while the novel codes possess both highly structured parity-check matrices and very flexible choices in circulant size.
Multitype quasi-cyclic (QC) low-density parity-check (LDPC) codes are a class of protograph LDPC codes lifted cyclically from protographs with multiple edges, represented by two weight and slope matrices. For a given weight-matrix, an approach is proposed to find the maximum-achievable girthgmaxof the corresponding multitype QC-LDPC codes by some inevitable chains having less complexity than the existing methods. This advantage leads to some new patterns of the weight matrices such that the corresponding codes have some improvements in terms of the maximum-achievable girths or the minimum-distance upper-bounds. In continue, for a given weight-matrix with maximum-achievable girthgmax, some slope-matrices are constructed by a depth-first search algorithm for which the corresponding multitype QC-LDPC codes with even girthg,g≤gmax, have smaller lengths, higher rates, or larger minimum-distances than the state-of-the-art achievements. Simulation results show that the constructed codes have some error-rate advantages than PEG, random-like, CCSDS, and 802.11n/ac IEEE standard LDPC codes.
Four classes of maximum-girth geometrically structured column-weight-two regular quasi-cyclic (QC) low-density parity-check (LDPC) codes are introduced. Two classes of these codes, referred to as Type-I and Type-II codes, are with row-weights 4 and 3, and maximum girths 16 and 24, respectively. The idea behind the construction of these two classes of codes, with rates at least 1/2 and 1/3, is slightly generalized to obtain two classes of variable-high-rate codes, referred to as Type-III1 and Type-III2 codes, with maximum girth 20 and 16, respectively. A low-complexity deterministic algorithm for constructing these four classes of codes is given. The algorithm generates maximum-girth Type-I and Type-II codes with almost arbitrary length eta not less than 216 and 243, respectively. The output of the algorithm substantially improves on some of the previously best known codes constructed using a randomized progressive edge-growth (RPEG) algorithm. For instance, we have rate-0.71 Type-III1 codes of lengths 308 and 728 with girths 10 and 12, respectively, versus the code lengths 385 and 840 obtained by the RPEG algorithm. Simulation results on AWGN channel confirm that, from BER performance perspective, the constructed LDPC codes are superior to the column-weight-two LDPC codes constructed by the previously reported methods. The generator matrix G(D) of the convolutional codes associated with Type-I and Type-II codes is given. The free distance dfreeof such a convolutional code is equal to the minimum distance of the corresponding QC block code.
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.