PaperlayerView exact revision on arXiv

Source-linked AI summary

Reed-Muller Codes Achieve Capacity on Erasure Channels

Santhosh Kumar, Henry D. Pfister

arXiv:1505.05123v2cs.IT

TL;DR

The paper addresses whether deterministic linear-code sequences can achieve capacity on erasure channels without relying on precise code structure. It uses EXIT-function area arguments and sharp thresholds for monotone Boolean functions to show that double transitivity suffices, yielding capacity results for Reed–Muller and related code families.

  • Problem

    The paper investigates capacity achievement for sequences of binary linear codes on the binary erasure channel under maximum-aposteriori decoding.

  • Method

    The proof combines sharp-threshold results for monotone Boolean functions with the area theorem for extrinsic information transfer functions, exploiting code symmetry rather than precise code structure.

  • Results

    Any sequence with strictly increasing blocklengths, rates converging to r ∈(0, 1), and doubly transitive permutation groups achieves capacity under MAP decoding; this includes Reed–Muller codes and related families.

  • Takeaways & Limitations

    The result shows that linearity and double transitivity alone can guarantee capacity for binary and q-ary erasure-channel code sequences, including affine-invariant and extended primitive narrow-sense BCH codes.

Abstract

from arXiv · show

This paper introduces a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes, this method requires only that the codes are highly symmetric. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge to a number between 0 and 1, and the permutation group of each code is doubly transitive. This also provides a rare example in information theory where symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed-Muller codes with increasing blocklength achieves capacity if its code rate converges to a number between 0 and 1. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to affine-invariant codes and, thus, to all extended primitive narrow-sense BCH codes. The primary tools used in the proof are the sharp threshold property for monotone boolean functions and the area theorem for extrinsic information transfer functions.

I. INTRODUCTION

The paper proves that doubly transitive symmetry suffices for capacity achievement on erasure channels under MAP decoding, with Reed-Muller codes as a key consequence. It uses EXIT functions, their area theorem, and sharp-threshold results for monotone Boolean functions.

  • Main result: The primary theorem covers strictly increasing blocklengths, rates converging to r∈(0,1), and doubly transitive permutation groups.Under these conditions, a linear-code sequence achieves capacity on a memoryless erasure channel under MAP decoding.
  • Main result: Binary Reed-Muller codes achieve capacity on the BEC under block-MAP decoding.The analysis primarily studies bit erasure under bit-MAP decoding and extends to block erasure in relevant cases.
  • Extensions: The result extends to q-ary linear codes under symbol-MAP decoding, including Generalized Reed-Muller and extended primitive narrow-sense BCH codes.Affine-invariant codes qualify because their permutation groups contain a doubly transitive affine linear group.
  • Motivation: Earlier Reed-Muller capacity results covered rates approaching 0 or 1, leaving rates bounded away from both endpoints unresolved.The present theorem addresses the intermediate-rate regime under the stated symmetry and blocklength conditions.
  • Proof strategy: The proof exploits isoperimetric inequalities for monotone Boolean functions and the EXIT area theorem rather than a code’s precise structure.The area theorem supplies the limiting transition point of the EXIT function.

B. MAP EXIT Functions

This section defines MAP EXIT functions through conditional entropies and connects them to erasure probabilities and monotone recovery sets. Their symmetry, monotonicity, continuity, and area properties support the later threshold analysis.

  • Definitions: The EXIT function is directly related to bit erasure probability under bit-MAP decoding.The relevant erasure patterns are those preventing indirect recovery of the target bit.
  • Recovery sets: The recovery-failure sets and pivotal boundaries encode which erasure patterns make a bit unrecoverable or make another bit decisive.These sets are used to express EXIT functions and their derivatives.
  • Properties: The area under the average EXIT function equals the code rate.This area theorem is central to locating the transition required for capacity achievement.
  • Properties: Each bit EXIT function, and therefore the average EXIT function, is continuous and strictly increasing on [0,1], with endpoint values 0 and 1.The functions are non-constant polynomials under the paper’s code assumptions.

C. Permutations of Linear Codes

The paper formalizes code permutation groups and shows how transitivity makes EXIT functions symmetric across bits. Double transitivity further equalizes pivotal-boundary behavior, enabling the sharp-threshold argument.

  • Permutation groups: A code’s permutation group consists of bit permutations that preserve its set of codewords.For linear codes, this group is related to weight-preserving linear transformations.
  • Group properties: A doubly transitive group can fix one bit while mapping any other distinct bit to a third bit.This is stronger than ordinary transitivity, which only maps arbitrary individual positions.
  • EXIT symmetry: Transitivity induces a weight-preserving bijection between the recovery-failure sets associated with different bits.Consequently, all bit EXIT functions coincide with the average EXIT function.
  • EXIT symmetry: Double transitivity similarly relates the pivotal boundaries for different non-target bit positions.The resulting symmetry is used to control the derivatives needed in the threshold analysis.

