  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. Based on the column-wise
approach, the $r$-wise Hamming distance is introduced as a generalization to
the 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. An exact
formula for the average error probability of an arbitrary 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\leq4$ and an arbitrary blocklength $n$, the globally optimal codes (in the
sense of minimizing the average error probability) are found. For $M=5,6$ and
an arbitrary 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.
