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:2110.14438 · International Conference on Communications

Classification of Automorphisms for the Decoding of Polar Codes

Charles Pillet, Valerio Bioglio, Ingmar Land

Published May 16, 2022• 26 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/icc45855.2022.9838937

Related papers

Group Properties of Polar Codes for Automorphism Ensemble Decoding

Valerio Bioglio, Ingmar Land, Charles Pillet

In this paper, we propose an analysis of the automorphism group of polar codes, with the aim of designing codes tailored forautomorphism ensemble(AE) decoding. Using a novel description of polar codes as monomial codes through negative monomials, we prove the equivalence between the notion ofdecreasing monomial codesand the universal partial order (UPO) framework for polar codes; this property is widely believed to hold true but a formal proof was missing. We further provide a rigorous mathematical connection between code word permutations and affine transformations, an important link to understand the considered automorphisms. Based on this mathematical formalisms, we analyze the algebraic properties of theaffine automorphisms groupof polar codes, providing a novel description of its structure. We classify automorphisms such that all automorphisms in the same class lead to the same result under permutation decoding, which gives rise to the concept ofredundantautomorphisms. Mathematically this is achieved by introducing equivalence classes of affine automorphisms under AE-based decoding. For practical application, we provide an algorithm to compute representatives for the equivalence classes, such that one automorphism from each equivalence class can be selected for use in AE decoding. A numerical analysis of the error correction performance of AE decoding of polar codes, based on equivalence classes, concludes the paper.

arXiv:2206.03342•IEEE Transactions on Information Theory•Jan 25, 2023•15 citations

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 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

Automorphism Set Construction for Automorphism Ensemble Decoding With Reduced Delay

Anna A. Fominykh, Kirill Shabunov

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.

IEEE Open Journal of the Communications Society•Jan 1, 2025•0 citations

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
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.
In this paper, we propose an analysis of the automorphism group of polar codes, with the aim of designing codes tailored forautomorphism ensemble(AE) decoding. Using a novel description of polar codes as monomial codes through negative monomials, we prove the equivalence between the notion ofdecreasing monomial codesand the universal partial order (UPO) framework for polar codes; this property is widely believed to hold true but a formal proof was missing. We further provide a rigorous mathematical connection between code word permutations and affine transformations, an important link to understand the considered automorphisms. Based on this mathematical formalisms, we analyze the algebraic properties of theaffine automorphisms groupof polar codes, providing a novel description of its structure. We classify automorphisms such that all automorphisms in the same class lead to the same result under permutation decoding, which gives rise to the concept ofredundantautomorphisms. Mathematically this is achieved by introducing equivalence classes of affine automorphisms under AE-based decoding. For practical application, we provide an algorithm to compute representatives for the equivalence classes, such that one automorphism from each equivalence class can be selected for use in AE decoding. A numerical analysis of the error correction performance of AE decoding of polar codes, based on equivalence classes, concludes the paper.
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.
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.
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.
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.