Abstract

An extension from the pairwise Hamming distance to the r-wise
Hamming distance is presented. It can be used to fully characterize
the maximum-likelihood decoding (MLD) error of an arbitrary code over
the binary erasure channel (BEC). By noting that good codes always
have large minimum r-wise Hamming distances for all r, a new
design criterion for a code is introduced: the minimum r-wise
Hamming distance. We then prove an upper bound for the minimum
r-wise Hamming distance of an arbitrary code, called the
generalized Plotkin bound, and provide a class of (nonlinear)
codes that achieve the bound for every r.

-||-   _|_ _|_     /    __|__   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: Tue Feb 4 13:50:44 CET 2020