Codage unaire

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

Sommaire

1 Principe

2 Longueur du code

3 Optimalité

4 Utilisations

5 Analogies

6 Voir aussi

6.1 Articles connexes

Principe

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 \cdot λ x \cdot x$

1 10 0000 0001 1 $λ f \cdot λ x \cdot f x$

11 110 0000 0010 2 $λ f \cdot λ x \cdot f (f x)$

111 1110 0000 0011 3 $λ f \cdot λ x \cdot f (f (f x))$

1111 1 1110 0000 0100 4 $λ f \cdot λ x \cdot f (f (f (f x)))$

1 1111 11 1110 0000 0101 5 $λ f \cdot λ x \cdot f (f (f (f (f x))))$

Longueur du code

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

$L = N + 1$

Optimalité

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

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

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

Voir aussi

Articles connexes

Système unaire

Codage entropique

Compression de données

v · d · m

Techniques de compression de données

Sans perte

Codage entropique Unaire · Binaire tronqué · Gamma · Delta · Omega · Zeta · Fibonacci · Levenshtein · Even-Rodeh · Stout · Golomb · Rice · Exp-Golomb · Shannon-Fano · Huffman · Shannon-Fano-Elias · Arithmétique · Par intervalle

Dictionnaire LZ77 · LZ78 · LZSS · LZW · LZO

Modélisation de contextes Modélisation de Markov dynamique (DMC) · Prédiction par reconnaissance partielle (PPM) · Pondération de contextes (CM) · Pondération de contextes arborescents (CTW)

Techniques hybrides Implode · Deflate · LZP · LZMA · ROLZ

Autres Codage par plage (RLE)

Transformations Codage différentiel (Delta) · Transformée en étoile · MTF · Transformée de Burrows-Wheeler (BWT) · Transformée par substitution de mots (WRT) · BCJ2

Avec pertes

Codage par transformation Compression par ondelettes

Autres Modulation par impulsions et codage différentiel adaptatif (ADPCM) · Compression fractale

Transformations Transformée de Karhunen-Loève (KLT) · Transformée en cosinus discrète (DCT) · Transformée de Fourier discrète (DFT) · Transformée en ondelettes discrète (DWT)

Portail de l’informatique

Catégories :
Codage entropique
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 \cdot λ x \cdot x$
1	10	0000 0001	1	$λ f \cdot λ x \cdot f x$
11	110	0000 0010	2	$λ f \cdot λ x \cdot f (f x)$
111	1110	0000 0011	3	$λ f \cdot λ x \cdot f (f (f x))$
1111	1 1110	0000 0100	4	$λ f \cdot λ x \cdot f (f (f (f x)))$
1 1111	11 1110	0000 0101	5	$λ f \cdot λ x \cdot f (f (f (f (f x))))$

Contenu soumis à la licence CC-BY-SA. Source : Article Codage unaire de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

Codage gamma — Le codage gamma ou codage gamma d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code gamma produit est un code préfixe et universel. Sommaire 1 Principe 2 Codage des entiers… … Wikipédia en Français
Codage de Rice — Le codage de Rice, codage de Golomb Rice ou GPO2 (pour Golomb power of 2) est un codage entropique inventé par Robert F. Rice et James R. Plaunt en 1971 et utilisé essentiellement en compression de données. Le code produit est un code préfixe.… … Wikipédia en Français
Codage de Golomb — Le codage de Golomb est un codage entropique inventé par Solomon Wolf Golomb en 1966 et utilisé essentiellement en compression de données. Le code produit est un code préfixe. Sommaire 1 Principe 2 Longueur du code 3 Optimalité … Wikipédia en Français
Codage zeta — Le codage zeta ou codage de Boldi Vigna est un codage entropique inventé par Paolo Boldi et Sebastiano Vigna en 2003 et utilisé essentiellement en compression de graphes. Le code zeta produit est un code préfixe et universel. Sommaire 1 Principe… … Wikipédia en Français
Codage delta — Pour les articles homonymes, voir Code Delta (émission de télévision). Le codage delta ou codage delta d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code delta produit est un… … Wikipédia en Français
Codage omega — Le codage omega ou codage omega d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code omega produit est un code préfixe et universel. Sommaire 1 Principe 1.1 Codage 1.2 Décodage … Wikipédia en Français
Codage de Levenshtein — Le codage de Levenshtein est un codage entropique inventé par Vladimir Levenshtein en 1968 et utilisé essentiellement en compression de données. Le code de Levenshtein produit est un code préfixe et universel. Sommaire 1 Principe 2 Longueur du… … Wikipédia en Français
Codage entropique — Le codage entropique (ou codage statistique à longueur variable) est une méthode de codage de source sans pertes, dont le but est de transformer la représentation d une source de données pour sa compression et/ou sa transmission sur un canal de… … Wikipédia en Français
Codage de Huffman — Le codage de Huffman est un algorithme de compression de données sans perte élaboré par David Albert Huffman, lors de sa thèse de doctorat au MIT. L algorithme a été publié en 1952 dans l article A Method for the Construction of Minimum… … Wikipédia en Français
Codage binaire tronqué — Le codage binaire tronqué 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… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Codage unaire

Sommaire

Principe

Longueur du code

Optimalité

Utilisations

Analogies

Voir aussi

Articles connexes

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Codage unaire

Sommaire

Principe

Longueur du code

Optimalité

Utilisations

Analogies

Voir aussi

Articles connexes

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link