Codage binaire tronqué

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'est pas une puissance de 2.

Le code résultant est équivalent au code de Huffman canonique qui est obtenu en considérant que les différents symboles de l'alphabet sont équiprobables.

Sommaire

Principe

Contrairement au codage binaire de taille fixe, le codage binaire tronqué utilise un code préfixe à longueur variable. La longueur de ce code est toujours inférieure ou égale à celle du code binaire optimal équivalent, qui est de \lceil \log_2 N \rceil où N est la taille de l'alphabet à coder.

Pour un alphabet de taille N = 2k + b, le codage binaire tronqué sépare l'ensemble des valeurs à coder en deux groupes : les N − 2b = 2k − b = 2k + 1 − N premières valeurs d'une part, et les 2b valeurs restantes d'autre part. Les premières valeurs sont codées sur k = \lfloor \log_2 N \rfloor bits, tandis que les secondes sont codées sur k + 1 = \lceil \log_2 N \rceil bits.

Les codes utilisés pour coder ces dernières valeurs sont les 2b derniers codes de longueur k + 1 ; il n'y a donc pas de continuité entre les valeurs codées sur k bits et celles codées sur k + 1 bits. C'est cette façon de coder qui fait du code binaire tronqué un code préfixe.

Gains en termes d'espace par rapport au codage binaire

Dans le pire des cas, un code binaire tronqué est de la même longueur que le code binaire équivalent. Lorsque la taille de l'alphabet est une puissance de 2, ce pire cas est systématique, et les codes produits sont identiques. On peut ainsi voir le codage binaire comme un cas particulier de codage binaire tronqué, avec un alphabet dont la taille est une puissance de 2.

Dans tous les autres cas, le gain est de 1 bit pour chaque valeur parmi les 2^{\lceil \log_2 N \rceil} - N premières de l'alphabet, et il est nul pour toutes les autres valeurs.

Le gain global G pour coder une source de longueur l sur un alphabet A de taille N peut être exprimé par :

G = l \times \sum_{i=0}^{N-1} p(A_i) \delta_i

Où p(x) est la probabilité d'apparition de la valeur x et \begin{cases}\begin{align}&\delta_x = 1, x < 2^{\lceil \log_2 N \rceil} - N\\&\delta_x = 0, x \ge 2^{\lceil \log_2 N \rceil} - N\end{align}\end{cases}

Lorsque la distribution des valeurs est connue et non uniforme, il est intéressant de réorganiser l'alphabet pour que les valeurs ayant la plus forte probabilité d'apparition soient au début de celui-ci.

Exemples

Codage d'un alphabet de taille 5

Le code binaire optimal pour un alphabet de taille 5 est de longueur \lceil \log_2 5 \rceil = 3.

On peut donc coder sur 2 bits les 23 − 5 = 3 premières valeurs, et sur 3 bits les valeurs restantes.

Représentation des premiers entiers naturels en binaire optimal et en binaire tronqué
Décimal Binaire optimal
(sur 3 bits)		 Binaire tronqué
0 000 00
1 001 01
2 010 10
3 011 110
4 100 111

Dans le cas d'une distribution uniforme, le codage binaire tronqué sur un alphabet de taille 5 offre un gain moyen de 0,6 bits par caractère, soit 20%.

Codage d'un alphabet de taille 7

Le code binaire optimal pour un alphabet de taille 7 est de longueur \lceil \log_2 7 \rceil = 3.

On peut donc coder sur 2 bits la 23 − 7 = 1 première valeur, et sur 3 bits les valeurs restantes.

Représentation des premiers entiers naturels en binaire optimal et en binaire tronqué
Décimal Binaire optimal
(sur 3 bits)		 Binaire tronqué
0 000 00
1 001 010
2 010 011
3 011 100
4 100 101
5 101 110
6 110 111

Dans le cas d'une distribution uniforme, le codage binaire tronqué sur un alphabet de taille 7 offre un gain moyen de 0,14 bits par caractère, soit 4,76%.

Utilisations

Le codage binaire tronqué est utilisé pour coder un alphabet dont la taille n'est pas une puissance de 2, lorsque la longueur du code est critique. Dans le cas général (lorsque la vitesse est plus importante que la longueur du code), le codage binaire est préféré car il est plus simple et plus rapide à manipuler (notamment car sa taille fixe permet un indiçage immédiat).

Le codage binaire tronqué est en particulier utilisé pour le codage de la position lors d'un codage de Golomb ou d'un codage zeta.

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 binaire tronqué de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Codage de Golomb — Le codage de Golomb est un codage entropique inventé par Solomon Wolf Golomb en 1966 et utilisé essentiellement en compression de données. Le code produit est un code préfixe. Sommaire 1 Principe 2 Longueur du code 3 Optimalité …   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 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 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 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 de Levenshtein — Le codage de Levenshtein est un codage entropique inventé par Vladimir Levenshtein en 1968 et utilisé essentiellement en compression de données. Le code de Levenshtein produit est un code préfixe et universel. Sommaire 1 Principe 2 Longueur du… …   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 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 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

Share the article and excerpts

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