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. A Revisitation of Low-Rate Bounds on the Reliability Function of Discrete Memoryless Channels for List Decoding
 
research article

A Revisitation of Low-Rate Bounds on the Reliability Function of Discrete Memoryless Channels for List Decoding

Bondaschi, Marco  
•
Dalai, Marco
May 1, 2022
Ieee Transactions On Information Theory

We revise the proof of low-rate upper bounds on the reliability function of discrete memoryless channels for ordinary and list-decoding schemes, in particular Berlekamp and Blinovsky's zero-rate bound, as well as Blahut's bound for low rates. The available proofs of the zero-rate bound devised by Berlekamp and Blinovsky are somehow complicated in that they contain in one form or another some "non-standard" procedures or computations. Here we follow Blinovsky's idea of using a Ramsey-theoretic result by Komlos, and we complement it with some missing steps to present a proof which is rigorous and easier to inspect. Furthermore, we show how these techniques can be used to fix an error that invalidated the proof of Blahut's low-rate bound, which is here presented in an extended form for list decoding and for general channels.

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

WOS:000784190500006

Author(s)
Bondaschi, Marco  
Dalai, Marco
Date Issued

2022-05-01

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC

Published in
Ieee Transactions On Information Theory
Volume

68

Issue

5

Start page

2829

End page

2838

Subjects

Computer Science, Information Systems

•

Engineering, Electrical & Electronic

•

Computer Science

•

Engineering

•

error exponents

•

list decoding

•

ramsey theory

•

zero error capacity

•

probability

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LINX  
Available on Infoscience
May 9, 2022
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/187632
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