Кодирование Негафибоначчи
В математике представляет кодирование негафибоначчи собой универсальный код , который кодирует ненулевые целые числа в двоичные кодовые слова . Оно похоже на кодирование Фибоначчи , за исключением того, что оно позволяет представлять как положительные, так и отрицательные целые числа. Все коды заканчиваются на «11» и не имеют цифры «11» в конце.
Метод кодирования
[ редактировать ] | Этот раздел содержит инструкции, советы и инструкции . ( сентябрь 2022 г. ) |
Чтобы закодировать ненулевое целое число X :
- Вычислите наибольшее (или наименьшее) кодируемое число с помощью N битов путем суммирования нечетных (или четных) чисел негафибоначчи от 1 N. до
- Когда будет определено, что N бит достаточно, чтобы содержать X , вычтите N-е число негафибоначчи из X , отслеживая остаток, и поместите единицу в N-й бит вывода.
- Двигаясь вниз от N-го бита к первому, сравните каждое из соответствующих чисел негафибоначчи с остатком. Вычтите его из остатка, если абсолютное значение разницы меньше И если в следующем старшем бите еще нет единицы. В соответствующий бит помещается единица, если вычитание выполнено, или ноль, если нет.
- Для завершения поместите единицу в бит N+1 .
Чтобы декодировать токен в коде, удалите последнюю «1», присвойте оставшимся битам значения 1, –1, 2, –3, 5, –8, 13... (числа негафибоначчи) и добавьте « 1" биты.
Представление Негафибоначчи
[ редактировать ]| Часть серии о |
| Системы счисления |
|---|
| Список систем счисления |
Кодирование Негафибоначчи тесно связано с представлением Негафибоначчи , позиционной системой счисления, иногда используемой математиками. Код негафибоначчи для конкретного ненулевого целого числа в точности соответствует коду представления негафибоначчи целого числа, за исключением того, что порядок цифр изменен на обратный и в конце добавлена дополнительная цифра «1». Код негафибоначчи для всех отрицательных чисел имеет нечетное количество цифр, а для всех положительных чисел — четное количество цифр.
Стол
[ редактировать ]Код для целых чисел от −11 до 11 приведен ниже.
| Число | Представление Негафибоначчи | Код Негафибоначчи |
|---|---|---|
| −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 |
См. также
[ редактировать ]Ссылки
[ редактировать ] | Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( сентябрь 2022 г. ) |
Цитируемые работы
[ редактировать ]- Кнут, Дональд (2008). Числа Негафибоначчи и гиперболическая плоскость . Ежегодное собрание Математической ассоциации Америки. Сан-Хосе, Калифорния.
- Кнут, Дональд (2009). Искусство компьютерного программирования , Том 4, Глава 1: Побитовые приемы и методы; Бинарные диаграммы решений . Аддисон-Уэсли. ISBN 978-0-321-58050-4 . В предварительном проекте раздела 7.1.3 см., в частности, стр. 36–39.
- Маргенштерн, Морис (2008). Клеточные автоматы в гиперболических пространствах . Достижения в области нетрадиционных вычислений и клеточных автоматов. Том. 2. Архивы современности. п. 79. ИСБН 9782914610834 .
сжатия данных Методы |
|---|
