PaperlayerView exact revision on arXiv

Source-linked AI summary

From Polar to Reed-Muller Codes: a Technique to Improve the Finite-Length Performance

Marco Mondelli, S. Hamed Hassani, Rüdiger Urbanke

arXiv:1401.3127v3cs.ITmath.IT

TL;DR

Near capacity, polar codes may require large block lengths to achieve a target error probability. This paper introduces a family interpolating between polar and RM codes and reports finite-length gains from suitable members under low-complexity decoding. Numerical observations also show MAP error probability increasing with the interpolation parameter.

  • Problem

    Near capacity, polar codes require large block lengths to achieve a target error probability, and their BEC scaling exponent is approximately 3.627 versus 2 for random codes.

    Source: §I · p. 1

  • Method

    The paper varies α to form a code family between the original polar code at α=1 and an RM code at α=0.

    Source: §I · p. 2

  • Results

    Numerical observations show MAP error probability increasing with α, while suitable interpolating codes improve finite-length performance under low-complexity decoding on the BEC and BAWGNC.

    Source: §I · p. 2, §V · p. 7

  • Takeaways & Limitations

    Suitable codes from the family can significantly improve polar-code finite-length performance with low-complexity decoders such as SCL and BP.

    Source: §I · p. 2, A. General Construction of an… · p. 7

    MAP decoding is generally impractical because of its exponential complexity, motivating the use of low-complexity decoders for the reported gains.

    Source: §V · p. 7

Abstract

from arXiv · show

We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that "interpolates" between RM and polar codes, call this family ${\mathcal C}_{\rm inter} = \{C_{\alpha} : \alpha \in [0, 1]\}$, where $C_{\alpha} \big |_{\alpha = 1}$ is the original polar code, and $C_{\alpha} \big |_{\alpha = 0}$ is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of $\alpha$. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family ${\mathcal C}_{\rm inter}$ even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.

I. INTRODUCTION

The introduction frames polar codes’ large-block-length needs near capacity and the reported MAP advantage of RM codes as motivation for interpolation. It presents an RM-to-polar code family whose suitable members improve finite-length performance under practical decoders.

Motivation

  • At rates near capacity, polar codes require large block lengths to meet a target error probability; on the BEC their scaling exponent is approximately 3.627 versus 2 for random codes.The introduction distinguishes scaling exponent from error exponent: the former fixes error probability and tracks the gap to capacity with block length.Source: §I · p. 1
  • RM codes are reported to outperform polar codes under MAP decoding, despite poorer performance under successive and iterative decoding.Whether RM codes achieve capacity under MAP decoding for sufficiently symmetric channels remains open.Source: §I · p. 2

Contribution

  • The paper proposes C_inter, a family interpolating between polar and RM codes with the same block length and rate.The family ranges from the original polar code at α=1 to an RM code at α=0.Source: §I · p. 2
  • Numerical observations report that MAP error probability increases with α, while suitable family members improve finite-length performance under SCL and BP decoding.The simulations cover the BEC and BAWGNC; the authors state that the improvement could substantially reduce the scaling exponent.Source: §I · p. 2

II. FROM POLAR TO RM CODES: AN INTERPOLATION

Polar and RM codes select rows of the same generator matrix by different criteria: polar construction uses channel reliability, whereas RM construction uses row Hamming weight. The proposed family interpolates between these rules by designing for a scaled BEC and changing selected rows as α decreases.

Construction rules

  • For a fixed block length and rate, RM construction selects rows with the highest Hamming weights, a channel-independent rule, while polar construction selects rows with the lowest Bhattacharyya parameters for the channel.Both code families obtain their generator matrices by selecting rows from G_N.Source: §II · p. 2

Relation between constructions

  • As the BEC erasure probability tends to zero, the polar code designed for that channel becomes an RM code.The proof relates the ordering of synthetic-channel Bhattacharyya parameters at small erasure probability to row Hamming weights.Source: §II · pp. 2–3

Interpolating family

  • For transmission over BEC(ε), Cα is a polar code of block length N and rate R designed for BEC(αε); α=1 gives the polar code for W, while α→0 yields an RM code.The construction selects NR rows that minimize expression (3).Source: §II · pp. 2–3
  • As α decreases, successive generator matrices change one row at a time, with simulations showing that each new row has higher Hamming weight than the removed row.The accompanying heuristic says the polar rule depends on both the number and positions of 1s in an index, while the RM rule depends on their number.Source: §II · p. 3

III. IMPROVING THE FINITE-LENGTH PERFORMANCE OF POLAR CODES FOR THE BEC

For BEC transmission, MAP error probability across the interpolating family is reported to increase with α, making the RM endpoint the minimum-error choice in the plotted setting. The section evaluates this behavior alongside SC and low-complexity decoding schemes.

Evaluation setup

  • The BEC simulations examine interpolating codes under MAP and SC decoding and consider low-complexity alternatives including SCL and BP.The stated setup uses fixed block length and rate, with Monte Carlo trials.Source: §III · p. 3

MAP decoding

  • MAP error probability increases with α for all plotted ε values, so the RM code at α=0 achieves the minimum error probability.Figure 1 plots MAP error probability against α for four ε values.Source: §III · p. 3, Figure 1 · p. 3

