Разработка операционной части арифметического устройства

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Омский государственный технический университет

Кафедра Информатики и вычислительной техники

КУРСОВОЙ ПРОЕКТ

На тему: Разработка операционной части арифметического устройства

по дисциплине «Дискретная математика»

Студент

Артем Турин

Руководитель проекта

Потапов И.В.

Омск 2011

Содержание

Введение

1. Описание алгоритма и посчитанные по ним примеры

2. Схема Алгоритма

3. Структурная схема ОА

4. Листинг программы

Заключение

Список используемой литературы

Введение

Условно вычислительную машину можно разделить на Управляющий Автомат (УА) и Операционный Автомат (ОА).

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

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

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

Далее перейдем к описанию алгоритма.

1. Описание алгоритма

Первый ускоренный метод деления с анализом одного разряда основан на следующих соображениях. Будем полагать, что очередной частичный остаток a_i>0, а нормализованный делитель B>2a_i, т.е. делитель больше остатка, сдвинутого влево на один разряд. Очевидно, что в следующем цикле деления из удвоенного частичного остатка следует вычесть делитель. В результате на сумматоре сформируется число (2a_iB)<0, что приводит к формированию очередной цифры частного, равной нулю. В следующем цикле деления очередной отрицательный частичный остаток удвоится, к нему прибавится делитель B, и на сумматоре сформируется число 2(2a_iB)+B = 4a_iB. Аналогичный остаток может быть сформирован на сумматоре в случае пропуска операции вычитания делителя в (i+1)-м цикле. Действительно, в результате двух сдвигов влево на один разряд остаток a_i будет умножен на 4, а поскольку он положительный, то в (i+2)-м цикле из него следует вычесть делитель. Для случая a_i<0 рассуждения аналогичны.

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

Пример.

[А]_пр = 0,101001;

[В]_пр = 0,110011;

С = А/В.

1. Определение знака частного.

Зн_С = Зн_А Зн_В = 0 0 = 0.

2. Деление мантисс.

Частное Делитель

;

0.

< 0, деление без переполнения

1. ;

2. ;

;

3. ;

;

4. ;

;

5. ;

;

6. ;

;

Таким образом, частное C = 0,110011.

Описанный метод позволяет ускорить выполнение операции деления только в тех циклах, в которых остаток денормализован, а в остальных циклах деление происходит по неускоренному алгоритму. Поэтому в худшем случае при постоянном формировании нормализованного остатка этот метод не дает прироста производительности.

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

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

При денормализации влево сумматор мантисс сдвигается вправо, а к сумматору порядков прибавляется единица. При денормализации вправо сумматор мантисс сдвигается влево и из сумматора порядка вычитается единица.

После устранение денормализации, если она возникла, происходит выполнение операции анализа переполнения сумматора порядков. Признаком такого переполнения сумматора порядков служит сумма по модулю 2 знаковых разрядов регистров порядков, если она равна 0 и сумма по модулю два знакового разряда любого из регистров порядка (так как они равны по первому условию) и знакового разряда сумматора порядков. Если эти условия не выполняются, происходит вывод результата и завершение работы, если выполняются и в знаковых разрядах регистров порядках содержится 1, сумматор мантисс обнуляется и происходит вывод данных, если нет то результатом работы является переполнение сумматора порядков.

Метод преобразования множителя заключается в том, что в некоторых случаях число содержащихся в множителе единиц можно уменьшить, заменив их нулями, что приводит к пропуску такта суммирования, поскольку при умножении на 0 содержимое сумматора не изменяется.

Пусть в множителе три или более идущих друг за другом разрядов a_m, a_m-1, …, a_k равны единице. В соответствии с элементарной двоичной арифметикой такая последовательность может быть представлена как разность двух чисел: . Покажем это на примере множителя B=0,011100:

0,100000

0,000100

0,011100

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

Отдельно стоящие нули или единицы могут увеличить число единиц в преобразованном множителе. Рассмотрим, например, фрагмент множителя, состоящий из нулей и единицы в i-том разряде, и его преобразованный вид:

В этом случае умножение множимого A на преобразованный множитель должно выполняться в соответствии с выражением

Если фрагмент множителя с нулем в i-м разряде и его преобразование имеют вид

то умножение множимого A на преобразованный множитель должно выполняться в соответствии с выражением

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

Таблица 1.1

