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

В двоичной системе счисления запись числа в модифицированном коде имеет  вид:

Sg1 Sg2.c₁,c₂,…,c_n,  где c₁,c₂,…,c_n – числовые разряды, Sg1 Sg2 – два знаковых разряда, каждый из которых занимает один бит, точка между знаковой и числовой частью служит исключительно для удобства чтения чисел, так как в разрядной сетке регистра отсутствует какой-либо разделитель этих двух частей в записи числа. Положение запятой при такой записи обозначается  только в пояснениях, которые содержатся в сопровождающей  документации.

Критерий переполнения d разрядной сетки формулируется следующим образом:

d=0  Û  Sg1=Sg2.

Если Sg1 ¹ Sg2, и Sg1=0, говорят о положительном переполнении разрядной сетки.

Если Sg1 ¹ Sg2, и Sg1=1, говорят об отрицательном переполнении разрядной сетки.

В случае чисел с фиксированной  запятой положительное переполнение разрядной сетки является фатальным и сопровождается выработкой требования прерывания. Отрицательное переполнение разрядной сетки не требует прерывания. В этом случае результату присваивается значение 0. 

При представлении чисел в форме  с плавающей запятой данные представляются в нормализованном виде. Нарушение нормализации означает, что мантисса результата вычислений не удовлетворяет заданному диапазону значений. Как было отмечено выше, допустимые значения нормализованной мантиссы находятся в диапазоне p^-1£ |m| < 1. Поэтому переполнение разрядной сетки мантиссы называется нарушением нормализации справа, критерием нарушения нормализации справа является  d=1 (d=1Û Sg1 ¹ Sg2).

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

Если нарушена левая часть приведенного неравенства, говорят о нарушении нормализации слева. Критерием нарушения нормализации слева является  величина l.

l=1 Û Sg2=c_1. Т.е. в случае равенства значений знакового разряда и старшего числового разряда при отсутствии переполнения разрядной сетки.  Очевидно, l=1 означает, что значение мантиссы меньше, чем р^-1. Для нормализации числа требуется выполнить сдвиг мантиссы на один разряд влево и вычесть 1 из значения порядка.

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

Умножение двоичных чисел в форме  с плавающей запятой

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

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

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

Умножение чисел с фиксированной  запятой на ДСДК, схема 1

При умножении сомножители играют разную роль: множимое подсуммируется к накопленным значениям частичного произведения. А множитель управляет процессом подсуммирования. Порядок выполнения действий и требуемые аппаратные средства определяются схемой Горнера. Результат умножения получается в дополнительном коде с правильным знаком и двойной точности. Схема Горнера э это математическое выражение, представляющее умножение как операцию над значением множимого, когда множитель записан в виде взвешенной суммы значений разрядов. Инверсные коды (дополнительный и обратный) при отрицательном множителе инвертируют значения его разрядов в соответствии с правилами образования соответствующего кода. Поэтому непосредственное умножение «столбиком» на отрицательный множитель приводит к неверному результату. Поэтому прежде, чем рассматривать собственно алгоритм умножения необходимо понять, на что же должно умножаться множимое. В соответствии с вышеизложенным, дополнительный код положительного числа совпадает с его естественным представлением, а в случае отрицательного числа  множитель, полученный из памяти, представлен в соответствии с правилом образования дополнительного кода. На основании этого правила необходимо определить то значение множителя В, на которое должно производиться умножение. Итак, при отрицательном множителе B<0 его код, принимаемый из памяти, имеет вид:  [B]_д=р+В. Отсюда

B=[B]_д – р = SgB.b₁b₂…b_n -p.

(1)

Так  как мы рассматриваем случай отрицательного множителя, SgB=1, и знаковая единица имеет вес  2⁰=1, выражение (1) можно переписать в виде:

B = 1,b₁b₂…b_n – 2 = 0,b₁b₂…b_n +1-2 = 0,b₁b₂…b_n – 1.

(2)

Запишем теперь произведение двух двоичных чисел в виде

[C]_д = [A]_д (b₁2^-1+b₂2^-2+…+b_n2^-n-1)=b₁([A]_д2^-1) + b₂([A]_д2^-2)+…+b_n([A]_д2^-n) - SgB[A]_д,

(3)

Из выражения (3) следует, что при умножении по схеме 1 на ДСДК регистр множимого А должен в каждом такте умножения сдвигаться на один разряд вправо; поэтому регистр А должен иметь двойную точность. Такую же точность должен иметь сумматор. Разряды множителя анализируются, начиная со старшего разряда. Поэтому регистр множителя сдвигается влево. Коме того из (3) видно, что, если SgB=1 ( случае отрицательного множителя), в начале умножения необходимо выполнить коррекцию, выполнив микрооперацию

