Мы все знаем как можно кодировать число в ту или иную систему счисления: в двоичную, восьмеричную, шестнадцатиричную. В этом материале я познакомлю Вас с кодированием на базе чисел Фиббоначи.
Многие про этот ряд слышали и сейчас я только хочу напомнить Вам этот ряд
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."
Чем же интересен построенный код?
Во первых он избыточен, даже слишком. Для любого числа код Фиббоначи, будет иметь такой вид, что между единицами как минимум(!) будет один ноль.
С одной стороны это плохо. На передачу такого кода понадобится почти в два раза больше времени, чем если бы кодирование осуществлялось двоичной системой.
В чем же плюс: В том, что избыточность кода позволяет нам легко обнаруживать ошибки при передаче. Это незаменимо при плохой связи.
Передача сообщений непрерывным потоком с помощь кодирования Фиббоначи, позволяет в реальном времени (в потоке) исправлять возникшие ошибки, по тому критерию, который был уже озвучен: в коде не может быть рядом стоящих единиц.
Кодирование 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 символов, например знаки препинания, математические знаки и прочее).
Даже немного завидую...
Несколько примеров
Исходное натуральное число 121
Перевод в Фиббоначиевую систему счисления 1001010100
Исходное натуральное число 666
Перевод в Фиббоначиевую систему счисления 10000100000001