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

Universal Journal of Electrical and Electronic Engineering

Performance Study and Synthesis of the New LDPC Error Correcting Code Using the Bit-Flipping Algorithm

Lagrini Lakbir, El Habti El Idrissi Anas, Moulay Brahim Sedra

Published Apr 1, 2020• 0 citations
Publisher

Abstract

The discovery in 1993 of the turbo codes Berrou C., A. and P. Glavieux Thitimajshima at the International Conférence of Communication Florida has revolutionized communication. This innovation made it possible to rediscovery the error correcting codes invented by Robert Gallager in 1963 and rediscovered by Mackay in 1995, currently called Low Density Parity Check (LDPC). This code is one of the error correction codes introduced by the transmission channel that have the fastest and most effective level of protection and correction of the information transmitted during the communication. This code has been almost generalized in communication standards such as satellites. The objective of our article is to minimize the number of iterations and in some cases completely remove the iteration produced by the LDPC code bit flipping algorithm. The result of this algorithm, if we take for example the LDPC code (n, k), the number of possible syndromes which we can find is 2k-1 and for each syndrome different from zero, we can do almost four iterations to correct the errors, which gives 4x(2k-1) iterations in totality. On the other hand, the proposed algorithm removes the iteration for k syndromes and reduces iterations for the rest of the cases from four to two iterations. This study of the new design gave more performance results and the results of the simulation below according to a hardware description language used in digital electronics using quartus software tools show the importance of this algorithm.

DOI
10.13189/ujeee.2020.070208

Related papers

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

On the Error Correction of Regular LDPC Codes Using the Flipping Algorithm

David Burshtein

The iterative bit flipping algorithm is applied to the standard regular low-density parity-check (LDPC) code ensemble. In the past, it was shown, for a typical code in the ensemble with left degree at least five and block length sufficiently large, that this algorithm can correct a linear (in the block length) number of worst case errors. In this paper, this result is extended to the case where the left degree is at least four. For the case where the left degree is larger than four, an improvement, compared to existing results, of several orders of magnitude is obtained on the fraction of worst case errors that can be corrected. It is also shown how the results can be further improved when random errors produced by the channel (as opposed to worst case errors) are considered.

IEEE Transactions on Information Theory•Jan 29, 2008•43 citations

On the error correction of regular LDPC codes using the flipping algorithm

David Burshtein

We apply the iterative bit flipping algorithm to the standard regular low-density parity-check (LDPC) code ensemble. In the past it was shown, for a typical code in the ensemble with left degree at least five and block length sufficiently large, that this algorithm can correct all error patterns with some linear (in the block length) number of errors. We extend this result to the case where the left degree is at least four. For the case where the left degree is larger than four, we obtain an improvement of several orders of magnitude compared to the existing results on the fraction of worst case errors that can be corrected. We also show how our results can be improved when we consider random errors (as opposed to worst case errors) produced by the channel.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•7 citations

Bit-Flipping LDPC Decoding Algorithm for Optical Fiber Communication Systems

Oulfa Laouar, Imed Amamra, Nadir Derouiche

The increasing popularity of optical communication systems emphasizes the need for effective errorcorrection solutions, including high-efficiency hardware decoder designs and codes with strong performance. Within optical communication networks, Low-Density Parity-Check (LDPC) codes utilizing sparse matrices and decoded through the Bit-Flipping (BF) algorithm, known for its hard iterative decoding approach are extensively utilized. These codes effectively balance decoding complexity with error-correction performance.This paper focuses on comparing the optical performance of LDPC codes with and without the BF decoding algorithm using two simulation software packages: MATLAB and OptiSystem 7.0. The comparison is conducted across different wavelengths and quality factors. Through this study, we evaluate the advantages of LDPC codes in terms of error-rate reduction and enhancing the reliability of optical transmission.

International Conference on Advances in Electrical and Communication Technologies (ICAECOT)•Oct 1, 2024•0 citations

New hard decision decoder of LDPC codes using single Bit Flipping algorithm

Soufian Addi, Ahlam Berkani, Ahmed Azouaoui +1 more

