Nonlinear codes outperform the best linear codes on the binary erasure channel

Po-Ning Chen, Hsuan Yin Lin, Stefan M. Moser

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

The exact value of the average error probability of an arbitrary code (linear or nonlinear) using maximum likelihood decoding is studied on binary erasure channels (BECs) with arbitrary erasure probability 0 < δ < 1. The family of the fair linear codes, which are equivalent to a concatenation of several Hadamard linear codes, is proven to perform better (in the sense of average error probability with respect to maximum-likelihood decoding) than all other linear codes for many values of the blocklength n and for a dimension k = 3. It is then noted that the family of fair linear codes and the family of fair nonlinear weak flip codes both maximize the minimum Hamming distance under certain blocklengths. However, the fair nonlinear weak flip codes actually outperform the fair linear codes, i.e., linearity and global optimality cannot be simultaneously achieved for the number of codewords being M = 23.

Original languageEnglish
Title of host publicationProceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1751-1755
Number of pages5
ISBN (Electronic)9781467377041
DOIs
StatePublished - 28 Sep 2015
EventIEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong
Duration: 14 Jun 201519 Jun 2015

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2015-June
ISSN (Print)2157-8095

Conference

ConferenceIEEE International Symposium on Information Theory, ISIT 2015
CountryHong Kong
CityHong Kong
Period14/06/1519/06/15

Keywords

  • Binary erasure channel
  • generalized Plotkin bound
  • optimal nonlinear channel coding
  • r-wise Hamming distance
  • weak flip codes

Fingerprint Dive into the research topics of 'Nonlinear codes outperform the best linear codes on the binary erasure channel'. Together they form a unique fingerprint.

Cite this