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 Signal Processing and Communication Systems

An efficient algorithm for determining the girth and ACE distributions in LDPC code Tanner graphs

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

Published Dec 1, 2016• 6 citations
Publisher

Abstract

We propose a simple and efficient algorithm for evaluating the girth and approximate cycle extrinsic message degree (ACE) of all short cycles through symbol nodes in short-to-medium length low-density parity-check (LDPC) code Tanner graphs. The algorithm uses single-edge tree-apex (SETA) subgraph expansions to find all the short cycles in a code graph in a direct manner, unlike existing algorithms which use message-passing algorithms or trellis representations of code graphs. The complexity of the algorithm, when applied to a parity-check matrix H of dimension m × n, is O(n m). Due to the fact that both girth and ACE are features of cycles, we adopt parameters similar to those used for girth descriptions for ACE descriptions. Accordingly, we define the `local ACE' at a symbol node or the `symbol node ACE', as the minimum ACE of the short cycles through the symbol node in the graph. This basic parameter enables the local ACE distribution, minimum and maximum local ACE, modal ACE, and the average ACE of an LDPC code graph to be determined using SETA subgraph expansions. The average ACE of an LDPC code graph is a concise single-valued measure of the overall connectivity of cycles in the graph. The proposed algorithm determines the local girth and ACE distributions in irregular short length LDPC codes in less time than existing algorithms. The algorithm is not intended for quasi-cyclic (QC) LDPC codes.

DOI
10.1109/icspcs.2016.7843313

Related papers

Joint Short-Cycle and ACE Statistics in LDPC Tanner Graphs via Fast Message Passing

Xiang Li, Xuan He

Short cycles in Tanner graphs strongly affect the structural quality and decoding performance of low-density parity-check (LDPC) codes. Besides cycle multiplicities, the approximate cycle extrinsic message degree (ACE) is also an important indicator for characterizing short-cycle structures. This paper proposes ACE-FMPA, a fast message-passing algorithm for jointly computing short-cycle and ACE statistics in LDPC Tanner graphs. Specifically, it jointly computes, for each cycle length 2l with l ∈ [g/2, g − 1], the cycle multiplicity η2l, the minimum ACE value ξ2l, and the multiplicity ψ2l of minimum-ACE cycles. The proposed algorithm only adds constant-size ACE-state maintenance to the baseline short-cycle counting process, and thus preserves the same asymptotic complexity order. Experimental results show that ACE-FMPA provides richer structural information with limited extra running time.

International Conference on Networks, Communications and Information Technology (CNCIT)•May 29, 2026•0 citations

Improved minimum weight, girth, and ACE distributions in ensembles of short block length irregular LDPC codes constructed using PEG and cyclic PEG (CPEG) algorithms

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

In this paper we introduce a novel progressive edge-growth (PEG) algorithm, the cyclic PEG (CPEG) algorithm. The CPEG algorithm uses an alternative edge establishment sequence to construct low-density parity-check (LDPC) codes. Irregular LDPC codes constructed using the CPEG algorithm have improved girth and approximate cycle extrinsic message degree (ACE) compared to existing PEG algorithms. We also analyze the minimum codeword weight, minimum stopping set weight, local girth, and local ACE distributions for codes in four very large ensembles of irregular LDPC codes. The code ensembles analyzed were constructed using standard PEG, ACE modified standard PEG, CPEG, and ACE modified CPEG algorithms. Modifications to improve the ACE in PEG LDPC codes, by Xiao and Banihashemi, were implemented in the ‘ACE modified’ versions of the PEG algorithms. The ACE modified standard PEG algorithm constructed the code ensemble with the highest minimum codeword weight and minimum stopping set weight distributions, and the ACE modified CPEG algorithm constructed the code ensemble with the highest local girth and ACE distributions. Short block length irregular LDPC codes with good degree distributions which have higher minimum weights than have been published for similar LDPC codes were found in the four code ensembles.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2016•4 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

On the equivalence of the ACE and the EMD of a cycle for the ACE spectrum constrained LDPC codes

Kuntal Deka, A. Rajesh, Prabin Kumar Bora

The Extrinsic Message Degree (EMD) of a cycle in the Tanner graph of a low density parity check (LDPC) code measures the connectivity of the cycle. As it is difficult to calculate the EMD, the Approximate EMD (ACE) is generally used. However, the ACE of a cycle is not always equal to its EMD. This paper presents some sufficient conditions for the equivalence of the ACE and the EMD of a cycle for the ACE spectrum constrained LDPC codes.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 1, 2014•6 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

Counting Short Cycles of Quasi Cyclic Protograph LDPC Codes

