Кодирование Фибоначчи

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

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

Определение

Для номера $N\!$ , если $d(0),d(1),\ldots ,d(k-1),d(k)\!$ представляют собой цифры кодового слова, обозначающего $N\!$ тогда мы имеем:

N=\sum _{i=0}^{k-1}d(i)F(i+2),{\text{ and }}d(k-1)=d(k)=1.\!

где $F (i)$ — $i-$ е число Фибоначчи , и поэтому $F (i +2)$ — $i-$ е отличное число Фибоначчи, начинающееся с $1,2,3,5,8,13,\ldots$ . Последний бит $d(k)$ всегда является добавленным битом 1 и не несет в себе разрядного значения.

Можно показать, что такое кодирование уникально, и единственное появление «11» в любом кодовом слове находится в конце, т. е. d ( k −1) и d ( k ). Предпоследний бит является наиболее значимым битом, а первый бит — наименее значащим битом. Также нельзя опускать ведущие нули, как, например, в десятичных числах.

Ниже показаны первые несколько кодов Фибоначчи, а также их так называемая подразумеваемая вероятность — значение для каждого числа, которое имеет код минимального размера в кодировании Фибоначчи.

Символ	Представление Фибоначчи	Кодовое слово Фибоначчи	Подразумеваемая вероятность
1	$F(2)$	11	1/4
2	$F(3)$	011	1/8
3	$F(4)$	0011	1/16
4	$F(2)+F(4)$	1011	1/16
5	$F(5)$	00011	1/32
6	$F(2)+F(5)$	10011	1/32
7	$F(3)+F(5)$	01011	1/32
8	$F(6)$	000011	1/64
9	$F(2)+F(6)$	100011	1/64
10	$F(3)+F(6)$	010011	1/64
11	$F(4)+F(6)$	001011	1/64
12	$F(2)+F(4)+F(6)$	101011	1/64
13	$F(7)$	0000011	1/128
14	$F(2)+F(7)$	1000011	1/128

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

Найдите наибольшее число Фибоначчи, равное или меньшее N ; вычтите это число из N , отслеживая остаток.
Если вычтенное число было i -м числом Фибоначчи F ( i ), поместите 1 на место i -2 в кодовом слове (считая самую левую цифру за позицию 0).
остатком Повторите предыдущие шаги, заменяя N , пока остаток не будет равен 0.
Поставьте дополнительную цифру 1 после самой правой цифры кодового слова.

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

Сравнение с другими универсальными кодами

Кодирование Фибоначчи обладает полезным свойством, которое иногда делает его привлекательным по сравнению с другими универсальными кодами: оно является примером самосинхронизирующегося кода , облегчающего восстановление данных из поврежденного потока. В большинстве других универсальных кодов, если изменить один бит , ни одна из данных, следующих за ним, не будет правильно прочитана. С другой стороны, при кодировании Фибоначчи измененный бит может привести к тому, что один токен будет прочитан как два, или к тому, что два токена будут прочитаны неправильно как один, но чтение «0» из потока остановит дальнейшее распространение ошибок. Поскольку единственный поток, в котором нет «0», — это поток токенов «11», общее расстояние редактирования между потоком, поврежденным одной битовой ошибкой, и исходным потоком составляет не более трех.

Этот подход — кодирование с использованием последовательности символов, в которой запрещены некоторые шаблоны (например, «11»), можно свободно обобщать. ^[1]

Пример

В следующей таблице показано, что число 65 представлено в кодировке Фибоначчи как 0100100011, поскольку 65 = 2 + 8 + 55 . Первые два числа Фибоначчи (0 и 1) не используются, всегда добавляется дополнительная 1.

{\begin{array}{ccccccccccc|c}\hline 0&1&1&2&3&5&8&13&21&34&55&-\\\hline F(0)&F(1)&F(2)&F(3)&F(4)&F(5)&F(6)&F(7)&F(8)&F(9)&F(10)&\scriptstyle {\text{additional}}\\\hline -&-&0&1&0&0&1&0&0&0&1&1\\\hline \end{array}}

Обобщения

Кодировки Фибоначчи для положительных целых чисел представляют собой двоичные строки, которые заканчиваются на «11» и не содержат других экземпляров «11». Это можно обобщить на двоичные строки, которые заканчиваются N последовательными единицами и не содержат других экземпляров N последовательных единиц. Например, для N = 3 положительные целые числа кодируются как 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, …. В этом случае количество кодировок как функция длины строки определяется последовательностью чисел Трибоначчи .

Для общих ограничений, определяющих, какие символы разрешены после данного символа, максимальная скорость передачи информации может быть получена путем нахождения оптимальных вероятностей перехода с использованием случайного блуждания с максимальной энтропией , а затем использования энтропийного кодера (с переключаемым кодером с декодером) для кодирования сообщения как последовательность символов, удовлетворяющая найденным оптимальным вероятностям перехода.

См. также

База золотого сечения
Негафибоначчи-кодирование
Нумерация Островского
Универсальный код
Варикод , практическое применение
Теорема Цекендорфа
Случайное блуждание с максимальной энтропией

Ссылки

^ Дуда, Ярек (2007). «Оптимальное кодирование на дискретной решетке с ограничениями трансляционного инварианта с использованием статистических алгоритмов». arXiv : 0710.3861 [ cs.IT ].

Аллуш, Жан-Поль; Шалит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . п. 105 . ISBN 978-0-521-82332-6 . Збл 1086.11015 .
Френкель, Авиезри С.; Кляйн, Шмуэль Т. (1996). «Надежные универсальные полные коды для передачи и сжатия». Дискретная прикладная математика . 64 (1): 31–55. CiteSeerX 10.1.1.37.3064 . дои : 10.1016/0166-218X(93)00116-H . ISSN 0166-218X . Збл 0874.94026 .

Дальнейшее чтение

Стахов, АП (2009). Математика гармонии: от Евклида к современной математике и информатике . Сингапур: Всемирное научное издательство .

[1] Дуда, Ярек (2007). «Оптимальное кодирование на дискретной решетке с ограничениями трансляционного инварианта с использованием статистических алгоритмов». arXiv : 0710.3861 [ cs.IT ].

[1]