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.

Keywords

Binary erasure channel, maximum likelihood decoding, r-wise
Hamming distance, weak flip codes.

-||-   _|_ _|_     /    __|__   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:42 CET 2020