Abstract

A new family of nonlinear codes, called weak flip codes, is presented
and is shown to contain many beautiful properties. In particular, the
subfamily of fair weak flip codes can be seen as a generalization of
linear codes, i.e., they possess some quasi-linear properties.
Different from linear codes that only exist for a number of
codewords M being an integer-power of 2, the fair weak flip code
can be defined for an arbitrary M. It is then noted that the fair weak
flip codes are related to binary nonlinear Hadamard codes: both code
families maximize the minimum Hamming distance and meet the Plotkin
bound. However, while the binary nonlinear Hadamard codes have only
been shown to possess good Hamming-distance properties, the fair weak
flip codes are proven to be globally optimal — in the sense of
minimizing the error probability, and under the assumption that the
optimal codes can be constructed recursively in blocklength n — among
all linear or nonlinear codes for the binary erasure channel (BEC) for
many values of the blocklength n and for M ≤ 6. For M > 6, similar
optimality results are conjectured.

Moreover, some applications to known bounds on the error probability
for a finite blocklength is introduced for comparison, while as
blocklength n going to infinity, the error exponent of a BEC for a
fixed number of codewords is also discussed.

The results in this work are founded upon a new powerful tool for the
analysis and generation of block codes: the column-wise approach to
the codebook matrix.


Keywords

Binary erasure channel (BEC), channel capacity, finite blocklength,
flip codes, maximum likelihood (ML) decoder, minimum average error
probability, optimal codes, 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: Sat Jun 1 09:32:14 UTC+8 2013