Le codage de Fibonacci est un codage entropique utilisé essentiellement en compression de données. Il utilise les nombres de la suite de Fibonacci, dont les termes ont la particularité d'être composés de la somme des deux termes consécutifs précédents, ce qui lui confère une robustesse aux erreurs.
Le code de Fibonacci produit est un code préfixe et universel. Dans ce code, la séquence « 11 » apparaît uniquement en fin de chaque nombre encodé, et sert ainsi de délimiteur.
Pour encoder un entier X :
Exemple
décomposition de 50.
Les éléments de la 1 ligne du tableau sont : 1 2 3 5 8 13 21 34
50 = 34 + 13 + 3 (50 = 34 + 8 + 5 + 3 est incorrect car le 13 n'a pas été utilisé)
D'où le tableau :
| Suite de Fibonacci | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |
|---|---|---|---|---|---|---|---|---|
| Présence dans la décomposition | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
Pour effectuer l'opération inverse, il suffit de supprimer le "1" de fin, puis de reporter les "0" et les "1" au fur et à mesure qu'on les rencontre dans la 2ème ligne du tableau, et enfin d'effectuer la somme des éléments de la 1ère ligne comportant des "1".
Premier exemple
Décoder le nombre 10001010011
On enlève le dernier "1" puis on reporte les "0" et les "1" restants dans le tableau suivant :
| Suite de Fibonacci | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
|---|---|---|---|---|---|---|---|---|---|---|
| Présence dans la décomposition | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
On effectue la somme : 1 + 8 + 21 + 89 = 119
Le code 10001010011 désigne donc l'entier 119 selon le codage de Fibonacci.
Deuxième exemple
Décoder le nombre 1011001111
Si on enlève le dernier "1" puis que l'on reporte les "0" et les "1" restants dans le tableau de décodage, on obtient :
| Suite de Fibonacci | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
|---|---|---|---|---|---|---|---|---|---|
| Présence dans la décomposition | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
On effectue la somme : 1 + 3 + 5 + 21 + 34 + 55 = 119
Or, le codage de Fibonacci est unique, le code 1011001111 contient en réalité trois séquences codées, celles-ci sont caractérisées par la suite de deux « 1 » successifs : « 11 »
On décompose:
| 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 |
| 1 | 1 |
On enlève les '1' de la fin,
| 1 | 0 | 1 |
| 0 | 0 | 1 |
| 1 |
On les place dans le tableau et on fait les sommes :
| Suite de Fibonacci | 1 | 2 | 3 | 5 | Somme |
|---|---|---|---|---|---|
| Présence dans la décomposition | 1 | 0 | 1 | 1 + 3 = 4 | |
| Présence dans la décomposition | 0 | 0 | 1 | 3 = 3 | |
| Présence dans la décomposition | 1 | 1 = 1 |
Le code 1011001111 représente les nombres 4, 3 et 1 selon le codage de Fibonacci.
On remarquera que tous les nombres de la suite de Fibonacci sont codés selon le modèle "0[n-1 fois]11" où n est le rang du nombre dans la suite de Fibonacci.
Comme pour les codages d'Elias, il est possible de coder des entiers relatifs avec le codage de Fibonacci en utilisant une bijection pour transformer les nombres négatifs ou nul en nombres strictement positifs avant le codage à proprement parler. Après le décodage, l'opération inverse doit être effectuée pour retrouver les entiers relatifs d'origine.
| Décimal | Décomposition de Fibonacci | Code de Fibonacci | |
|---|---|---|---|
| 1 | 1 | f(1) | 1 1 |
| 2 | 2 | f(2) | 01 1 |
| 3 | 3 | f(3) | 001 1 |
| 4 | 1 + 3 | f(1) + f(3) | 1 01 1 |
| 5 | 5 | f(4) | 0001 1 |
| 6 | 1 + 5 | f(1) + f(4) | 1 001 1 |
| 7 | 2 + 5 | f(2) + f(4) | 01 01 1 |
| 8 | 8 | f(5) | 00001 1 |
| 9 | 1 + 8 | f(1) + f(5) | 1 0001 1 |
| 10 | 2 + 8 | f(2) + f(5) | 01 001 1 |
| 11 | 3 + 8 | f(3) + f(5) | 001 01 1 |
| 12 | 1 + 3 + 8 | f(1) + f(3) + f(5) | 1 01 01 1 |