česky
previous main page content next

Adaptive arithmetic coding - initial frequencies of source units set to 1

Main features

Time and space complexities

Time complexity of algorithm: O(|Σ|*n)
Space complexity of algorithm: O(|Σ|)

History

As written in reference 1, arithmetic codes were invented by Elias, Rissanen and Pasco, and subsequently made practical by Witten in 1987.

Description

Arithmetic coding, unlike many others methods, does not code source units one by one, but codes whole input into one decimal number from interval <0,1).

An interval is divided into disjoint subintervals, each belonging to one source unit. Each loaded unit is represented within a new interval using the same range as subinterval belonging to the unit in previous interval. New interval is then divided according to frequencies of units. As a result could be taken any number lying in the interval belonging to last loaded unit.

This version sets initial frequencies of all source units to 1. It is adaptive because of increasing frequency of each loaded unit during coding.

This implementation uses special character # for detection of end-of-input.

Pseudo-code


 1:  begin
 2:     set initial frequencies of all source units to 1
 3:     interval I := new interval [0;1)
 4:     divide I according to frequencies of source units
 5:     readSymbol(X)
 6:     while (X != EOF) do 
 7:      begin
 8:        new I := subinterval I matching X
 9:        divide I according to frequencies of source units
10:        increase frequency of X
11:        readSymbol(X)
12:      end
13:  end

References

  1. David J. C. MacKay: Information Theory, Inference, and Learning Algorithms.
  2. Arithmetic coding. Wikipedia, the free encyclopedia.
  3. E. Bodden, M. Clasen, J. Kneis: Arithmetic Coding revealed - description of the method.
  4. Context-Based Adaptive Binary Arithmetic Coding (CABAC) - application of the method.

Example