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:0810.1105

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

Shashi Kiran Chilappagari, Anantha Raman Krishnan, Bane V. Vasic, Michael W. Marcellin

Published Oct 7, 2008• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.0810.1105

Related papers

LDPC codes which can correct three errors under iterative decoding

Shashi Kiran Chilappagari, Anantha Raman Krishnan, Bane Vasic

In this paper, we provide necessary and sufficient conditions for a column-weight-three LDPC code to correct all patterns up to three errors when decoded using Gallager A algorithm. We then provide a construction technique which results in a code satisfying the above conditions. We also provide numerical assessment of code performance via simulation results.

arXiv:0801.1282•IEEE Information Theory Workshop (ITW)•May 1, 2008•15 citations

LDPC codes which can correct three errors under iterative decoding

Anantha Raman Krishnan, Bane V. Vasic

Abstract — In this paper, we provide necessary and sufficient conditions for a column-weight-three LDPC code to correct three errors when decoded using Gallager A algorithm. We then provide a construction technique which results in a code satisfying the above conditions. We also provide numerical assessment of code performance via simulation results. I.

•Jan 1, 2008•19 citations

Error-Correction Capability of Column-Weight-Three LDPC Codes

Shashi Kiran Chilappagari, Bane Vasic

In this paper, the error-correction capability of column-weight-three low-density parity-check (LDPC) codes when decoded using the Gallager A algorithm is investigated. It is proved that a necessary condition for a code to correct all error patterns with up to k ges 5 errors is to avoid cycles of length up to 2k in its Tanner graph. As a consequence of this result, it is shown that given any alpha > 0, exist N such that forall n > N, no code in the ensemble of column-weight-three codes can correct all alphan or fewer errors. The results are extended to the bit flipping algorithms.

arXiv:0807.3582•IEEE Transactions on Information Theory•Apr 22, 2009•38 citations

The effect of cycles on binary message-passing decoding of LDPC codes

Gottfried Lechner

We study the error-floor behavior of binary message-passing decoders for low-density parity-check (LDPC) codes. We find that the stability condition is independent of the quality of the channel messages (i.e. soft or hard decision). Furthermore, we identify a structure in the graph where the involved variable nodes cannot be corrected by the binary message-passing decoder. This leads to an error floor for regular LDPC codes with variable node degree smaller than four. An additional constraint on the degree distribution is derived which allows to avoid this structure, leading to optimized LDPC codes without error floors.

Australian Communications Theory Workshop•Feb 1, 2010•5 citations

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

Lucile Sassatelli, Shashi Kiran Chilappagari, Bane Vasic +1 more

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.

arXiv:0901.2090•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•18 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
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.
In this paper, the error-correction capability of column-weight-three low-density parity-check (LDPC) codes when decoded using the Gallager A algorithm is investigated. It is proved that a necessary condition for a code to correct all error patterns with up to k ges 5 errors is to avoid cycles of length up to 2k in its Tanner graph. As a consequence of this result, it is shown that given any alpha > 0, exist N such that forall n > N, no code in the ensemble of column-weight-three codes can correct all alphan or fewer errors. The results are extended to the bit flipping algorithms.
We study the error-floor behavior of binary message-passing decoders for low-density parity-check (LDPC) codes. We find that the stability condition is independent of the quality of the channel messages (i.e. soft or hard decision). Furthermore, we identify a structure in the graph where the involved variable nodes cannot be corrected by the binary message-passing decoder. This leads to an error floor for regular LDPC codes with variable node degree smaller than four. An additional constraint on the degree distribution is derived which allows to avoid this structure, leading to optimized LDPC codes without error floors.
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.