Asymptotic Optimality of the Asymmetric Encoding-Decoding Scheme

The Asymmetric Encoding-Decoding Scheme (AED) recently proposed by the authors is a lossless data compression scheme that can attain a compression ratio better than (or at worst the same as) the Huffman code and the tANS (tabled variant of Asymmetric Numeral Systems). In this paper, we will derive an upper bound on the average codeword length of the optimal AEDS for any stationary memoryless source with a finite discrete alphabet and evaluate how fast it converges to the source entropy as the number of internal states increases in the AEDS.