Fibonacci-Kodierung

Die Fibonacci-Kodierung ist ein universeller Binärcode, der jeder positiven Ganzzahl eine eindeutige Bitfolge zuordnet, die stets mit zwei aufeinanderfolgenden Einsen endet. Die Konstruktion stützt sich auf den Satz von Zeckendorf: Jede positive Ganzzahl ist die Summe nicht aufeinanderfolgender Fibonacci-Zahlen der Folge, die mit eins, zwei, drei, fünf, acht und so weiter beginnt. Setzen Sie eine Eins für jeden Summanden, eine Null für jeden ausgelassenen Basiswert ab F zwei und hängen Sie ein abschließendes Terminator-Bit an, damit der Code mit elf endet. Studierende der Informationstheorie, Kompressionsübungen und Protokollentwerfer, die eine selbstbegrenzende Ganzzahlkodierung brauchen, nutzen diesen Umrechner, um Beispiele zu prüfen, ohne die Fibonacci-Tabelle von Hand aufzubauen.

Was Fibonacci-Kodierung ist und warum Codes mit 11 enden

Die Fibonacci-Kodierung gehört zur Familie universeller Codes für positive Ganzzahlen: Jedes n größer oder gleich eins erhält ein Binärwort, und kein Codewort ist Präfix eines anderen, sodass ein Strom von Codes ohne Längenpräfixe geparst werden kann. Die zentrale mathematische Tatsache ist der Satz von Zeckendorf.

Mit der Fibonacci-Folge geschrieben als F zwei gleich eins, F drei gleich zwei, F vier gleich drei, F fünf gleich fünf und so weiter (die übliche Folge ohne die erste Verdopplung der Eins) hat jede positive Ganzzahl eine eindeutige Darstellung als Summe nicht aufeinanderfolgender Terme dieser Folge. Die Kodierung setzt unter jeden Basiswert von F zwei bis zum größten auftretenden Summanden ein Bit: Das Bit ist eins, wenn diese Fibonacci-Zahl verwendet wird, sonst null.

Weil Zeckendorf zwei aufeinanderfolgende Einsen in den Basisbits verbietet, ist das höchste genutzte Bit stets eins und wird innerhalb der Basis nie von einer weiteren Eins gefolgt. Das Anhängen einer einzelnen Terminator-Eins erzeugt daher ein charakteristisches Ende aus zwei aufeinanderfolgenden Einsen. Dieses Muster ist das Stoppsignal des Decoders: Bits lesen, bis elf erscheint, die letzte Eins entfernen und die Zeckendorf-Summe zurückgewinnen.

Klassische kleine Werte machen das Muster greifbar. Eins kodiert sich als elf, zwei als null eins eins, drei als null null eins eins, vier als eins null eins eins, fünf als null null null eins eins und sechs als eins null null eins eins. Ein größeres n verlängert einfach die Fibonacci-Tabelle bis zum größten Fk höchstens n, führt die gierige Auswahl von oben aus und gibt dieselbe terminierte Zeichenkette aus.

Die Code-Länge wächst wie O des Logarithmus zur Basis phi von n, sodass selbst große sichere Ganzzahlen kurze Bitstrings bleiben — geeignet für Demos, Testvektoren und Lehrfolien zu präfixfreien Ganzzahlcodes.

Wofür sich die Fibonacci-Kodierung eignet

Kurse zur Informationstheorie und Kompression nutzen die Fibonacci-Kodierung als konkreten universellen Code neben Elias-Gamma und -Delta; ein Live-Umrechner lässt Studierende Hausaufgabenkodierungen für beliebige positive Ganzzahlen prüfen, ohne jedes Mal eine Fibonacci-Tabelle zu bauen. Wettbewerbsprogrammierung und Algorithmus-Blogs zu Zeckendorf-Darstellungen, Fibonacci-Zahlensystemen oder selbstbegrenzenden Strömen brauchen ein deterministisches Orakel, das Bitstring und Summanden für Unit-Tests liefert. Protokollentwerfer, die variable Ganzzahlkodierungen bewerten, können Fibonacci-Codelängen mit fester Breite und LEB128-artigen Schemata an Beispiel-ID-Folgen vergleichen, bevor sie ein Wire-Format festlegen.

Fehlgeschlagene Validierung wird nicht berechnet.