Codage de Fibonacci
Un article de Wikipédia, l'encyclopédie libre.
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 :
- Trouver le plus grand nombre de Fibonacci inférieur ou égal à X ; soustraire ce nombre de X, garder le reste.
- 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.
- 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.
- 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 ».