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 = 2^3.

Keywords

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

-||-   _|_ _|_     /    __|__   Stefan M. Moser
[-]     --__|__   /__\    /__   Senior Scientist, ETH Zurich, Switzerland
_|_     -- --|-    _     /  /   Adjunct Professor, National Yang Ming Chiao Tung University, Taiwan
/ \     []  \|    |_|   / \/    Web: https://moser-isi.ethz.ch/

Last modified: Thu Apr 9 10:30:54 UTC+8 2015