Codage de Fibonacci

 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 (1, 2, 3, 5, 8...) 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 :

Suite de Fibonacci	1	2	3	5	8	13	21	34
Présence dans la décomposition	0	0	1	0	0	1	0	1

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

Codage de Fibonacci - Binaire - Decoder, Encoder en Ligne (dcode.fr)

Nombres Fibonacci