// Fibonacci-kodning – självsynkroniserande kod baserad på matematiken bakom det gyllene snittet
Fungerar för alla positiva heltal utan extra parametrar.
Kan återfå synkronisering efter överföringsfel med hjälp av mönstret 11.
Baserad på Fibonacci-följden och Zeckendorf-satsen.
Fibonacci-kodning använder Zeckendorf-satsen: varje positivt heltal har en unik representation som en summa av icke-intilliggande Fibonacci-tal. Koden är denna representation i binär form (1 om Fibonacci-talet används, 0 annars) följt av en extra 1 som terminator. Mönstret 11 uppträder bara i slutet 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 Inga två på varandra följande Fibonacci-tal används Mönstret 11 visas endast i slutet av koden
Fibonacci-kodning är en universell kod som representerar positiva heltal med hjälp av Fibonacci-följden. Den bygger på Zeckendorf-satsen och ger självsynkroniserande koder där mönstret 11 bara uppträder som terminator.
Zeckendorf-satsen säger att varje positivt heltal kan representeras entydigt som en summa av icke-intilliggande Fibonacci-tal. Denna representation är grunden för Fibonacci-kodning.
Mönstret 11 alltså två på varandra följande ettor uppträder bara i slutet av varje kodord. Därför kan en dekoder efter överföringsfel hitta ordgränser genom att leta efter 11.
Fibonacci-kodning används i forskning om datakomprimering, i felrobusta överföringssystem och inom teoretisk datavetenskap. Den uppskattas mer för sina matematiska egenskaper än för praktisk effektivitet.