Устройство для умножения

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ."-; и .,„, эф; 6($

ОПИСАНИЕ ИЗОЬГЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4885773/24 (22) 22.11.90 (46) 15.08.93. Бюл, М 30 (72) А.М.Романов и Ю.И.Шпаков (56) IEEE Translectlons on Computers vol. с-29, В 3, March, 1980, Авторское свидетельство СССР

М 1104509, кл. G 06 F 7/52, 1984. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано в

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

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

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

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

Входы регистров 6 и 7 являются входами устройства первого и второго операндов соответственно, выход регистра 6 соединен с входами первых слагаемых сумматоров 1 и 2 и третьими входами элементов И блока

8, прямой выход регистра 7 подключен к входу второго слагаемого сумматора 1 и вторым входам элементов И блока 9, обратный выход регистра 7 соединен с входом второго слагаемого сумматора 2, выходы. сумматоров 1 и 2 без младшего разряда через селек;50 1833866 Al (st)s G 06 F 7/52 устроиствах цифровой обработки c rHanoe различного назначения. Цельизобретения— сокращение объема оборудования за счет уменьшения емкости блока памяти в 2 раза.

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

И блока 9, а через элемент 10 НЕ к первым входам элементов И блока 8, выходы блока

3 памяти, блоков 8 и 9 элементов И соеди- ©© нены с входами второго, третьего и первого слагаемых сумматора 5, выход которого является выходом устройства.

Преимущество предлагаемого устрой- С© ства перед прототипом (2) заключается в ЯЬ том, что объем оборудования (емкость памя- 0 ти) блока 3 памяти сокращается в 2 раза.

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

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

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

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

/ двумя и-разрядными операндами, представленными целыми двоичными числами.

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

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

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

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

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

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

Блоки 8, 9 элементов И вЂ” для выдачи величины коррекции, равной Х и У, в сумматор 5 для формирования окончательного результата умножения в зависимости от значения последнего разряда в сумматоре

1 и переноса из старшего разряда в сумматоре 2.

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

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

Умножение производится по методу цифрового четвертьквадратного перемножения, основанному на равенстве: х Y — — ((x+ у) (х v) )—

gx+Y} x+ ֧

4 4

Это выражение можно также представить в виде: у (Х+ у (Х вЂ” У)г

Алгоритм функционирования устройства для умножения представлен на рис, 2, Операнды Х и Y разрядности п, участвующие в операции умножения, поступают с входных регистров 6 и 7, соответственно, на входы сумматоров 1, 2, причем на вход сумматора 2 операнд Y подается с инверсного

"0 выхода входного регистра 7. На их выходах получаются величины, равные А= X+ Y u

В - Х+ Y. Селектором 4 выходы сумматоров

1 и 2 поочередно подключаются к входу блока 3 памяти, причем поступают они без

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

X +Y X — Y

2 2, †. Сначала на вход блока 3 паX+V

20 мяти поступает целое число, на его выходе появляется соответствующее ему

X+Y2 целое число (), которое поступает в сумматор 5 и там хранится, Затем на вход

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

Х вЂ” У, на его выходе появляется соответстХ вЂ” Уг вующее ему целое число (), которое в

30 обратном коде из блока 3 памяти подается на сумматор 5,. где определяется окончаx+v х-v2 тельный результат () — () = Х У, > 2 2

Полученное произведение поступает на

35 выходной регистр 8.

Пример: пусть Х и Y - и — разрядные числа, где и = 3

Х110; Y=100;

Х+ Y = 1010; X - Y = 010;

Х + У 101 Х вЂ” Y 001 () — 11001; (— ) = 00001;

45 (— у — ) — () =11000.

Таким образом, результат верен.

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

X+Y Х вЂ” Y

50 р33рА4 (получение 2 и 2 ) может быть потеряна единица младшего разряда (если один из входных операндов четный, а другой — нечетный).

Например:

Х-111; Y =010

Х+ У = 1001 Х вЂ” Y = 101

"+ - ioog "= ioi iQ

1833866

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

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

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

Х+ У)г Х - У)г

X Y() — ()г+ Х, если X < Y.

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

X— - V памяти по адресу, на сумматоре 5 Х+уг уже сложатся () и величина коррекции с блоков 9, 10 элементов И (Y или X).

Далее к полученной величине прибавляется

X — Yz 25 величина () и результат произведения поступает в выходной регистр 8, Предлагаемое устройство для умножения позволяет выполнить эту операцию со скоростью, свойственной устройствам на 30 основе ПЗУ, но значительно меньшем объеме памяти. Объем памяти. сокращается за счет того, что количество адресов блока памяти, по которым находится величина () и (— ) (причем множество знаХ+Уг X — Уг 35

X — Уг чений () является подмножеством множества значений (2 ) ) уменьшает- 40

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

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

X+yг множества значений величин (— — ) и

Х вЂ” Уг () и составляет (2" х2п) бит.

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

2n+1 . 2 и 2п+1 — 2 (раз)

2п

Формула изобретения

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

1833866

Составитель А.Романов

Техред M.Mîðlåíòàë Корректор О.Густи

Редактор

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 2686 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5