The Bit-Flipping (BF) algorithm is considered as a hard decoding method for LDPC codes. It is much simpler than the probabilistic methods like Sum Product Algorithm (SPA), and can be efficiently implemented by electronic circuits. In this paper, we propose a new Bit Flipping algorithm for Low-Density Parity-Check codes (LDPC) called Single Bit-Flipping (SBF). Compared to the Gallager Bit-Flipping algorithm, the proposed algorithm employs criteria of flipping single bit chosen carefully. This method eliminates the risk for flipping more than one bit at a time that can induce additional error bits and propagate the errors to the later iterations. We present some results obtained by applying this new method that provides a gain in performance in comparison to the standard Gallager Bit-Flipping with low complexity.

International Conference on Wireless Networks and Mobile Communications (WINCOM)•Nov 1, 2017•5 citations

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
The discovery in 1993 of the turbo codes Berrou C., A. and P. Glavieux Thitimajshima at the International Conférence of Communication Florida has revolutionized communication. This innovation made it possible to rediscovery the error correcting codes invented by Robert Gallager in 1963 and rediscovered by Mackay in 1995, currently called Low Density Parity Check (LDPC). This code is one of the error correction codes introduced by the transmission channel that have the fastest and most effective level of protection and correction of the information transmitted during the communication. This code has been almost generalized in communication standards such as satellites. The objective of our article is to minimize the number of iterations and in some cases completely remove the iteration produced by the LDPC code bit flipping algorithm. The result of this algorithm, if we take for example the LDPC code (n, k), the number of possible syndromes which we can find is 2k-1 and for each syndrome different from zero, we can do almost four iterations to correct the errors, which gives 4x(2k-1) iterations in totality. On the other hand, the proposed algorithm removes the iteration for k syndromes and reduces iterations for the rest of the cases from four to two iterations. This study of the new design gave more performance results and the results of the simulation below according to a hardware description language used in digital electronics using quartus software tools show the importance of this algorithm.
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.
The iterative bit flipping algorithm is applied to the standard regular low-density parity-check (LDPC) code ensemble. In the past, it was shown, for a typical code in the ensemble with left degree at least five and block length sufficiently large, that this algorithm can correct a linear (in the block length) number of worst case errors. In this paper, this result is extended to the case where the left degree is at least four. For the case where the left degree is larger than four, an improvement, compared to existing results, of several orders of magnitude is obtained on the fraction of worst case errors that can be corrected. It is also shown how the results can be further improved when random errors produced by the channel (as opposed to worst case errors) are considered.
We apply the iterative bit flipping algorithm to the standard regular low-density parity-check (LDPC) code ensemble. In the past it was shown, for a typical code in the ensemble with left degree at least five and block length sufficiently large, that this algorithm can correct all error patterns with some linear (in the block length) number of errors. We extend this result to the case where the left degree is at least four. For the case where the left degree is larger than four, we obtain an improvement of several orders of magnitude compared to the existing results on the fraction of worst case errors that can be corrected. We also show how our results can be improved when we consider random errors (as opposed to worst case errors) produced by the channel.
The increasing popularity of optical communication systems emphasizes the need for effective errorcorrection solutions, including high-efficiency hardware decoder designs and codes with strong performance. Within optical communication networks, Low-Density Parity-Check (LDPC) codes utilizing sparse matrices and decoded through the Bit-Flipping (BF) algorithm, known for its hard iterative decoding approach are extensively utilized. These codes effectively balance decoding complexity with error-correction performance.This paper focuses on comparing the optical performance of LDPC codes with and without the BF decoding algorithm using two simulation software packages: MATLAB and OptiSystem 7.0. The comparison is conducted across different wavelengths and quality factors. Through this study, we evaluate the advantages of LDPC codes in terms of error-rate reduction and enhancing the reliability of optical transmission.
The Bit-Flipping (BF) algorithm is considered as a hard decoding method for LDPC codes. It is much simpler than the probabilistic methods like Sum Product Algorithm (SPA), and can be efficiently implemented by electronic circuits. In this paper, we propose a new Bit Flipping algorithm for Low-Density Parity-Check codes (LDPC) called Single Bit-Flipping (SBF). Compared to the Gallager Bit-Flipping algorithm, the proposed algorithm employs criteria of flipping single bit chosen carefully. This method eliminates the risk for flipping more than one bit at a time that can induce additional error bits and propagate the errors to the later iterations. We present some results obtained by applying this new method that provides a gain in performance in comparison to the standard Gallager Bit-Flipping with low complexity.
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.