Automorphism Ensemble (AE) decoding has recently drawn attention as a possible alternative to list decoding of polar codes. In this letter, we investigate the distribution of Partially-Symmetric Reed-Muller (PS-RM) codes, a family of polar codes yielding good performances under AE decoding. We prove the existence of these codes for almost all code dimensions for code lengths N ≤ 256. Moreover, we analyze the absorption group of this family of codes under SC decoding, proving that valuable permutations in AE decoding always exist. Finally, we experimentally show that PS-RM codes can outperform state-of-the-art polar-code-construction algorithms in terms of error-correction performance for short code lengths, while reducing decoding latency.
Automorphism Ensemble (AE) decoding has recently drawn attention as a possible alternative to list decoding of polar codes. In this letter, we investigate the distribution of Partially-Symmetric Reed-Muller (PS-RM) codes, a family of polar codes yielding good performances under AE decoding. We prove the existence of these codes for almost all code dimensions for code lengths N ≤ 256. Moreover, we analyze the absorption group of this family of codes under SC decoding, proving that valuable permutations in AE decoding always exist. Finally, we experimentally show that PS-RM codes can outperform state-of-the-art polar-code-construction algorithms in terms of error-correction performance for short code lengths, while reducing decoding latency.
Reed–Muller (RM) codes are known for their good maximum likelihood (ML) performance in the short block-length regime. Despite being one of the oldest classes of channel codes, finding a low complexity soft-input decoding scheme is still an open problem. In this work, we present a versatile decoding architecture for RM codes based on their rich automorphism group. The decoding algorithm can be seen as a generalization of multiple-bases belief propagation (MBBP) and may use any polar or RM decoder as constituent decoders. We provide extensive error-rate performance simulations for successive cancellation (SC)-, SC-list (SCL)- and belief propagation (BP)-based constituent decoders. We furthermore compare our results to existing decoding schemes and report a near-ML performance for the RM(3,7)-code (e.g., 0.04 dB away from the ML bound at BLER of 10−3) at a competitive computational cost. Moreover, we provide some insights into the automorphism subgroups of RM codes and SC decoding and, thereby, prove the theoretical limitations of this method with respect to polar codes.
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%.
In this paper we deal with polar code automorphisms that are beneficial under low-latency automorphism ensemble (AE) decoding, and we propose polar code designs that have such automorphisms. Successive-cancellation (SC) decoding and thus SC-based AE decoding are invariant with respect to the only known polar code automorphisms, namely those of the lower-triangular affine (LTA) group. To overcome this problem, we provide methods to determine whether a given polar code has non-LTA automorphisms and to identify such automorphisms. Building on this, we design specific polar codes that admit automorphisms in the upper-diagonal linear (UTL) group, and thus render SC-based AE decoding effective. Demonstrated by examples, these new polar codes under AE decoding outperform conventional polar codes under SC list decoding in terms of error rate, while keeping the latency comparable to SC decoding. Moreover, state-of-the-art BP-based permutation decoding for polar codes is beaten by BP-based AE thanks to this design.
The anticipated demands of 6G ultra-reliable low-latency communications (URLLC) call for near-instantaneous data transfers and error-correction efficiency rivaling maximum-likelihood (ML) decoding. Achieving an effective compromise between latency, power consumption, and decoding accuracy is a pivotal challenge in contemporary coding theory. Polar codes have distinguished themselves by achieving capacity on symmetric memoryless channels. To narrow the gap to ML performance, refined techniques like successive-cancellation list (SCL) decoding have been developed, albeit with a rise in computational burden. More recently, automorphism ensemble (AE) decoding has unlocked parallelization benefits for codes with rich automorphism groups, such as Reed-Muller codes. This paper discusses the reduced-delay AE (RD-AE) decoder, which harnesses a carefully chosen subset of automorphisms to drastically cut decoding latency while allowing a flexible trade-off between speed and error-correction performance. This article is an extended version of research previously introduced at a conference. We discuss key aspects and nuances of the algorithm and its implementation, including: (1) algorithms for selecting automorphism sets to meet specific performance targets, (2) a detailed procedure for combining bits from different permutations, (3) code construction methodologies for RD-AE decoding, and (4) implementation considerations. Furthermore, we explore various scenarios and applications of the proposed algorithm and present simulation results demonstrating significant latency reductions while maintaining error-correction performance.
By exploiting the rich automorphisms of Reed-Muller (RM) codes, the recently developed automorphism ensemble (AE) successive cancellation (SC) decoder achieves a near-maximum-likelihood (ML) performance for short block lengths. However, the appealing performance of AE-SC decoding arises from the diversity gain that requires a list of SC decoding attempts, which results in a high decoding complexity. To address this issue, this paper proposes a novel quasi-optimal path convergence (QOPC)-aided early termination (ET) technique for AE-SC decoding. This technique detects strong convergence between the partial path metrics (PPMs) of SC constituent decoders to reliably identify the optimal decoding path at runtime. When the QOPC-based ET criterion is satisfied during the AE-SC decoding, only the identified path is allowed to proceed for a complete codeword estimate, while the remaining paths are terminated early. The numerical results demonstrated that for medium-to-high-rate RM codes in the short-length regime, the proposed QOPC-aided ET method incurred negligible performance loss when applied to fully parallel AE-SC decoding. Meanwhile, it achieved a complexity reduction that ranged from 35.9% to 47.4% at a target block error rate (BLER) of 10-3, where it consistently outperformed a state-of-the-art path metric threshold (PMT)-aided ET method. Additionally, under a partially parallel framework of AE-SC decoding, the proposed QOPC-aided ET method achieved a greater complexity reduction that ranged from 81.3% to 86.7% at a low BLER that approached 10-5 while maintaining a near-ML decoding performance.
Polar codes have been recently shown to have an automorphism group larger than the lower-triangular affine group. Permutations from this group can be used in an automorphism successive cancellation (SC) decoding algorithm providing a lower latency compared to that of successive cancellation list decoding. In this paper, we demonstrate that any permutation from the automorphism group of Reed-Muller codes is suitable for permutation-based SC decoding of polar codes. Specifically, a code obtained by a permutation that is not in the automorphism group of the code, but is in the automorphism group of Reed-Muller codes, is shown to be a polar subcode. Simulations results show that these additional permutations allow improving performance of the automorphism SC decoding algorithm limited to the permutations from the automorphism group of the code.