Codage arithmétique

Le codage arithmétique est un codage entropique utilisé en compression de données sans perte.

Normalement une chaîne de caractères comme "hello world" est représentable en utilisant un nombre fixe de bits par caractère, comme dans le code ASCII. Comme le Codage de Huffman, le codage arithmétique est un code à longueur variable. Ce qui différencie le codage arithmétique des autres codages source est qu'il encode le message entièrement et le représente par un seul nombre n (flottant) alors que les autres codages séparent le message d'entrée en les symboles qui le composent et encodent ensuite chaque symbole par un mot code.

Le codage arithmétique est toujours meilleur que le Codage de Huffman sauf si dans l'arbre de Huffman tous les poids des feuilles/nœuds/racines sont des puissances de 2.

Exemple : Si les poids sont A 1, B 1, C 1 l'arbre d'Huffman sera le suivant

0	A
10	B
11	C

On voit que A qui est pourtant aussi fréquent que B ou C est avantagé et on utilisera en moyenne 5/3= 1,667 bits par caractère. Le codage arithmétique utilisera lui exactement log2(3) bits par caractère soit 1,585 bits par caractère. Ce serait encore plus flagrant avec des poids tels que A 31, B 1 qui donneraient 1 bit par caractère pour Huffman contre (31 * (log2(32) - log2(31)) + 1 * (log2(32) - log2(1)))/32 = 0,201 soit 5 fois moins.

Le principe consiste à transformer les poids en intervale. Pour A 1, B 1, C 1 on a

[0, 1/3]	A
[1/3, 2/3]	B
[2/3, 1]	C

Donc au depart l'encodeur rencontre A, son intervale deviendra [0, 1/3] puis B, la composition des intervales donne [1/9, 2/9] puis C [1/9+2/27, 2/9] puis ...

En terme informatique on ne peut pas se permettre de stocker des fractions non calculées, il y a donc des erreurs au niveau des arrondis, mais ce type de codage va faire les mêmes erreurs au décodage qu'à l'encodage et évite donc cet écueil. De la même manière on ne peut pas gérer un flottant qui serait codé sur plusieurs dizaines de Kio (voire Mio, Gio) il faut donc "streamer" l'intervalle : Pour [0, 1/3] mon intervale est en dessous de 1/2 et le sera toujours, à quoi bon utiliser un bit en mémoire pour garder cette information, l'encodeur envoie un 0 dans la sortie et je transforme mon intervalle en [0, 2/3]. De la même manière s'il est plus élevé que 1/2 l'encodeur envoie un 1. Par contre si 1/2 est contenu dans l'intervalle l'encodeur ne peut rien envoyer mais il va peut-être être amené à le faire s'il arrive en limite de precision exemple : l'encodeur doit savoir qu'avec sa precision en memoire pour les flottants il ne sera pas à même de découper l'intervalle [0,49999999999 , 0,5000000001] sans pertes d'information (les erreurs d'arrondi causent des décalages de l'intervalle mais pas de perte) dans ce cas l'encodeur sera obligé de couper l'intervalle en deux.

Voir aussi

• Codage entropique
• Compression de données

Bibliographie

• (en) David MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003 (ISBN 0-521-64298-1)  [détail des éditions]