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

В математике негафибоначчиева система счисления — универсальный код, который кодирует ненулевые целые числа в двоичные кодовые слова. Обобщает фибоначчиеву систему счисления на все ненулевые целые числа (а не только натуральные). Все коды заканчиваются "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) соответствует номеру разряда в искомом слове.
2. Поставить единицу в N-ый разряд искомого слова.
3. Вычесть из кодируемого числа X значение N-го числа негафибоначчи.
4. Повторять шаги 1-3 пока X не станет равным нулю.
5. За старшим разрядом искомого слова помещается дополнительная единица (завершающий бит).

Пример для числа 16:

1. Суммируем положительные числа: 1+2+5+13=21 — найдена сумма превысившая число 16. Последним прибавлено число 13 (это 7-е число ряда).
2. Записываем единицу в 7-ю позицию: 0000001.
3. 16-13=3.
4. Суммируем: 1+2=3 — найдена сумма дающая число 3. Последним прибавлено число 2 (3-е число ряда).
5. Записываем единицу в 3-ю позицию: 0010001.
6. 3-2=1.
7. Суммируем: 1=1 — найдена сумма дающая число 1. Последним прибавлено число 1 (1-е число ряда).
8. Записываем единицу в 1-ю позицию: 1010001.
9. Добавляем завершающий бит: 10100011.

Для декодирования следует удалить последнюю единицу, остальным битам присвоить значения чисел негафибоначчи (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, Advances in unconventional computing and cellular automata, vol. 2, Archives contemporaines, p. 79, ISBN 9782914610834.