

























This paper proposes a new lossless data compression coding scheme named an asymmetric encoding-decoding scheme (AEDS), which can be considered as a generalization of tANS (tabled variant of asymmetric numeral systems). In the AEDS, a data sequence $\mathbf{s}=s_1s_2\cdots s_n$ is encoded in backward order $s_t, t=n, \cdots, 2,1$, while $\mathbf{s}$ is decoded in forward order $s_t, t=1, 2, \cdots, n$ in the same way as the tANS. But, the code class of the AEDS is much broader than that of the tANS. We show for i.i.d.~sources that an AEDS with 2 states (resp.~5 states) can attain a shorter average code length than the Huffman code if a child of the root in the Huffman code tree has a probability weight larger than 0.61803 (resp.~0.56984). Furthermore, we derive several upper bounds on the average code length of the AEDS, which also hold for the tANS, and we show that the average code length of the optimal AEDS and tANS with $N$ states converges to the source entropy with speed $O(1/N)$ as $N$ increases.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。