Array‐based non‐binary (NB) low‐density parity‐check (LDPC) codes are attractive in practice for their advantages in implementation and performance. However, existing construction of array‐based NB LDPC codes is only with the prime number cases. In this Letter, the authors extend the array‐based construction to composite numbers to give an explicit construction of structured array‐based NB LDPC codes with column weights three, four, and five. The resulting codes have girth at least six. The simulation results show that the proposed structured codes perform as well as the random codes constructed by progressive edge‐growth algorithm, when decoded with the Q‐ary sum product algorithm and the low‐complexity weighted bit‐reliability‐based decoding algorithm.
Array‐based non‐binary (NB) low‐density parity‐check (LDPC) codes are attractive in practice for their advantages in implementation and performance. However, existing construction of array‐based NB LDPC codes is only with the prime number cases. In this Letter, the authors extend the array‐based construction to composite numbers to give an explicit construction of structured array‐based NB LDPC codes with column weights three, four, and five. The resulting codes have girth at least six. The simulation results show that the proposed structured codes perform as well as the random codes constructed by progressive edge‐growth algorithm, when decoded with the Q‐ary sum product algorithm and the low‐complexity weighted bit‐reliability‐based decoding algorithm.
This study considers the construction of four‐cycle free quasi‐cyclic low‐density parity‐check (QC‐LDPC) codes. These codes are based on the cyclotomic cosets of q modulo n where q is a prime power, n is a prime and ( n , q ) = 1. If s is the order of q modulo n , then n − 1 = sl for some integer l . Then there are l distinct cyclotomic cosets , 1 ≤ i ≤ l . Concatenation of the l circulant matrices formed using these sets gives an s × sl matrix M co ( n , q ). In addition, the Kronecker product of the transpose of ∪ i with itself modulo n gives an sl × sl matrix M kr ( n , q ). Replacing the entries of these matrices with their associated dispersed binary n × n matrices provides binary QC‐LDPC codes with girth at least six. Furthermore, for any prime power q ′ such that q ′ = n + 1 or q ′ ≥ 2 n , these two matrices can be used to construct q ′‐ary QC‐LDPC codes with girth at least six. These constructions produce large classes of four‐cycle free binary and non‐binary QC‐LDPC codes. Among the structured LDPC codes, the introduced technique, from code‐construction‐complexity perspective, which is an engineering factor, is at least among the best ones if not the best. Performance results are presented which show that the codes obtained perform well over additive white Gaussian noise channel with the iterative sum‐product decoding algorithm.
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.
A new combinatorial technique for constructing girth-6 structured binary regular low-density parity-check (LDPC) codes based on special types of t-designs is given. A very large number of well-known t-designs can be used by this method for code construction. Based on this method, a t-(v,k,λ) design D=(X,B) can be exploited for code construction if it satisfies the following three conditions: 1) |B1 ∩ B2|≤ t for any two blocks B1,B2∈ B and B1≠ B2; 2) λ>1; and 3) k>t. Though the technique works for any t-design satisfying these conditions, we focus only on the utilization of simple triple systems, super-simple BIBDs, Steiner systems, and large sets (LSs) of t-designs. We also construct binary and non-binary girth-6 QC-LDPC codes from the t-designs satisfying these conditions by using matrix dispersion method. Experimental results show that the constructed non-binary QC-LDPC codes can provide good practical performance under iterative decoding using the fast Fourier transform based q-ary sum-product algorithm (FFT-QSPA) and they can achieve acceptable coding gains over random-like codes of comparable parameters decoded with sum-product algorithm (SPA).
Motivated by the superior performance of array-based non-binary low-density parity-check (LDPC) codes, we study in this paper their structural properties by combinational and graphical techniques. The main results are summarized as follows. First, we show that there exist codewords with symbol weight six and seven in array-based non-binary LDPC (NBLDPC) codes with column weight 3. Second, we characterize the graphical substructures induced by weight-6 and weight-7 codewords. Finally, we carry out comparisons to confirm the performance advantage of array-based NBLDPC codes.
In this study, using Group Permutation Low‐Density Parity‐Check (GP‐LDPC) codes, the authors generalise the concept of array Low‐Density Parity‐Check (LDPC) codes from fields of prime order to those of prime power order. In fact, they consider the additive group of the finite field GF( q ), q a prime power, as the underlying group for the GP‐LDPC code construction and since when q is a prime, the author's code construction method coincides with that of quasi‐cyclic array LDPC codes, they call their codes, generalised array LDPC (GA‐LDPC) codes. First, they prove that, like array LDPC codes, GA‐LDPC codes are quasi‐cyclic codes. Then, they analyse the girth of GA‐LDPC codes in a way similar to that for array LDPC codes and introduce some shortened GA‐LDPC codes with girths 8, 10 and 12. For many values of g , J and L , the lengths of ( J , L )‐regular shortened GA‐LDPC codes of girth g and rate at least 1 − J / L , constructed in this study, are smaller than the lengths of ( J , L )‐regular LDPC codes of girth g and rate at least 1 − J / L , constructed in the literature. Also, simulation results show that GA‐LDPC codes perform well with the iterative message‐passing decoding.
This paper,based on algebra and graph,proposes a method for constructing structured low-density parity-check(LDPC) codes.In this method,the authors design a connected graph with three kinds of special path to ensure that the Tanner graph of the parity check matrix mapped from the connected graph is without short cycles.The construction method results in two classes of(3,k)-regular quasi-cyclic LDPC codes with girth 8 and 12 respectively.Furthermore,by extending this construction method,two classes of LDPC codes with column weight 2,whose girths are respectively 16 and 24,can be obtained.The simulation studies show that these codes can achieve better performance than randomly constructed regular LDPC codes over AWGN channels with iterative decoding.At the BER of 10-5,the new proposed(3,6)-regular(4356,2205) QC-LDPC code performs 1.48dB from the Shannon limit.Moreover,it outperforms the random regular LDPC code of comparable parameters by 0.1dB.For the new proposed structured LDPC codes with column weight 2,they can achieve about 2dB coding gains with respect to the random regular LDPC codes with similar block lengths and code rates.