Арифметика вычислительных машин

1. Выполнение операции сложения чисел с фиксированной точкой

Сложение чисел, представленных в прямом коде дает неправильный результат (числа с разными знаками). Это множество чисел - незамкнутое множество относительно операции сложения: z=x+y.

Введем дополнительное кодирование.

Если x 0 - дополнительный код =прямому коду,

если x < 0, то =2^n-1 - |а| - значимая часть кода, а

=2ⁿ - |а| - это дополнительный код со знаком,

где n- число разрядов, включая знаковый слева,

если x>0,то знаковый разряд =0,

если x<0, то знаковый разряд =1.

Примечание: знаковую часть положительного числа для дополнительного кодирования можно продолжить влево на любое число разрядов, а для прямого кодирования нельзя.

Пример: «-5»= 2⁴-5 = 11 =1011

следовательно 1011- это дополнительный код числа «-5», где «1» в старшем разряде - это знаковый разряд, а «011»- это значимая часть кода.

Дополнительный код для отрицательного числа равен прямому коду для положительного числа, например,

код числа «-1» =коду числа 7

код числа «-2» =коду числа 6

код числа «-3» =коду числа 5

код числа «-4» =коду числа 4 и т.д.

x	прямой код	дополнительный код
3	011	011
2	010	010
1	001	001
0	000	000
-0	100	000
-1	101	111
-2	110	110
-3	111	101

Обратное кодирование

Если а0, то обратный код = прямому,

а<0, то обратный код числа x это а’=2^n-1-1-|a’|

например для n=4 дополнительный код числа «-5»=2³-1-5=2=1010.

Связь обратного и дополнительного кодов: а’+ =1.

Сложение чисел представленных в дополнительном коде

= + , рассмотрим 4 случая:

1. x.0 и y0

Обычное сложение. Правило будет работать, если не будет переполнения, т.е., если |z|<2 ⁿ.

Пример: 5+7, n=5

00101

00111

01100

1. x.>0 и y<0

= + =|x|+2ⁿ-|y|= а) |x||y|, 2ⁿ+(|x|+|y|)

б) |x|>|y|, 2ⁿ-(|y|-|x|)

Примеры: x=7 0111

y=-5 1011

0010 - результат в прямом коде

(есть перенос в знаковый разряд)

x=-7 1001

y=5 0101

1110 -результат в дополнительном коде

(переноса нет)

1. x.<0 и y>0 (см. случай 2)

2. x.<0 и y<0

= + =2ⁿ-|x|+2ⁿ -|y|=2ⁿ+2ⁿ -(|x|+|y|)

z2ⁿ -переполнения нет, если z>2ⁿ, то будет переполнение разрядной сетки.

Пример: x=-5 n=4 1011

y=-1 1111

1010 - «-6» в дополнительном коде

x=-5 1011

y=-4 1100

0111 - результат неверный, переполнение

Переполнение. Оно существует когда результат z>2ⁿ, и не существует когда z2ⁿ. Если было переполнение, то был перенос в знаковый разряд, а из знакового не было, либо наоборот- есть перенос из знаковой части, а в знаковую часть нет переноса. Если одновременно отсутствует или присутствуют переносы в знаковую и из знаковой части , то переполнения нет.

Способы определения переполнения.

1. фиксировать переносы в знаковую и из знаковой части. Для этого вводится 2 триггера: Т1 - фиксирует перенос в знаковый разряд, Т2 -фиксирует перенос из знаковой части.

Т1+Т2=Тпер (Триггер переполнения).

1. для x и y отводится под знаковый разряд два разряда. Если совпадают значения знаковых разрядов, то переполнения нет, а если различны, то переполнение есть.

Сложение чисел представленных в обратном коде

z’=x’+y’ рассмотрим 4 случая:

1. x>0, y>0, простое сложение

2. x>0, y<0,

z’=|x|+2ⁿ-|y|-1= a) 2ⁿ+(|x|-|y|)-1, если |x|>|y

б) 2ⁿ-(|y|-|x|)-1, если |x|<|y|

в б) результат в обратном коде,

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

Пример: x=5 0101

y=-2 1101

0010

1

0011 - «3» в прямом коде

