Automorphism ensemble decoding (AED) with the successive cancellation (SC) constituent decoder (AED-SC) can achieve similar decoding performance to the successive cancellation list (SCL) decoder when decoding short-to-medium-length polar codes. However, implementing automorphisms requires additional hardware for routing, leading to significant area overhead, especially with a large number of automorphisms. We propose methods for selecting automorphisms in SC decoders to reduce routing overhead. We establish the equivalence between automorphism selection and the NP-hard minimum K-union (MKU) problem. To maintain decoding performance under the selected automorphisms, we formulate the equivalence class property of AED-SC as a quadratic constraint. Compared to the state-of-the-art, our method achieves up to a 2.9× reduction in the number of routes needed to implement all automorphisms.
Automorphism ensemble decoding (AED) with the successive cancellation (SC) constituent decoder (AED-SC) can achieve similar decoding performance to the successive cancellation list (SCL) decoder when decoding short-to-medium-length polar codes. However, implementing automorphisms requires additional hardware for routing, leading to significant area overhead, especially with a large number of automorphisms. We propose methods for selecting automorphisms in SC decoders to reduce routing overhead. We establish the equivalence between automorphism selection and the NP-hard minimum K-union (MKU) problem. To maintain decoding performance under the selected automorphisms, we formulate the equivalence class property of AED-SC as a quadratic constraint. Compared to the state-of-the-art, our method achieves up to a 2.9× reduction in the number of routes needed to implement all automorphisms.
Automorphism ensemble decoding with the successive cancellation constituent decoder (AED-SC) can improve the decoding performance of the successive cancellation decoder when decoding polar codes with short-to-medium code lengths. To reduce the number of automorphisms used by the AEDSC, simplified repetition handling early-stopping is proposed in this work. Compared to the original repetition handling earlystopping, our simplified version compares the path metric instead of the codeword. Up to a 2× reduction in the number of automorphisms used is observed when decoding polar codes with different code lengths and dimensions while having little degraded decoding performance. Also, the proposed simplification reduces the number of bit comparisons from a number equal to the code length to the number of bits required to represent the path metric.
The discovery of suitable automorphisms of polar codes gained a lot of attention by applying them in Automorphism Ensemble Decoding (AED) to improve the error-correction performance, especially for short block lengths. This paper introduces Successive Cancellation Automorphism List (SCAL) decoding of polar codes as a novel application of automorphisms in advanced Successive Cancellation List (SCL) decoding. Initialized with L permutations selected from the automorphism group, a superposition of different noise realizations and path splitting takes place inside the decoder. In this way, the SCAL decoder automatically adapts to the channel conditions and outperforms the error-correction performance of conventional SCL decoding and AED. For a polar code of length 128, SCAL performs near Maximum Likelihood (ML) decoding with L=8, in contrast to M=16 needed decoder cores in AED. Application-Specific Integrated Circuit (ASIC) implementations in a 12nm technology show that high-throughput, pipelined SCAL decoders outperform AED in terms of energy efficiency and power density, and SCL decoders additionally in area efficiency.
In the short block length regime, pre-transformed polar codes together with successive cancellation list (SCL) decoding possess excellent error correction capabilities. However, in practice, the list size is limited due to the suboptimal scaling of the required area in hardware implementations. Automorphism ensemble decoding (AED) can improve performance for a fixed list size by running multiple parallel SCL decodings on permuted received words, yielding a list of estimates from which the final estimate is selected. Yet, AED is limited to appropriately designed polar codes. Subcode ensemble decoding (ScED) was recently proposed for low-density parity-check codes and does not impose such design constraints. It uses multiple decodings in different subcodes, ensuring that the selected subcodes jointly cover the original code. We extend ScED to polar codes by expressing polar subcodes through suitable pre-transformations (PTs). To this end, we describe a framework classifying pre-transformations for pretransformed polar codes based on their role in encoding and decoding. Within this framework, we propose a new type of PT enabling ScED for polar codes, analyze its properties, and discuss how to construct an efficient ensemble.
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.
Automorphism ensemble decoding (AED) is a highly parallel approach that enables decoding of polar and Reed-Muller (RM) codes with automorphisms, offering a practical solution with near-maximum likelihood (ML) performance and manageable computational complexity. To meet the growing demands for high throughput and low latency in cloud and virtual random access networks, this paper presents a graphics processing unit (GPU)-based AED architecture for polar and RM codes, utilizing low-complexity successive cancellation (SC) and small list SC (SCL) decoders as the constituent of AED. The proposed architecture exploits the inherent parallelism of AED to optimize decoding tasks on the GPU, significantly enhancing throughput by efficiently harnessing the extensive parallel processing capabilities of the GPU. Additionally, improved thread mapping and data management techniques markedly reduce latency for automorphism ensemble SC (Aut-SC) decoding, while a low-latency sorting mechanism further accelerates automorphism ensemble SCL (Aut-SCL) decoding. Experimental results on an NVIDIA RTX 4090 demonstrate that the proposed Aut-SC decoder, with an ensemble size of 8, achieves a throughput exceeding 17 Gbps. Compared to the state-of-the-art softwarebased SCL decoders, the proposed GPU-based Aut-SC and Aut-SCL architectures outperform existing solutions by factors of up to 28× and 10×, respectively, in normalized throughput while maintaining the same or even superior error correction performance.
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%.