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

Mathematics in Science and Engineering/Mathematics in science and engineering

Error and Complexity in Error-Free, Parallel, and Probabilistic Computations

Vangipuram Lakshmikantham, S.K. Sen

Published Jan 1, 2005• 0 citations
Publisher
DOI
10.1016/s0076-5392(05)80057-8

Related papers

Classical and probabilistic computation

Joseph M. Landsberg

Graduate studies in mathematics•Jun 19, 2024•0 citations

A Probabilistic Parallel Bit-Flipping Decoder for Low-Density Parity-Check Codes

Khoa Le, Fakhreddine Ghaffari, Lounis Kessal +4 more

This paper presents a new bit flipping (BF) decoder, called the probabilistic parallel BF (PPBF) for low-density parity-check codes on the binary symmetric channel. In the PPBF, the flipping operation is performed in a probabilistic manner which is shown to significantly improve the error correction performance. The advantage of the PPBF also comes from the fact that no global computation is required during the decoding process and that all the computations can be executed in the local computing units and in parallel. The PPBF provides a considerable improvement of the operating frequency and complexity, compared to other known BF decoders, while obtaining a significant gain in error correction. An improved version of the PPBF, called non-syndrome PPBF is also introduced, in which the global syndrome check is moved out of the critical path and a new terminating mechanism is proposed. In order to show the superiority of the new decoders in terms of hardware efficiency and decoding throughput, the corresponding hardware architectures are presented in Section II. The application-specific integrated circuit synthesis results confirm that the operating frequency of the proposed decoders is significantly improved, compared to that of the BF decoders in the literature while requiring lower complexity to be efficiently implemented.

IEEE Transactions on Circuits and Systems I Regular Papers•Jul 4, 2018•19 citations

One-sided two-sided error in probabilistic computation

Harry Buhrman, Lance Fortnow

•Jan 1, 1999•3 citations

A novel high-throughput, low-complexity bit-flipping decoder for LDPC codes

Khoa Le, Fakhreddine Ghaffari, David Declercq +2 more

This paper presents a new high-throughput, low-complexity Bit Flipping (BF) decoder for Low-Density Parity-Check (LDPC) codes on the Binary Symmetric Channel (BSC), called Probabilistic Parallel Bit Flipping (PPBF). The advantage of PPBF comes from the fact that, no global operation is required during the decoding process and from that, all of the computations could be parallelized and localized at the computing units. Also in PPBF, the probabilistic feature in flipping the Variable Node (VN) is incorporated for all satisfaction level of its CN neighbors. This type of probabilistic incorporation makes PPBF more dynamic to correct some error patterns which are unsolvable by other BF decoders. PPBF offers a faster decoding process with an equivalent error correction performance to the Probabilistic Gradient Descent Bit Flipping (PGDBF) decoder, which is better than all so-far introduced BF decoders in BSC channel. A hardware implementation architecture of PPBF is also presented in this paper with detailed circuits for the probabilistic signal generator and processing units. The implementation of PPBF on FPGA confirms that, the PPBF complexity is much lower than that of the PGDBF and even lower than the one of the deterministic Gradient Descent Bit Flipping (GDBF) decoder. The good decoding performance along with the high throughput and low complexity lead PPBF decoder to become a brilliant candidate for the next generation of communication and storage standards.

International Conference on Advanced Technologies for Communications•Oct 1, 2017•15 citations

Error correction and fault-tolerant computation

Chiara Macchiavello, Guillermo Palma

Springer eBooks•Jun 1, 2001•2 citations

Efficient Hardware Implementation of Probabilistic Gradient Descent Bit Flipping

B Srisailam, T Nagaraju

