Scribd
Upload
48 views20 pages

Arithmetic Coding

The document discusses arithmetic coding, which represents strings of symbols by intervals to produce uniquely decodable codes. It explains the basic idea that each string is assigned a unique interval based on symbol probabilities, and the code is a number in that interval. Examples are provided to illustrate how intervals are calculated for encoding and decoding. Issues like scaling and integer arithmetic are also covered to discuss practical implementation of arithmetic coding.

Uploaded by

perhacker
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
48 views20 pages

Arithmetic Coding

The document discusses arithmetic coding, which represents strings of symbols by intervals to produce uniquely decodable codes. It explains the basic idea that each string is assigned a unique interval based on symbol probabilities, and the code is a number in that interval. Examples are provided to illustrate how intervals are calculated for encoding and decoding. Issues like scaling and integer arithmetic are also covered to discuss practical implementation of arithmetic coding.

Uploaded by

perhacker
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 20

Lecture 8:

Arithmetic Coding

Thinh Nguyen
Oregon State University
Representation of Real Number in
Binary
Real-to-Binary Conversion Algorithm
Arithmetic Coding
‡ Basic idea in arithmetic coding (Shannon-Fano-
Elias):

„ Represent each string x of length n by a unique interval [L,R)


in [0,1).

„ The width r-l of the interval [L,R) represents the probability of


x occurring.

„ The interval [L,R) can itself be represented by any number,


called a tag, within the half open interval.

„ The k significant bits of the tag .t1t2t3... is the code of x. That


is, . .t1t2t3...tk000... is in the interval [L,R).
Example of Arithmetic Coding
Some Tags are better than others

14/27
Examples
Code Generation from Tags
Guaranteed Code Example
Arithmetic Coding Algorithm
C(xi) = P(x0) + P(x1) + … P(xi)

Initialize L: = 0 and R: = 1;
For i = 1 to n do
W:= R – L;
L: = L + W*C(xi-1);
R := L + W*C(xi);
T: = (L+R)/2;
Choose code for the tag
Example
P(A) = ¼, P(b) = ½ , P(c) = ¼
C(a) = ¼, C(b) = ¾, C(c) = 1
abca
Example
P(A) = ¼, P(b) = ½ , P(c) = ¼
C(a) = ¼, C(b) = ¾, C(c) = 1
bbbb
Decoding
Decoding
Decoding
Arithmetic Decoding Algorithm
C(xi) = P(x0) + P(x1) + … P(xi)
Decode b1b2 …bm, the number of symbols in n

Initialize L:= 0 and R := 1;


t:= .b1b2…bm
For i = 1 to n do
W := R-L;
Find j such that L + W*C(xj-1) <= t < L + W*C(xj)
Output xj;
L := L + W*C(xj-1);
R := L + W*C(xj);
Decoding Example
P(a) = ¼, P(b) = ½ , P(c) = ¼
C(a) = 0, C(b) = 1/4, C(c) = 3/4
Decoding Issues
‡ There are two ways for the decoder to know
when to stop decoding.

1. Transmit the length of the string


2. Transmit a unique end of string symbol
Practical Arithmetic Coding
‡ Scaling:

„ By scaling we can keep L and R in a reasonable range of


values so that W = R - L does not underflow.
„ The code can be produced progressively, not at the end.
„ Complicates decoding some.

‡ Integer arithmetic coding avoids floating point


altogether.
Uniqueness and Efficiency of Arithmetic
Code
‡ Uniqueness:
Proof:

‡ Efficiency:
Proof:

You might also like