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 Transactions on Communications

Kikuchi approximation method for joint decoding of LDPC codes and partial-response channels

Payam Pakzad, Venkat Anantharam

Published Jul 1, 2006• 26 citations
Publisher

Abstract

In this letter, we apply the Kikuchi approximation method to the problem of joint decoding of a low-density parity-check code and a partial-response channel. The Kikuchi method is, in general, more powerful than the conventional loopy belief propagation (BP) algorithm, and can produce better approximations to an underlying inference problem. We will first review the Kikuchi approximation method and the generalized BP algorithm, which is an iterative message-passing algorithm based on this method. We will then report simulation results which show that the Kikuchi method outperforms the best conventional iterative method

DOI
10.1109/tcomm.2006.877944

Related papers

Check-Belief Propagation Decoding of LDPC Codes

Wu Guan, Liping Liang

Variant belief propagation (BP) algorithms are applied to low-density parity-check (LDPC) codes. However, conventional decoders suffer from a large resource consumption due to gathering messages from all the neighbour variable-nodes and/or check-nodes through cumulative calculations. In this paper, a check-belief propagation (CBP) decoding algorithm is proposed. Check-belief is used as the probability that the corresponding parity-check is satisfied. All check-beliefs are iteratively enlarged in a sequential recursive order, and successful decoding will be achieved after the check-beliefs are all big enough. Compared to previous algorithms employing a large number of cumulative calculations to gather all the neighbour messages, CBP decoding can renew each check-belief by propagating it from one check-node to another through only one variable-node, resulting in a low complexity decoding with no cumulative calculations. The simulation results and analyses show that the CBP algorithm provides little error-rate performance loss in contrast with the previous BP algorithms, but consumes much fewer calculations and memories than them. It earns a big benefit in terms of complexity.

arXiv:2305.05286•IEEE Transactions on Communications•Aug 24, 2023•16 citations

Iterative decoding beyond belief propagation

Shiva Kumar Planjery, Shashi Kiran Chilappagari, Bane V. Vasic +2 more

At the heart of modern coding theory lies the fact that low-density parity-check (LDPC) codes can be efficiently decoded by belief propagation (BP). The BP is an inference algorithm which operates on a graphical model of a code, and lends itself to low-complexity and high-speed implementations, making it the algorithm of choice in many applications. It has unprecedentedly good error rate performance, so good that when decoded by the BP, LDPC codes approach theoretical limits of channel capacity. However, this capacity approaching property holds only in the asymptotic limit of code length, while codes of practical lengths suffer abrupt performance degradation in the low noise regime known as the error floor phenomenon. Our study of error floor has led to an interesting and surprising finding that it is possible to design iterative decoders which are much simpler yet better than belief propagation! These decoders do not propagate beliefs but a rather different kind of messages that reflect the local structure of the code graph. This has opened a plethora of exciting theoretical problems and applications. This paper introduces this new paradigm.

Information Theory and Applications Workshop (ITA)•Jan 1, 2010•18 citations

An Improved Decoding Algorithm for Finite-Geometry LDPC Codes

Yin-bing BIAN, Yuanqing Wang, Jie Wang

In this letter, we propose a new modification to the belief propagation (BP) decoding algorithm for Finite-Geometry low-density parity-check (LDPC) codes. The modification is based on introducing into the iterative process, which can break the oscillations of bit log-likelihood ratio (LLR) values. Simulations show that, with a given maximum iteration, the feedback BP (FBP) algorithm can achieve better performance than the conventional belief propagation algorithm.

IEICE Transactions on Communications•Apr 1, 2007•1 citation

A differential binary message-passing LDPC decoder

Nastaran Mobini, A.H. Banihashemi, Saied Hemati

In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finitegeometry LDPC codes, the proposed algorithm can perform as close as about 1 dB and 0.5 dB to belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.

IEEE Transactions on Communications•Sep 1, 2009•31 citations

A Differential Binary Message-Passing LDPC Decoder

Nastaran Mobini, Amir H. Banihashemi, Saied Hemati

In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finite-geometry LDPC codes, the proposed algorithm can achieve performance as close as 1.3 dB and 0.7 dB to that of belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.

Globecom•Nov 1, 2007•16 citations

Decoding with belief propagation

Marc Mézard, Andrea Montanari A

Abstract This chapter revisits the problem of decoding low density parity check (LDPC) codes. The maximum a posteriori probability (MAP) decoding of a bit is described as a statistical inference problem, and belief propagation is applied to its solution. The corresponding message passing procedure is analyzed in details, and the threshold noise level below which this ‘iterative decoding’ achieves perfect decoding is derived. The chapter ends with a general discussion of the relation between message passing and optimal (exact symbol MAP) decoding.

•Jan 22, 2009•0 citations
In this letter, we apply the Kikuchi approximation method to the problem of joint decoding of a low-density parity-check code and a partial-response channel. The Kikuchi method is, in general, more powerful than the conventional loopy belief propagation (BP) algorithm, and can produce better approximations to an underlying inference problem. We will first review the Kikuchi approximation method and the generalized BP algorithm, which is an iterative message-passing algorithm based on this method. We will then report simulation results which show that the Kikuchi method outperforms the best conventional iterative method
Variant belief propagation (BP) algorithms are applied to low-density parity-check (LDPC) codes. However, conventional decoders suffer from a large resource consumption due to gathering messages from all the neighbour variable-nodes and/or check-nodes through cumulative calculations. In this paper, a check-belief propagation (CBP) decoding algorithm is proposed. Check-belief is used as the probability that the corresponding parity-check is satisfied. All check-beliefs are iteratively enlarged in a sequential recursive order, and successful decoding will be achieved after the check-beliefs are all big enough. Compared to previous algorithms employing a large number of cumulative calculations to gather all the neighbour messages, CBP decoding can renew each check-belief by propagating it from one check-node to another through only one variable-node, resulting in a low complexity decoding with no cumulative calculations. The simulation results and analyses show that the CBP algorithm provides little error-rate performance loss in contrast with the previous BP algorithms, but consumes much fewer calculations and memories than them. It earns a big benefit in terms of complexity.
At the heart of modern coding theory lies the fact that low-density parity-check (LDPC) codes can be efficiently decoded by belief propagation (BP). The BP is an inference algorithm which operates on a graphical model of a code, and lends itself to low-complexity and high-speed implementations, making it the algorithm of choice in many applications. It has unprecedentedly good error rate performance, so good that when decoded by the BP, LDPC codes approach theoretical limits of channel capacity. However, this capacity approaching property holds only in the asymptotic limit of code length, while codes of practical lengths suffer abrupt performance degradation in the low noise regime known as the error floor phenomenon. Our study of error floor has led to an interesting and surprising finding that it is possible to design iterative decoders which are much simpler yet better than belief propagation! These decoders do not propagate beliefs but a rather different kind of messages that reflect the local structure of the code graph. This has opened a plethora of exciting theoretical problems and applications. This paper introduces this new paradigm.
In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finitegeometry LDPC codes, the proposed algorithm can perform as close as about 1 dB and 0.5 dB to belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.
In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finite-geometry LDPC codes, the proposed algorithm can achieve performance as close as 1.3 dB and 0.7 dB to that of belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.
Abstract This chapter revisits the problem of decoding low density parity check (LDPC) codes. The maximum a posteriori probability (MAP) decoding of a bit is described as a statistical inference problem, and belief propagation is applied to its solution. The corresponding message passing procedure is analyzed in details, and the threshold noise level below which this ‘iterative decoding’ achieves perfect decoding is derived. The chapter ends with a general discussion of the relation between message passing and optimal (exact symbol MAP) decoding.