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.
Principe
Comme le codage gamma et le codage delta, le codage omega permet de coder tous les entiers naturels, à l'exception de zéro, sans qu'il y ait besoin de connaitre au préalable l'intervalle des valeurs à coder (contrairement, par exemple, au codage binaire de taille fixe, qui ne permet de coder que des nombres inférieurs à une borne supérieure fixée à l'avance).
Codage
Pour cela, le codage omega fait précéder la représentation binaire du nombre par sa longueur (en nombre de bits), comme le font les codages gamma et delta. Comme l'intervalle des valeurs pouvant être prise par cette longueur n'est pas non plus connu à l'avance, elle doit être codée avec un code préfixe. Contrairement au codage gamma qui utilise un codage unaire à cet effet, ou au codage delta qui utilise un codage gamma, le codage omega utilise un codage omega. Ce codage est donc un codage récursif.
En pratique, chaque représentation binaire est précédée de sa longueur moins un en codage omega (car une longueur nulle n'a pas de sens), et la représentation binaire de 1 (correspondant au nombre 1 ou à une longueur 2) est omise, car implicite (1 est donc le cas d'arrêt de la récursion). L'ensemble du code omega est suivi d'un 0 faisant office de séparateur, indiquant que la représentation binaire qui le précède est celle du nombre codé et non pas celle d'une longueur (il n'y a pas d'ambigüité car toutes les représentations binaires commencent par un 1).
Décodage
Au début du décodage, il est considéré qu'un 1 implicite a déjà été décodé, correspondant soit au nombre 1, soit à une longueur 2. À chaque étape du décodage, le premier bit suivant est considéré : si c'est un 0, il indique la fin du code omega, c'est-à-dire que la dernière valeur décodée était le nombre codé (donc un, la première fois) ; si c'est un 1, il indique le début de la représentation binaire suivante, dont la longueur est la dernière valeur décodée plus un (donc deux, la première fois).
Codage des entiers relatifs
Comme pour le codage gamma et le codage delta, il est possible de coder des entiers relatifs avec le codage omega en utilisant une bijection pour transformer les nombres négatifs ou nul en nombres strictement positifs avant le codage à proprement parler. Après le décodage, l'opération inverse doit être effectuée pour retrouver les entiers relatifs d'origine.
Exemples
| Décimal | Binaire | Code omega | Code delta équivalent | Code gamma équivalent |
|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 |
| 2 | 10 | 10 0 | 100 0 | 10 0 |
| 3 | 11 | 11 0 | 100 1 | 10 1 |
| 4 | 100 | 10 100 0 | 101 00 | 110 00 |
| 5 | 101 | 10 101 0 | 101 01 | 110 01 |
Voir aussi
Articles connexes
Portail de l’informatique