Введение
Код Фибоначчи — это универсальный код, кодирующий положительные целые числа в двоичные кодовые слова. В математике и информатике кодирование Фибоначчи представляет собой универсальный код, кодирующий положительные целые числа в двоичные кодовые слова. Это один из примеров представления целых чисел на основе чисел Фибоначчи. Каждое кодовое слово заканчивается на "11" и не содержит других последовательностей "11" до конца. Код Фибоначчи тесно связан с представлением Зекендорфа — позиционной системой счисления, использующей теорему Зекендорфа и обладающей свойством, что ни одно число не имеет представления с двумя последовательными единицами. Кодовое слово Фибоначчи для данного целого числа является его представлением Зекендорфа, записанным в обратном порядке с добавленной в конце единицей.
In mathematics and computing, Fibonacci coding is a universal code which encodes positive integers into binary code words. It is one example of representations of integers based on Fibonacci numbers. Each code word ends with "11" and contains no other instances of "11" before the end. The Fibonacci code is closely related to the Zeckendorf representation, a positional numeral system that uses Zeckendorf's theorem and has the property that no number has a representation with consecutive 1s. The Fibonacci code word for a particular integer is exactly the integer's Zeckendorf representation with the order of its digits reversed and an additional "1" appended to the end.
Сравнение с другими универсальными кодами
Кодирование Фибоначчи обладает полезным свойством, которое иногда делает его более привлекательным по сравнению с другими универсальными кодами: это пример самосинхронизирующегося кода, что облегчает восстановление данных из поврежденной последовательности. В большинстве других универсальных кодов изменение одного бита приводит к тому, что ни один из последующих данных не будет прочитан правильно. Однако, при кодировании Фибоначчи измененный бит может привести к тому, что один токен будет интерпретирован как два, или два токена будут ошибочно интерпретированы как один, но чтение "0" из последовательности останавливает дальнейшее распространение ошибок. Поскольку единственная последовательность, не содержащая "0", – это последовательность токенов "11", общее расстояние редактирования между поврежденной одной битовой ошибкой последовательностью и исходной последовательностью не превышает трех. Этот подход – кодирование с использованием последовательности символов, в которой некоторые шаблоны (например, "11") запрещены – может быть свободно обобщен.
Пример
В следующей таблице показано, что число 65 в кодировке Фибоначчи представляется как 0100100011, поскольку 65 = 2 + 8 + 55. Первые два числа Фибоначчи (0 и 1) не используются, и в конце всегда добавляется единица.
Обобщения
Кодировки Фибоначчи для положительных целых чисел – это двоичные строки, заканчивающиеся на "11" и не содержащие других последовательностей "11". Это можно обобщить на двоичные строки, заканчивающиеся N последовательными единицами и не содержащие других последовательностей из N последовательных единиц. Например, для N = 3 положительные целые числа кодируются как 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111. В этом случае количество кодировок как функция от длины строки задается последовательностью чисел Трибоначчи. Для общих ограничений, определяющих допустимые символы, следующие за данным символом, максимальную скорость передачи информации можно получить, сначала определив оптимальные вероятности переходов с помощью случайного блуждания с максимальной энтропией, а затем используя энтропийный кодер (с кодером и декодером, работающими в режиме переключения), чтобы закодировать сообщение в виде последовательности символов, соответствующих найденным оптимальным вероятностям переходов.