Kodowanie Fibonacciego

W matematyce i informatyce kodowanie Fibonacciego jest uniwersalnym kodem ^{[ potrzebne źródło ]} , który koduje dodatnie liczby całkowite w binarne słowa kodowe . Jest to jeden z przykładów reprezentacji liczb całkowitych opartych na liczbach Fibonacciego . Każde słowo kodowe kończy się na „11” i nie zawiera żadnych innych wystąpień „11” przed końcem.

Kod Fibonacciego jest ściśle powiązany z reprezentacją Zeckendorfa , pozycyjnym systemem liczbowym , który wykorzystuje twierdzenie Zeckendorfa i ma tę właściwość, że żadna liczba nie ma reprezentacji z kolejnymi jedynekami. Słowo kodowe Fibonacciego dla określonej liczby całkowitej jest dokładnie reprezentacją Zeckendorfa liczby całkowitej z odwróconą kolejnością cyfr i dodatkową „1” dołączoną na końcu.

Definicja

$ldots$ liczby , jeśli $, d (k-1), d (k) \!}$ ${\ Displaystyle d (0), d (1), \$ reprezentują cyfry słowa kodowego reprezentującego ${\ Displaystyle N \!},$ to mamy: N {\ Displaystyle N \!}

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

gdzie $fa (ja)$ jest $i-$ tą liczbą Fibonacciego , a więc $fa (ja + 2)$ jest $i-$ tą odrębną liczbą Fibonacciego zaczynającą się od ${\ Displaystyle 1,2,3 ,5,8,13,\ldkropki }$ . Ostatni bit $ma$ zawsze dołączonym bitem 1 i nie

Można wykazać, że takie kodowanie jest unikalne, a jedyne wystąpienie „11” w dowolnym słowie kodowym występuje na końcu, tj. d ( k −1) i d ( k ). Przedostatni bit jest bitem najbardziej znaczącym, a bit pierwszy najmniej znaczącym. Również początkowych zer nie można pominąć, jak to jest możliwe np. w liczbach dziesiętnych.

Poniżej pokazano kilka pierwszych kodów Fibonacciego, a także ich tzw. implikowane prawdopodobieństwo , czyli wartość dla każdej liczby, która ma kod o minimalnym rozmiarze w kodzie Fibonacciego.

Symbol	Reprezentacja Fibonacciego	Słowo kodu Fibonacciego	Domniemane prawdopodobieństwo
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
13	${\ Displaystyle F (7)}$	0000011	1/128
14	${\ Displaystyle F (2) + F (7)}$	1000011	1/128

Aby zakodować liczbę całkowitą N :

Znajdź największą liczbę Fibonacciego równą lub mniejszą niż N ; odejmij tę liczbę od N , śledząc resztę.
Jeśli odjętą liczbą była i- ta liczba Fibonacciego F ( i ), wstaw 1 w miejsce i −2 w słowie kodowym (licząc cyfrę najbardziej wysuniętą na lewo jako miejsce 0).
Powtórz poprzednie kroki, zastępując resztę N , aż zostanie osiągnięta reszta 0.
Umieść dodatkową 1 po skrajnej prawej cyfrze w słowie kodowym.

Aby zdekodować słowo kodowe, usuń ostatnią „1”, przypisz pozostałe wartości 1,2,3,5,8,13... (liczby Fibonacciego ) do bitów w słowie kodowym i zsumuj wartości bity „1”.

Porównanie z innymi kodami uniwersalnymi

Kodowanie Fibonacciego ma przydatną właściwość, która czasami czyni go atrakcyjnym w porównaniu z innymi uniwersalnymi kodami: jest przykładem kodu samosynchronizującego się , ułatwiającego odzyskanie danych z uszkodzonego strumienia. W przypadku większości innych uniwersalnych kodów, jeśli pojedynczy bit zostanie zmieniony, żadne dane, które pojawią się po nim, nie zostaną poprawnie odczytane. Z drugiej strony w przypadku kodowania Fibonacciego zmieniony bit może spowodować, że jeden token zostanie odczytany jako dwa lub spowoduje, że dwa tokeny zostaną odczytane niepoprawnie jako jeden, ale odczytanie „0” ze strumienia zapobiegnie dalszemu rozprzestrzenianiu się błędów. Ponieważ jedynym strumieniem, który nie zawiera „0”, jest strumień „11” tokenów, całkowita odległość edycji między strumieniem uszkodzonym przez błąd jednego bitu a oryginalnym strumieniem wynosi co najwyżej trzy.

Takie podejście – kodowanie za pomocą sekwencji symboli, w których niektóre wzorce (np. „11”) są zabronione, można dowolnie uogólniać.

Przykład

Poniższa tabela pokazuje, że liczba 65 jest reprezentowana w kodzie Fibonacciego jako 0100100011, ponieważ 65 = 2 + 8 + 55 . Pierwsze dwie liczby Fibonacciego (0 i 1) nie są używane, a dodatkowa 1 jest zawsze dołączana.

{\ Displaystyle {\ rozpocząć {tablica} {cccccccccc| c} \ hline 0 i 1 i 1 i 2 i 5 i 8 i 13 i 21 i 34 i 55 i - \\\ hline F (0) i F (1) i F (2) i F (3) i F (4)&F(5)&F(6)&F(7)&F(8)&F(9)&F(10)&\scriptstyle {\text{dodatkowy}}\\\hline -&-&0&1&0&0&1&0&0&0&1&1\\\hline \ koniec {tablica}}}

Uogólnienia

Kodowanie Fibonacciego dla dodatnich liczb całkowitych to łańcuchy binarne, które kończą się na „11” i nie zawierają żadnych innych wystąpień „11”. Można to uogólnić na ciągi binarne, które kończą się N kolejnymi jedynekami i nie zawierają żadnych innych wystąpień N kolejnych jedynek. Na przykład dla N = 3 dodatnie liczby całkowite są kodowane jako 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, …. W tym przypadku liczba kodowań jako funkcja długości łańcucha jest określona przez sekwencję liczb Tribonacciego .

W przypadku ogólnych ograniczeń określających, które symbole są dozwolone po danym symbolu, maksymalną szybkość informacji można uzyskać, najpierw znajdując optymalne prawdopodobieństwa przejścia za pomocą błądzenia losowego maksymalnej entropii , a następnie użyć kodera entropijnego (z przełączanym koderem z dekoderem) do zakodowania wiadomości jako ciąg symboli spełniający znalezione optymalne prawdopodobieństwa przejścia.

Zobacz też

Allouche, Jean-Paul; Szallit, Jeffrey (2003). Sekwencje automatyczne: teoria, zastosowania, uogólnienia . Wydawnictwo Uniwersytetu Cambridge . P. 105 . ISBN 978-0-521-82332-6 . Zbl 1086.11015 .
Fraenkel, Aviezri S.; Klein, Shmuel T. (1996). „Solidne uniwersalne kompletne kody do transmisji i kompresji” . Dyskretna matematyka stosowana . 64 (1): 31–55. CiteSeerX 10.1.1.37.3064 . doi : 10.1016/0166-218X(93)00116-H . ISSN 0166-218X . Zbl 0874.94026 .

Dalsza lektura

Stachow, AP (2009). Matematyka harmonii: od Euklidesa do współczesnej matematyki i informatyki . Singapur: Światowe wydawnictwa naukowe .