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:2102.08250 · IEEE Information Theory Workshop (ITW)

Polar Codes for Automorphism Ensemble Decoding

Charles Pillet, Valerio Bioglio, Ingmar Land

Published Oct 17, 2021• 36 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/itw48936.2021.9611504

Related papers

The Complete SC-Invariant Affine Automorphisms of Polar Codes

Zicheng Ye, Yuan Li, Huazi Zhang +4 more

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.

arXiv:2201.12714•IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•8 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

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

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

Automorphism Ensemble Decoding With Reduced Delay

Anna A. Fominykh, Kirill Shabunov

Projected requirements for 6G ultra-reliable low-latency communications (URLLC) scenario require extremely low latency and efficient error correction akin to maximum likelihood (ML) performance. The quest for codes and decoding methods that balance low latency, energy efficiency, and error correction ability is at its height. Polar codes known for their capacity achievement in symmetric memoryless channels have shown promise in 5G applications. Advancing further existing decoding techniques like successive cancellation list (SCL) algorithm offer a path towards ML performance, whilst at the expense of having increased computational complexity. The introduction of automorphism ensemble (AE) decoding provided a novel approach for parallel decoding, particularly beneficial for codes with rich automorphism group like Reed-Muller (RM) codes. This work introduces a novel modification of AE decoding termed reduced-delay AE (RD-AE) decoder. RD-AE leverages a tailored set of automorphisms with the primary aim at diminishing decoding delay but also offering the flexibility to prioritize either delay reduction or error correction performance.

IEEE Globecom Workshops (GC Wkshps)•Dec 8, 2024•0 citations

Classification of Automorphisms for the Decoding of Polar Codes

Charles Pillet, Valerio Bioglio, Ingmar Land

This paper proposes new polar code design principles for the low-latency automorphism ensemble (AE) decoding. Our proposal permits to design a polar code with the desired automorphism group (if possible) while assuring the decreasing monomial property. Moreover, we prove that some automorphisms are redundant under AE decoding, and we propose a new automorphisms classification based on equivalence classes. Finally, we propose an automorphism selection heuristic based on drawing only one element of each class; we show that this method enhances the block error rate (BLER) performance of short polar codes even with a limited number of automorphisms.

arXiv:2110.14438•International Conference on Communications•May 16, 2022•26 citations
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 (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.
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.
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 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.
Projected requirements for 6G ultra-reliable low-latency communications (URLLC) scenario require extremely low latency and efficient error correction akin to maximum likelihood (ML) performance. The quest for codes and decoding methods that balance low latency, energy efficiency, and error correction ability is at its height. Polar codes known for their capacity achievement in symmetric memoryless channels have shown promise in 5G applications. Advancing further existing decoding techniques like successive cancellation list (SCL) algorithm offer a path towards ML performance, whilst at the expense of having increased computational complexity. The introduction of automorphism ensemble (AE) decoding provided a novel approach for parallel decoding, particularly beneficial for codes with rich automorphism group like Reed-Muller (RM) codes. This work introduces a novel modification of AE decoding termed reduced-delay AE (RD-AE) decoder. RD-AE leverages a tailored set of automorphisms with the primary aim at diminishing decoding delay but also offering the flexibility to prioritize either delay reduction or error correction performance.
This paper proposes new polar code design principles for the low-latency automorphism ensemble (AE) decoding. Our proposal permits to design a polar code with the desired automorphism group (if possible) while assuring the decreasing monomial property. Moreover, we prove that some automorphisms are redundant under AE decoding, and we propose a new automorphisms classification based on equivalence classes. Finally, we propose an automorphism selection heuristic based on drawing only one element of each class; we show that this method enhances the block error rate (BLER) performance of short polar codes even with a limited number of automorphisms.