Системы счисления. Литература Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М. Бином. Лаборатория знаний, 2004
 Скачать 215 Kb.
|
|
Фибоначчиева система счисления (фсс) Для компьютеров, основанных на классической двоичной системе счисления, не всегда можно эффективно решать проблему отсутствия механизма обнаружения ошибок. В 80-х годах XX столетия группа ученых под руководством профессора Алексея Петровича Стахова из Таганрогского радиотехнического института создала опытный экземпляр помехоустойчивого процессора [3]. Этот процессор мог сам контролировать возникающие в его работе сбои. Для кодирования информации была выбрана фибоначчиева система счисления. Ее использование позволило построить удивительный процессор, на званный “Фибоначчи-процессор”, или “Ф-процессор”. И хотя успешная попытка построения помехоустойчивого процессора на основе фибоначчиевой системы счисления носила скорее теоретический, чем практический интерес, изучение этой замечательной системы счисления заслуживает внимания. Для указания, что число записано в ФСС, будем использовать в нижнем индексе сокращение fib. Например, 10000101fib = 3810. Числа Фибоначчи — элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10 946, …, в которой каждое последующее число, начиная с третьего, равно сумме двух предыдущих чисел. Для формального определения чисел Фибоначчи используют следующее рекуррентное соотношение: F0 = 1, F1 = 1, Fn= Fn2 + Fn1 . Последовательность, известная у нас как числа Фибоначчи, использовалась в Древней Индии задолго до того, как стала известна в Европе после изучения и описания ее Леонардо Пизанским Фибоначчи (1170-1250).  Леонардо Пизанский Фибоначчи. Благодаря книге Фибоначчи “LiberAbaci” Европа узнала индоарабскую систему чисел, которая позднее вытеснила традиционные для того времени римские числа. ФСС относится к позиционным системам. Алфавитом ФСС являются цифры 0 и 1, а ее базисом — последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 … . Обратите внимание, что F0 = 1 в базис не включается. В табл. перечислены некоторые числа в двоичной и фибоначчиевой системах счисления.
Фибоначчиева система является разновидностью двоичной системы — ее алфавит составляют цифры 0 и 1. Следовательно, эту неклассическую двоичную систему счисления, вообще говоря, можно использовать для кодирования информации в компьютере, так как элементная база современной компьютерной техники ориентирована на обработку двоичных последовательностей. Избыточность ФСС проявляется в различных кодовых представлениях одного и того же числа. 4.1. Алгоритмы перевода целых чисел из ФСС в десятичную систему и обратно Как известно, все позиционные системы устроены одинаково и, следовательно, перевод из любой позиционной системы счисления в десятичную осуществляется по одному и тому же алгоритму. В P-ичных системах счисления базис является геометрической прогрессией. Вклад в значение числа цифры a, стоящей на k-м месте слева, равен a-Pk, где P — основание системы счисления. Часто говорят, что “вес” k-го разряда равен Pk. В ФСС “вес” каждого разряда числа также определяется базисом этой системы. Для удобства дальнейшей работы выпишем “веса” первых 10 разрядов ФСС (нумерацию разрядов ведем справа налево, начиная с первого). Такая нумерация разрядов удобна, поскольку в качестве веса k-го разряда используется k-е число Фибоначчи.
Пример 1. Пусть нам дано число Afib= 10101010 записанное в фсс. Чему равно это число в десятичной системе счисления? Чтобы ответить на этот вопрос, запишем цифры числа в разрядную сетку, затем умножим каждую цифру на вес разряда и сложим полученные числа. Так как цифрами фибоначчиевой системы счисления являются 0 и 1, то нам достаточно сложить веса тех разрядов, где стоят единицы.
Получим: Afib = 10101010fib = 34 + 13 + 5 + 2 = 5410. Алгоритм перевода целых чисел из фибоначчиевой системы счисления в десятичную
Пример 2. Решим обратную задачу. Запишем в фибоначчиевой системе счисления десятичные числа 1010, 2510 и 10010. Для решения нашей задачи достаточно подобрать такие числа Фибоначчи, сумма которых равна исходному десятичному числу. Например, число 10 можно представить суммой следующих чисел Фибоначчи: 1010 = 5 + 3 + 2. Это позволяет записать нам 1010 в виде 1110 (выполнили разложение по базису). Однако это же число 1010 можно записать в фибоначчиевой системе счисления и по-другому: 1010 = 10010fib = 1*8 + 0*5 + 0*3 + 1*2 + 0*1. Аналогично, число 2510 можно также записать несколькими способами: 2510 = 1000101fib = 110101fib. Число 10010 можно записать как минимум шестью способами: 10010 = 1000010011fib = 1000010100fib = 110010011fib = 110010100fib = 101110011fib = 101110100fib. Алгоритм перевода целых чисел из десятичной системы счисления в ФСС 1. Найдем максимальное число Fиз базиса фибоначчиевой системы, которое не превосходит число А, и зафиксируем его номер k (F= Fk). Искомая запись числа А в фибоначчиевой системе будет содержать k цифр. Сформируем “заготовку” искомого фибоначчиева числа в виде 10...0. (нулей - k-1 штук). 2. Вычислим разность А = А - F,. 3. Если полученное значение А равно 0, переход на п. 7. 4. Найдем максимальное число Fиз базиса фибоначчиевой системы, которое не превосходит число А, и зафиксируем его номер p (F= Fp). 5. В сформированную заготовку на р-е место поставим 1.
4.2. Избыточность ФСС. Операции свертки и развертки в ФСС Фибоначчиева система счисления обладает удивительным свойством — свойством избыточности, оказывается, что многие числа в ФСС могут выглядеть по-разному. Например, десятичное число 40 можно записать в ФСС четырьмя разными способами 4010 = 10001001fib = 10000111fib = 1101001fib = 110011fib Различные фибоначчиевы представления одного и того же числа могут быть получены друг из друга с помощью специальных фибоначчиевых операций свертки (011 => 100) и развертки (100 => 011). Эти операции выполняются над фибоначчиевой записью числа и не меняют значения числа. (По определению, очередное число базиса равно сумме двух предыдущих.) Замечание 1. Операция свертки уменьшает количество единиц в фибоначчиевой записи числа, но может увеличить на единицу количество цифр в записи, если исходная запись начиналась с двух единиц. Например, 110101 = 1000101 . Замечание 2. Операция развертки увеличивает количество единиц в фибоначчиевой записи числа, но может уменьшить на единицу количество цифр в записи, если исходная запись начиналась с комбинации “100”. Например, 1000101 = 110101. Если над записью числа в ФСС выполнить все возможные свертки, то мы придем к специальному фибоначчиевому представлению числа, называемому минимальной формой, в которой нет двух рядом стоящих единиц. Если же в фибоначчиевой записи выполнить все возможные операции развертки, то придем к специальному фибоначчиевому изображению, называемому максимальной, или развернутой, формой, в которой рядом не встречается двух нулей. Любое число А представляется в минимальной или максимальной форме единственным способом. Правило приведения фибоначчиевой записи числа к минимальной форме 1. Просматривая запись числа слева направо, найдем первую комбинацию “11”. 2. Выполним над ней операцию свертки:
3. Последовательно выполним операции свертки для всех комбинаций “11”, двигаясь по записи числа слева направо. 4. Если в получившейся записи есть две рядом стоящие единицы, то переход на п. 1, иначе получившаяся запись будет искомой минимальной формой. Какое самое большое число в ФСС, представленное в минимальной форме, можно записать в k разрядах? Очевидно, что самая старшая цифра должна быть 1. Далее для построения максимального числа цифры 0 и 1 должны чередоваться. Тогда максимальное число, которое можно записать в k разрядах, равно 10101…10 при четном k и 10101…01 при нечетном k.
При записи чисел в фибоначчиевой системе счисления принято использовать минимальную форму записи: в этой форме нет двух подряд идущих единиц. То есть числа 100 в ФСС будут записано однозначным образом. Так как цифрами фибоначчиевой системы счисления являются 0 и 1, то фибоначчиев код содержит только нули и единицы. Но если при передаче фибоначчиева кода, представленного в минимальной форме, появились две подряд идущих единицы, то можно однозначно сказать, что информация пришла с искажением (потерей). “Естественная” избыточность кодов Фибоначчи, которая проявляется в “множественности” представлений одного и того же числа, может быть использована для целей контроля числовых преобразований в цифровых устройствах. Анализ фибоначчиевой арифметики показал, что основными ее операциями являются операции свертка, развертка и основанная на них операция приведения кода Фибоначчи к минимальной форме. Эти математические результаты стали основой для проектов создания компьютерных и измерительных систем на основе фибоначчиевой системы счисления. Как известно, компьютерная программа реализуется с помощью команд процессора, сама программа и обрабатываемые данные хранятся в оперативной памяти. К сожалению, представлена в фибоначчиевой системе счисления;
В качестве таких базовых операций были выбраны:
Первые две операции были рассмотрены нами выше. Операция перемещения является поразрядной двуместной операцией M(A, B). Если ячейка A имеет двоичную цифру 1 в k-м разряде, а ячейка B в этом разряде имеет цифру 0, то в результате операции перемещения цифра 1 из ячейки A перемещается в ячейку B, а цифра 0 из ячейки В перемещается в ячейку A.
Операция поглощения P(A, B) также является поразрядной двуместной операцией и состоит в том, что две двоичные единицы одного и того же разряда ячеек A и B взаимно уничтожаются, то есть заменяются нулями.
Функциональная полнота базовых фибоначчиевых операций Покажем, что любую логическую операцию можно выполнить через базовые фибоначчиевы операции [4]. Для этого достаточно показать, что с помощью этих операций можно реализовать конъюнкцию, дизъюнкцию и отрицание. А так как эта система операций {*, +, } является полной [2], то в итоге мы сможем выразить через базовые операции любые другие. Вопрос читателю. Что нам дает знание того, что некоторая система операций над двоичными последовательностями является полной? Так как работа всего компьютера построена на логических преобразованиях двоичных последовательностей, то для проектирования компьютера достаточно уметь строить ограниченный набор логических элементов, каждый из которых реализует определенную операцию или функцию, входящую в некоторую полную систему. Известно, что современная цифровая техника строится на основе трех логических элементов — конъюнктора, дизъюнктора и инвертора. Но оказывается, что базовые операции {M, P} вместе с константой 1 также образуют полную систему логических функций. 1) Покажем, что через базовые операции {M, P} с использованием константы 1 можно выразить любую логическую операцию булевой логики. Напомним таблицы истинности для основных операций булевой логики — конъюнкции, дизъюнкции и отрицания.
Операции перемещения M(A, B) = (A', B') и поглощения P(A, B) = (A", B") можно рассматривать как логические операции с двумя аргументами и двумя значениями. Составим таблицы истинности для этих операций.
Сравнивая табл., мы видим, что A' содержит результат поразрядной конъюнкции, т.е. A' = A*B, а B' — результат поразрядной дизъюнкции, т.е. B' = A +B. Логическая операция отрицание сводится к выполнению операции поглощения над исходной кодовой комбинацией A и константой 1. В результате операции поглощения (A", B") = P(А, В), где В = 1, мы получаем B" = A и A" = 0. 6. Выполнение операции сложения в ФСС Выполнение операции сложения в позиционных системах счисления происходит по таблицам сложения. Для двоичной системы таблица сложения довольно проста. 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10 Последняя строка в табл. 5 задает правило формирования переноса при двоичном сложении единиц (1 + 1 = 10). |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||