Fibonacci-Codierung - Fibonacci coding

Zahlensysteme
Hindu-Arabisches Zahlensystem
Westarabisch Ostarabisch Bengali Devanagari Gujarati Gurmukhi Odia singhalesisch Tamil Malayalam Telugu Kannada Dzongkha Tibetisch Balinesisch birmanisch Javanisch Khmer Laos mongolisch Thai
Ostasiate
Chinesisch Suzhou Hokkien japanisch Koreanisch Vietnamesisch Tangut Zählstäbe
amerikanisch
Cherokee Kaktovik (Iñupiaq)
Alphabetisch
Abjad Armenisch ryabhaṭa kyrillisch Meine Güte georgisch griechisch hebräisch römisch
Ehemalige
ägäisch Dachboden Babylonisch Brahmi Tschuwaschen Zisterzienser ägyptisch Etrusker glagolitisch Kharosthi Maya- Musik Pentimal Rumi Prähistorische Zählung Zählmarken Quipu
Positionssysteme nach Basis
2 3 4 5 6 8 10 12 16 20 60
Nicht standardmäßige Positionsziffernsysteme
Bijektive Numerierung ( 1 ) Vorzeichen-Darstellung ( symmetrisch ternär ) gemischt ( faktoriell ) Negativ Komplexbasissystem ( 2 i ) Nicht ganzzahlige Numerierungsbasis ( φ ) Asymmetrische Zahlensysteme
Liste der Zahlensysteme
v t e

In der Mathematik und Informatik ist die Fibonacci-Codierung ein universeller Code, der positive ganze Zahlen in binäre Codewörter codiert . Es ist ein Beispiel für Darstellungen von ganzen Zahlen basierend auf Fibonacci-Zahlen . Jedes Codewort endet mit "11" und enthält keine weiteren Instanzen von "11" vor dem Ende.

Der Fibonacci - Code ist eng mit der im Zusammenhang Zeckendorf Darstellung eines Positionszahlensystem , das verwendet Zeckendorf-Theorem und hat die Eigenschaft , daß keine Zahl , die eine Darstellung mit konsekutiver 1s hat. Das Fibonacci-Codewort für eine bestimmte ganze Zahl ist genau die Zeckendorf-Darstellung der ganzen Zahl mit umgekehrter Reihenfolge ihrer Ziffern und einer zusätzlichen "1" am Ende.

Definition

Für eine Zahl , wenn die Ziffern des Codeworts darstellen , haben wir: ${\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{ und }}d(k-1)=d(k)=1 .\!}$

wobei F ( i ) die i- te Fibonacci-Zahl ist , und somit ist F ( i +2) die i- te unterschiedliche Fibonacci-Zahl beginnend mit . Das letzte Bit ist immer ein angehängtes Bit von 1 und trägt keinen Stellenwert. ${\displaystyle 1,2,3,5,8,13,\ldots}$${\displaystyle d(k)}$

Es kann gezeigt werden, dass eine solche Codierung einzigartig ist und das einzige Vorkommen von "11" in jedem Codewort am Ende ist, dh d ( k −1) und d ( k ). Das vorletzte Bit ist das höchstwertige Bit und das erste Bit ist das niedrigstwertige Bit. Auch führende Nullen dürfen nicht weggelassen werden, wie dies zB bei Dezimalzahlen der Fall ist.

Die ersten paar Fibonacci-Codes werden unten gezeigt, und auch ihre sogenannte implizite Wahrscheinlichkeit , der Wert für jede Zahl, die einen Code mit minimaler Größe in der Fibonacci-Codierung hat.

Symbol	Fibonacci-Darstellung	Fibonacci-Codewort	Implizite Wahrscheinlichkeit
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

So codieren Sie eine ganze Zahl N :

1. Finden Sie die größte Fibonacci-Zahl gleich oder kleiner als N ; subtrahiere diese Zahl von N und behalte den Rest im Auge.
2. Wenn die subtrahierte Zahl die i- te Fibonacci-Zahl F ( i ) war, setze eine 1 an die Stelle i −2 im Codewort (zähle die Ziffer ganz links als Stelle 0).
3. Wiederholen Sie die vorherigen Schritte und ersetzen Sie N durch den Rest , bis ein Rest von 0 erreicht ist.
4. Platzieren Sie eine zusätzliche 1 nach der Ziffer ganz rechts im Codewort.

