Group Properties of Polar Codes for Automorphism Ensemble Decoding
Valerio Bioglio, Ingmar Land, Charles Pillet · IEEE Transactions on Information Theory · 2023
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.