Разряды множителя	Состояние триггера Тг	Действия
n-1	n
0	0	0	-
0	1	0	СМ + А
1	0	0	-
1	1	0	СМ - А, Тг = 1
0	0	1	СМ + А, Тг = 0
0	1	1	-
1	0	1	СМ - А
1	1	1	-

Следует отметить, что перед началом выполнения умножения триггер должен быть установлен в состояние «0». По окончании умножения триггер также должен установиться в «0», поэтому в некоторых случаях требуется выполнение дополнительного цикла умножения для обработки последней единицы в множителе.

При умножении мантисс следует использовать модифицированный код, поскольку в некоторых случаях может возникать переполнение разрядной сетки.

Определение знака и порядка произведения, а также нормализация выполняются так же, как при неускоренном умножении.

Пример.

Умножим числа с фиксированной запятой.

[А]_пр = 0,11001001;

[В]_пр = 0,11101011;

С = А В.

1. Определение знака произведения.

Зн_С = Зн_А Зн_В = 0 0.

2. Умножение мантисс.

;

; ;

1.

;

;

2. ;

3.

;

4. ;

5.

;

6. ;

7. ;

8. ;

9. + ;

Окр. +

3. Ограничение результата восемью разрядами и присвоение знака.

Окончательно [С]_пр = 0,10111001;

Перейдем непосредственном к схеме алгоритма, описанных операций.

2. Схема Алгоритма

алгоритм программа листинг

Рассмотрим схемы алгоритмов. Ниже будет представления схема алгоритма умножения.

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

Рисунок 1 - СА умножения.



Рисунок 2- Схема Алгоритма деления



Рисунок 3 - Общая схема

3. Структурная схема ОА

Одним из основных элементов структурной схемы ОА является набор сигналов. Условно сигналы делят на 2 группы, то есть управляющие сигналы и оповещающие сигналы.

Под управляющим сигналами понимаются микрооперации надо регистрами и сумматорами и счетчиками, такие как сдвиг, сложение, начало/конец операции.

Оповещающий сигнал это логическое условие, для выбора набора управляющих сигналов. Оповещающих сигналов, как правило, по количеству меньше чем управляющих.

Таблица - Управляющие и Оповещающие сигналы

Управляющий сигнал	Микрооперация	Оповещающие сигналы	Логическое условие
Y1	Smm=0,Tg=0 Rg1m=Ma Rg1p=Pa Rg2m=Mb Rg2p=Pb Сч=N-2	X1	Rg1M=0
Y2	Smp= Smp+Rg2p	X2	Rg2M=0
Y3	Smm=Smm+Rg1m,Тг=0	X3	Cч=0
Y4	Smm,Rg2m сдвиг вправо Сч=Сч-1	X4	Тг=0
Y5	Smm=Smm-Rg1m,Тг=1	X5	Rg2m[n-1]=0
Y6	Smm=Smm cдвиг влево	X6	Rg2m[n]=0
Y7	SmP=Smp-1(k)	X7	SMM(2) SMM(3)=1
Y8	Smp=Smp+1(k)	X8	SMM(1) SMM(2)=1
Y9	Smm=Smm cдвиг вправо	X9	RG1P(1) RG2P(1)=1
Y10	Smm=0	X10	SMP(1) RG1P(1)=1
Y11	Smp=+?	X11	SMM(1)=1
Y12	Вывод SMM,SMP	X12	SMM(1)=1 SMM(2)=1
Y13	Smm=Smm+Rg1m	X13	SMM(1)=0 SMM(2)=0
Y14	Smm=Smm-Rg1m
Y15	Smm= Rg1m. Rg1m=0
Y16	Smm=Smm-Rg2m
Y17	Smm=Smm Rg1m= Rg1m cдвиг влево
Y18	Rg1m(N)=1
Y19	Rg1m(N)=0
Y20	Smm= Rg1m
Y21	Smp=Smp+Rg2p

Далее приведена схема ОА.

Рисунок 4 - Схема ОА.

4. Листинг программы

Ниже приведен листинг программы. Программа моделирующая устройство на ПК написана на языке С++. Это дает некоторое преимущественно в побитовой обработке данных введенных пользователем.

Рисунок 5 - Работа программы в режиме умножения



Рисунок 6 - Работа программы в режиме деления

program Zachot;

{$APPTYPE CONSOLE}