1. x0,см. случай 2

2. x<0, y<0,

z’=x’+y’=2ⁿ-|x|-1+2ⁿ-|y|-1=2ⁿ+[2ⁿ-(|x|+|y|)-1]-1 , результат в дополнительном коде , результат также корректируется с помощью циклического переноса.

Пример: x=-5 1010

y= -1 1110

1000

1

1001 - «-6» в обратном коде.

Вычитание чисел в дополнительном и обратном кодах

Операция вычитания сводится к операции сложения за счет того, что вычитаемое число записывается либо в дополнительном, либо обратном кодах.

= - = + (- ),

z’=x’-y’=x’+(-y’).

Микропрограмма и оборудование АЛУ для выполнения операции сложения и вычитания чисел с фиксированной точкой

В состав АЛУ входят n-разрядный параллельный комбинационный сумматор-(КС), регистр сумматора RC, входные регистры сумматора RА и RВ, входной регистр АЛУ- R1. Длина всех регистров =длине операндов=n.

Швх

RA RB

R1

+1

RC

Швых

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

Из оперативной памяти по входной информационной шине Швх в АЛУ поступают операнды: положительные числа в прямом, а отрицательные в дополнительном кодах. Операнды помещаются в регистр А (RA)-первое слагаемое, и регистр B (RВ)- второе слагаемое. Регистр R1 связан с RВ.

В случае операции сложения второй операнд переписывается в регистр RA без изменения. Если выполняется операция вычитания, то операнд переписывается в RA в обратном коде. Далее, в зависимости от кода операции происходит суммирование операндов RA+RB, либо суммирование с добавлением 1 ( в случае вычитания). Результат операции записывается в регистр суммы РС, он выдается из АЛУ в оперативную память по выходной шине Швых..

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

Результат операции Признак результата

0 0 0

<0 0 1

>0 1 0

переполнение 1 1

Операция алгебраического вычитания может быть сведена к изменению знака вычитаемого Y и операции алгебраического сложения.

Z=X-Y=X+(-Y)

В этом случае принятый в регистр RB код числа предается инверсно в регистр R1 и при сложении осуществляется подсуммирование 1 в младший разряд сумматора.

Передача информации в регистрах АЛУ производится отдельными микрооперациями:

RA:=Швх (прием 1-ого операнда)

RB:=Швх (прием 2-ого операнда)

если сложение, то RB:=R1 иначе

вычитание RB:= ;

если сложение, то RC:=RА+RВ иначе

вычитание RC:=RА+RВ +1;

если ПР=11,то переполнение, иначе

Швых:=RC (выдача результата);

конец;

Рассмотрим работу программы на примере:

1-ое слагаемое 12₁₀=01100₂

2-ое слагаемое -5₁₀=11011₂ ( т.к. число отрицательное, то в допол. коде)

RA:=01100

RB:=11011

если сложение, то RB:=R1, т.е. RB:=11011, иначе

RB:= , т.е. RB:=00100 (обрат.код числа-5);

если сложение, то RC:=RA+RВ, т.е. 11011

01100 00111₂=7₁₀ , иначе

RC:=RА+RВ+1, т.е. 00100

01100

10000

1
10001₂=17₁₀

Результат при сложении: 12+(-5)=7₁₀=00111₂

Результат при вычитании: 12-(-5)=12+5=17₁₀=10001

1. Выполнение операции умножения над числами с фиксированной точкой

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

Выполнение операции умножения в АЛУ сводится к последовательности операций сложения и сдвига. Примем разрядность операндов N, тогда разрядность произведения будет 2N. Если при выполнении операции умножения сдвигать множимое, то аппаратные затраты составят:

• - для множимого 2N разрядов;

• - для множителя N разрядов;

• - для произведения 2N разрядов.

Существует четыре способа умножения:

1. Умножение чисел начиная с младших разрядов множителя при сдвиге множимого влево и неподвижной сумме частичных результатов.

Если младший разряд множителя=1, то к сумме частичных произведений прибавляется множимое; если младший разряд множителя =0, то прибавление не делается. Делается сдвиг множимого на каждом шаге на 1 разряд влево, а сумма частичных произведений (промежуточный результат) остается неподвижной. Число сдвигов =N

