International Conference on Networks, Communications and Information Technology (CNCIT)

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

Xiang Li, Xuan He

Published May 29, 2026• 0 citations

Abstract

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.

DOI: 10.1145/3821162.3821166

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 SystemsDec 1, 20166 citations

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 ProcessingAug 1, 20146 citations

Optimization of QC-LDPC Codes by Edge Exchange Method Based on ACE

Xin Qin, Chuanchuan Yang, Ziyuan Zheng +1 more

Long quasi-cyclic low-density parity check (QC-LDPC) codes have been chosen as one of the forward error correction (FEC) schemes in passive optical network (PON) systems benefiting from the excellent performance. About how to get the appropriate LDPC codes, some traditional methods which focus on obtaining large girth or flat approximated cycle extrinsic message degree (ACE) spectrums are proposed for the design of LDPC codes. These methods which may still make the existence of small stopping sets containing short cycles probably are not so useful for long QC-LDPC codes. Recently, the parallel vector message passing (PMP) algorithm oriented-to decreasing the number of short cycles is proved to be an effective method to optimize LDPC codes. Since ignoring short cycles with poor connectivity which can induce error floor, this method cannot guarantee its effectiveness for long QC-LDPC codes. In this letter, an edge exchange optimization method based on the global properties of ACE and girth called EEA method is proposed, which tries to reduce cycles with low ACE in the order of cycle length. The numerical results prove that our EEA method can bring the improvements of error floor up to two orders of magnitude to long QC-LDPC codes and obviously outperforms PMP algorithm.

IEEE Photonics Technology LettersJul 7, 20194 citations

Fast Identification of Error-Prone Patterns for LDPC Codes under Message Passing Decoding

Jing Lei, Wen Gao

Although density evolution accurately predicts the asymptotic performance of LDPC codes, it provides limited information for codes of short or moderate block length. For this reason, combinatorial methods have been employed to analyze the performance of finite-length LDPC codes under message passing decoding. The error floor phenomenon is a key issue of finite-length effects, which is caused largely by poorly connected subgraphs residing in the LPDC codes structure. Because of the unequal noise immunity of different bit levels, error floors become more pronounced for LDPC-coded high-order modulation. Nevertheless, the enumeration of error-prone patterns that lead to error floors has been proven to be NP-hard, which motivates us to find substitute metrics with manageable complexity. Considering trapping sets always comprise loops of low extrinsic message degree (EMD) and the connectivity of a loop with the residual graph can be characterized by its approximate EMD (ACE), in this paper we propose a fast method to identify loops with low ACE for a given code. In light of this, the vulnerable variable nodes residing on low-ACE loops are judiciously mapped to bit levels benefitting from stronger error protection. As a result, the error floor can be significantly improved at the cost of a minor increase of hardware complexity.

GlobecomJan 1, 20084 citations

An Improved ACE Algorithm Based on Structural Optimization LDPC

Wang Li

In order to improve the performance of LDPC code,an optimized LDPC code was constructed by calculating extrinsic message degree of the cycle.This algorithm can remove the short cycle,which is produced unavoidably in constructing LDPC codes,to improve a bipartite graph local connectivity.Experimental results show that the algorithm is better to improve LDPC codes' performance in the same code length,code rate and the degree distribution.

Journal of Henan University of Science & TechnologyJan 1, 20100 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 CommunicationsAug 1, 200930 citations