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 Information Theory

Iterative List Decoding of Some LDPC Codes

JØrn Justesen, Tom Høholdt, Johann Hjaltason

Published Nov 1, 2007• 7 citations
Publisher

Abstract

We present an iterative list decoding algorithm for low-density parity-check (LDPC) codes. In particular we apply this decoder to a class of LDPC codes from finite geometries and show that the (73,45,10) projective geometry code can be maximum-likelihood (ML) decoded with low complexity. Moreover, the list decoding approach enables us to give a theoretical analysis of the performance. We also consider list bit-flipping (BF) decoding of longer LDPC codes.

DOI
10.1109/tit.2007.907485

Related papers

On Decoding of Low-Density Parity-Check Codes Over the Binary Erasure Channel

Hossein Pishro-Nik, Faramarz Fekri

This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length codes.

IEEE Transactions on Information Theory•Mar 1, 2004•147 citations

A List Decoding Algorithm for Short Low-Density Parity-Check Codes

Telex M. N. Ngatched, Fambirai Takawira

Abstract In this paper, a list decoding algorithm for lowdensity parity-check (LDPC) codes is presented. The algorithm uses a modification of the simple Gallager bit-flipping algorithm to generate a sequence of candidate codewords iteratively one at a time using a set of test error patterns based on the reliability information of the received symbols. It is particularly efficient for short block LDPC codes, both regular and irregular. Computer simulation results are used to compare the performance of the proposed algorithm with other known decoding algorithms for LDPC codes, with the result that the presented algorithm offers excellent performances. Performances comparable to those obtained with iterative decoding based on belief propagation can be achieved at a much smaller complexity. 1 I.

•Apr 3, 2006•0 citations

Low Density Parity Check Codes Based on Finite Geometries: A Rediscovery and More

Yu Kou, Shu Lin, M.P.C. Fossorier

Low density parity check (LDPC) codes with iterative decoding based on belief propagation achieve astonishing error performance close to Shannon limit. No algebraic or geometric method for constructing these codes has been reported and they are largely generated by computer search. As a result, encoding of long LDPC codes is in general very complex. This paper presents two classes of high rate LDPC codes whose constructions are based on finite Euclidean and projective geometries, respectively. These classes of codes a.re cyclic and have good constraint parameters and minimum distances. Cyclic structure adows the use of linear feedback shift registers for encoding. These finite geometry LDPC codes achieve very good error performance with either soft-decision iterative decoding based on belief propagation or Gallager's hard-decision bit flipping algorithm. These codes can be punctured or extended to obtain other good LDPC codes. A generalization of these codes is also presented.

•Oct 20, 1999•89 citations

An Efficient Decoding Algorithm for Finite-Geometry Low-Density Parity-Check Codes

Quan Zi-yi

Based on decoding performance,complexity and latency of finite-geometry low-density parity-check(FG-LDPC) codes,an efficient decoding algorithm is proposed.The new algorithm is a hybrid bit-flipping(BF)/majority-logic(MLG) decoding scheme.In BF decoding,an efficient method was explored to measure the reliability of the checks.At the completion of a small number of iterations,the output from BF decoding is decoded by MLG decoding.In the hybrid algorithm,there are no float operations.Simulation results show that the hybrid algorithm can provide 0.3?dB coding gain over weight bit-flipping(WBF) decoding.

Beijing Youdian Xueyuan xuebao•Jan 1, 2007•0 citations

Low-density parity-check codes based on finite geometries: a rediscovery and new results

Y. Kou, Shu Lin, M.P.C. Fossorier

This paper presents a geometric approach to the construction of low-density parity-check (LDPC) codes. Four classes of LDPC codes are constructed based on the lines and points of Euclidean and projective geometries over finite fields. Codes of these four classes have good minimum distances and their Tanner (1981) graphs have girth 6. Finite-geometry LDPC codes can be decoded in various ways, ranging from low to high decoding complexity and from reasonably good to very good performance. They perform very well with iterative decoding. Furthermore, they can be put in either cyclic or quasi-cyclic form. Consequently, their encoding can be achieved in linear time and implemented with simple feedback shift registers. This advantage is not shared by other LDPC codes in general and is important in practice. Finite-geometry LDPC codes can be extended and shortened in various ways to obtain other good LDPC codes. Several techniques of extension and shortening are presented. Long extended finite-geometry LDPC codes have been constructed and they achieve a performance only a few tenths of a decibel away from the Shannon theoretical limit with iterative decoding.