{%File 'treble.in'}

{%File 'treble.out'}

uses

SysUtils;

var

okrp,okr,smm,smp,rg1m,rg2m,rg1p,rg2p:string;

sch,i,a,s:integer;

p,straz,j,f,x:byte;

procedure vyvod;

begin

if x=1 then

writeln(smm,' ',smp)

else

writeln(rg2m,' ',smp);

end;

{function max(s1,s2:string):string;

var

h:string;

t,y,c:integer;

begin

h:=s1;

delete(h,1,2);

val(h,t,c);

h:=s2;

delete(h,1,2);

val(h,y,c);

if t>y then

max:=s1

else

max:=s2;

end;}

function convob(s:string;h:integer):string;

var

n,o:integer;

begin

o:=h;

n:=0;

if s=smp then

n:=1;

repeat

if s[h]='1' then

s[h]:='0'

else

s[h]:='1';

dec(h);

until h=0;

if n<>1 then

begin

s[1]:='1';

if (o=a+1) or (o=a) then

s[2]:='1';

end;

convob:=s;

end;

procedure provn0(s:string);

var

bufs:string;

bufi:integer;

begin

bufs:=s;

delete(bufs,1,2);

val(bufs,bufi,i);

if bufi=0 then

begin

if ((x=0) and (s=rg1m)) then

begin

smm:='infinity';

smp:='';

end;

vyvod;

f:=1;

end;

end;

function sum(s1,s2:string;h:integer):string;

var

bufs:string;

i,k,d:integer;

begin

d:=0;

k:=0;

for i:=h+1 downto 1 do

begin

if (s1[i]='0') and (s2[i]='0') then

d:=d+0;

if ((s1[i]='0') and (s2[i]='1')) or ((s1[i]='1') and (s2[i]='0')) then

d:=d+1;

if (s1[i]='1') and (s2[i]='1') then

begin

d:=d+0;

k:=1;

end;

k:=(d div 2)+k;

d:=(d mod 2);

str(d,bufs);

s1[i]:=bufs[1];

d:=k;

k:=0;

end;

sum:=s1;

end;

function convd(s1:string;u:integer):string;

var

r:string;

begin

s1:=convob(s1,u);

if u=(a+1) then

r:=sum(s1,okr,u);

if u=s then

r:=sum(s1,okrp,u);

if u=a then

r:=sum(s1,okr,u);

convd:=r;

end;

procedure provsmp;

var

l:integer;

begin

if (((rg1p[1]='1') and (rg2p[1]='1')) or ((rg1p[1]='0') and (rg2p[1]='0'))) then

if ((smp[1]='1') and (rg1p[1]='1')) then

begin//на "-0"

if sum(smp,convd(okrp,s),s-1)[1]='0' then

for l:=1 to a+1 do

smm[l]:='0';

end

else

if (((smp[1]='1') and (rg1p[1]='0')) or ((smp[1]='0') and (rg1p[1]='1'))) then

begin

if rg1p[1]<>'0' then

for l:=1 to a+1 do

smm[l]:='0'

else

begin

smm:='infinity';

smp:='';

end;

end;

end;

begin

assign(input,'treble.in');

assign(output,'treble.out');

reset(input);

rewrite(output);

readln(x);

readln(rg1m);

readln(rg1p);

readln(rg2m);

readln(rg2p);

smm:='';

smp:='';

okr:='';

okrp:='';

j:=0;

f:=0;

p:=0;

a:=length(rg1m);{число n}

s:=length(rg1p);{число k}

for i:=1 to a+1 do

begin

smm:=smm+'0';

okr:=okr+'0';

end;

if x=0 then

begin

delete(smm,a+1,1);

delete(okr,a+1,1);

end;

okr[length(okr)]:='1';

for i:=1 to s do

begin

okrp:=okrp+'0';

smp:=smp+'0';

end;

okrp[s]:='1';

if x=1 then

begin

if rg1m[1]='1' then//при выборе операции умножения

rg1m:=convob(rg1m,a);

if rg2m[1]='1' then

rg2m:=convob(rg2m,a);

sch:=a-2;{счётчик}

provn0(rg1m);

if f<>1 then

provn0(rg2m);

if rg2m[1]='1' then

j:=1;

if f<>1 then

begin

rg1m:=rg1m+'0';

smm:=rg1m;

repeat//умножение

if rg2m[a]='1' then

