Data Compression


Criteria

Survey Formats

Basics

Compression Methods

Data Formats


Arithmetic Coding (AC)

Principle of the AC

Dividing into Intervals

Assignment to Codes

Sub-Intervals

Codes for 2 Symbols

Scheme Intervals "aaaa"

Scheme Intervals "abcd"

General Algorithm

AC versus Huffman

Data with high Redundancy

Adaptive AC

Implementations


Glossary

Index


Download


www.BinaryEssence.com

Sub-Intervals


After the initial encoding, any further symbol will not relate to the basic intervall [0; 1). The sub-interval identified by the first symbol has to be used for the next step. In the case of an 'a' the new interval would be [0; 0.4), for 'b' [0.4; 0.6).


Providing a constant probability distribution and the first symbol 'a', the new sub-intervals would be:


Divide interval after encoding of 'a'


    total: [0.0; 1.0)       total: [0.0; 0.4)

Sym. P(x)  Intervals              Sub-Intervals
 a   0.4   [0.0; 0.4) ----- 0.16   [0.00; 0.16)
 b   0.2   [0.4; 0.6)   |   0.08   [0.16; 0.24)
 c   0.2   [0.6; 0.8)   |   0.08   [0.24; 0.32)
 d   0.1   [0.8; 0.9)   |   0.04   [0.32; 0.36)
 e   0.1   [0.9; 1.0)    -- 0.04   [0.36; 0.40)
    -----                  ------
Sum  1.0                    0.40

 <   ^   > 

Principle of the Arithmetic Coding Assignment of Intervals to Codes Codes for 2 Symbols