П

+

ример: x=6 0110

y=5 0101

+

0000

0110

+

+

+

0110

0000

00110

0110

011110

0000

0011110 -«30»

1. Умножение чисел начиная с младших разрядов множителя со сдвигом вправо суммы частичных произведений и неподвижном множимом.

Пример: x=6 0110

y=5 0101

0000

0110

0110 

00110

0000

00110 

000110

0110

011110 

0011110

0000

0011110 

00011110 -«30»

1. Умножение чисел начиная со старших разрядов множителя при сдвиге суммы частичных произведений влево и неподвижном множимом.

4) Умножение чисел начиная со старших разрядов множителя при сдвиге множимого вправо и неподвижной сумме частичных произведений.

Из указанных способов наиболее распространенным является второй способ (меньше оборудования тратится).

Алгоритм умножения целых положительных чисел (чисел в прямом коде):

1. определение знака результата sign(z)= sign(x) sign(y);

2. sign(x)=sign(y)=0;

3. умножение;

4. формирование результата с учетом знака.

Структурная схема АЛУ для выполнения умножения по 2 способу.

С=АВ, А,В - N разрядов

С - 2N разрядов

Рг1- множимое,

РА- либо множимое, либо 0,

Рг2 - множитель,

Рг2, Рг3 -для сдвига множителя,

СМ - сумма частичных произведений,

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

РС - сдинутая на 1 разряд вправо сумма частичных произведений.

Операнды в АЛУ записываются в прямом коде. Множимое хранится в регистре Рг1, множитель в регистре Рг2. Для осуществления сдвига множителя вправо используется Рг2 и Рг3. Результат операции умножения будет формироваться в регистрах РС и Рг2, в РС- старшая часть, в Рг2 -младшая. Анализ множителя начинается с младшего разряда, т.е. на каждом шаге анализируется нулевой разряд регистра Рг2и после анализа содержимое этого регистра сдвигается вправо на один разряд. Если нулевой разряд регистра Рг2=1, то к промежуточному результату прибавляется множимое, а если в нулевом разряде множителя стоит ноля, то прибавления множимого не происходит. Знак произведения формируется в результате анализа знаков сомножителей. Если сомножители имеют одинаковые знаки, то произведение получается положительным. Если знаки различны - произведение будет отрицательным. После определения знака результат знаковые разряды сомножителей обнуляются и умножение производится над положительными числами. При выполнении операции умножения используется не модифицированный сдвиг, т.е. при сдвиге промежуточного произведения старший разряд заполняется нулем.

Необходимо также иметь счетчик циклов Сч.Ц, сначала устанавливается «n», далее работает на вычитание. Если Сч.Ц=0, то прекращается умножение.

Микропрограмма умножения

Р1:=Швх; (множимое)

Р2:=Швх; РВ:=0; (множитель)

СчЦ:=n;

ТЗ:=Р1[0]+P2[0];

P1[0]:=0;

P2[0]:=0;

┌──────────────────────────────┐

│ "1" ┌─────┴──────┐ "0"

│ ┌─────────┤ Р2[n-1] ├─────────┐

│ ┌─────┴─────┐ └────────────┘ ┌─────┴─────┐

│ │ РA:=Р1 │ │ РA:=0 │

│ └─────┬─────┘ └─────┬─────┘

│ └───────────────┬────────────────┘

│ ┌─────────────┴──────────────┐

│ │ СM:=РA+РB │

│ │ РC:=П(1)СM │

│ │ Р3:=П(1)Р2 │

│ │ Р3[0]:=СM[n-1] │

│ └─────────────┬──────────────┘

│ ┌─────┴──────┐

│ │ РB:=РC │

│ └─────┬──────┘

│ ┌─────────────┴──────────────┐

│ │ Р2:=Р3 │

│ │ СчЦ:=СчЦ-1 │

│ └─────────────┬──────────────┘

│ нет ┌───┴───┐ да

└──────────────────────────┤ СчЦ=0?├───────────────┐

└───────┘ │

РA:=0

РС:=РA+РB

PC[1-(n-1)]:=РA+РB

