Abstract
Based on a new way of designing codes using codebook columns, a family
of nonlinear codes, called weak flip codes, is presented and shown to
contain many beautiful properties. In particular the subfamily fair
weak flip codes, which goes back to definitions by Berlekamp,
Gallager, and Shannon and which was shown to achieve the error
exponent with a fixed number of codewords M, can be seen as a
generalization of linear codes. The fair weak flip codes are related
to binary nonlinear Hadamard codes.
The exact formula of the average error probability of an arbitrary
code (linear or nonlinear) using maximum likelihood decoding is
provided on binary erasure channels (BECs) with arbitrary erasure
probability 0 < δ < 1. An extension of pairwise Hamming distance, the
r-wise generalized Hamming distance, is rediscovered and found
to be a key to the understanding of the codes’ performance. A
generalization of the Plotkin bound for r-wise generalized Hamming
distance then is purposed for arbitrary binary codes. It is then noted
that the family of fair linear codes, which is equivalent to a
concatenation of several Hadamard linear codes, maximize the minimum
pairwise Hamming distance under certain blocklengths, and the family
of fair weak flip codes can be shown to be the generalized Plotkin
Bound achieving codes.
For the performance analysis of BEC, the globally optimal codes (in
the sense of minimizing the average error probability) for an
arbitrary finite blocklength are given with a number of codewords M
satisfying M ≤ 4. For M ≥ 5, similar global optimality are conjectured
for the fair codes and weak flip codes. It is also proven that the
fair linear codes is actually strictly suboptimal among all codes for
many values of the blocklength n with M = 8.
Keywords
Binary erasure channel (BEC), r-wise generalized Hamming
distance, finite blocklength, weak flip codes, maximum likelihood (ML)
decoder, minimum average error probability, generalized Plotkin bound
-||- _|_ _|_ / __|__ 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: Fri May 27 08:18:35 UTC+8 2016