PaperlayerView exact revision on arXiv

Source-linked AI summary

Algebraic Properties of Polar Codes From a New Polynomial Formalism

Magali Bardet, Vlad Dragoi, Ayoub Otmani, Jean-Pierre Tillich

arXiv:1601.06215v2cs.IT

TL;DR

Polar and Reed–Muller codes share a monomial-evaluation formalism, but choosing polar generating monomials is channel dependent. The paper proves a channel-independent decreasing order for these monomials and derives large symmetry and efficient minimum-weight enumeration.

  • Problem

    Choosing generating monomials that optimize polar-code successive cancellation decoding is difficult and channel dependent.

  • Method

    The paper defines a nontrivial partial order on monomials and analyzes codes whose generating sets are decreasing under that order.

  • Results

    For every binary-input symmetric channel, polar codes are decreasing monomial codes whose permutation groups contain the lower triangular affine group, while minimum-weight codewords are organized into efficiently countable orbits.

  • Takeaways & Limitations

    The decreasing structure explains major algebraic properties of polar codes, including large permutation groups and convenient counting of minimum-weight codewords.

Abstract

from arXiv · show

Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attain 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 hard task and 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 fo a binary-input symmetric channel always form a decreasing set. This property turns out to have rather deep consequences on the structure of the polar code. Indeed, the permutation group of a decreasing monomial code contains a large 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.

I. INTRODUCTION

The paper identifies channel-independent algebraic structure in polar-code generating monomials and shows that decreasing monomial codes inherit large symmetry and tractable minimum-weight structure.

  • Motivation: Polar codes attain many information-theoretic limits with low-complexity successive cancellation decoding, while their generating monomials differ from Reed–Muller choices and depend on the channel.Both code families are evaluation codes of monomials, but Reed–Muller monomials are not generally suited to successive cancellation decoding.
  • Universal structure: For every binary-input symmetric channel, polar-code generating monomials form a decreasing set under a nontrivial partial order.A decreasing set contains every smaller monomial whenever it contains a given monomial.
  • Permutation group: Decreasing monomial codes have a very large permutation group containing the lower triangular affine group.For length 2^m, this subgroup has size 2^Θ(m^2), superpolynomial in code length, although it may be only one-transitive for polar codes.
  • Minimum-weight codewords: Minimum-weight codewords correspond to orbits containing evaluations of maximum-degree generating monomials, enabling efficient counting of minimum-weight codewords.The number of such orbits is small because every orbit contains a generating monomial of maximum degree.
  • Further properties: Decreasing monomial codes also remain decreasing under duality, can be weakly self-dual under a mild condition, and are closed under the star product.These properties support applications including quantum polar codes, decoding, secure multiparty computation, and cryptanalysis.
  • Consequences: Together, these properties clarify polar-code structure and explain both their large permutation groups and tractable minimum-weight enumeration.The same properties have also been used in attacks on McEliece systems based on polar codes.

II. REED-MULLER, MONOMIAL AND POLAR CODES

The section formulates Reed–Muller and polar codes as monomial evaluation codes, then defines polar-code monomial selection through channel-dependent bit-channel quality.

  • Reed–Muller codes: Reed–Muller codes of length 2^m are evaluation codes generated by monomials of degree at most r.Monomials are products of binary-exponent variables, and evaluation is taken over all points in F_2^m.
  • Monomial codes: A monomial code C(I) is generated by evaluations of a finite monomial set I, and its dimension equals |I|.The dimension result follows from linear independence of monomials and injectivity of the evaluation map.
  • Polar codes: Polar codes use selected rows of a Kronecker-power generator matrix, whose rows correspond to evaluations of all monomials.The selected subset determines the generating monomials, and the convention used only reorders code positions relative to the usual definition.
  • Channel-dependent selection: For a channel W, a dimension-k polar code selects the k monomials with the smallest Bhattacharyya parameters B(W^g).This selection identifies the k best bit-channels for successive cancellation decoding.
  • Channel-dependent selection: The associated channels are formed through the polar transform, with each monomial determining a sequence of minus and plus operations.The output alphabets of these synthesized channels grow exponentially in m, making ranking delicate despite available efficient methods.

III. DECREASING MONOMIAL CODES

