Codage delta
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png)
Pour les articles homonymes, voir Code Delta (émission de télévision).
![Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/12px-Info_Simple.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a1/2017-fr.wp-orange-source.svg/45px-2017-fr.wp-orange-source.svg.png)
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
![Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/12px-Info_Simple.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Design_plat_Calendrier_orange.svg/45px-Design_plat_Calendrier_orange.svg.png)
Cet article manque de repères chronologiques ou de dates ().
Vous pouvez ajouter les données manquantes avec leurs sources.
Le codage delta ou codage delta d'Elias est un codage entropique inventé [Quand ?] par Peter Elias et utilisé essentiellement en compression de données.
Le code delta produit est un code préfixe et universel.
Principe
Comme le codage gamma, le codage delta 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 delta se fait en deux étapes :
- le codage du nombre de bits nécessaires pour représenter l'entier avec un codage gamma ;
- le codage à proprement parler de l'entier avec un codage binaire sur ce même nombre de bits nécessaires.
La démarche est donc similaire à celle du codage gamma, la différence étant que le codage unaire de la première étape est remplacé par un codage gamma.
En pratique, le bit de poids fort de l'entier n'est pas encodé car implicite, mais, contrairement à ce qui est fait lors d'un codage gamma, c'est son nombre de bits qui est encodé au cours de la première étape (sans lui soustraire 1, car le codage gamma ne permet de coder que des entiers naturels strictement positifs).
Mathématiquement, pour coder un entier , on code d'abord en gamma, puis les bits de poids faible de en binaire (en perdant au passage le bit de poids fort qui est implicite).
Codage des entiers relatifs
Comme pour le codage gamma, il est possible de coder des entiers relatifs avec le codage delta 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.
Longueur du code
La longueur du code gamma associé à un entier naturel strictement positif peut être exprimée par :
Cette longueur croît moins rapidement avec que lors d'un codage gamma. Contrairement à ce dernier, le codage delta permet d'obtenir des codes de longueur asymptotiquement optimale.
Exemples
Décimal | Binaire | Nombre de bits | Nombre de bits ( en codage gamma) | Binaire, privé du bit de poids fort | Code delta en gamma suivi de | Code gamma équivalent |
---|---|---|---|---|---|---|
1 | 1 | 1 | 0 | 0 | 0 | |
2 | 10 | 2 | 100 | 0 | 100 0 | 10 0 |
3 | 11 | 2 | 100 | 1 | 100 1 | 10 1 |
4 | 100 | 3 | 101 | 00 | 101 00 | 110 00 |
5 | 101 | 3 | 101 | 01 | 101 01 | 110 01 |
Notes et références
Voir aussi
- Codage gamma
- Codage omega
- Codage entropique
- Compression de données
v · m Techniques de compression de données | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Sans perte |
| ||||||||||||||
Avec pertes |
|
Portail de l’informatique