> fibonacci | zeckendorf | universal <
// Кодирование Фибоначчи — самосинхронизирующийся код на основе математики золотого сечения
Универсальный код
Работает для любого положительного целого числа без дополнительных параметров.
Самосинхронизация
Позволяет восстановить синхронизацию после ошибок передачи, используя шаблон 11.
Золотое сечение
Основан на последовательности Фибоначчи и теореме Цеккендорфа.
>> техническая информация
Как работает кодирование Фибоначчи:
Кодирование Фибоначчи использует теорему Цеккендорфа: любое положительное целое число имеет единственное представление в виде суммы не соседних чисел Фибоначчи. Код — это двоичное представление этой суммы (1, если данное число Фибоначчи используется, 0 — если нет) с добавлением завершающего бита 1. Шаблон 11 появляется только в конце кода.
Примеры кодирования:
Последовательность Фибоначчи: 1, 2, 3, 5, 8, 13, 21... 1 = F(1) → 11 2 = F(2) → 011 3 = F(3) → 0011 4 = F(3)+F(1) → 1011 5 = F(4) → 00011 12 = F(5)+F(3)+F(1) → 101011 Не используются соседние числа Фибоначчи Шаблон 11 встречается только в конце кода
Зачем использовать кодирование Фибоначчи:
- ▸Свойство самосинхронизации
- ▸Не требует параметров
- ▸Устойчивость к ошибкам
- ▸Единственное представление
- ▸Математическая элегантность
>> часто задаваемые вопросы
Что такое кодирование Фибоначчи?
Кодирование Фибоначчи — это универсальный код, представляющий положительные целые числа с помощью последовательности Фибоначчи. Он основан на теореме Цеккендорфа и формирует самосинхронизирующиеся коды, где шаблон 11 встречается только как терминатор.
Что такое представление Цеккендорфа?
Теорема Цеккендорфа утверждает, что любое положительное целое число можно единственным образом представить в виде суммы не соседних чисел Фибоначчи. Это представление лежит в основе кодирования Фибоначчи.
Почему код самосинхронизирующийся?
Шаблон 11 то есть две единицы подряд появляется только в конце каждого кодового слова. Поэтому декодер может после ошибок передачи восстановить границы слов, отыскивая в потоке битов вхождения 11.
Где используется кодирование Фибоначчи?
Кодирование Фибоначчи используется в исследованиях по сжатию данных, в помехоустойчивых системах передачи и в теоретической информатике. Его ценят прежде всего за математические свойства, а не за практическую эффективность.