The paper defines decreasing monomial codes through partial orders on monomials and shows that polar and Reed–Muller codes fit this framework. For polar codes, the generating set is decreasing under divisibility and, more strongly, under a finer order.

  • Polar codes and decreasing sets: A polar code is generated by monomials selected according to channel-dependent bit-channel quality, while its universal algebraic structure requires a channel-independent ordering.The generating monomials are chosen for the k smallest Bhattacharyya parameters among all monomials.
  • Polar codes and decreasing sets: Under the divisibility order f ⪯w g iff f divides g, every divisor of a generating monomial also belongs to the polar code’s generating set.This makes the set weakly decreasing and immediately includes the constant monomial 1 whenever the code has nonzero dimension.
  • The monomial orders: The finer order compares same-degree monomials coordinatewise and extends across degrees through divisibility.For monomials of equal degree, xi1⋯xis ⪯ xj1⋯xjs when iℓ ≤ jℓ for every ℓ; different degrees are connected through a divisor of the larger monomial.
  • Definitions: A set is decreasing when it contains every monomial below each of its elements, and the corresponding evaluation code is called a decreasing monomial code.The weak version uses only the divisibility order ⪯w.
  • Main structural result: Theorem 1 states that polar codes for binary-input symmetric channels are decreasing monomial codes under the finer partial order.Reed–Muller codes are also decreasing monomial codes, with generating monomials consisting of all monomials of degree at most r.

A. Proof of Proposition 4

The proof of weak decrease relies on channel degradation: ordered monomials induce ordered bit-channels, and Bhattacharyya parameters reverse this degradation order. This transfers channel ordering into inclusion of the polar code’s generating set.

  • Channel degradation: Channel degradation is defined by post-processing: W′ is degraded from W when W′ = W″ ◦ W for some memoryless channel W″.The degradation relation is transitive, and degraded channels have no smaller Bhattacharyya parameter than the original channel.
  • Channel degradation: For binary-input symmetric W, W is degraded from W+ and W− is degraded from W.The first relation follows by discarding components of W+; the second is constructed using a randomized second channel use and the symmetry involution π.
  • The degradation construction: The constructed channel satisfies W″ ◦ W = W−, as verified by averaging over the auxiliary bit and using symmetry of W.The transition probability becomes 1/2 {W(y1|b)W(y2|x = 0) + W(y1|1 ⊕ b)W(y2|x = 1)}.
  • Ordering bit-channels: Proposition 5 establishes that f ⪯w g implies the corresponding bit-channel for g is degraded relative to that for f.The proof proceeds by induction on the number of variables, using degradation lemmas for the polar transforms.
  • Conclusion: Because degradation reverses Bhattacharyya ordering, if g belongs to the selected set then every f with f ⪯w g also belongs to it.Applying the Bhattacharyya inequality to the ordered bit-channels yields the defining-set inclusion directly.

B. Proof of Theorem 1

The proof of the finer order decomposes monomial comparisons into local index shifts and uses degradation relations between the associated bit-channels. Induction then establishes the full ordering needed for Theorem 1.

  • Bit-channel model: The proof models each bit-channel W^f through randomized inputs, linear encoding by G_m, transmission through W, and disclosure of selected auxiliary bits.The output consists of the received vector y together with auxiliary entries indexed by monomials larger than f.
  • Bit-channel transformations: A cyclic permutation of monomial indices, followed by reordering and erasing outputs, converts one modeled bit-channel into another.This construction underlies the degradation relations used for local comparisons.
  • Local comparisons: Lemma 6 handles local comparisons between same-degree monomials whose differing index blocks are consecutive shifts.The general case extends this comparison when the monomials agree outside the shifted interval.
  • Inductive ordering: Lemma 7 extends the channel ordering to any same-degree pair f ⪯ g by induction on the number of variables.The induction identifies the first differing index, groups a maximal shifted block, applies the local lemma, and then invokes the induction hypothesis.
  • Proof of Theorem 1: Theorem 1 follows by reducing different-degree comparisons to a same-degree comparison with a divisor g* of g, then combining the resulting degradation with Proposition 4.This proves that whenever g is selected and f ⪯ g, f is selected as well.

IV. STRUCTURAL PROPERTIES OF DECREASING MONOMIAL CODES

The algebraic framework supports structural analysis of decreasing monomial codes, including their duals, minimum distances, and permutation groups.

  • Structural properties: The paper focuses on three structural properties of decreasing monomial codes: dual-code characterization, minimum-distance estimation, and a large permutation-group subgroup.These properties are presented as consequences of the preceding algebraic formalism.

A. Duality

For a decreasing monomial code, taking multiplicative complements preserves the relevant order structure and yields a decreasing dual code. Under a complement-exclusion condition, the code is weakly self-dual; polar codes commonly satisfy this condition at rates below one-half.

  • Dual-code structure: Multiplicative complements reverse the monomial order: f ⪯ g if and only if ˇf ⪰ ˇg.This order reversal supports the complement-based characterization of the dual generating set.
  • Dual-code structure: The dual construction follows by showing that the complement of the complemented generating set is decreasing and its evaluation code lies in the original code's dual.The proof uses the decreasing-set property and the complement relation between products of monomials.
  • Dual-code structure: The dual of a decreasing monomial code is itself a decreasing monomial code.Its generating set is described using the complement of the original decreasing set.
  • Weak self-duality: A decreasing monomial code is weakly self-dual exactly when no generating monomial belongs to the complemented generating set, under the stated dimension condition.The condition is |I| ≤ 2^(m−1).
  • Weak self-duality: Polar codes of rate sufficiently smaller than 1/2 generally satisfy the weak-self-duality assumption, while above 1/2 their duals do.The paper relates this pattern to the polarization process used to select polar-code monomials.

