codage de Fibonacci

ANALYSE
ARITHMETIQUE

Le codage de Fibonacci est utilisé en compression de données.
Il utilise des nombres de la suite de Fibonacci et s’appuie sur le théorème de Zeckendorf .

Pour coder un entier : * on le décompose en une somme de nombres de Fibonacci en choisissant toujours les nombres les plus grands possibles (exemple on choisit 50 = 34 + 13 + 3 et non pas 50 = 34 + 8 + 5 +3).
* On construit un tableau à 2 lignes, dans la première on écrit la suite des nombres de Fibonacci (dans l’ordre croissant de gauche à droite), dans la seconde ligne on écrit 1 en dessous des éléments de la décomposition, 0 en dessous des autres Remarquons qu’il ne peut pas y avoir des 1 consécutifs. Pour 50 on obtient 00100101 .
* Pour terminer on ajoute 1 à la fin de la liste. Le codage de 50 est donc 001001011.
On remarque que c’est seulement à la fin qu’il y a un double 1 .
* Pour décoder une longue liste de 1 et de 0, on commence par repérer les doubles 1, ce qui permet de séparer les différents nombres, puis pour chaque nombre on rétablit le tableau du type ci-dessus