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.
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.
In this digital era, modern communication systems play an essential part in nearly every aspect of life, with examples ranging from mobile networks and satellite communications to Internet and data transfer. Unfortunately, all communication systems in a practical setting are noisy, which indicates that we can either improve the physical characteristics of the channel or find a possible systematical solution, i.e. error control coding. The history of error control coding dates back to 1948 when Claude Shannon published his celebrated work “A Mathematical Theory of Communication”, which built a framework for channel coding, source coding and information theory. For the first time, we saw evidence for the existence of channel codes, which enable reliable communication as long as the information rate of the code does not surpass the so-called channel capacity. Nevertheless, in the following 60 years none of the codes have been proven closely to approach the theoretical bound until the arrival of turbo codes and the renaissance of LDPC codes. As a strong contender of turbo codes, the advantages of LDPC codes include parallel implementation of decoding algorithms and, more crucially, graphical construction of codes. However, there are also some drawbacks to LDPC codes, e.g. significant performance degradation due to the presence of short cycles or very high decoding latency. In this thesis, we will focus on the practical realisation of finite-length LDPC codes and devise algorithms to tackle those issues. \n \nFirstly, rate-compatible (RC) LDPC codes with short/moderate block lengths are investigated on the basis of optimising the graphical structure of the tanner graph (TG), in order to achieve a variety of code rates (0.1 < R < 0.9) by only using a single encoder-decoder pair. As is widely recognised in the literature, the presence of short cycles considerably reduces the overall performance of LDPC codes which significantly limits their application in communication systems. To reduce the impact of short cycles effectively for different code rates, algorithms for counting short cycles and a graph-related metric called Extrinsic Message Degree (EMD) are applied with the development of the proposed puncturing and extension techniques. A complete set of simulations are carried out to demonstrate that the proposed RC designs can largely minimise the performance loss caused by puncturing or extension. \n \nSecondly, at the decoding end, we study novel decoding strategies which compensate for the negative effect of short cycles by reweighting part of the extrinsic messages exchanged between the nodes of a TG. The proposed reweighted belief propagation (BP) algorithms aim to implement efficient decoding, i.e. accurate signal reconstruction and low decoding latency, for LDPC codes via various design methods. A variable factor appearance probability belief propagation (VFAP-BP) algorithm is proposed along with an improved version called a locally-optimized reweighted (LOW)-BP algorithm, both of which can be employed to enhance decoding performance significantly for regular and irregular LDPC codes. More importantly, the optimisation of reweighting parameters only takes place in an offline stage so that no additional computational complexity is required during the real-time decoding process. \n \nLastly, two iterative detection and decoding (IDD) receivers are presented for multiple-input multiple-output (MIMO) systems operating in a spatial multiplexing configuration. QR decomposition (QRD)-type IDD receivers utilise the proposed multiple-feedback (MF)-QRD or variable-M (VM)-QRD detection algorithm with a standard BP decoding algorithm, while knowledge-aided (KA)-type receivers are equipped with a simple soft parallel interference cancellation (PIC) detector and the proposed reweighted BP decoders. In the uncoded scenario, the proposed MF-QRD and VM-QRD algorithms are shown to approach optimal performance, yet require a reduced computational complexity. In the LDPC-coded scenario, simulation results have illustrated that the proposed QRD-type IDD receivers can offer near-optimal performance after a small number of detection/decoding iterations and the proposed KA-type IDD receivers significantly outperform receivers using alternative decoding algorithms, while requiring similar decoding complexity.
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
It is well known that extremely long low-density parity-check (LDPC) codes perform exceptionally well for error correction applications, short-length codes are preferable in practical applications. However, short-length LDPC codes suffer from performance degradation owing to graph-based impairments such as short cycles, trapping sets and stopping sets and so on in the bipartite graph of the LDPC matrix. In particular, performance degradation at moderate to high Eb/N0 is caused by the oscillations in bit node a posteriori probabilities induced by short cycles and trapping sets in bipartite graphs. In this study, a computationally efficient algorithm is proposed to improve the performance of short-length LDPC codes at moderate to high Eb/N0. This algorithm makes use of the information generated by the belief propagation (BP) algorithm in previous iterations before a decoding failure occurs. Using this information, a reliability-based estimation is performed on each bit node to supplement the BP algorithm. The proposed algorithm gives an appreciable coding gain as compared with BP decoding for LDPC codes of a code rate equal to or less than 1/2 rate coding. The coding gains are modest to significant in the case of optimised (for bipartite graph conditioning) regular LDPC codes, whereas the coding gains are huge in the case of unoptimised codes. Hence, this algorithm is useful for relaxing some stringent constraints on the graphical structure of the LDPC code and for developing hardware-friendly designs.
The best known practical algorithm for the decoding of low-density parity-check (LDPC) codes is the iterative sum-product or belief propagation algorithm, operating on a Tanner graph (TG) of the code. Conventionally, in each iteration, all the symbol nodes and subsequently all the check nodes in the TG pass new messages to their neighbors (the so-called "flooding schedule"). We propose a new message-passing schedule, called "probabilistic schedule." Unlike flooding, the probabilistic schedule operates based on the structure of the TG, and probabilistically balances the frequency at which different symbol nodes update their outgoing messages in accordance with their girths. Our results show that, particularly for short block lengths, the new schedule offers a much better performance/complexity trade-off. For a particular example of a (1268,456) code, at no cost in complexity, the probabilistic schedule not only decreases both the bit and message error rates by an order of magnitude, but also reduces the number of undetected errors considerably. This work shows the importance of scheduling in the performance of iterative decoding algorithms and suggests that a schedule which matches the structure of the TG can substantially improve the performance/complexity trade-off in the decoding of short 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.
Low-density parity-check (LDPC) codes have been known for their outstanding error-correction capabilities. With low- complexity decoding algorithms and a near capacity performance, these codes are among the most promising forward error correction schemes. LDPC decoding algorithms are generally sub-optimal and their performance not only depends on the codes, but also on many other factors, such as the code representation. In particular, a given non- binary code can be associated with a number of different field or ring image codes. Additionally, each LDPC code can be described with many different Tanner graphs. Each of these different images and graphs can possibly lead to a different performance when used with iterative decoding algorithms. Consequently, in this dissertation we try to find better representations, i.e., graphs and images, for LDPC codes. We take the first step by analyzing LDPC codes over multiple-input single-output (MISO) channels. In an n_T by 1 MISO system with a modulation of alphabet size 2M̂, each group of n_T transmitted symbols are combined and produce one received symbol at the receiver. As a result, we consider the LDPC-coded MISO system as an LDPC code over a 2̂{M n_T}-ary alphabet. We introduce a modified Tanner graph to represent MISO-LDPC systems and merge the MISO symbol detection and binary LDPC decoding steps into a single message passing decoding algorithm. We present an efficient implementation for belief propagation decoding that significantly reduces the decoding complexity. With numerical simulations, we show that belief propagation decoding over modified graphs outperforms the conventional decoding algorithm for short length LDPC codes over unknown channels. Subsequently, we continue by studying images of non-binary LDPC codes. The high complexity of belief propagation decoding has been proven to be a detrimental factor for these codes. Thereby, we suggest employing lower complexity decoding algorithms over image codes instead. We introduce three classes of binary image codes for a given non-binary code, namely: basic, mixed, and extended binary image codes. We establish upper and lower bounds on the minimum distance of these binary image codes, and present two techniques to find binary image codes with better performance under belief propagation decoding algorithm. In particular, we present a greedy algorithm to find optimized binary image codes. We then proceed by investigation of the ring image codes. Specifically, we introduce matrix-ring-image codes for a given non-binary code. We derive a belief propagation decoding algorithm for these codes, and with numerical simulations, we demonstrate that the low-complexity belief propagation decoding of optimized image codes has a performance very close to the high complexity BP decoding of the original non-binary code. Finally, in a separate study, we investigate the performance of iterative decoders over binary erasure channels. In particular, we present a novel approach to evaluate the inherent unequal error protection properties of irregular LDPC codes over binary erasure channels. Exploiting the finite length scaling methodology, that has been used to study the average bit error rate of finite-length LDPC codes, we introduce a scaling approach to approximate the bit erasure rates in the waterfall region of variable nodes with different degrees. Comparing the bit erasure rates obtained from Monte Carlo simulation with the proposed scaling approximations, we demonstrate that the scaling approach provides a close approximation for a wide range of code lengths. In view of the complexity associated with the numerical evaluation of the scaling approximation, we also derive simpler upper and lower bounds and demonstrate through numerical simulations that these bounds are very close to the scaling approximation