This paper presents a new Bit Flipping (BF) decoder, called Probabilistic Parallel Bit Flipping (PPBF) for Low-Density Parity-Check (LDPC) codes on the Binary Symmetric Channel.In PPBF, the flipping operation is preceded with a probabilistic behavior which is shown to improve significantly the error correction performance.The advantage of PPBF comes from the fact that, no global computation is required during the decoding process and from that, all the computations can be executed in the local computing units and in-parallel.PPBF provides a considerable improvement of the decoding frequency and complexity, compared to other known BF decoders, while obtaining a significant gain in error correction.One improved version of PPBF, called non-syndrome PPBF (NS-PPBF) is also introduced, in which the global syndrome check is moved out of the critical path and a new terminating mechanism is proposed.In order to show the superiority of the new decoders in terms of hardware efficiency and decoding throughput, the corresponding hardware architectures are presented in the second part of the paper.The ASIC synthesis results confirm that, the decoding frequency of the proposed decoders is significantly improved, much higher than the BF decoders of literature while requiring lower complexity to be efficiently implemented.

International Journal of Innovative Technology and Research•Jan 11, 2020•0 citations
This paper presents a new bit flipping (BF) decoder, called the probabilistic parallel BF (PPBF) for low-density parity-check codes on the binary symmetric channel. In the PPBF, the flipping operation is performed in a probabilistic manner which is shown to significantly improve the error correction performance. The advantage of the PPBF also comes from the fact that no global computation is required during the decoding process and that all the computations can be executed in the local computing units and in parallel. The PPBF provides a considerable improvement of the operating frequency and complexity, compared to other known BF decoders, while obtaining a significant gain in error correction. An improved version of the PPBF, called non-syndrome PPBF is also introduced, in which the global syndrome check is moved out of the critical path and a new terminating mechanism is proposed. In order to show the superiority of the new decoders in terms of hardware efficiency and decoding throughput, the corresponding hardware architectures are presented in Section II. The application-specific integrated circuit synthesis results confirm that the operating frequency of the proposed decoders is significantly improved, compared to that of the BF decoders in the literature while requiring lower complexity to be efficiently implemented.
This paper presents a new high-throughput, low-complexity Bit Flipping (BF) decoder for Low-Density Parity-Check (LDPC) codes on the Binary Symmetric Channel (BSC), called Probabilistic Parallel Bit Flipping (PPBF). The advantage of PPBF comes from the fact that, no global operation is required during the decoding process and from that, all of the computations could be parallelized and localized at the computing units. Also in PPBF, the probabilistic feature in flipping the Variable Node (VN) is incorporated for all satisfaction level of its CN neighbors. This type of probabilistic incorporation makes PPBF more dynamic to correct some error patterns which are unsolvable by other BF decoders. PPBF offers a faster decoding process with an equivalent error correction performance to the Probabilistic Gradient Descent Bit Flipping (PGDBF) decoder, which is better than all so-far introduced BF decoders in BSC channel. A hardware implementation architecture of PPBF is also presented in this paper with detailed circuits for the probabilistic signal generator and processing units. The implementation of PPBF on FPGA confirms that, the PPBF complexity is much lower than that of the PGDBF and even lower than the one of the deterministic Gradient Descent Bit Flipping (GDBF) decoder. The good decoding performance along with the high throughput and low complexity lead PPBF decoder to become a brilliant candidate for the next generation of communication and storage standards.
This paper presents a new Bit Flipping (BF) decoder, called Probabilistic Parallel Bit Flipping (PPBF) for Low-Density Parity-Check (LDPC) codes on the Binary Symmetric Channel.In PPBF, the flipping operation is preceded with a probabilistic behavior which is shown to improve significantly the error correction performance.The advantage of PPBF comes from the fact that, no global computation is required during the decoding process and from that, all the computations can be executed in the local computing units and in-parallel.PPBF provides a considerable improvement of the decoding frequency and complexity, compared to other known BF decoders, while obtaining a significant gain in error correction.One improved version of PPBF, called non-syndrome PPBF (NS-PPBF) is also introduced, in which the global syndrome check is moved out of the critical path and a new terminating mechanism is proposed.In order to show the superiority of the new decoders in terms of hardware efficiency and decoding throughput, the corresponding hardware architectures are presented in the second part of the paper.The ASIC synthesis results confirm that, the decoding frequency of the proposed decoders is significantly improved, much higher than the BF decoders of literature while requiring lower complexity to be efficiently implemented.