An iterative algorithm to construct optimal binary AIFV-m codes

摘要

We propose an algorithm to construct an optimal code that achieves the minimum average codeword length in the class of binary AIFV-m codes with m code trees T₀, T₁,..., T_m-1for a given stationary memoryless source. The algorithm is an iterative algorithm such that the optimal T_kfor a given set of costs is derived by dynamic programming (DP) and the costs are updated from the set of code trees (T₀, T₁, · · ·, T_m-1), iteratively. The proposed DP works with polynomial time and space for source alphabet size. We prove the AIFV-m code obtained by the proposed algorithm is optimal for m = 2, 3,4, 5 although the algorithm works for any m and we conjecture the optimality also holds for m ≥ 6. Furthermore, we verify by some examples of sources that the average codeword length of the optimal binary AIFV-m codes can be decreased as m becomes large.