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

International Conference on Communications

Construction of irregular LDPC codes with low error floors

Tao Tian, C. Jones, John D. Villasenor, Richard D. Wesel

Published Mar 30, 2004• 196 citations
Publisher

Abstract

This work explains the relationship between cycles, stopping sets, and dependent columns of the parity check matrix of low-density parity-check (LDPC) codes. Furthermore, it discusses how these structures limit LDPC code performance under belief propagation decoding. A new metric called extrinsic message degree (EMD) measures cycle connectivity in bipartite graph. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids cycles and increases stopping set size. This algorithm yields codes with error floors that are orders of magnitude below those of girth-conditional codes.

DOI
10.1109/icc.2003.1203996

Related papers

Selective Avoidance of Cycles in Irregular LDPC Code Construction

T. Tian, C.R. Jones, John D. Villasenor +1 more

This letter explains the effect of graph connectivity on error-floor performance of low-density parity-check (LDPC) codes under message-passing decoding. A new metric, called extrinsic message degree (EMD), measures cycle connectivity in bipartite graphs of LDPC codes. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids small cycle clusters that are isolated from the rest of the graph. This algorithm is different from conventional girth conditioning by emphasizing the connectivity as well as the length of cycles. The algorithm yields codes with error floors that are orders of magnitude below those of random codes with very small degradation in capacity-approaching capability.

IEEE Transactions on Communications•Aug 1, 2004•396 citations

Fast estimation of error floor effect for irregular low-density parity-check codes

Aleksei Ovinnikov, Vladimir V. Vityazev

The article summarizes a comparison of numerous irregular low-density parity-check codes using a set of metrics such as girth, number of short cycles in Tanner graph and extrinsic message degree (EMD). Based on this these metrics, we analyze how to decrease error floor for such codes with no negative effect to threshold.

International Siberian Conference on Control and Communications•May 1, 2015•0 citations

Studies on Lowering the Error Floors of Finite Length LDPC codes

Huanlin Li

Low-density parity-check (LDPC) codes can approach the Shannon limit performance closely, and are becoming one of the most promising channel codes in the Error Control Coding area.The performance of an LDPC code with given length is mainly affected by the sizes of some combinatorial characteristics of its corresponding bipartite graph and the distribution of variable degrees and check node degrees.With the help of the density evolution algorithm, randomly designed LDPC codes, with carefully chosen degree distribution pairs, have been shown to achieve better Shannon capacity performance than their regular counterparts when decoded using the iterative belief propagation (BP) decoding algorithm.However, regular LDPC codes outperform their irregular counterparts in term of their error floors.Therefore, construction of LDPC codes which have both attractive error rate performance and low error floor performance has become an attractive topic.Currently, optimization of variable node degree distribution and check node degree distribution for an LDPC code with given length, which could help the code to achieve good Shannon limit performance, has been extensively studied.In this dissertation, we demonstrate some approaches of improving the error floor performance for a given LDPC code with desired degree distribution pair.The contribution mainly includes three parts.In the first part, the relationship between cycles and unfavorable combinatorial

•Jan 1, 2011•0 citations

Construction of short-length LDPC codes with low error floor

X. Zheng, Francis C. M. Lau, Chi Kong Tse +1 more

It has been known that stopping sets and trapping sets are the main contributors to error floors exhibited by short-length low-density parity-check (LDPC) codes. In this work, a new metric called ldquoapproximate cycle set extrinsic message degree (ACSE)rdquo is defined to help removing stopping sets with small size and bad trapping sets. Based on the new metric, we propose a code-construction algorithm that produces LDPC codes with very low error floors. Finally, we compare the error rates between codes produced by the proposed algorithm and MacKay code.

IEEE Asia Pacific Conference on Circuits and Systems (APCCAS)•Nov 1, 2008•2 citations

On Lowering the Error Floor of Short-to-Medium Block Length Irregular Low Density Parity Check Codes

Umar-Faruk Abdu-Aguye