PC[0]=TЗ

Швых:=РС (старшая часть рез-та)

РA:=0

PB:=P2

PC:=PA+PB

Швых:=РС (младшая часть рез-та)

Умножение целых чисел, представленных в дополнительном коде

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

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

= 

1. x0, y0

2. x0, y<0

=  =|x|(2 ⁿ-|y|)=2 ⁿ|x|-|x||y| - неправильный результат, обозначим его как а), правильный результат должен быть =2 ²ⁿ-|x||y|, обозначим его как в), поэтому необходимо скорректировать результат:

т.е. надо из в) вычесть а), тогда а) - в) =2 ²ⁿ-2 ⁿ |x|=2 ⁿ  (2 ⁿ - |x|) = с), т.е.

это мы получили дополнительный код множимого - x, сдвинутый на n-разрядов влево. Чтобы получить правильный результат надо к а)+с).

Пример: x=7=0111 0111

y=-3=1101 1101

z=-21 0111

00111

000111

0111

100011

0100011

0111

1011011

01011011

1001 (дополнит.код 7)

11101011

10010101

1. x0

=  =(2 ⁿ - |x|) |y|= 2 ⁿ |y|  |x||y|+(2 ²ⁿ – 2 ⁿ |y|), а должно быть

=2 ²ⁿ - |x||y|

2 ⁿ (2 ⁿ- |y|)- дополнит. код множителя,

2 ²ⁿ –2 ⁿ |y| -коррекция.

4) x<0, y<0

=  =(2 ⁿ - |x|)  (2 ⁿ - |y|)=2 ²ⁿ – 2 ⁿ |y| - 2ⁿ |x| + |x||y| = а)- неправильный результат, должно быть = |x||y|.

|x|- дополнительный код множимого сдвинутый на разряд влево т.е.

|x|=2 ⁿ (2 ⁿ - |x|),

|y|- дополнительный код множителя

Правильный результат будет, если к а) прибавить дополнит. код множимого и множителя сдвинутых на n разрядов влево.

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

Для 1) и 3) случая коррекция не нужна , а для 2)и 4) нужно одно сложение для коррекции.

Пример: x=-5=1011 а) 1011 в) 1011

y=-7=1001 1001 1001

1011 1011

01011 11011

001011 111011

0001011 1111011

1011 1011

1100011 1010011

01100011 11010011

0101 код +5 0101

10110011 00100011

0111 код+7

00100011 -прямой код 35

а) без модифицированного сдвига

в) с модифицированным сдвигом- сохранение знакового разряда.

Правило:

1. Умножение производится обычным образом.

2. Если множитель отрицательный (y<0), то необходимо прибавить дополнит. код множимого -x.

3. Если множимое отрицательное (x<0), то необходимо прибавить дополнит. код множителя -y.

4. Если множимое и множитель отрицательны (x<0, y<0), то необходимо прибавить дополнит. код множимого и дополнительный код множителя.

Микропрограмма и схема АЛУ для выполнения операции умножения в дополнительном коде

РА -множимое,

Рг2- множитель, младшая часть,

РВ -старшая часть множимого.

Используется одна коррекция; модифицированный сдвиг.

1. Множитель был бы утерян по окончании операции; и необходимо было бы иметь дополнит. регистр для его хранения.

2. отличие от простого умножения ( микропрограмму см. выше):

а) вместо РС:= П(1) (РА+РВ) надо написать

РС[0]:=0, PC[1-(n-1)]:=П(1) (РА+РВ),

если сумма СМ[0]:=0,то РС[0]:=0

СМ[0]:=1,то РС[0]:=1,

вместо РС[0]:=0 , будет РС[0]:=СМ[0];

в) коррекция - к старшей части (РВ) прибавляется дополнительный код множителя - x , если y <0.

1. после выхода из цикла (СчЦ=0?), надо проанализировать знак множителя, если он =0, то выдача результата, если он=1, то предварительно корректируем результат.

Ускоренное выполнение операции умножения

Существует два основных подхода:

1. аппаратные методы ускоренного умножения -АМ;

2. логические методы умножения- ЛМ.

