Competitive optimality of source codes
Hirosuke Yamamoto and Tadaaki Itoh
IEEE Trans. on Information Theory, vol.41, no.6, pp.2015-2019, Nov. 1995
- The competitively optimal coding is considered and the following is proved. 1) If the competitively optimal code exists for a given source probability $p(x)$, then it also attains the minimum expected codeword length. 2) If the Huffman code tree for $p(x)$ is unbalanced in probability weight, then the competitively optimal code does not exist. Furthermore, the relation between the competitively optimal coding and the game theory is considered.
- Index Terms: competitive optimality, source coding, Huffman code game theory
- DOI: 10.1109/18.476328