smm:=sum(smm,rg1m,a);//суммирование

delete(smm,a+1,1);//сдвиг smm

if ((smm[1]='0') and (smm[2]='0')) or ((smm[1]='0') and (smm[2]='1')) then

smm:='0'+smm;

if ((smm[1]='1') and (smm[2]='1')) or ((smm[1]='1') and (smm[2]='0')) then

smm:='1'+smm;

delete(rg2m,a,1);//сдвиг rg2m

if j=1 then

rg2m:='1'+rg2m

else

rg2m:='0'+rg2m;

dec(sch);

until (sch=0);

rg1m:=convd(rg1m,a);

smm:=sum(smm,rg1m,a);

smm:=sum(smm,okr,a);

if rg1p[1]='0' then

smp:=rg1p

else

smp:=convd(rg1p,s);

if rg2p[1]='0' then

smp:=sum(smp,rg2p,s-1)

else

smp:=sum(smp,convd(rg2p,s),s-1);

if (((smm[2]='0') and (smm[3]='0')) or ((smm[2]='1') and (smm[3]='1'))) then//норм-я мантиссы

begin

delete(smm,1,1);//сдвиг smm <--<3--x

smm:=smm+'0';

end;

provsmp;

vyvod;

end;

end

else

begin//деление

if (((rg1m[1]='0') and (rg2m[1]='1')) or ((rg2m[1]='1') and (rg1m[1]='0'))) then//знак частного

j:=1;

smm:=rg1m;

if smm[1]='1' then

begin

smm[1]:='0';

smm[2]:='0';

end;

rg1m:=rg2m;

if rg2m[1]='1' then

begin

rg1m[1]:='0';

rg1m[2]:='0';

end;

for i:=1 to a do

rg2m[i]:='0';

provn0(smm);

if f<>1 then

provn0(rg1m);

if f<>1 then

begin

smm:=sum(smm,convd(rg1m,a),a-1);//0 цикл

if smm[1]='0' then

rg2m[a]:='1';

sch:=a-2;//счётчик

straz:=0;

if rg1m[3]=rg1m[4] then //0010 or 0011

straz:=1;

repeat

delete(smm,1,1);//сдвиг smm

smm:=smm+'0';

delete(rg2m,1,1);//сдвиг rg2m

rg2m:=rg2m+'0';

if (((smm[2]='0') and (smm[3]='1') and (smm[4]='1')) or ((smm[2]='1') and (smm[3]='0') and (smm[4]='0'))) then

p:=1;

if ((straz=0) and ((smm[2]='0') and (smm[3]='1') and (smm[4]='0'))) then

p:=1;

if p=1 then

begin

if smm[1]='1' then

smm:=sum(smm,rg1m,a-1)

else

smm:=sum(smm,convd(rg1m,a),a-1);

if smm[1]='0' then

rg2m[a]:='1'

else

rg2m[a]:='0';

end

else

rg2m[a]:=smm[1];

p:=0;

dec(sch);

until sch=0;

smp:=sum(rg1p,convd(rg2p,s),s);

provsmp;

if j=1 then

begin

rg2m[1]:='1';

rg2m[2]:='1';

end;

vyvod;

end;

end;

close(input);

close(output);

end.

Листинг 2 - Моделирование операции деления на ПК.

Заключение

В начале работы были поставлены задачи, направленные на разработку схемы ОА и алгоритма работы ОА, а также разработке программы, которая могла бы задействовать все те методы, которые используются в алгоритме работы ОА. Задачи были выполнены, алгоритм протестирован на ПК. Также можно отметить, что была проведена оптимизация алгоритма, путем сокращения количества сигналов. Как можно заметить в схеме алгоритма за некоторые блоки, к примеру, сложение порядков или прибавление к сумматору, отвечает один и тоже же управляющий сигнал. Сократить количество оповещающих сигналов представилось возможным, только в одном случае.

Список использованной литературы

1. Операции двоичной и десятичной арифметики в ЭВМ: Метод. указания / Сост. Пальянов И.А.; Омск: ОмПИ, 1990. - 36 с.

2. Моделирование на ЭВМ алгоритмов выполнения арифметических операций и синтез управляющих автоматов: Метод. указания / Сост. Пальянов И.А., Шафеева О.П.; Омск: ОмПИ, 1988. - 36 с.

Размещено на Allbest.ru