An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel
| Autor: | Jaikumar Radhakrishnan, Venkatesan Guruswami Carnegie, Marco Dalai |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Standards
zero-error capacity decoding perfect hash family Noise measurement Perfect hashing List decoding Context (language use) 0102 computer and information sciences 02 engineering and technology Library and Information Sciences 01 natural sciences Upper and lower bounds Combinatorics Channel capacity zero-error list-decoding capacity Simple (abstract algebra) 0202 electrical engineering electronic engineering information engineering 0101 mathematics Hamming space Zero error Mathematics Discrete mathematics Bipartite graph Decoding Upper bound 010102 general mathematics 020206 networking & telecommunications list decoding Computer Science Applications 010201 computation theory & mathematics Bounded function Perfect hash function Decoding methods Information Systems Communication channel |
| Zdroj: | ISIT |
| ISSN: | 1557-9654 0018-9448 |
| DOI: | 10.1109/tit.2019.2933424 |
| Popis: | 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 26n/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}. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|