Low-density parity-check (LDPC) codes can be applied to many different types of communication systems such as video broadcasting and satellite communications. However, the performance of the codes in practice may deviate a lot from the theoretical limits, achievable only by codes with infinite length. In this thesis, we will conduct a detailed investigation on the performance of short-length LDPC codes over additive white Gaussian noise (AWGN) channels. First, we look into the rich dynamical behavior occurring at the LDPC decoders when the LDPC code has a finite length. We will report the various types of bifurcation phenomena as the signal-to-noise ratio (SNR) increases. By linearizing the iterative equations used for decoding the signals, we are able to evaluate the eigenvalues corresponding to the fixed points. Based on the eigenvalues, we can further characterize the properties of the fixed points. In addition, we make use of a simple feedback technique in an attempt to improving the convergence rate of the decoder at the waterfall (medium-SNR) region. Then, we attempt to "optimize" the distributions of the variable-node degrees and check-node degrees such that lower error rates can be produced. Although some "optimized" variable-node and check-node degree distributions have already been reported in the literature, they are found based on the assumption that the LDPC codes having an infinite length. Therefore, the error performance of a finite-length LDPC code obeying such degree distributions may not be "optimized" and there are possibilities that codes following other degree distributions may produce better performance in terms of block/bit error rates (BLERs/BERs). Since the LDPC decoders rely on passing messages iteratively between the set of variable nodes and the set of check nodes, decreasing the short average path length (APL) will no doubt accelerate the exchange of messages among the variable nodes, thereby reducing the number of iterations the decoder algorithm takes to converge. Inspired by the short average path length (APL) between nodes in complex networks with scale-free (SF) degree distributions, we make the first attempt in applying complex-network theories to communications engineering and build short-length LDPC codes with variable-node degrees following SF degree distributions. Not only have we evaluated the theoretical performance of our SF-LDPC codes, but also the simulated error rates. Furthermore, we compare our results with those of other well-known LDPC codes.
Low-density parity-check (LDPC) codes can be applied to many different types of communication systems such as video broadcasting and satellite communications. However, the performance of the codes in practice may deviate a lot from the theoretical limits, achievable only by codes with infinite length. In this thesis, we will conduct a detailed investigation on the performance of short-length LDPC codes over additive white Gaussian noise (AWGN) channels. First, we look into the rich dynamical behavior occurring at the LDPC decoders when the LDPC code has a finite length. We will report the various types of bifurcation phenomena as the signal-to-noise ratio (SNR) increases. By linearizing the iterative equations used for decoding the signals, we are able to evaluate the eigenvalues corresponding to the fixed points. Based on the eigenvalues, we can further characterize the properties of the fixed points. In addition, we make use of a simple feedback technique in an attempt to improving the convergence rate of the decoder at the waterfall (medium-SNR) region. Then, we attempt to "optimize" the distributions of the variable-node degrees and check-node degrees such that lower error rates can be produced. Although some "optimized" variable-node and check-node degree distributions have already been reported in the literature, they are found based on the assumption that the LDPC codes having an infinite length. Therefore, the error performance of a finite-length LDPC code obeying such degree distributions may not be "optimized" and there are possibilities that codes following other degree distributions may produce better performance in terms of block/bit error rates (BLERs/BERs). Since the LDPC decoders rely on passing messages iteratively between the set of variable nodes and the set of check nodes, decreasing the short average path length (APL) will no doubt accelerate the exchange of messages among the variable nodes, thereby reducing the number of iterations the decoder algorithm takes to converge. Inspired by the short average path length (APL) between nodes in complex networks with scale-free (SF) degree distributions, we make the first attempt in applying complex-network theories to communications engineering and build short-length LDPC codes with variable-node degrees following SF degree distributions. Not only have we evaluated the theoretical performance of our SF-LDPC codes, but also the simulated error rates. Furthermore, we compare our results with those of other well-known LDPC codes.
In this paper, we are concerned with the finite-length analysis of low-density parity-check (LDPC) codes when used over additive white Gaussian noise (AWGN) channels. We present the iterative decoding algorithm of LDPC codes, and we also discuss the encoding methods and the bipartite graph representation of LDPC codes ensemble. Finite-length LDPC code performances are investigated, and the influence of cycle is pointed out. Simulation results show that irregular LDPC codes with variable and check node degree distribution optimized for infinite-length codes are not optimal for finite-length LDPC codes, and the error patterns of both regular and irregular codes are investigated as an effort to improve the performance and design methodology of finite-length LDPC codes.
Study of complex networks has been conducted across many fields of science, including computer networks, biological networks and social networks. Characteristics of different types of complex networks such as random networks, regular-coupled networks, small-world networks and scale-free networks have been discovered by researchers. Application of such network properties to solve engineering problems, however, is still at the infancy stage. In this study, we make one of the first attempts in applying complex network theories to communications engineering. In particular, inspired by the shortest-average-path-length property of scale-free networks, we design short-length low-density-parity-check (LDPC) codes with an aim to shortening the average distance between any two variable nodes. We will also compare the error performance, both theoretically and by simulations, of the proposed codes with those of other well-known LDPC codes.
Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate performance.
Gallager proposed and developed low density parity check (LDPC) codes in the early 1960s. LDPC codes were rediscovered in the early 1990s and shown to be capacity approaching over the additive white Gaussian noise (AWGN) channel. Subsequently, density evolution (DE) optimized symbol node degree distributions were used to significantly improve the decoding performance of short to medium length irregular LDPC codes. Currently, the short to medium length LDPC codes with the lowest error floor are DE optimized irregular LDPC codes constructed using progressive edge growth (PEG) algorithm modifications which are designed to increase the approximate cycle extrinsic message degrees (ACE) in the LDPC code graphs constructed. The aim of the present work is to find efficient means to improve on the error floor performance published for short to medium length irregular LDPC codes over AWGN channels in the literature. An efficient algorithm for determining the girth and ACE distributions in short to medium length LDPC code Tanner graphs has been proposed. A cyclic PEG (CPEG) algorithm which uses an edge connections sequence that results in LDPC codes with improved girth and ACE distributions is presented. LDPC codes with DE optimized/’good’ degree distributions which have larger minimum distances and stopping distances than previously published for LDPC codes of similar length and rate have been found. It is shown that increasing the minimum distance of LDPC codes lowers their error floor performance over AWGN channels; however, there are threshold minimum distances values above which there is no further lowering of the error floor performance. A minimum local girth (edge skipping) (MLG (ES)) PEG algorithm is presented; the algorithm controls the minimum local girth (global girth) connected in the Tanner graphs of LDPC codes constructed by forfeiting some edge connections. A technique for constructing optimal low correlated edge density (OED) LDPC codes based on modified DE optimized symbol node degree distributions and the MLG (ES) PEG algorithm modification is presented. OED rate-½ (n, k)=(512, 256) LDPC codes have been shown to have lower error floor over the AWGN channel than previously published for LDPC codes of similar length and rate. Similarly, consequent to an improved symbol node degree distribution, rate ½ (n, k)=(1024, 512) LDPC codes have been shown to have lower error floor over the AWGN channel than previously published for LDPC codes of similar length and rate. An improved BP/SPA (IBP/SPA) decoder, obtained by making two simple modifications to the standard BP/SPA decoder, has been shown to result in an unprecedented generalized improvement in the performance of short to medium length irregular LDPC codes under iterative message passing decoding. The superiority of the Slepian Wolf distributed source coding model over other distributed source coding models based on LDPC codes has been shown.
Low-density parity-check (LDPC) codes can approach the Shannon limit performance closely, and are becoming one of the most promising channel codes in the Error Control Coding area.The performance of an LDPC code with given length is mainly affected by the sizes of some combinatorial characteristics of its corresponding bipartite graph and the distribution of variable degrees and check node degrees.With the help of the density evolution algorithm, randomly designed LDPC codes, with carefully chosen degree distribution pairs, have been shown to achieve better Shannon capacity performance than their regular counterparts when decoded using the iterative belief propagation (BP) decoding algorithm.However, regular LDPC codes outperform their irregular counterparts in term of their error floors.Therefore, construction of LDPC codes which have both attractive error rate performance and low error floor performance has become an attractive topic.Currently, optimization of variable node degree distribution and check node degree distribution for an LDPC code with given length, which could help the code to achieve good Shannon limit performance, has been extensively studied.In this dissertation, we demonstrate some approaches of improving the error floor performance for a given LDPC code with desired degree distribution pair.The contribution mainly includes three parts.In the first part, the relationship between cycles and unfavorable combinatorial
After the introduction of iterative coding, Low Density Parity Check (LDPC) codes have received a lot of attention due to their remarkable near Shannon-limit performance and practical decoder implementation. However, when employing an LDPC code for various applications, multiple issues do arise at the simulation, algorithm and implementation levels. The first issue is the performance evaluation of the iterative LDPC decoder in the very low Bit Error Rate (BER) regions. So far, no analytical tool has been developed to evaluate the performance of LDPC codes. Unfortunately standard Monte Carlo (MC) simulations cannot be used for performance estimation in these low BER regions due to prohibitive execution times. The second issue is the efficiency of the decoding algorithm. Due to the presence of short cycles in the bipartite graph, sum-product decoding algorithms lead to considerable performance loss for short block-length LDPC codes and produce error floors for longer codes. In addition, the iterative processing and estimation of soft probabilistic values with these algorithms result in very high computational complexity, which in turn impedes the adoption of LDPC codes for power constrained systems. Another prime objective is to design a high throughput decoder architecture which is capable of supporting multiple rates and variable code lengths within minimal area.
This work aims to address and provide solutions to the above problems. As a solution to the performance estimation problem of LDPC codes, a highly efficient and novel fast BER simulation technique is developed. At the algorithm level, a performance improvement and error floor avoidance method is introduced, and a computationally efficient algorithm is developed for the sum-product decoding of LDPC codes. And finally, at the architecture level, a high throughput multi-rate variable code length implementation is presented which, when implemented, efficiently minimizes device resources while alleviating the routing complexity of the decoder.