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