A. Motivation: MAP Decoding

The section motivates MAP-based interpolation by noting RM codes’ stronger MAP performance than polar codes, then examines how MAP error varies across the interpolating family. It also connects the interpolation toward RM codes with a conjecture about capacity achievement on the BEC.

A. Motivation: MAP Decoding

B. SC Decoding

Under SC decoding, error probability decreases as α increases, favoring the polar-code endpoint. The section attributes this behavior to the polar choice minimizing a sum of selected synthetic-channel Bhattacharyya parameters.

B. SC Decoding

  • Across four erasure probabilities, SC error probability decreases as α increases for transmission over the BEC.Source: B. SC Decoding · p. 4
  • The best SC performance in the interpolation family occurs at α=1, the polar code.Source: B. SC Decoding · p. 4
  • The stated explanation is that the sum of selected synthetic-channel Bhattacharyya parameters is minimized at α=1.The passage describes the bound as tight.Source: B. SC Decoding · p. 4

C. Something Between the Two Extremes: List Decoding and Belief Propagation

The section compares SC, SCL, and BP decoding across the interpolating codes. Smaller α can lower MAP error, but SCL may require larger lists to approach it; selected codes also improve finite-length performance under SCL and BP.

C. Something Between the Two Extremes: List Decoding and Belief Propagation

IV. GENERALIZATION TO ANY BMSC

The paper extends the interpolation approach from the BEC to general BMS channels and analyzes transmission over a BAWGNC. Its reported BEC SCL results show improvement from reducing α, with the advantage clearer at a larger list size.

IV. GENERALIZATION TO ANY BMSC

  • The generalization section first proposes a construction for the interpolating family, then analyzes performance over a BAWGNC.The supplied BEC result is distinct from the stated BAWGNC analysis.Source: §IV · pp. 5–6
  • With L = 8, reducing α improves SCL performance over the original polar code; the advantage of smaller α is more evident at L = 32.Figure 5 uses the BEC, N = 2^10, and R = 0.5.Source: Figure 5 · p. 6, §IV · p. 6

A. General Construction of an Interpolating Family

For a BMSC, the construction interpolates by designing polar codes for a family of degraded channels between the original channel and a perfect channel. In the limit α → 0, the resulting code is RM; the reported decoding trends differ between MAP and SC.

A. General Construction of an Interpolating Family

  • For a BMSC W, the construction uses Wα = αW + (1 − α)Wopt, whose Bhattacharyya parameter is Zα = αZ.The channels in the family are ordered by degradation, from W to the perfect channel Wopt.Source: A. General Construction of an… · p. 6
  • As α → 0, the polar code designed for Wα becomes an RM code.The result applies to the stated BMSC construction.Source: A. General Construction of an… · p. 6
  • Numerical simulations show MAP error probability increasing with α, while SC achieves its optimal performance at α = 1.The SC result contrasts with the MAP trend across the interpolating family.Source: A. General Construction of an… · p. 7
  • For low-complexity decoders that approach MAP error probability, a suitable Cα significantly improves polar-code finite-length performance.For the BAWGNC, the interpolation family is constructed differently from the general BMSC construction.Source: A. General Construction of an… · pp. 6–7

B. Case Study: W = BAWGNC(σ2)

The BAWGNC case study defines codes for a noise-scaled channel and reports a performance gain over the original polar code using SCL decoding.

B. Case Study: W = BAWGNC(σ2)

  • The interpolating codes achieve a remarkable performance gain over the original polar code in the BAWGNC case study.The results are described as qualitatively similar to those for the BEC.Source: B. Case Study: W = BAWGNC(σ2) · p. 7
  • The simulations use fixed block length N = 211 and rate R = 0.5, with codes optimized for SNR = 2 dB.The setup uses σ2 = 0.6309 and M = 105 Monte Carlo trials.Source: B. Case Study: W = BAWGNC(σ2) · p. 7
  • For W = BAWGNC(σ2), Cα is designed for Wα = BAWGNC(ασ2); as α approaches 0, Cα becomes an RM code.The scaled channel tends to the perfect channel as α approaches 0.Source: B. Case Study: W = BAWGNC(σ2) · p. 7

V. CONCLUDING REMARKS

The paper modifies both the code and SC decoding through a fixed-length, fixed-rate family interpolating between polar and RM codes. Numerical results report gains under low-complexity decoding and an MAP-decoding comparison with random codes.

V. CONCLUDING REMARKS

  • The proposed fixed-length, fixed-rate family Cinter modifies the code jointly with SC decoding and interpolates between the original polar code and an RM code.The family is defined as Cinter = {Cα : α ∈ [0, 1]}.Source: §V · p. 7
  • For BEC transmission, sufficiently small α yields MAP error probability very close to that of random codes, which achieve a better scaling exponent than polar codes.The paper also reports significant benefits from interpolating-family codes under BP and SCL decoding on the BEC and BAWGNC.Source: §V · p. 7
  • At Pe = 10^-3, Figure 7 reports an improvement ≥0.5 dB over the original polar code under SCL decoding.The comparison is for BAWGNC transmission with block length N = 211 and rate R = 0.5.Source: Figure 7 · p. 7
Loading 1401.3127v3…