Codage de Rice

Le codage de Rice d'un entier naturel ${\displaystyle N}$ dépend d'un paramètre ${\displaystyle k}$ et se fait en deux étapes :

1. le codage du quotient de la division euclidienne de ${\displaystyle N}$ par ${\displaystyle 2^{k}}$ avec un codage unaire ;
2. le codage du reste de la même division avec un codage binaire sur ${\displaystyle k}$ bits.

Le codage de Rice de paramètre ${\displaystyle k}$ est strictement équivalent à un codage de Golomb de paramètre ${\displaystyle 2^{k}}$.

Mathématiquement, pour coder un entier ${\displaystyle N,N\in \mathbb {N} ,N=q\times 2^{k}+r}$, on code d'abord ${\displaystyle q=\lfloor N/2^{k}\rfloor }$ en unaire, puis ${\displaystyle r=N-2^{k}\times q}$ en binaire.

La division par ${\displaystyle 2^{k}}$ peut être implémentée par un décalage de ${\displaystyle k}$ bits vers la droite, et la seconde étape revient à répliquer les ${\displaystyle k}$ bits de poids faible de la valeur à coder. Ces opérations simples font que le codage de Rice est particulièrement adapté pour une implémentation rapide.

La longueur du code d'un entier ${\displaystyle N}$ en bits est : ${\displaystyle L(N,k)=\lfloor N/2^{k}\rfloor +1+k}$.

Le codage de Rice est adapté pour des données dans lesquelles les valeurs les plus faibles sont plus probables que les autres (mais où les autres peuvent malgré tout apparaitre).

Il est particulièrement apprécié en informatique car son implémentation est simple et rapide.

Le choix du paramètre ${\displaystyle k}$ utilisé lors du codage de Rice détermine le taux de compression qu'il est possible d'obtenir.

Le paramètre optimal ${\displaystyle k_{opt}}$ pour coder ${\displaystyle V}$ valeurs sur un intervalle de taille ${\displaystyle I}$ est exprimé par :

${\displaystyle k_{opt}=-\left\lceil {\dfrac {log_{2}\left(2-{\dfrac {V}{I}}\right)}{log_{2}\left(1-{\dfrac {V}{I}}\right)}}\right\rceil }$

Le codage de Rice fait partie des codages entropiques les plus utilisés, lorsque les données à compresser présentent une distribution géométrique (ou approchante) et que la vitesse de l'algorithme est un critère important.

On le retrouve notamment dans de nombreux algorithmes de compression multimédia : audio (FLAC, Monkey's Audio, MPEG-4 ALS, ALAC...), vidéo, image... et dans certains algorithmes de compression d'index[1] (pour les moteurs de recherche).