WikiDer > Кодирование НегаФибоначчи

NegaFibonacci coding

В математика, кодирование негаФибоначчи это универсальный код который кодирует ненулевые целые числа в двоичную систему кодовые слова. Это похоже на Кодирование Фибоначчи, за исключением того, что он позволяет представлять как положительные, так и отрицательные целые числа. Все коды заканчиваются на «11» и не имеют «11» в конце.

Код Фибоначчи тесно связан с представление negaFibonacciпозиционный система счисления иногда используется математиками. Код negaFibonacci для конкретного ненулевого целого числа в точности совпадает с кодом представления negaFibonacci целого числа, за исключением того, что порядок его цифр изменен на противоположный, и в конце добавлена ​​дополнительная «1». Код НегаФибоначчи для всех отрицательных чисел состоит из нечетного числа цифр, а для всех положительных чисел - из четного числа цифр.

Метод кодирования

Чтобы закодировать ненулевое целое число Икс:

  1. Вычислить наибольшее (или наименьшее) кодируемое число с помощью N бит путем суммирования нечетных (или четных) Негафибоначчи числа от 1 до N.
  2. Когда будет установлено, что N бит достаточно, чтобы содержать Икс, вычтите Nth число negaFibonacci из Икс, отслеживая остаток, и поместите единицу в Nth бит вывода.
  3. Работая вниз от Nth бит с первым, сравните каждое из соответствующих чисел негаФибоначчи с остатком. Вычтите его из остатка, если абсолютное значение разницы меньше, И если в следующем более высоком бите еще нет единицы. Единица помещается в соответствующий бит, если выполняется вычитание, или ноль, если нет.
  4. Поместите один в N + 1-й немного закончить.

Чтобы декодировать токен в коде, удалите последнюю «1», присвойте оставшимся битам значения 1, -1, 2, -3, 5, -8, 13… ( Negafibonacci числа) и сложите биты "1".

Таблица

Код для целых чисел от −11 до 11 приведен ниже.

количествопредставление negaFibonacciкод negaFibonacci
−111010000001011
−101010011001011
−91000100100011
−81000000000011
−71000011000011
−61001000010011
−51001011010011
−4101001011
−3100000011
−2100110011
−110011
00(не может быть закодирован)
1111
21000011
31011011
410010010011
510000000011
610001100011
710100001011
810101101011
9100101001010011
10100100000010011
11100100110010011

Смотрите также

использованная литература

  • Кнут, Дональд (2008), Числа Негафибоначчи и гиперболическая плоскость, Доклад, представленный на ежегодном собрании Математической ассоциации Америки, Сан-Хосе, Калифорния..
  • Кнут, Дональд (2009), Искусство программирования, Том 4, Часть 1: Побитовые приемы и методы; Диаграммы двоичных решений, ISBN 0-321-58050-8. в предпубликационный черновик раздела 7.1.3 см., в частности, стр. 36–39.
  • Маргенштерн, Морис (2008), Клеточные автоматы в гиперболических пространствах, Достижения в области нетрадиционных вычислений и клеточных автоматов, 2, Archives contemporaines, стр. 79, ISBN 9782914610834.