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

arXiv:2201.12714 · IEEE International Symposium on Information Theory (ISIT)

The Complete SC-Invariant Affine Automorphisms of Polar Codes

Zicheng Ye, Yuan Li, Huazi Zhang, Rong Li, Jun Wang, Guiying Yan, Zhiming Ma

Published Jun 26, 2022• 8 citations
arXivHTMLPDF

Abstract

Automorphism ensemble (AE) decoding for polar codes was proposed by decoding permuted codewords with successive cancellation (SC) decoders in parallel and hence has lower latency compared to that of successive cancellation list (SCL) decoding. However, some automorphisms are SC-invariant, thus are redundant in AE decoding. In this paper, we find a necessary and sufficient condition related to the block lower-triangular structure of transformation matrices to identify SC-invariant automorphisms. Furthermore, we provide an algorithm to determine the complete SC-invariant affine automorphisms under a specific polar code construction.

DOI
10.1109/isit50566.2022.9834828

Related papers

Polar Codes for Automorphism Ensemble Decoding

Charles Pillet, Valerio Bioglio, Ingmar Land

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.

arXiv:2102.08250•IEEE Information Theory Workshop (ITW)•Oct 17, 2021•36 citations

Improved Permutation-Based Successive Cancellation Decoding of Polar Codes

Mikhail Kamenev

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.

International Siberian workshops and tutorials on electron devices and materials•Jun 30, 2021•8 citations

Improved Automorphism Ensemble Decoder for Polar Codes

Seokju Han, Bonghoe Kim, Jaehoon Chung +1 more

In this work, we propose an improved automorphism ensemble (AE) decoder for polar codes. With successive cancellation (SC) variant automorphisms, multiple decoding paths in the AE decoder produce their estimates of the transmitted codeword. In the proposed scheme, the decoding results from the multiple paths are cleverly utilized to generate a new channel output with which an additional decoding path is established. Performance evaluations clearly demonstrate that the proposed decoder achieves significantly improved error-rate performance as compared to the existing AE decoder for polar codes.

IEEE Communications Letters•May 30, 2024•5 citations

Successive Cancellation Automorphism List Decoding of Polar Codes

Lucas Johannsen, Claus Kestel, Marvin Geiselhart +3 more

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.

arXiv:2306.16245•International Symposium on Turbo Codes and Iterative Information Processing•Sep 4, 2023•17 citations

Automorphism Ensemble Decoding of Polar Codes with Reduced Number of Routes

Jiajie Li, Huayi Zhou, Ryan Seah +1 more

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.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 18, 2025•1 citation

Subcode Ensemble Decoding of Polar Codes

Henning Lulei, Jonathan Mandelbaum, Marvin Rübenacke +3 more

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.

arXiv:2504.17511•International Symposium on Turbo Codes and Iterative Information Processing•Aug 18, 2025•2 citations
Automorphism ensemble (AE) decoding for polar codes was proposed by decoding permuted codewords with successive cancellation (SC) decoders in parallel and hence has lower latency compared to that of successive cancellation list (SCL) decoding. However, some automorphisms are SC-invariant, thus are redundant in AE decoding. In this paper, we find a necessary and sufficient condition related to the block lower-triangular structure of transformation matrices to identify SC-invariant automorphisms. Furthermore, we provide an algorithm to determine the complete SC-invariant affine automorphisms under a specific polar code construction.
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.
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.
In this work, we propose an improved automorphism ensemble (AE) decoder for polar codes. With successive cancellation (SC) variant automorphisms, multiple decoding paths in the AE decoder produce their estimates of the transmitted codeword. In the proposed scheme, the decoding results from the multiple paths are cleverly utilized to generate a new channel output with which an additional decoding path is established. Performance evaluations clearly demonstrate that the proposed decoder achieves significantly improved error-rate performance as compared to the existing AE decoder for polar codes.
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.
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.
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.