Fibonacci coding

• Основы кодирования Фибоначчи

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

• Определение и кодирование

  • Для числа N, если d(0), d(1), …, d(k-1), d(k) представляют цифры кодового слова, то: 
  • d(k) всегда является битом «1» и не несет значения места. 
  • Кодирование уникально, и «11» в кодовом слове встречается только в конце. 
  • Последний бит является наиболее значимым, а первый — наименее значимым. 
  • Ведущие нули не могут быть опущены, как в десятичных числах. 

• Примеры и декодирование

  • Первые несколько кодовых слов Фибоначчи и их так называемая вероятность, значение для каждого числа с минимальным размером кода в кодировании Фибоначчи. 
  • Для кодирования целого числа N: найти наибольшее число Фибоначчи, меньшее или равное N, вычесть его из N, отслеживая остаток. 
  • Повторять предыдущие шаги, заменяя остаток на N, пока не останется 0. 
  • Добавить дополнительный 1 после последней цифры в кодовом слове. 
  • Для декодирования кодового слова удалить последний «1», присвоить оставшимся значениям 1, 2, 3, 5, 8, 13 … (числа Фибоначчи) и суммировать значения битов «1». 

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

  • Кодирование Фибоначчи обладает полезным свойством самосинхронизации, что облегчает восстановление данных из поврежденного потока. 
  • В отличие от большинства универсальных кодов, изменение одного бита может привести к ошибкам в данных, но в кодировании Фибоначчи это может привести к остановке ошибок. 
  • Общее расстояние редактирования между потоком, поврежденным одной ошибкой бита, и исходным потоком не превышает трех. 

• Обобщения

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

• Максимально возможная информационная скорость

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