Codage de Fibonacci - Définition

Le code de Fibonacci est un code universel qui encode les nombres entiers en mots de code binaire. La séquence " 11 " apparaît uniquement en fin de chaque nombre encodé, et délimite ainsi les nombres. Le code commence comme ci-dessous :

1  11
2  011
3  0011
4  1011
5  00011
6  10011
7  01011
8  000011
9  100011
10 010011
11 001011
12 101011

Pour encoder un entier X :

1. Trouver le plus grand nombre de Fibonacci inférieur ou égal à X ; soustraire ce nombre de X, garder le reste.
2. Si le nombre que nous avons utilisé pour la soustraction était le Nième nombre de Fibonacci, mettre un 1 dans le Nième chiffre de notre résultat.
3. Répéter les étapes précédentes, en remplaçant le X par notre reste, jusqu'à ce que nous trouvions un reste égal à 0.
4. Placer un 1 après le dernier 1 apparaissant naturellement dans notre résultat.

Pour décoder une marque dans le code, enlever le dernier " 1 ", assigner aux bits restants les valeurs 1, 2, 3, 5, 8, 13, ... (les nombres de Fibonacci), et additionner les valeurs assignées aux bits " 1 ".