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: Theory and Algorithms
 
research article

Reed-Muller Codes: Theory and Algorithms

Abbe, Emmanuel  
•
Shpilka, Amir
•
Ye, Min  
June 1, 2021
Ieee Transactions On Information Theory

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems.

  • Details
  • Metrics
Type
research article
DOI
10.1109/TIT.2020.3004749
Web of Science ID

WOS:000652795200005

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

2021-06-01

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC

Published in
Ieee Transactions On Information Theory
Volume

67

Issue

6

Start page

3251

End page

3277

Subjects

Computer Science, Information Systems

•

Engineering, Electrical & Electronic

•

Computer Science

•

Engineering

•

reed-muller codes

•

shannon capacity

•

weight enumerator

•

decoding algorithms

•

polarization

•

polar

•

variables

•

capacity

•

weights

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/179129
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