> fibonacci | zeckendorf | universal <
// Fibonacci-Codierung – selbstsynchronisierender Code auf Basis der Mathematik des Goldenen Schnitts
Universeller Code
Funktioniert für jede positive Ganzzahl ohne zusätzliche Parameter.
Selbstsynchronisierend
Kann nach Übertragungsfehlern über das Muster 11 wieder synchronisiert werden.
Goldener Schnitt
Basiert auf der Fibonacci-Folge und dem Zeckendorf-Satz.
>> technische details
Wie Fibonacci-Codierung funktioniert:
Fibonacci-Codierung verwendet den Zeckendorf-Satz: Jede positive Ganzzahl besitzt eine eindeutige Darstellung als Summe nicht aufeinanderfolgender Fibonacci-Zahlen. Der Code besteht aus dieser Darstellung in Binärform (1 wenn die Fibonacci-Zahl verwendet wird, 0 wenn nicht) gefolgt von einer zusätzlichen 1 als Abschluss. Das Muster 11 tritt nur am Ende eines Codeworts auf.
Kodierungsbeispiele:
Fibonacci: 1, 2, 3, 5, 8, 13, 21... 1 = F(1) → 11 2 = F(2) → 011 3 = F(3) → 0011 4 = F(3)+F(1) → 1011 5 = F(4) → 00011 12 = F(5)+F(3)+F(1) → 101011 Es werden keine aufeinanderfolgenden Fibonacci-Zahlen verwendet Das Muster 11 erscheint nur am Ende des Codes
Warum Fibonacci-Codierung?:
- ▸Selbstsynchronisation
- ▸Keine Parameter nötig
- ▸Robust gegenüber Fehlern
- ▸Eindeutige Darstellung
- ▸Mathematische Eleganz
>> häufige fragen
Was ist Fibonacci-Codierung?
Fibonacci-Codierung ist ein universeller Code, der positive Ganzzahlen mit der Fibonacci-Folge darstellt. Er basiert auf dem Zeckendorf-Satz und erzeugt selbstsynchronisierende Codes, bei denen das Muster 11 nur als Abschluss auftritt.
Was ist die Zeckendorf-Darstellung?
Der Zeckendorf-Satz besagt, dass jede positive Ganzzahl eindeutig als Summe nicht benachbarter Fibonacci-Zahlen dargestellt werden kann. Diese Darstellung bildet die Grundlage der Fibonacci-Codierung.
Warum ist der Code selbstsynchronisierend?
Das Muster 11 also zwei aufeinanderfolgende Einsen tritt nur am Ende eines Codeworts auf. Dadurch kann ein Decoder nach Bitfehlern die Wortgrenzen wiederfinden, indem er nach 11 sucht.
Wo wird Fibonacci-Codierung eingesetzt?
Fibonacci-Codierung wird in der Forschung zu Datenkompression, in fehlertoleranten Übertragungssystemen und in der theoretischen Informatik verwendet. Sie wird eher wegen ihrer mathematischen Eigenschaften als wegen praktischer Effizienz geschätzt.