Abstract
This paper investigates fundamental properties of nonlinear
binary codes by looking at the codebook matrix not row-wise
(codewords), but column-wise. The family of weak flip
codes is presented and shown to contain many beautiful
properties. In particular the subfamily fair weak flip codes,
which goes back to 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 to an
arbitrary number of codewords. The fair weak flip codes are related
to binary nonlinear Hadamard codes.
Based on the column-wise approach to the codebook matrix, the
r-wise Hamming distance is introduced as a generalization
to the well-known and widely used (pairwise) Hamming distance. It is
shown that the minimum r-wise Hamming distance satisfies a
generalized r-wise Plotkin bound. The r-wise Hamming
distance structure of the nonlinear fair weak flip codes is analyzed
and shown to be superior to many codes. In particular, it is proven
that the fair weak flip codes achieve the r-wise Plotkin bound
with equality for all r.
In the second part of the paper, these insights are applied to a
binary erasure channel (BEC) with an arbitrary erasure
probability 0< delta <1. An exact formula for the average error
probability of an arbitrary (linear or nonlinear) code using maximum
likelihood decoding is derived and shown to be expressible using
only the r-wise Hamming distance structure of the code. For a
number of codewords M satisfying M <= 4 and an
arbitrary finite blocklength n, the globally optimal codes (in the
sense of minimizing the average error probability) are found. For
M=5 or M=6 and an arbitrary finite blocklength
n, the optimal codes are conjectured. For larger M,
observations regarding the optimal design are presented, e.g., that
good codes have a large r-wise Hamming distance structure for all
r. Numerical results validate our code design criteria and show
the superiority of our best found nonlinear weak flip codes compared
to the best linear codes.
Keywords
Binary erasure channel (BEC), finite blocklength, generalized Plotkin
bound, maximum likelihood (ML) decoder, minimum average error
probability, optimal nonlinear code design, 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: Tue Feb 4 13:50:44 CET 2020