Le codage arithmétique est une méthode de compression de données sans perte, de la famille du codage entropique. Il représente un message entier par un unique nombre compris entre 0 et 1, ce qui lui permet d'approcher l'entropie, la limite théorique de la compression sans perte, de plus près que le codage de Huffman.

Esquissé dès 1948 par Claude Shannon et rendu récursif par Peter Elias, il ne devient praticable qu'en 1976, lorsque Richard Pasco et Jorma Rissanen montrent comment le mener avec une précision finie. Son principe consiste à partir de l'intervalle [0 ; 1[ et à le restreindre en sous-intervalles proportionnels à la probabilité de chaque symbole, jusqu'à un intervalle propre au message dont on transmet un nombre.

Longtemps jugé trop lent et gêné par des brevets, il s'est répandu à mesure que ceux-ci expiraient et qu'apparaissaient des implémentations plus rapides et mieux adaptées au matériel, comme le codage par intervalle, les codeurs binaires d'IBM, le CABAC ou les systèmes de numération asymétrique. Il est aujourd'hui omniprésent dans la compression d'images (JPEG 2000, JPEG XL), de vidéos (H.264, H.265, AV1) et de données en général (LZMA, Zstandard).

Les prémisses du codage arithmétique apparaissent en 1948, dans l'article fondateur de Claude Shannon sur la théorie de l'information. Il y suggère que des messages de ${\displaystyle n}$ symboles pourraient être codés en les classant tous par probabilité, puis en transmettant, pour le message voulu, la somme des probabilités de ceux qui le précèdent dans ce classement. Ce code prend la forme d'une fraction binaire : l'idée de représenter un message entier par un unique nombre compris entre 0 et 1 est née^[1].

Des travaux non publiés de Peter Elias, décrits par Abramson en 1963, reprennent cette idée et la transforment en un algorithme récursif qui n'exige plus de trier les messages : la probabilité cumulée se calcule symbole par symbole, en restreignant l'intervalle à chaque ajout^[2]. La méthode reste cependant inutilisable en l'état : chaque ajout de symbole resserre l'intervalle, ce qui exige une précision arbitrairement grande pour le représenter et des calculs de plus en plus lourds à mesure que le nombre de décimales augmente^[1].

C'est ce problème de précision que résolvent indépendamment deux chercheurs, Richard Pasco et Jorma Rissanen, en 1976. Ils montrent comment mener le même calcul avec une précision finie fixe, en arrondissant les valeurs intermédiaires, de sorte qu'un message de longueur quelconque puisse être codé sans que la précision nécessaire augmente avec lui^[3],[4]. Le terme « codage arithmétique » apparaît la même année dans le titre de l'article de Rissanen^[3].

Bien que le codage arithmétique offre un meilleur taux de compression que Huffman, et que la publication d'un code source performant en langage C en 1987 l'ait fait connaître^[5], il peine à s'imposer. La méthode est jugée trop lente pour le matériel grand public, et juridiquement risquée en raison des multiples brevets déposés par IBM, dont certains portent justement sur des optimisations du temps de calcul^[6].

D'autres évolutions arrivent ensuite. Les calculs sont accélérés en se restreignant à un codeur binaire, dont l'alphabet se limite aux bits 0 et 1, et en estimant les probabilités de façon dynamique. La première de ces optimisations, le Q-Coder d'IBM, remplace les multiplications de l'encodage par des additions et des décalages de bits, bien moins coûteux^[7].

Son descendant, le QM-Coder, devient le codeur arithmétique commun aux standards JPEG (1992) et JBIG, mais reste soumis à une redevance^[8],[9]. Le MQ-Coder, variante proche du QM-Coder dont il inverse l'attribution des sous-intervalles entre symbole le plus et le moins probable, est retenu en 2000 pour le JPEG 2000^[10],[11], puis le M-Coder (codeur modulo) équipe le codage CABAC des normes vidéo H.264 et H.265^[12],[11].

Leur diffusion s'élargit nettement dans les années 2010, portée d'abord par l'expiration progressive des brevets, puis par l'arrivée des systèmes de numération asymétrique (ANS), une famille voisine du codage arithmétique proposée par Jarek Duda à partir de 2007^[13]. L'ANS atteint un taux de compression proche de la limite théorique tout en étant généralement plus rapide que Huffman^[14]. Yann Collet en publie fin 2013 une implémentation libre et multi-symboles, le FSE (Finite State Entropy), dont la vitesse, en particulier au décodage, surpasse celle de l'implémentation Huffman de zlib^[15]. Adoptée dès 2015 par de grands acteurs du numérique, comme Facebook avec Zstandard et Apple avec LZFSE, puis par des formats d'image comme JPEG XL, cette approche fait du codage entropique proche de l'optimum une brique courante des formats modernes^[13].

Comme tout codage entropique, le codage arithmétique cherche à réduire la taille d'un message en faisant en sorte que les symboles fréquents occupent moins de place que les symboles rares. La méthode la plus répandue de cette famille, le codage de Huffman, attribue à chaque symbole un code formé d'un nombre entier de bits, d'autant plus court que le symbole est fréquent^[11].

Cette contrainte d'un nombre entier de bits par symbole impose une limite. Un symbole très fréquent, présent par exemple neuf fois sur dix, devrait idéalement coûter environ 0,15 bit, mais le codage de Huffman lui attribue au minimum 1 bit, soit plus de six fois la taille optimale. Le codage arithmétique lève cette limite en renonçant à coder les symboles un par un : il représente le message entier par un seul nombre, ce qui répartit le coût sans l'arrondir au bit pour chaque symbole^[16].

Pour cela, il part de l'intervalle [0 ; 1[ et le partage en sous-intervalles, un par symbole de l'alphabet, dont la longueur est proportionnelle à la probabilité du symbole. Coder le premier symbole revient à se restreindre à son sous-intervalle, lui-même partagé de la même façon pour le symbole suivant, et ainsi de suite : chaque symbole emboîte l'intervalle un peu plus profondément. À la fin, l'intervalle obtenu est propre au message.

On transmet alors un seul nombre situé dans cet intervalle, et plus l'intervalle est large, plus il est facile d'y trouver un nombre à peu de chiffres. Or un symbole fréquent, qui occupe un large sous-intervalle, ne resserre l'intervalle que faiblement, là où un symbole rare le resserre beaucoup. Un message fait surtout de symboles fréquents conserve donc un intervalle assez large, désigné par un nombre court. Ce nombre étant écrit en binaire, ces chiffres sont en fait des bits, et c'est là que se mesure le gain de compression^[5].

Pour le codage, on note ${\displaystyle b}$ et ${\displaystyle h}$ les bornes inférieure et supérieure de l'intervalle courant, et ${\displaystyle L=h-b}$ sa longueur. Cet intervalle vaut [0 ; 1[ au départ. Dans la table de probabilités, le symbole à coder occupe un sous-intervalle de borne inférieure ${\displaystyle b_{\text{sym}}}$ et de borne supérieure ${\displaystyle h_{\text{sym}}}$. Son ajout remplace les bornes courantes par : ${\displaystyle b_{\text{suiv}}=b+L\times b_{\text{sym}}}$ ${\displaystyle h_{\text{suiv}}=b+L\times h_{\text{sym}}}$ On applique ces deux opérations à chaque symbole du message, puis on transmet un nombre situé dans l'intervalle final, accompagné de la longueur du message si aucun symbole dédié à signaler la fin du message (EOF pour End Of File) n'a été mis en place^[5].

Le nombre transmis n'est pas un point quelconque de cet intervalle, mais le plus court à écrire en binaire. Pour l'obtenir, on n'en conserve que les premiers bits, juste assez pour que la valeur qu'ils désignent reste dans l'intervalle final une fois sa suite complétée par le décodeur selon une convention fixée. Il en faut de l'ordre de ${\displaystyle -\log _{2}L}$, à un ou deux bits près, où L est la longueur de l'intervalle final. Chaque message reçoit ainsi un préfixe de bits qui lui est propre, de sorte qu'aucun code n'est le début d'un autre.

Le décodage emprunte le chemin inverse à partir de ce nombre, noté ${\displaystyle V}$, à l'aide de la même table de probabilités. À chaque étape, on identifie le symbole dont le sous-intervalle contient ${\displaystyle V}$ et on l'ajoute au message. À l'aide de la borne inférieure ${\displaystyle b_{\text{sym}}}$ et de la probabilité ${\displaystyle p_{\text{sym}}}$ de ce symbole (la longueur de son sous-intervalle), on remplace alors ${\displaystyle V}$ par : ${\displaystyle V_{\text{suiv}}={\frac {V-b_{\text{sym}}}{p_{\text{sym}}}}}$ ce qui ramène la valeur dans [0 ; 1[ pour l'étape suivante. On répète l'opération autant de fois que le message compte de symboles ou jusqu'à rencontrer le symbole EOF^[5].

Mettons que nous voulions dérouler le codage arithmétique tel que proposé par Elias (sans renormalisation) sur le message « ANANAS », en traitant chaque lettre comme un symbole et sans recourir à un symbole de fin. On suppose donc que la longueur du message est transmise en même temps que la valeur codée.

On relève d'abord le nombre d'apparitions de chaque lettre, puis on en déduit sa probabilité d'apparition et l'intervalle qui lui est attribué dans [0 ; 1[, de longueur proportionnelle à cette probabilité.

Probabilités et intervalles des lettres de « ANANAS »

Lettre	Nombre d'apparitions	Probabilité	Intervalle	Intervalle (décimal)
A	3	1/2	[0 ; 1/2[	[0 ; 0,5[
N	2	1/3	[1/2 ; 5/6[	[0,5 ; 0,833[
S	1	1/6	[5/6 ; 1[	[0,833 ; 1[

Les valeurs décimales sont données à titre informatif, mais les calculs sont menés sur les fractions exactes.

Le codage part de l'intervalle [0 ; 1[, puis le restreint à chaque lettre lue en utilisant les formules vues plus haut.

Par exemple, pour la deuxième lettre, un N, l'intervalle courant est [0 ; 1/2[, donc ${\displaystyle b=0}$ et ${\displaystyle L=1/2}$. Le N occupe l'intervalle [1/2 ; 5/6[, d'où une nouvelle borne inférieure ${\displaystyle 0+{\tfrac {1}{2}}\times {\tfrac {1}{2}}={\tfrac {1}{4}}}$ et une nouvelle borne supérieure ${\displaystyle 0+{\tfrac {1}{2}}\times {\tfrac {5}{6}}={\tfrac {5}{12}}}$.

En appliquant ces opérations à chaque lettre, on obtient :

Codage du message « ANANAS »

Lettre ajoutée	Borne inférieure	Borne supérieure	Longueur de l'intervalle
Départ	0	1	1
A	0	1/2	1/2
N	1/4	5/12	1/6
A	1/4	1/3	1/12
N	7/24	23/72	1/36
A	7/24	11/36	1/72
S	131/432	11/36	1/432

À l'issue du codage, l'intervalle obtenu est [131/432 ; 11/36[, soit environ [0,3032 ; 0,3056[. N'importe quel nombre de cet intervalle représente fidèlement le message. On en choisit un dont l'écriture reste simple, par exemple 263/864 ≈ 0,304, qui sert de valeur codée finale.

Le décodage utilise le même tableau de probabilités. À chaque étape, on identifie la lettre dont l'intervalle contient la valeur courante, on l'ajoute au message, puis on ramène cet intervalle à [0 ; 1[ et on recommence.

Par exemple, la valeur initiale 263/864 ≈ 0,304 tombe dans [0 ; 1/2[, l'intervalle du A : la première lettre est donc A. La nouvelle valeur est ${\displaystyle {\frac {{\tfrac {263}{864}}-0}{\tfrac {1}{2}}}={\tfrac {263}{432}}}$.

En répétant l'opération, on retrouve les lettres du message :

Décodage de la valeur 263/864

Valeur courante	Symbole décodé	Nouvelle valeur
263/864 ≈ 0,304	A	263/432
263/432 ≈ 0,608	N	47/144
47/144 ≈ 0,326	A	47/72
47/72 ≈ 0,653	N	11/24
11/24 ≈ 0,458	A	11/12
11/12 ≈ 0,917	S	1/2

Au bout de six lettres, le décodeur a reconstruit le message « ANANAS ». Comme la longueur du message a été transmise avec la valeur codée, le décodeur sait qu'il doit s'arrêter ici.

Sans cette information, rien n'indiquerait que le message est terminé. Le calcul se poursuivrait et produirait des lettres supplémentaires, étrangères au message d'origine. En reprenant à partir de la dernière valeur obtenue, 1/2, le décodage continuerait ainsi :

Poursuite du décodage au-delà du message

Valeur courante	Symbole décodé	Nouvelle valeur
1/2 ≈ 0,5	N	0
0	A	0
0	A	0

La valeur reste alors bloquée à 0 et le décodeur sort une suite infinie de A. Pour éviter ce comportement, on transmet la longueur du message, comme dans cet exemple, ou bien on ajoute à l'alphabet un symbole de fin qui marque l'arrêt du décodage.

Le codage arithmétique repose sur la notion d'entropie, introduite par Claude Shannon en 1948 avec la théorie de l'information. L'entropie mesure la quantité moyenne d'information portée par chaque symbole d'une source. Pour une source dont les symboles ${\displaystyle x}$ appartiennent à un alphabet ${\displaystyle {\mathcal {X}}}$ et apparaissent avec les probabilités ${\displaystyle p(x)}$, elle s'écrit ${\displaystyle H(X)=-\sum _{x\in {\mathcal {X}}}p(x)\log _{2}p(x)}$ et se mesure en bits par symbole^[17].

Shannon a montré que cette entropie fixe la limite de la compression sans perte. En moyenne, aucun codage ne peut représenter une source avec moins de ${\displaystyle H(X)}$ bits par symbole, si bien qu'un message de ${\displaystyle n}$ symboles ne peut être ramené, en moyenne, sous ${\displaystyle n\times H(X)}$ bits^[17].

À l'échelle d'un symbole, la taille idéale d'un symbole de probabilité ${\displaystyle p}$ est de ${\displaystyle -\log _{2}p}$ bits, valeur qui descend sous 1 bit dès que le symbole est fréquent^[1]. Un codage à nombre entier de bits par symbole, comme celui de Huffman, ne peut l'atteindre, là où le codage arithmétique, qui code le message entier en une seule fois, n'arrondit pas ce coût symbole par symbole^[15].

La longueur moyenne par symbole obtenue par le codage arithmétique, notée ${\displaystyle \ell }$, est encadrée par ${\displaystyle H(X)\leq \ell \leq H(X)+{\frac {2}{n}}}$. L'écart à l'entropie vaut au plus 2 bits pour le message entier. Réparti sur les ${\displaystyle n}$ symboles, il devient négligeable lorsque le message s'allonge. Le codage arithmétique est ainsi qualifié d'asymptotiquement optimal : sa longueur moyenne par symbole tend vers l'entropie quand la longueur du message tend vers l'infini^[11].

Le codage de Huffman, lui, n'atteint l'entropie que dans un cas particulier : lorsque toutes les probabilités des symboles sont des puissances de deux, c'est-à-dire de la forme ${\displaystyle 2^{-k}}$. La taille idéale ${\displaystyle -\log _{2}p}$ de chaque symbole est alors un entier, les deux méthodes produisent un code de même longueur et sont toutes deux optimales^[11],[17].

L'algorithme décrit jusqu'ici reste le socle commun à toutes les variantes. Sa mise en pratique a toutefois demandé des ajustements, que l'on peut séparer en raffinements présents dans la plupart des implémentations modernes et en variantes propres à certaines sous-familles.

Décrit tel quel, le codage arithmétique représente les bornes de l'intervalle par des nombres dont la précision augmente à chaque symbole ajouté, au-delà de ce que les types numériques de taille fixe d'un ordinateur peuvent contenir. Pour ramener le calcul à une précision fixe, par exemple 16 ou 32 bits, deux mécanismes complémentaires interviennent, la renormalisation et la sortie incrémentale. La renormalisation agrandit l'intervalle, le plus souvent par des décalages de bits vers la gauche, lorsqu'il devient trop petit pour conserver assez de précision dans les registres. La sortie incrémentale transmet les chiffres de poids fort dès qu'ils sont identiques pour les deux bornes, sans attendre la fin du message, ce qui évite de saturer la mémoire.

Par exemple, en décimal, les deux bornes d'un intervalle [0,235 ; 0,243[ commencent par le même chiffre de poids fort. Le codeur émet ce 2, décale les décimales vers la gauche et poursuit avec l'intervalle [0,35 ; 0,43[^[18].

Ce procédé impose deux gestions particulières. D'une part les reports de retenue, lorsqu'une addition modifie un chiffre déjà émis et doit se propager vers la gauche. D'autre part les situations où les deux bornes encadrent durablement le milieu de l'intervalle de travail sans qu'aucun chiffre de poids fort ne se fixe, ce qui bloque toute sortie tant qu'elles ne sont pas résolues^[16].

Un autre raffinement porte sur le modèle de probabilités. Plutôt que d'utiliser une table fixée à l'avance, le codage arithmétique adaptatif met à jour les probabilités au fil des symboles rencontrés, en fonction de ceux déjà lus, le décodeur appliquant les mêmes mises à jour pour rester synchronisé. Le codage colle ainsi aux statistiques réelles du message, y compris lorsqu'elles évoluent en cours de route. Cette adaptation dispense de plus de transmettre la table de probabilités, puisque le décodeur la reconstitue de lui-même^[19].

Enfin, beaucoup d'implémentations acceptent une légère perte de compression en échange de calculs plus simples et plus rapides, par exemple en approchant la subdivision de l'intervalle pour éviter les multiplications coûteuses^[16].

La plupart des variantes du codage arithmétique reprennent l'emboîtement d'intervalles décrit plus haut et n'en changent que la mise en œuvre, par le type de nombres employés, la taille de l'alphabet ou la façon d'estimer les probabilités. Elles forment ainsi une famille de cousines, chacune ajustée à un usage particulier, plutôt que des méthodes concurrentes.

Le codage par intervalle (range coding), proposé indépendamment en 1979 par Nigel Martin, mène le même calcul en arithmétique entière plutôt qu'avec des nombres compris entre 0 et 1. Il peut produire sa sortie dans n'importe quelle base, souvent octet par octet, ce qui le rend rapide sur les processeurs courants. Martin note lui-même, après coup, que sa méthode est très proche des travaux contemporains de Rissanen^[20].

Les codeurs binaires d'IBM restreignent l'alphabet à un seul bit, 0 ou 1. Sur un alphabet aussi réduit, la subdivision de l'intervalle se ramène à des additions et des décalages de bits, sans multiplication, et la probabilité du bit est estimée de façon adaptative. Le premier, le Q-Coder, a donné naissance au QM-Coder, retenu pour la norme JBIG et pour le mode arithmétique de JPEG, puis au MQ-Coder, retenu pour JPEG 2000^[7],[18].

Le codage arithmétique binaire adaptatif à base de contexte (context-based adaptive binary arithmetic coding, CABAC) spécialise cette approche binaire pour la vidéo. Il procède en trois temps : une binarisation qui ramène chaque élément à une suite de bits, une modélisation par contexte qui choisit la probabilité d'un bit selon les bits déjà codés, et un moteur de codage sans multiplication, le codeur modulo (M coder). CABAC équipe la norme H.264/AVC et ses successeurs comme H.265^[12],[11].

Les systèmes de numération asymétrique (asymmetric numeral systems, ANS), proposés par Jarek Duda à partir de 2007, forment la cousine la plus éloignée. Au lieu de suivre un intervalle défini par deux bornes, ils représentent le message par un unique entier, l'état, ce qui simplifie la renormalisation et accélère le traitement. Deux variantes principales coexistent, le rANS, qui calcule l'état par une formule, et le tANS, qui le lit dans une table préétablie. L'ensemble atteint une compression proche de celle du codage arithmétique pour une vitesse proche de celle de Huffman^[14],[13].

• Image : le fax s'appuie sur la norme JBIG, qui code les images noir et blanc en utilisant le QM-coder^[9]. JPEG propose en option ce même codeur d'IBM, plus efficace que Huffman de l'ordre de 5 à 10 %, mais optionnel et rarement présent dans les bibliothèques car plus complexe à implémenter, et soumis à des brevets, aujourd'hui expirés^[21],[8]. JBIG2, employée pour comprimer les documents numérisés, utilise quant à elle le MQ-coder^[10]. JPEG 2000 y recourt cette fois exclusivement pour comprimer les coefficients d'ondelettes, ce qui lui vaut un meilleur taux de compression que le JPEG d'origine et des usages en imagerie médicale, au cinéma et dans la vidéo. Sa complexité, qui réclame souvent des circuits dédiés, a toutefois freiné son adoption^[18]. Le dernier-né de la famille, JPEG XL, retient le rANS^[13]. Pour l'archivage de documents, le format DjVu repose sur un autre codeur arithmétique binaire, le Z-coder.

• Vidéo : les normes H.264/AVC et H.265/HEVC confient le codage entropique à CABAC, qui s'appuie sur le codeur modulo (M coder) pour atteindre les taux de compression qu'exige la haute définition^[11]. H.263 offrait déjà un codeur arithmétique en option, dans son annexe E, mais encore tributaire de multiplications (donc plus lent), et reposant sur des probabilités statiques, c'est-à-dire non adaptatives^[12]. Le standard AV1, plus récent, emploie un codeur arithmétique multi-symboles hérité du codec Daala^[22].

• Compression générale : LZMA, l'algorithme par défaut de 7-Zip, repose sur un codage par intervalle et privilégie le taux de compression^[21]. PPM (prediction by partial matching), particulièrement efficace sur le texte, s'appuie lui aussi sur un codeur arithmétique pour produire sa sortie et est proposé par 7-Zip^[23]. L'implémentation FSE du tANS a donné naissance à LZFSE, créé par Apple, et à Zstandard, créé par Facebook, ce dernier étant libre et désormais présent dans le noyau Linux, Hadoop, MySQL et FreeBSD. Le rANS, autre variante des systèmes de numération asymétrique, équipe pour sa part la bibliothèque Draco de Google^[13].

• Codage entropique
• Codage de Huffman
• Compression de données
• Entropie de Shannon
• JPEG 2000
• H.264

• Jean-Guillaume Dumas et al., Théorie des codes : compression, cryptage, correction, Dunod, coll. « Info sup », 2018 (ISBN 978-2-10-078109-6)
• Mark Nelson (trad. de l'anglais par Hervé Soulard), La Compression de données : textes, images et sons, Dunod, 1993, 421 p. (ISBN 2-10-001681-4)

• Portail de l’informatique