Adaptive multi-alphabet arithmetic coding is a key component of many data compression algorithms. The well-known integer implementation of the arithmetic coding, proposed by Witten and Cleary, requires multiplications and divisions. This makes it difficult to use the coder, especially in hardware. Therefore, the vast majority of existing implementations represent non-binary data as a set of binary symbols (called binarization) and compress them using context modeling and a multiplication-free adaptive binary arithmetic coding (BAC). However, this approach can provide less compression performance comparing to multi-alphabet arithmetic coding. In this project we developed novel adaptive multi-alphabet arithmetic coding based on generalized virtual sliding window, which has the following advantages:

• Comparing to Witten and Cleary implementation it does not require multiplications or divisions.
• Comparing to BAC-based implementations it utilizes only one renormalization per input non-binary symbol and does not use binarization with corresponding context-modeling.
• It provides better compression performance in average than Witten and Cleary or BAC-based coders.

For more detailed information please see [1].

For comparisons, we used classic Witten and Cleary multi-alphabet adaptive arithmetic coding implementation and four multi-alphabet adaptive arithmetic coding based on adaptive BAC. As an adaptive BAC we used MQ-coder from JPEG2000 image coding standard and M-coder from H.264/AVC and H.265/HEVC video coding standards. For representing non-binary data into binary format we applied unary binarization and tree binarization. The proposed coder was realized in two versions. The first version, denoted as Proposed 1, is the case, when the best window length was selected for each file, while Proposed 2 utilizes single window for all files using different precision of approximation of the multiplication (higher K means better precision).

The following table shows the compression performance for Large Calgary Corpus. Here we use Witten and Cleary's implementation as reference coder and compare it with the multiplication-free implementations, so that an average gain with sign '-' means that a considered coder provides better results than the reference one.

The following table shows the compression performance for Large Corpus.

The presented results show that:

• Proposed 1 and Proposed 2 with K = 8 provide the best average results among considered coders. Herewith, Proposed 1 outperforms Proposed 2 with the price of multiple encoding with different window lengths, i.e., it can be used to achieve the maximum compression ratio at high performance platforms.
• Decreasing the precision of the multiplication approximation reduces the compression performance. However, the precision with K = 3 is enough to provide better results than both M-coder and MQ-coder for The Large Corpus (+3.0% and +4.4% versus +1.2%) and better or comparable results for Large Calgary Corpus (+0.3% and -0.7% versus -0.5%).

GVSW arithmetic coder, Version 1.0 [download]

[1] E.Belyaev, S.Forchhammer, Kai Liu, An adaptive multi-alphabet arithmetic coding based on generalized virtual sliding window, IEEE Signal Processing Letters, vol.24, is.7, 2017. [download] [draft]