Негафибоначчиево кодирование

В математике негафибоначчиева система счисления — универсальный код, который кодирует ненулевые целые числа в двоичные кодовые слова. Обобщает фибоначчиеву систему счисления на все ненулевые целые числа (а не только натуральные). Все коды заканчиваются "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 следует:

Рассчитать количество необходимых разрядов N путём суммирования нечетных (или четных) чисел негафибоначчи с номерами от 1 до N.
После нахождения N — количества битов для кодирования X — вычесть N-е число негафибоначчи из X, запомнить получившуюся разность и поставить единицу на место N-го разряда искомого кодового слова.
Спускаясь от N-го бита до первого, сравнивать каждое соответствующее число негафибоначчи с получившейся разностью. Вычитать его из разности, если модуль новой разности будет меньше, и, кроме того, предыдущий старший разряд не единица. Рассматривать новую разность и т.д. В соответствующий разряд ставится единица, если вычитание осуществлялось, и ноль в противном случае.
На N+1-е место помещается единица, чтобы закончить кодирование и показать, что бит, чтобы закончить.

Для декодирования следует удалить последнюю единицу, остальным битам присвоить значения 1, -1, 2, -3, 5, -8, 13... (числа негафибоначчи), и сложить значения в ненулевых разрядах.

См. такжеПравить

СсылкиПравить

Knuth, Donald (2008), Negafibonacci Numbers and the Hyperbolic Plane, Paper presented at the annual meeting of the Mathematical Association of America, San Jose, California .
Knuth, Donald (2009), The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams, ISBN 0-321-58050-8 . In the pre-publication draft of section 7.1.3 see in particular pp. 36–39.
Margenstern, Maurice (2008), Cellular Automata in Hyperbolic Spaces, vol. 2, Advances in unconventional computing and cellular automata, Archives contemporaines, с. 79, ISBN 9782914610834, <https://books.google.com/books?id=eEgvfic3A4kC&pg=PA79> .