Truncated binary encoding

Le codage binaire tronqué est une technique de codage entropique couramment utilisée pour les distributions de probabilité uniformes avec un alphabet fini. Il est paramétré par un alphabet de taille totale n. C'est une forme légèrement plus générale du codage binaire lorsque n n'est pas une puissance de deux.

Si n est une puissance de deux, alors le code pour 0 ≤ x < n est le code binaire simple pour x de longueur log₂(n). Sinon, soit k = floor(log₂(n)), de sorte que 2^k < n < 2^k+1, et soit u = 2^k+1 − n.

Le codage binaire tronqué attribue les u premiers symboles des mots de code de longueur k, puis attribue les n − u symboles restants aux n − u derniers mots de code de longueur k + 1. Comme tous les mots de code de longueur k + 1 sont constitués d'un mot de code non attribué de longueur k avec un "0" ou "1" ajouté, le code résultant est un prefix code.

Histoire

Utilisé depuis au moins 1984, les codes de phase-in, également connus sous le nom de codes économiques, sont également connus sous le nom de codage binaire tronqué.

Exemple avec n = 5

Par exemple, pour l'alphabet {0, 1, 2, 3, 4}, n = 5 et 2² ≤ n < 2³, donc k = 2 et u = 2³ − 5 = 3. Le codage binaire tronqué attribue aux u premiers symboles les mots de code 00, 01 et 10, tous de longueur 2, puis attribue aux n − u derniers symboles les mots de code 110 et 111, les deux derniers mots de code de longueur 3.

Par exemple, si n est 5, le codage binaire simple et le codage binaire tronqué attribuent les mot de code suivants. Les chiffres en ~~barré~~ ne sont pas transmis dans le codage binaire tronqué.

Codage binaire tronqué	Encodage	Codage binaire standard
0	0	0	0	0
1	0	0	1	1
2	0	1	0	2
INUTILISÉ	0	1	1	3
INUTILISÉ	1	0	0	4
INUTILISÉ	1	0	1	5/INUTILISÉ
3	1	1	0	6/INUTILISÉ
4	1	1	1	7/INUTILISÉ

Il faut 3 bits pour coder n en utilisant le codage binaire direct, donc 2³ − n = 8 − 5 = 3 sont inutilisés.

En termes numériques, pour envoyer une valeur x, où 0 ≤ x < n, et où il y a 2^k ≤ n < 2^k+1 symboles, il y a u = 2^k+1 − n entrées inutilisées lorsque la taille de l'alphabet est arrondie à la puissance de deux la plus proche. Le processus pour coder le nombre x en binaire tronqué est le suivant : si x est inférieur à u, le coder en k bits binaires ; si x est supérieur ou égal à u, coder la valeur x + u en k + 1 bits binaires.

Exemple avec n = 10

Un autre exemple, le codage d'un alphabet de taille 10 (entre 0 et 9) nécessite 4 bits, mais il y a 2⁴ − 10 = 6 codes inutilisés, donc les valeurs d'entrée inférieures à 6 ont le premier bit supprimé, tandis que les valeurs d'entrée supérieures ou égales à 6 sont décalées de 6 à la fin de l'espace binaire. (Les motifs inutilisés ne sont pas montrés dans ce tableau.)

Valeur d'entrée	Décalage	Valeur de décalage	Codage binaire standard	Codage binaire tronqué
0	0	0	0000	000
1	0	1	0001	001
2	0	2	0010	010
3	0	3	0011	011
4	0	4	0100	100
5	0	5	0101	101
6	6	12	0110	1100
7	6	13	0111	1101
8	6	14	1000	1110
9	6	15	1001	1111

Pour décoder, lire les k premiers bits. Si ils codent une valeur inférieure à u, le décodage est terminé. Sinon, lire un bit supplémentaire et soustraire u du résultat.

Exemple avec n = 7

Voici un cas plus extrême : avec n = 7, la puissance de 2 suivante est 8, donc k = 2 et u = 2³ − 7 = 1 :

Valeur d'entrée	Décalage	Valeur de décalage	Codage binaire standard	Codage binaire tronqué
0	0	0	000	00
1	1	2	001	010
2	1	3	010	011
3	1	4	011	100
4	1	5	100	101
5	1	6	101	110
6	1	7	110	111

Ce dernier exemple montre qu'un bit zéro de tête n'indique pas toujours un code court ; si u < 2^k, certains codes longs commenceront par un bit zéro.

Algorithme simple

Générer le codage binaire tronqué pour une valeur x, 0 ≤ x < n, où n > 0 est la taille de l'alphabet contenant x. n n'a pas besoin d'être une puissance de deux.

string TruncatedBinary (int x, int n)
{
	// Définir k = floor(log2(n)), c'est-à-dire k tel que 2^k <= n < 2^(k+1).
	int k = 0, t = n;
	while (t > 1) { k++;  t >>= 1; }

	// Définir u au nombre de mots de code inutilisés = 2^(k+1) - n.
	int u = (1 << k + 1) - n;

	if (x < u)
        return Binary(x, k);
    else
        return Binary(x + u, k + 1));
}

La routine Binary est explicative ; généralement, seuls les bits de droite len de la variable x sont souhaités. Ici, nous émettons simplement le code binaire pour x en utilisant len bits, en remplissant avec des 0 d'ordre supérieur si nécessaire.

string Binary (int x, int len)
{
	string s = "";
	while (x != 0) {
		if (even(x))
            s = '0' + s;
		else  s = '1' + s;

		x >>= 1;
	}
	while (s.Length < len)
        s = '0' + s;
	return s;
}

Sur l'efficacité

Si n n'est pas une puissance de deux, et que les symboles de k bits sont observés avec une probabilité p, alors les symboles de (k + 1) bits sont observés avec une probabilité 1 − p. Nous pouvons calculer le nombre moyen de bits par symbole $b_{e}$ comme

$b_{e}=pk+(1-p)(k+1).$

Le codage brut du symbole a $b_{u}=k+1$ bits. Ensuite, l'économie d'espace relative s (voir Data compression ratio) du codage peut être définie comme

$s=1-{\frac {b_{e}}{b_{u}}}=1-{\frac {pk+(1-p)(k+1)}{k+1}}.$

Lorsque simplifiée, cette expression conduit à

$s={\frac {p}{k+1}}={\frac {p}{b_{u}}}.$

Cela indique que l'efficacité relative du codage binaire tronqué augmente à mesure que la probabilité p des symboles de k bits augmente, et que la longueur des bits du symbole de codage brut $b_{u}$ diminue.

Voir aussi

• Loi de Benford
• Codage de Golomb

---

 Facebook Page

🐤 Twitter Follow us on Twitter !

Read or create/edit this page in another language

• Truncated binary encoding in English