An improved bound on the zero-error list-decoding capacity of the 4/3 channel
Open Access
- 1 June 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1658-1662
Abstract
We prove a new, improved upper bound on the size of codes C ⊆{1, 2, 3, 4} n 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 6n/19 +o(n) , 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}.Keywords
This publication has 9 references indexed in Scilit:
- An upper bound on the zero-error list-coding capacityIEEE Transactions on Information Theory, 1994
- A new upper bound on nonbinary block codesDiscrete Mathematics, 1990
- New Bounds for Perfect Hashing via Information TheoryEuropean Journal of Combinatorics, 1988
- Zero error capacity under list decodingIEEE Transactions on Information Theory, 1988
- Fredman–Komlós bounds and information theorySIAM Journal on Algebraic Discrete Methods, 1986
- On the Size of Separating Systems and Families of Perfect Hash FunctionsSIAM Journal on Algebraic Discrete Methods, 1984
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979
- An information-theoretic method in combinatorial theoryJournal of Combinatorial Theory, Series A, 1977
- The zero error capacity of a noisy channelIEEE Transactions on Information Theory, 1956