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

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

Anantha Raman Krishnan, Shashi Kiran Chilappagari

Published Dec 1, 2009• 1 citation
OpenAlex

Abstract

In this paper, we give necessary and sufficient conditions for low-density parity-check (LDPC) codes with column-weight four to correct three errors when decoded using 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.

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•1 citation

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

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•39 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

Low-density parity-check codes

Sarah J. Johnson

Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.

Cambridge University Press eBooks•Nov 19, 2009•6 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 four to correct three errors when decoded using 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, 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.
Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.
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.