D. Capacity-Achieving Codes

Capacity achievement is characterized by a sharp transition of the average EXIT function at the channel-capacity threshold. The paper links vanishing transition width to capacity and uses this framework for Reed-Muller sequences.

  • Capacity criterion: A code sequence with rates converging to r is capacity achieving under bit-MAP decoding when its average bit-erasure probability vanishes for p<1−r.The corresponding block-MAP definition uses block-erasure probabilities in the same sub-capacity region.
  • Reed-Muller application: The average EXIT transition width decreases with increasing blocklength for the rate-1/2 Reed-Muller codes illustrated in Figure 1.If this width converges to zero, the associated Reed-Muller sequence achieves capacity.
  • Capacity criterion: Capacity achievement is equivalent to the average EXIT function converging to 0 below 1−r and to 1 above 1−r.Thus, the EXIT curve must undergo a sharp transition at the capacity threshold.
  • Technical framework: The inverse of the average EXIT function is well-defined because the function is continuous and strictly increasing.This inverse provides a convenient parametrization for the threshold analysis.
  • Proof strategy: The EXIT area theorem fixes the limiting transition point, making sharp-threshold results sufficient to establish capacity.Determining a threshold’s precise location is generally difficult without such prior information.

III. SHARP THRESHOLDS FOR MONOTONE BOOLEAN FUNCTIONS VIA ISOPERIMETRIC INEQUALITIES

The paper connects capacity-achieving erasure decoding to sharp threshold behavior of monotone Boolean functions. Symmetry equalizes influences, enabling doubly transitive code sequences to achieve capacity under bit-MAP decoding and, with additional conditions, block-MAP decoding.

  • Isoperimetric inequalities: Monotone-set threshold inequalities relate the derivative of µ_p(Ω) to the set boundary and total influence.The Margulis-Russo lemma characterizes the derivative through boundary structure, while influence inequalities yield narrow transitions.
  • Symmetry: Sufficient symmetry can force equal influences and produce sharp threshold behavior without detailed knowledge of the monotone set.The paper uses this principle because doubly transitive code permutation groups impose the required influence symmetry.
  • Capacity result: Any code sequence with increasing blocklengths, rates converging to r ∈(0, 1), and doubly transitive permutation groups achieves BEC capacity under bit-MAP decoding.The result is stated for linear codes and follows by combining influence symmetry with EXIT-function arguments.
  • Block-MAP extension: Block-MAP capacity follows when the EXIT transition is sufficiently sharp, either through a suitable minimum-distance condition or stronger symmetry inequalities.Theorem 18 uses rapidly growing minimum distance, whereas Theorem 19 avoids that requirement when the transition-width parameter diverges.

A. Affine-Invariant Codes

Affine-invariant codes contain affine-group symmetries that make their permutation groups doubly transitive. Consequently, increasing-length sequences with rates converging inside (0, 1) achieve erasure-channel capacity, including Reed-Muller and extended primitive narrow-sense BCH codes.

  • Affine invariance: An affine-invariant code has a permutation group containing the affine transformations π_β,γ induced by field scaling and translation.The transformations form a group under composition when β ≠ 0.
  • Double transitivity: Affine-invariant code permutation groups are doubly transitive because suitable β and γ can fix one coordinate while mapping another to any third coordinate.This supplies the symmetry hypothesis needed by the general capacity theorem.
  • q-ary extension: The same capacity conclusions extend to affine-invariant F_q-linear codes over q-ary erasure channels under symbol-MAP decoding.Generalized Reed-Muller and extended primitive narrow-sense BCH codes are identified as examples.
  • Reed-Muller codes: RM(v, m) is a binary linear code of length N = 2^m whose codewords are evaluations of degree-at-most-v polynomials.Its minimum distance is 2^(m−v), which can be too small for some block-MAP arguments.
  • Reed-Muller codes: The permutation group of RM(v, m) is doubly transitive.This is established by constructing invertible linear transformations that map any ordered pair of distinct coordinates to another suitable pair.

C. Bose-Chaudhuri-Hocquengham Codes

