arXiv:2406.02012 · International Symposium on Wireless Communication Systems

Improved Generalized Automorphism Belief Propagation Decoding

Jonathan Mandelbaum, Sisi Miao, Nils Albert Schwendemann, Holger Jäkel, Laurent Schmalen

Published Jul 14, 2024• 2 citations

Abstract

With the increasing demands on future wireless systems, new design objectives become eminent. Low-density parity-check codes together with belief propagation (BP) decoding have outstanding performance for large block lengths. Yet, for future wireless systems, good decoding performance for short block lengths is mandatory, a regime in which BP decoding typically shows a significant gap to maximum likelihood decoding. Automorphism ensemble decoding (AED) is known to reduce this gap effectively and, in addition, enables an easy trade-off between latency, throughput, and complexity. Recently, generalized AED (GAED) was proposed to increase the set of feasible automorphisms suitable for ensemble decoding. By construction, GAED requires a preprocessing step within its constituent paths that results in information loss and potentially limits the gains of GAED. In this work, we show that the preprocessing step can be merged with the Tanner graph of BP decoding, thereby improving the performance of the constituent paths. Finally, we show that the improvement of the individual paths also enhances the overall performance of the ensemble.

DOI: 10.1109/iswcs61526.2024.10639098

Related papers

Generalized Automorphisms of Channel Codes: Properties, Code Design, and a Decoder

Jonathan Mandelbaum, Holger Jäkel, Laurent Schmalen

Low-density parity-check codes together with belief propagation (BP) decoding are known to be well-performing for large block lengths. However, for short block lengths there is still a considerable gap between the performance of BP decoding and maximum likelihood decoding. Different ensemble decoding schemes such as, e.g., automorphism ensemble decoding (AED), can reduce this gap in short block length regime. We propose generalized AED (GAED) that uses automorphisms according to the definition in linear algebra. Here, an automorphism of a vector space is defined as a linear, bijective self-mapping, whereas in coding theory self-mappings that are scaled permutations are commonly used. We show that the more general definition leads to an explicit joint construction of codes and automorphisms, and significantly enlarges the search space for automorphisms of existing linear codes. Furthermore, we prove the concept that generalized automorphisms can indeed be used to improve decoding. Additionally, we propose a code construction of linear codes enabling the construction of codes with suitably designed automorphisms. Finally, we analyze the decoding performances of GAED for some of our constructed codes.

arXiv:2304.14379International Symposium on Turbo Codes and Iterative Information ProcessingSep 4, 20236 citations

Automorphism Ensemble Decoding of Quasi-Cyclic LDPC Codes by Breaking Graph Symmetries

Marvin Geiselhart, Moustafa Ebada, Ahmed Elkelesh +2 more

We consider automorphism ensemble decoding (AED) of quasi-cyclic (QC) low-density parity-check (LDPC) codes. Belief propagation (BP) decoding on the conventional factor graph is equivariant to the quasi-cyclic automorphisms and therefore prevents gains by AED. However, by applying small modifications to the parity-check matrix at the receiver side, we can break the symmetry without changing the code at the transmitter. This way, we can leverage a gain in error-correcting performance using an ensemble of identical BP decoders, without increasing the worst-case decoding latency. The proposed method is demonstrated using LDPC codes from the CCSDS, 802.11n and 5G standards and produces gains of 0.2 to 0.3 dB over conventional BP decoding. Compared to the similarly performing saturated BP (SBP), the proposed algorithm reduces the average decoding latency by more than eight times.

arXiv:2202.00287IEEE Communications LettersMay 11, 202216 citations

A Comparative Study of Ensemble Decoding Methods for Short Length LDPC Codes

Felix Krieg, Jannis Clausius, Marvin Rübenacke +1 more

To alleviate the suboptimal performance of belief propagation (BP) decoding of short low-density parity-check (LDPC) codes, a plethora of improved decoding algorithms has been proposed over the last two decades. Many of these methods can be described using the same general framework, which we call ensemble decoding: A set of independent constituent decoders works in parallel on the received sequence, each proposing a code-word candidate. From this list, the maximum likelihood (ML) decision is designated as the decoder output. In this paper, we qualitatively and quantitatively compare different realizations of the ensemble decoder, namely multiple-bases belief propagation (MBBP), automorphism ensemble decoding (AED), scheduling ensemble decoding (SED), noise-aided ensemble decoding (NED) and saturated belief propagation (SBP). While all algorithms can provide gains over traditional BP decoding, ensemble methods that exploit the code structure, such as MBBP and AED, typically show greater performance improvements.

