Алгоритм умножения двоичных чисел III сп. в ДК с простой коррекцией

Постановка задачи

 

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

Функциональную схему устройства построить в основном логическом базисе. Операнды разрядностью 4 байта (тридцать два разряда) поступают по входной шине (ШИВх) в дополнительном коде (ДК), результат также в ДК выводится по выходной шине (ШИВых).

Алгоритм умножения двоичных чисел III сп. в ДК с простой коррекцией

 

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

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

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

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

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

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

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

. Произвести анализ цифры очередного разряда множителя.

. Произвести суммирование множимого с суммой частичных произведений (ЧП), если цифра множителя «1», иначе перейти к п.7 алгоритма.

. Произвести сдвиг множителя и суммы ЧП на один разряд влево.

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

 

3. Численные примеры

 

Выполним ручной подсчет в соответствии с вышеуказанным алгоритмом.

В качестве множителя возьмём число 55, а в качестве множимого 36.

 

1. Представим числа отрицательными.

= -55 = 110111₂, А_пк = 1,110111, А_дк = 1,001001= -36 = 100100₂, В_пк = 1,100100, В_дк = 1,011100.

 

Таблица 1.

Множитель	Множимое	Сумматор	Пояснения
1,001001	1,011100	0,000000000000 0,000001001000
		0,000001001000	Коррекция
		0,000000110111 0,000000100100 0,000001001011
1,010010		0,000101101100	Сдвиг
1,100100		0,001011011000	Сдвиг
		0,000000011100	Сложение
		0,001011110100
1,001000		0,01011110100	Сдвиг
1,010000		0,10111101000	Сдвиг
1,100000		0,011110100000	Сдвиг
		0,000000011100	Сложение
		0,011110111100

Получили результат: 0,011110111100

= (-55)*(-36) = 1980 = 11110111100₂

 

.Представим числа таким образом: А<0, B>0

= -55 = 110111₂, А_пк = 1,110111, А_дк = 1,001001= 36 = 100100₂, В_пк = 0,100100, В_дк = 0,100100.

 

Таблица 2.

МножительМножимоеСумматорПояснения
1,001001	0,100100	0,000000111000 0,000000000000 0,000000111000	Коррекция
1,010010		0,000001110000	Сдвиг
1,100100		0,000011100000	Сдвиг
		0,000000100100	Сложение
		0,000100000100
1,001000		0,001000001000	Сдвиг
1,010000		0,010000010000	Сдвиг
1,100000		0,100000100000	Сдвиг
		0,000000100100	Сложение
		0,100001000100

 

Получили результат: 0,100001000100

 

(A*B)_дк=1,100001000100, (A*B)_пк=1,011110111100

P = (-55)*36 = -1980 = -11110111100₂

 

.Представим числа положительными:

= 55 = 110111₂, А_пк = 0,110111, А_дк = 0,110111= 36 = 100100₂, В_пк = 0,100100, В_дк = 0,100100.

Таблица 3.

МножительМножимоеСумматорПояснения
0,110111	0,100100	0,000000000000
		0,000000100100	Сложение
		0,000000100100
0,101110		0,000001001000	Сдвиг
		0,000000100100	Сложение
		0,000001101100
0,011100		0,000011011000	Сдвиг
0,111000		0,000110110000	Сдвиг
		0,000000100100	Сложение
		0,000111010100
0,110000		0,001110101000	Сдвиг
		0,000000100100	Сложение
		0,001111001100
0,100000		0,011110011000	Сдвиг
		0,000000100100	Сложение
		0,011110111100

 

Получили результат: 0,011110111100

Коррекция не нужна, получаем результат:

=55*36 = 1980 = 11110111100₂

Реализация содержательной ГСА

 

Содержательная граф-схема алгоритма представлена на рис. 2.

Выполнение алгоритма начинается с проверки наличия множителя на ШИВх. Он заносится в RG1, RG2, логическим условием P5 проверяется осведомительный сигнал, если он равен “1”, то поступил не нулевой операнд, иначе алгоритм заканчивается и результат умножения равен “0”. Далее с инверсных выходов RG2 множитель подаётся на плечо В сумматора SM, где получается ДК, а затем заносится в RG3. Далее происходит проверка наличия множимого на ШИвх и занесение его в RG2 с последующей проверкой на “0” и подачей на плечо В сумматора SM. Также в счетчик тактов заносится 1, знак произведения определяется путём сложения по модулю 2 знаков множителя и множимого.

Далее, следуя алгоритму, логическим условием P3 проверяется знак множимого, если он равен “1”, то логическим условием Р1 проверяется знак множителя и в зависимости от его знака на плечо А сумматора SM поступают данные, записанные в RG3 или происходит проверка очередной цифры множителя. Если ли знак множимого равен “0”, то RG3 очищается и происходит проверка знака множителя логическим условием Р1. Далее проверяется очередная цифра множителя логическим условием Р2, если он равен “1”, то производим такт сложения суммы ЧП с множимым, иначе переходим к проверке логического условия P4. Если он равен “0”, то следует произвести сдвиги суммы ЧП и множителя, т.е. RG3 и RG1, в счётчик СТ прибавляется 1, в противном случае такт является последним и производится проверка на возможность выдачи результата на ШИВых, завершение алгоритма.

Построение отмеченной ГСА

 

