Fibonacci-koding - Fibonacci coding

I matematikk og databehandling er Fibonacci-koding en universell kode som koder positive heltall i binære kodeord . Det er et eksempel på representasjoner av heltall basert på Fibonacci-tall . Hvert kodeord slutter med "11" og inneholder ingen andre forekomster av "11" før slutten.

Fibonacci-koden er nært beslektet med Zeckendorf-representasjonen , et posisjonalt tallsystem som bruker Zeckendorfs teorem og har den egenskapen at intet tall har en representasjon med påfølgende 1-er. Fibonacci-kodeordet for et bestemt heltall er nøyaktig heltallets Zeckendorf-representasjon med rekkefølgen på sifrene omvendt og en ekstra "1" lagt til slutten.

Definisjon

For et tall , hvis representerer sifrene i kodeordet som representerer, har vi: ${\ displaystyle N \!}$ ${\ displaystyle d (0), d (1), \ ldots, d (k-1), d (k) \!}$ ${\ displaystyle N \!}$

{\ displaystyle N = \ sum _ {i = 0} ^ {k-1} d (i) F (i + 2), {\ text {and}} d (k-1) = d (k) = 1 . \!}

hvor $F (i)$ er den $i$ th Fibonacci tall , og slik at $F (i 2)$ er det $i$ th tydelig Fibonacci nummer som begynner med . Den siste biten er alltid en vedlagt bit på 1 og har ikke plassverdi. ${\ displaystyle 1,2,3,5,8,13, \ ldots}$ ${\ displaystyle d (k)}$

Det kan vises at en slik koding er unik, og den eneste forekomsten av "11" i et hvilket som helst kodeord er på slutten, dvs. d ( k −1) og d ( k ). Den nest siste biten er den viktigste biten og den første biten er den minst betydningsfulle biten. Også ledende nuller kan ikke utelates som de kan i f.eks. Desimaltall.

De første få Fibonacci-kodene er vist nedenfor, og også deres såkalte underforståtte sannsynlighet , verdien for hvert tall som har en minimumskode i Fibonacci-koding.

Symbol	Fibonacci-representasjon	Fibonacci kodeord	Underforstått sannsynlighet
1	${\ displaystyle F (2)}$	11	1/4
2	${\ displaystyle F (3)}$	011	1/8
3	${\ displaystyle F (4)}$	0011	1/16
4	${\ displaystyle F (2) + F (4)}$	1011	1/16
5	${\ displaystyle F (5)}$	00011	1/32
6	${\ displaystyle F (2) + F (5)}$	10011	1/32
7	${\ displaystyle F (3) + F (5)}$	01011	1/32
8	${\ displaystyle F (6)}$	000011	1/64
9	${\ displaystyle F (2) + F (6)}$	100011	1/64
10	${\ displaystyle F (3) + F (6)}$	010011	1/64
11	${\ displaystyle F (4) + F (6)}$	001011	1/64
12	${\ displaystyle F (2) + F (4) + F (6)}$	101011	1/64
1. 3	${\ displaystyle F (7)}$	0000011	1/128
14	${\ displaystyle F (2) + F (7)}$	1000011	1/128

For å kode et helt tall N :

Finn det største Fibonacci-tallet som er lik eller mindre enn N ; trekk dette tallet fra N , og hold oversikt over resten.
Hvis tallet som ble trukket, var det i Fibonacci-tallet F ( i ), setter du en 1 på plass i −2 i kodeordet (teller det venstre sifferet som sted 0).
Gjenta de forrige trinnene, og erstatt resten med N , til en rest på 0 er nådd.
Plasser ytterligere 1 etter sifferet til høyre i kodeordet.

For å dekode et kodeord, fjern det siste "1", tildel de resterende verdiene 1,2,3,5,8,13 ... ( Fibonacci-tallene ) til bitene i kodeordet, og summer verdiene til "1" -bitene.

Sammenligning med andre universelle koder

Fibonacci-koding har en nyttig egenskap som noen ganger gjør det attraktivt i forhold til andre universelle koder: det er et eksempel på en selvsynkroniseringskode , noe som gjør det lettere å gjenopprette data fra en skadet strøm. Med de fleste andre universelle koder, hvis en enkelt bit endres, blir ingen av dataene som kommer etter den lest korrekt. Med Fibonacci-koding, derimot, kan en endret bit føre til at ett token blir lest som to, eller at to token blir lest feil som en, men å lese et "0" fra strømmen vil stoppe feilene fra å forplante seg ytterligere. Siden den eneste strømmen som ikke har "0" i seg er en strøm med "11" -tegn, er den totale redigeringsavstanden mellom en strøm som er skadet av en enkeltbitfeil og den opprinnelige strømmen på det meste tre.

Denne tilnærmingen - koding ved bruk av symboler, der noen mønstre (som "11") er forbudt, kan generaliseres fritt.

Eksempel

Tabellen nedenfor viser at tallet 65 er representert i Fibonacci-koding som 0100100011, siden 65 = 2 + 8 + 55 . De to første Fibonacci-tallene (0 og 1) brukes ikke, og 1 ekstra legges alltid til.

{\ displaystyle {\ begin {array} {ccccccccccc | c} \ hline 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & - \\\ hline F (0) & F (1) & F (2) & F (3) & F (4) & F (5) & F (6) & F (7) & F (8) & F (9) & F (10) & \ scriptstyle {\ text {tillegg}} \\\ hline - & - & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\\ hline \ end {array}}}

Generaliseringer

Fibonacci-kodingene for de positive heltallene er binære strenger som slutter med "11" og inneholder ingen andre forekomster av "11". Dette kan generaliseres til binære strenger som slutter med N påfølgende 1 og ikke inneholder andre forekomster av N påfølgende 1. For eksempel er for N = 3 de positive heltallene kodet som 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111,…. I dette tilfellet er antall kodinger som en funksjon av strenglengde gitt av sekvensen av Tribonacci-tall .

For generelle begrensninger som definerer hvilke symboler som er tillatt etter et gitt symbol, kan den maksimale informasjonshastigheten oppnås ved først å finne de optimale overgangssannsynlighetene ved å bruke maksimal entropi tilfeldig gange , og deretter bruke entropikoder (med svitsjet kode med dekoder) for å kode en melding som en sekvens av symboler som oppfyller de funnet optimale overgangssannsynlighetene.

Se også

Referanser

Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatiske sekvenser: Teori, applikasjoner, generaliseringer . Cambridge University Press . s. 105 . ISBN 978-0-521-82332-6. Zbl 1086.11015 .
Fraenkel, Aviezri S .; Klein, Shmuel T. (1996). "Robuste universelle komplette koder for overføring og komprimering". Diskret anvendt matematikk . 64 (1): 31–55. CiteSeerX 10.1.1.37.3064 . doi : 10.1016 / 0166-218X (93) 00116-H . ISSN 0166-218X . Zbl 0874.94026 .

Videre lesning

Stakhov, AP (2009). The Mathematics of Harmony: From Euclid to Contemporary Mathematics and Computer Science . Singapore: World Scientific Publishing .

Languages

In other projects