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

 

Союз Советских

Социалистических

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИ ЕТЕЛЬСТВУ

<185?975 (61) Дополнительное к авт. свид-ву— (22) Заявлено 2111.79 (21) 2844144/18-24 с присоединением заявки Ho—

G 06 F 7/48

Государстаеииый комитет

СССР по делам изобретеиий и открытий (23) ПриоритетОпубликовано 230сг81. Бюллетень Йо 31, Дата опубликования описания 210881 (53) УДН 681. 325 (088.8) I

В. А. Стулов, В. С . Харькин и В. А. Чекулаев (72) Авторы изобретения г

I (71) Заявитель (54 ) УСТРОИСТВО ДЛЯ ВОЗВЕДЕНИЯ В КВАДРАТ И УМНОЖЕНИЯ

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

Известны устройства умножения, выполненные в виде кналратной матрицы, элементов И, выходы которых подсоединены к блокам сумматоров, соединенных 10 цепями распространения переносов (1 ).

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

Известно также устройство для .воз 15 ведения н квадрат, выполненное в виде треугольной матрицы элементов И с двумя группами. входов, выходы которой подключены к входам одноразрядных сумматоров, соединенных цепями распрост- 20 ранения переносов (2 ).

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

Цель изобоетения — увеличение быстродействия при выполнении операции умножения. 30

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

k-той строки матрицы (k=1, ..., n, где n — разрядность исходных операндов) соединен со входом (2k-1)-го разряда первого сумматора, выход

i-го элемента И k-той строки матрицы (i =2, ..., п -k+1) соединен со входом .(2k + i - 1)-го разряда первого сумматора, введены два нходных и ныходной коммутаторы, промежуточный регистр и второй сумкатогз, пгзичем входы первого и второго входных коммутаторов соединены с входами операндов устройства, выход k-ro разряда nepsoro входного коммутатора соединен с перньмы входами элементов

И k-той строки матРицы, выход m-ro разряда второго входного коммутатора (m 1,...,п) соединен с вторьм входом (m-k+1)-ro элемента И к-той строки матрицы, выход "Сумма" р-го разряда первого сумматора (р=1,...,2n-l) соединен с входом р-го разряда промежуточного регистра, с первьми входами р-го разряда второго сумматора и

857975 выходного коммутатора, выход переноса перво о сумматора соединен со входом

2п-ro разряда промежуточного регистра, с первыми входами 2п-го разряда второго сумматора и выходного коммутатора, выходы разрядов промежуточного регистра соединены с вторыми входами соответствующих разрядов второго сумматора, выход "Сумма" п-го разряда второго сумматора (r 2,...,2n) соединен с вторым входом k-ro разряда (3-1,...,2п-1) выходного коммутатора, выход переноса второго сумматора соединен с вторым входом 2п-го разряда выходного коммутатора, выходы выходного коммутатора являются выходами устройства.

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

Устройство содержит и-разрядные первый 1 и второй 2 входные коммутаторы, треугольную матрицу 3 из и+ ) двухвходовых элементов И 4, первый (2 и-1 )-разрядный сумматор 5, 2п-раз— рядный промежуточный регистр 6, второй сумматор 7 и выходной коммутатор

8 (n ðàýðÿäíoñòü исходных операндов).

Входы а а ...а первого исходного операнда подсоединены к входам 9 пер— вого входного коммутатора 1 и к входам 10 второго входного коммутатора

2, входы Ь, Ь ... Ь„, второго исходного операнда подсоединены к входам 10 первого входного коммутатора 1 и к .входам 9 второго входного коммутатора 2. Выход k-ro разряда 11 (k 1,...,и) первого входного коммутатора 1 соединен с входами 12 эле— ментов И 4 k-ой строки матрицы 3, выход m-ro разряда 13 второго входного коммутатора 2 (m=1.....п) сое— динен с входом 14 (m-k+1)-ro элемента И 4 k-ой строки матрицы 3, выход первого элемента И 4 k-ой строки матрицы 3 соединен с входом (2k-1)-го разряда 15 первого сумматора 5, выход i-го элемента И 4

k-ой строки матрицы 3 (! 2,...,n-k+1) соединен со входом (2k+i -1)-го разряда 15 первого сумматора 5, выход

"Сумма" 16 р-ro разряда 15 первого сумматора 5 (р=1, °,2n-1) соединен с входом р-ro разряда 17 промежуточного регистра б, с входом

18 р-го разряда 19 второго сумматора 7, с входом 20 р-ro разряда 21 выходного коммутатора 8, выход переноса 22 первого сумматора 5 соединен.с входом 2п-го разряда 17 промежуточного регистра 6, с входом

18 2п-го разряда 19 второго сумматора 7 и с входом 20 2п-го разряда 21 выходного коммутатора 8. Выходы раз— рядов 17 промежуточного регистра 6 соединены с входами 23 соответствующих разрядов 19 второго сумматора 7 и с входом 20 2п-го разряда 21 выходного коммутатора 8. Выходы разрядов 17 промежуточного регистра 6 соединены со входами 23 соответствующих разрядов 19 второго сумматора 7.

