Устройство для умножения двух n-разрядных чисел

Устройство для умножения двух n-разрядных чисел

Иллюстрации

Показать все

Реферат

 

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

Сецивпистичесиие

Респубпии

О 11 И А Н И Е ()920711

ИЗОБРЕТЕНИЯ (6l ) Дополнительное к авт, свид-sy (22)Заявлено06.! l, 79 (21) 2837362/18-24 с присоединением заявки М (23) Приоритет (5! )М. Кл, G Об F 7/52

9куларатпнныМ камнтет

СССР вв лелем изабретений и открытки

Опубликовано 15.04.82. Бюллетень ¹ 14 ($3II Д (б81 325 (088. 8)

Дата опубликования описания 15.04.82 (72) Автор изобретения

А.И.Стасюк

Киевский ордена Трудового Красного Знамени институт. инженеров гражданской авиации (71) Заявитель (54) УСТРОАСТВ0 f32

Д -РАЗРЯДНЫХ ЧИСЕЛ

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

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

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

Наиболее близким по технической сущности к предлагаемому является устройство „,ля умножения двух И-разрядных чис ел, содержащее сумматор (3) .

Недостатки этого устройства — пониженные бысгродействие и надежность.

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

Указанная цель достигается тем, что устройство содержит вычитатель, блок сравнения и блок элементов И, первая группа входов которого соединена с шинами множителя, вторая группа входов — с шинами множимого, первая, вторая и третья группы выходов с первой, второй и третьей группами входов сумматора соответственно, rtepвая и вторая группы выходов сумматора подключены соответственно к псрвой и второй группам входов вычитателя и к первой группе выходных шин устройства, третья группа выходов сумматора соединена.со второй группой выходных шин устройства, группа выходов вычитателя подключена к первой группе входов блока сравнения, вторая группа входов которого соединена с четвертой группой выходов блока эле9207

3 ментов И а выход блока сравнения является контрольным выходом устройства, и тем, что блок элементов И выполнен в виде матрицы из П столбцов и (2п-1) строк, причем порядковый номер !1j элемента И (нумерация элементов столбца сверху вниз), расположенного в L-м столбце и I-й строке (нумерация столбцов слева направо, нумерация строк сверху вниз) опре-lo деляется по формуле Nij = 1 (; q) первые входы элементов И каждого столбца соединены соответственно с первой группой входов блока и соответственно с четвертой группой выходов блока, вторые входы элементов И с одинаковыми номерами 11 (i=-1,2,... и) подключены соответственно к первой группе выходов блока, выходы элементов И с номерами giI =2,3...1 +1-! (i=1,2,...п) соединены соответственно со второй группой выходов блока, выходы элементов И каждого столбца с номерами Njj tl +1 — 1(1=1,2 ...п) подключены соответственно к третьей группе выходов блока, и тем, что вычитатель содержит группу элементов

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

35 группсй входов вычитателя, первые и вторые входы вторых элементов И группы соединены соответственно с выходами элементов сложения по модулю два первой и второй групп, а выходы - с вторыми входами элементов сложения по модулю два первой группы, выходы элементов сложения по мо-. дулю два второй группы являются группой выходов вычитателй, а также

45 тем, что блок сравнения содержит элемент ИЛИ .и группу элементоB сложения по модулю два, первые и вторые входы которых являются первой и второй группой входов блока, а выходы соединены с.группой входов элемента ИЛИ, выход которого подключен к выходу блока.

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

Схема содержит блок элементов

И 1, сумматор 2, вычитатель 3, блок

1! 4 сравнения 4, шины множителя, мноKHMOI O H выходные 5, б L H,7 - CO0T ветственно (i=1,2,...n; ) =l 2,... и, f =1,2,...,2n) элементы И 8, группа элементов И 9, первый и вто" рой сумматоры 10 и 11, первую, вторую группы элементов сложения по модулю два 12, 13 и 14, элемент ИЛИ 15, группу элементов И 16.

Запись числа х в разрядной форме представляется в виде где С вЂ” основание системы счисления, знак соответствия ° Разрядная

7 матрица числа К представляет собой ленточную матрицу, столбцами которой являются разрядные векторы X того же числа, При этом каждый -й столбец получается путем сдвига вниз на один разряд относительно (I.-l )-го столбца < то есть при =4 можно записать или соответственно

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

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

Для реализации умножения числа х на число 1, то есть ax= 3 их пред2О

v1

Ц25

5 920 ставляют в разрядной форме ь виде выражения ч Y =6 электронная модель которого пред-. ставляет собой комбинационный блок у множ ения, Для нормализованного разрядного вектора а числа а (то есть для разрядного вектора а, у которого старV 1О ший разряд а =1 равен единице) строится разрядная матрица 3, из разрядных ве аршего разряv< да а 0 а а, то есть которая является подматрицей разрядной матрицы 8. Далее1если разрядную

9 матрицу а" умножать на разрядный ч вектор х, получим некоторый разрядный вектор S, 1 а к =Я

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

7 1 чений разрядов x" и а1 разрядных векv 1 торов х и 0 и после окончания переходного процесса в устройстве на выходах элементов И 8 каждого столбца блока 1 образуются векторы частичных

v П произведений ах, ах,...,ах,...ах которые суммируются в сумматоре 2, на выходе которого (то есть на выходе выходной шины 7Ц согласно выраже" нию (3) образуется вектор II . Б то же время на выходах первых сумматоров lO сумматора 2 образуется разрядный вектор S в соответствии с выражением (5) . Разрядные векторы и подаются на вход вычитателя 3, на выходе которого по выражению (6) об" разуется вектор, поступающий на первую группу входов блока 4, на вто-, -рую группу входов которой поступает исходный вектор Х с блока I. Если они равны, то операция умножения выполнена правильно и в устройстве закончен переходной процесс.

Группа элементов И 9 является электронной моделью произведения матриv4 ч цы а на вектор х, а х, функциональное назначение которой состоит в определении частичных произведений

V«Yq g Ю V n а х,а х,...,а х,...а х, которые суммируются по выражению (5} первыми сумматорами lO сумматора 2, на выходах

Ф которых образуется вектор ь. Группа 9 является составной частью блока

1, за счет этого результат произведения в и вектор Э вычисляются одним .и тем же оборудованием. чiv v

P-$=ак -с к =

Это выражение и положено в основу контрольного соотношения для провер- 1р ки умножения и фиксации конца переходного процесса в схеме.

Содержательный смысл контрольного соотношения (6) состоит в том, что в процессе умножения а на, то есть в процессе определения разрядного вектора В по выражению (3) (во время переходного процесса в схеме) вычисляется по выражению (б) раэрядТ ный вектор х, который сравнивается

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

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

При подаче на шину множителя 5 и множимого 6 соответственно энаВ том случае, когда старший разряд а или m старших разрядов разрядv ного вектора а равны нулю, необходимо а сдвинуть влево на один или соответственно m разрядов (то есть

Y нормализовать вектор а), а результат произведения Ь сдвинуть вправо на соответствующее количество разрядов.

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

1есть результат вычисления практически получается за время, равное вре92071 мени задержки сигнала между входными шинами 5 I, 6 j и выходной шиной 7(, кроме тогс, в устройстве осуществляется параллельный контроль вычислений и фиксируется момент окончания переходного процесса в схеме, то есть момент окончания выполнения операции умножения, за счет чего из устройства в этот момент можно считывать

V достоверный результат Ь, а устройство запус:кать на следуюший цикл работы. 11а сути предлагаемое устройство является асинхронным с возможностью диагностического контроля правильности его функционирова«сия в про- 5 цессе работы, что споссбствует применению устройства для синтеза систем управления динамическими процессами в реальном масштабе времени технологическими процессами, в системах оперативного управления.

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

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

И-разрядных чисел, содержащее су сматор, о т л и ч а ю щ е е с я тем, что„с нерп>ю повышения быстродействия и надежности устройства, оно содержит вычитатель, блок сравнения и блок элементов И, первая группа входов которого соединена с шинами множителяя, вторая группа входов — с шинами множимого, перьая, вторая и тре35 тья группы выходов — с первой, второй и третьей группами входов сумматора соответственно, первая и вторая группы выходов сумматора подключены соответственно к первой и вта49 рой группам входов вычитателя H к первой группе выходных шин устройства, третья группа выходов сумматора соединена со второй группой выходных шин устройства, группа выходов вычи45 тателя подключена к первой группе входов блока сравнения, вторая группа входов которого соединена с четвертой группой выходов блока элементов И, а выход блока сравнения является контрольным выходом устройства.

5О

2. Устройство по п. 1, о т л и— ч а ю щ е е с я тем, что блок элементов И выполнен в виде матрицы из б столбцов и 2п-iстрок,,причем порядковый номер Ni элемента И (нумерация элементов столбца сверху вниз), расположеннога в i -столбце

1 8 и — строке (нумерация столбцов слева направо, нумерапия строк сверлу вниз) определяется по формуле 5j

=iv(-1>f †первые входы элементов

И каждого столбца с:оединены соответственна с первой группой входов блока и соответственно с четвертой гру тпай выходов блока, вторые входы элементов И с одинаковыми номерами (i=1,2,...,п) г:,одключе «ы соответственно к первой группе выходов блока, выходы элементов И с номерами (ю

=2,3,. °,,и+1-1(1=1,2,...,п, соединены соответственно со второй группой выходов блока„ выходы элементов

И каждого столбца с номерами 1 > +11 (i =1,2,...,n) подключены соответственно к третьей группе выходов блока.

3. Устройствс по п. 1 о т л H ч а ю щ е е с я тем, что вычитатель содержит группу элементов И, первую и вторую группу элементов сложения по модулю два, первые входы первой группы элементов сложения по модулю два подключены к входам первой группы вычитателя, выходы — к первым входам элементов сложения по модулю два второй группы, вторые входы которых являются второй группой входов вычитателя, первые и вторые ьходы вторых элементов И группы соединены соответственно с. выходами элементов сложения по модулю два первой и второй групп, а выходы — с вторыми входами элементов сложения по модулю два первой группы, выходы элементов сложения по модулю два второй группы являются группой выходов вычитателя.

4. Устройство па п. 1, о т л и ч а ю щ е е с я -:ем, что, блок сравнения содержит =-:лемент ИЛИ, группу элементов сложения по модулю два, первые и вторые входы которых являются первой и второй группой входов блока, а выходы соединены с группой входов элемента ИЛИ, выход которого подключен «I выходу блока.

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

1. .Авторское свидетельство СССР

М- 651341, кл. G 06 F 7,/39, 1978.

2. Авторское свидетельство СССР

Ф 623204, кл, G 06 F 7!39, 1978 (прототип).

92(77) I

Составитель И. Алексеев

Редактор Л.Авраменко Техред А,Бабииец Корректор С.Шекмар

Заказ 2 343/55 Тираж 732 Лодписное

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

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

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