Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Codage de Fibonacci
Résumé
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 chaque terme est la somme des deux termes consécutifs précédents, ce qui lui confère une robustesse aux erreurs.
Le code de Fibonacci produit est un code préfixe et universel.
Dans ce code, on utilise la représentation de Zeckendorf, de telle façon que la séquence « 11 », interdite dans le nombre, apparaisse uniquement en fin de codage, et serve ainsi de délimiteur.
Pour coder un entier X :
Créer un tableau avec 2 lignes.
Dans la , mettre les éléments de la suite de Fibonacci (1, 2, 3, 5, 8...) inférieurs ou égaux à X.
Décomposer l'entier X en une somme d'entiers correspondant aux éléments de la du tableau, en employant les plus grands possibles.
Dans la du tableau, mettre des « 1 » en dessous des éléments qui ont permis de décomposer X, « 0 » sinon.
Écrire la du tableau en rajoutant un « 1 » pour terminer.
Exemple
décomposition de 50.
Les éléments de la du tableau (ou poids) sont : 1 2 3 5 8 13 21 34
50 = 34 + 13 + 3 (50 = 34 + 8 + 5 + 3 est incorrect car le 13 n'a pas été utilisé)
D'où le tableau :
Il reste à écrire le codage du nombre 50 en ajoutant le terminateur : 00100101
normalisation d'une décomposition exacte non conforme
la décomposition 50 = 21+13+8+5+3, donnerait une représentation brute 00111110 qu'on peut normaliser en considérant que, tout poids étant la somme des deux précédents, 110 = 001 au sein de la représentation. Donc 001'11 = 001''01 = 001'001'01, représentation correcte au sens de Zeckendorf. En ajoutant maintenant le "1" terminateur, on obtient encore 00100101
Pour effectuer l'opération inverse, il suffit de supprimer le "1" de fin, puis de reporter les "0" et les "1" au fur et à mesure qu'on les rencontre dans la du tableau, et enfin d'effectuer la somme des éléments de la comportant des "1".
Premier exemple Décoder le nombre 10001010011
On enlève le dernier "1" puis on reporte les "0" et les "1" restants dans le tableau suivant :
On effectue la somme : 1 + 8 + 21 + 89 = 119
Le code 10001010011 désigne donc l'entier 119 selon le codage de Fibonacci.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.