B. Minimum Distance of Decreasing Monomial Codes

The minimum distance of a decreasing monomial code is determined by the largest initial consecutive monomial contained in its generating set. Related index parameters also determine corresponding properties of the dual code.

  • Parameters: For a decreasing monomial code C(I), r+ is the largest r such that x0 · · · x_{r−1} belongs to I.Equivalently, r− is defined through the largest suffix monomial x_{m−r} · · · x_{m−1} in I.
  • Minimum distance: The parameters r− and r+ connect membership of extremal monomials with minimum-distance properties of a decreasing monomial code and its dual.This provides a compact algebraic way to estimate distance from the generating set.
  • Minimum distance: The minimum distance of C(I) is 2^(m−r+(C(I))).The same proposition gives equalities relating r− and r+ for the dual code.

C. Permutation Group

Although general affine transformations can take a monomial code outside the monomial-code class, decreasing monomial codes retain a large permutation subgroup. The lower triangular affine group preserves their evaluation codes.

  • Motivation: Affine permutations may transform a monomial code into a polynomial code rather than another monomial code.This motivates restricting attention to decreasing monomial codes when seeking a large permutation group.
  • Lower triangular affine group: The lower triangular affine group consists of transformations x ↦ Ax+b with A lower triangular and diagonal entries equal to 1.The group is denoted LTA(m, 2).
  • Invariance: The permutation group of every decreasing monomial code in m variables contains LTA(m, 2).Thus the code has a large explicitly identified subgroup of coordinate permutations.
  • Invariance: For a decreasing generating set, substituting lower triangular affine variables produces only monomials that remain in the generating set.The decreasing property ensures the resulting products indexed by subsets stay inside I.
  • Scope: The paper notes that the full permutation group of decreasing monomial codes remains an open question.The result identifies a large subgroup, not necessarily the complete permutation group.

V. MINIMUM WEIGHT CODEWORDS

The paper analyzes minimum-weight codewords through lower triangular affine orbits of evaluated monomials. Young diagrams provide a combinatorial representation of monomials and support orbit counting.

  • Orbit structure: The orbit of a monomial g consists of its transformed polynomials under LTA(m, 2).For orbit counting, the stabilizer subgroup LTA(m, 2)_g is introduced.
  • Orbit structure: Minimum-weight codewords are organized by the action of the lower triangular affine group on evaluated generating monomials.The orbit structure gives a convenient description of minimal codewords.
  • Orbit counting: The orbit size equals the size of the stabilizer-related group action, with a bijection between orbit elements and admissible pairs (A,b).This reduces counting orbit elements to counting the corresponding lower triangular matrices and translation vectors.
  • Young-diagram representation: Monomials of degree d in m variables are in bijection with Young diagrams inside a d × (m−d) grid.The diagram is obtained from the indices of the variables in the monomial.
  • Young-diagram representation: For g=x1x4 with m=5, the associated partition is (3,1), and the example gives |O_{x1x4}| = 2^6.The count comes from 2^4 admissible matrices and 2^2 translation vectors.
  • Orbit counting: The orbit cardinality is determined from the associated Ferrers diagram and its size, with degree-one monomial orbits providing a simpler special case.Higher-degree cases are harder because the stabilizer need not be trivial.

B. The minimum weight codewords of a decreasing monomial code.

For a decreasing monomial code, minimum-weight codewords are exactly the disjoint LTA orbits of evaluations of maximal-degree generating monomials, yielding a counting formula.

  • Each minimum-weight codeword belongs to the orbit of an evaluation of a maximal-degree monomial in the generating set.The argument establishes both inclusions between the minimum-weight codewords and the union of these orbits.
  • Minimum-weight codewords are evaluations of products of r+ independent linear forms, each having weight 2^(m−r+).Products with repeated maximal variables can be rewritten into equivalent products with distinct maximal variables.
  • Distinct monomials have disjoint LTA orbits, so the orbit decomposition supports an exact count of minimum-weight codewords.The disjointness follows because comparable monomials retain distinguishing terms under the group action, with the same conclusion for incomparable monomials.
  • Theorem 3 gives the number of minimum-weight codewords in a decreasing monomial code from these orbit contributions.Its proof invokes the orbit characterization and orbit disjointness.
  • For Reed–Muller codes, the corresponding count is expressed through a Gaussian binomial coefficient.The coefficient counts r-dimensional subspaces of F_2^m, equivalently rank-r matrices in reduced echelon form; Young diagrams provide the combinatorial identity.
Loading 1601.06215v2…