Fibonacci coding

Fibonaccin koodaus on positiivisia kokonaislukuja bitteihin muuttava yleiskoodi, joka tunnetaan Fibonaccin lukujen pohjalta. Jokainen koodisana päättyy ”11” ja sisältää muita esiintymiä merkkijonosta ”11” ennen loppua.

Fibonaccin koodi liittyy läheisesti Zeckendorf representationiin, joka on paikallinen numerosysteemi, joka käyttää Zeckendorf's theoremia ja jolla on se ominaisuus, että yhdelläkään luvulla ei ole edustusta, jossa on peräkkäisiä ykkösiä. Fibonaccin koodisana tiettyyn kokonaislukuun on täsmälleen luvun Zeckendorf-esitys merkkien järjestyksessä käännettynä ja lisätty ”1” loppuun.

Määritelmä[muokkaa]

Luvulle $N\!$ , jos $d(0),d(1),\ldots ,d(k-1),d(k)\!$ edustavat koodisanan numeroita, jotka edustavat $N\!$ , niin:

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

missä Malline:Math on Malline:Math:s Fibonacci number, ja niin ollen Malline:Math on Malline:Math:s erillinen Fibonacci-luku, joka alkaa $1,2,3,5,8,13,\ldots$ . Viimeinen bitti $d(k)$ on aina lisätty bitti 1 ja se ei kuljeta paikan arvoa.

Näytetään, että tällainen koodaus on yksilöllinen, ja ainoa esiintymä merkkijonosta ”11” missä tahansa koodisanassa on lopussa (eli d(k−1) ja d(k)) . Toiseksi viimeinen bitti on merkittävin bitti ja ensimmäinen bitti on vähäpätöisin bitti. Myös johtavat nollat eivät voi jätetä pois kuten ne voivat olla esimerkiksi desimaaliluvuissa.

Ensimmäiset muutamat Fibonaccin koodit ovat alla, ja myös niiden niin sanottu implied probability, arvo joka kullekin luvulle on minimikokoinen koodi Fibonaccin koodauksessa.

Symbol	Fibonacci representation	Fibonacci code word	Implied probability
1	$F(2)$	11	1/4
2	$F(3)$	011	1/8
3	$F(4)$	0011	1/16
4	$F(2)+F(4)$	1011	1/16
5	$F(5)$	00011	1/32
6	$F(2)+F(5)$	10011	1/32
7	$F(3)+F(5)$	01011	1/32
8	$F(6)$	000011	1/64
9	$F(2)+F(6)$	100011	1/64
10	$F(3)+F(6)$	010011	1/64
11	$F(4)+F(6)$	001011	1/64
12	$F(2)+F(4)+F(6)$	101011	1/64
13	$F(7)$	0000011	1/128
14	$F(2)+F(7)$	1000011	1/128

Koodata kokonaisluku Malline:Mvar:

Etsi suurin Fibonacci number joka on yhtäsuuri tai pienempi kuin Malline:Mvar, vähennä tämä luku Malline:Mvarsta, pitäen kirjaa jäännöksestä.
Jos vähennetty luku oli Malline:Mvar:s Fibonacci-luku Malline:Math, aseta 1 paikkaan Malline:Math koodisanassa (laskien vasemmanpuoleisinta numeroa paikaksi 0).
Toista edelliset vaiheet, korvaamalla jäännös Malline:Mvar, kunnes jäännös on 0.
Aseta lisäksi 1 oikeanpuoleisimman numeron jälkeen koodisanassa.

Puraakoodisanan, poista loppuosa ”1”, anna loput arvoilla 1,2,3,5,8,13... (Fibonacci number) bittejä koodisanassa, ja summaa ”1” bittejä arvoja.

Vertailu muihin yleiskoodauksiin[muokkaa]

Fibonaccin koodaus on hyödyllinen ominaisuus, joka tekee sen joskus houkuttelevaksi verrattuna muihin yleiskoodauksiin: se on esimerkki self-synchronizing codesta, joka tekee datan palautuksen helpompi vioittuneesta datavirrasta. Useimmissa muissa yleiskoodauksissa, jos yksi bit muuttuu, niin yksikään dataa, joka tulee sen jälkeen, ei lueta oikein. Fibonaccin koodauksessa, toisesta puoletta, muutettu bitti voi saada yhden merkin luetaan kahdella, tai saada kaksi merkkiä luetaan väärin yhdellä, mutta lukeminen ”0” datavirrasta estää virheet leviämästä edelleen. Koska ainoa virta, jossa ei ole ”0” on virta ”11” merkkejä, kokonainen edit distance vioittuneen datavirran ja alkuperäisen datavirran välillä on korkeintaan kolme.

Tämä lähestymistapa, koodausta käyttäen symbolisarjoja, joissa jotkin kuvioista (kuten ”11”) ovat kiellettyjä, voidaan vapaasti yleistää.^[1]

Esimerkki[muokkaa]

Seuraava taulukko näyttää, että luku 65 esitetään Fibonaccin koodauksessa 0100100011, koska 65 = 2 + 8 + 55. Ensimmäiset kaksi Fibonacci-lukua (0 ja 1) eivät ole käytössä, ja aina lisätään yksi lisä.

{\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{additional}}\\\hline *&-&0&1&0&0&1&0&0&0&1&1\\\hline \end{array}}

Yleistykset[muokkaa]

Fibonaccin koodaukset positiivisille kokonaisluvuille ovat binaarisia merkkijonoja, jotka päättyvät ”11” ja sisältävät muita esiintymiä merkkijonosta ”11”. Tämä voidaan yleistää binaarisiksi merkkijonoiksi, jotka päättyvät N peräkkäisiin ykkösiin ja sisältävät muita esiintymiä N peräkkäisiin ykkösiin. Esimerkiksi N = 3 positiiviset kokonaisluvut koodataan 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, …. Tässä tapauksessa koodausten määrä merkkijonon pituuden funktiona voidaan antaa tribonacci numbern sarjan avulla.

Yleisesti rajoitteet, jotka määrittelevät, mitkä symbolit ovat sallittuja jonkin symbolin jälkeen, voidaan saada maksimi-informaatiomäärä optimaalisilla siirtymistodennäköisyyksillä käyttämällä maximal entropy random walkia, sitten käyttämällä entropy coderia (vaihdettu koodaaja ja purkaja) viestin koodaamiseen symbolisarjan muotoon, joka täyttää löydetyt optimaaliset siirtymistodennäköisyydet.

Viitteet[muokkaa]

↑ Malline:Cite arXiv

(2003) Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 105. ISBN 978-0-521-82332-6.
"Robust universal complete codes for transmission and compression" (1996). Discrete Applied Mathematics 64: 31–55. doi:10.1016/0166-218X(93)00116-H. ISSN 0166-218X.

Lisää lukemista[muokkaa]

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

Malline:Compression Methods