An Optimality Proof of the Iterative Algorithm for AIFV-m Codes

Iwata and Yamamoto proposed an iterative algorithm to obtain the optimal AIFV-m code with m code trees for a given source probability distribution, which can attain better compression rate than Huffman codes generally. In this paper, we generalize the optimization problem of AIFV-m code trees to the...

Full description

Saved in:
Bibliographic Details
Main Authors: Fujita, Ryusei, Iwata, Ken-Ichi, Yamamoto, Hirosuke
Format: Conference Proceeding
Language:English
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Iwata and Yamamoto proposed an iterative algorithm to obtain the optimal AIFV-m code with m code trees for a given source probability distribution, which can attain better compression rate than Huffman codes generally. In this paper, we generalize the optimization problem of AIFV-m code trees to the optimization problem of the average performance of finite Markov systems with m states, which have a unique stationary distribution. Then, we prove that the generalized iterative algorithm can derive the optimal system with m states, and hence, the original iterative algorithm can derive the optimal AIFV-m code.
ISSN:2157-8117
DOI:10.1109/ISIT.2018.8437861