Системы счисления. Литература Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М. Бином. Лаборатория знаний, 2004
 Скачать 215 Kb.
|
|
Построим таблицу сложения для ФСС. Если оба слагаемых имеют 1 в разряде с номером k > 3, то при сложении единица в k-м разряде сохраняется, и возникает перенос двух единиц в соседние младшие разряды: в (k- 1)-й и (k - 2)-й. Это следует из тождества: Fk+ Fk= Fk+ Fk-1 + Fk-2. Для k= 1: 1 + 1 = 10 (выделен 1-й разряд). Для k= 2: 1 + 1 = 101 (выделен 2-й разряд). Таблицу сложения в ФСС можно записать в виде:
Возникающий при выполнении сложения перенос будем накапливать в отдельной ячейке R, которую назовем многоразрядным переносом. Для первого и второго разрядов многоразрядный перенос не формируется, переносимые единицы сразу записываются в формируемую сумму. Таким образом, не возникает ситуация, когда в одном из разрядов перенос состоит более чем из одной единицы. Алгоритм сложения целых чисел в ФСС Перед сложением суммируемые фибоначчиевые числа приводятся к минимальной форме. Поразрядное сложение выполняется справа налево. Будем использовать следующие обозначения: S— промежуточная сумма; R — многоразрядный перенос.
Промежуточная сумма S, приведенная к минимальной форме, и есть результат сложения. Конец алгоритма. Пример. Требуется сложить два числа a = 10101 fibи b = 1001 „в ФСС. В нашем примере числа уже записаны в минимальной форме, две единицы стоят только в первом разряде, поэтому многоразрядный перенос равен 0. В соответствии с табл. 6 получим: 10101 + 1001 S=11110 Результат приведем к минимальной форме, для этого дважды выполним операцию свертки: 11110 => 100110 => 101000. Проверим себя, переведем исходные слагаемые и полученный результат в десятичную систему счисления: 85321 5321 1385321 a = 10101 = 12; b = 1001 = 6, S = 101000= 18. Пример. Сложим десятичные числа A = 2010 и B = 2010 в фибоначчиевой системе счисления. Сначала запишем числа в ФСС в минимальной форме: A = B = 2010 = 101010. Операция сложения будет выполняться в несколько шагов. В этом примере две единицы стоят во втором, четвертом и шестом разрядах, но при сложении на первом шаге перенос будет возникать только для четвертого и шестого разрядов (см. табл. 6). 1) 101010 + 101010 S=101101 R=011110 Получили промежуточную сумму S = 101101 и многоразрядный перенос R = 011110. 2) Приведем Sк минимальной форме: 101101 => 110001 => 1000001. 3) Вычислим S+R 1000001 + 11110 S=1011111 Получили промежуточную сумму S=1011111 1011111 и нулевой многоразрядный перенос. 4) Запишем Sв минимальной форме: 1011111 => 1100111 => 1101001 => 10001001. Проверим себя: 34 21 13 8 5 3 2 1 1 0 0 0 1 0 0 1 = 34 + 5 + 1 = 40. Алгоритм фибоначчиева сложения кажется сложным и утомительным, но после приобретения некоторого опыта эта процедура оказывается даже занятной. 6.1. Реализация операции сложения в ФСС через базовые операции Покажем, что через базовые операции {S, R, M, P} можно реализовать фибоначчиево сложение ячеек А и В. В основе этой реализации лежит идея перебрасывания единиц из k-го разряда ячейки А в k-й разряд ячейки В, если там был 0. При этом на каждом шаге сумма модифицированных ячеек остается прежней. Алгоритм заканчивается, когда ячейка А становится равной 0, в этом случае искомая сумма накоплена в ячейке В. В качестве примера просуммируем два числа: A0 = 10100100 = 5010 и B0 = 1010100 = 3210
Проверим себя: В4 = 101001001 = 55 + 21 + 5 + 1 = 8210. Можно показать, что операции вычитания, умножения и деления также реализуются через базовые операции. Таким образом, через базовые операции {S, R, M, P} можно выразить любую логическую и любую арифметическую операцию. И, следовательно, мы можем проектировать Фибоначчи-процессор на основе базовых микроопераций. Какое преимущество будет иметь такой фибоначчи-процессор в сравнении с классическими компьютерами, основанными на классической двоичной системе счисления? Ответ на этот вопрос состоит в том, что такой процессор обладает возможностью контроля ошибок, которые могут возникнуть в процессоре под влиянием различных внешних и внутренних факторов [5]. К сожалению, создать фибоначчи-компьютер по разным причинам пока так и не удалось: группа А.П. Стахова спроектировала только экспериментальный Ф-процессор, который действительно сам определял, произошел ли сбой при работе процессора. При разработке элементной базы Ф-процессора основным операционным элементом стало устройство приведения кода Фибоначчи к минимальной форме. Это устройство реализовывалось через RS-триггеры и логические элементы И и ИЛИ. Теоретические основы данного направления представляют несомненный интерес и могут стать источником новых идей не только в компьютерной области. Современные математики проявляют большой интерес к “фибоначчиеву” направлению. В 1963 г. группа американских математиков, возглавляемая Вернером Хоггаттом, организовала математическую фибоначчи-ассоциацию, которая выпускает журнал “The Fibonacci Quarterly” и ежегодно с 1984 г. проводит международную конференцию “Fibonacci Numbers and Their Applications”. |