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

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

Следующие шаги описывают, как закодировать ненулевое целое число . Обратите внимание, что обозначает последовательность Негафибоначчи.${\displaystyle x}$${\displaystyle f}$

1. Если положительно, вычислите наибольшее нечетное отрицательное целое число , такое что сумма нечетных отрицательных членов последовательности Негафибоначчи от -1 до с шагом -2 была больше или равна : Если отрицательно, вычислите наибольшее четное отрицательное целое число , такое что сумма четных отрицательных членов последовательности Негафибоначчи от 0 до с шагом -2 была меньше или равна :${\displaystyle x}$${\displaystyle n}$${\displaystyle n}$${\displaystyle x}$
   ${\displaystyle n\in \{-\left(2k+1\right),k\in [0,\infty [\},\quad \sum _{i=-1,\;i\;нечет}^{n-2}f(i)<x\leq \sum _{i=-1,\;i\;нечет}^{n}f(i).}$
   ${\displaystyle x}$${\displaystyle n}$${\displaystyle n}$${\displaystyle x}$
   ${\displaystyle n\in \{-2k,k\in [2,\infty [\},\quad \sum _{i=-2,\;i\;четно}^{n-2}f(i)>x\geq \sum _{i=-2,\;i\;четно}^{n}f(i)}$
2. Добавьте 1 к биту двоичного слова. Вычтите из .${\displaystyle |n|^{\text{й}}}$${\displaystyle f(n)}$${\displaystyle x}$
3. Повторите процесс с шага 1 с новым значением x , пока оно не достигнет 0.
4. Добавьте 1 слева от полученного двоичного слова, чтобы завершить кодирование.

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

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

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

• Числа Фибоначчи
• Золотое сечение основа
• Теорема Цекендорфа

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (September 2022) (Learn how and when to remove this message)