Устройство для умножения двух N-разрядных чисел Советский патент 1982 года по МПК G06F7/52 

(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ДВУХ Изобретение относится к вычисли тельной технике и может быть использовано в составе универсальных вычислительных машин или в специализированных вычислительных устройствах. Известно устройство для умножения двух чисел, содержащее регистры множимого и множителя, сдвигаюощй регист сумматоры-вычитатёли, счетчик, блок управления и элемент И-НЕ СП . Недостатком устройств является невысокое быстродействие, определяемое тем, что вычислительный процесс в них представляется в виде последовательности шагов, кроме того, из-за невозможности осуществления контроля вычислительного процесса и конечного результата выполнения операции умножения снижается их надежность. Наиболее близким по технической сущности к предлагаемому является устройство яvпя умножения двух Г5-разрядных чисел, содержащее сумматор 2 П -РАЗРЯДНЫХ ЧИСЕЛ Недостатки этого устройства - пониженные быстродействие и надежность. Цель изобретения - повышение быстродействия надежности устройства. Указанная цель достигается тем, что устройство содержит вычитатель, блок сравнения и блок элементов И, первая группа входов которого соединена с шинами множителя, вторая группа входов - с шинами множимого,.первая, вторая и третья группы выходов с первой, второй и третьей группами входов сумматора соответственно, первая и вторая группы выходов сумматора подключены соответственно к первой и второй группам входов вычитателя и к первой группе выходных шин устройства, третья группа выходов сумматора соединена.со второй группой выходных шин устройства, группа выходов вычитателя подключена к первой группе входов блока сравнения, вторая группа входов которого соединена с четвертой группой выходов блока элементов И а выход блока сравнения является контрольным выходом устройства, и тем, что блок элементов И выполнен в виде матрицы из П столбцов и (2п-1) строк, причем порядковы номер Mii элемента И (нумераддия элементов столбца сверху вниз), расположенного в 1-м столбце и 1-й строке (нумерация столбцов слева направо, нумерация строк сверху вниз) опр деляется по формуле Nij М(;- , первые входы элементов И каждого столбца соединены соответственно с первой группой входов блока и соответственно с четвертой группой выходов блока, вторые входы элем/гнтов И с одинаковыми номерами Nil {i 1 ,2,,, n) подключены соответственно к первой группе выходов блока, выходы эле меитов И с номерами ,3.,.М+1{i 1,2, . .n) соединены соответственн со второй группой выходов блока, выходы элементов И каждого столбца с номерами hiu П+1-1 (1 1 ,2 ...п) подключены соответственно к третьей группе выходов блока, и тем, что вычитатель содержит, группу элементов И, первую и вторую группы элементов сложения по модулю два, первые входы первой группы.элементов сложения по модулю два подключены к входам первой группы вычитателя, выходы - к первым входам элементов сложения по модулю два второй группы, вторые входы которых являются второй группой входов вычитателя, первые; и вторые входы вторых элементов И груп пы соединены соответственно с выходами элементов сложения по модулю два первой и второй групп, а выходы - с вторыми входами элементов сложения по модулю два первой группы, выходы элементов сложения по модулю два второй группы являются группой выходов вычитателА, а также тем, что блок сравнения содержит элемент ИЛИ .и группу элементов сложения по модулю два, первые и .вторые входы которых являются первой и второй группой входов блока, а выходы соединены сгруппой входов элемента ИЛИ, выход которого подключен к выходу блока.

На чертеже приведена схема устроства для схгучая, когда перемножаемы числа содержат п 5 двоичных разрядоэ.

Схема содержит блок элементов И 1, сумматор 2, вычитатель 3,, блок 9

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

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

Для реализации умножения числа о. на число К , то есть вх о их пред14сравнения 4,. шины множителя, множимого и выходные St, 6 L и .7 t соответственно (i l,2,...n; ,2,.,. n,t 1,2,,,.,2n), эл.ементы И 8, группа элементов И 9, первый и второй сумматоры 10 и 11, первую, вторую группы элементов сложения по модулю два 12, 13 и 14, элемент ИЛИ 15, группу элементов И 16, Запись числа х в разрядной форме представляется в виде п -( 4 K-ICX 1-1 где с - основание системы счисления, - знак соответствия, Разрядная матрица X числа X представляет собой ленточную матрицу, столбцами которой являются разряднь е векторы X того же числа. При этом каждый -й столбец получается путем сдвига вниз на один разряд относительно (1-1)-го столбИЛИ соответственно ставляют в разрядной форме Б виде выражения V у i электронная модель которого представляет собой комбинационный бло умножения. Для нормализованного разрядног вектора а числа а (то есть для ра рядного вектора а , у которого ст ший разряд а 1 равен единице) стр ится разрядная матрица I, из разр а ,бер cy apmero разря .а без „стар foTrrfrfp.дато есть

которая является подматрицей раз.ряднон матрицы И. Далее, если разрядную 1

умножать на разрядный

матрицу получим некоторый разрядвектор X , S,., . ный вектор

л

а хРеализовав

раз.ность между разряднывекторами В и Sj получим векми

тор X

V - V « V5-5 04 -cix - X Это выражение и полажено в основу контрольного соотношения для провер ки умножения и фиксации конца переходного процесса в схеме. Содержательньп сьЯ)1сл контрольного соотношения (6) состоит в том, ч в процессе умножения а на , то есть в процессе определения разрядн го вектора 6 по выражению (3J (во время переходного процесса в схеме) вычисляется по выражению (бЭ разрядный вектор X , который сравнивается с исходным разрядным вектором х. Их равенство является моментом фиксации конца переходного процесса в схеме, а также правильного выполнени операции умножения. Убтройство работает следующим образом. При подаче на шину множителя 5и и множимого 6i соответственно знатронной моделью произведения матрицы а на вектор х , ах , функциональвектор

а л которой состоит ное назначение

в

определении частичных произведении

vt f П

а х,а х7..,а х,...а х, которые суммируются по выражению (з) первыми сумматорами 10 сумматора 2, на выходах которых образуется вектор S. Группа 9 является составной частью блока 1, за счет этого результат произведения D и вектор 8 вычисляются одним -и тем не оборудованием.

В том случае, когда старший раз11о и а разрядных векчении разрядов торов ч и а и после окончания переходного процесса в устройстве на выходах элементов И 8 каждого столбца « блока 1 образуются векторы частичных „ I i V ( V и произведении ах, ах,...,ах,,.,ах , которые суммируются в сумматоре 2, на выходе которого (то есть на выходе выходной шины 7) согласно выражению (з) образуется вектор g. В то же время на выходах первых сумматоров 10 сумма.тора 2 образуется разрядный вектор S в соответствии с выра жением (5) . Разрядные векторы & и подаются на вход вычитателя 3, на выходе которого по выражению (б) образуется вектор Я, поступающий на первую группу входов блока 4, на вто-, рую группу входов которой поступает исходный BfeKTOp % с блока I. Если они равны, то операция умножения выполнена правильно и в устройстве закончен переходной процесс. Группа элементов И 9 является элекm старших разрядов разрядряд а или а равны нулю, необховектораа сдвинуть влево на один или (то есть соответст.венно m разрядов нормализовать вектор а), а результат произведения Ь сдвинуть вправо на соответствующее количество разрядов. Во всем остальном работа устройства осуществляется аналогично. Использование новых элементов устройства, а также наличие новых связей между нимио.тличает предлагаемое устройство для умножения двухП-разрядных чисел от известного, так как в , предлагаемом устройстве за счет новой структурной организации существенно увеличивается -быстродействие, которое характеризуется в данном случае временем переходного процесса в схеме, то есть результат вычисления практически пблучается за время, равное аре9мени задержки сигнала между входными шинами 51, 6 i выходной lUHHoft li, кроме того, в устройстве осуществляется параллельный контроль вычислений и фиксируется момент окончания переходного процесса в схеме, то ест момент окончания выполнения операции умножешия, за счет чего из устро ства в этот момент можно считывать достоверный результат &, а устройство запускать на следующий цикл работы. По сути предлагаемое устройство является асинхронны с возможностью диагностического контроля пра вильности его функционирования в про цессе работы, что cnoccecToyej приме нению устройства для синтеза систем управления динамическими процессами в реальном масштабе времет технологическими процессами, в системах оперативного управления. Фор мул i изобрете шя 1.Устройство для умножения двух Л-разрядн)х чисел, содержащее сумг атор, о т л и ч аю щ е е с я тем, что, с целью повьЕпения быстродействия и над(ажности устройства, оно содержит 1зь читатель5 блок сравнения и блок элементов И, первая группа входов которого соединена с шинами множителя, вторая группа входов - с шинами множимого, первая, вторая и тре тья группы выходов - с первой, второй и третьей группами входов сумматора соответственно, первая и вторая группы выходов сумматора подключены соответственно к первой и второй группам входов вычитателя и к первой группе выходных шин устройства, третья группа выходов сумматора соединена со второй группой выходны шин устройства, группа выходов вычитателя подключена к первой группе входов блока сравнения, вторая группа входов которого соединена с четвертой группой выходов элемен тов И, а выход блока сравнения явля ется контрольным выходом устройства 2.Устройство по п. 1, отли чающееся тем, что блок элементов И выполнен в виде матрицы из f столбцов и 2п-1 строк, причем порядковый номер Mil элемента И (нумер.ация элементов столбца сверху вниз), расположенного в i-столбце И j-строке (.рация столЬцов слева направо, нумерация строк сверху вниз) определяется по формуле Mii NO 1)j -I первые входа элементов И каждого столбца соединены соответственно с первой группой входов блока и соответственно с четвертой группой выходов блока, вторые входы элементов И с одинаковыми номерами Mil (i 1 ,2 5 ,,. , п) подключвгП) соответственно к первой группе выходов блока, выходы элементов И с номерами Nijf 2 S 3 5. , . 5 Г1+ 1 - i (i 1,2 ,, . . , n) соединены соответственно со второй груп пой выходов блока, выходы элементов И каждого столбца с номерами 1 (i 1 ,2 ,, , „ S п) подк.иючены соответ ственно к третье:й группе выходов блока. 3,Устройство по ц„ 1, о т л и чающееся тем, что вычитатель содержит группу элементов И, первую и вторую группу элементов сложения по модулю два, первые входы первой группы элементов сложения по модулю два подключены к входам первой группы вычитателя, выходы - к первым входам элементов сложения по модулю два второй группы., вторые входы которых являются второй группой входов вычитателя, первые и вторые входы вторых элементов И группы соединены соответственно с выходами элементов сложения по модулю два первой и второй групп, а выходы - с вторыми входами элементов сложения по модулю два первой группы, выходы элементов сложения по модулю два второй группы являются груг1пой выходов вычитателя. 4.Устройство по п. , отличающееся тем, что, блок сравнершя содержит элемент ИЛИ, группу элементов сложе1шя по модулю два, первые и вторые входы которых являются первой и второй группой входов блока, а выходы соединены с группой входов элеме;нта ИЛИ, выход кото- рого подключен к выходу блока. Источники информации, принятые во внимание при экспертизе 1„ Авторское свидетельство СССР № 65134, кл. G 06 F 7/39, 1978. 2, Авторское свидетельство СССР № 623204, кл, G 06 F 7/39, 1978 (прототип).