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. 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) among all linear or nonlinear
codes for the binary erasure channel (BEC) for many values of the
blocklength n and for \(M\leq 6\). For \(M > 6\), similar
optimality results are conjectured.
The results in this paper are founded on a new
powerful tool for the analysis and generation of block codes: the
column-wise approach to the codebook matrix.