Fibonacci-code

In de wiskunde en speciaal in de informatica is de Fibonacci-code een universele code, gebaseerd op de Fibonacci-getallen (de getallen in de rij van Fibonacci), die de positieve gehele getallen codeert tot binaire woorden. De code wordt gebruikt in datacompressie, daarom eindigt elk woord met "11" en komt de combinatie "11" verder niet in een woord voor.

Volgens de Stelling van Zeckendorf heeft elk positief geheel getal een Zeckendorf-representatie, een voorstelling als som van niet-opeenvolgende Fibonacci-getallen. Voor het getal 100 is dit:

100 = 3 + 8 + 89 {\displaystyle 100=3+8+89}

De rij van Fibonacci begint met:

0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , . . . {\displaystyle 0,1,1,2,3,5,8,13,21,34,55,89,...}

Voor 100 kan daarom in een soort positiestelsel geschreven worden:

100 = 0010100001 Z {\displaystyle 100=0010100001_{Z}} ,

waarin geteld wordt vanaf de tweede 1 in de rij.(Normaal gesproken zou dit andersom genoteerd worden met de hoogste positie voorop, dus als 1000010100.)

De rij 0'en en 1'en eindigt voor elk getal met een 1. Voor de herkenbaarheid van het eind van de code voegt de Fibonacci-codering er nog een 1 aan toe. Omdat in de representatie nooit twee opeenvolgende Fibonacci-getallen voorkomen, staat alleen aan het eind van een code "11". De Fibonacci-code voor 100 is dus:

100 = 00101000011 F {\displaystyle 100=00101000011_{F}}

De Fibonacci-code voor het positieve gehele getal n {\displaystyle n} is het binaire woord:

d 0 d 1 d 2 … d k {\displaystyle d_{0}d_{1}d_{2}\ldots d_{k}} ,

dus met d i ∈ { 0 , 1 } {\displaystyle d_{i}\in \{0,1\}} , waarvoor geldt:

d k − 1 = d k = 1 {\displaystyle d_{k-1}=d_{k}=1}

en

n = ∑ i = 0 k − 1 d i f i + 2 {\displaystyle n=\sum _{i=0}^{k-1}d_{i}f_{i+2}} .

Daarin is f i {\displaystyle f_{i}} het i-de getal in de rij van Fibonacci, dus, met weglating van de eerste twee, ongebruikte, elementen, de rij:

f 2 = 1 , f 3 = 2 , f 4 = 3 , f 5 = 5 , f 6 = 8 , f 7 = 13 , … {\displaystyle f_{2}=1,f_{3}=2,f_{4}=3,f_{5}=5,f_{6}=8,f_{7}=13,\ldots }

In deze codering is de voorlaatste bit de meest significante bit en de eerste bit d 0 {\displaystyle d_{0}} de minst significante.

In de onderstaande tabel staan de Fibonacci-codes van de getallen 1 tot en met 14.

getal	Zeckendorf-representatie	Fibonacci-code
1	f 2 = 1 {\displaystyle f_{2}=1}	11
2	f 3 = 2 {\displaystyle f_{3}=2}	011
3	f 4 = 3 {\displaystyle f_{4}=3}	0011
4	f 2 + f 4 = 1 + 3 {\displaystyle f_{2}+f_{4}=1+3}	1011
5	f 5 = 5 {\displaystyle f_{5}=5}	00011
6	f 2 + f 5 = 1 + 5 {\displaystyle f_{2}+f_{5}=1+5}	10011
7	f 3 + f 5 = 2 + 5 {\displaystyle f_{3}+f_{5}=2+5}	01011
8	f 6 = 8 {\displaystyle f_{6}=8}	000011
9	f 2 + f 6 = 1 + 8 {\displaystyle f_{2}+f_{6}=1+8}	100011
10	f 3 + f 6 = 2 + 8 {\displaystyle f_{3}+f_{6}=2+8}	010011
11	f 4 + f 6 = 3 + 8 {\displaystyle f_{4}+f_{6}=3+8}	001011
12	f 2 + f 4 + f 6 = 1 + 3 + 8 {\displaystyle f_{2}+f_{4}+f_{6}=1+3+8}	101011
13	f 7 {\displaystyle f_{7}}	0000011
14	f 2 + f 7 = 1 + 13 {\displaystyle f_{2}+f_{7}=1+13}	1000011

• Talstelsel met basis gulden snede
• Stelling van Zeckendorf

• Allouche, Jean-Paul, Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 105. ISBN 978-0-521-82332-6.
• T. C. Bell and I. H. Witten. Text Compression. Prentice Hall, 1990.

• (en) Fast Fibonacci Encoding Algorithm, Jiri Walder, Michal Kratky, and Jan Platos
• (en) Robust universal complete codes for transmission and compression. Discrete Applied Mathematics 64: 31–55 (1996). ISSN 0166-218X