WikiDer > Fibonacci-Code

Fibonacci-code

In dem Mathematik und vor allem im Informatik ist der Fibonacci-Code ein universeller Code, basierend auf Fibonacci-Zahlen (die Zahlen im Fibonaccia-Folge), dass die positiv ganze Zahlen kodiert zu binär Wörter. Der Code wird verwendet in Datenkompression, daher endet jedes Wort mit "11" und die Kombination "11" kommt in keinem anderen Wort vor.

Laut der Satz von Zeckendorf jede positive ganze Zahl hat eine Zeckendorf-Darstellung, eine Darstellung als Summe nicht aufeinanderfolgender Fibonacci-Zahlen. Für die Zahl 100 ist dies:

{Anzeigestil 100=3 8 89}

Die Fibonacci-Folge beginnt mit:

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

Für 100 kann also eine Art sein Positionssystem geschrieben sein:

{displaystyle 100=0010100001_{Z}}

,

die ab der zweiten 1 in der Reihe zählt (Normalerweise würde dies umgekehrt mit der höchsten Position zuerst geschrieben, also als 1000010100).

Die Reihe der Nullen und Einsen endet für jede Zahl mit einer 1. Um das Ende des Codes erkennbar zu machen, fügt die Fibonacci-Codierung eine 1 hinzu. Da die Darstellung nie zwei aufeinanderfolgende Fibonacci-Zahlen enthält, ist nur das Ende eines Codes "11". Der Fibonacci-Code für 100 lautet also:

{displaystyle 100=00101000011_{F}}

Definition

Das Fibonacci-Code für die positive ganze Zahl ${displaystyle n}$ ist das binäre Wort:

{displaystyle d_{0}d_{1}d_{2}ldots d_{k}}

,

also mit ${displaystyle d_{i}in {0.1}}$ , für die:

{displaystyle d_{k-1}=d_{k}=1}

und

{displaystyle n=sum _{i=0}^{k-1}d_{i}f_{i 2}}

.

Darin ist ${displaystyle f_{i}}$ es ich-die Zahl in der Fibonacci-Folge, also ohne die ersten beiden, unbenutzten Elemente, die Folge:

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

In dieser Codierung ist das vorletzte bisschen das höchstwertige Bit und das erste Bit ${displaystyle d_{0}}$ die am wenigsten bedeutsame.

Die folgende Tabelle listet die Fibonacci-Codes für die Zahlen 1 bis 14 auf.

Nummer	Zeckendorf-Vertretung	Fibonacci-Code
1	${displaystyle f_{2}=1}$	11
2	${displaystyle f_{3}=2}$	011
3	${displaystyle f_{4}=3}$	0011
4	${displaystyle f_{2} f_{4}=1 3}$	1011
5	${displaystyle f_{5}=5}$	00011
6	${displaystyle f_{2} f_{5}=1 5}$	10011
7	${Anzeigestil f_{3} f_{5}=2 5}$	01011
8	${displaystyle f_{6}=8}$	000011
9	${displaystyle f_{2} f_{6}=1 8}$	100011
10	${Anzeigestil f_{3} f_{6}=2 8}$	010011
11	${Anzeigestil f_{4} f_{6}=3 8}$	001011
12	${displaystyle f_{2} f_{4} f_{6}=1 3 8}$	101011
13	${displaystyle f_{7}}$	0000011
14	${displaystyle f_{2} f_{7}=1 13}$	1000011