2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | O.1.4 | ||
| Paper Title | On D-ary Fano Codes | ||
| Authors | Ferdinando Cicalese, Eros Rossi, University of Verona, Italy | ||
| Session | O.1: Data Compression | ||
| Presentation | Lecture | ||
| Track | Source Coding | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | We define a $D$-ary Fano code based on a natural generalization of the splitting criterion of the binary Fano code to the case of $D$-ary code. We show that this choice allows for an efficient computation of the code tree and also leads to a strong guarantee with respect to the redundancy of the resulting code: for any source distribution p = (p_1, ..., p_n) 1) for D = 2, 3, 4, the resulting code satisfies L - H_D(p) \leq 1 - p_{min}, (*) where L is the average codeword length, p_{min} = min_i p_i and $H_D(\p) = \sum_{i=1}^n p_i \log_D \frac{1}{p_i}$ (the $D$-ary entropy); 2) inequality (*) holds for every $D >= 2$ whenever every internal node has exactly $D$ children in the code tree produced by our construction. We also formulate a conjecture on the basic step applied by our algorithm in each internal node of the code tree, that, if true, would imply that the bound in (*) is actually achieved for all $D \geq 2$ without the restriction of item 2). | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
