// Fibonacci-Codierung – selbstsynchronisierender Code auf Basis der Mathematik des Goldenen Schnitts
Funktioniert für jede positive Ganzzahl ohne zusätzliche Parameter.
Kann nach Ăśbertragungsfehlern ĂĽber das Muster 11 wieder synchronisiert werden.
Basiert auf der Fibonacci-Folge und dem Zeckendorf-Satz.
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.
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
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.
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.
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.
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.