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

Изобретение относится к вычислительной технике и может быть и-споль.зовано в универсальных или специализированных вычислительных машинах и устройствах. Известны устройства умножения, выполненные в виде квадратной матрицы/ элементов И, выходы которых подсоединены к блокам сумматоров, соединенных цепя1ми распространения переносов 1 . Однако в этих устройствах операция возведения в квадрат выполняется как обычная операция умножения. Известно также устройство для -воз ведения в квадрат, выполненное в виде треугольной матрицы элементов И с двумя группами-входов, выходы которо подключены к входам одноразрядных сум маторов, соединенных цепями распрост ранения переносов 2 3Недостаток этого устройства з ключается в том, что выполнение операции умножения, не обеспечивает высокого быстродействия, что резко ограничивает сферу применения устройства. Цель изобретения - увеличение быстродействия при выполнении операции умножения. Поставленная цель достигзется тем, что в УСТРОЙСТВО для возведения в квадрат и умножения, содержащее треугольную матрицу двухвходовых элементов И и первый сумматор, причем выход первого элемента И k-той строки матрицы (k 1п; где п - разрядность исходных операндов) соединен со входом (2k-1)-ro разряда первого сумматора, выход i-го элемента И k-той строки матрицы (is2, ..., n-k+1) соединен со входом.(2k + i - 1)-го разряда пер всго сумматора, введены два входных и выходной коммутаторы, зтромежуточный регистра и второй сумматор, причем входы первого и второго входных кокмутаторов соединены с входа- ми операндов устройства, выход k-ro разряда первого входного коммутатора соединен с первьмы входами элементов И k-той строки матрицы, выход т-го разряда второго входного коммутатора (msl, ..,,п) соединен с вторьм входом ()-rp э/1емента И к-той строки матрицы, выход Сумма р-го разряда первого сумматора (,...,2п-1) соединен с входом р-го разряда промежуточного регистра, с первьми входами р-го разряда второго сумматора и выходного коммутатора, выход перенос nepBdO сумматора соединен со входом 2п-го разряда промежуточного регистра , с первыми входами 2п-го разряда второго сумматора и выходного коммутатора, выходы разрядов промежуточ ного регистра соединены с вторыни вх дами соответствуюших разрядов второго сумматора, выход Сумма г-го раз ряда второго сумматора (,.,.,2п) соединен с вторым входом Е-го разЪяда (Е-12п-1) НЕСХОДНОГО коммутатора, выход переноса второго сумматора соединен с вторым входом 2п-го разряда выходного коммутатора, выходы выходного коммутатора являются выходами устройства. На чертеже представлена схема уст ройства для возведения в квадрат и умножения. Устройство содержит п-разрядные первый 1 и второй 2 входные комвдтаторы, треугольную матрицу 3 из двухвходовых элементов И 4, первый (2п-1 )-разрядный сумматор 5, 2п-разрядный промежуточный регистр б, второй сумматор 7 и выходной коммутатор 8 (п-разрядность исходных операндов Входы , . . а пврвого исходного операнда подсоединены к входам 9 пер вого входного коммутатора 1 и к вхо дам°10 вт-орого входного коммутатора 2, входы Ьд Ь . . . Ь увторого исходного операнда подсоединены к входам 10 первого входного коммутатора 1 и к .входам 9 второго входного коммутатора 2. Выход k-ro разряда 11 (kcl ,.,,,п) первого входного комму татора 1 соединен с входами 12 элементов И 4 k-ой строки матрицы 3, выход т-го разряда 13 второго входного коммутатора 2 (гп 1 , . . . , п ) сое динен с входом 14 (m-k+l)-ro элемента И 4 k-ой строки матрицы 3, выход первого элемента И 4 k-ой строки матрицы 3 соединен с входом {2k-l)-ro разряда 15 первого сумматора 5, выход i-го элемента И 4 k-ой строки матрицы 3 ( i 2 , . . . , п -k + 1 ) соединен со входом (2k+i-1)-ro разряда 15 первого сумматора 5, выход Сумма 16 р-го разряда 15 первого сумматора 5 (,...,2п-1) соединен с входом р-го разряда 17 промежуточного регистра б, с входом 18 р-го разряда 19 второго сумматора 7 , с входом 20 р-го разряда 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 г-го разряда 19 второго сумматора 7 {г-г2,.,.п) соединен с входом 25 С-го разряда 21 ,,.., 2п-1) выходного коммутатора 8. Выход переноса 26 второго сумматора 7 соединен с входом 25 2п-го разряда 21 выходного коммутатора 8, Выходы выходного коммутатора 8 являются выходами устройства. Устройство работает следующим образом. При возведении в квадрат исходныЬо Ь-, . . . Ь,., а.и ми операндами является код возводимого в квадрат числа. Свыходов входных коммутаторов 1 и 2 код возводимого в квадрат числа поступает на входы 12 и 14 элементов И 4 матрицы 3. Результаты поразрядного перемножения с выходов элементов И 4 матрицы 3 поступают на входы первого -.суг ниатора 5 . Результат суммирования поразрядных произведении в первом сумматоре 5 с выходов Суммы 16 и с выхода переноса 22 поступает на входы 20 выходного коммутатора 8, Коммутатор 8 разрешает прохождение кода с входов 20 на выходы устройства. После окончания переходных процессов с выходов устройства снимается код, соответствующий квадрату исходного числа. При выполнении операции умножения исходными операндами являются коды перемножаемых чисел, В первом такте входные коммутаторы 1 и 2 разрешают прохождение первого сомножителя на вход 14, а второго - на входы 12 элементов И 4 матрицы 3. После окончания суммирования в первом сумматоре 5 код полученного частного произведения запоминается в промежуточном регистре 6 и начинается второй такт операции умножения, при котором происходит переключение входных коммутаторов 1 и 2, в результате чего на входы 14 элементов И 4 матрицы 3 проходит второй сомножитель, а на входы 12 первый сомножитель. Получаемый в результате суммирования в первом сумматоре 5 код полученного второго частного произведения поступает на входы 28 второго сумматора 7 и суммируется с полученным в первом такте первым частным произведением, поступаю1аим на входы 13 второго сумматора 7 с выходов промежуточного регистра 6. После окончания суммирования в сумматоре 7 код полученного произведения через выходной коммутатор 8 поступает на выходы устройства. Необходимо отметить, что использование двух младших разрядов 15 сумматора 5, второго разряда 17 регистра 6 и второго разряда 19 суммаюра 7 не является обязательным.

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

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

Устройство для возведения в квадрат и умножения, содержащее треугольную матрицу двухвходовых элементов И и первый сумматор, причем выход первого элемента И k-ой строки матрицы (k l , . . .,п ; где п - разрядность исходных операндов) соединен со входом (2k-l)-ro разряда первого сукр- матора, выход i-го элемента И k-той строки матрицы ( i 2 , . . . ,п-k + 1 ) соединен с входом (. /-го разряда первого сумматора, отличающееся тем, что, с целью повышения быстродействия при выполнении операции умножения, устройство содержит два входных и выходной кся 1утаторы, промежуточный регистр и второй сумматор, причем входы первого и второго входных коммутаторов 5 соединены с входами операндов устройства, выход k-ro разряда первого входного коммутатора соединен с первыми входами элементов И k-той строки матри1цл, выход т-го разряда п второго входного коммутатора

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

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

V

Источники информации

принятые во внимание при экспертизе

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

2.Вычислительная техника и вопро сы кибернетики. Л., ЛГУ, 1975, вып.12, 0 с. 37-SO (прототип). itoj lOj .bj ,0., ,b, |o, tt, 10, ffj Ьз |аг|Ьг i ib, .