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, ….
- Количество кодировок как функция длины строки задается последовательностью чисел Трибоначчи.
-
Максимально возможная информационная скорость
- Для общих ограничений на символы, разрешенные после заданного символа, максимальная информационная скорость может быть получена путем нахождения оптимальных переходных вероятностей с использованием максимальной энтропийной случайной прогулки, а затем использования энтропийного кодера для кодирования сообщения в соответствии с найденными оптимальными переходными вероятностями.
Полный текст статьи: