Codage gamma

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.

Sommaire

Principe

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 \in \mathbb{N}^*, on code d'abord \lfloor \log_2 N \rfloor en unaire, puis les \lfloor \log_2 N \rfloor bits de poids faible de N en binaire (en perdant au passage le bit de poids fort qui est implicite).

Codage des entiers relatifs

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 \left [ -A; +\infty \right ), A \in \mathbb{N}, on peut appliquer la fonction \begin{cases}\begin{align}&\scriptstyle f \colon \left [ -A; +\infty \right ) \to \mathbb{N}^* \\ &\textstyle x \mapsto x + A + 1\end{align}\end{cases} avant le codage gamma, et son inverse \begin{cases}\begin{align}&\scriptstyle f \colon \mathbb{N}^* \to \left [ -A; +\infty \right ) \\ &\textstyle x \mapsto {x - A - 1}\end{align}\end{cases} après le décodage gamma.

Pour coder tous les entiers relatifs sur \mathbb{Z}, on peut appliquer la fonction \begin{cases}\begin{align}&\scriptstyle f \colon \mathbb{Z} \to \mathbb{N}^* \\ &\textstyle x \mapsto \begin{cases} 2 \times x, x > 0\\ -2 \times x + 1, x \le 0\end{cases}\end{align}\end{cases} avant le codage gamma, et son inverse \begin{cases}\begin{align}&\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{align}\end{cases} après le décodage gamma.

Longueur du code

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

L = 2 \times \lfloor \log_2 N \rfloor + 1

Exemples

Représentation des premiers entiers naturels strictement positifs avec un codage gamma
Décimal
N		 Binaire
N		 Nombre de bits moins un
U = \lfloor \log_2 N \rfloor		 Nombre de bits moins un
(U en codage unaire)		 Binaire, privé du bit de poids fort
B = N − 2U + 1		 Code gamma
U en unaire suivi de 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

Généralisation

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.

Voir aussi

Articles connexes

v · d · m
Techniques de compression de données
Sans perte
Codage entropique Unaire · Binaire tronqué · Gamma · Delta · Omega · Zeta  · Fibonacci · Levenshtein · Even-Rodeh · Stout · Golomb · Rice · Exp-Golomb · Shannon-Fano · Huffman · Shannon-Fano-Elias · Arithmétique · Par intervalle
Dictionnaire LZ77 · LZ78 · LZSS · LZW · LZO
Modélisation de contextes Modélisation de Markov dynamique (DMC) · Prédiction par reconnaissance partielle (PPM) · Pondération de contextes (CM) · Pondération de contextes arborescents (CTW)
Techniques hybrides Implode · Deflate · LZP · LZMA · ROLZ
Autres Codage par plage (RLE)
Transformations Codage différentiel (Delta) · Transformée en étoile · MTF · Transformée de Burrows-Wheeler (BWT) · Transformée par substitution de mots (WRT) · BCJ2
Avec pertes
Codage par transformation Compression par ondelettes
Autres Modulation par impulsions et codage différentiel adaptatif (ADPCM) · Compression fractale
Transformations Transformée de Karhunen-Loève (KLT) · Transformée en cosinus discrète (DCT) · Transformée de Fourier discrète (DFT) · Transformée en ondelettes discrète (DWT)

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Codage gamma de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Codage delta — Pour les articles homonymes, voir Code Delta (émission de télévision). Le codage delta ou codage delta d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code delta produit est un… …   Wikipédia en Français

  • 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. Sommaire 1 Principe 1.1 Codage 1.2 Décodage …   Wikipédia en Français

  • Codage zeta — Le codage zeta ou codage de Boldi Vigna est un codage entropique inventé par Paolo Boldi et Sebastiano Vigna en 2003 et utilisé essentiellement en compression de graphes. Le code zeta produit est un code préfixe et universel. Sommaire 1 Principe… …   Wikipédia en Français

  • Codage unaire — Le codage unaire est un codage entropique utilisé essentiellement en compression de données et s appuyant sur la base 1. Sommaire 1 Principe 2 Longueur du code 3 Optimalité 4 …   Wikipédia en Français

  • Codage de Fibonacci — Le codage de Fibonacci est un codage entropique utilisé essentiellement en compression de données. Il utilise les nombres de la suite de Fibonacci, dont les termes ont la particularité d être composés de la somme des deux termes consécutifs… …   Wikipédia en Français

  • Gamma (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Alphabet grec et dérivés Gamma est le nom d une lettre de l alphabet grec, Γ. Elle est utilisée : sous sa forme majuscule (Γ), la fonction gamma… …   Wikipédia en Français

  • Codage entropique — Le codage entropique (ou codage statistique à longueur variable) est une méthode de codage de source sans pertes, dont le but est de transformer la représentation d une source de données pour sa compression et/ou sa transmission sur un canal de… …   Wikipédia en Français

  • Codage de Huffman — Le codage de Huffman est un algorithme de compression de données sans perte élaboré par David Albert Huffman, lors de sa thèse de doctorat au MIT. L algorithme a été publié en 1952 dans l article A Method for the Construction of Minimum… …   Wikipédia en Français

  • Codage binaire tronqué — Le codage binaire tronqué est un codage entropique utilisé essentiellement en compression de données et s appuyant sur la base 2. Il est plus généralement utilisé pour coder de façon efficace en termes de longueur, un alphabet dont la taille n… …   Wikipédia en Français

  • Codage de Rice — Le codage de Rice, codage de Golomb Rice ou GPO2 (pour Golomb power of 2) est un codage entropique inventé par Robert F. Rice et James R. Plaunt en 1971 et utilisé essentiellement en compression de données. Le code produit est un code préfixe.… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”