// Fibonacci-kodning - selvsynkroniserende kode baseret pĂĄ gyldne forholds matematik
Fungerer for alle positive heltal uden parametre.
Kan gendanne synkronisering efter fejl ved hjælp af mønstret 11.
Baseret på Fibonacci-rækken og Zeckendorf-sætningen.
Fibonacci-kodning bruger Zeckendorfs sætning: hvert positivt heltal har en entydig repræsentation som en sum af ikke-naboliggende Fibonacci-tal. Koden er denne repræsentation i binær form (1 hvis tallet bruges, 0 hvis det ikke bruges) efterfulgt af en ekstra 1 som afslutning. Mønstret 11 optræder kun ved slutningen af en kodeord.
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å hinanden følgende Fibonacci-tal bruges Mønstret 11 forekommer kun i slutningen
Fibonacci-kodning er en universel kode, der repræsenterer positive heltal ved hjælp af Fibonacci-rækken. Den bygger på Zeckendorfs sætning og giver selvsynkroniserende koder, hvor mønstret 11 kun optræder som afslutning.
Zeckendorfs sætning siger, at hvert positivt heltal kan skrives entydigt som en sum af ikke-naboliggende Fibonacci-tal. Denne repræsentation bruges som grundlag for Fibonacci-kodning.
Mønstret 11 altså to på hinanden følgende 1-taller optræder kun i slutningen af hvert kodeord. Det gør det muligt for dekoderen at genfinde grænserne mellem kodeord efter transmissionsfejl ved at lede efter 11.
Fibonacci-kodning bruges i forskning i datakomprimering, fejlrobuste transmissionssystemer og teoretisk datalogi. Den værdsættes mest for sine matematiske egenskaber snarere end praktisk effektivitet.