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

International Symposium on Information Theory and its Applications

On the dependency between the code symmetries and the decoding efficiency

Kirill Svyatoslavich Ivanov, Rudiger L. Urbanke

Published Oct 24, 2020• 3 citations
OpenAlex

Abstract

A framework of monomial codes is considered, which includes linear codes generated by the evaluation of certain monomials. Polar and Reed-Muller codes are the two best-known representatives of such codes and can be considered as two extreme cases. Reed-Muller codes have a large automorphism group but their low-complexity maximum likelihood decoding still remains an open problem. On the other hand, polar codes have much less symmetries but admit the efficient near-ML decoding.

Related papers

Efficient Maximum-Likelihood Decoding of Reed–Muller RM(m−3,m) Codes

Andrew Thangaraj, Henry D. Pfister

Reed-Muller (RM) codes, a classical family of codes known for their elegant algebraic structure, have recently been shown to achieve capacity under maximum-likelihood (ML) decoding on the binary erasure channel and this has rekindled interest in their efficient decoding. We consider the code family RM(m-3,m) and develop a new ML decoder, for transmission over the binary symmetric channel, that exploits their large symmetry group. The new decoder has lower complexity than an earlier method introduced by Seroussi and Lempel in 1983.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•5 citations

Algebraic properties of polar codes from a new polynomial formalism

Magali Bardet, Vlad Drăgoi, Ayoub Otmani +1 more

Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attains many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a nontrivial task and is channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised for a binary-input symmetric channel always form a decreasing set. We call such codes decreasing monomial codes. The fact that polar codes are decreasing monomial codes turns out to have rather deep consequences on their structure. Indeed, we show that decreasing monomial codes have a very large permutation group by proving that it contains a group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from evaluations of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.

arXiv:1601.06215•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•162 citations

Automorphism Ensemble Decoding of Reed–Muller Codes

Marvin Geiselhart, Ahmed Elkelesh, Moustafa Ebada +2 more

Reed–Muller (RM) codes are known for their good maximum likelihood (ML) performance in the short block-length regime. Despite being one of the oldest classes of channel codes, finding a low complexity soft-input decoding scheme is still an open problem. In this work, we present a versatile decoding architecture for RM codes based on their rich automorphism group. The decoding algorithm can be seen as a generalization of multiple-bases belief propagation (MBBP) and may use any polar or RM decoder as constituent decoders. We provide extensive error-rate performance simulations for successive cancellation (SC)-, SC-list (SCL)- and belief propagation (BP)-based constituent decoders. We furthermore compare our results to existing decoding schemes and report a near-ML performance for the RM(3,7)-code (e.g., 0.04 dB away from the ML bound at BLER of 10−3) at a competitive computational cost. Moreover, we provide some insights into the automorphism subgroups of RM codes and SC decoding and, thereby, prove the theoretical limitations of this method with respect to polar codes.

arXiv:2012.07635•IEEE Transactions on Communications•Jul 21, 2021•104 citations

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•17 citations

Decoding Reed-Muller Codes Using Minimum- Weight Parity Checks

Elia Santi, Christian Häger, Henry D. Pfister

Reed-Muller (RM) codes exhibit good performance under maximum-likelihood (ML) decoding due to their highly-symmetric structure. In this paper, we explore the question of whether the code symmetry of RM codes can also be exploited to achieve near-ML performance in practice. The main idea is to apply iterative decoding to a highly-redundant parity-check (PC) matrix that contains only the minimum-weight dual codewords as rows. As examples, we consider the peeling decoder for the binary erasure channel, linear-programming and belief propagation (BP) decoding for the binary-input additive white Gaussian noise channel, and bit-flipping and BP decoding for the binary symmetric channel. For short block lengths, it is shown that near-ML performance can indeed be achieved in many cases. We also propose a method to tailor the PC matrix to the received observation by selecting only a small fraction of useful minimum-weight PCs before decoding begins. This allows one to both improve performance and significantly reduce complexity compared to using the full set of minimum-weight PCs.

arXiv:1804.10319•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•51 citations

Recursive Decoding of Reed-Muller Codes Starting With the Higher-Rate Constituent Code

