Fibonacci Coding
Le codage de Fibonacci est un code préfixe fondé sur la représentation de Zeckendorf (tout entier positif est de manière unique une somme de nombres de Fibonacci non consécutifs) ; il bat le codage unaire pour les distributions géométriques.
Objectif
Coder des séquences d'entiers à distribution géométrique plus compactement que le codage unaire, tout en restant un code préfixe simple.
Mécanisme
L'entier n se décompose en somme de nombres de Fibonacci non consécutifs (théorème de Zeckendorf) ; les positions correspondantes valent 1 et le reste 0, avec un 1 final ajouté comme terminateur — le seul endroit où apparaissent deux 1 consécutifs.
Cas d’usage
- Alternative au codage de Golomb exponentiel
- Codage d'entiers à distribution géométrique
- Codage universel à longueur variable