While several implementations of LDPC codes decoders are available, the effects of fixed-point quantisation are still somewhat obscure. This paper aims at defining a systematic and general methodology to attack the LDPC decoding problem under finite–precision arithmetic. Statistical analysis is completed with Monte Carlo simulations to deploy the basics of the quantisation problem; the key aspect of this work is the independent study of channel reliability and extrinsic messages. As a case example, a short block, structured LDPC code is considered, and the results are shown. The extension to different codes confirms the validity of our method in relating design parameters and performance. This study is at the basis of the exploration of the trade-off between system performance and hardware complexity and can be easily extended to other applications.
While several implementations of LDPC codes decoders are available, the effects of fixed-point quantisation are still somewhat obscure. This paper aims at defining a systematic and general methodology to attack the LDPC decoding problem under finite–precision arithmetic. Statistical analysis is completed with Monte Carlo simulations to deploy the basics of the quantisation problem; the key aspect of this work is the independent study of channel reliability and extrinsic messages. As a case example, a short block, structured LDPC code is considered, and the results are shown. The extension to different codes confirms the validity of our method in relating design parameters and performance. This study is at the basis of the exploration of the trade-off between system performance and hardware complexity and can be easily extended to other applications.
Low-density parity-check (LDPC) codes are among the most powerful known error correcting codes and they have been shown to achieve performance very close to the Shannon bound. In practical hardware implementations of LDPC decoders, bit error rate performances are affected strongly by fixed-point representation of processed data and, although many papers have been published in recent years on the subject of LDPC codes, only a few of them report results on the effects of finite precision. In the paper two novel arithmetic approximations for the basic processing operations of the decoding algorithm are presented. The two proposed solutions are analysed in terms of bit error rate performance for different finite precison representations of both external and internal data; the estimated performance loss is comparable to that reported by previous works and limited to approximately 0.1 dB for cases of interests. However the proposed solutions support a reduced complexity formulation of the decoding algorithm, so enabling the implementation of flexible decoders that can be adapted to different LDPC codes, block sizes and code rates.
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.
Firstly, 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.
Secondly, 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.
Lastly, 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.
Much attention has been paid recently to the so-called layered decoding of LDPC codes, also known as turbo-decoding message passing (TDMP). The TDMP algorithm for decoding LDPC codes is known to possess some desirable features, such as fast convergence speed, reduced memory requirements and reduced implementation complexity in comparison with standard two-phase message passing algorithm. In this paper we analyze an important issue connected with hardware implementation of TDMP algorithm, namely the finite precision representation of messages influence on the decoding performance. Constrained dynamic range of the finite precision representation of messages entails overflow errors. We present an analysis revealing that in the subsequent decoding iterations, the subtraction of non-overflowed intrinsic message from overflowed extrinsic message is a source of errors that have substantial impact on the decoding results. The analysis is confirmed by simulation results showing significant performance loss. However this performance loss can be almost completely eliminated with a basic modifications in the messages computation algorithm. Effectiveness of the presented modifications is confirmed by simulation results obtained with hardware TDMP decoder implementation that has been developed.
This paper analyzes the performance of quantized min-sum decoding algorithms for irregular low-density parity-check (LDPC) codes. For regular LDPC codes, it is known that the normalized or offset min-sum decoding algorithm with quantization bits less than 6 bits achieves good performances over wide range of signal-to-noise ratios (SNR). However, finite precision effects in decoding irregular LDPC codes are different from that in decoding regular LDPC codes which is caused by the difference of convergence speeds between low degree nodes and high degree nodes. This paper proposes a novel method to improve the performance of the conventional normalized or offset min-sum decoding algorithm when it is approximated with finite precision for hardware implementations. The proposed method applies down-scaling factors to intrinsic information which has effects on increasing the reliability of extrinsic information at variable nodes and compensating the quantization errors caused by finite precision. Computer simulation results for irregular LDPC codes show that the proposed normalized and offset min-sum decoding algorithms achieve better performances at high SNR compared to the conventional normalized and offset min-sum algorithms under (6:2) quantization scheme.
An efficient method for finite-length low-density parity-check (LDPC) code analysis is proposed. This method is based on studying the channel variations when observed during a finite-length codeword. To this end, channel parameters are interpreted as random variables and their distributions are found. Assuming that a decoding failure is the result of an observed channel worse than the code's decoding threshold, the block error probability of finite-length LDPC codes is estimated. Using an extrinsic information transfer chart analysis, bit error probability is obtained from the block error probability. Our results suggest that by considering only the channel variations around its expected behavior and even ignoring the effects of cycles, one can closely predict the performance of LDPC codes of a few thousand bits or longer in the waterfall region.
An efficient method for analyzing the performance of finite-length low-density parity-check (LDPC) codes in the waterfall region, when transmission takes place on a memoryless binary-input output-symmetric channel is proposed. This method is based on studying the variations of the channel quality around its expected value when observed during the transmission of a finite-length codeword. We model these variations with a single parameter. This parameter is then viewed as a random variable and its probability distribution function is obtained. Assuming that a decoding failure is the result of an observed channel worse than the codeiquests decoding threshold, the block error probability of finite-length LDPC codes under different decoding algorithms is estimated. Using an extrinsic information transfer chart analysis, the bit error probability is obtained from the block error probability. Different parameters can be used for modeling the channel variations. In this work, two of such parameters are studied. Through examples, it is shown that this method can closely predict the performance of LDPC codes of a few thousand bits or longer in the waterfall region.