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<\delta<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.