Gallager proposed and developed low density parity check (LDPC) codes in the early 1960s. LDPC codes were rediscovered in the early 1990s and shown to be capacity approaching over the additive white Gaussian noise (AWGN) channel. Subsequently, density evolution (DE) optimized symbol node degree distributions were used to significantly improve the decoding performance of short to medium length irregular LDPC codes. Currently, the short to medium length LDPC codes with the lowest error floor are DE optimized irregular LDPC codes constructed using progressive edge growth (PEG) algorithm modifications which are designed to increase the approximate cycle extrinsic message degrees (ACE) in the LDPC code graphs constructed. The aim of the present work is to find efficient means to improve on the error floor performance published for short to medium length irregular LDPC codes over AWGN channels in the literature. An efficient algorithm for determining the girth and ACE distributions in short to medium length LDPC code Tanner graphs has been proposed. A cyclic PEG (CPEG) algorithm which uses an edge connections sequence that results in LDPC codes with improved girth and ACE distributions is presented. LDPC codes with DE optimized/’good’ degree distributions which have larger minimum distances and stopping distances than previously published for LDPC codes of similar length and rate have been found. It is shown that increasing the minimum distance of LDPC codes lowers their error floor performance over AWGN channels; however, there are threshold minimum distances values above which there is no further lowering of the error floor performance. A minimum local girth (edge skipping) (MLG (ES)) PEG algorithm is presented; the algorithm controls the minimum local girth (global girth) connected in the Tanner graphs of LDPC codes constructed by forfeiting some edge connections. A technique for constructing optimal low correlated edge density (OED) LDPC codes based on modified DE optimized symbol node degree distributions and the MLG (ES) PEG algorithm modification is presented. OED rate-½ (n, k)=(512, 256) LDPC codes have been shown to have lower error floor over the AWGN channel than previously published for LDPC codes of similar length and rate. Similarly, consequent to an improved symbol node degree distribution, rate ½ (n, k)=(1024, 512) LDPC codes have been shown to have lower error floor over the AWGN channel than previously published for LDPC codes of similar length and rate. An improved BP/SPA (IBP/SPA) decoder, obtained by making two simple modifications to the standard BP/SPA decoder, has been shown to result in an unprecedented generalized improvement in the performance of short to medium length irregular LDPC codes under iterative message passing decoding. The superiority of the Slepian Wolf distributed source coding model over other distributed source coding models based on LDPC codes has been shown.

•Jan 1, 2018•0 citations

An efficient algorithm for finding dominant trapping sets of irregular LDPC codes

Mehdi Karimi, Amir H. Banihashemi

