Codage de fibonacci
- Codage de fibonacci
-
Codage de Fibonacci
Le code de Fibonacci est un code universel qui encode les nombres entiers en mots de code binaire. La séquence « 11 » apparaît uniquement en fin de chaque nombre encodé, et délimite ainsi les nombres. Le code commence comme ci-dessous :
1 11
2 011
3 0011
4 1011
5 00011
6 10011
7 01011
8 000011
9 100011
10 010011
11 001011
12 101011
Pour encoder un entier X :
- Trouver le plus grand nombre de Fibonacci inférieur ou égal à X ; soustraire ce nombre de X, garder le reste.
- Si le nombre que nous avons utilisé pour la soustraction était le Nième nombre de Fibonacci, mettre un 1 dans le Nième chiffre de notre résultat.
- Répéter les étapes précédentes, en remplaçant le X par notre reste, jusqu'à ce que nous trouvions un reste égal à 0.
- Placer un 1 après le dernier 1 apparaissant naturellement dans notre résultat.
Pour décoder une marque dans le code, enlever le dernier « 1 », assigner aux bits restants les valeurs 1, 2, 3, 5, 8, 13, ... (les nombres de Fibonacci), et additionner les valeurs assignées aux bits « 1 ».
Catégories : Numération | Algorithme de compression sans perte
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Codage de fibonacci de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Codage De Fibonacci — Le code de Fibonacci est un code universel qui encode les nombres entiers en mots de code binaire. La séquence « 11 » apparaît uniquement en fin de chaque nombre encodé, et délimite ainsi les nombres. Le code commence comme ci… … Wikipédia en Français
Codage de Fibonacci — Le codage de Fibonacci est un codage entropique utilisé essentiellement en compression de données. Il utilise les nombres de la suite de Fibonacci, dont les termes ont la particularité d être composés de la somme des deux termes consécutifs… … 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 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 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 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 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
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 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
