codage de Fibonacci

Prenons le nombre 50 et une rangée de valeurs de Fibonacci : 1, 2, 3, 5, 8, 13, 21, 34. On coche 34, 13 et 3, car leur somme vaut 50. Sous ces valeurs, les coches deviennent des 1 et les autres places des 0.

Deux valeurs voisines de la rangée ne sont jamais cochées ensemble. On ajoute enfin un 1 au mot obtenu. Les deux 1 de la fin signalent alors où s'arrête ce nombre dans une suite de codes.

Le codage de Fibonacci est un code binaire pour les entiers strictement positifs. Il utilise les poids 1, 2, 3, 5, 8, 13, etc., c'est-à-dire les nombres de Fibonacci à partir du second 1, sans répéter le poids 1. Le théorème de Zeckendorf garantit que chaque entier positif possède une unique décomposition en somme de tels poids non consécutifs. Pour un entier noté n, le coefficient b_k vaut 1 lorsque le poids de Fibonacci F_k est retenu, et 0 sinon. L'indice m désigne celui du plus grand poids retenu.

La dernière condition interdit deux poids consécutifs. Les bits b₂, b₃, … sont écrits par poids croissants jusqu'au dernier bit égal à 1. On leur ajoute un bit 1 : le code complet se termine donc par 11. Comme la partie issue de Zeckendorf ne contient jamais 11, ce suffixe sert de séparateur lors du décodage de codes concaténés.

On veut coder l'entier 50. Les poids disponibles, dans l'ordre croissant, sont 1, 2, 3, 5, 8, 13, 21 et 34.

1. Le plus grand poids inférieur ou égal à 50 est 34. Le reste vaut 50 − 34 = 16.

2. Le plus grand poids inférieur ou égal à 16 est 13. Le nouveau reste vaut 16 − 13 = 3.

3. On retient 3, puis le reste devient nul. La décomposition obtenue est 50 = 34 + 13 + 3.

4. Sous les poids 1, 2, 3, 5, 8, 13, 21, 34, on écrit respectivement 0, 0, 1, 0, 0, 1, 0, 1. La partie significative est donc 00100101.

5. On ajoute le bit terminal 1. Le codage de 50 est 001001011. Pour contrôler, les 1 internes redonnent 3 + 13 + 34 = 50, aucun n'est voisin d'un autre, et le seul 11 apparaît à la fin.

Pour encoder un entier positif, on soustrait successivement le plus grand poids de Fibonacci qui ne dépasse pas le reste. Le calcul s'arrête lorsque le reste vaut zéro, puis les poids retenus deviennent des bits 1.

Pour décoder un mot, on retire son 1 terminal et on additionne les poids associés aux bits 1 restants. Dans un flux concaténé, on lit jusqu'au premier 11 : ce couple ferme le mot courant.

Ce code convient lorsque les petites valeurs sont fréquentes, car sa longueur varie avec l'entier et aucun séparateur externe n'est nécessaire. Un code à longueur fixe reste préférable si l'accès direct à chaque mot ou une taille constante prime.

Décomposition de Zeckendorf. Elle exprime un entier comme somme de nombres de Fibonacci non consécutifs ; le codage de Fibonacci transforme cette décomposition en bits et ajoute un 1 terminal. Ainsi, 50 = 34 + 13 + 3 est une décomposition, tandis que 001001011 est le code correspondant.

Écriture binaire usuelle. Elle utilise des puissances de 2 comme poids et ne possède pas, par elle-même, le suffixe terminal 11. Le nombre 50 s'écrit 110010 en base 2, mais 001001011 en codage de Fibonacci.

Zéro. La convention décrite porte sur les entiers strictement positifs. Le mot correspondant à zéro n'est donc pas défini par cette règle ; un protocole qui doit représenter zéro doit annoncer une convention supplémentaire.

Double 1 placé trop tôt. Dans un mot valide isolé, 11 n'apparaît qu'à la fin. Si le lecteur rencontre 11, il doit arrêter le mot à ce second 1, et non continuer à lui attribuer des poids.

Deux poids consécutifs choisis. Une suite comme 011… prétend retenir 2 et 3 simultanément. Elle ne suit pas la décomposition de Zeckendorf, car 2 + 3 doit être remplacé par 5 avant de former le code.

Convention sur le début de la suite. La suite de Fibonacci contient habituellement deux termes égaux à 1, mais le codage emploie les poids 1, 2, 3, 5, … . Conserver les deux 1 détruirait l'unicité de la lecture des poids.

Le théorème de Zeckendorf établit l'existence et l'unicité de la décomposition qui fournit les bits du code.

La suite de Fibonacci précise la construction des poids 1, 2, 3, 5, 8, … employés pour représenter les entiers.