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.

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

Article détaillé : Codage_gamma#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.

Longueur du code

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !

Exemples

Représentation des premiers entiers naturels strictement positifs avec un codage omega

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

• Codage gamma
• Codage delta
• Codage entropique
• Compression de données