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

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