Finite-precision arithmetic coding via index-splitting and probability-fitting

This paper proposes a fitting-by-splitting algorithm (abbreviated as the FS algorithm), which is composed of an index-splitting (IS) algorithm and a probability-fitting (PF) algorithm, to effectively achieve the finite-precision arithmetic coding code named as the FS-AC code. The FS algorithm generates the FS-AC codes of arbitrarily specified length without the need of post-appended sentinel symbol or pre-affixed side-information bits. Its IS process can split the input symbols into paired indices to make the residual information space be reused as effectively as possible at the end of arithmetically encoding a fixed-precision code. And, the PF process performs after each IS operation for enhancing the reuse efficiency via a fast adaptation process of probability table. Through the integration of IS and PF processes, not only the coding efficiency of proposed finite-precision AC codec can be close to that of unlimited precision AC codec especially for our proposed binary AC codecs. And also, consecutive FS-AC codes can be mutually independent such that the error propagation can be almost blocked to an AC code in problem. Hence, our new AC codecs can be appropriate for generating finite-precision AC codes in the high-speed networks.