Negafibonacci coding (original) (raw)
In mathematics, negafibonacci coding is a universal code which encodes nonzero integers into binary code words. It is similar to Fibonacci coding, except that it allows both positive and negative integers to be represented. All codes end with "11" and have no "11" before the end.
| Property | Value |
|---|---|
| dbo:abstract | In mathematics, negafibonacci coding is a universal code which encodes nonzero integers into binary code words. It is similar to Fibonacci coding, except that it allows both positive and negative integers to be represented. All codes end with "11" and have no "11" before the end. (en) В математике негафибоначчиева система счисления — универсальный код, который кодирует ненулевые целые числа в двоичные кодовые слова. Обобщает фибоначчиеву систему счисления на все ненулевые целые числа (а не только натуральные). Все коды заканчиваются "11" и не имеют "11" в середине или начале слова. Коды для целых чисел от -11 до 11 приведены ниже. xx негафибоначчиево представление негафибоначчиев код-11 101000 0001011-10 101001 1001011-9 100010 0100011-8 100000 0000011-7 100001 1000011-6 100100 0010011-5 100101 1010011-4 1010 01011-3 1000 00011-2 1001 10011-1 10 011 0 0 (не кодируется) 1 1 11 2 100 0011 3 101 1011 4 10010 010011 5 10000 000011 6 10001 100011 7 10100 001011 8 10101 101011 9 1001010 01010011 10 1001000 00010011 11 1001001 10010011 Код Фибоначчи тесно связан с негафибоначчиевым представлением, иногда используемой математиками позиционной системой счисления. Код негафибоначчи для каждого ненулевого целого числа — это в точности его негафибоначчиево представление (представление через числа Фибоначчи с отрицательными номерами) с обратным порядком цифр и дополнительной единицей в конце. Все отрицательные числа имеют нечетное количество разрядов, все положительные — четное. Для кодирования ненулевого целого числа X следует: 1. * Рассчитать количество необходимых разрядов N путём суммирования нечетных (или четных) чисел негафибоначчи с номерами от 1 до N. 2. * После нахождения N — количества битов для кодирования X — вычесть N-е число негафибоначчи из X, запомнить получившуюся разность и поставить единицу на место N-го разряда искомого кодового слова. 3. * Спускаясь от N-го бита до первого, сравнивать каждое соответствующее число негафибоначчи с получившейся разностью. Вычитать его из разности, если модуль новой разности будет меньше, и, кроме того, предыдущий старший разряд не единица. Рассматривать новую разность и т.д. В соответствующий разряд ставится единица, если вычитание осуществлялось, и ноль в противном случае. 4. * На N+1-е место помещается единица, чтобы закончить кодирование и показать, что бит, чтобы закончить. Для декодирования следует удалить последнюю единицу, остальным битам присвоить значения 1, -1, 2, -3, 5, -8, 13... (числа негафибоначчи), и сложить значения в ненулевых разрядах. (ru) |
| dbo:wikiPageExternalLink | https://www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz https://books.google.com/books%3Fid=eEgvfic3A4kC&pg=PA79 |
| dbo:wikiPageID | 10335993 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-fr:Codage_de_Fibonacci |
| dbo:wikiPageLength | 4854 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1112702359 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Mathematics dbc:Fibonacci_numbers dbr:Golden_ratio_base dbr:Zeckendorf's_theorem dbc:Lossless_compression_algorithms dbc:Non-standard_positional_numeral_systems dbr:Numeral_system dbr:Fibonacci_numbers dbr:Code_word dbr:Fibonacci_coding dbr:Universal_code_(data_compression) dbr:The_Art_of_Computer_Programming |
| dbp:wikiPageUsesTemplate | dbt:Compression_Methods dbt:Cite_book dbt:Cite_conference dbt:No_footnotes dbt:Numeral_systems dbt:Refbegin dbt:Refend dbt:Reflist dbt:How_to |
| dcterms:subject | dbc:Fibonacci_numbers dbc:Lossless_compression_algorithms dbc:Non-standard_positional_numeral_systems |
| rdfs:comment | In mathematics, negafibonacci coding is a universal code which encodes nonzero integers into binary code words. It is similar to Fibonacci coding, except that it allows both positive and negative integers to be represented. All codes end with "11" and have no "11" before the end. (en) В математике негафибоначчиева система счисления — универсальный код, который кодирует ненулевые целые числа в двоичные кодовые слова. Обобщает фибоначчиеву систему счисления на все ненулевые целые числа (а не только натуральные). Все коды заканчиваются "11" и не имеют "11" в середине или начале слова. Коды для целых чисел от -11 до 11 приведены ниже. Для кодирования ненулевого целого числа X следует: Для декодирования следует удалить последнюю единицу, остальным битам присвоить значения 1, -1, 2, -3, 5, -8, 13... (числа негафибоначчи), и сложить значения в ненулевых разрядах. (ru) |
| rdfs:label | Negafibonacci coding (en) Негафибоначчиево кодирование (ru) |
| owl:sameAs | wikidata:Negafibonacci coding dbpedia-ru:Negafibonacci coding https://global.dbpedia.org/id/cEMG |
| prov:wasDerivedFrom | wikipedia-en:Negafibonacci_coding?oldid=1112702359&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Negafibonacci_coding |
| is dbo:wikiPageRedirects of | dbr:NegaFibonacci_coding dbr:Negafibonacci_representation dbr:Negafibonacci |
| is dbo:wikiPageWikiLink of | dbr:NegaFibonacci_coding dbr:Negafibonacci_representation dbr:Negafibonacci |
| is foaf:primaryTopic of | wikipedia-en:Negafibonacci_coding |