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

Threshold Values and Convergence Properties of Majority-Based Algorithms for Decoding Regular Low-Density Parity-Check Codes

Pirouz Zarrinkhat, Amir H. Banihashemi

Published Dec 1, 2004• 39 citations
Publisher

Abstract

This work presents a detailed study of a family of binary message-passing decoding algorithms for low-density parity-check (LDPC) codes, referred to as "majority-based algorithms." Both Gallager's algorithm A (G/sub A/) and the standard majority decoding algorithm belong to this family. These algorithms, which are, in fact, the building blocks of Gallager's algorithm B (G/sub B/), work based on a generalized majority-decision rule and are particularly attractive for their remarkably simple implementation. We investigate the dynamics of these algorithms using density evolution and compute their (noise) threshold values for regular LDPC codes over the binary symmetric channel. For certain ensembles of codes and certain orders of majority-based algorithms, we show that the threshold value can be characterized as the smallest positive root of a polynomial, and thus can be determined analytically. We also study the convergence properties of majority-based algorithms, including their (convergence) speed. Our analysis shows that the stand-alone version of some of these algorithms provides significantly better performance and/or convergence speed compared with G/sub A/. In particular, it is shown that for channel parameters below threshold, while for G/sub A/ the error probability converges to zero exponentially with iteration number, this convergence for other majority-based algorithms is super-exponential.

DOI
10.1109/tcomm.2004.838738

Related papers

Density Evolution and Convergence Properties of Majority-based Algorithms for Decoding Low-density Parity-check (LDPC) Codes

Pirouz Zarrinkhat, Amir H. Banihashemi

This paper presents a detailed study of a family of binary messagepassing decoding algorithms for low-density parity-check (LDPC) codes, referred to as "majority-based decoding algorithms."Both Gallager's decoding algorithm A and standard majority decoding algorithm belong to this family.These algorithms, which work based on a generalized majority-decision rule, are particularly attractive for their remarkably simple implementation.We investigate the dynamics of these algorithms using density evolution and compute the threshold values for regular LDPC codes decoded by these algorithms.We also present analytical and graphical approaches to study and characterize the convergence properties of majority-based decoding algorithms, including their (convergence) speed.It appears that many of these algorithms enjoy very fast convergence.The analytical and graphical approaches used in this paper are quite general in principle, and with minor changes can be applied to many other algorithms.

•Oct 2, 2002•0 citations

Hybrid decoding of irregular LDPC codes

Pirouz Zarrinkhat, Amir H. Banihashemi

Time-invariant hybrid (HTI) decoding of irregular low-density parity-check (LDPC) codes is studied. Focusing on HTIalgorithms with majority-based (MB) binary message-passing constituents, we use density evolution and finite-length simulation to analyze the performance and the convergence properties of these algorithms. Tight upper bounds on the threshold of MB HTIalgorithms are derived, and it is proven that the asymptotic error probability for these algorithms tends to zero at least exponentially with the number of iterations. We devise optimal MB HTIalgorithms for irregular LDPC codes, and show that these algorithms outperform Gallager's algorithm A applied to optimized irregular LDPC codes. We also show that compared to switch-type algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different MB algorithms, MB HTIalgorithms are more robust, and can better cope with unknown channel conditions, and thus can be practically more attractive

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•4 citations

Hybrid Hard-Decision Iterative Decoding of Irregular Low-Density Parity-Check Codes

Pirouz Zarrinkhat, Amir H. Banihashemi

Time-invariant hybrid (HscrTI) decoding of irregular low-density parity-check (LDPC) codes is studied. Focusing on HscrTIalgorithms with majority-based (MB) binary message-passing constituents, we use density evolution (DE) and finite-length simulation to analyze the performance and the convergence properties of these algorithms over (memoryless) binary symmetric channels. To apply DE, we generalize degree distributions to have the irregularity of both the code and the decoding algorithm embedded in them. A tight upper bound on the threshold of MB HscrTIalgorithms is derived, and it is proven that the asymptotic error probability for these algorithms tends to zero, at least exponentially, with the number of iterations. We devise optimal MB HscrTIalgorithms for irregular LDPC codes, and show that these algorithms outperform Gallager's algorithm A applied to optimized irregular LDPC codes. We also show that compared to switch-type algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different MB algorithms, MB HscrTIalgorithms are more robust and can better cope with unknown channel conditions, and thus can be practically more attractive.

IEEE Transactions on Communications•Feb 1, 2007•6 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

Bounds on the performance of belief propagation decoding

David Burshtein, G. Miller

We consider Gallager's (1963) soft-decoding (belief propagation) algorithm for decoding low-density parity-check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as a certain robustness to the details of the channel noise. Our results apply both to regular and irregular LDPC codes.

IEEE Transactions on Information Theory•Jan 1, 2002•42 citations

Hybrid Hard-Decision Iterative Decoding of Regular Low-Density Parity-Check Codes

Pirouz Zarrinkhat, Amir H. Banihashemi

