Codage de Golomb

codage entropique
(Redirigé depuis Code 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.

Courbe montrant la redondance du codage de Golomb quand la valeur m est choisie de manière optimale.

Le code produit est un code préfixe.

Principe

modifier

Le codage de Golomb d'un entier naturel   dépend d'un paramètre   et se fait en deux étapes :

  1. le codage du quotient de la division euclidienne de   par   avec un codage unaire ;
  2. 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

modifier

Optimalité

modifier

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

modifier
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 = 4
Code de Golomb
k = 16
0 0000 0 0 0 0 00 0 0000
1 0001 10 0 1 0 01 0 0001
2 0010 110 10 0 0 10 0 0010
3 0011 1110 10 1 0 11 0 0011
4 0100 11110 110 0 10 00 0 0100
5 0101 111110 110 1 10 01 0 0101
6 0110 1111110 1110 0 10 10 0 0110
7 0111 11111110 1110 1 10 11 0 0111
8 1000 111111110 11110 0 110 00 0 1000
9 1001 1111111110 11110 1 110 01 0 1001
10 1010 11111111110 111110 0 110 10 0 1010

Utilisations

modifier

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

modifier

Articles connexes

modifier

Bibliographie

modifier
  • Solomon Wolf Golomb, « Run-length encodings », IEEE Transactions on Information Theory IT-12, pp. 399-401, 1966.