Московский Авиационный Институт
(национальный исследовательский университет)
Кафедра 304
Курсовая работа
по курсу
«Организация ЭВМ»
Принял: Выполнил:
доцент, к. т.н. студент гр. 13-401
Роговцев К. Г.
Оценка:______________ Подпись:_____________
Подпись:_____________
«____» __________________ 2012г.
Москва 2012
Содержание
Теоретическое обоснование метода................................................................................ 4
Пример выполнения умножения..................................................................................... 5
Функциональная схема АЛУ........................................................................................... 6
Микропрограмма............................................................................................................... 7
Структурная схема алгоритма микропрограммы.......................................................... 8
Графы переходов............................................................................................................... 9
Вычисление времени выполнения микропрограммы.................................................. 9
Список используемой литературы.................................................................................. 10
Теоретическое обоснование метода
По заданию необходимо разработать устройство для умножения в прямом коде двух чисел разрядностью 8 бит: 7 разрядов – значащие, один разряд (старший) – знаковый. Метод умножения – начиная с младших разрядов множителя со сдвигом суммы частичных произведений вправо при неподвижном множимом.
Представим операцию умножения как Z = X * Y.
X – множимое;
Y – множитель;
Z – произведение.
Умножение
Умножение чисел в прямом коде по методу «начиная с младших разрядов множителя со сдвигом суммы частичных произведений вправо при неподвижном множимом» выполняется следующим образом:
1) Производится определение знака результата путем сложения по модулю 2 знаковых разрядов множимого и множителя;
2) Берутся модули от сомножителей;
3) Исходное значение суммы частичных произведений принимается равным 0;
4) Анализируются значение младшего разряда множителя (очередное значение).
Если этот разряд равен 1, то к сумме частичных произведений прибавляется текущее значение множимого. Если разряд равен 0, то прибавления не происходит (или прибавляется 0);
5) Производится сдвиг суммы частичных произведений и множителя вправо на 1 разряд;
6) Пункты 3 и 4 повторяются для всех n разрядов множителя;
7) Произведению присваивается знак плюс, если знаки сомножителей одинаковы, в противном случае присваивается знак минус.
Пример
Рассмотрим операцию умножения на примере четырехразрядных чисел:
Х = 0.101(2) - множимое, Y = 1.101(2) - множитель, Z – произведение, Z’ – сумма частичных произведений, Zn – знак произведения.
Определяем знак произведения путём сложения знаковых разрядов множимого 0.101 и множителя 1.101 по модулю 2: Zn = 0Å1 = 1, следовательно, результат умножения будет с отрицательным знаком.
Берём модули от сомножителей: X = 0101, Y = 0101
Цикл | Значения | Пояснение |
1 | X = 0101 Y = 0101 Z = | Начальное значение |
Y’ = 0101 Z’ = Z’’= Y’’= 0010 | Анализируем младший разряд множителя. Прибавляем к Z значение X, т. к. младший разряд Y равен 1. Сдвиг вправо на 1 разряд суммы частичных произведений. Сдвиг вправо на 1 разряд множителя. | |
2 | Y = 0010 Z = Z’ = Z’ = Y’ = 0001 | Анализируем младший разряд множителя. Прибавляем к Z значение 0, т. к. младший разряд Y равен 0. Сдвиг вправо на 1 разряд суммы частичных произведений. Сдвиг вправо на 1 разряд множителя. |
3 | Y = 0001 Z = Z’ = Z’’= Y’ = 0000 | Анализируем младший разряд множителя. Прибавляем к Z значение X, т. к. младший разряд Y равен 1. Сдвиг вправо на 1 разряд суммы частичных произведений. Сдвиг вправо на 1 разряд множителя. |
4 | Y = 0000 Z = Z’ = Z’’= Y’ = 0000 | Анализируем младший разряд множителя. Прибавляем к Z значение 0, т. к. младший разряд Y равен 0. Сдвиг вправо на 1 разряд суммы частичных произведений. Сдвиг вправо на 1 разряд множителя. |
Z = |
Произведению присваивается ранее определённый знак: Z = 1.0011001(2) = -25(10).
Функциональная схема АЛУ
Используемые обозначения:
Швх – шина входных данных;
Швых – шина выходных данных;
SM – регистр суммы комбинационного сумматора;
ТЗ – триггер знака;
КС – комбинационный сумматор;
СЧ – счетчик цикла.
Операнды в КС записываются в прямом коде. Множимое хранится в регистре R1, множитель – в регистре R2. Результат операции умножения будет формироваться в регистрах RC и R2: в RC - старшая часть, в R2 - младшая.
Анализ множителя начинается с младшего разряда, т. е. на каждом шаге анализируется нулевой разряд регистра R2 и после анализа содержимое этого регистра сдвигается вправо на один разряд. Если нулевой разряд регистра R2 равен 1, то к сумме частичных произведений прибавляется множимое, а если в нулевом разряде множителя стоит 0, то к сумме частичных произведений прибавляется 0.
Знак произведения формируется в результате анализа знаков сомножителей. Если сомножители имеют одинаковые знаки, то произведение получается положительным, если знаки различны - произведение будет отрицательным. После определения знака результата знаковые разряды сомножителей обнуляются и умножение производится над положительными числами.
При выполнении операции умножения используется не модифицированный сдвиг, т. е. при сдвиге промежуточного произведения старший разряд заполняется нулем.
Число циклов выполнения операции умножения равно n. Это объясняется тем, что до этапа коррекции (после выполнения (n-1) циклов) требуется сдвиг на 1 разряд вправо в связи с тем, что знаковый разряд обнуляется в начале выполнения операции. Этого можно достичь, занося в счетчик циклов n, а не (n-1).
Микропрограмма
|
R1:= Швх; Сч:= n;
|
RА:=RВ:=R3:=SM:=RС:= 0;
|
ТЗ:= R1[n-1]ÅR2[n-1];
|
|
Если R2[0]:= 0, то идти к 7;
|
|
RA:= 1;
|
SM:= RA+RB; RC:= П(1) SM;
|
R3[n-1]:= SM[0]
|
RB:= RC;
|
R2:= R3;
|
Если Сч < > 0, то идти к 5;
|
Швых:= RC;
|
Швых:= R2;
|
Структурная схема алгоритма микропрограммы
Графы переходов
Вычисление времени выполнения микропрограммы
Тумн. ср. = τ+τ+τ+n(τ+p1τ +τ+τ+τ+τ+τ+τ)+ p2τ+τ+τ = 3τ+n(7τ+p1τ)+ p2τ+2τ = 5τ+n(7τ+p1τ)+ p2τ
Учитывая, что n=8 и значения появляются со следующей вероятностью: p1=0,5, p2= 0,125, получаем:
Тумн. ср. = 5τ+7,5τn+0,125τ = 5,125τ+7,5τn = τ(5,125+7,5n) = 65,125τ
Список используемой литературы
1. , Каневский вычислительные машины и системы. – М.: Энергия
2. Каган вычислительные машины и системы. – М.: Энергоатомиздат.
3. Савельев теория цифровых автоматов. – М.: Высшая школа.
