Codage de Fibonacci

En mathématiques et en informatique, le codage de Fibonacci est un code universel qui encode les entiers positifs en mots de code binaires . C'est un exemple de représentation d'entiers basés sur les nombres de Fibonacci . Chaque mot de code se termine par « 11 » et ne contient aucune autre instance de « 11 » avant la fin.

Le code de Fibonacci est étroitement lié à la représentation de Zeckendorf , un système de numération positionnelle qui utilise le théorème de Zeckendorf et qui a la propriété qu'aucun nombre n'a de représentation avec des 1 consécutifs. Le mot de code de Fibonacci pour un entier particulier est exactement la représentation de Zeckendorf de l'entier avec l'ordre de ses chiffres inversé et un « 1 » supplémentaire ajouté à la fin.

Pour un nombre , si représentent les chiffres du mot de code représentant alors on a :

où F ( i ) est le i- ème nombre de Fibonacci , et donc F ( i +2) est le i -ème nombre de Fibonacci distinct commençant par . Le dernier bit est toujours un bit ajouté de 1 et ne porte pas de valeur de position.

Il est possible de montrer qu'un tel codage est unique et que la seule occurrence de « 11 » dans un mot de code est à la fin (c'est-à-dire d ( k −1) et d ( k )). L'avant-dernier bit est le bit le plus significatif et le premier bit est le bit le moins significatif. De plus, les zéros non significatifs ne peuvent pas être omis car ils peuvent l'être, par exemple, dans les nombres décimaux.

Les premiers codes de Fibonacci sont présentés ci-dessous, ainsi que leur soi-disant probabilité implicite , la valeur de chaque nombre qui a un code de taille minimale dans le codage de Fibonacci.

Pour encoder un entier N :

1. Trouvez le plus grand nombre de Fibonacci égal ou inférieur à N ; soustrayez ce nombre de N en gardant une trace du reste.
2. Si le nombre soustrait était le i ème nombre de Fibonacci F ( i ) , placez un 1 à la place i − 2 dans le mot de code (en comptant le chiffre le plus à gauche comme la place 0).
3. Répétez les étapes précédentes en remplaçant N par le reste , jusqu'à ce qu'un reste de 0 soit atteint.
4. Placez un 1 supplémentaire après le chiffre le plus à droite du mot de code.

Pour décoder un mot de code, supprimez le « 1 » final, attribuez les valeurs restantes 1, 2, 3, 5, 8, 13... (les nombres de Fibonacci ) aux bits du mot de code et additionnez les valeurs des bits « 1 ».

Le codage de Fibonacci a une propriété utile qui le rend parfois attrayant par rapport à d'autres codes universels : c'est un exemple de code auto-synchronisant , ce qui facilite la récupération des données d'un flux endommagé. Avec la plupart des autres codes universels, si un seul bit est altéré, aucune des données qui le suivent ne sera correctement lue. Avec le codage de Fibonacci, en revanche, un bit modifié peut entraîner la lecture d'un jeton comme deux, ou la lecture incorrecte de deux jetons comme un seul, mais la lecture d'un "0" dans le flux empêchera les erreurs de se propager davantage. Étant donné que le seul flux qui ne contient pas de "0" est un flux de "11" jetons, la distance d'édition totale entre un flux endommagé par une erreur d'un seul bit et le flux d'origine est au maximum de trois.

Cette approche, qui consiste à coder à l'aide d'une séquence de symboles, dans laquelle certains motifs (comme « 11 ») sont interdits, peut être librement généralisée.

Le tableau suivant montre que le nombre 65 est représenté dans le codage de Fibonacci par 0100100011, puisque 65 = 2 + 8 + 55. Les deux premiers nombres de Fibonacci (0 et 1) ne sont pas utilisés et un 1 supplémentaire est toujours ajouté.

Les codages de Fibonacci pour les entiers positifs sont des chaînes binaires qui se terminent par « 11 » et ne contiennent aucune autre instance de « 11 ». Cela peut être généralisé aux chaînes binaires qui se terminent par N 1 consécutifs et ne contiennent aucune autre instance de N 1 consécutifs. Par exemple, pour N = 3, les entiers positifs sont codés comme 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, …. Dans ce cas, le nombre de codages en fonction de la longueur de la chaîne est donné par la séquence de nombres de Tribonacci .

Pour les contraintes générales définissant quels symboles sont autorisés après un symbole donné, le débit d'information maximal peut être obtenu en trouvant d'abord les probabilités de transition optimales à l'aide d'une marche aléatoire d'entropie maximale , puis en utilisant un codeur d'entropie (avec codeur et décodeur commutés) pour coder un message sous la forme d'une séquence de symboles remplissant les probabilités de transition optimales trouvées.