Код Фиббоначи. Система счисления

Целое положительное число не больше 1 миллиона

Исходное натуральное число

Результат кодирования в код Фиббоначи

Перевод вычисленного кода в десятиричную систему

Мы все знаем как можно кодировать число в ту или иную систему счисления: в двоичную, восьмеричную, шестнадцатиричную. В этом материале я познакомлю Вас с кодированием на базе чисел Фиббоначи.

Про эти числа уже рассказывалось и сейчас я только хочу напомнить Вам этот ряд

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946

Этим рядом, можно также привести любое натуральное число в совокупность нулей и единиц, как это делается например в двоичной системе.

Алгоритм кодирования (вернее его описание) мы возьмем с википедии без каких либо изменений

"Для кодирования целого числа N :

Найти наибольшее число Фибоначчи, равное или меньшее N ; вычтите это число из N , отслеживая остаток.
Если вычтенное число было i- м числом Фибоначчи F ( i ), поместите 1 вместо i -2 в кодовом слове (считая самую левую цифру как место 0).
Повторите предыдущие шаги, заменяя остаток на N , пока не будет достигнут остаток от 0.
Поместите еще 1 после самой правой цифры в кодовом слове."

Но калькулятор который осуществляет кодирование на этой странице построен совсем по другому принципу.

Как минимум не выполняется 4 пункт. Он ставит единицу как маркер окончания слова. В моем калькуляторе этого нет.

Что касается алгоритма...

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

Калькулятор имеет ограничение сверху в один миллион. Для того что бы понять структуру, применимость кода этого вполне достаточно.

Кроме этого код преобразует полученную совокупность нулей и единиц в десятичную систему по двоичной базе.

Чем же интересен построенный код?

Во первых он избыточен, даже слишком. Для любого числа код Фиббоначи, будет иметь такой вид, что между единицами как минимум(!) будет один ноль.

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

В чем же плюс: В том, что избыточность кода позволяет нам легко обнаруживать ошибки при передаче. Это незаменимо при плохой связи, при общении с поселениями на различных планетах.

Передача сообщений непрерывным потоком с помощь кодирования Фиббоначи, позволяет в реальном времени (в потоке) исправлять возникшие ошибки, по тому критерию, который был уже озвучен: в коде не может быть рядом стоящих единиц.

Кодирование 8-ми битной таблицы символов ASCII новым кодом потребовало бы 11 разрядов ( 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ), но туда помещались бы не 256 знаков, а 287 (2*144-1). С учетом уже "встроенной помехоустойчивости" это неплохо, получить еще лишний 31 знак.

Так как букв в алфавите 33, то мы можем зашифровать каждую букву 7-ью битами (1,2,3,5,8,13,21). В этот же размер помещается еще дополнительно 8 знаков(21*2-1-33). Мы можем наш алфавит уменьшить до 31 ( считая что е- ё, и-й одной буквой) и получим что что в 7 бит мы поместили русский алфавит и все цифры.

С английским языком еще проще. Там всего 23 буквы и кодируя 7-ми битным кодом, мы умещаем (не только английский алфавит и все цифры, но и еще 8 символов, например знаки препинания, математические знаки и прочее).

Даже немного завидую...

Несколько примеров

Исходное натуральное число

$Исходное натуральное число$