Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Magnetics Conference

On LDPC codes satisfying the (0, k) constraint

S. Babvey, S.W. McLaughlin

Published Jan 1, 2005• 0 citations
Publisher

Abstract

In this paper, we use the stochastic expectation-maximization method to illustrate how to come close to achieving the capacity of the noisy (0, k) constrained AWGN channels. We use the bit-flipping based constrained coding system proposed by Vasic to transmit (0, k) constrained LDPC codewords over an AWGN channel. In the original approach of Vasic, if the number of flipped bits is large, the message-passing decoder of LDPC codes fails to correct all the errors and the system is prone to an error floor even at high SNR values [Vasic, B et al., 2003]. We propose a flip decoder that exploits the information from the message-passing decoder to correct the flipped bits. We illustrate that the message-passing decoder and the flip decoder together correct both the channel and flip errors, and achieve rates close to the noisy (0, k) channel capacity.

DOI
10.1109/intmag.2005.1463928

Related papers

On the modification of bit-flipping decoder of LDPC-codes

S. S. Gurskiy, N. S. Mogilevskaya

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.

Advanced Engineering Research•Apr 4, 2021•0 citations

Bit-Flipping Post-Processing For Forced Convergence Decoding Of Ldpc Codes

Ernesto Zimmermann, Prakash Pattisapu, Gerhard Paul Fettweis

The recently proposed forced convergence technique allows for reducing the decoding complexity of Low-Density Parity-Check Codes (LDPCC) at only slight deterioration in performance. The basic idea is to restrict the message passing during LDPC decoding to the nodes that still significantly contribute to the decoding result. In this paper, we propose to add a bit-flipping post-processor to the forced convergence decoder in order to alleviate some problems of this novel technique, namely the error floors observed when aiming for high reduction in decoding complexity. Our results show that combining a hard decision bit-flipping with the forced convergence approach enables to almost retain original error correction performance while further reducing decoding complexity. 1.

European Signal Processing Conference (EUSIPCO)•Sep 8, 2005•13 citations

Linear-time encoding and decoding of low-density parity-check codes

Mikael Simberg

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.

•Jan 20, 2015•0 citations

Noise Thresholds for Discrete LDPC Decoding Mappings

Brian M. Kurkoski, Kazuhiko Yamaguchi, Kingo Kobayashi

For decoding low-density parity-check (LDPC) codes on discrete memoryless channels, a method to quantize messages and to find message-passing decoding functions for the variable and check nodes is developed. These are used to obtain noise thresholds by density evolution. The message-passing decoding alphabet is restricted to be discrete with a fixed maximum alphabet size. Discrete quantization is required to obtain this fixed alphabet size; a greedy algorithm which uses the mutual information between the code bit and message is presented. It is argued that using this message-passing decoding framework is more efficient for approaching channel capacity than simply quantizing the belief-propagation algorithm. This method is evaluated using regular LDPC codes on the binary symmetric channel. Using a maximum alphabet size of 16 (4 bits), noise thresholds close to those of belief propagation are obtained.

Globecom•Jan 1, 2008•49 citations

Error performance of LDPC decoder using bit flip algorithm

Ashwini Wanjari, Sandeep Kakde, Atish S. Khobragade

Low density parity check codes nowadays use in modern system due to their excellent performance. There are different message passing algorithm for LDPC codes to decode. In this paper, we have mention bit flip algorithm in brief and gave its bit error performance over AWGN channel via simulation result. For this communication, we use BPSK i.e. Binary phase shift keying digital modulation technique. This algorithm is based on binary decision message passing algorithm. This paper shows bit error performance of bit flip algorithm for different block lengths of LDPC code. The significance of showing bit error performance in this paper is that it shows how efficiently this algorithm works. We have also mention why BPSK modulation technique is more efficient than any other modulation technique.

International Conference on Communications and Signal Processing (ICCSP)•Apr 1, 2016•3 citations

Decoding LDPC Codes with Probabilistic Local Maximum Likelihood Bit Flipping

Rejoy Roy Mathews

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.

International Symposium on Information Theory and its Applications•Mar 9, 2020•1 citation
In this paper, we use the stochastic expectation-maximization method to illustrate how to come close to achieving the capacity of the noisy (0, k) constrained AWGN channels. We use the bit-flipping based constrained coding system proposed by Vasic to transmit (0, k) constrained LDPC codewords over an AWGN channel. In the original approach of Vasic, if the number of flipped bits is large, the message-passing decoder of LDPC codes fails to correct all the errors and the system is prone to an error floor even at high SNR values [Vasic, B et al., 2003]. We propose a flip decoder that exploits the information from the message-passing decoder to correct the flipped bits. We illustrate that the message-passing decoder and the flip decoder together correct both the channel and flip errors, and achieve rates close to the noisy (0, k) channel capacity.
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.
The recently proposed forced convergence technique allows for reducing the decoding complexity of Low-Density Parity-Check Codes (LDPCC) at only slight deterioration in performance. The basic idea is to restrict the message passing during LDPC decoding to the nodes that still significantly contribute to the decoding result. In this paper, we propose to add a bit-flipping post-processor to the forced convergence decoder in order to alleviate some problems of this novel technique, namely the error floors observed when aiming for high reduction in decoding complexity. Our results show that combining a hard decision bit-flipping with the forced convergence approach enables to almost retain original error correction performance while further reducing decoding complexity. 1.
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.
For decoding low-density parity-check (LDPC) codes on discrete memoryless channels, a method to quantize messages and to find message-passing decoding functions for the variable and check nodes is developed. These are used to obtain noise thresholds by density evolution. The message-passing decoding alphabet is restricted to be discrete with a fixed maximum alphabet size. Discrete quantization is required to obtain this fixed alphabet size; a greedy algorithm which uses the mutual information between the code bit and message is presented. It is argued that using this message-passing decoding framework is more efficient for approaching channel capacity than simply quantizing the belief-propagation algorithm. This method is evaluated using regular LDPC codes on the binary symmetric channel. Using a maximum alphabet size of 16 (4 bits), noise thresholds close to those of belief propagation are obtained.
Low density parity check codes nowadays use in modern system due to their excellent performance. There are different message passing algorithm for LDPC codes to decode. In this paper, we have mention bit flip algorithm in brief and gave its bit error performance over AWGN channel via simulation result. For this communication, we use BPSK i.e. Binary phase shift keying digital modulation technique. This algorithm is based on binary decision message passing algorithm. This paper shows bit error performance of bit flip algorithm for different block lengths of LDPC code. The significance of showing bit error performance in this paper is that it shows how efficiently this algorithm works. We have also mention why BPSK modulation technique is more efficient than any other modulation technique.
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.