CM:=CM + Рг`А.  Инверсное значение множимого `А может быть получено с помощью инвертора, который инвертирует все цифры множимого, принятого из памяти. При этом получается обратный код А. Для получения дополнительного кода числа , записанного в РгА,  в соответствии с правилом образования дополнительного кода необходимо одновременно подать на вход переноса младшего разряда сумматора 1. При этом обратный код, полученный при инвертировании, становится дополнительным кодом. При положительном множителе SgB=0, и коррекция не выполняется.  Таким образом, выражение (3) полностью описывает все этапы выполнения умножения по схеме 1 на ДСДК.

ПРИМЕР 

Пусть А=0,1101, В=-0,1011. Требуется определить произведение [C]_д = [A]_д´В. Составим таблицу расчета в соответствии с формулой (3).

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

СМ	РгА	РгВ	СТ	Комментарии
0.0000 0000 +1.0011 0000    1.0011 0000 +0.0011 0100   1.0110 0100 +0.0000 1101   1.011 0001	0.1101 0000	1.0101	4	Такт 1. СМ:=0, РгА:= [A]д|0000, РгВ:= [В]д , СТ:=4 (четыре числовых разряда, которые должны быть проанализированы).
				Такт 2. Проверка знака  В. SgB=1, следовательно, выполняется коррекция: СМ:=СМ+ØРгА+1.
	0.0110.1000	0101*		Такт 3. РгА:= R(1)РгА, РгВ:=L(1)РгВ,
	0.0011 0100	101**	3	Такт 4. Выполняется проверка РгВ[0]=1. Условие не выполняется. Поэтому такт подсуммирования пропускается, выполняются сдвиги и декремент счетчика: РгА:= R(1)РгА, РгВ:=L(1)РгВ, СТ:=СТ-1.
				Такт 5. Проверка: СТ=0. Условие  не выполняется. Выполняется проверка РгВ[0]=1. Условие выполняется. СМ:=СМ+РгА.
	0.0001 1010	01***	2	Такт 6. РгА:= R(1)РгА, РгВ:=L(1)РгВ, СТ:=СТ-1.
	0.0000 1101	1****	1	Такт 7. Выполняется проверка РгВ[0]=1. Условие не выполняется. Поэтому такт подсуммирования пропускается, выполняются сдвиги и декремент счетчика: РгА:= R(1)РгА, РгВ:=L(1)РгВ, СТ:=СТ-1.
			0	Такт 8. Проверка: СТ=0. Условие  выполняется. Выход из цикла. Конец  умножения.

 

Чтобы прочесть результат, запишем  его в естественной форме: С = - 0.100 1111. Последняя запись получена обратным преобразованием дополнительного кода отрицательного числа в естественную форму представления. Как видно, результат получился автоматически с правильным знаком.

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

В этом случае рассуждения совпадают  со схемой предыдущего раздела. Однако, так как правило образования обратного кода отрицательного числа  имеет вид [B]_o=p + B - 1*2^-n,  схема Горнера принимает следующий вид:

[C]_o = [A]_o*(b₁2^-1+b₂2^-2+…+b_n2^-n-1+1*2^-n).

(4)

Подставляя (4) в произведение, получим

[C]_o= b₁ ([A]_o2^-1)+b₂([A]_o2^-2) +…+ b_n([A]_o2^-n) - SgB[A]_o+ SgB*2^-n.

(5)

Из (5) следует, что при умножении  на отрицательный множитель на ДСОК выполняется две коррекции: первая коррекция (– SgB*[A]_o) выполняется перед входом в цикл, вторая –

(+SgB*2^-n) –после выхода из цикла.

Пример 2. Пусть А=-0.1101,  В=-0.1011. Тогда [A]_o = 1.0010,  [B]_o = 1.0100. Процедуру умножения и результат  представим в виде таблицы 2.

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

