Codage unaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le codage unaire est un codage entropique utilisé essentiellement en compression de données et s'appuyant sur la base 1.

Principe[modifier | modifier le code]

Chaque symbole est assimilé à un entier naturel n et est représenté par n occurrences de 1 (la représentation de l'entier naturel en base 1) suivies d'un 0 faisant office de délimiteur. Le codage unaire produit donc un code préfixe.

Représentation des premiers entiers naturels avec différents codes
Base 1 Unaire Binaire
(sur 8 bits)
Décimal Nombre de Church
0 0000 0000 0 λ f  · λ x  · x
1 10 0000 0001 1 λ f  · λ x  · f x
11 110 0000 0010 2 λ f  · λ x  · f (f x)
111 1110 0000 0011 3 λ f  · λ x  · f (f (f x))
1111 1 1110 0000 0100 4 λ f  · λ x  · f (f (f (f x)))
1 1111 11 1110 0000 0101 5 λ f  · λ x  · f (f (f (f (f x))))

Longueur du code[modifier | modifier le code]

La longueur L du code unaire associé à un entier naturel N peut être exprimée par :

L = N + 1

Optimalité[modifier | modifier le code]

Le codage unaire est optimal au niveau du symbole pour coder une source dont la distribution est non uniforme et suit la loi de probabilité :

p(x)=2^{-x-1}

Autrement dit, ce code est optimal lorsque la probabilité de coder un 0 est de \tfrac1 2, celle de coder un 1 de \tfrac1 4, celle de coder un 2 de \tfrac1 8...

Dans ce cas, le code produit est identique au code de Shannon-Fano ou au code de Huffman équivalent. Un codage arithmétique, optimal au niveau du bit, pourra cependant produire un code encore plus court.

Utilisations[modifier | modifier le code]

Le codage unaire est rarement utilisé seul, un codage de Huffman étant dans le pire des cas aussi efficace et dans tous les autres cas meilleurs.

Il demeure cependant intéressant du fait de sa simplicité et de sa rapidité, et est notamment utilisé pour le codage du quotient lors d'un codage de Golomb ou d'un codage de Rice. Ces deux techniques sont d'ailleurs équivalentes au codage unaire lorsque leur paramètre est 1.

Le codage unaire sert également pour coder le nombre de bits nécessaires pour coder un entier en binaire lors d'un codage gamma (et aussi, du coup, lors d'un codage delta).

Analogies[modifier | modifier le code]

La représentation des entiers naturels par le codage de Church, utilisé en lambda-calcul est assimilable à un codage unaire.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]