Abstract
We present an extension of the pairwise Hamming distance, the \(r\)-wise Hamming distance, and show that it can
be used to fully characterize the maximum-likelihood decoding (MLD) error of an arbitrary code used over the binary
erasure channel (BEC). Based on these insights, we present a new design criterion for a code: the minimum
\(r\)-wise Hamming distance. We prove that, for every \(r\geq 2\), the class of fair weak flip codes
achieves the largest minimum \(r\)-wise Hamming distance among all codes of equal size \(M\) and blocklength
\(n\). Thus, it is conjectured that the fair weak flip code is optimal in the sense of achieving the smallest MLD
error over the BEC. We confirm this conjecture for \(M\leq 4\) and all \(n\geq 1\). For a code size \(M=8\), we find
that the best (in the sense of smallest MLD error) linear code cannot achieve the largest minimum \(4\)-wise
Hamming distance and is thus strictly outperformed by the fair weak flip code over the BEC.
Keywords
Binary erasure channel, maximum likelihood decoding, r-wise Hamming distance, weak flip codes.