TD 3, Arithmetic coding

Introduction to Information Theory

January 20 2023

Let I={0,…,n−1} (typically n=256) be a memoryless source. For all i in I the probabilities are given by Pr(i)=p_i/M where p_i is a positive integer and M an integer (generally a power of $2$, equal to 65536 here). We denote by s_i the sum Σ_j<i p_j.

Outline of the encoding

Initialize the interval as [a,b[=[0,M[, and let k=0 be a counter
for each letter i output by the source
- [a,b[ becomes [a + s_i*(b−a)/M, a + (s_i+p_i)*(b−a)/M[ (the numbers are rounded down)
- the new interval [a,b[ is reduced (see below)
when all symbols are read:
- if a < M/4 then 01^k+1 is added to the output, or 10^k+1 is added to the output.

Reduction of the interval [a,b[ while one of these conditions is met

if b ≤ M/2, the interval becomes [2a, 2b[
01^k is added to the output, k is reset to 0
else if a ≥ M/2, the interval becomes [2a − M, 2b − M[
10^k is added to the output, k is reset to 0
else if M/4 ≤ a < b ≤ 3M/4, the interval becomes [2a − M/2, 2b − M/2[
the counter k is incremented

For a stream (i₁,…,i_L) the output is the truncated binary representation of S(x₁,…,x_n).

The class Source.java contains the definitions of the constants and the probability distributions and some useful methods.
Implement the arithmetic encoder. You can use the following implementation of the decoder to check your implementation. To use the decoder, run java Decoder fichier.code where fichier.code is your encoded file.

You can use the unix commands

java Coder candide.txt > candide.code
java Decoder candide.code > candide.decode
diff candide.txt candide.decode

Ressources:

This document was translated from ^LAT_EX by H^EV^EA