Codage de Golomb

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

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 ${\displaystyle N}$ dépend d'un paramètre ${\displaystyle k}$ et se fait en deux étapes :

1. le codage du quotient de la division euclidienne de ${\displaystyle N}$ par ${\displaystyle k}$ 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 ${\displaystyle N,N\in \mathbb {N} ,N=q\times k+r}$, on code d'abord ${\displaystyle q=\lfloor N/k\rfloor }$ en unaire, puis ${\displaystyle r=N-k\times q}$ en binaire tronqué.

Longueur du code

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 = 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

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

• Codage unaire
• Codage binaire tronqué
• Codage de Rice
• Codage entropique
• Compression de données

Bibliographie

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

• Portail de l’informatique