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:2002.00325 · IEEE Transactions on Information Theory

Polar Decreasing Monomial-Cartesian Codes

Eduardo Camps-Moreno, Hiram H. López, Gretchen L. Matthews, Eliseo Sarmiento

Published Dec 28, 2020• 15 citations
arXivHTMLPDF

Abstract

In this article, we introduce a new family of polar codes from evaluation codes, called polar decreasing monomial-Cartesian codes, and prove that families of polar codes with multiple kernels over certain symmetric channels can be viewed as polar decreasing monomial-Cartesian codes. This offers a unified treatment for such codes over any finite field. We define decreasing monomial-Cartesian codes as evaluation codes obtained from a set of monomials closed under divisibility over a Cartesian product and determine their parameters (length, dimension, and minimum distance). We show that the dual of a decreasing monomial-Cartesian code is monomially equivalent to a decreasing monomial-Cartesian code. Polar decreasing monomial-Cartesian codes are then obtained by utilizing decreasing monomial-Cartesian codes whose sets of monomials are closed with respect to a partial order. We prove that any sequence of invertible matrices over an arbitrary field satisfying certain conditions polarizes any channel that is symmetric over the field.

DOI
10.1109/tit.2020.3047624

Related papers

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

On the Equivalence between Pre-transformed and Parity-check Monomial Codes

Yuanxin Guo, Zihan Tang, Bin Li

Polar codes and Reed-Muller codes belong to a family of codes called monomial codes. In this work, we study pre-transformed monomial codes, which cover several constructions including parity-check (PC) codes and PAC codes. We show that any pre-transformed monomial code can be transformed into a parity-check monomial code with the same codewords, and give an explicit algorithm for this transformation. We further prove that for certain monomial codes, the minimum weight is invariant under pre-transformation, but specific pre-transformation matrices can be constructed to reduce the number of minimum-weight codewords. These results offer theoretical support for the success of various heuristics, e.g., PAC codes attain dispersion bound, and provide guidance for designing short codes.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 30, 2021•1 citation

Algebraic Properties of PAC Codes

Vlad Drăgoi, Mohammad Rowshan

We analyze polarization-adjusted convolutional codes using the algebraic representation of polar and Reed-Muller codes. We define a large class of codes, called generalized polynomial polar codes which include PAC codes and Reverse PAC codes. We derive structural properties of generalized polynomial polar codes, such as duality, minimum distance. We also deduce some structural limits in terms of number of minimum weight codewords, and dimension of monomial sub-code.

arXiv:2601.10262•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•1 citation

A Deterministic Algorithm for Computing the Weight Distribution of Polar Code

Hanwen Yao, Arman Fazeli, Alexander Vardy

In this work, we present a deterministic algorithm for computing the entire weight distribution of polar codes. As the first step, we derive an efficient recursive procedure to compute the weight distribution that arises in successive cancellation decoding of polar codes along any decoding path. This solves the open problem recently posed by Polyanskaya, Davletshin, and Polyanskii. Using this recursive procedure, at code lengthn, we can compute the weight distribution of anypolar cosetsin timeO(n2). We show that any polar code can be represented as a disjoint union of such polar cosets; moreover, this representation extends to polar codes with dynamically frozen bits. However, the number of polar cosets in such representation scales exponentially with a parameter introduced herein, which we call themixing factor. To upper bound the complexity of our algorithm for polar codes being decreasing monomial codes, we study the range of their mixing factors. We prove that among all decreasing monomial codes with rates at most 1/2, self-dual Reed-Muller codes have the largest mixing factors. To further reduce the complexity of our algorithm, we make use of the fact that, as decreasing monomial codes, polar codes have a large automorphism group. That automorphism group includes the block lower-triangular affine group (BLTA), which in turn contains the lower-triangular affine group (LTA). We prove that a subgroup of LTA acts transitively on certain subsets of decreasing monomial codes, thereby drastically reducing the number of polar cosets that we need to evaluate. This complexity reduction makes it possible to compute the weight distribution of polar codes at lengthn= 128.

IEEE Transactions on Information Theory•Feb 8, 2023•24 citations

Exponents of Hybrid Multi-Kernel Polar Codes

Lei Cheng, Lijun Zhang, Qiang Sun

Multi-kernel polar codes are constructed from the Kronecker product. For ordinary multi-kernels, constituent polarizing matrices of the same stage are identical. However, in a stage, applying different constituent matrices based on channel property can further improve performance. This family of polar codes is defined as hybrid multi-kernel polar codes. Exponents of hybrid multi-kernels are analyzed. The matrix of a hybrid multi-kernel is generated by a Kronecker-like product operation, and so are partial distances. All exponents of hybrid multi-kernels take values between the maximum and the minimum exponents among all constituent matrices. Exponents are related to the error probability of the original channel and exhibit a trend of convergence as block-length increases. The convergence rate is also related to the original error probability.

International Symposium on Turbo Codes and Iterative Information Processing•Dec 1, 2018•3 citations

Convolutional Polar Codes

Andrew J. Ferris, Christoph Hirche, David Poulin