АМ и ЛМ требуют дополнительного оборудования. При использовании ЛМ дополнительное оборудование не зависит от длины-n сомножителя, а при АМ - зависит.

Логические методы - метод Лемана.

На каждом шаге умножения необходимо было осуществлять операцию «+» множимого или «0» и сдвиг вправо, т.е. необходимо потратить время на сложение и сдвиг t₁+t₂ - за один цикл АЛУ.

Метод Лемана позволяет уменьшить число необходимых сложений: надо наблюдать за разрядом множителя, если он=0, то пропустить t₁( время сложения) , а только сдвинуть, если он=1, то и сложить и сдвинуть.

Можно считать, что появление «0» или «1» в множителе равновероятно, поэтому число сложений равно n/2.

Идея метода Лемана:

а)в множителе можно всегда выделить единичные и нулевые k-наборы, которые могут чередоваться (0110001110),

• при переходе от 0 к 1 -вычесть множимое, ,т.е. прибавить дополнительный код множимого,

• при переходе от 1 к 0 - сложить с множимым;

в) сделать k-раз сложений.

Когда единицы и нули чередуются следующим образом - 01010101 -то метод Лемана не работает.

А нализируется не 1 разряд множителя, а группы. Введем нелогические переменные:

0, не надо выполнять операцию «+» и «-» на i шаге умножения

d_i=

1, надо выполнять операцию «+» и «-» на i шаге умножения

0, надо выполнять операцию «+», если d_i =1

S_i=

1, надо выполнять операцию «-», если d_i =1

Пусть b_j – j разряд множителя.

…b₃,b₂,b₁ ; b₁ – младший разряд множителя.

d_i=(b_i b_i-1) d₀=0; b₀=0;

S_i= b_i+1•d_i

Пример: 1 1 0 0 1 1 1 = 103

b₆ b₅ b₄ b₃ b₂ b₁ b₀

d₁=(b₁ b₀)  = (1 0)  =1 - сдвиг 1

S₁=b₂d₁= 1 1=1

d₂=(b₂ b₁)  = (1 1) 0 =0 сдвиг 2

d₃=(b₃ b₂)  = (1 1) 1 =0 сдвиг 3

d₄=(b₄ b₃)  = (0 1)  =1 сдвиг 4

S₄= b₅d₄= 01=0

d₅=(b ₅ b₄)  = (0 0)  =0 сдвиг 5

d₆=(b₆ b₅)  = (1 0) 0 =1 сдвиг 6

S₆=11=1 d₇=(b₇ b₆)  = (1 1) 0 =0 сдвиг 7

Микропрограмма и АЛУ при анализе групп.

Микропрограмма и АЛУ баз. на приведённом выше, при описании умножения по схеме.

Р1 м-е Р2

п и

Р А РВ Р3

БУУ

ТККККККК

Аппаратные методы ускорения операции умножения.

Матричная схема умножения

Мн-е

Деление.

Рассмотрим деление 2 способами:

• с восстановлением остатка

• без восстановления

Разрядная сетка для целых чисел ограниченна: z = xy.

1. деление обр. операция для умножения;

z, y – выделяется по n разрядов, а (x) – 2n.

Можно делить (x) на y в том случае, когда z < 2^n-1 , если 1 знаковый.

Правило переполнения для частного.

z = xy, пусть x, y  0, целые представленные в прямом коде.

z < 2^n-1 ; xy < 2^n-1; x < y2^n-1; x - y2^n-1 < 0 правило возможности выполнения операции.

Д о деления осуществляется пробное вычитание, если величина оказалась  0, то переполнение, если < 0 – можно делить.

x

2n

y2^n-1

Пример: 30/5 n = 4 0101

00011110 1011

0101

0 0011110

1011

1110

Деление с восстановлением остатка.

Делитель неподвижен, сдвигается на один разряд влево. Если получ. ост. на какое либо число > 0,

очередной разряд r – 1, если < 0 , то 0.

Если остаток оказался < 0, то вост. Остаток и делители сдвигается в право.

П ример: 0 0 0 11 11 0 0 1 0 1

1 0 1 1 0 1 1 0

1 0 1 1

1 1 1 0

0 1 0 1

0 0 1 1 1 1 0  0, частное – 1

