An Optimality Proof of the Iterative Algorithm for AIFV-m Codes
Ryusei Fujita, Ken‐ichi Iwata, H. Yamamoto · 2018
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.