Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

   

2008 Research Summary

Tilted Arithmetic Coding (T-DAC)

View Current Project Information

Cheng Chang and Anant Sahai

In [1], Rissanen proposed a variable-length entropy coding scheme, arithmetic coding, where a source string is encoded by an interval in [0,1] and the size of the interval is proportional to the likelihood of the source string. In [2], we derived the error exponent for a delay constrained lossless source coding problem, where the achievability is proved by using a prefix-free code with code length proportional to the logarithm of an optimal tilted distribution.

In this project, we generalize the standard arithmetic code to achieve the delay constrained source coding error exponent. The size of the interval corresponding to a source string is proportional to the optimal tilted likelihood of the string instead of the original likelihood. This coding scheme is thus termed as "tilted arithmetic code." This work shows the versatility of the arithmetic coding.

[1]
J. Rissanen, "Generalized Kraft Inequality and Arithmetic Coding," IBM Journal of Research and Development, Vol. 20, No. 3, May 1976, pp. 198-203.
[2]
C. Chang and A. Sahai, "The Error Exponent with Delay for Lossless Source Coding," IEEE Information Theory Workshop, 2006.