Fibonacci coding

Fibonacci kodlama matematik ve bilgisayar biliminde, pozitif tam sayıları ikili kod sözcüklerine çeviren bir evrensel kodtur. Fibonacci sayılarına dayalı olarak sayıların temsili bir örneğidir. Her kod sözcüğü "11" ile sona erer ve başlangıçta başka "11" ifadeleri içermez.

Fibonacci kodlama, ardışık 1'ler içermeyen Zeckendorf temsili ile yakından ilişkilidir. Bir sayının Fibonacci kod sözcüğü, sözcük rakamlarının sırasını tersine çevirerek ve ekstra bir "1" ekleyerek Zeckendorf temsilidir.

Tanım[değiştir]

$N$ sayısı için, $d(0),d(1),\ldots ,d(k-1),d(k)$ rakamları $N$ sayısını temsil eden kod sözcüğünü oluşturuyorsa:

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

burada $F(i)$ $i$ . Fibonacci sayısıdır, bu nedenle $F(i+2)$ $i$ . farklı Fibonacci sayısıdır ve $1,2,3,5,8,13,\ldots$ ile başlar. Son bit $d(k)$ her zaman eklenen bir bit olarak 1'dir ve yer değeri taşımaz.

Bu kodlamanın benzersiz olduğu ve her kod sözcüğünde tek "11" ifadesinin sondan bir önce olduğu (yani $d(k-1)$ ve $d(k)$ ) gösterilebilir. Son bit en önemli bit, ilk bit ise en az önemli bit olarak kabul edilir. Baştaki sıfırların atılmaması gerekir, çünkü ondalık sayılarda olduğu gibi bu durumda atılamazlar.

İlk birkaç Fibonacci kodları aşağıda gösterilmiştir, ayrıca her sayının Fibonacci kodlamada en küçük boyutlu kod için "implied probability" değeri:

Sembol	Fibonacci temsili	Fibonacci kod sözcüğü	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

Bir tam sayıyı kodlamak için:

$N$ sayısına eşit veya daha küçük olan en büyük Fibonacci sayısını bulun, bu sayıyı $N$ sayısından çıkarın ve kalanı tutun.
Çıkarılan sayı $i$ . Fibonacci sayısı $F(i)$ ise, kod sözcüğünün $i-2$ yerine bir 1 koyun (sol taraftaki rakamı 0 olarak sayarak).
Kalanı $N$ ile değiştirerek yukarıdaki adımları tekrarlayın, sıfır kalana kadar devam edin.
Kod sözcüğünün sağındaki en son rakama ekstra bir 1 ekleyin.

Kod sözcüğünü çözmek için son "1" rakamını kaldırın, kalan rakamları Fibonacci sayılarına (1, 2, 3, 5, 8, 13, ...) atayın ve "1" rakamlarının değerlerini toplayın.

Diğer evrensel kodlarla karşılaştırma[değiştir]

Fibonacci kodlama, zararlı veri akışlarından veriyi düzeltmeyi kolaylaştıran bir özellik içerir ve bu nedenle diğer evrensel kodlara göre bazen daha avantajlıdır. Çoğu evrensel kodda, eğer bir bit değiştirilirse, bundan sonraki hiçbir veri doğru okunmaz. Ancak, Fibonacci kodlama ile bir bit değiştirildiğinde, bir token iki token olarak okunabilir veya iki token tek bir token olarak yanlış okunabilir, ancak bir "0" okunması hataların ileriye yayılmasını durdurur. "11" tokenleri dışında hiçbir akışta "0" yoktur, bu nedenle tek bir bit hatasıyla zararlı olan bir akış ile orijinal akış arasındaki toplam düzenleme mesafesi en fazla üçtür.

Bu yaklaşım, belirli desenlerin (örneğin "11") yasaklandığı bir sembol dizisini kodlamaya genelleştirilebilir.^[1]

Örnek[değiştir]

Aşağıdaki tablo, sayı 65'in Fibonacci kodlamasının 0100100011 olduğunu gösterir, çünkü 65 = 2 + 8 + 55. İlk iki Fibonacci sayısı (0 ve 1) kullanılmaz ve her zaman ekstra bir 1 eklenir.

{\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}}

Genelleştirmeler[değiştir]

Pozitif tam sayılar için Fibonacci kodlamaları, "11" ile sona eren ve başka "11" ifadeleri içermeyen ikili dizilerdir. Bu, N ardışık 1'lerle sona eren ve başka N ardışık 1'leri içermeyen ikili diziler ile genelleştirilebilir. Örneğin, N = 3 için pozitif tam sayılar 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, ... şeklinde kodlanır. Bu durumda, dizinin uzunluğuna göre kodlamaların sayısı Tribonacci sayıları tarafından verilir.

Belirli kısıtlamalar altında hangi sembollerin izin verildiğini tanımlayan genel durumlar için, maksimum bilgi oranı, önce en optimal geçiş olasılıklarını maksimum entropi rastgele yürüyüş kullanarak bulmak ve daha sonra bir entropi kodlayıcı (kodlayıcı ve kod çözücü değiştirilmiş) kullanarak bir mesajı bulunan en optimal geçiş olasılıklarına uygun bir sembol dizisi olarak kodlamakla elde edilir.

Kaynaklar[değiştir]

Şablon:Kaynakça/styles.css sayfası içerik yok.

↑ Şablon:Cite arXiv

Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. s. 105. ISBN 978-0-521-82332-6. Zbl 1086.11015. Geçersiz |url-erişimi=limited (yardım)
Fraenkel, Aviezri S.; Klein, Shmuel T. (1996). "Robust universal complete codes for transmission and compression". Discrete Applied Mathematics. 64 (1): 31–55. CiteSeerX 10.1.1.37.3064 $2. doi:10.1016/0166-218X(93)00116-H. ISSN 0166-218X. Zbl 0874.94026.

Daha fazla okuma[değiştir]

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