A Novel Variant of Arithmetic Coding Using the Stern-Brocot Tree and Farey Addition
AbstractIn arithmetic coding, the input data is mapped to a small subinterval within the interval [0, 1). In the conventional implementation, a rational number is selected from this, which can be represented as a fraction with a power of two in the denominator. Only the numerator of this fraction is saved in the compressed file because the power of the denominator corresponds to the number of bits in the numerator and can therefore be reconstructed from it. This paper introduces a new variant that instead uses the Stern-Brocot tree and the Farey addition to find the rational number that has the smallest possible denominator within the same interval. Now the denominator must be stored in the same way as the numerator, but the numerator and denominator together have only about as many binary digits as the number obtained using the conventional method. In around one in four cases, the result of the new approach is even shorter than the conventional binary number. The results show that this new method is not only interesting for theoretical reasons, but even has the potential to outperform established methods.