Fibonacci Coding
Die Fibonacci-Kodierung ist ein Präfixcode auf Basis der Zeckendorf-Darstellung (jede positive ganze Zahl ist eindeutig eine Summe nicht aufeinanderfolgender Fibonacci-Zahlen); sie schlägt bei geometrischen Verteilungen den Unärcode.
Zweck
Ganzzahlfolgen mit geometrischer Verteilung kompakter kodieren als mit Unärcode und dennoch ein einfacher Präfixcode bleiben.
Mechanismus
Die Zahl n wird in eine Summe nicht aufeinanderfolgender Fibonacci-Zahlen zerlegt (Satz von Zeckendorf); die zugehörigen Positionen sind 1, der Rest 0, mit einem angehängten finalen 1 als Terminator – die einzige Stelle, an der zwei aufeinanderfolgende Einsen auftreten.
Anwendungsfälle
- Alternative zur exponentiellen Golomb-Kodierung
- Kodierung geometrisch verteilter Ganzzahlen
- Universelle Variablenlängen-Kodierung