Communication channels are inherently noisy making error correction coding a major topic of research for modern communication systems. Error correction coding is the addition of redundancy to information transmitted over communication channels to enable detection and recovery of erroneous information. Low-density parity-check (LDPC) codes are a class of error correcting codes that have been effective in maintaining reliability of information transmitted over communication channels. Multiple algorithms have been developed to benefit from the LDPC coding scheme to improve recovery of erroneous information. This work develops a matrix construction that stores the information error probability statistics for a communication channel. This combined with the error correcting capability of LDPC codes enabled the development of the Probabilistic Local Maximum Likelihood Bit Flipping (PLMLBF) algorithm, which is the focus of this research work.
Communication channels are inherently noisy making error correction coding a major topic of research for modern communication systems. Error correction coding is the addition of redundancy to information transmitted over communication channels to enable detection and recovery of erroneous information. Low-density parity-check (LDPC) codes are a class of error correcting codes that have been effective in maintaining reliability of information transmitted over communication channels. Multiple algorithms have been developed to benefit from the LDPC coding scheme to improve recovery of erroneous information. This work develops a matrix construction that stores the information error probability statistics for a communication channel. This combined with the error correcting capability of LDPC codes enabled the development of the Probabilistic Local Maximum Likelihood Bit Flipping (PLMLBF) algorithm, which is the focus of this research work.
Low-density parity-check (LDPC) codes had a renaissance when they were rediscovered in the 1990’s. Since then LDPC codes have been an important part of the field of error-correcting codes, and have been shown to be able to approach the Shannon capacity, the limit at which we can reliably transmit information over noisy channels. Following this, many modern communications standards have adopted LDPC codes. Error-correction is equally important in protecting data from corruption on a hard-drive as it is in deep-space communications. It is most commonly used for example for reliable wireless transmission of data to mobile devices. For practical purposes, both encoding and decoding need to be of low complexity to achieve high throughput and low power consumption. This thesis provides a literature review of the current state-of-the-art in encoding and decoding of LDPC codes. Message- passing decoders are still capable of achieving the best error-correcting performance, while more recently considered bit-flipping decoders are providing a low-complexity alternative, albeit with some loss in error-correcting performance. An implementation of a low-complexity stochastic bit-flipping decoder is also presented. It is implemented for Graphics Processing Units (GPUs) in a parallel fashion, providing a peak throughput of 1.2 Gb/s, which is significantly higher than previous decoder implementations on GPUs. The error-correcting performance of a range of decoders has also been tested, showing that the stochastic bit-flipping decoder provides relatively good error-correcting performance with low complexity. Finally, a brief comparison of encoding complexities for two code ensembles is also presented.
Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.
Introduction. In all types of digital communication, error control coding techniques are used. Many digital communication standards, such as Wi-Fi and 5G, use low density parity check (LDPC) codes. These codes are popular because they provide building encoders and decoders with low computational complexity. This work objective is to increase the error correcting capability of the well-known bit-flipping decoder (BF) of LDPC-codes. For this purpose, a modification of the decoder is built, which enables to dynamically control one of its main parameters whose choice affects significantly the quality of decoding. Materials and Methods. The well-known bit-flipping decoder of binary LDPC-codes is considered. This decoder has several parameters that are not rigidly bound with the code parameters. The dependence of the decoding quality on the selection of the output parameters of the bit-flipping decoder was investigated through simulation modeling. It is shown that the decoding results in this case are significantly affected by the input parameter of the decoder — threshold T. A modification of the BF-decoder of binary LDPC-codes has been developed, in which it is proposed to set the threshold dynamically during the execution of the algorithm depending on the error rate. A comparative analysis of the error- correcting capability of decoders is carried out by the simulation modeling method. Results. A lemma on the maximum value of the decoder threshold T is formulated and proved. Upper bounds for the number of operations are found for the original and modified decoders. A simulation model that implements a digital noise-immune communication channel has been built. In the model, the initial data is encoded with a given LDPC-code, then it is made noisy by additive uniformly distributed errors, and thereafter, it is decoded in turn by the bit-flipping algorithm with different threshold T parameters, as well as by a modified decoder. Based on the input and output data, the correction capacity of the decoders used is estimated. Experiments have shown that the error-correcting capability of the modified decoder in the range of the real error rate is higher than that of the original decoder, regardless of the selection of its parameters. Discussion and Conclusions. The lemma, proved in the paper, sets the upper bound on the threshold value in the original decoder, which simplifies its adjustment. The developed modification of the decoder has a better error- correcting capability compared to the original decoder. Nevertheless, the complexity of the modification is slightly increased compared to the original algorithm. It has been pointed out that the decoding quality of a modified decoder develops with a decrease in the number of cycles in the Tanner graph and an increase in the length of the code.
In the domain of wireless communication systems, Error Control Coding schemes are one of the widely relied upon or responsible methodology for securing the integrity and authenticity of the data transmission process. In the last decade, due to the advent of modern communication standards and their wide range of services, there has been a resurgence of interest and support in the research community towards the conception of efficient and versatile error control coding techniques. Recent developments in the wireless communication-based technologies have witnessed the pliable nature of low-density parity-check (LDPC) codes and their contributions which cannot be overstated. As of now, the decoding schemes based on LDPC codes have emerged as one of the most promising and efective coding scheme for addressing several key problems of reliable data communication. In this article, comprehensive overview on the on some well-known LDPC hard decision decoding algorithms is provided. In addition, simulations carried out on various LDPC decoding algorithms based on their performance is also presented. Finally, at the end of this review, the scope for future prospects are forecasted through discussions.
In this paper, we propose a new class of bit flipping algorithms for low-density parity-check (LDPC) codes over the binary symmetric channel (BSC). Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its “strength.” The introduction of this additional bit increases the guaranteed error correction capability by a factor of at least 2. An additional bit can also be employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis of the proposed algorithms is described. These algorithms outperform the Gallager A/B algorithm and the min-sum algorithm at much lower complexity. Concatenation of two-bit bit flipping algorithms show a potential to approach the performance of belief propagation (BP) decoding in the error floor region, also at lower complexity.
The error correction capability of bit-flipping decoding algorithm for low density parity-check (LDPC) codes is studied by introducing variable node adjacency (VNA) graphs which are derived from Tanner graphs of LDPC codes. For codes with column weight λ and girth g = 8, it can be shown that error patterns of weight less than or equal to λ - 1 can be corrected. This result implies that the bit-flipping algorithm could decode up to the random error-correcting capability over binary symmetric channel for girth 8 codes whose random error-correcting capability is equal to λ - 1.