Codage gamma

Le codage gamma ou codage gamma d'Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données.

Le code gamma produit est un code préfixe et universel.

Le codage gamma 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).

Pour cela, le codage gamma se fait en deux étapes :

1. le codage du nombre de bits nécessaires pour représenter l'entier, avec un codage unaire ;
2. le codage à proprement parler de l'entier avec un codage binaire sur ce même nombre de bits nécessaires.

En pratique, le bit de poids fort de l'entier n'est pas encodé car implicite et c'est le nombre de bits auquel on soustrait 1 qui est encodé au cours de la première étape (pour la même raison).

Mathématiquement, pour coder un entier N ∈ N ∗ {\displaystyle N\in \mathbb {N} ^{*}} , on code d'abord ⌊ log 2 ⁡ N ⌋ {\displaystyle \lfloor \log _{2}N\rfloor } en unaire, puis les ⌊ log 2 ⁡ N ⌋ {\displaystyle \lfloor \log _{2}N\rfloor } bits de poids faible de N {\displaystyle N} en binaire (en perdant au passage le bit de poids fort qui est implicite).

Il est possible de coder des entiers relatifs avec le codage gamma 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.

Par exemple, pour coder les entiers relatifs de l'intervale [ − A ; + ∞ ) , A ∈ N {\displaystyle \left[-A;+\infty \right),A\in \mathbb {N} } , on peut appliquer la fonction { f : [ − A ; + ∞ ) → N ∗ x ↦ x + A + 1 {\displaystyle {\begin{cases}{\begin{aligned}&\scriptstyle f\colon \left[-A;+\infty \right)\to \mathbb {N} ^{*}\\&\textstyle x\mapsto x+A+1\end{aligned}}\end{cases}}} avant le codage gamma, et son inverse { f : N ∗ → [ − A ; + ∞ ) x ↦ x − A − 1 {\displaystyle {\begin{cases}{\begin{aligned}&\scriptstyle f\colon \mathbb {N} ^{*}\to \left[-A;+\infty \right)\\&\textstyle x\mapsto {x-A-1}\end{aligned}}\end{cases}}} après le décodage gamma.

Pour coder tous les entiers relatifs sur Z {\displaystyle \mathbb {Z} } , on peut appliquer la fonction { f : Z → N ∗ x ↦ { 2 × x , x > 0 − 2 × x + 1 , x ≤ 0 {\displaystyle {\begin{cases}{\begin{aligned}&\scriptstyle f\colon \mathbb {Z} \to \mathbb {N} ^{*}\\&\textstyle x\mapsto {\begin{cases}2\times x,x>0\\-2\times x+1,x\leq 0\end{cases}}\end{aligned}}\end{cases}}} avant le codage gamma, et son inverse { f : N ∗ → Z x ↦ { x 2 , x ≡ 0 ( mod 2 ) − x − 1 2 , x ≡ 1 ( mod 2 ) {\displaystyle {\begin{cases}{\begin{aligned}&\scriptstyle f\colon \mathbb {N} ^{*}\to \mathbb {Z} \\&\textstyle x\mapsto {\begin{cases}{\tfrac {x}{2}},x\equiv 0{\pmod {2}}\\-{\tfrac {x-1}{2}},x\equiv 1{\pmod {2}}\end{cases}}\end{aligned}}\end{cases}}} après le décodage gamma.

La longueur L {\displaystyle L} du code gamma associé à un entier naturel strictement positif N {\displaystyle N} peut être exprimée par :

L = 2 × ⌊ log 2 ⁡ N ⌋ + 1 {\displaystyle L=2\times \lfloor \log _{2}N\rfloor +1}

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

Décimal N {\displaystyle N}	Binaire N {\displaystyle N}	Nombre de bits moins un U = ⌊ log 2 ⁡ N ⌋ {\displaystyle U=\lfloor \log _{2}N\rfloor }	Nombre de bits moins un ( U {\displaystyle U} en codage unaire)	Binaire, privé du bit de poids fort B = N − 2 U + 1 {\displaystyle B=N-2^{U+1}}	Code gamma U {\displaystyle U} en unaire suivi de B {\displaystyle B}
1	1	0	0		0
2	10	1	10	0	10 0
3	11	1	10	1	10 1
4	100	2	110	00	110 00
5	101	2	110	01	110 01

Une généralisation du codage gamma est le codage zeta ; le codage gamma peut être vu comme un codage zeta de paramètre 1.

• Codage delta
• Codage omega
• Codage zeta
• Codage entropique
• Compression de données

• Portail de l’informatique