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, …. 
  • Количество кодировок как функция длины строки задается последовательностью чисел Трибоначчи. 

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

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