Устройство для умножения Советский патент 1993 года по МПК G06F7/52 

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

Целью изобретения является сокращение объема оборудования за счет уменьшения емкости блока памяти.

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

Устройство содержит сумматоры 1 и 2, блок 3 памяти, селектор 4, сумматор 5, регистры 6 и 7, блоки 8 и 9 элементов И, элемент 10 НЕ.

Входы регистров 6 и 7 являются входами устройства первого и второго операндов соответственно, выход регистра 6 соединен с входами первых слагаемых сумматоров 1 и 2 и третьими входами элементов И блока 8, прямой выход регистра 7 подключен к входу второго слагаемого сумматора 1 и вторым входам элементов И блока 9, обратный выход регистра 7 соединен с входом второго слагаемого сумматора 2, выходы, сумматоров 1 и 2 без младшего разряда через селектор 4 подключены к блоку 3 памяти, выход младшего разряда сумматора 1 соединен со вторыми входами элементов И блоков 8 и первыми входами элементов И блока 9, выход переноса из старшего разряда сумматора 2 подключен к третьим входам элементов И блока 9, а через элемент 10 НЕ к первым входам элементов И блока 8, выходы блока 3 памяти, блоков 8 и 9 элементов И соединены с входами второго, третьего и первого слагаемых сумматора 5, выход которого является выходом устройства.

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

СО

о

нии произведения, когда в младшем разряде результата, поученного в сумматорах 1 и 2, будет единица, введены блоки 8, 9 элементов И, элемент 10 НЕ с.соответствующи- ми связями, позволяющие произвести коррекцию результата произведения в сумматоре 5.

Входные регистры 6 и 7 операндов введены как общепринятые узлы в арифметико- логических устройствах Входной регистр, позволяет выдать в сумматор 2 операнд в обратном коде для выполнения операции вычитания..

Устройство для. умножения предназначено для выполнения этой операции над двумя n-разрядными операндами, представленными целыми двоичными числами.

Назначение узлов устройства для умножения.

Регистры 6, 7 для приема, хранения и выдачи двоичных n-разрядных исходных операндов X и Y.

Сумматор 1 - для определения суммы исходных операндов А - X + Y .

Сумматор 2 - для определения разницы исходных операндов В Х + Y и преобразовании результата, полученного в обратном коде, в прямой код в случае.Х Y.

Селектор 4 - для последовательной выдачи двоичных чисел А и В без младшего разряда т.е. А/2 и В/2, в блок 3 памяти. Что равносильно сдвигу на 1 разряд вправо.

Блок 3 памяти - для хранения и выдачи чисел (А/2)2 и (В/2)2. Причем (В/2)2 выдается в обратном коде.

Сумматор 5 - для формирования окончательного результата умножения с учетом и без учета коррекции.

Блоки 8, 9 элементов И - для выдачи величины коррекции, равной X и Y, в сумматор 5 для формирования окончательного результата умножения в зависимости от значения последнего разряда в сумматоре 1 и переноса из старшего разряда в сумматоре 2.

Элемент НЕ 10 - для инвертирования значения переноса из старшего разряда в сумматоре 2, поступающего на блок И 8.

Устройство работает следующим образом.

Умножение производится по методу -цифрового четвертьквадратного перемножения, основанному «а равенстве:

(X + Y)2-(X-Y)2

(X + Y)2 (X.-+ Y)2 .

44

Это выражение можно также представить в виде:

X Y (X + Y,

Д-Ys

Алгоритм функционирования устройства для умножения представлен на рис. 2.

Операнды X и Y разрядности п, участвующие в операции умножения, поступают с входных регистров 6 и 7, соответственно, на входы сумматоров 1,2, причем на вход сум- матора 2 операнд Y подается с инверсного

выхода входного регистра 7. На их выходах получаются величины, равные A X + Y и В X + Y. Селектором 4 выходы сумматоров 1 и 2 поочередно подключаются к входу блока 3 памяти, причем поступают они без младшего разряда (т.е. сдвинуты на 1 разряд вправо), что равносильно выражениям

X Ь Y X - Y

n , -г- . Сначала на вход блока 3 паX + Y

20 мяти поступает целое число --

на его

выходе появляется соответствующее ему целое число (---)2 , которое поступает в

сумматор 5 и там хранится, Затем, на вход

блока 3 памяти поступает целое число

X -у

-г- , на его выходе появляется соответст

вующее ему целое число (---)2

которое в

обратном коде из блока 3 памяти подается на сумматор 5, где определяется окончательный результат (Х Y)2 - fc)2 X Y.

Полученное произведение поступает на выходной регистр 8.

Пример: пусть X и У - п - разрядные числа, где п 3

0

Х-110;

X + Y 1010;

Р-101; ,Х + Y,2

X-Y 010;

-001; X - Y,2

5

Ру-Ч - f1001: - 00001; (2 + Y)2(XzY)2 11000i

Таким образом, результат верен. Следует заметить, что в результате сдвига величины X + Y и X - Y вправо на 1

разряд (получение

X + Y X - Y

) может

22

быть потеряна единица младшего разряда (если один из входных операндов четный, а другой - нечетный).

Например: Х-1Т1; X + X+Y

Y 010 Х-Y 101 X-Y

юоЩ 101 |Т

Л это при«едет к возникновению погрешности результата умножения.

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

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

X - У (у)2 - ()2 + Y, если X Y.

X - Y (Цг)2 - (-Т+ Х- если X Y.

При коррекции произведения быстродействие предлагаемого устройства по сравнению с прототипом не ухудшается, так как пока производится обращение к блоку 3

X - Y памяти по адресу на сумматоре 5

уже сложатся ()2 и величина коррекции с блоков 9, 10 элементов И (Y или X). Далее к полученной величине прибавляется

X - у величина () и результат произведения

поступает в выходной регистр 8.

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

(-п-)2 и (-т-)2 причем множество знаX - V 7

чений () является подмножеством

v i Y

множества значений (--к-) уменьшается. К этому приводит операция сдвига величины (X + Y) и (X - Y) вправо на 1 разряд, что равносильно делению на 2.

Объем памяти, требуемый для хранения

,Х + Уч2

множества значении величин () и (Х Y)2 и составляет (2П х2п) бит.

Выигрыш в объеме блока 3 памяти составляет по отношению к прототипу:

2п+1 . 2п

,п + 1

2 (раз)

52П 2 п2П

Формула изобретения Устройство для умножения, содержащее первый и второй входные регистры, первый и второй сумматоры, селектор и

Q блок памяти, вход которого соединен с выходом селектора, первый и второй входы которого соединены соответственно с выходами разрядов суммы, кроме выходов младшего,, разряда, первого и второго

5 сумматоров, входы первых слагаемых которых соединены с выходом первого входного регистра, вход которого соединен с входом первого операнда устройства, вход второго операнда которого соединен с входом втоQ рого входного регистра, прямой выход которого соединен с входом второго слагаемого первого сумматора, отличающееся тем, что, с целью сокращения объема оборудования за счет уменьшения

5 емкости блока памяти, в него введены тре- . тий сумматор,.два блока элементов И и элемент НЕ, выход которого соединен с первыми входами элементов И первого бло- . ка, вторые входы которых соединены с выQ ходом младшего разряда первого сумматора и первыми входами элементов И второго блока, вторые входы которых соеди: нены с входами второго слагаемого первого сумматора и прямым выходом второго вход5 ного регистра, инверсный выход которого соединен с входом второго слагаемого второго сумматора, выход переноса которого . соединен с входом элемента НЕ и третьими входами элементов И второго блока, выходы

Q которых соединены с входом первого слагаемого третьего сумматора, входы второго и третьего слагаемых которого соединены соответственно с выходом блока памяти и выходами элементов И первого блока, третьи

5 входы которых соединены с входами первых слагаемых первого и вторс;о сумматоров и выходом первого входного регистра, выход третьего сумматора соединен с выходом результата устройства.

Изобретение относится к вычислительной технике и может быть использовано в устройствах цифровой обработки сигналов различного назначения. Цель изобретения - сокращение объема оборудования за счет уменьшения емкости блока памяти в 2 раза. Цель достигается сокращением адресов в блоке памяти, по которым хранится заранее занесенная информация, используемая при формировании произведения двух п-раз- рядных чисел по методу четвертьквадратич- ного перемножения. 1 ил.