Фибоначчиева система счисления (фсс)

Для компьютеров, основанных на классической двоичной системе счисления, не всегда можно эффективно решать проблему отсутствия механизма обнаружения ошибок. В 80-х годах XX столетия группа ученых под руководством профессора Алексея Петровича Стахова из Таганрогского радиотехнического института создала опытный экземпляр помехоустойчивого процессора [3]. Этот процессор мог сам контролировать возникающие в его работе сбои. Для кодирования информации была выбрана фибоначчиева система счисления. Ее использование позволило построить удивительный процессор, на званный “Фибоначчи-процессор”, или “Ф-процессор”. И хотя успешная попытка построения помехоустойчивого процессора на основе фибоначчиевой системы счисления носила скорее теоретический, чем практический интерес, изучение этой замечательной системы счисления заслуживает внимания.

Для указания, что число записано в ФСС, будем использовать в нижнем индексе сокращение fib. Например, 10000101 _fib = 38₁₀.

Числа Фибоначчи — элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10 946, …, в которой каждое последующее число, начиная с третьего, равно сумме двух предыдущих чисел.

Для формального определения чисел Фибоначчи используют следующее рекуррентное соотношение:

F ₀ = 1, F 1 = 1, F_n = F_{n 2} + F_n1.

Последовательность, известная у нас как числа Фибоначчи, использовалась в Древней Индии задолго до того, как стала известна в Европе после изучения и описания ее Леонардо Пизанским Фибоначчи (1170-1250).

Леонардо Пизанский Фибоначчи. Благодаря книге Фибоначчи “Liber Abaci” Европа узнала индоарабскую систему чисел, которая позднее вытеснила традиционные для того времени римские числа.

ФСС относится к позиционным системам. Алфавитом ФСС являются цифры 0 и 1, а ее базисом — последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …. Обратите внимание, что F 0 = 1 в базис не включается.

В табл. перечислены некоторые числа в двоичной и фибоначчиевой системах счисления.

Фибоначчиева система является разновидностью двоичной системы — ее алфавит составляют цифры 0 и 1. Следовательно, эту неклассическую двоичную систему счисления, вообще говоря, можно использовать для кодирования информации в компьютере, так как элементная база современной компьютерной техники ориентирована на обработку двоичных последовательностей.

Избыточность ФСС проявляется в различных кодовых представлениях одного и того же числа.

4.1. Алгоритмы перевода целых чисел из ФСС в десятичную систему и обратно

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

В P -ичных системах счисления базис является геометрической прогрессией. Вклад в значение числа цифры a, стоящей на k -м месте слева, равен a-P^k, где P — основание системы счисления. Часто говорят, что “вес” k -го разряда равен P^k.

В ФСС “вес” каждого разряда числа также определяется базисом этой системы. Для удобства дальнейшей работы выпишем “веса” первых 10 разрядов ФСС (нумерацию разрядов ведем справа налево, начиная с первого). Такая нумерация разрядов удобна, поскольку в качестве веса k -го разряда используется k -е число Фибоначчи.

Пример 1. Пусть нам дано число A_fib = 10101010 записанное в фсс. Чему равно это число в десятичной системе счисления?

Чтобы ответить на этот вопрос, запишем цифры числа в разрядную сетку, затем умножим каждую цифру на вес разряда и сложим полученные числа. Так как цифрами фибоначчиевой системы счисления являются 0 и 1, то нам достаточно сложить веса тех разрядов, где стоят единицы.

Получим: A_fib = 10101010 _fib = 34 + 13 + 5 + 2 = 54₁₀.