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 Siberian Conference on Control and Communications

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

Aleksei Ovinnikov, Vladimir V. Vityazev

Published May 1, 2015• 0 citations
Publisher

Abstract

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.
DOI
10.1109/sibcon.2015.7147163

Related papers

Construction of irregular LDPC codes with low error floors

Tao Tian, C. Jones, John D. Villasenor +1 more

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.

International Conference on Communications•Mar 30, 2004•196 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

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

Increasing the local girth of irregular low-density parity-check codes based on degree-spectrum analysis

Francis C. M. Lau, Wai M. Tam, Chi Kong Tse

A low-density parity-check (LDPC) code can be described by a Tanner graph composed of symbol nodes and check nodes. Short cycles in the Tanner graph should be avoided because such cycles will degrade the performance of the decoder and hence increase the error rate. In most of the circumstances, cycles of length 4 can be totally eliminated in the Tanner graph when the LDPC code has been designed properly. Locally, for each variable node in the Tanner graph, the girth may take the value of 6 or 8, or even higher. In this study, the authors attempt to increase the local girths of a Tanner graph with an aim to improving the error performance of the code. The authors propose and analyse the ‘degree spectrum’ of the symbol nodes connecting to each of the check nodes. Based on the analysis, the authors can determine if the local girths can be further increased. The authors also propose simple ways to construct codes with higher local girths. Finally, the authors show the characteristics and the error performance of the codes constructed with the proposed methods.

IET Communications•Jul 22, 2011•2 citations

Lowering the error floor of short-to-medium length LDPC codes using optimal low-correlated-edge density (OED) PEG Tanner graphs

Umar-Faruk Abdu-Aguye, Marcel Ambroze, Martin Tomlinson

We propose a simple modification to the progressive edge-growth (PEG) algorithm in order to control the girth of low-density parity-check (LDPC) code Tanner graphs constructed. Using the modified algorithm, the edge densities in short irregular rate-% LDPC code graphs can be increased without increasing the correlation between edges in graphs by creating cycles of undesired length. Density evolution (DE) optimized symbol node degree distributions used for constructing short-to-medium length codes were further optimized (slightly altered) while maintaining the maximum edge correlation (minimum local girths) that exists in graphs constructed using the unaltered DE optimized distributions. As a result of improved degree sequences (and graph densities) which were derived, short-to-medium length LDPC codes with lower error floors than published for LDPC codes of identical length and rate were found. These slightly denser codes have lower error floor than codes constructed using DE optimized degree distributions in PEG algorithms modified for improved approximate cycle extrinsic message degrees (ACE). Simulation results show that, at a code length of 512, efficient irregular rate-% PEG codes have significantly lower error floors than a rate-% IEEE 802.16e (WiMAX) LDPC code of length 576.

International Conference on Software, Telecommunications and Computer Networks (SoftCOM)•Sep 1, 2016•1 citation

An efficient algorithm for irregular Low density Parity Check code with reduced computational complexity and error floor

Devichand P. Rathod, Raval N. Awale

Low-density Parity check codes (LDPC) are gaining interest for high data rate application in both terrestrial and spatial communications which requires low bit error rate. This paper proposes an algorithm through which the best parity check matrix is obtained for irregular low density parity check codes, which reduces the Bit Error Rate ,Frame Error Rate and computational complexity. Tanner graph also called a bipartite graph format in an Low Density Parity Check (LDPC) code design contains many short cycles; it will produce a computational complexity in a code design process and it degrades the code performance. To overcome this effect, we proposed an new algorithm which obtains a best final parity check matrix. Throughout the paper we will give the detailed description of an efficient algorithm proposed. The complexity is studied graphically and analytically. Using proposed algorithm, cycles of length four observed in corresponding matrix are removed. Each matrix is evaluated over a noisy Additive White Gaussian Noise (AWGN) channel. Bit Error rate and Frame error rate is calculated. The results are compared with randomly generated best parity check matrix. Simulation results shows that proposed method successfully overcomes the computational complexity and meets the near Shannon limit.

International Conference on Communication, Information & Computing Technology•Oct 1, 2012•3 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.
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 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.
A low-density parity-check (LDPC) code can be described by a Tanner graph composed of symbol nodes and check nodes. Short cycles in the Tanner graph should be avoided because such cycles will degrade the performance of the decoder and hence increase the error rate. In most of the circumstances, cycles of length 4 can be totally eliminated in the Tanner graph when the LDPC code has been designed properly. Locally, for each variable node in the Tanner graph, the girth may take the value of 6 or 8, or even higher. In this study, the authors attempt to increase the local girths of a Tanner graph with an aim to improving the error performance of the code. The authors propose and analyse the ‘degree spectrum’ of the symbol nodes connecting to each of the check nodes. Based on the analysis, the authors can determine if the local girths can be further increased. The authors also propose simple ways to construct codes with higher local girths. Finally, the authors show the characteristics and the error performance of the codes constructed with the proposed methods.
We propose a simple modification to the progressive edge-growth (PEG) algorithm in order to control the girth of low-density parity-check (LDPC) code Tanner graphs constructed. Using the modified algorithm, the edge densities in short irregular rate-% LDPC code graphs can be increased without increasing the correlation between edges in graphs by creating cycles of undesired length. Density evolution (DE) optimized symbol node degree distributions used for constructing short-to-medium length codes were further optimized (slightly altered) while maintaining the maximum edge correlation (minimum local girths) that exists in graphs constructed using the unaltered DE optimized distributions. As a result of improved degree sequences (and graph densities) which were derived, short-to-medium length LDPC codes with lower error floors than published for LDPC codes of identical length and rate were found. These slightly denser codes have lower error floor than codes constructed using DE optimized degree distributions in PEG algorithms modified for improved approximate cycle extrinsic message degrees (ACE). Simulation results show that, at a code length of 512, efficient irregular rate-% PEG codes have significantly lower error floors than a rate-% IEEE 802.16e (WiMAX) LDPC code of length 576.
Low-density Parity check codes (LDPC) are gaining interest for high data rate application in both terrestrial and spatial communications which requires low bit error rate. This paper proposes an algorithm through which the best parity check matrix is obtained for irregular low density parity check codes, which reduces the Bit Error Rate ,Frame Error Rate and computational complexity. Tanner graph also called a bipartite graph format in an Low Density Parity Check (LDPC) code design contains many short cycles; it will produce a computational complexity in a code design process and it degrades the code performance. To overcome this effect, we proposed an new algorithm which obtains a best final parity check matrix. Throughout the paper we will give the detailed description of an efficient algorithm proposed. The complexity is studied graphically and analytically. Using proposed algorithm, cycles of length four observed in corresponding matrix are removed. Each matrix is evaluated over a noisy Additive White Gaussian Noise (AWGN) channel. Bit Error rate and Frame error rate is calculated. The results are compared with randomly generated best parity check matrix. Simulation results shows that proposed method successfully overcomes the computational complexity and meets the near Shannon limit.