1 1 0 1 1

1 0 0 0 1 0 1 0

1 0 1 1

1 0 1 1

Делитель оставляем неподвижным, а делимое и промежуточное основание сдвигаются влево на один разряд.

П ример: 0 0 0 1 1 1 1 0 0 1 1 0

0 0 1 1 1 1 0 0 1 0 1

1 0 1 0

1 1 0 1

0 1 1 0

0 0 1 1 1 1 0

0 1 1 1 1 1 0

1 0 1 0

0 0 0 1 1 1 0

Микропрограмма и АЛУ для выполнения операции деления.

Ш вх.

Р1 Р2 R3

n-1

РА РВ Р3

(R) СП

RC

Ш вых.

СП – схема переноса (сдвиг на один разряд влево)

СЦ – счётчик циклов.

Делимое (2n) – Rb

Делитель (n) – R1

Результат (частное) – R2

1. Установка (делимого, делителя, СЦ)

2. Выравнивание (сдвиг на один разряд влево делимого)

3. Проверка возможности деления

4. Проверка знака результата

0 – переполнение

1. Восстановить (в RCM существует величена)

2. Сдвиг делимого на один разряд влево.

3. Вычитание делителя

4. Проверка знака остатка

5. Запись 1 в част., СЦ:=СЦ – 1 сдвиг

6. Вычитание

7. СЦ  0, то п 6

СЦ = 0, то п 15

1. (0) в частное

2. СЦ:= СЦ – 1

3. СЦ  0, то п 5

СЦ = 0, то п 15

Микропрограмма.

Р 1 := Швх

РВ := Швх Установка

R2 := Швх

СЦ := n-1

R A := 0

RC := [PA + PB]

R3 := (1) P2 Сдвиг делителя

RC[0] := P2[n-1]

PB := PC; R2 := R3

P A := R1

RC := (PA + RB + 1)

0

1 0

Переполнение

R2[0]:=0

RA:=0

PC:= (1)(PA + PB); R3:= (1)R2; RC[0] :=[n-1];

RB:=PC; R2:=R3;

Вычитание: RA:=R1

RC:=RA+RB+1

0

1 0

R2[0]:=0 R2[0]:=1

СЦ:=СЦ – 1 СЦ:=СЦ – 1

= 0 >0

= 0 >0

Выход

Проверить выполнение деления.

Деление без востановления остатка.

а – значение числа на каком либо шаге

а > 0; сдвигаем влево (2а) и вычитаем (y); 2а – у

а < 0; востанавливаем предыдущий остаток; сдвиг влево 2а(а+у) = 2ау + 2у

2а + 2у – у = 2а + у

Правило: Если остаток а > 0, то сдвигаем влево на один разряд и вычитаем делитель

Если а < 0, то его сдвигают влево на один разряд и прибавляют делитель

АЛУ и микропрограмма.

Z = x/y

[1] Р1 Р2 R3

n

Р А РВ Р3

+1

[2]

[3]

CП[4]

RC

Ш вых. RB := RC – последний уровень вентиля

• [n] – уровень вентиля

• СП, РС;

• х, у заданы в прямом коде

• х занимает 2n разрядов; у – n разрядов; z – n разрядов

P1 – y

PB – сташая часть х

P2 – младшая часть х

Частное (z) в R2 и остаток в RB

Перед делением образ. знак частного 0 – старший

Т3 = Р1[0]  P2[0]

Установка (0) в знак разряды делимого и делителя

1. Проверка возможности деления.

 0 <0

Д еление не возможно выч. делителя и сдвиг сложение делителя и сдвиг

РА:=P1 РА:=P1

RC := (PA + RB + 1) RC := (PA + RB)

RС := (1) PС, R3 := (1) P2 RС := (1) PС

PC[n-1]:=P2[0] R3 := (1) P2

PB:=PC PC[n-1]:=P2[0]

СЦ:=СЦ – 1

= 0 >0

Вывод, конец деления = >0

Замечания.

Временная диаграмма работы АЛУ  после команд таких как РА:=R1, RC:=А(1)(РА + РВ)

Можно было поступать, выполняя в каждом также одну команду.