Um ein Codewort zu decodieren, entfernen Sie die letzte "1", weisen Sie den verbleibenden Werten 1,2,3,5,8,13... (die Fibonacci-Zahlen ) den Bits im Codewort zu und summieren Sie die Werte von die "1"-Bits.

Vergleich mit anderen Universalcodes

Fibonacci-Codierung hat eine nützliche Eigenschaft, die sie manchmal im Vergleich zu anderen universellen Codes attraktiv macht: Es ist ein Beispiel für einen selbstsynchronisierenden Code , der es einfacher macht, Daten aus einem beschädigten Stream wiederherzustellen. Bei den meisten anderen universellen Codes werden, wenn ein einzelnes Bit geändert wird, keine der darauffolgenden Daten korrekt gelesen. Bei der Fibonacci-Codierung kann ein geändertes Bit andererseits dazu führen, dass ein Token als zwei gelesen wird oder dass zwei Token fälschlicherweise als eins gelesen werden, aber das Lesen einer "0" aus dem Stream verhindert, dass sich die Fehler weiter ausbreiten. Da der einzige Stream, der keine "0" enthält, ein Stream von "11"-Token ist, beträgt die gesamte Editierentfernung zwischen einem durch einen einzelnen Bitfehler beschädigten Stream und dem ursprünglichen Stream höchstens drei.

Dieser Ansatz – die Kodierung unter Verwendung einer Folge von Symbolen, bei der einige Muster (wie „11“) verboten sind – kann frei verallgemeinert werden.

Beispiel

Die folgende Tabelle zeigt, dass die Zahl 65 in der Fibonacci-Codierung als 0100100011 dargestellt wird, da 65 = 2 + 8 + 55 . Die ersten beiden Fibonacci-Zahlen (0 und 1) werden nicht verwendet, und es wird immer eine zusätzliche 1 angehängt.

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

Verallgemeinerungen

Die Fibonacci-Kodierungen für die positiven ganzen Zahlen sind binäre Strings, die mit "11" enden und keine anderen Instanzen von "11" enthalten. Dies kann auf binäre Zeichenfolgen verallgemeinert werden, die mit N aufeinanderfolgenden Einsen enden und keine anderen Instanzen von N aufeinanderfolgenden Einsen enthalten. Für N  = 3 werden die positiven ganzen Zahlen beispielsweise als 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, … codiert. In diesem Fall ist die Anzahl der Codierungen als Funktion der Stringlänge durch die Folge der Tribonacci-Zahlen gegeben .

Für allgemeine Beschränkungen, die definieren, welche Symbole nach einem gegebenen Symbol erlaubt sind, kann die maximale Informationsrate erhalten werden, indem zuerst die optimalen Übergangswahrscheinlichkeiten unter Verwendung des maximalen Entropie-Random-Walks gefunden werden und dann Entropiecodierer (mit geschaltetem Codierer mit Decoder) verwendet wird, um eine Nachricht als a Folge von Symbolen, die die gefundenen optimalen Übergangswahrscheinlichkeiten erfüllen.

Siehe auch

• Basis des Goldenen Schnitts
• NegaFibonacci-Codierung
• Ostrowski-Nummerierung
• Universalcode
• Varicode , eine praktische Anwendung
• Satz von Zeckendorf
• Random Walk mit maximaler Entropie

Verweise

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatische Sequenzen: Theorie, Anwendungen, Verallgemeinerungen . Cambridge University Press . s. 105 . ISBN 978-0-521-82332-6. Zbl  1086.11015 .
• Fraenkel, Aviezri S.; Klein, Schmuel T. (1996). "Robuste universelle Komplettcodes für Übertragung und Komprimierung". Diskrete Angewandte Mathematik . 64 (1): 31–55. CiteSeerX  10.1.1.37.3064 . doi : 10.1016/0166-218X(93)00116-H . ISSN  0166-218X . Zbl  0874.94026 .

Weiterlesen

• Stakhov, AP (2009). Die Mathematik der Harmonie: Von Euklid zu zeitgenössischer Mathematik und Informatik . Singapur: World Scientific Publishing .