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. Conferences, Workshops, Symposiums, and Seminars
  4. Reed-Muller codes polarize
 
conference paper

Reed-Muller codes polarize

Abbe, Emmanuel  
•
Ye, Min
January 1, 2019
2019 Ieee 60Th Annual Symposium On Foundations Of Computer Science (Focs 2019)
60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

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 Gm = [1?] "' 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 Gm; while this is a more elaborate and channel-dependent rule, the top-to-down ordering allows Ankan 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 paper, 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 Gm, the conditional mutual information again polarizes. We further demonstrate that it does so faster than for polar codes. This implies that Gm contains another code, different than the polar code and called here the twin-RM code, that is provably capacityachieving on any symmetric channel. This gives in particular a necessary condition for RM codes to achieve capacity on symmetric channels. It further gives a sufficient condition if the rows with largest conditional mutual information correspond to the heaviest rows, i.e., if the twin-RM code is the RM code. We demonstrate here that the two codes are at least similar and give further evidence that they are indeed the same.

  • Details
  • Metrics
Type
conference paper
DOI
10.1109/FOCS.2019.00026
Web of Science ID

WOS:000510015300017

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

2019-01-01

Publisher

IEEE COMPUTER SOC

Publisher place

Los Alamitos

Published in
2019 Ieee 60Th Annual Symposium On Foundations Of Computer Science (Focs 2019)
ISBN of the book

978-1-7281-4952-3

Series title/Series vol.

Annual IEEE Symposium on Foundations of Computer Science

Start page

273

End page

286

Subjects

reed-muller codes

•

polar codes

•

shannon theory

•

capacity-achieving codes

•

capacity

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
MDS1  
Event nameEvent placeEvent date
60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

Baltimore, MD

Nov 09-12, 2019

Available on Infoscience
March 5, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/166987
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