Fibonacci coding (original) (raw)
Le codage de Fibonacci est un codage entropique utilisé essentiellement en compression de données. Il utilise les nombres de la suite de Fibonacci, dont chaque terme est la somme des deux termes consécutifs précédents, ce qui lui confère une robustesse aux erreurs. Le code de Fibonacci produit est un code préfixe et universel.Dans ce code, on utilise la représentation de Zeckendorf, de telle façon que la séquence « 11 », interdite dans le nombre, apparaisse uniquement en fin de codage, et serve ainsi de délimiteur.
| Property | Value |
|---|---|
| dbo:abstract | In mathematics and computing, Fibonacci coding is a universal code which encodes positive integers into binary code words. It is one example of representations of integers based on Fibonacci numbers. Each code word ends with "11" and contains no other instances of "11" before the end. The Fibonacci code is closely related to the Zeckendorf representation, a positional numeral system that uses Zeckendorf's theorem and has the property that no number has a representation with consecutive 1s. The Fibonacci code word for a particular integer is exactly the integer's Zeckendorf representation with the order of its digits reversed and an additional "1" appended to the end. (en) Le codage de Fibonacci est un codage entropique utilisé essentiellement en compression de données. Il utilise les nombres de la suite de Fibonacci, dont chaque terme est la somme des deux termes consécutifs précédents, ce qui lui confère une robustesse aux erreurs. Le code de Fibonacci produit est un code préfixe et universel.Dans ce code, on utilise la représentation de Zeckendorf, de telle façon que la séquence « 11 », interdite dans le nombre, apparaisse uniquement en fin de codage, et serve ainsi de délimiteur. (fr) In de wiskunde en speciaal in de informatica is de Fibonacci-code een , gebaseerd op de Fibonacci-getallen (de getallen in de rij van Fibonacci), die de positieve gehele getallen codeert tot binaire woorden. De code wordt gebruikt in datacompressie, daarom eindigt elk woord met "11" en komt de combinatie "11" verder niet in een woord voor. Volgens de Stelling van Zeckendorf heeft elk positief geheel getal een Zeckendorf-representatie, een voorstelling als som van niet-opeenvolgende Fibonacci-getallen. Voor het getal 100 is dit: De rij van Fibonacci begint met: Voor 100 kan daarom in een soort positiestelsel geschreven worden: , waarin geteld wordt vanaf de tweede 1 in de rij.(Normaal gesproken zou dit andersom genoteerd worden met de hoogste positie voorop, dus als 1000010100.) De rij 0'en en 1'en eindigt voor elk getal met een 1. Voor de herkenbaarheid van het eind van de code voegt de Fibonacci-codering er nog een 1 aan toe. Omdat in de representatie nooit twee opeenvolgende Fibonacci-getallen voorkomen, staat alleen aan het eind van een code "11". De Fibonacci-code voor 100 is dus: (nl) La codifica di Fibonacci è una codificazione entropica per la rappresentazione dei numeri interi basata sulla successione di Fibonacci. Per il teorema di Zeckendorf esiste una rappresentazione unica degli interi come somma di numeri di Fibonacci distinti. La rappresentazione di Zeckendorf ha inoltre la proprietà che non sono presenti due cifre consecutive uguali ad uno. Si codifica quindi il numero in maniera inversa rispetto alla rappresentazione binaria polinomiale rispetto alla base φ, aggiungendo una cifra "1" in modo che termini con "11", ottenendo un codice prefisso. (it) System Fibonacciego to binarny, pozycyjny system liczbowy, w którym poszczególnym pozycjom odpowiadają kolejne liczby Fibonacciego. W zapisie liczby nie używa się pierwszych dwóch liczb z ciągu Fibonacciego (czyli zera i pierwszej z dwóch występujących w nim jedynek).Zaczynającemu się od 1 ciągowi cyfr 0 i 1 (tylko takich się używa) anan-1...a2odpowiada liczbaan⋅Fn+an-1⋅Fn-1 + ... + a2⋅F2. Na przykład liczba zapisana w systemie Fibonacciego jako 1000F oznacza piątą liczbę w ciągu Fibonacciego czyli 5, * 1000101F = F8+F4+F2 = 21+3+1 = 25 * 10010010F = F9+F6+F3 = 34+8+2 = 44 Taki sposób zapisu liczb nie byłby jednoznaczny (np. 100F=11F), więc dodaje się wymaganie, by kolejne dwie liczby nie były jednocześnie jedynkami (dwie jedynki zastępujemy jedną na wcześniejszym miejscu …011…= …100…). W ten sposób otrzymujemy jednoznaczny zapis każdej liczby naturalnej. (pl) Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т. д. (ru) Система числення Фібоначчі — змішана система числення для цілих чисел на основі чисел Фібоначчі , , , , і т. д. (uk) 斐波那契編碼（Fibonacci coding）是一種僅使用兩種符號（0和1）表達數值的。這種編碼是基於斐波那契數來表達整數的一個例子。這種編碼皆以「11」為結尾，並且在結尾之前不會出現連續2個1。 斐波那契編碼與齊肯多夫表述法密切相關。齊肯多夫表述法是一種基於齊肯多夫定理的进制系統，並且也具有不連續使用兩個1的特性。特定整數的斐波那契編碼正是數字順序顛倒的齊肯多夫表述法，並在末尾附加了一個額外的“1”。 (zh) |
| dbo:wikiPageExternalLink | https://archive.org/details/automaticsequenc00jpal https://archive.org/details/automaticsequenc00jpal/page/n122 |
| dbo:wikiPageID | 48063 (xsd:integer) |
| dbo:wikiPageLength | 7788 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1099281474 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Varicode dbr:Mathematics dbc:Fibonacci_numbers dbr:Golden_ratio_base dbr:Ostrowski_numeration dbr:Zeckendorf's_theorem dbr:Maximal_entropy_random_walk dbc:Lossless_compression_algorithms dbc:Non-standard_positional_numeral_systems dbr:Fibonacci_number dbr:Numeral_system dbr:Bit dbr:Code_word dbr:Edit_distance dbr:NegaFibonacci_coding dbr:Universal_code_(data_compression) dbr:Self-synchronizing_code dbr:Entropy_coder dbr:Tribonacci_number dbr:World_Scientific_Publishing |
| dbp:wikiPageUsesTemplate | dbt:Compression_Methods dbt:Citation_needed dbt:Cite_book dbt:Cite_journal dbt:Math dbt:No_footnotes dbt:Numeral_systems dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Fibonacci_numbers dbc:Lossless_compression_algorithms dbc:Non-standard_positional_numeral_systems |
| gold:hypernym | dbr:Code |
| rdf:type | yago:WikicatNon-standardPositionalNumeralSystems yago:WikicatNumeralSystems yago:Artifact100021939 yago:Instrumentality103575240 yago:Object100002684 yago:PhysicalEntity100001930 dbo:Film yago:System104377057 yago:Whole100003553 yago:WikicatPositionalNumeralSystems |
| rdfs:comment | Le codage de Fibonacci est un codage entropique utilisé essentiellement en compression de données. Il utilise les nombres de la suite de Fibonacci, dont chaque terme est la somme des deux termes consécutifs précédents, ce qui lui confère une robustesse aux erreurs. Le code de Fibonacci produit est un code préfixe et universel.Dans ce code, on utilise la représentation de Zeckendorf, de telle façon que la séquence « 11 », interdite dans le nombre, apparaisse uniquement en fin de codage, et serve ainsi de délimiteur. (fr) La codifica di Fibonacci è una codificazione entropica per la rappresentazione dei numeri interi basata sulla successione di Fibonacci. Per il teorema di Zeckendorf esiste una rappresentazione unica degli interi come somma di numeri di Fibonacci distinti. La rappresentazione di Zeckendorf ha inoltre la proprietà che non sono presenti due cifre consecutive uguali ad uno. Si codifica quindi il numero in maniera inversa rispetto alla rappresentazione binaria polinomiale rispetto alla base φ, aggiungendo una cifra "1" in modo che termini con "11", ottenendo un codice prefisso. (it) Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т. д. (ru) Система числення Фібоначчі — змішана система числення для цілих чисел на основі чисел Фібоначчі , , , , і т. д. (uk) 斐波那契編碼（Fibonacci coding）是一種僅使用兩種符號（0和1）表達數值的。這種編碼是基於斐波那契數來表達整數的一個例子。這種編碼皆以「11」為結尾，並且在結尾之前不會出現連續2個1。 斐波那契編碼與齊肯多夫表述法密切相關。齊肯多夫表述法是一種基於齊肯多夫定理的进制系統，並且也具有不連續使用兩個1的特性。特定整數的斐波那契編碼正是數字順序顛倒的齊肯多夫表述法，並在末尾附加了一個額外的“1”。 (zh) In mathematics and computing, Fibonacci coding is a universal code which encodes positive integers into binary code words. It is one example of representations of integers based on Fibonacci numbers. Each code word ends with "11" and contains no other instances of "11" before the end. (en) System Fibonacciego to binarny, pozycyjny system liczbowy, w którym poszczególnym pozycjom odpowiadają kolejne liczby Fibonacciego. W zapisie liczby nie używa się pierwszych dwóch liczb z ciągu Fibonacciego (czyli zera i pierwszej z dwóch występujących w nim jedynek).Zaczynającemu się od 1 ciągowi cyfr 0 i 1 (tylko takich się używa) anan-1...a2odpowiada liczbaan⋅Fn+an-1⋅Fn-1 + ... + a2⋅F2. Na przykład liczba zapisana w systemie Fibonacciego jako 1000F oznacza piątą liczbę w ciągu Fibonacciego czyli 5, * 1000101F = F8+F4+F2 = 21+3+1 = 25 * 10010010F = F9+F6+F3 = 34+8+2 = 44 (pl) In de wiskunde en speciaal in de informatica is de Fibonacci-code een , gebaseerd op de Fibonacci-getallen (de getallen in de rij van Fibonacci), die de positieve gehele getallen codeert tot binaire woorden. De code wordt gebruikt in datacompressie, daarom eindigt elk woord met "11" en komt de combinatie "11" verder niet in een woord voor. Volgens de Stelling van Zeckendorf heeft elk positief geheel getal een Zeckendorf-representatie, een voorstelling als som van niet-opeenvolgende Fibonacci-getallen. Voor het getal 100 is dit: De rij van Fibonacci begint met: , (nl) |
| rdfs:label | Fibonacci coding (en) Codifica di Fibonacci (it) Codage de Fibonacci (fr) Fibonacci-code (nl) System Fibonacciego (pl) Фибоначчиева система счисления (ru) 斐波那契编码 (zh) Система числення Фібоначчі (uk) |
| owl:sameAs | dbpedia-fr:Fibonacci coding freebase:Fibonacci coding yago-res:Fibonacci coding wikidata:Fibonacci coding dbpedia-it:Fibonacci coding dbpedia-nl:Fibonacci coding dbpedia-pl:Fibonacci coding dbpedia-ru:Fibonacci coding dbpedia-uk:Fibonacci coding dbpedia-zh:Fibonacci coding https://global.dbpedia.org/id/2UFad |
| prov:wasDerivedFrom | wikipedia-en:Fibonacci_coding?oldid=1099281474&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Fibonacci_coding |
| is dbo:wikiPageRedirects of | dbr:Fibonacci_code dbr:Fibonacci_encoding dbr:Fibonacci_representation |
| is dbo:wikiPageWikiLink of | dbr:Entropy_coding dbr:List_of_algorithms dbr:Non-adjacent_form dbr:List_of_recreational_number_theory_topics dbr:Varicode dbr:182_(number) dbr:Golden_ratio_base dbr:Comma_code dbr:Complete_sequence dbr:Zeckendorf's_theorem dbr:Maximal_entropy_random_walk dbr:Fibonacci_number dbr:Numbers_(season_4) dbr:Prefix_code dbr:Universal_code_(data_compression) dbr:Negafibonacci_coding dbr:List_of_things_named_after_Fibonacci dbr:Self-synchronizing_code dbr:Non-standard_positional_numeral_systems dbr:Fibonacci_code dbr:Fibonacci_encoding dbr:Fibonacci_representation |
| is dbp:lang of | dbr:182_(number) |
| is foaf:primaryTopic of | wikipedia-en:Fibonacci_coding |