Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Reed-Muller Codes Polarize
 
research article

Reed-Muller Codes Polarize

Abbe, Emmanuel  
•
Ye, Min
December 1, 2020
Ieee Transactions On Information Theory

Reed-Muller (RM) codes were introduced in 1954 and have long been conjectured to achieve Shannon's capacity on symmetric channels. The activity on this conjecture has recently been revived with the emergence of polar codes. RM codes and polar codes are generated by the same matrix G(m) =

[GRAPHICS]

(circle times m) but using different subset of rows. RM codes select simply rows having largest weights. Polar codes select instead rows having the largest conditional mutual information proceeding top to down in G(m); while this is a more elaborate and channel-dependent rule, the top-to-down ordering allows Arikan to show that the conditional mutual information polarizes, and this gives directly a capacity-achieving code on any symmetric channel. RM codes are yet to be proved to have such a property, despite the recent success for the erasure channel. In this article, we connect RM codes to polarization theory. We show that proceeding in the RM code ordering, i.e., not top-to-down but from the lightest to the heaviest rows in G(m), the conditional mutual information again polarizes. Here "polarization" means that almost all the conditional mutual information becomes either very close to 0 or very close to 1. Polarization itself is a necessary condition for RM codes to achieve capacity on symmetric channels while polarization together with a strong order on the conditional mutual information gives a sufficient condition, where strong order means that rows with larger weight always correspond to larger conditional mutual information. Although we are not able to prove the strong order, we establish a partial order on the conditional mutual information, which is a subset of the strong order. While the main results of this article-polarization together with the partial order-provide some advances on the capacity-achieving conjecture of RM codes, we emphasize that our results do not allow us to prove the conjecture.

  • Details
  • Metrics
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés