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 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.

À 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.

Concepts associés (3)

Cours associés (2)

Séances de cours associées (48)

Codage de Fibonacci

Suite de Fibonacci

vignette|Une juxtaposition de carrés dont les côtés ont pour longueur des nombres successifs de la suite de Fibonacci : 1, 1, 2, 3, 5, 8, 13 et 21. En mathématiques, la suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Notée , elle est définie par , et pour . Les termes de cette suite sont appelés nombres de Fibonacci et forment la : vignette|Représentation géométrique de la fraction continue de φ faisant apparaître les nombres de la suite de Fibonacci.

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

MATH-111(e): Linear Algebra

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et ses applications.

Logique et algorithmes CS-101: Advanced information, computation, communication I

Couvre la logique, le raisonnement mathématique, les structures de base et les algorithmes, explorant les preuves, les ensembles, les fonctions et la récursion.

Stabilité du point fixe Feigenbaum

Explore la stabilité du point fixe Feigenbaum avec une criticité infinie et ses applications dans la théorie du chaos.

Relations, séquences, sommation CS-101: Advanced information, computation, communication I

Couvre les progressions arithmétiques, les treillis, la vérification formelle, les chaînes, les formules explicites, les relations de récurrence, les formules fermées et l'argument Diagonal de Cantor.