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

arXiv:0901.2090 · IEEE International Symposium on Information Theory (ISIT)

Two-bit message passing decoders for LDPC codes over the binary symmetric channel

Lucile Sassatelli, Shashi Kiran Chilappagari, Bane Vasic, David Declercq

Published Jun 1, 2009• 18 citations
arXivHTMLPDF

Abstract

A class of two-bit message passing decoders for decoding column-weight-four LDPC codes over the binary symmetric channel is proposed. The thresholds for various decoders in this class are derived using density evolution. For a specific decoder, the sufficient conditions for correcting all error patterns with up to three errors are derived.

DOI
10.1109/isit.2009.5205790

Related papers

Low-Density Parity-Check Codes Which Can Correct Three Errors Under Iterative Decoding

Shashi Kiran Chilappagari, Anantha Raman Krishnan, Bane V. Vasic +1 more

In this paper, we give necessary and sufficient conditions for low-density parity-check (LDPC) codes with column-weight three to correct three errors when decoded using hard-decision message-passing decoding. Additionally, we give necessary and sufficient conditions for column-weight-four codes to correct three errors in four iterations of hard-decision message-passing decoding. We then give a construction technique which results in codes satisfying these conditions. We also provide numerical assessment of code performance via simulation results.

arXiv:0810.1105•Oct 7, 2008•0 citations

Properties of Optimum Binary Message-Passing Decoders

Masoud Ardakani, Frank R. Kschischang

We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them.

IEEE Transactions on Information Theory•Sep 26, 2005•14 citations

Finite alphabet iterative decoders for LDPC codes surpassing floating-point iterative decoders

Shiva Kumar Planjery, David Declercq, Ludovic Danjean +1 more

Introduced is a new type of message-passing (MP) decoders for low-density parity-check (LDPC) codes over the binary symmetric channel. Unlike traditional belief propagation (BP) based MP algorithms which propagate probabilities or log-likelihoods, the new MP decoders propagate messages requiring only a finite number of bits for their representation in such a way that good performance in the error floor region is ensured. Additionally, these messages are not quantised probabilities or log-likelihoods. As examples, MP decoders are provided that require only three bits for message representation, but surpass the floating-point BP (which requires a large number of bits for representation) in the error-floor region.

Electronics Letters•Aug 4, 2011•26 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•51 citations

Multilevel decoders surpassing belief propagation on the binary symmetric channel

Shiva Kumar Planjery, David Declercq, Shashi Kiran Chilappagari +1 more

In this paper, we propose a new class of quantized message-passing decoders for LDPC codes over the BSC. The messages take values (or levels) from a finite set. The update rules do not mimic belief propagation but instead are derived using the knowledge of trapping sets. We show that the update rules can be derived to correct certain error patterns that are uncorrectable by algorithms such as BP and min-sum. In some cases even with a small message set, these decoders can guarantee correction of a higher number of errors than BP and min-sum. We provide particularly good 3-bit decoders for 3-left-regular LDPC codes. They significantly outperform the BP and min-sum decoders, but more importantly, they achieve this at only a fraction of the complexity of the BP and min-sum decoders.

arXiv:1001.3421•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•34 citations

Analysis of LDPC code performance over binary symmetric channel

Yuxiang Li

Low-Density Parity-Check code (LDPC) is a kind of linear block error-correcting codes.Sum-product algorithm is an iterative decoding algorithms commonly used in LDPC code decoding.This paper studies into the LDPC code message passing iterative decoding algorithm under the binary symmetric channel (BSC) and simulates the bit error probability,then simulates the convergence of check nodes' and variable nodes' probability density in the iterative process using the method of density evolution.The result show that under a given channel threshold,LDPC code has a good correction performance.

Journal of Northeast Normal University•Jan 1, 2010•0 citations
A class of two-bit message passing decoders for decoding column-weight-four LDPC codes over the binary symmetric channel is proposed. The thresholds for various decoders in this class are derived using density evolution. For a specific decoder, the sufficient conditions for correcting all error patterns with up to three errors are derived.
In this paper, we give necessary and sufficient conditions for low-density parity-check (LDPC) codes with column-weight three to correct three errors when decoded using hard-decision message-passing decoding. Additionally, we give necessary and sufficient conditions for column-weight-four codes to correct three errors in four iterations of hard-decision message-passing decoding. We then give a construction technique which results in codes satisfying these conditions. We also provide numerical assessment of code performance via simulation results.
We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them.
Introduced is a new type of message-passing (MP) decoders for low-density parity-check (LDPC) codes over the binary symmetric channel. Unlike traditional belief propagation (BP) based MP algorithms which propagate probabilities or log-likelihoods, the new MP decoders propagate messages requiring only a finite number of bits for their representation in such a way that good performance in the error floor region is ensured. Additionally, these messages are not quantised probabilities or log-likelihoods. As examples, MP decoders are provided that require only three bits for message representation, but surpass the floating-point BP (which requires a large number of bits for representation) in the error-floor region.
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.
In this paper, we propose a new class of quantized message-passing decoders for LDPC codes over the BSC. The messages take values (or levels) from a finite set. The update rules do not mimic belief propagation but instead are derived using the knowledge of trapping sets. We show that the update rules can be derived to correct certain error patterns that are uncorrectable by algorithms such as BP and min-sum. In some cases even with a small message set, these decoders can guarantee correction of a higher number of errors than BP and min-sum. We provide particularly good 3-bit decoders for 3-left-regular LDPC codes. They significantly outperform the BP and min-sum decoders, but more importantly, they achieve this at only a fraction of the complexity of the BP and min-sum decoders.
Low-Density Parity-Check code (LDPC) is a kind of linear block error-correcting codes.Sum-product algorithm is an iterative decoding algorithms commonly used in LDPC code decoding.This paper studies into the LDPC code message passing iterative decoding algorithm under the binary symmetric channel (BSC) and simulates the bit error probability,then simulates the convergence of check nodes' and variable nodes' probability density in the iterative process using the method of density evolution.The result show that under a given channel threshold,LDPC code has a good correction performance.