The r-wise Hamming Distance and its Operational Interpretation for Block Codes

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 >= 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 <= 4 and all n >= 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.