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 communication. Les principaux types de codage entropique sont le codage de Huffman et le codage arithmétique.

Le codage entropique utilise des statistiques sur la source pour construire un code, c'est-à-dire une application qui associe à une partie de la source un mot de code, dont la longueur dépend des propriétés statistiques de la source. On utilise donc en général un code à longueur variable, qui attribue les mots de codes les plus courts aux symboles de source les plus fréquents. Le codage entropique est issu de la théorie de l'information, et traite de ces codes et de leurs propriétés. L'information à coder est représentée par une variable aléatoire à valeur dans un alphabet de taille finie. Un résultat important est le théorème du codage de source, qui établit la limite à la possibilité de compression, et établit cette limite comme étant l'entropie.

Historiquement développé dans les années 1940-50 avec la théorie de l'information, le codage entropique est devenu une technique fondamentale en compression de données, et est présent dans de nombreux programmes de compression et de normes de compression d'image et de compression vidéo.

Définitions

On considère une source discrète, c'est-à-dire un dispositif qui fournit aléatoirement des séquences de symboles issus d'un ensemble discret fini. Une source peut être un texte, une image, ou plus généralement, tout signal numérique. Une source est modélisée par un ensemble de variables aléatoires, à valeur dans un alphabet de taille finie, $\Omega=\{x_0, \ldots,x_N\}$ . $Ω$ est appelé l'ensemble des symboles de source.

Définition — Une source est dite sans mémoire si la séquence de symboles générée par la source est une suite de variables indépendantes et identiquement distribuées.

Définition — Un code de source C pour une variable aléatoire $X$ de distribution de probabilité $p$ , est une application de $Ω$ vers l'ensemble des chaînes de symboles d'un alphabet D-aire $A$ .

L'ensemble des chaînes de symboles d'un alphabet D-aire $A$ est noté $A +$ . En général, cet alphabet est binaire et on a $D = 2$ , $A = {0,1}$ . $A +$ est alors l'ensemble des chaînes de caractères de taille finie formées de 0 et de 1, $A^+=\{0, 1, 00, 01, 10, 11, 000, \ldots\}$ . Un code associe à un symbole de source $x$ un mot de code $C (x)$ . Ce mot de code est de longueur variable $l (x)$ , la longueur étant son nombre de bits. Ces codes sont appelés codes à longueur variable.

L'espérance de la longueur d'un code $C$ (ou longueur moyenne, selon la loi de probabilité de X) est donnée par:

$L(C)=\sum_{x \in \Omega}p(x) \cdot l(x)$ .

$L (C)$ peut également se voir comme le taux de codage, c'est-à-dire le nombre moyen de bits codés par symbole de source.

Définition — L'extension $C +$ d'un code $C$ est l'application de $Ω +$ dans $A +$ , qui associe à une séquence de symboles de source la concaténation de ses mots de code:

$C^+(x_0 x_1 \ldots x_N)=C(x_0)C(x_1) \ldots C(x_N)$ .

Cette définition est motivée par le fait que l'on transmet des séquences de symboles, et non des symboles isolés séparés par un symbole de séparation, ce qui serait inefficace^[1].

Propriétés des codes de source

Un code doit respecter certaines propriétés pour être utile: une concaténation de mots de code doit avoir un décodage unique, aisé, et permettre la plus grande compression possible^[2]. Certaines conditions sont imposées au code pour satisfaire ces propriétés.

Définition — Un code est dit uniquement décodable (ou uniquement déchiffrable) si

$\forall x,y \in \Omega^+, x \ne y \Rightarrow C^+(x) \ne C^+(y)$

Autrement dit, toute séquence codée est décodable par une unique séquence de symbole de source.

Définition — Un code est un code préfixe si aucun mot de code n'est le préfixe d'un autre mot de code.

L'intérêt des codes préfixés est qu'ils sont décodables immédiatement, en les parcourant de la gauche vers la droite. La fin d'un mot de code est reconnaissable immédiatement, sans la nécessité d'un code spécial pour indiquer la terminaison ou une séparation^[2]^,^[3]. De plus, les codes préfixes sont uniquement décodables.

Exemple: Soit le code défini par le tableau suivant

Définition du code $C 1$
Symbole de source	Mot de code	Longueur du mot de code
a	0	1
b	10	2
c	110	3
d	111	3

Le code $C 1 = {0,10,110,111}$ est un code préfixé. La séquence codée comme

11011111010110010110111

se décompose facilement en:

110 111 110 10 110 0 10 110 111

et se décode donc comme:

c d c b c a b c d

Inégalité de Kraft

Article détaillé : Inégalité de Kraft.