IEEE Transactions on Information Theory•Jan 1, 2001•1,303 citations

An improved decoding algorithm for finite-geometry LDPC codes

Telex M. N. Ngatched, Fambirai Takawira, Martin Bossert

In this letter, an improved bit-flipping decoding algorithm for high-rate finite-geometry low-density parity-check (FG-LDPC) codes is proposed. Both improvement in performance and reduction in decoding delay are observed by flipping multiple bits in each iteration. Our studies show that the proposed algorithm achieves an appealing tradeoff between performance and complexity for FG-LDPC codes.

IEEE Transactions on Communications•Feb 1, 2009•27 citations
We present an iterative list decoding algorithm for low-density parity-check (LDPC) codes. In particular we apply this decoder to a class of LDPC codes from finite geometries and show that the (73,45,10) projective geometry code can be maximum-likelihood (ML) decoded with low complexity. Moreover, the list decoding approach enables us to give a theoretical analysis of the performance. We also consider list bit-flipping (BF) decoding of longer LDPC codes.
This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length codes.
Abstract In this paper, a list decoding algorithm for lowdensity parity-check (LDPC) codes is presented. The algorithm uses a modification of the simple Gallager bit-flipping algorithm to generate a sequence of candidate codewords iteratively one at a time using a set of test error patterns based on the reliability information of the received symbols. It is particularly efficient for short block LDPC codes, both regular and irregular. Computer simulation results are used to compare the performance of the proposed algorithm with other known decoding algorithms for LDPC codes, with the result that the presented algorithm offers excellent performances. Performances comparable to those obtained with iterative decoding based on belief propagation can be achieved at a much smaller complexity. 1 I.
Low density parity check (LDPC) codes with iterative decoding based on belief propagation achieve astonishing error performance close to Shannon limit. No algebraic or geometric method for constructing these codes has been reported and they are largely generated by computer search. As a result, encoding of long LDPC codes is in general very complex. This paper presents two classes of high rate LDPC codes whose constructions are based on finite Euclidean and projective geometries, respectively. These classes of codes a.re cyclic and have good constraint parameters and minimum distances. Cyclic structure adows the use of linear feedback shift registers for encoding. These finite geometry LDPC codes achieve very good error performance with either soft-decision iterative decoding based on belief propagation or Gallager's hard-decision bit flipping algorithm. These codes can be punctured or extended to obtain other good LDPC codes. A generalization of these codes is also presented.
Based on decoding performance,complexity and latency of finite-geometry low-density parity-check(FG-LDPC) codes,an efficient decoding algorithm is proposed.The new algorithm is a hybrid bit-flipping(BF)/majority-logic(MLG) decoding scheme.In BF decoding,an efficient method was explored to measure the reliability of the checks.At the completion of a small number of iterations,the output from BF decoding is decoded by MLG decoding.In the hybrid algorithm,there are no float operations.Simulation results show that the hybrid algorithm can provide 0.3?dB coding gain over weight bit-flipping(WBF) decoding.
This paper presents a geometric approach to the construction of low-density parity-check (LDPC) codes. Four classes of LDPC codes are constructed based on the lines and points of Euclidean and projective geometries over finite fields. Codes of these four classes have good minimum distances and their Tanner (1981) graphs have girth 6. Finite-geometry LDPC codes can be decoded in various ways, ranging from low to high decoding complexity and from reasonably good to very good performance. They perform very well with iterative decoding. Furthermore, they can be put in either cyclic or quasi-cyclic form. Consequently, their encoding can be achieved in linear time and implemented with simple feedback shift registers. This advantage is not shared by other LDPC codes in general and is important in practice. Finite-geometry LDPC codes can be extended and shortened in various ways to obtain other good LDPC codes. Several techniques of extension and shortening are presented. Long extended finite-geometry LDPC codes have been constructed and they achieve a performance only a few tenths of a decibel away from the Shannon theoretical limit with iterative decoding.