Codage arithmétique

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

Bibliographie


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Codage arithmétique de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Codage arithmetique — Codage arithmétique Le codage arithmétique est une technique de compression 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 …   Wikipédia en Français

  • Codage De Huffman — Le codage de Huffman est un algorithme de compression qui fut mis au point en 1952 par David Albert Huffman. C est une compression de type statistique qui grâce à une méthode d arbre que nous allons détailler plus loin permet de coder les octets… …   Wikipédia en Français

  • Codage de huffman — Le codage de Huffman est un algorithme de compression qui fut mis au point en 1952 par David Albert Huffman. C est une compression de type statistique qui grâce à une méthode d arbre que nous allons détailler plus loin permet de coder les octets… …   Wikipédia en Français

  • Codage De Source — Le but du codage de source peut être de compresser l information répétitive du langage, sa redondance. Pour toute langue, on peut considérer l entropie d un message, c est à dire la quantité d information transmise. Ceci donne lieu au théorème du …   Wikipédia en Français

  • Codage de source — Le but du codage de source peut être de compresser l information répétitive du langage, sa redondance. Pour toute langue, on peut considérer l entropie d un message, c est à dire la quantité d information transmise. Ceci donne lieu au théorème du …   Wikipédia en Français

  • Codage entropique — Le codage entropique (ou codage statistique à longueur variable) est une méthode de codage de source sans pertes, dont le but est de transformer la représentation d une source de données pour sa compression et/ou sa transmission sur un canal de… …   Wikipédia en Français

  • Codage de Huffman — Le codage de Huffman est un algorithme de compression de données sans perte élaboré par David Albert Huffman, lors de sa thèse de doctorat au MIT. L algorithme a été publié en 1952 dans l article A Method for the Construction of Minimum… …   Wikipédia en Français

  • Codage de Shannon-Fano — Le codage de Shannon Fano est un algorithme de compression de données sans perte élaboré par Robert Fano à partir d une idée de Claude Shannon. Il s agit d un codage entropique produisant un code préfixe très similaire à un code de Huffman, bien… …   Wikipédia en Français

  • Codage unaire — Le codage unaire est un codage entropique utilisé essentiellement en compression de données et s appuyant sur la base 1. Sommaire 1 Principe 2 Longueur du code 3 Optimalité 4 …   Wikipédia en Français

  • Arithmetique modulaire — Arithmétique modulaire Couverture de l’édition originale des Recherches arithmétiques de Gauss, livre fondateur de l’arithmétique modulaire. En mathématiques et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”