TD 3, Codage Arithmétique

Introduction à la théorie de l'information

24 janvier 2020


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)=pi/Mpi 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 sij<i pj.

Grandes lignes de l'algorithme de codage : Reduction de l'intervalle [a,b[, tant que l'une des conditions est vérifiée Pour un fichier à compresser (i1,…,iL) la sortie sera l'écriture en base 2 de S(x1,…,xn) tronquée "au bon endroit". Si vous suivez exactement les instructions ci-dessus, çà marche.
  1. 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).
  2. Écrire un codeur, on pourra utiliser le décodeur pour tester son programme. La syntaxe du décodeur est java Decoder fichier.codefichier.code est le fichier codé.
  3. 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 LATEX par HEVEA