Low-density parity check (LDPC) codes are very popular among error correction codes because of their high-performance capacity. Numerous investigations have been carried out to analyze the performance and simplify the implementation of LDPC codes. Relatively slow convergence of iterative decoding algorithm affects the performance of LDPC codes. Faster convergence can be achieved by reducing the number of iterations during the decoding process. In this thesis, a new approach for faster convergence is suggested by choosing a systematic parity check matrix that yields lowest Second Smallest Eigenvalue Modulus (SSEM) of its corresponding Laplacian matrix. MATLAB simulations are used to study the impact of eigenvalues on the number of iterations of the LDPC decoder. It is found that for a given (n, k) LDPC code, a parity check matrix with lowest SSEM converges quickly as compared to the parity check matrix with high SSEM. In other words, a densely connected graph that represents the parity check matrix takes more iterations to converge than a sparsely connected graph.
Low-density parity check (LDPC) codes are very popular among error correction codes because of their high-performance capacity. Numerous investigations have been carried out to analyze the performance and simplify the implementation of LDPC codes. Relatively slow convergence of iterative decoding algorithm affects the performance of LDPC codes. Faster convergence can be achieved by reducing the number of iterations during the decoding process. In this thesis, a new approach for faster convergence is suggested by choosing a systematic parity check matrix that yields lowest Second Smallest Eigenvalue Modulus (SSEM) of its corresponding Laplacian matrix. MATLAB simulations are used to study the impact of eigenvalues on the number of iterations of the LDPC decoder. It is found that for a given (n, k) LDPC code, a parity check matrix with lowest SSEM converges quickly as compared to the parity check matrix with high SSEM. In other words, a densely connected graph that represents the parity check matrix takes more iterations to converge than a sparsely connected graph.
Low-density parity check (LDPC) codes are very popular among error correction codes because of their high-performance capacity. Numerous investigations have been carried out to analyze the performance and simplify the implementation of LDPC codes. Relatively slow convergence of iterative decoding algorithm affects the performance of LDPC codes. Faster convergence can be achieved by reducing the number of iterations during the decoding process. In this thesis, a new approach for faster convergence is suggested by choosing a systematic parity check matrix that yields lowest Second Smallest Eigenvalue Modulus (SSEM) of its corresponding Laplacian matrix. MATLAB simulations are used to study the impact of eigenvalues on the number of iterations of the LDPC decoder. It is found that for a given (n, k) LDPC code, a parity check matrix with lowest SSEM converges quickly as compared to the parity check matrix with high SSEM. In other words, a densely connected graph that represents the parity check matrix takes more iterations to converge than a sparsely connected graph.
The new developments in coding theory research have revolutionized the application of coding to practical systems. Low-Density Parity Check (LDPC) codes form a class of Shannon limit approaching codes opted for digital communication systems that require high reliability. This thesis investigates the underlying relationship between the spectral properties of the parity check matrix and LDPC decoding convergence. The bit error rate of an LDPC code is plotted for the parity check matrix that has different Second Smallest Eigenvalue Modulus (SSEM) of its corresponding Laplacian matrix. It is found that for a given (n,k) LDPC code, large SSEM has better error floor performance than low SSEM. The value of SSEM decreases as the sparseness in a parity-check matrix is increased. It was also found from the simulation that long LDPC codes have better error floor performance than short codes. This thesis outlines an approach to analyze LDPC decoding based on the eigenvalue analysis of the corresponding parity check matrix.
Low Density Parity Check (LDPC) codes are considered to be one of the best classes of error-correcting codes. This thesis deals with two major issues in LDPC codes: decoder design to enhance error correction performance and efficient decoder implementation. Five techniques have been introduced in this thesis. First, an efficient platform for LDPC code design and performance evaluation is developed. This platform implements parallel simulation algorithms to efficiently evaluate the performance of the proposed algorithms for LDPC decoders and code design. Second, an innovative technique is introduced to improve the performance of LDPC decoding in the error-floor region. Special structures in the code graph, called trapping sets, are considered to be the major source of decoding errors in the error-floor region. The proposed technique is based on eliminating the negative effect of trapping sets during LDPC decoding. As a third contribution, a novel approach to improve the decoder performance and/or throughput is introduced. This approach is based on utilizing LDPC decoder idle times by introducing two queues: one at the decoder input and the other at the decoder output. This architecture enables the decoder to run extra iterations beyond the conventional maximum allowable iterations. The fourth proposed technique reduces the bit error rate of LDPC decoders. This technique is based on tracking the number of failed parity check equations in the intermediate decoding iterations, rather than only relying on the final decoder output (after reaching the maximum number of iterations). The last proposed technique deals with the construction of interconnect efficient fully-parallel LDPC codes with high error correction performance. Fully-parallel implementation is very hard due to the complexity of processing elements interconnections. The proposed technique is based on constructing LDPC codes with less complex interconnections and with low impact on the error correction performance. This goal is achieved by putting a constraint on the maximum connection length between any two processing elements.
Abstract: In this paper, a fast-convergence algorithm is proposed for the decoding of low-density parity-check (LDPC) codes. By putting more weight on the message update from check node to variable node in current iteration, the proposed method speeds up the decoding significantly. Simulation results show that compared with the standard layered min-sum decoding algorithm, the proposed scheme may reduce about 1/6 iteration numbers for LDPC codes used in DVB-S2, with hardware complexity overhead less than 2%. Key–Words: LDPC code, fast convergence decoding algorithm, layered decoding, min-sum algorithm, hardware implementation 1
Recent advances in coding theory have uncovered the previously forgotten power of Low-Density Parity-Check (LDPC) codes. Their popularity can be related to their relatively simple iterative decoders and their potential to achieve high performance close to shannon limit. These make them an attractive candidate for error correcting application in communication systems. In this thesis, we focus our research on the iterative decoding algorithms for Low-Density Parity-Check codes and present an improved decoding algorithm. First, the graph structure of LDPC codes is studied and a graph-based search algorithm to find the shortest closed walk and shortest cycle for each node of the graph is proposed. Then, the Deterministic schedule is applied on nodes of the graph with the objective of preserving the optimality of the algorithms. Finally, Hybrid Switch-Type technique is applied on the improved algorithms to provide a desirable complexity/performance trade-off. Hybrid Technique and Deterministic schedule are combined for decoding regular and irregular LDPC codes. The performance and complexity of the decoder is studied for Sum-Product and Gallager A algorithms. The result is a flexible decoder for any available LDPC code and any combination of decoding algorithms based on the communication systems need. In this technique, we benefit the high performance of soft-decision algorithms and low complexity of hard-decision algorithms by changing the decoding rule after a few iterations. Hence, a desirable performance can be obtained with less average number of soft iterations. Moreover, all the nodes do not update messages in each iteration. As a result, the total number of computations is reduced considerably
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.