Hybrid decoding means to combine different iterative decoding algorithms with the aim of improving error performance or decoding complexity. In this work, we introduce "time-invariant" hybrid (H/sub TI/) algorithms, and using density evolution show that for regular low-density parity-check (LDPC) codes and binary message-passing algorithms, H/sub TI/ algorithms perform remarkably better than their constituent algorithms. We also show that compared to "switch-type" hybrid (H/sub ST/) algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different iterative decoding algorithms, H/sub TI/ algorithms are far less sensitive to channel conditions and thus can be practically more attractive.

IEEE Communications Letters•Apr 1, 2004•12 citations
This work presents a detailed study of a family of binary message-passing decoding algorithms for low-density parity-check (LDPC) codes, referred to as "majority-based algorithms." Both Gallager's algorithm A (G/sub A/) and the standard majority decoding algorithm belong to this family. These algorithms, which are, in fact, the building blocks of Gallager's algorithm B (G/sub B/), work based on a generalized majority-decision rule and are particularly attractive for their remarkably simple implementation. We investigate the dynamics of these algorithms using density evolution and compute their (noise) threshold values for regular LDPC codes over the binary symmetric channel. For certain ensembles of codes and certain orders of majority-based algorithms, we show that the threshold value can be characterized as the smallest positive root of a polynomial, and thus can be determined analytically. We also study the convergence properties of majority-based algorithms, including their (convergence) speed. Our analysis shows that the stand-alone version of some of these algorithms provides significantly better performance and/or convergence speed compared with G/sub A/. In particular, it is shown that for channel parameters below threshold, while for G/sub A/ the error probability converges to zero exponentially with iteration number, this convergence for other majority-based algorithms is super-exponential.
This paper presents a detailed study of a family of binary messagepassing decoding algorithms for low-density parity-check (LDPC) codes, referred to as "majority-based decoding algorithms."Both Gallager's decoding algorithm A and standard majority decoding algorithm belong to this family.These algorithms, which work based on a generalized majority-decision rule, are particularly attractive for their remarkably simple implementation.We investigate the dynamics of these algorithms using density evolution and compute the threshold values for regular LDPC codes decoded by these algorithms.We also present analytical and graphical approaches to study and characterize the convergence properties of majority-based decoding algorithms, including their (convergence) speed.It appears that many of these algorithms enjoy very fast convergence.The analytical and graphical approaches used in this paper are quite general in principle, and with minor changes can be applied to many other algorithms.
Time-invariant hybrid (HTI) decoding of irregular low-density parity-check (LDPC) codes is studied. Focusing on HTIalgorithms with majority-based (MB) binary message-passing constituents, we use density evolution and finite-length simulation to analyze the performance and the convergence properties of these algorithms. Tight upper bounds on the threshold of MB HTIalgorithms are derived, and it is proven that the asymptotic error probability for these algorithms tends to zero at least exponentially with the number of iterations. We devise optimal MB HTIalgorithms for irregular LDPC codes, and show that these algorithms outperform Gallager's algorithm A applied to optimized irregular LDPC codes. We also show that compared to switch-type algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different MB algorithms, MB HTIalgorithms are more robust, and can better cope with unknown channel conditions, and thus can be practically more attractive
Time-invariant hybrid (HscrTI) decoding of irregular low-density parity-check (LDPC) codes is studied. Focusing on HscrTIalgorithms with majority-based (MB) binary message-passing constituents, we use density evolution (DE) and finite-length simulation to analyze the performance and the convergence properties of these algorithms over (memoryless) binary symmetric channels. To apply DE, we generalize degree distributions to have the irregularity of both the code and the decoding algorithm embedded in them. A tight upper bound on the threshold of MB HscrTIalgorithms is derived, and it is proven that the asymptotic error probability for these algorithms tends to zero, at least exponentially, with the number of iterations. We devise optimal MB HscrTIalgorithms for irregular LDPC codes, and show that these algorithms outperform Gallager's algorithm A applied to optimized irregular LDPC codes. We also show that compared to switch-type algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different MB algorithms, MB HscrTIalgorithms are more robust and can better cope with unknown channel conditions, and thus can be practically more attractive.
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.
We consider Gallager's (1963) soft-decoding (belief propagation) algorithm for decoding low-density parity-check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as a certain robustness to the details of the channel noise. Our results apply both to regular and irregular LDPC codes.
Hybrid decoding means to combine different iterative decoding algorithms with the aim of improving error performance or decoding complexity. In this work, we introduce "time-invariant" hybrid (H/sub TI/) algorithms, and using density evolution show that for regular low-density parity-check (LDPC) codes and binary message-passing algorithms, H/sub TI/ algorithms perform remarkably better than their constituent algorithms. We also show that compared to "switch-type" hybrid (H/sub ST/) algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different iterative decoding algorithms, H/sub TI/ algorithms are far less sensitive to channel conditions and thus can be practically more attractive.