Выход "Сумма" 24 r-ro разряда 19 второго сумматора 7 (я=2,...,2п) соединен с входом 25 f-го разряда 21 ((=1,..., 2n-i) выходного коммутатора 8. Выход переноса 26 второго сумматора 7 соединен с входом 25 2п-го разряда 21 выходного коммутатора 8 ° Выходы выходнorо коммутатора 8 являются выходами устройства.

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

При возведении в квадрат исходными операндами а а ...аи- и Ьо Ь ... Ьм о является код возводимого в квадрат числа. С выходов входных коммутаторов 1 и 2 код возводимого в квадрат числа поступает на входы 12 и 14 элементов И 4 матрицы 3. Результаты

20 поразрядного перемножения с выходов элементов И 4 матрицы 3 поступают на входы первого сумматора 5. Результат суммирования поразрядных произведении в первом сумматоре 5 с выходов д "Суммы" 16 и с выхода переноса 22 поступает на входы 20 выходного комму— татора 8. Коммутатор 8 разрешает прохождение кода с входов 20 на выходы устройства. После окончания переходных процессов с выходов vcTpoH ства снимается код, соответствующий квадрату исходного числа. При выполнении операции умножения исходными операндами являются коды леремножаемых чисел. В первом такте входные коммутаторы 1 и 2 разрешают прохождение первого сомножителя на вход 14, а второго — на входы 12 элементов

H 4 матрицы 3. .После окончания суммирования в первом сумматоре 5 код по40 лученного частного произведения запоминаетси в промежуточном регистре б и начинается второй такт операции умножения, при котором происходит переключение входных коммутаторов

1 и 2, в результате чего на входы

14 элементов И 4 матрицы 3 проходит второй сомножитель, а а входы 12 первый сомножитель. Получаемый в результате суммирования в первом

®О сумматоре 5 код полученного второго частного произведения поступает на входы 28 второго сумматора 7 и суммируется с полученным в первом такте первым частным произведением, поступающим на входы 13 второго сум>5 матора 7 с выходов промежуточного регистра 6, После окончания суммирования в сумматоре 7 код полученного произведения через выходной коммутатор 8 поступает на выходы устройства.

Необходимо отметить, что использование двух младших разрядов 15 сумматора 5, второго разряда 17 регистра 6 и второго разряда 19 сумма(ора 7 не ивляетси обяэательныл.

857975

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

Устройство для возведения в квадрат и умножения, содержащее треугольную матрицу двухвходовых элементов

И и первый сумматор. причем выход первого элемента И k-ой строки матрицы (k=1,...,n, где п — разрядность исходных операндов) соединен со входом (2k-1)-го разряда первого суя матора, выход i-го элемента И

k-той строки матрицы (1=2,...,п -k+1) соединен с входом (2k+i-1i-ro раз— ряда первого сумматора, о т л и ч аю щ е е с я тем, что, с целью повышения быстродействия при выпол30

40

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

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

Увеличение быстродействия, возможность использования одной и той же схемы для возведения в квадрат и умножения расширяют сферу применения 20 устроиства. нении операции умножения, устроиство содержит два входных и выходной коммутаторы, прсйежуточный регистр и второй сумматор, причем входы первого и второго входных коммутаторов соединены с входами операндов устройства, выход k-го разряда первого входного коммутатора соединен с первыми входами элементов И k-той строки матрицы, выход m-го разряда второго входного коммутатора (m=1,...,п) соединен с вторым входом (m-k+!)-го элемента И k-той строки, матрицы, выход "Сумма" о-го оазряпа первого сумматора (p-.1,...,2п-1) соединен о входом р-го разряда промежуточного регистра, с первыми входами р-го разряда второго сумматора и выходного коммутатора, выход переноса сумматора соединен с входом

2п-го разряда промежуточного регистра, с первьми входами 2п-го разряда второго сумматора и .выходного коммутатора, выходы разрядов промежуточного регистра соединены с вторыми входами соответствующих разрядов второго сумматора, выход "Сумма" r-го разряда второго сумматора (г=2,...,2n) соединен со вторыч входом t -го раз—

РЯда (0.=1, ...,2п-1) выходного коммутатора, выход переноса второго сумматора соединен с вторым входом 2п-го разряда выходного коммутатора, выходы выходного коммутатора являются выходами устройства.

Ъ

Источники информации, принятые во внимание при экспертизе

1. Патент США М 3346729, кл. 235-164, 1966.

2. Вычислительная техника и вопросы кибернЕтики. Л., ЛГУ, 1975, вып.12, с. 37-ЬО (прототип ).

Составитель Н.Слюсарев

Техред М. Рейвес Корректор М. Коста

Редактор П.Ортутай

Заказ 7244/78 Тираж 745 Подписное

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

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

Филиал ППП "Патент", г. уж ород, ул. Проектнзя, 4