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. Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels
 
conference paper

Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels

Hassani, Hamed  
•
Kudekar, Shrinivas  
•
Ordentlich, Or
Show more
January 1, 2018
2018 Ieee International Symposium On Information Theory (Isit)
IEEE International Symposium on Information Theory (ISIT)

Consider a binary linear code of length N, minimum distance d(min), transmission over the binary erasure channel with parameter 0 < epsilon < 1 or the binary symmetric channel with parameter 0 < epsilon < 1/2, and block-MAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the block-MAP decoder transitions "quickly" from delta to 1-delta for any delta > 0 if the minimum distance is large. In particular the width of the transition is of order O(1/root d(min)). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as Theta(1/N1/2-kappa), for any kappa > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since Theta(1/N-1/2) is the smallest transition possible for any code, we speak of "almost" optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma.

  • Details
  • Metrics
Type
conference paper
DOI
10.1109/ISIT.2018.8437453
Web of Science ID

WOS:000448139300063

Author(s)
Hassani, Hamed  
Kudekar, Shrinivas  
Ordentlich, Or
Polyanskiy, Yury
Urbanke, Rudiger  
Date Issued

2018-01-01

Publisher

IEEE

Publisher place

New York

Published in
2018 Ieee International Symposium On Information Theory (Isit)
ISBN of the book

978-1-5386-4781-3

Series title/Series vol.

IEEE International Symposium on Information Theory

Start page

311

End page

315

Subjects

Computer Science, Information Systems

•

Engineering, Electrical & Electronic

•

Computer Science

•

Engineering

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LTHC  
ISC  
Event nameEvent placeEvent date
IEEE International Symposium on Information Theory (ISIT)

Vail, CO

Jun 17-22, 2018

Available on Infoscience
December 13, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/152311
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