Codage binaire tronqué

Le codage binaire tronqué (aussi appelé « economy code » ou « code phase-in » dans les compresseurs de la famille LZ) 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.

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=2^{k}+b$, le codage binaire tronqué sépare l'ensemble des valeurs à coder en deux groupes : les $N-2b=2^{k}-b=2^{k+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{aligned}&\delta _{x}=1,x<2^{\lceil \log _{2}N\rceil }-N\\&\delta _{x}=0,x\geq 2^{\lceil \log _{2}N\rceil }-N\end{aligned}}\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 $2^{3}-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 $2^{3}-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.

Variation

Une version modifiée tire profit de la loi des grands nombres. Dans beaucoup d'applications, il y a plus de grands nombres que de petits nombres et il devient préférable d'économiser un bit pour les nombres élevés au lieu des nombres proches de zéro. On encode alors le nombre $N$-n au lieu de n.

Voir aussi

• Section "5.3.4.2: Codes phase-in" dans http://stevenpigeon.org/Publications/publications/phd.pdf : Steven Pigeon — Contributions à la compression de données — Thèse de doctorat, Université de Montréal, Déc 2001

Articles connexes

• Codage entropique
• Compression de données