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 Symposium on Turbo Codes and Iterative Information Processing

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

Published Aug 1, 2014• 6 citations
Publisher

Abstract

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.

DOI
10.1109/istc.2014.6955087

Related papers

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

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

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.

International Conference on Signal Processing and Communication Systems•Dec 1, 2016•6 citations

Transactions papers evaluation and design of irregular LDPC codes using ACE spectrum

Dejan Vukobratović, V. Šenk

The construction of finite-length irregular LDPC codes with low error floors is currently an attractive research problem. In particular, for the binary erasure channel (BEC), the problem is to find the elements of selected irregular LDPC code ensembles with the size of their minimum stopping set being maximized. Due to the lack of analytical solutions to this problem, a simple but powerful heuristic design algorithm, the approximate cycle extrinsic message degree (ACE) constrained design algorithm, has recently been proposed. Building upon the ACE metric associated with a cycle in a code graph, we introduce the ACE spectrum of LDPC codes as a useful tool for evaluation of codes from selected irregular LDPC code ensembles. Using the ACE spectrum, we generalize the ACE constrained design algorithm, making it more flexible and efficient. We justify the ACE spectrum approach through examples and simulation results.

IEEE Transactions on Communications•Aug 1, 2009•30 citations

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

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

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

A cycle-based rate-compatible puncturing technique for non-binary LDPC codes

Kuntal Deka, A. Rajesh, Prabin Kumar Bora

This paper presents a cycle-based rate-compatible puncturing technique for non-binary (NB) low-density parity-check (LDPC) codes. The proposed puncturing technique is based on the connectivity of the short non-binary (NB) cycles present in the Tanner graph. The connectivity of a cycle is measured by the extrinsic message degree (EMD). The short cycles with low values of EMD degrade the performance of iterative decoders significantly. The proposed technique selects the variable nodes for puncturing by reckoning their involvements in the short NB cycles with a low EMD. Simulations in different contexts are performed to check the efficiency of the proposed technique.

International Conference on Signal Processing and Communications (SPCOM)•Jun 1, 2016•1 citation
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.
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.
The construction of finite-length irregular LDPC codes with low error floors is currently an attractive research problem. In particular, for the binary erasure channel (BEC), the problem is to find the elements of selected irregular LDPC code ensembles with the size of their minimum stopping set being maximized. Due to the lack of analytical solutions to this problem, a simple but powerful heuristic design algorithm, the approximate cycle extrinsic message degree (ACE) constrained design algorithm, has recently been proposed. Building upon the ACE metric associated with a cycle in a code graph, we introduce the ACE spectrum of LDPC codes as a useful tool for evaluation of codes from selected irregular LDPC code ensembles. Using the ACE spectrum, we generalize the ACE constrained design algorithm, making it more flexible and efficient. We justify the ACE spectrum approach through examples and simulation results.
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.
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.
This paper presents a cycle-based rate-compatible puncturing technique for non-binary (NB) low-density parity-check (LDPC) codes. The proposed puncturing technique is based on the connectivity of the short non-binary (NB) cycles present in the Tanner graph. The connectivity of a cycle is measured by the extrinsic message degree (EMD). The short cycles with low values of EMD degrade the performance of iterative decoders significantly. The proposed technique selects the variable nodes for puncturing by reckoning their involvements in the short NB cycles with a low EMD. Simulations in different contexts are performed to check the efficiency of the proposed technique.