// Fibonacci-koding – selvsynkroniserende kode basert på matematikken bak det gylne snitt
Fungerer for alle positive heltall uten ekstra parametere.
Kan gjenvinne synkronisering etter feil ved hjelp av mønsteret 11.
Basert på Fibonacci-følgen og Zeckendorf-teoremet.
Fibonacci-koding bruker Zeckendorf-teoremet: hvert positivt heltall har en unik representasjon som en sum av ikke-påfølgende Fibonacci-tall. Koden er denne representasjonen i binær form (1 hvis Fibonacci-tallet brukes, 0 hvis ikke) etterfulgt av en ekstra 1 som avslutning. Mønsteret 11 forekommer bare på slutten av koden.
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 Ingen to påfølgende Fibonacci-tall brukes Mønsteret 11 vises bare på slutten av koden
Fibonacci-koding er en universell kode som representerer positive heltall ved hjelp av Fibonacci-følgen. Den bygger på Zeckendorf-teoremet og gir selvsynkroniserende koder der mønsteret 11 bare opptrer som avslutning.
Zeckendorf-teoremet sier at hvert positivt heltall kan skrives entydig som en sum av ikke-påfølgende Fibonacci-tall. Denne representasjonen ligger til grunn for Fibonacci-koding.
Mønsteret 11 altså to etterfølgende 1-biter forekommer kun i slutten av hvert kodeord. Dermed kan en dekoder etter overføringsfeil finne tilbake til ordgrensene ved å lete etter 11.
Fibonacci-koding brukes i forskning på datakomprimering, feilrobuste overføringssystemer og teoretisk informatikk. Den verdsettes hovedsakelig for sine matematiske egenskaper mer enn praktisk effektivitet.