Mikhail Kamenev

Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length$(\leq 256)$RM codes. Recursive decoding employs the Plotkin construction to split the original code into two shorter RM codes with different rates. In contrast to the standard approach which decodes the lower-rate code first, the method in this paper decodes the higher-rate code first. This modification enables an efficient permutation-based decoding technique, with permutations being selected on the fly from the automorphism group of the code using soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms, enhanced by a permutation selection technique, is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for short RM codes and for RM codes of length$2^{m}$and order$m-3$with reasonable complexity.

arXiv:2101.11328•IEEE Transactions on Information Theory•Jul 29, 2022•5 citations
A framework of monomial codes is considered, which includes linear codes generated by the evaluation of certain monomials. Polar and Reed-Muller codes are the two best-known representatives of such codes and can be considered as two extreme cases. Reed-Muller codes have a large automorphism group but their low-complexity maximum likelihood decoding still remains an open problem. On the other hand, polar codes have much less symmetries but admit the efficient near-ML decoding.
Reed-Muller (RM) codes, a classical family of codes known for their elegant algebraic structure, have recently been shown to achieve capacity under maximum-likelihood (ML) decoding on the binary erasure channel and this has rekindled interest in their efficient decoding. We consider the code family RM(m-3,m) and develop a new ML decoder, for transmission over the binary symmetric channel, that exploits their large symmetry group. The new decoder has lower complexity than an earlier method introduced by Seroussi and Lempel in 1983.
Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attains many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a nontrivial task and is channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised for a binary-input symmetric channel always form a decreasing set. We call such codes decreasing monomial codes. The fact that polar codes are decreasing monomial codes turns out to have rather deep consequences on their structure. Indeed, we show that decreasing monomial codes have a very large permutation group by proving that it contains a group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from evaluations of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.
Reed–Muller (RM) codes are known for their good maximum likelihood (ML) performance in the short block-length regime. Despite being one of the oldest classes of channel codes, finding a low complexity soft-input decoding scheme is still an open problem. In this work, we present a versatile decoding architecture for RM codes based on their rich automorphism group. The decoding algorithm can be seen as a generalization of multiple-bases belief propagation (MBBP) and may use any polar or RM decoder as constituent decoders. We provide extensive error-rate performance simulations for successive cancellation (SC)-, SC-list (SCL)- and belief propagation (BP)-based constituent decoders. We furthermore compare our results to existing decoding schemes and report a near-ML performance for the RM(3,7)-code (e.g., 0.04 dB away from the ML bound at BLER of 10−3) at a competitive computational cost. Moreover, we provide some insights into the automorphism subgroups of RM codes and SC decoding and, thereby, prove the theoretical limitations of this method with respect to polar codes.
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.
Reed-Muller (RM) codes exhibit good performance under maximum-likelihood (ML) decoding due to their highly-symmetric structure. In this paper, we explore the question of whether the code symmetry of RM codes can also be exploited to achieve near-ML performance in practice. The main idea is to apply iterative decoding to a highly-redundant parity-check (PC) matrix that contains only the minimum-weight dual codewords as rows. As examples, we consider the peeling decoder for the binary erasure channel, linear-programming and belief propagation (BP) decoding for the binary-input additive white Gaussian noise channel, and bit-flipping and BP decoding for the binary symmetric channel. For short block lengths, it is shown that near-ML performance can indeed be achieved in many cases. We also propose a method to tailor the PC matrix to the received observation by selecting only a small fraction of useful minimum-weight PCs before decoding begins. This allows one to both improve performance and significantly reduce complexity compared to using the full set of minimum-weight PCs.
Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length(≤256)(\leq 256)(≤256)RM codes. Recursive decoding employs the Plotkin construction to split the original code into two shorter RM codes with different rates. In contrast to the standard approach which decodes the lower-rate code first, the method in this paper decodes the higher-rate code first. This modification enables an efficient permutation-based decoding technique, with permutations being selected on the fly from the automorphism group of the code using soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms, enhanced by a permutation selection technique, is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for short RM codes and for RM codes of length2m2^{m}2mand orderm−3m-3m−3with reasonable complexity.