Title :
Competitive optimality of source codes
Author :
Yamamoto, Hirosuke ; Itoh, Tadaaki
Author_Institution :
Dept. of Math. Eng. & Inf. Phys., Tokyo Univ., Japan
fDate :
11/1/1995 12:00:00 AM
Abstract :
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 competitively optimal coding and game theory is considered
Keywords :
Huffman codes; game theory; probability; source coding; Huffman code tree; competitive optimality; competitively optimal coding; game theory; minimum expected codeword length; source codes; source probability; Australia; Binary codes; Costs; Decoding; Game theory; Information theory; Length measurement; Physics; Random variables; Source coding;
Journal_Title :
Information Theory, IEEE Transactions on