При м.програмной реализации, если обращаться после за м.ком. в память, то потребуется больше время.

М.прогр. памяти считываются за 1 цикл навора м.ком. будут выполняться последовательно.

[4]

[3]

[2]

[1]

такты

1 2 3 4

1

0

21

31

РУ

БУУ

Инор.

П осле получения М.ком. в РУ – дв. набор следует открытие вентилей .

Три входа, плюс синхроимпульсы в n такте воздействуют только на вентили n уровня.

Такт работы АЛУ склад из подтактов (из 4 синхроинпульсов)

У

ГСИ

множаются цикл обращения к М.ком. памяти. Вых. [1]

Задержка

[2]

Деление чисел, представленные в дополнительном коде.

Как и умножение требует коррекции. Сначала делим по одному из способов (вез/с восстановлением остатка), а затем в зависимости от знака делимого или делителя необходимо произвести коррекцию.

Итерационный метод выполнения операции деления.

Z = x/y

В некоторых случиях операцию деления рализуют непосредственно операциии умножения: Z = 1/y*х

Неоходимо найти величине обратную делителю: у ^–1 = 1/у. Эта операция достигается за счёт использования итераций формулы, где существуют только операции сложения и умножения .

Для делителя (у) из соответствующей таблици берётся некоторое приближение.

Погрешность: 1/у – t₁

 = 1/у = 1 – уt₁;

1/у = t₁/(1 – ₁).

Рассмотрим 1/(1 – ₁) запишим в виде ряда: 1/(1 – ₁) = 1 + ₁ + ²₁ + ³₁ – ограничивываем двумя слогаемыми.

1 + ₁ = 1 – ²₁

1 – ₁

1 + ₁ + ²₁ + ⁿ₁ = 1 – _1n ⁺¹

1 – ₁

1/у  t₁ (1+₁) = 1/у = t₁ (1 + 1 – yt₁) = t₁ (2 – yt₁)

t_i+1 = t_i (2 – yt_i ) итерационная формула , которая обеспечивает получение 1/у.

Оценки получения погрешности 1/у.

t₁ = 1/y (1 – ₁) t₁  

t₁ = 1/y (1 – ₁) (2 – y *1/y(1 – ₁)) = 1/y(1 – ₁)(2 – 1 + ₁) = 1/y(1 – ₁²)

1. Исх. к разрядов, необходимо получить n 3. Время а) 3t

2. Число шагов Время б) 6t

а) Log₂ n/k

б) Log₃ n/k

1. Затрачиваемое время

а) 3t Log₂ n/k

б) 6t Log₃ n/k

5. Пусть n/k = а, найдём отношение времён:

½ = t₁ / t₂ = 3t Log₂a = 3t Log₂a = Ln a * Ln3 = 0,79

6tLog₃a 6tLog₃a Ln a * 2 * Ln a

t₁/t₂ = 0,79;

t₁ = 0,79 t₂. Этот способ выгодней (за больше шагов, но за меньшее время )

t₁ = 1/y (1 – ₁)

t_i = t_i (3(1 – yt_i) + (yt_i)²)

t₂ = 1/y(1 – ₁) [3  (1 – y  1/y(1 – ₁) +( y  1/y(1 – ₁))²)] = 1/y (1 – ₁)  [3  (1 – (1 – ₁)) + (1 – ₁)²] =

1/y(1 – ₁) [3₁ + (1 – ₁)²] = 1/y(1 – ₁) [3₁ + 1 – 2₁ + ₁²] = 1/y (1 – ₁) [ 1 + ₁ + ₁²] =1/y(1 – ³₁).

t₃ = 1/y(1 – ²₁)[ 2 – y  1/y (1 – ²₁)) = 1/y(1 – ²₁)(2 – 1 + ₁²) = 1/y(1 – ₁²)( 1 + ²₁) = 1/y(1 – ⁴₁).

Если t₁ заданно с точностью четырёх разрядов, а надо получить 1/у с точностью 32 разрядов, необходимо сделать три шага, т.к. на каждом из них число верхних разрядов удваивается.

Для получения t_i+1 на каждом шаге, необходимо произвести два умножения и одно вычитание.

10