An improved bound on the zero-error list-decoding capacity of the 4/3 channel

Abstract

We prove a new, improved upper bound on the size of codes C ⊆{1, 2, 3, 4} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> with the property that every four distinct codewords in C have a coordinate where they all differ. Specifically, we show that such a code has size at most 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">6n/19 +o(n)</sup> , or equivalently has rate bounded by 6/19 ≤ 0.3158 (measured in bits). This improves the previous best upper bound of 0.3512 due to (Arikan 1994), which in turn improved the 0.375 bound that followed from general bounds for perfect hashing due to (Fredman and Komlos, 1984) and (Korner and Marton, 1988). The context for this problem is two-fold: zero-error list decoding capacity, where such codes give a way to communicate with no error on the “4/3 channel” when list-of-3 decoding is employed, and perfect hashing, where such codes give a perfect hash family of size n mapping C to {1, 2, 3, 4}.