The section establishes capacity results for extended BCH and BCH codes by combining affine-invariance, double transitivity, and EXIT-function arguments. It also identifies a limitation for BCH block-erasure analysis and records the first capacity-achieving binary cyclic-code sequences.

  • Primitive narrow-sense BCH codes have length 2^m−1, designed distance v+1, and minimum distance at least v+1.
  • For every rate r ∈(0, 1), parameters v_m can be selected so BCH and extended BCH rates converge to r.
  • Extended BCH codes are affine-invariant, so their permutation groups are doubly transitive, enabling the paper’s symmetry-based capacity argument.
  • For every r ∈(0, 1), a sequence of extended BCH codes achieves BEC capacity under bit-MAP decoding.
  • The affine-semi-linear symmetry of extended BCH codes does not provide enough factors for the paper’s block-erasure analysis, unlike the GL(m, F2) symmetry available for Reed-Muller codes.
  • For every r ∈(0, 1), extended BCH codes achieve BEC capacity under block-MAP decoding, while puncturing yields BCH sequences achieving it under both decoding modes.
  • The authors state that this gives the first proof of capacity-achieving sequences among binary cyclic codes.

A. Comparison with the Work of Tillich and Z´emor

The section explains why earlier sharp-threshold approaches do not directly suffice and develops conditions under which symmetry and distance support capacity on the BEC. It also states limitations and open directions for extending the method.

  • A. Comparison with the Work of Tillich and Z´emor: A linear-distance LDPC ensemble can have minimum distance growing linearly while its EXIT function remains bounded away from a sharp threshold.
  • A. Comparison with the Work of Tillich and Z´emor: The earlier approach fails to extend automatically to EXIT-function sharp thresholds because the required pivotality argument breaks down.
  • A. Comparison with the Work of Tillich and Z´emor: Transitivity alone is insufficient: bounded minimum distance prevents capacity achievement, and bounded minimum dual distance creates an analogous obstruction.
  • B. Conditions of Theorem 17: The paper identifies diverging minimum and minimum-dual distances as necessary conditions in its conjecture for transitive code sequences.
  • B. Conditions of Theorem 17: Under the stated distance condition, the sequence achieves BEC capacity under bit-MAP decoding.
  • B. Conditions of Theorem 17: For reducible transitive codes, each irreducible component inherits the relevant transitivity, distance, and common EXIT-function conditions.

C. Beyond the Erasure Channel

The paper extends its symmetry-based capacity results beyond binary erasure channels and analyzes Reed–Muller rate regimes. It also identifies implications for symmetric channels and open directions where the method does not directly apply.

  • The approach has implications for Reed–Muller decoding on the binary symmetric channel through reductions from correctable erasure patterns.The cited result relates correction of an error pattern for RM(m −(2t + 2), m) to an erasure pattern with the same support for RM(m −(t + 1), m).
  • Extending the approach to binary-input memoryless symmetric channels remains open because generalized EXIT analysis leads to functions that are neither boolean nor monotonic.
  • Affine-invariant Fq-linear codes achieve capacity because their permutation groups are doubly transitive.
  • For Reed–Muller codes with rates tending to zero, the paper proves bit-MAP capacity under the condition rm log(Nm) →∞.The resulting asymptotic regime is non-overlapping with the earlier condition rm = O(Nm^-κ).
  • The method extends to Fq-linear codes on q-ary erasure channels under symbol-MAP decoding.
  • Generalized Reed–Muller codes and extended primitive narrow-sense BCH codes achieve capacity on q-ary erasure channels under block-MAP decoding.

APPENDIX I PROOF OF PROPOSITION 10

The appendix proves Proposition 10 by relating EXIT-function transition widths to inverse-function integrals and the area theorem. This establishes equivalent threshold statements centered at erasure probability 1 − r.

  • The EXIT area theorem and monotonicity constrain the limiting transition point of h^(n)(p) to 1 − r.
  • The proof bounds the interval between inverse-function levels pε1 and pε2 by integrating the derivative of a transformed function.The argument treats cases according to whether the inverse levels lie inside or across the interval [a,b].
  • Lemma 29 converts the derivative bound into an upper bound on the transition width pε2 − pε1.
  • Applying the lemma with ε2 = 1/2 and ε1 = h−1(δ) yields the desired bound on h(δ).

A. Proof of Theorem 18

The proof of Theorem 18 uses inverse EXIT functions, transition-width control, and block-versus-bit erasure bounds. Under the stated asymptotic conditions, it concludes capacity under block-MAP decoding.

  • The transition point approaches 1 − r after applying Proposition 10’s threshold statement to the inverse EXIT function.
  • The block erasure probability is bounded using the bit erasure probability and the code’s minimum distance.
  • The sequence {Cn} is therefore capacity achieving on the BEC under block-MAP decoding.
  • The inverse EXIT-function transition width vanishes when the relevant endpoint conditions and wn log Nn →∞ hold.
Loading 1505.05123v2…