Теория автоматов

Таблица 8 Умножения двоичных чисел с фиксированной запятой на ДСОК, схема 4

СМ	РгВ	СТ	Комментарии
0.0000 0000 +0.0000 1101 0.0000 1101	1.0100	4	СМ:=0, РгА:=[A’]o, РгВ:=[B]o, СТ:=4,
			РгB[0]=1? ДА Первая коррекция: СМ:=СМ+Рг`А,
0.0001 1010	0100 1.		СМ:= R(1) CM, РгВ:=СдвЦ L(1) РгВ, (циклический сдвиг),
0.0011 0100	100 1.0	3	РгВ[0]=1? НЕТ Пропускаем такт подсуммирования. СТ=0? НЕТ СМ:= R(1) CM, РгВ:=СдвЦ L(1) РгВ, (циклический сдвиг), СТ:=СТ-1,
0.0011 0100 +1.1111 0010 0.0010 0111			РгВ[0]=1 ДА СМ:=СМ+РгА,
0.0100 1110	00 1.01	2	РгВ[0]=1? НЕТ Пропускаем такт подсуммирования. СТ=0? НЕТ СМ:= R(1) CM, РгВ:=СдвЦ L(1) РгВ, (циклический сдвиг), СТ:=СТ-1,
0.1001 1100	0 1.010	1	РгВ[0]=1? НЕТ Пропускаем такт подсуммирования. СТ:=СТ-1,
	1.0100	0	СТ=0? ДА РгВ:=СдвЦ L(1) РгВ, (циклический сдвиг),
0.1001 1100 +1.1111 0010 0.1000 1111			РгB[0]=1? ДА Вторая коррекция: СМ:=СМ+РгА’,
			В сумматоре получен  результат умножения: С=0.1000 1111.

 

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

Деление двоичных чисел с плавающей  запятой.

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

Деление двоичных чисел с фиксированной запятой с восстановлением остатка

Прежде всего, необходимо отметить, что при делении чисел с  фиксированной запятой цифры  частного вычисляются в прямом или  обратном коде. Знак результата при  делении  определяется как сумма по модулю 2 знаков делимого и делителя. Знак присваивается результату в конце выполнения операции деления. Деление выполняется всегда в инверсном коде. Поэтому, при отсутствии переполнения разрядной сетки частного положительный результат может передаваться в память непосредственно из регистра частного, так как в этом случае в псевдознаковом разряде находится 0. Если же результат деления отрицательный, то передача его в память должна производиться в том коде, в котором данные поступили на обработку из памяти (дополнительном или обратном). В случае обратного кода это означает необходимость инвертирования всего содержимого регистра частного, включая псевдознаковый разряд. Если же операция деления выполнялась в дополнительном коде, то получение инверсного кода требует использования сумматора из-за необходимости подсуммирования единицы в младший разряд инверсного кода числа, находящегося в регистре частного.

Рассмотрим алгоритм деления на примере деления модулей операндов. Пусть А – делимое, В – делитель. Требуется разделить А на В с точностью до i-го разряда. Тогда 

(1)

При любом значении I должно выполняться неравенство

(2)

т.е. остаток от деления A - BY_i  должен быть меньше делителя, умноженного на 2^-i.  Преобразуем  (2) к виду

(3)

Обозначив (A – BY_i)2ⁱ=R_i, получим

(4)

Цифры частного определяются последовательно, начиная со старшего разряда.  Допустим, что в результате выполнения i циклов получены i старших разрядов частного, т.е. приближенное значение частного Y_i,  удовлетворяющие неравенству (4).  В следующем (i+1)м цикле будет получено значение (i+1) – го разряда частного. Исходными данными для этого цикла являются  Y_i и R_i.

Цифра y_i+1 принимает значение в множестве {0,1}. Если y_i+1=0, то

(5)

(6)

т.е. в частном записывается 0 при  условии

(7)

Если y_i+1=1, то

(8)

(9)

т.е. цифра частного равна 1, если выполняется  условие

(10)

или 

(11)

Так как всегда выполняется  одно из условий (7) или (11), то для определения  текущей цифры частного достаточно проверить  одно из них.  Обычно проверяют  условие (7).  Левая часть этого  неравенства выполняется заведомо, так как согласно (4)  т.е. очередной остаток перед началом следующего шага  деления – всегда положительное число.

Для проверки правой части неравенства  сравним разность (2R_i – B)  с нулем. Если эта разность окажется отрицательной, то в (i+1) – й разряд частного запишем 0 и для подготовки исходных данных для (i+2)-го цикла определим R_i+1 следующим образом:

(12)

Если разность 2R_i-B  то запишем в (i+1)-разряд частного 1, а в качестве исходного значения  для следующего (i+2)-го цикла используем вычисленную разность R_i+1=2R_i – B.

Исходными данными для 1-го цикла  являются Y₀=0, R₀=(A-BY₀)2⁰=A < B,  т.е. неравенство (4) выполняется и перед началом первого цикла.  После завершения n-го цикла мы получим n-значное частное Y_n, вычисленное с недостатком.  Таким образом, правило деления с восстановлением остатков формулируется следующим образом. Делитель вычитается из делимого и определяется знак остатка. Если остаток положительный (делим модули операндов), в псевдознаковом разряде записывается 1. В противном случае в псевдознаковый народ записываем 0, а затем производим восстановление остатка путем подсуммирования делителя к текущему остатку. Далее выполняется сдвиг восстановленного остатка на один разряд влево и повторное вычитание делителя.  В рассматриваемом случае цифры частного  получаются как инверсное значение знака текущего остатка.

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

 

Таблица 9 Действия, выполняемые при делении мантисс

SgA		0		0		1		1
SgB		0		1		0		1
СМ		³0	<0	³0	<0	>0	£0	>0	£0
Действие на СМ		+(ØB)	+B	+B	+(ØB)	+(ØB)	+B	+B	+(ØB)
Цифра частного	ПК	1	0	1	0	0	1	0	1
	ОК	1	0	0	1	1	0	0	1

 

Для выполнения операции деления мантисс  требуются следующие структурные  элементы ОА:

• 2 регистра для хранения делимого и делителя в модифицированном коде;
• сумматор ДСДК (ДСОК), согласованный по формату с регистрами операндов;
• инвертор, для инверсии делителя, так как на сумматоре всегда складываются числа с разными знаками;
• счетчик, задающий число вычисляемых разрядов частного;
• триггер прерывания, который устанавливается в 1, если значение делителя равно 0;
• комбинационные схемы, определяющие значение очередной цифры частного, знак результат,  знак подсуммирования делителя в текущем такте.

 

Пример деления двоичных чисел с фиксированной запятой на ДСДК со сдвигом текущего остатка с восстановлением остатка

Пусть С=А/В, А=-0,11101, В=0,100010. Дополнительные модифицированные коды делимого и делителя равны соответственно: Пример деления приведен в таблице 10.

 

Таблица 10 Деление со сдвигом текущего остатка с восстановлением остатка

СМ	РгС	СТ	Комментарии
00,00000	- - - - - -	6	СМ:=0, РгА:= , РгВ:= ТП:=0, СТ:=6,
+11,00011 11,00011 +00,10010 11,10101			СМ:=СМ+РгА,
			SgСМ=SgРгВ? НЕТ. Следовательно, СМ:=СМ+РгВ,
	- - - - - 1	5	SgСМ=SgРгА. Следовательно, РгС[5]:=1,  СТ:=СТ-1,
11,01010 +00,10010 11,11100	- - - - 1 -		СТ=0? НЕТ. Следовательно, РгС:=L(1) РгС, СМ:=L(1) CM,
			SgСМ=SgРгВ? НЕТ Следовательно, СМ:=СМ+РгВ,
	- - - - 11	4	SgСМ=SgРгА. ДА. Следовательно, РгС[5]:=1, СТ:=СТ-1,
11,11000 +00,10010  00,01010	- - - 11 -		СТ=0? НЕТ. Следовательно, РгС:=L(1) РгС, СМ:=L(1) CM,
			SgСМ=SgРгВ? НЕТ. Следовательно, СМ:=СМ+РгВ,
	- - - 110	3	SgСМ=SgРгА? НЕТ. Следовательно, РгС[5]:=0,  СТ:=СТ-1, Знак сумматора в этом такте инвертировался. Производится восстановление остатка. SgСМ=SgРгВ? ДА. Следовательно,
00,01010 +11,01110 11,11000
11,10000 +00,10010 00,00010	- - 110 -		СТ=0? НЕТ. Следовательно, РгС:=L(1) РгС, СМ:=L(1) CM,
			SgСМ=SgРгВ? НЕТ. Следовательно, СМ:=СМ+РгВ,
00,00010 +11,01110  11,10000	- - 1100	2	SgСМ=SgРгА? НЕТ. Следовательно, РгС[5]:=0,  СТ:=СТ-1, Знак сумматора в этом такте инвертировался. Производится восстановление остатка. SgСМ=SgРгВ? ДА. Следовательно,
11,00000 +00,10010 11,10010	- 1100 -		СТ=0? НЕТ. Следовательно, РгС:=L(1) РгС, СМ:=L(1) CM,
			SgСМ=SgРгВ? НЕТ. Следовательно, СМ:=СМ+РгВ,
	- 11001	1	SgСМ=SgРгА. ДА. Следовательно, РгС[5]:=1,  СТ:=СТ-1,
11,00100 +00,10010 11,10110	11001 -		СТ=0? НЕТ. Следовательно, РгС:=L(1) РгС, СМ:=L(1) CM,
			SgСМ=SgРгВ? НЕТ. Следовательно, СМ:=СМ+РгВ,
	110011	0	SgСМ=SgРгА. ДА. Следовательно, РгС[5]:=1,  СТ:=СТ-1,
	011001		СТ=0? ДА. Выход из цикла. Проверяем переполнение разрядной  сетки: РгС[0]=1? ДА. Следовательно, переполнение разрядной сетки частного имеет место. Выполняем нормализацию результата. С этой целью мантиссу сдвигаем логическим сдвигом на один разряд вправо, и к порядку прибавляем 1. Младший разряд частного сваливается с разрядной сетки и теряется. РгС:=R(1)РгС; СМП:=СМП+1; (Операции над порядком в этой таблице не отображены).

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

Деление двоичных чисел с фиксированной запятой без восстановления остатка.

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

Рассмотрим случай, когда очередной  остаток (при делении модулей  операндов)  отрицательный, R_i<0.  В предыдущем алгоритме в этом случае выполнялись следующие операции.

• Восстановление остатка:

• Сдвиг восстановленного остатка влево:

• Вычитание модуля делителя из восстановленного и сдвинутого влево остатка для определения следующего остатка:

R_i+1=4R_i-1 - |B|.

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

Результат в этом случае отличается от действительного на величину +|B|. Поэтому в качестве второго шага необходимо произвести коррекцию результата на эту величину:

R_i+1=4R_i-1 - 2´|B|+|B|=4R_i-1 - |B|.

В результате получаем требуемую величину последующего остатка R_i+1 за два шага.

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

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