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 :

  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 ».

Autres langues