Code exponentiel-Golomb

Le code exponentiel-Golomb ou Exp-Golomb code (en) d'ordre k est un type de code universel, paramétrable par un nombre entier k. Ce code est souvent utilisé dans la compression de données en tant que codeur entropique, par exemple dans la norme vidéo H.264.

Principe

Pour encoder un entier positif dans un code exponentiel-Golomb d'ordre k, celui-ci peut utiliser la méthode suivante:

1. Prendre le nombre en binaire hormis les k derniers chiffres et lui ajouter 1. Notez-le.
2. Compter le nombre de bits écrits et soustraire un.
3. Ecrire un nouveau nombre binaire en commençant par le nombre de 0 déterminé dans l'étape précédente.
4. Concaténer les k derniers bits en binaire soit le nombre binaire noté dans la première étape.

Pour k = 0 le code commence par:

 0 → 1 → 1
 1 → 10 → 010
 2 → 11 → 011
 3 → 100 → 00100
 4 → 101 → 00101
 5 → 110 → 00110
 6 → 111 → 00111
 7 → 1000 → 0001000
 8 → 1001 → 0001001
...

Application dans la norme H.264

Le code exponentiel-Golomb pour k=0 est utilisé dans la norme de compression vidéo H.264 ou MPEG-4 AVC, dans laquelle les symboles sont signés et sont alternativement assignés au mot de code. En d'autres termes, le 0 correspond au 0, le +1 au 1, le -1 au 2 le +2 au 3 etc...

Cet outil est utilisé afin de coder tous les paramètres qui ne correspondent pas explicitement à des données des images telles que le type de l'image, les vecteurs de mouvement, les modes de prédiction inter ou intra. Les codes utilisés sont de longueur variable mais leur construction s'établit suivant une logique définie par une table. Ces symboles ne sont pas en nombre fini, cependant plus la valeur est grande et plus la longueur de la chaîne binaire correspondante sera importante. C'est pour cela que l'on attribue un code proche du zéro pour les éléments ou symboles fréquents et un code plus grand pour ceux qui sont plus rares. Chaque type d'élément est associé à une table spécifique qui permet de retourner le code numérique lui correspondant.

Autres applications

Ce code est aussi utilisé dans le codec vidéo Dirac.

Le code exponentiel-Golomb pour k=0 est identique au codage gamma du même nombre incrémenté de 1. Ainsi il peut encoder le zéro, tandis que le codage gamma peut seulement encoder les nombres strictement supérieur à zéro.

Le codage exp-Golomb diffère légèrement du codage de Golomb qui est également un codeur entropique mais non un code universel.

Notes et Références

• (en) E. G. Richardson, H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia, Chichester, John Wiley & Sons Ltd., septembre 2003 (ISBN 0-470-84837-5) 
• (en) tutoriaux h.264 VLC

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Exponential-Golomb coding » (voir la liste des auteurs)

Voir aussi

• H.264
• codage de Golomb
• codage entropique