Перед разметкой содержательной ГСА необходимо возле каждой операторной вершины проставить управляющие сигналы УА и обеспечивающие выполнение требуемых действий в соответствии со списком МО операционного автомата. Совокупность МО для каждой операторной вершины образуют микрокоманды (МК), список которых приведен в таблице 4.

 

Таблица 4.

MK	Совокупность МО
Y1	y0,y2,y4
Y2	y3,y5
Y3	y2
Y4	y4
Y5	y5
Y6	y1
Y7	y11

 

Каждой условной вершине содержательной ГСА поставим в соответствие один из входных сигналов управляющего автомата X1, …,X7, список которых дан в таблице 5.

 

Таблица 5.

Входной сигнал УА	X1	X2	X3	X4	X5	X6	X7
Логическое условие ОА	X	P1	P2	P3	P4	P5	Z

 

Далее в полном соответствии с содержательной ГСА строим отмеченную ГСА(рис. 3), условным вершинам которой приписывается один из входных сигналов УА (Х1,...,Х7), а операторным вершинам - одна из МК (в скобках указана совокупность МО для каждой МК). Выделение состояний управляющего МПА возможно в соответствии с моделью Мили или моделью Мура. умножение двоичный число автомат

На рис. 3 приведена разметка ГСА для модели Мили символами a₀, а₁,..., а₈ и для модели Мура - символами b₀, b₁,..., b₁₀. Таким образам, если строить управляющий МПА в соответствии с моделью Мили, то он будет иметь 9 состояний, а в соответствии с моделью Мура - 11 состояний.

Замечание. В двух вершинах ожидания (3 и 17) при разметке по Муру введены фиктивные состояния автомата b₃ и b₉.

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

Библиографический список

 

Курс лекций по дисциплине “Дискретная математика”.

В.Ю. Мельцов. Синтез микропрограммных управляющих автоматов. Учебное пособие. Киров, 2000.

Курс лекций по дисциплине “Теория автоматов”.

Постановка задачи

 

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

Функциональную схему устройства построить в основном логическом базисе. Операнды разрядностью 4 байта (тридцать два разряда) поступают по входной шине (ШИВх) в дополнительном коде (ДК), результат также в ДК выводится по выходной шине (ШИВых).

Алгоритм умножения двоичных чисел III сп. в ДК с простой коррекцией

 

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

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

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

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

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

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

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

. Произвести анализ цифры очередного разряда множителя.

. Произвести суммирование множимого с суммой частичных произведений (ЧП), если цифра множителя «1», иначе перейти к п.7 алгоритма.

. Произвести сдвиг множителя и суммы ЧП на один разряд влево.

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

 

3. Численные примеры

 

Выполним ручной подсчет в соответствии с вышеуказанным алгоритмом.

В качестве множителя возьмём число 55, а в качестве множимого 36.

 

1. Представим числа отрицательными.

= -55 = 110111₂, А_пк = 1,110111, А_дк = 1,001001= -36 = 100100₂, В_пк = 1,100100, В_дк = 1,011100.

 

Таблица 1.

Множитель	Множимое	Сумматор	Пояснения
1,001001	1,011100	0,000000000000 0,000001001000
		0,000001001000	Коррекция
		0,000000110111 0,000000100100 0,000001001011
1,010010		0,000101101100	Сдвиг
1,100100		0,001011011000	Сдвиг
		0,000000011100	Сложение
		0,001011110100
1,001000		0,01011110100	Сдвиг
1,010000		0,10111101000	Сдвиг
1,100000		0,011110100000	Сдвиг
		0,000000011100	Сложение
		0,011110111100

Получили результат: 0,011110111100

= (-55)*(-36) = 1980 = 11110111100₂

 

.Представим числа таким образом: А<0, B>0

= -55 = 110111₂, А_пк = 1,110111, А_дк = 1,001001= 36 = 100100₂, В_пк = 0,100100, В_дк = 0,100100.

 

Таблица 2.

МножительМножимоеСумматорПояснения
1,001001	0,100100	0,000000111000 0,000000000000 0,000000111000	Коррекция
1,010010		0,000001110000	Сдвиг
1,100100		0,000011100000	Сдвиг
		0,000000100100	Сложение
		0,000100000100
1,001000		0,001000001000	Сдвиг
1,010000		0,010000010000	Сдвиг
1,100000		0,100000100000	Сдвиг
		0,000000100100	Сложение
		0,100001000100

 

Получили результат: 0,100001000100

 

(A*B)_дк=1,100001000100, (A*B)_пк=1,011110111100

P = (-55)*36 = -1980 = -11110111100₂

 

.Представим числа положительными:

= 55 = 110111₂, А_пк = 0,110111, А_дк = 0,110111= 36 = 100100₂, В_пк = 0,100100, В_дк = 0,100100.

Таблица 3.

МножительМножимоеСумматорПояснения
0,110111	0,100100	0,000000000000
		0,000000100100	Сложение
		0,000000100100
0,101110		0,000001001000	Сдвиг
		0,000000100100	Сложение
		0,000001101100
0,011100		0,000011011000	Сдвиг
0,111000		0,000110110000	Сдвиг
		0,000000100100	Сложение
		0,000111010100
0,110000		0,001110101000	Сдвиг
		0,000000100100	Сложение
		0,001111001100
0,100000		0,011110011000	Сдвиг
		0,000000100100	Сложение
		0,011110111100

 

Получили результат: 0,011110111100

Коррекция не нужна, получаем результат:

=55*36 = 1980 = 11110111100₂