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
Type
research article
DOI
10.1109/TIT.2020.3023487
Web of Science ID

WOS:000594905600001

Author(s)
Abbe, Emmanuel  
Ye, Min
Date Issued

2020-12-01

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC

Published in
Ieee Transactions On Information Theory
Volume

66

Issue

12

Start page

7311

End page

7332

Subjects

Computer Science, Information Systems

•

Engineering, Electrical & Electronic

•

Computer Science

•

Engineering

•

reed-muller codes

•

shannon capacity

•

polar codes

•

polarization

•

capacity-achieving codes

•

capacity

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
MDS1  
Available on Infoscience
June 19, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/179050
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