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

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

Иллюстрации

Показать все

Реферат

 

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

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

РЕСПУБЛИН (19(® (1(> 1

99, А эапц G 06 F 7/49

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 1.;

И ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗО6РЕТЕНИЙ И ОТНРЬП ИЙ

{21) 3394389/18-24 (22) 17.0?,82 (46) 23.07,83; Вюл. М 27 (72) В.A. Краснобаев и E.И. Бороденка (53) 681.325(088.8) (56) 1. Авторское свидетельство СССР к 922731, кл. G 06 F 7/38, 1978.

2. Авторское свидетельство СССР по заявке У 3247??0/18-24, кл. G 06 F 7/49, 1981 {прототип). (54)(57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ,ЦИСЕЛ ПО ИОДУЛН), содержащее первый и второй входные регистры, входы кото" рых являются соответствующими информационными входами устройства, первый и второй дешифраторы, первую, вторую, третью и четвертую группы элементов 1А., первую, вторую, третью и четвертую группы элементов ИЛИ, первую и вторую группы ключей, коммутатор, первый, второй, третий, четвертый и пятый элементы ИЛИ, первый и второй элементы И, причем выходы первого и второго входных регистров подключены соответственно к входам первого и второго дешифраторов, выходы первой и второй групп которых подключены соответственно к первым и вторым входам элементов ИЛИ первой и второй групп и к входам соответственно перво го, второго, третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих ключей соответственно первой и второй групп, вторые входы которых объединены и являются управляющим входом устройства, а выходы подключены соот . ветственно к входам первой и второй групй коммутатора, выходы первого и четвертого, второго и третьего эле" ментов ИЛИ подключены к входам соответственно первого и второго элемен" i тов И, выходы которых подключены. к входам пятого элемента ИЛИ, первые входы элементов И первой группы объединены с первыми входами соответствующих элементов И второй группы и подключены к соответствующим выходам группы выходов коммутатора, анхо" . ды элементов И первой и второй групп подключены соответственно к первым и вторым входам соответствующих элементов ИЛИ третьей группы, группа вы ходов щирфатора подключена соответственно к первым входам элементов И Я третьей группы, выходы которых под" кппнвны соответственно к первым вко. ® дам элементов ИЛИ четвертой группы, вторые входы которых подключены к 4 соответствующим выходам сумматора по модулю Р, первая группа вход-. которого подключена соответстве,. .э к выходам элементов И четверто;; руп. пы, а вторая является входом конс ан- ©А,1 ты Р/2 устрЬйства, выходы элемен- () тов ИЛИ четвертой группы являются выходом устройства, о т л и ч à ю щ с е с я тем,что,с целью уменьшения объема оборудования, вторые входы элементов И первой и второй групп объ" единены и подключены к выходу пята» го элемента ИЛИ, выходы элементов ИЛИ третьей группы подключены к соответствующим входам шифратора, выходы которого подключены соответственно к первым входам элементов И четвертой группы, вторые входы элементов И третьей и четвертой групп объединены и подключены к выходу коррекции коммутатора.

1 030799

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

Известно устройство для умножения в системе остаточных классов, содержащее входные и выходные регистры, дешифраторы, коммутатор, ключевые элементы, элементы И и ИЛИ, входные ре-. 1p

I гистры последовательно через соответ" ствующие дешифраторы, элементы ИЛИ и ключи подключены к первым и вторым входам коммутатора 1 1, Недостаток ycTpo c aa - больш объем оборудования.

Наиболее близким к изобретению техническим решением является устройство для умножения чисел по модулю, содержащее первый и второй вход- 20 ные регистры, первый и второй дешифраторы, группу элементов И, первую вторую и третью группы элементов ИЛИ, первую и вторую группы ключей, коммутатор, пять элементов ИЛИ, первый 25 и второй элементы И, выходной регистр, причем входы первого и второго входных регистров являются информационными входами устройства, вь(ходы " подключены соответственно к вхо- gp дам соответственно первого и второго дешифраторов, выходы первой и второй групп первого и второго дешифраторов подключены соответственно к первым и вторым входам элементов ИЛИ первой и второй групп и к входам соответственно первого., второго, третьего и четвертого элементов ИЛИ,выходы элементов ИЛИ первой и второй групп подклю, чены к первым входам соответствующих ключей соответственно первой и второй групп, вторые входы которых .объеди" нены и являются управляющим входом -. устройства, а выходы подключены соответственно к первой и второй группам входом коммутатора, выходы элементов ИЛИ третьей группы подключены к. соответствующим входам выходного ре" гистра, кроме того, устройство содержит два элемента И, четыре группы элементов И, шифратор, шестой элемент ИЛИ,четвертую группу элемен" тов ИЛИ, сумматор по модулю P (Рмодуль, по которому работает устрой" ство), первые входы элементов И первой группы объединены с первыми вхо- 55 дами соответствующих элементов И второй группы и подключены к соответствующим выхоаам группы коммутатора, выходы первого и четвертого, второго и третьего элементов ИЛИ подключены к входам соответственно первого и второго элементов И, выходы которых подключены к входам пятого элемента ИЛИ, вторые входы элементов И первой группы элементов И второй группы объединены и подключены к выходу пятого элемента ИЛИ, а выходы подключены соответственно к первым и вторым входам соответствующих элементов ИЛИ третьей группы, входы

К-го элемента И третьей группы (К = — )) подключены к j --му и ) -му выходам соответственно первого и второго дешифраторов (= 1,2,...,Р-1;

) = 1,2 ..., Р-1), для которых A, 3=

А„, В (ггде А и В исходные числа, (. ) - искусственная Форма произведения, Х вЂ” искусственная форма операнда), выходы элементов И третьей группы подключены к входам шестого элемента ИЛИ, выход. которого под" ключен к первым входам элементов И . четвертой и пятой групп, выходы ввходного регистра подключены к соответствующим входам шифратора, выходы которого подключены к вторым входам соответствующих элементов И четвертой группы и к входам первой группы сумматора по модулю Р, вторая группа входов которого подключена к выходам соответствующих элементов И пятой группы, вторые входы которых объединены и являются входом константы

Р устройства, выходы элементов И пятой группы и сумматора по модулю P подключены соответственно к входам соответствующих элементов ИЛИ четвертой группы, выходы которых являются выходом устройства (Rj .

Ф

Недостаток устройства - большой объем оборудования.

Цель изобретения - уменьшение объема оборудования.

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

I второй входные регистры, входы которых являют=я соответствующими информационными входами устройства, первый и второй дешифраторы, первую, вторую, третью и четвертую группы элементов И, первую, вторую, третью и четвертую группы элементов ИЛИ, первую и вторую группы ключей, коммутатор,:,первый, второй, третий, четвертый и пятый элементы ИЛИ, первый и второй элементы И, причем выходы

1030799 первого и второго входных регистров подключены соответственно к входам первого и второго дешифраторов, выходы первой и второй групп которых подключены соответственно к первым и вторым входам элементов ИЛИ первой и второй групп и к входам соответственно первого, второго, третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и вто- 1о рой групп подключены к первым входам соответствующих ключей соответственно первой и второй групп, вторые входы которых объединены и являются управляющим входом устройства, а выходы подключенй соответственно к входам первой и второй групп коммутатора,выходы первого и четвертого, второго и третьего элементов ИЛИ подключены к входам соответственно первого и второго элементов И, выходы которых подключены к входам пятого элемента ИЛИ, первые входы элементов первой группы объединены с первыми входами соответствующих элементов И второй группы и подключены к соответствующим выходам группы выходов коммутатора, выходы элементов И первой и второй групп подключены соответственно к первым и вторым входам соответствующих элементов ИЛИ третьей группы, группа выходов шифратора под. ключена соответственно к первым входам элементов И третьей группы, выходы которых подключены соответственно к первым входам элементов ИЛИ четвер- З5 той группы, вторые входы которых под". ключены к соответствующим выходам сумматора по модулю Р, первая группа входов которого подключена соответственно к выходам элементов И четвертой 40 группы, а вторая является входом константы Р/2 устройства, выходы элементов ИЛИ четвертой группы являются выходом устройства, вторые входы элементов И первой и второй групп объеди- 45 нены и подключены к выходу пятого элемента ИЛИ, выходы элементов ИЛИ третьей группы подключены к соответствующим входам шифратора, выходы которого подключены соответственно к Я1 первым входам элементов И четвертой группы, вторые входы элементов И третьей и четвертой групп объединены и подключены к выходу коррекции коммутатора. 55

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

Устройство содержит первый 1 и второй 2 входы устройства первыи 3 и второй 4 входные регистры, первый 5 и второй 6 дешифраторы, первую 7 и вторую 8 группы элементов ИЛИ, первую 9 и вторую 10 группы ключей, управляющий вход 11 устройства, комму" татар 12, первую 13 и вторую 14 груп-. пы элементов И, первый 15, второй 16 третий 17 и четвертый 18 элемен- ты ИЛИ, первый 19 и второй 20 элементы И, пятый 21 элемент ИЛИ, третью 22 группу элементов ИЛИ, шифратор 23, третью 24 и четвертую 25 группы элементов И, сумматор 26 по модулю Р, вход 27 константы P/2, четвертую 28 группу элементов ИЛИ, выход 29 устройства.

Дешифраторы 5 и 6 служат для преобразования операндов из двоичного кода в унитарный. Иифратор ?3 служит для преобразования операндов из унитарного кода в двоичный. Коммутатор 12 представляет собой двухвходовое ПЗУ.

Количество элементов И в узлах у " мутатора 12 по модулю Р равно () .

Количество входных шин в каждой. груп пе входов коммутатора 12 равно Р-2J2, .

Если входные операнды устройства лежат в интервале 1 A В P -1, то входные операнды коммутатора 12 в

I интервале 1 «С1 P «р- 2- J 2 . В . качестве коммутатора 12 используется 11 квад" рант (табл. 1) таблицы модульного умножения А В (од Р, т.е. схемам сов. падения и коммутатора 1? присваивают" ся значения G P od Р = 14.

Известно, что для операндов, представленных в искусственной форме

P P

A = A + — В = В + —, результат

2 2 операции модульного умножения представляем в виде (АВ) = А В или !

АВ = А H + p/ß . Это обусловлено погрешностью P/Q вычисления значений

А.H (и)ОВР) и AR(06 @.

Таким образом, в некоторых случаях при вычислении (AB)podP) результат операции необходимо корректировать путем добавления величины Pjg .

В табл. 1 знаком (+) отмечены элементы И, значения которых корректировать не надо, т.е. операнды для ко" торкх A В (р.ОД Р) = АВ(во @+ (АВ) = А B 3..

Отдельной входной шиной объединяютгя элементы И, отмеченные зна-! f ком (+ ). Остальные значения0 (иод Р) коммутатора 17 необходимо коррек1 03 0799

6 9+ 12+

8+ 12+ 2 6

6 11+ 2

12+ 4 10+ 2 8+ тировать путем добавления значения

P у . Эту oneрацию осуществляет сум, матор по модулю P ?6, т.е. операцию (a P»(((ad Р»+ Цтобы P.

Наличие выходного сигнала пятого элемента ИЛИ 21 свидетельствует о необходимости инвертирования по мо" дулю Р,значениями» p(»(иодР),Сигнал формируется в зависимости от значения входных операндов А и В !

Q.=-YGhWpмта тр

15 где (» (-2

У З =а,ЕСЛИ 1=Ай (С» =Д,»5=В ); ((p42

7„т =, если — «А Ь Р-» (с» =Р-i(„P=P b ).

В качестве примера приводим табли- 2О цу операндов в искусственной форме для Р = 14 ("габл. ?).

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

По входным шинам 1 и 2 входныеопе" 25 ранды А(и В в двоичном коде поступают на соответствующие входные регистры 3 и 4, с выходов которых по= ступают на соответствующие дешиФраторы 5 и 6. С выходов дешифраторов 5 . и,6 операнды А и В в унитарном коде

30 поступают на соответствующие элементы ИЛИ 7 и 8, с выходов которых. one" ранды (и p через ключи 9 и 10, которые открываются сигналом шины 11, поступают на входы коммутатора I2. З5

Выходной сигнал коммутатора 1?., соот»ветствующий значени»(» Сцъ 1,ynggp),поступает на первые входы К"го элемен" та И 13 и К-»-o элемента И 14. Если .g. = 0 (отсутствует выходной сигнал элемента ИЛИ ?1), тогда сигнал через открытый К-й элемент И 14 поступает на первый вход К-го элемента ИЛИ ?2.

Если.й. = 1 (присутствует выходной сигнал элемента ИЛИ H), тогда сиг" нал через открытый К-й элемент И 13 поступает на вход (Р-К)-ro элемента ИЛИ 22 (вь»ходной сигнал элемента ИЛИ 21 открывает элементы И 13 и .закрывает элементы И 14), Сигнал с выхода элемента ИЛИ 22 поступает на вход шифратора 23, с выхода которого результат операции коммутатора 12 в двоичном коде гоступает на первые входы элементов И 24 и 25. Если

1 (присутствует сигнал коррекции коммутатора 12), то результат опера-! ции г» рЦ»поД Р) через открытые элементы И ?4 (сигнал коррекции $ коммута" тора открывает эл(ементы И 24 и закрывает sRpMGHT».» И 25), элементы ИЛИ 28 поступают на выход 29. устройства. Если = П (отсутствует сигнал коррекции коммутатора 12), тогда результат операции через открытые элементы И 25 поступает на первь»й вход сумматора 26, на второй вход которого по шине 27 в двоичном коде поступает значение

Р

Сумматор осущ(ествляет операцию

Io 1ъ I o cl д .» — 3м o8 P сигнал которого через элементь» ИЛИ 28 поступает на выход 29 устройства.

Таким образом,, исключение из со. става устройства элемента ИЛИ и груг»пы элементов И позволяет уменьшить обьем оборудовайия устройства при сохранении быстродействия функциональ- . ных воэможностей, Т а б л и ц а 1

1030799

Таблица 2

А

>о

10 1

1030799

ВНИИПИ Заказ 5214/49 . Тираж 706 Подписное

Ф ° ° Ф

Филиал ППП "Патент", г.

Ужгород, ул. Проектная, 4