This paper presents an efficient algorithm for finding the dominant trapping sets of irregular low-density parity-check (LDPC) codes. The algorithm can be used to estimate the error floor of irregular LDPC codes or to be part of the apparatus to design irregular LDPC codes with low error floors. The algorithm is initiated with a set of short cycles, variable nodes with low degree, and cycles with low approximate cycle extrinsic message degree (ACE), as the input. The input structures are then expanded recursively to dominant trapping sets of increasing size. The algorithm is devised based on the careful inspection of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles, low-degree variable nodes and cycles with low ACE. In particular, the important role of degree-2 variable nodes in the structure of dominant trapping sets is discussed. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•15 citations
This work explains the relationship between cycles, stopping sets, and dependent columns of the parity check matrix of low-density parity-check (LDPC) codes. Furthermore, it discusses how these structures limit LDPC code performance under belief propagation decoding. A new metric called extrinsic message degree (EMD) measures cycle connectivity in bipartite graph. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids cycles and increases stopping set size. This algorithm yields codes with error floors that are orders of magnitude below those of girth-conditional codes.
This letter explains the effect of graph connectivity on error-floor performance of low-density parity-check (LDPC) codes under message-passing decoding. A new metric, called extrinsic message degree (EMD), measures cycle connectivity in bipartite graphs of LDPC codes. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids small cycle clusters that are isolated from the rest of the graph. This algorithm is different from conventional girth conditioning by emphasizing the connectivity as well as the length of cycles. The algorithm yields codes with error floors that are orders of magnitude below those of random codes with very small degradation in capacity-approaching capability.
Low-density parity-check (LDPC) codes can approach the Shannon limit performance closely, and are becoming one of the most promising channel codes in the Error Control Coding area.The performance of an LDPC code with given length is mainly affected by the sizes of some combinatorial characteristics of its corresponding bipartite graph and the distribution of variable degrees and check node degrees.With the help of the density evolution algorithm, randomly designed LDPC codes, with carefully chosen degree distribution pairs, have been shown to achieve better Shannon capacity performance than their regular counterparts when decoded using the iterative belief propagation (BP) decoding algorithm.However, regular LDPC codes outperform their irregular counterparts in term of their error floors.Therefore, construction of LDPC codes which have both attractive error rate performance and low error floor performance has become an attractive topic.Currently, optimization of variable node degree distribution and check node degree distribution for an LDPC code with given length, which could help the code to achieve good Shannon limit performance, has been extensively studied.In this dissertation, we demonstrate some approaches of improving the error floor performance for a given LDPC code with desired degree distribution pair.The contribution mainly includes three parts.In the first part, the relationship between cycles and unfavorable combinatorial
It has been known that stopping sets and trapping sets are the main contributors to error floors exhibited by short-length low-density parity-check (LDPC) codes. In this work, a new metric called ldquoapproximate cycle set extrinsic message degree (ACSE)rdquo is defined to help removing stopping sets with small size and bad trapping sets. Based on the new metric, we propose a code-construction algorithm that produces LDPC codes with very low error floors. Finally, we compare the error rates between codes produced by the proposed algorithm and MacKay code.
Gallager proposed and developed low density parity check (LDPC) codes in the early 1960s. LDPC codes were rediscovered in the early 1990s and shown to be capacity approaching over the additive white Gaussian noise (AWGN) channel. Subsequently, density evolution (DE) optimized symbol node degree distributions were used to significantly improve the decoding performance of short to medium length irregular LDPC codes. Currently, the short to medium length LDPC codes with the lowest error floor are DE optimized irregular LDPC codes constructed using progressive edge growth (PEG) algorithm modifications which are designed to increase the approximate cycle extrinsic message degrees (ACE) in the LDPC code graphs constructed. The aim of the present work is to find efficient means to improve on the error floor performance published for short to medium length irregular LDPC codes over AWGN channels in the literature. An efficient algorithm for determining the girth and ACE distributions in short to medium length LDPC code Tanner graphs has been proposed. A cyclic PEG (CPEG) algorithm which uses an edge connections sequence that results in LDPC codes with improved girth and ACE distributions is presented. LDPC codes with DE optimized/’good’ degree distributions which have larger minimum distances and stopping distances than previously published for LDPC codes of similar length and rate have been found. It is shown that increasing the minimum distance of LDPC codes lowers their error floor performance over AWGN channels; however, there are threshold minimum distances values above which there is no further lowering of the error floor performance. A minimum local girth (edge skipping) (MLG (ES)) PEG algorithm is presented; the algorithm controls the minimum local girth (global girth) connected in the Tanner graphs of LDPC codes constructed by forfeiting some edge connections. A technique for constructing optimal low correlated edge density (OED) LDPC codes based on modified DE optimized symbol node degree distributions and the MLG (ES) PEG algorithm modification is presented. OED rate-½ (n, k)=(512, 256) LDPC codes have been shown to have lower error floor over the AWGN channel than previously published for LDPC codes of similar length and rate. Similarly, consequent to an improved symbol node degree distribution, rate ½ (n, k)=(1024, 512) LDPC codes have been shown to have lower error floor over the AWGN channel than previously published for LDPC codes of similar length and rate. An improved BP/SPA (IBP/SPA) decoder, obtained by making two simple modifications to the standard BP/SPA decoder, has been shown to result in an unprecedented generalized improvement in the performance of short to medium length irregular LDPC codes under iterative message passing decoding. The superiority of the Slepian Wolf distributed source coding model over other distributed source coding models based on LDPC codes has been shown.
This paper presents an efficient algorithm for finding the dominant trapping sets of irregular low-density parity-check (LDPC) codes. The algorithm can be used to estimate the error floor of irregular LDPC codes or to be part of the apparatus to design irregular LDPC codes with low error floors. The algorithm is initiated with a set of short cycles, variable nodes with low degree, and cycles with low approximate cycle extrinsic message degree (ACE), as the input. The input structures are then expanded recursively to dominant trapping sets of increasing size. The algorithm is devised based on the careful inspection of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles, low-degree variable nodes and cycles with low ACE. In particular, the important role of degree-2 variable nodes in the structure of dominant trapping sets is discussed. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.