Codage de Golomb
- Codage de Golomb
-
Le codage de Golomb est un codage entropique inventé par Solomon Wolf Golomb en 1966 et utilisé essentiellement en compression de données.
Le code produit est un code préfixe.
Principe
Le codage de Golomb d'un entier naturel N dépend d'un paramètre k et se fait en deux étapes :
- le codage du quotient de la division euclidienne de N par k avec un codage unaire ;
- le codage du reste de la même division avec un codage binaire tronqué.
Mathématiquement, pour coder un entier 
, on code d'abord 
en unaire, puis 
en binaire tronqué.
Longueur du code
Cette section est vide, insuffisamment détaillée ou incomplète.
Votre aide est la bienvenue !
Optimalité
Le codage de Golomb est adapté pour des données dans lesquelles les valeurs les plus faibles sont plus probables que les autres (mais où les autres peuvent malgré tout apparaitre).
Exemples
Représentation des premiers entiers naturels avec un codage de Golomb
| Décimal |
Binaire |
Code de Golomb
k = 1 (unaire) |
Code de Golomb
k = 2 |
Code de Golomb
k = 3 |
Code de Golomb
k = 4 |
Code de Golomb
k = 5 |
Code de Golomb
k = 10 |
Code de Golomb
k = 16 |
| 0 |
0000 |
0 |
0 0 |
0 0 |
0 00 |
0 00 |
0 000 |
0 0000 |
| 1 |
0001 |
10 |
0 1 |
0 10 |
0 01 |
0 01 |
0 001 |
0 0001 |
| 2 |
0010 |
110 |
10 0 |
0 11 |
0 10 |
0 10 |
0 010 |
0 0010 |
| 3 |
0011 |
1110 |
10 1 |
10 0 |
0 11 |
0 110 |
0 011 |
0 0011 |
| 4 |
0100 |
11110 |
110 0 |
10 10 |
10 00 |
0 111 |
0 100 |
0 0100 |
| 5 |
0101 |
111110 |
110 1 |
10 11 |
10 01 |
10 00 |
0 101 |
0 0101 |
| 6 |
0110 |
1111110 |
1110 0 |
110 0 |
10 10 |
10 01 |
0 1100 |
0 0110 |
| 7 |
0111 |
11111110 |
1110 1 |
110 10 |
10 11 |
10 10 |
0 1101 |
0 0111 |
| 8 |
1000 |
111111110 |
11110 0 |
110 11 |
110 00 |
10 110 |
0 1110 |
0 1000 |
| 9 |
1001 |
1111111110 |
11110 1 |
1110 0 |
110 01 |
10 111 |
0 1111 |
0 1001 |
| 10 |
1010 |
11111111110 |
111110 0 |
1110 10 |
110 10 |
110 00 |
10 000 |
0 1010 |
Utilisations
Le codage de Golomb est principalement utilisé dans sa variante dite codage de Rice qui peut être implémentée de façon plus efficace. Un codage de Rice est d'ailleurs équivalent à un codage de Golomb dont le paramètre est 2 élevé à la puissance du paramètre de Rice.
Voir aussi
Articles connexes
Bibliographie
- Solomon Wolf Golomb, « Run-length encodings », IEEE Transactions on Information Theory IT-12, pp. 399-401, 1966.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Codage de Golomb de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Codage de Rice — Le codage de Rice, codage de Golomb Rice ou GPO2 (pour Golomb power of 2) est un codage entropique inventé par Robert F. Rice et James R. Plaunt en 1971 et utilisé essentiellement en compression de données. Le code produit est un code préfixe.… … Wikipédia en Français
Codage binaire tronqué — Le codage binaire tronqué est un codage entropique utilisé essentiellement en compression de données et s appuyant sur la base 2. Il est plus généralement utilisé pour coder de façon efficace en termes de longueur, un alphabet dont la taille n… … 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
Golomb — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Golomb: Solomon W. Golomb le Graphe de Golomb Règle de Golomb la Suite de Golomb Codage de Golomb Catégorie : Homonymie … 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 delta — Pour les articles homonymes, voir Code Delta (émission de télévision). Le codage delta ou codage delta d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code delta produit est un… … Wikipédia en Français
Codage omega — Le codage omega ou codage omega d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code omega produit est un code préfixe et universel. Sommaire 1 Principe 1.1 Codage 1.2 Décodage … 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 gamma — Le codage gamma ou codage gamma d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code gamma produit est un code préfixe et universel. Sommaire 1 Principe 2 Codage des entiers… … 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
