TD 3, Codage Arithmétique

Introduction à la théorie de l'information

20 janvier 2023

On considère une source sans mémoire I={0,…,n−1} (typiquement n=256). Pour tout i dans I les probabilités sont données par Pr(i)=p_i/M où p_i est un entier strictement positif et M une constante entière (une puissance de 2 en pratique, et égale à 65536 dans ce TD). Nous noterons s_i=Σ_j<i p_j.

Grandes lignes de l'algorithme de codage :

on initialise l'intervalle [a,b[=[0,M[, et un compteur k=0
pour chaque lettre i produite par la source
- [a,b[ devient [a + s_i*(b−a)/M, a + (s_i+p_i)*(b−a)/M[ (les arrondis sont à l'entier inférieur)
- le nouvel intervalle [a,b[ est réduit (voir plus loin)
quand tous les caractères ont été lus:
- si a < M/4 alors 01^k+1 est ajouté à la sortie, sinon 10^k+1 est ajouté à la sortie.

Reduction de l'intervalle [a,b[, tant que l'une des conditions est vérifiée

si b ≤ M/2, l'intervalle devient [2a, 2b[
01^k est ajouté à la sortie, k est remis à 0
sinon si a ≥ M/2, l'intervalle devient [2a − M, 2b − M[
10^k est ajouté à la sortie, k est remis à 0
sinon si M/4 ≤ a < b ≤ 3M/4, l'intervalle devient [2a − M/2, 2b − M/2[
le compteur k est incrémenté

Pour un fichier à compresser (i₁,…,i_L) la sortie sera l'écriture en base 2 de S(x₁,…,x_n) tronquée "au bon endroit". Si vous suivez exactement les instructions ci-dessus, çà marche.

On vous donne un fichier Source.java qui contient les constantes (distribution de probas), et quelques fonctions utiles (recherche de l'intervalle de Shannon-Fano-Elias).
Écrire un codeur, on pourra utiliser le décodeur pour tester son programme. La syntaxe du décodeur est java Decoder fichier.code où fichier.code est le fichier codé.

Vous utilisera les mécanismes de redirection d'unix:

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

Ressources:

Ce document a été traduit de L^AT_EX par H^EV^EA