arXiv:2410.23980International ITG Conference on Systems, Communications and Coding (SCC)Mar 10, 20254 citations

Toward Universal Belief Propagation Decoding for Short Binary Block Codes

Yifei Shen, Zongyao Li, Yuqing Ren +5 more

Belief propagation (BP) decoding has been recognized for its capacity-approaching performance and high throughput when decoding long low-density parity-check (LDPC) codes. However, the application of BP decoding for short codes is hindered by dense parity-check matrices (PCMs) and prevalent short cycles in the Tanner graph. In this paper, we introduce a general method to extract an optimized sparse PCM for short binary block codes, which removes length-four cycles and enhances the connectivity of short cycles to enable BP decoding with improved performance. Notably, for short binary codes with lengths up to 64, our BP decoding performance approaches the maximum likelihood bound and surpasses the best-reported BP results with reduced computational complexity. Compared with other universal decoding algorithms, BP decoding using our extracted sparse PCMs is competitive in terms of both error-rate performance and computational complexity. These promising results suggest that our method to improve BP decoding for short codes is a step toward a practical universal BP decoder for next-generation communication systems.

IEEE Journal on Selected Areas in CommunicationsFeb 14, 20259 citations

Low-Complexity Automorphism Ensemble Decoding of Reed-Muller Codes Using Path Pruning

Kairui Tian, Rongke Liu, Zheng Lu

The newly developed automorphism ensemble decoder (AED) leverages the rich automorphisms of Reed-Muller (RM) codes to achieve near maximum likelihood (ML) performance at short code lengths. However, the performance gain of AED comes at the cost of high complexity, as the ensemble size required for near ML decoding grows exponentially with the code length. In this work, we address this complexity issue by focusing on the factor graph permutation group (FGPG), a subgroup of the full automorphism group of RM codes, to generate permutations for AED. We propose a uniform partitioning of FGPG based on the affine bijection permutation matrices of automorphisms, where each subgroup of FGPG exhibits permutation invariance (PI) in a Plotkin construction-based information set partitioning for RM codes. Furthermore, from the perspective of polar codes, we exploit the PI property to prove a subcode estimate convergence (SEC) phenomenon in the AED that utilizes successive cancellation (SC) or SC list (SCL) constituent decoders. Observing that strong SEC correlates with low noise levels, where the full decoding capacity of AED is often unnecessary, we perform path pruning to reduce the decoding complexity without compromising the performance. Our proposed SEC-aided path pruning allows only a subset of constituent decoders to continue decoding when the intensity of SEC exceeds a preset threshold during decoding. Numerical results demonstrate that, for the FGPG-based AED of various short RM codes, the proposed SEC-aided path pruning technique incurs negligible performance degradation, while achieving a complexity reduction of up to 67.6%.

EntropyJul 28, 20250 citations

Multiple-Bases Belief-Propagation with Leaking for Decoding of Moderate-Length Block Codes

Thorsten Hehn, Johannes B. Huber, Pei He +1 more

Short algebraic codes promise low-delay data transmission and good performance results when transmitted over the additive white Gaussian noise (AWGN) channel and decoded by maximum-likelihood (ML) soft-decision decoding. One reason for this is the large minimum distance of these codes. For belief-propagation (BP) decoding, short algebraic codes show suboptimal results due to their high-density parity-check matrices. Using a collection of parity-check matrices for a given code, Multiple-Bases Belief-Propagation (MBBP) allows for decoding of many dense linear block codes with near ML performance. One convenient way to generate these matrices is using the automorphism group of a code. We point out limits of this approach and show two novel improvements, a decoder modification and a construction algorithm for parity-check matrices, which emphasize that MBBP is a more general approach and independent of the automorphism group. We use these methods to extend the field of application for MBBP to codes of moderate length. This includes codes with parity-check matrices tailored for BP decoding, in particular Progressive Edge-Growth (PEG) codes. 1

Jun 1, 20115 citations