L'inégalité de Kraft donne une condition nécessaire et suffisante sur les longueurs des mots de code pour qu'un code possède un code préfixé équivalent (possédant la même distribution de longueur des mots). Pour un code défini sur un alphabet de taille $D$ , et un alphabet de source $Ω$ de taille $| Ω |$ , alors il est préfixé si et seulement si $\sum_{i=1}^{|\Omega|} D^{-l_i} \leq 1.$

Code optimal

Un code optimal est un code préfixé de longueur moyenne minimale. La compression est d'autant plus forte que la longueur moyenne des mots de code est faible. Trouver un code optimal revient donc à choisir les longueurs des mots de codes, par rapport à la distribution de probabilité des symboles de source, afin de rendre la longueur moyenne minimale. Pour trouver un tel code, il faut minimiser la longueur moyenne du code $L (C)$ , sous les conditions de l'inégalité de Kraft, soit:

minimiser $\sum_{i=1}^{|\Omega|}p_i l_i$ sous la condition $\sum_{i=1}^{|\Omega|} D^{-l_i} \leq 1.$

Par la méthode des multiplicateurs de Lagrange, on définit le lagrangien $J$ :

$J=\sum_{i=1}^{|\Omega|}p_i l_i + \lambda \sum_{i=1}^{|\Omega|} D^{-l_i}$

que l'on différentie par rapport aux $l i$ . Un rapide calcul^[4] donne les longueurs optimales $l_i^*=-\log_2 p_i$ , soit une longueur moyenne $L(C)=-\sum p_i \log_2 p_i$ , c'est-à-dire l'entropie $H (X)$ . Les longueurs données par cette méthode ne sont cependant pas entières, sauf dans le cas exceptionnel où les $p i$ sont des puissance négatives de 2. Ce résultat n'est donc pas utile en pratique, et il est nécessaire d'utiliser d'autres méthodes pour construire un code optimal.

Théorème du codage de source

Article détaillé : théorème du codage de source.

Types de codes

Codage de Shannon-Fano

Article détaillé : Codage de Shannon-Fano.

Le codage de Shannon-Fano est la première méthode de codage entropique efficace, développée en même temps par Claude Shannon et Robert Fano en 1949. Cette méthode n'est en revanche pas optimale, et a été rapidement supplantée par le codage de Huffman^[5].

Codage de Huffman

Article détaillé : Codage de Huffman.

Le codage de Huffman a été développé par David Huffman en 1952. C'est un code optimal au niveau symbole. De nombreuses améliorations ont été proposées après sa publication, notamment le codage adaptatif, qui permet de ré-estimer les probabilités à la volée. Ceci permet d'effectuer le codage et le décodage sans disposer de la totalité des statistiques de la source.

Codage arithmétique

Article détaillé : Codage arithmétique.

Le codage arithmétique est une extension du codage de Shannon-Fano-Elias. Il est optimal au niveau bit.

Code universel

Article détaillé : Code universel.

Applications

La principale application du codage entropique est la compression de données. Si le codage de Huffman a rapidement laissé sa place aux méthodes par dictionnaire pour la compression de données génériques^[6], il reste très utilisé en compression d'images, et est présent dans la norme JPEG. Le codage arithmétique s'est montré efficace seulement à partir du début des années 1990, et est utilisé aussi bien en compression de données génériques (PAQ) qu'en compression d'images (JPEG 2000) et vidéo (H.264).

Voir aussi

Codage de l'information

Bibliographie

(en) Thomas M. Cover, Joy A. Thomas, Elements of Information Theory, Wiley-Interscience, 2006 (ISBN 978-0-471-24195-9) [détail des éditions]
(en) David MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003 (ISBN 0-521-64298-1) [détail des éditions]
(fr) Mark Nelson, La compression de données, texte, images, sons. Dunod, 1993.

Notes et références

↑ Cover, Thomas (2006), p. 105
↑ ^{a et b} McKay (2003), p. 92
↑ Cover, Thomas (2006), p. 106
↑ Cover, Thomas (2006), p. 110-111
↑ Nelson, p. 23
↑ Nelson, p. 21

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)

Catégories :

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

Codage De Huffman — Le codage de Huffman est un algorithme de compression qui fut mis au point en 1952 par David Albert Huffman. C est une compression de type statistique qui grâce à une méthode d arbre que nous allons détailler plus loin permet de coder les octets… … Wikipédia en Français
Codage de huffman — Le codage de Huffman est un algorithme de compression qui fut mis au point en 1952 par David Albert Huffman. C est une compression de type statistique qui grâce à une méthode d arbre que nous allons détailler plus loin permet de coder les octets… … Wikipédia en Français
Codage de Shannon-Fano — Le codage de Shannon Fano est un algorithme de compression de données sans perte élaboré par Robert Fano à partir d une idée de Claude Shannon. Il s agit d un codage entropique produisant un code préfixe très similaire à un code de Huffman, bien… … Wikipédia en Français
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 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 1 Principe 2 Codage des entiers… … 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 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
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