СМ	РгА	РгВ	СТ	Комментарии
1.1111 1111 +0.1101 0000    0.1101 0000 + 1.1100 1011    0.1001 1011 +                   1    0.1001 1100 +1.1111 0010   0.1000 1110 +                  1   0.1000 1111	1.0010 1111	1.0100	4	Такт 1. СМ:=0, РгА:=[A]o|1111, РгВ:= [B]o, СТ:=4.
				Такт 2. Проверка знака  В. SgB=1, следовательно выполняется первая  коррекция: СМ:=СМ+ØРгА.
	1.1001 0111	01001		Такт 3. РгА:= R(1)РгА, РгВ:=СдвЦ L(1)РгВ, (так как после выхода из цикла потребуется выполнение второй коррекции (см. (5)), для сохранения знака применяем циклический сдвиг РгВ). При этом старший разряд переписывается на место младшего разряда этого же регистра.
	1.1100 1011	10010	3	Такт 4. Выполняется проверка РгВ[0]=1. Условие не выполняется. Поэтому такт подсуммирования пропускается, выполняются сдвиги и декремент счетчика: РгА:= R(1)РгА, РгВ:=L(1)РгВ, СТ:=СТ-1.
				Такт 5. Проверка: СТ=0. Условие  не выполняется. Выполняется проверка РгВ[0]=1. Условие выполняется. СМ:=СМ+РгА.
	1.1110 0101	00101	2	Такт 6. РгА:= R(1)РгА, РгВ:=СдвЦ L(1)РгВ, СТ:=СТ-1.
	1.1111 0010	01010	1	Такт 7. Выполняется проверка РгВ[0]=1. Условие не выполняется. Поэтому такт подсуммирования пропускается, выполняются сдвиги и декремент счетчика: РгА:= R(1)РгА, РгВ:=СдвЦ L(1)РгВ, СТ:=СТ-1.
			0	Такт 8. Такт 7. Выполняется  проверка РгВ[0]=1. Условие не выполняется. Поэтому такт подсуммирования пропускается, выполняется декремент счетчика: СТ:=СТ-1.
		1.0100		Такт 9. Проверка: СТ=0. Условие  выполняется. Выход из цикла. РгВ:= СдвЦ L(1)РгВ,
				Такт 10. Выполняется проверка: РгВ(0)=1. Условие выполняется. Производится вторая коррекция. СМ:= СМ+РгА. Конец.

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

Умножение двоичных чисел с фиксированной  запятой на ДСДК, схема 2

Схема Горнера имеет вид:

[C]_д=[A]_дB=[A]_д(b₁2^-1+b₂2^-2+…+b_n2^-n-SgB)=SgB _д+2^-1(b₁[A]_д+2^-1(b₂[A]_д+…+2^-1(b_n[A]_д+0))…).

(6)

Выражение (6) показывает, что в этом случае разряды множителя анализируются, начиная со старшего разряда, т.е. регистр В сдвигается в каждом такте на один разряд вправо, и сумматор сдвигается на каждом такте на один разряд вправо. Коррекция при отрицательном множителе выполняется после выхода из цикла. В этой схеме умножения используется модифицированный код множимого и сумматор одинарной точности, производящий подсуммирования в модифицированном коде. Так как результат при умножении получается двойной точности, то необходимо предусмотреть схему хранения младших разрядов произведения, которые при сдвигах сумматора вправо будут сваливаться с разрядной сетки. При умножении на ДСДК младшие разряды произведения по мере их получения записываются в старшие разряды регистра В, освобождающиеся при сдвиге его вправо после очередного подсуммирования. Пример умножения для значений сомножителей: А=0,1101 и В=-0,1011 представлен в таблице 3.

 

Таблица 3 Умножение на ДСДК, схема 2

СМ	РгВ	СТ	Комментарии
00.0000 +00.1101   00.1101   00.0110             00.0011    +00.1101 01.0000     00.1000         00.0100   + 11.0011 11.0011	1,0101	4	1. РгА:=[A]дм, РгВ:=[В]д, СМ:=0, СТ:=4,
			2. Выполняется проверка  РгВ[4]=1. Условие удовлетворяется. Следовательно, производится подсуммирование РгА в сумматор.
	1 1.010	3	3. Производится сдвиг  сумматора и РгВ  на один  разряд вправо. Одновременно младший разряд сумматора переписывается в старший разряд РгВ. Т.Е. РгВ:= R(1) Рг(В), РгВ[0]:=СМ[5], СМ:= R(1)СМ, СТ:=СТ-1.
			4. Проверка: СТ=0 ? НЕТ Значит, снова проверяется РгВ[4]=1? НЕТ Следовательно, такт подсуммирования пропускается. Выполняется пункт 3.
	01 1.01	2	5. СТ=0? НЕТ Следовательно проверяется  значение анализируемого разряда множителя: Рг B[4]=1? ДА Следовательно, производится подсуммирование РгА к содержимому сумматора: СМ:=СМ+РгА,
	001 1.0	1	6. Производится сдвиг  сумматора и РгВ  на один разряд вправо. Одновременно младший разряд сумматора переписывается в старший разряд РгВ. Т.Е. РгВ:= R(1) Рг(В), РгВ[0]:=СМ[5], СМ:= R(1)СМ, СТ:=СТ-1.
	0001 1.	0	7. Проверка: СТ=0 ? НЕТ Значит, снова проверяется РгВ[4]=1? НЕТ Следовательно, такт подсуммирования пропускается. Выполняется пункт 3.
			8. СТ=0? ДА Выход из  цикла. В РгВ[4] находится SgB. SgB=1? ДА Выполняется коррекция: СМ:=СМ+Рг`А,