Arikan's Polar codes attracted much attention as the first efficiently decodable and capacity achieving codes. Furthermore, Polar codes exhibit an exponentially decreasing block error probability with an asymptotic error exponent upper bounded by 1/2. Since their discovery, many attempts have been made to improve the error exponent and the finite block-length performance, while keeping the bloc-structured kernel. Recently, two of us introduced a new family of efficiently decodable error-correction codes based on a recently discovered efficiently-contractible tensor network family in quantum many-body physics, called branching MERA. These codes, called branching MERA codes, include Polar codes and also extend them in a non-trivial way by substituting the bloc-structured kernel by a convolutional structure. Here, we perform an in-depth study of a particular example that can be thought of as a direct extension to Arikan's Polar code, which we therefore name Convolutional Polar codes. We prove that these codes polarize and exponentially suppress the channel's error probability, with an asymptotic error exponent log_2(3)/2 which is provably better than for Polar codes under successive cancellation decoding. We also perform finite block-size numerical simulations which display improved error-correcting capability with only a minor impact on decoding complexity.

arXiv:1704.00715•Apr 3, 2017•17 citations
In this article, we introduce a new family of polar codes from evaluation codes, called polar decreasing monomial-Cartesian codes, and prove that families of polar codes with multiple kernels over certain symmetric channels can be viewed as polar decreasing monomial-Cartesian codes. This offers a unified treatment for such codes over any finite field. We define decreasing monomial-Cartesian codes as evaluation codes obtained from a set of monomials closed under divisibility over a Cartesian product and determine their parameters (length, dimension, and minimum distance). We show that the dual of a decreasing monomial-Cartesian code is monomially equivalent to a decreasing monomial-Cartesian code. Polar decreasing monomial-Cartesian codes are then obtained by utilizing decreasing monomial-Cartesian codes whose sets of monomials are closed with respect to a partial order. We prove that any sequence of invertible matrices over an arbitrary field satisfying certain conditions polarizes any channel that is symmetric over the field.
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.
Polar codes and Reed-Muller codes belong to a family of codes called monomial codes. In this work, we study pre-transformed monomial codes, which cover several constructions including parity-check (PC) codes and PAC codes. We show that any pre-transformed monomial code can be transformed into a parity-check monomial code with the same codewords, and give an explicit algorithm for this transformation. We further prove that for certain monomial codes, the minimum weight is invariant under pre-transformation, but specific pre-transformation matrices can be constructed to reduce the number of minimum-weight codewords. These results offer theoretical support for the success of various heuristics, e.g., PAC codes attain dispersion bound, and provide guidance for designing short codes.
In this work, we present a deterministic algorithm for computing the entire weight distribution of polar codes. As the first step, we derive an efficient recursive procedure to compute the weight distribution that arises in successive cancellation decoding of polar codes along any decoding path. This solves the open problem recently posed by Polyanskaya, Davletshin, and Polyanskii. Using this recursive procedure, at code lengthn, we can compute the weight distribution of anypolar cosetsin timeO(n2). We show that any polar code can be represented as a disjoint union of such polar cosets; moreover, this representation extends to polar codes with dynamically frozen bits. However, the number of polar cosets in such representation scales exponentially with a parameter introduced herein, which we call themixing factor. To upper bound the complexity of our algorithm for polar codes being decreasing monomial codes, we study the range of their mixing factors. We prove that among all decreasing monomial codes with rates at most 1/2, self-dual Reed-Muller codes have the largest mixing factors. To further reduce the complexity of our algorithm, we make use of the fact that, as decreasing monomial codes, polar codes have a large automorphism group. That automorphism group includes the block lower-triangular affine group (BLTA), which in turn contains the lower-triangular affine group (LTA). We prove that a subgroup of LTA acts transitively on certain subsets of decreasing monomial codes, thereby drastically reducing the number of polar cosets that we need to evaluate. This complexity reduction makes it possible to compute the weight distribution of polar codes at lengthn= 128.
Multi-kernel polar codes are constructed from the Kronecker product. For ordinary multi-kernels, constituent polarizing matrices of the same stage are identical. However, in a stage, applying different constituent matrices based on channel property can further improve performance. This family of polar codes is defined as hybrid multi-kernel polar codes. Exponents of hybrid multi-kernels are analyzed. The matrix of a hybrid multi-kernel is generated by a Kronecker-like product operation, and so are partial distances. All exponents of hybrid multi-kernels take values between the maximum and the minimum exponents among all constituent matrices. Exponents are related to the error probability of the original channel and exhibit a trend of convergence as block-length increases. The convergence rate is also related to the original error probability.
Arikan's Polar codes attracted much attention as the first efficiently decodable and capacity achieving codes. Furthermore, Polar codes exhibit an exponentially decreasing block error probability with an asymptotic error exponent upper bounded by 1/2. Since their discovery, many attempts have been made to improve the error exponent and the finite block-length performance, while keeping the bloc-structured kernel. Recently, two of us introduced a new family of efficiently decodable error-correction codes based on a recently discovered efficiently-contractible tensor network family in quantum many-body physics, called branching MERA. These codes, called branching MERA codes, include Polar codes and also extend them in a non-trivial way by substituting the bloc-structured kernel by a convolutional structure. Here, we perform an in-depth study of a particular example that can be thought of as a direct extension to Arikan's Polar code, which we therefore name Convolutional Polar codes. We prove that these codes polarize and exponentially suppress the channel's error probability, with an asymptotic error exponent log_2(3)/2 which is provably better than for Polar codes under successive cancellation decoding. We also perform finite block-size numerical simulations which display improved error-correcting capability with only a minor impact on decoding complexity.