Codage de Fibonacci - Fibonacci coding

Systèmes numériques
Système de numération hindou-arabe
Arabe occidental Arabe oriental bengali Devanagari gujarati Gurmukhi Odia Cinghalais Tamil malayalam Telugu Kannada Dzongkha Tibétain Balinais birman Javanais Khmer Lao mongol thaïlandais
de l'Asie de l'Est
chinois Suzhou Hokkien Japonais coréen vietnamien Tangut Tiges de comptage
américain
Cherokee Kaktovik (Iñupiaq)
Alphabétique
Abjad arménien ryabhaṭa cyrillique Geʽez géorgien grec hébreu romain
Ancien
égéen Grenier babylonien Brahmi Tchouvache cistercien égyptien étrusque glagolitique Kharosthi maya Muisca Pentimal Rumi Comptage préhistorique Marques de pointage Quipu
Systèmes positionnels par base
2 3 4 5 6 8 dix 12 16 20 60
Systèmes de numération positionnelle non standard
Numérotation bijective ( 1 ) Représentation des chiffres signés ( ternaire équilibré ) mixte ( factoriel ) négatif Système à base complexe ( 2 i ) Base non entier de numération ( φ ) Systèmes numériques asymétriques
Liste des systèmes numériques
v t e

En mathématiques et en informatique, le codage de Fibonacci est un code universel qui code les entiers positifs en mots de code binaires . C'est un exemple de représentations d'entiers basés sur des 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 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.

Définition

Pour un nombre , si représentent les chiffres du mot de code représentant alors nous avons : ${\style d'affichage N\!}$${\displaystyle d(0),d(1),\ldots ,d(k-1),d(k)\!}$${\style d'affichage N\!}$

${\displaystyle N=\sum _{i=0}^{k-1}d(i)F(i+2),{\text{ et }}d(k-1)=d(k)=1 .\!}$

où F ( i ) est le i ième nombre de Fibonacci , et si F ( i 2) est le i ième nombre de Fibonacci distinct à partir de . Le dernier bit est toujours un bit ajouté de 1 et ne porte pas de valeur de position. ${\displaystyle 1,2,3,5,8,13,\ldots }$${\style d'affichage d(k)}$

On peut montrer qu'un tel codage est unique et que la seule occurrence de "11" dans un mot de code se trouve à 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. Les zéros non significatifs ne peuvent pas non plus être omis, comme c'est le cas par exemple dans les nombres décimaux.

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

symbole	Représentation de Fibonacci	mot de code de Fibonacci	Probabilité implicite
1	${\style d'affichage F(2)}$	11	1/4
2	${\style d'affichage F(3)}$	011	1/8
3	${\style d'affichage F(4)}$	0011	1/16
4	${\style d'affichage F(2)+F(4)}$	1011	1/16
5	${\style d'affichage F(5)}$	00011	1/32
6	${\style d'affichage F(2)+F(5)}$	10011	1/32
7	${\style d'affichage F(3)+F(5)}$	01011	1/32
8	${\style d'affichage F(6)}$	000011	1/64
9	${\style d'affichage F(2)+F(6)}$	100011	1/64
dix	${\style d'affichage F(3)+F(6)}$	010011	1/64
11	${\style d'affichage F(4)+F(6)}$	001011	1/64
12	${\style d'affichage F(2)+F(4)+F(6)}$	101011	1/64
13	${\style d'affichage F(7)}$	0000011	1/128
14	${\style d'affichage F(2)+F(7)}$	1000011	1/128

Pour encoder un entier N :

1. Trouver 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 ), mettez un 1 à la place i -2 dans le mot de code (en comptant le chiffre le plus à gauche comme place 0).
3. Répétez les étapes précédentes, en remplaçant le reste par N , jusqu'à ce qu'un reste de 0 soit atteint.
4. Placez un 1 supplémentaire après le chiffre le plus à droite dans le 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 de les bits "1".

Comparaison avec d'autres codes universels

Le codage de Fibonacci a une propriété utile qui le rend parfois attractif par rapport à d'autres codes universels : c'est un exemple de code auto-synchronisant , facilitant la récupération des données d'un flux endommagé. Avec la plupart des autres codes universels, si un seul bit est modifié, aucune des données qui 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, 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 seule erreur de bit et le flux d'origine est d'au plus trois.

Cette approche de codage utilisant une séquence de symboles, dans laquelle certains motifs (comme "11") sont interdits, peut être librement généralisée.

Exemple

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

${\displaystyle {\begin{array}{ccccccccccc|c}\hline 0&1&1&2&3&5&8&13&21&34&55&-\\\hline F(0)&F(1)&F(2)&F(3)&F(4)&F(5)&F(6) &F(7)&F(8)&F(9)&F(10)&\scriptstyle {\text{additional}}\\\hline -&-&0&1&0&0&1&0&0&0&1&1\\\hline \end{array}}}$

Généralisations

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 sous la forme 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, …. Dans ce cas, le nombre d'encodages en fonction de la longueur de la chaîne est donné par la séquence des nombres de Tribonacci .

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

Voir également

• Base du nombre d'or
• Codage NegaFibonacci
• numération d'Ostrowski
• Code universel
• Varicode , une application pratique
• Le théorème de Zeckendorf
• Marche aléatoire d'entropie maximale

Les références

• Allouche, Jean-Paul ; Shallit, Jeffrey (2003). Séquences automatiques : théorie, applications, généralisations . Presse de l'Université de Cambridge . p. 105 . ISBN 978-0-521-82332-6. Zbl  1086.11015 .
• Fraenkel, Aviezri S.; Klein, Shmuel T. (1996). "Codes complets universels robustes pour la transmission et la compression". Mathématiques discrètes appliquées . 64 (1) : 31-55. CiteSeerX  10.1.1.37.3064 . doi : 10.1016/0166-218X(93)00116-H . ISSN  0166-218X . Zbl  0874.94026 .

Lectures complémentaires

• Stakhov, AP (2009). Les mathématiques de l'harmonie : d'Euclide aux mathématiques contemporaines et à l'informatique . Singapour : édition scientifique mondiale .