Codage de Fibonacci

Pour les articles homonymes, voir 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 :

1. Créer un tableau avec 2 lignes.
2. Dans la 1^re, mettre les éléments de la suite de Fibonacci à partir du terme ${\displaystyle F_{2}}$ (1, 2, 3, 5, 8...) et inférieurs ou égaux à X.
3. Décomposer l'entier X en une somme d'entiers correspondant aux éléments de la 1^re ligne du tableau, en employant les plus grands possibles.
4. Dans la 2^e ligne du tableau, mettre des « 1 » en dessous des éléments qui ont permis de décomposer X, « 0 » sinon.
5. Écrire la 2^e ligne du tableau en rajoutant un « 1 » pour terminer.

Exemple

décomposition de 50.

Les éléments de la 1^re ligne 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 : 001001011

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'111'10 = 001'110'01 = 001'001'01, représentation correcte au sens de Zeckendorf. En ajoutant maintenant le "1" terminateur, on obtient encore 001001011

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 2^e ligne du tableau, et enfin d'effectuer la somme des éléments de la 1^re ligne 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.

Deuxième exemple

Décoder le nombre 1011001111

Si on enlève le dernier "1" puis que l'on reporte les "0" et les "1" restants dans le tableau de décodage, on obtient :

On effectue la somme : 1 + 3 + 5 + 21 + 34 + 55 = 119

Or, le codage de Fibonacci est unique, le code 1011001111 contient en réalité trois séquences codées, celles-ci sont caractérisées par la suite de deux « 1 » successifs : « 11 »

On décompose :

On enlève les '1' de la fin,

On les place dans le tableau et on fait les sommes :

Le code 1011001111 représente les nombres 4, 3 et 1 selon le codage de Fibonacci.

On remarquera que tous les nombres de la suite de Fibonacci ont pour code "0[n-1 fois]11" où n est le rang du nombre dans la suite de Fibonacci.

Comme pour les codages d'Elias (en), il est possible de coder des entiers relatifs avec le codage de Fibonacci en utilisant une bijection pour transformer les nombres négatifs ou nul en nombres strictement positifs avant le codage à proprement parler. Après le décodage, l'opération inverse doit être effectuée pour retrouver les entiers relatifs d'origine.

Le code est un code binaire dont les poids croissent en gros comme les puissances de 1,618 (nombre d'or). Il demande environ 5 bits par chiffre décimal.

Ce codage ne résiste pas à une analyse fréquentielle (une lettre est toujours représentée par la même suite binaire).

Représentation des premiers entiers naturels strictement positifs avec un codage de Fibonacci

Décimal	Décomposition de Fibonacci		Code de Fibonacci
1	1	${\displaystyle F_{2}}$	1 1
2	2	${\displaystyle F_{3}}$	01 1
3	3	${\displaystyle F_{4}}$	001 1
4	1 + 3	${\displaystyle F_{2}+F_{4}}$	1 01 1
5	5	${\displaystyle F_{5}}$	0001 1
6	1 + 5	${\displaystyle F_{2}+F_{5}}$	1 001 1
7	2 + 5	${\displaystyle F_{3}+F_{5}}$	01 01 1
8	8	${\displaystyle F_{6}}$	00001 1
9	1 + 8	${\displaystyle F_{2}+F_{6}}$	1 0001 1
10	2 + 8	${\displaystyle F_{3}+F_{6}}$	01 001 1
11	3 + 8	${\displaystyle F_{4}+F_{6}}$	001 01 1
12	1 + 3 + 8	${\displaystyle F_{2}+F_{4}+F_{6}}$	1 01 01 1

• Suite de Fibonacci
• Base d'or
• Codage entropique
• Compression de données
• Théorème de Zeckendorf

• Portail de l’informatique