30 Операции над числами с фиксированной точкой. Алгоритмы. Реализация.

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

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

Для сложения отрицательных чисел используют дополнительное кодирование:

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

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

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

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

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

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

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

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

1. x.0 и y0

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

1. x.>0 и y<0

= + =|x|+2^n-1-|y|= а) |x||y|, 2^n-1+(|x|-|y|)

б) |x|<|y|, 2^n-1-(|y|-|x|)

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

1. x.<0 и y<0

= + =2^n-1-|x|+2^n-1 -|y|=2^n-1+2^n-1 -(|x|+|y|)

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

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

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

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

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

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

Сложение можно выполнять и в обратном коде

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

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

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

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

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

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

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

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

2. x>0, y<0,

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

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

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

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

Пример: x=5 0101

y=-2 1101

0010

1

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

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

1. x<0, y<0,

z’=x’+y’=2^n-1-|x|-1+2^n-1-|y|-1=2^n-1+[2^n-1-(|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

У-множитель, n результат 2n

Тогда z=x+z y раз.

Способы умножения:

• Без ускорения умноженя

• Ускоренное умножение

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

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

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

Пример: x=6

y=5

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. Умножение чисел, начиная со старших разрядов множителя при сдвиге суммы частичных произведений влево и неподвижном множимом.

x=6

y=5

0110

0101

 0000

0000

+ 0110

 00110

00110

+ 0000

 001100

001100

+ 0110

0011110 = 30

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

x=6

y=5

0110

0101

0000

+ 0110

00110

+ 0000

001100

+ 0110

0011110 = 30

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

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

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-разрядов влево. Чтобы получить правильный результат нужно к результату прибавить доп код множимого, сдвинутый на n разрядов влево

Пример:

X=3

Y=-5

0011

*1011

0011 

00011

+0011

01001 

001001 

0001001

+ 0011

0100001 

00100001

+ 1101

11110001 – доп код -15

1. x0

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

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

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

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

Чтобы получить правильный результат нужно к результату прибавить доп код множителя, сдвинутый на n разрядов влево

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. Умножение производится обычным образом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица действий при анализе двух разрядов:

кор	bi	bi+1	действие	кор
0	0	0	П(2) r	0
0	0	1	П(2) (r+М)	0
0	1	0	П(2) (r+2М)	0
0	1	1	П(2)(r-М)	1
1	0	0	П(2) (r+М)	0
1	0	1	П(2) (r+2М)	0
1	1	0	П(2)(r-М)	1
1	1	1	П(2) r	1

П(2) – сдвиг вправо, r-промежуточный результат, М-множимое

Соотношения, описывающие метод Лемана:

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

d_i=

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

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

S_i=

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

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

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

S_i= b_i+1•d_i

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

Объем оборудования зависит от числа разрядов.

4 Деление.

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

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

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

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

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

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

Можно делить (x) на y в том случае, когда z < 2^n-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

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

Алгоритм:

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

2. Знаковые разряды делимого и делителя сбрасываем и сдвигаем делимое на один разряд влево.

3. К делимому прибавляем дополнительный код делителя, выровненный по левому краю и анализируется знак результата.

4. Если получили отрицательный текущий остаток, то восстанавливаем предыдущий остаток (прибавляем делитель в прямом коде) и сдвигаем его. В этом случае разряд частного получает значение 0.

5. Если получили положительный текущий остаток, то очередной разряд частного принимает значение 1 и этот положительный текущий остаток сдвигается влево

6. Повторяем пункты 3-5 до получения n разрядов частного

Недостатком этого способа является необходимость восстановления остатка.

В общем случае после деления имеем целую часть и остаток от деления.

Пример:

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

Алгоритм:

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

2 Знаковые разряды делимого и делителя сбрасываем и сдвигаем делимое на один разряд влево.

3 К делимому прибавляем дополнительный код делителя, выровненный по левому краю и анализируется текущий остаток.

4 Если текущий остаток положительный, сдвигаем его влево на 1 разряд и вычитаем делитель

5 Если текущий остаток отрицательный, то сдвигаем его влево и прибавляем делитель

Пример:

Аппаратная реализация:

Р1-делитель

РВ – старшая часть делимого

Р2 – младшая часть делимого

СП-схема переноса - РС=СдвигВлево(См)

При первом способе деления :

при вычитании из текущего остатка делителя (РА=ИнверсияР1, СМ=РА+РВ+1) сохраняется предыдущий остаток и новый остаток. Если новый остаток отрицательный, то нужно взять сохраненный в РВ и Р2 предыдущий остаток и сдвинуть его. Если текущий остаток положительный, то сдвигаем его.

Разряды частного записываем в младщий разряд Р2

При втором способе:

Текущий остаток находится в РВ и Р2. От этого остатка требуется вычитать или складывать с ним делитель. Новый остаток всегда требуется сдвигать.

13