Mehdi Karimi, Amir H. Banihashemi

An efficient method for counting short cycles in the Tanner graphs of quasi cyclic (QC) protograph low-density parity-check (LDPC) codes is presented. The method is based on the relationship between the number of short cycles in the graph and the eigenvalues of the directed edge matrix of the graph. We demonstrate that for a QC protograph LDPC code, the complexity of computing such eigenvalues can be reduced significantly by representing the directed edge matrix as a block circulant matrix. Numerical results are presented to show the lower complexity of the proposed method compared to the existing algorithms for counting short cycles. These results also reveal that QC LDPC codes on average have a superior short cycle and girth distribution compared to similar randomly constructed codes.

IEEE Communications Letters•Feb 10, 2012•34 citations
We propose a simple and efficient algorithm for evaluating the girth and approximate cycle extrinsic message degree (ACE) of all short cycles through symbol nodes in short-to-medium length low-density parity-check (LDPC) code Tanner graphs. The algorithm uses single-edge tree-apex (SETA) subgraph expansions to find all the short cycles in a code graph in a direct manner, unlike existing algorithms which use message-passing algorithms or trellis representations of code graphs. The complexity of the algorithm, when applied to a parity-check matrix H of dimension m × n, is O(n m). Due to the fact that both girth and ACE are features of cycles, we adopt parameters similar to those used for girth descriptions for ACE descriptions. Accordingly, we define the local ACE' at a symbol node or the symbol node ACE', as the minimum ACE of the short cycles through the symbol node in the graph. This basic parameter enables the local ACE distribution, minimum and maximum local ACE, modal ACE, and the average ACE of an LDPC code graph to be determined using SETA subgraph expansions. The average ACE of an LDPC code graph is a concise single-valued measure of the overall connectivity of cycles in the graph. The proposed algorithm determines the local girth and ACE distributions in irregular short length LDPC codes in less time than existing algorithms. The algorithm is not intended for quasi-cyclic (QC) LDPC codes.
Short cycles in Tanner graphs strongly affect the structural quality and decoding performance of low-density parity-check (LDPC) codes. Besides cycle multiplicities, the approximate cycle extrinsic message degree (ACE) is also an important indicator for characterizing short-cycle structures. This paper proposes ACE-FMPA, a fast message-passing algorithm for jointly computing short-cycle and ACE statistics in LDPC Tanner graphs. Specifically, it jointly computes, for each cycle length 2l with l ∈ [g/2, g − 1], the cycle multiplicity η2l, the minimum ACE value ξ2l, and the multiplicity ψ2l of minimum-ACE cycles. The proposed algorithm only adds constant-size ACE-state maintenance to the baseline short-cycle counting process, and thus preserves the same asymptotic complexity order. Experimental results show that ACE-FMPA provides richer structural information with limited extra running time.
In this paper we introduce a novel progressive edge-growth (PEG) algorithm, the cyclic PEG (CPEG) algorithm. The CPEG algorithm uses an alternative edge establishment sequence to construct low-density parity-check (LDPC) codes. Irregular LDPC codes constructed using the CPEG algorithm have improved girth and approximate cycle extrinsic message degree (ACE) compared to existing PEG algorithms. We also analyze the minimum codeword weight, minimum stopping set weight, local girth, and local ACE distributions for codes in four very large ensembles of irregular LDPC codes. The code ensembles analyzed were constructed using standard PEG, ACE modified standard PEG, CPEG, and ACE modified CPEG algorithms. Modifications to improve the ACE in PEG LDPC codes, by Xiao and Banihashemi, were implemented in the ‘ACE modified’ versions of the PEG algorithms. The ACE modified standard PEG algorithm constructed the code ensemble with the highest minimum codeword weight and minimum stopping set weight distributions, and the ACE modified CPEG algorithm constructed the code ensemble with the highest local girth and ACE distributions. Short block length irregular LDPC codes with good degree distributions which have higher minimum weights than have been published for similar LDPC codes were found in the four code ensembles.
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.
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.
An efficient method for counting short cycles in the Tanner graphs of quasi cyclic (QC) protograph low-density parity-check (LDPC) codes is presented. The method is based on the relationship between the number of short cycles in the graph and the eigenvalues of the directed edge matrix of the graph. We demonstrate that for a QC protograph LDPC code, the complexity of computing such eigenvalues can be reduced significantly by representing the directed edge matrix as a block circulant matrix. Numerical results are presented to show the lower complexity of the proposed method compared to the existing algorithms for counting short cycles. These results also reveal that QC LDPC codes on average have a superior short cycle and girth distribution compared to similar randomly constructed codes.