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