TY - GEN
T1 - Nonlinear codes outperform the best linear codes on the binary erasure channel
AU - Chen, Po-Ning
AU - Lin, Hsuan Yin
AU - Moser, Stefan M.
PY - 2015/9/28
Y1 - 2015/9/28
N2 - 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.
AB - 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.
KW - Binary erasure channel
KW - generalized Plotkin bound
KW - optimal nonlinear channel coding
KW - r-wise Hamming distance
KW - weak flip codes
UR - http://www.scopus.com/inward/record.url?scp=84969819960&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2015.7282756
DO - 10.1109/ISIT.2015.7282756
M3 - Conference contribution
AN - SCOPUS:84969819960
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1751
EP - 1755
BT - Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - IEEE International Symposium on Information Theory, ISIT 2015
Y2 - 14 June 2015 through 19 June 2015
ER -