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

Assignment of Intervals to Codes


The symbols are identified by any number, which falls into the interval concerned. All values, which are greater or equal than 0.0 and less than 0.4, will be interpreted as 'a' for example.


Examples: assigning codes and intervals:


Symbol  Sub-Interval
   a     [0.0; 0.4)
   b     [0.4; 0.6)
   c     [0.6; 0.8)
   d     [0.8; 0.9)
   e     [0.9; 1.0)

Code Word  Sub-Interval  Symbol
   0.1      [0.0; 0.4)    -> a
   0.2      [0.0; 0.4)    -> a
   0.4      [0.4; 0.6)    -> b
   0.55     [0.4; 0.6)    -> c
   0.99     [0.9; 1.0)    -> e

All intervals have a closed lower endpoint (indicated by '[') and an open upper endpoint (indicated by ')'). The lower endpoint always belongs to the interval, while the upper endpoint is placed outside. I.e. the value 1 might be never encoded in this context.


 <   ^   > 

Principle of the Arithmetic Coding Dividing into Intervals Sub-Intervals