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

ОП ИСАНИЕ и 951296ИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветсиикСоциапистнчесииаРеспублик(51)М. Кл. 6 06 Е 7/49 ЬеуАадетв 6 яьй камктет СССР аа АеЛан язобретекка к отеритвй(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУЛЮ 1Изобретение относится к вычислительной технике.Известно устройство для умножения в сис. теме остаточных классов, содержащее входные и выходной регистры, дешифраторы, ключи,5 коммутатор и логические блоки поиска квадрата и квадрантов арифметической таблицы, В устройстве используются свойства симметрии арифметической таблицы модульного умножения двух операндов 1.тоНедостатком этого устройства является сложность построения и большое количество логических элементов.Наиболее близким к данному изобретению техническим решением является устройство дпя 5 умножения в системе остаточных классов, содержащее входные регистры, дешифраторы, ключи, коммутатор, выходной регистр, а также сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ, причем первый 20 и второй входные регистры последовательно через соответствующие первый и второй дешифраторы, первую и вторую группы элемен. тов ИЛИ и первый и второй ключи подключены соответственно к первой и второй группамвходов коммутатора, первые и вторые группывходов первого и второго дешифраторов подключены соответственно к входам первого,второго, третьего, четвертого элементов ИЛИ,выходы которых подключены к соответствую.щим входам сумматора по модулю два, управляющие .входы ключей являются входами уп.равления устройства, первая группа входовкоммутатора подключена к входам пятогоэлемента ИЛИ н первым входам шестого, седь.могб, восьмого, девятого и десятого элементов ИЛИ, к вторым входам которых подклю.чена вторая группа выходов коммутатора ивходы одиннадцатого элемента ИЛИ, выходкоторого подключеи к первым входам первогои второго элементов И, выход пятого элементаИЛИ подключен к первым входам третьего ичетвертого элементов И, вторые входы перво.го и третьего элементов И и второго и чет.вертого элементов И подключены соответственно к нулевому и единичному выходам сумматора по модулю два, а выходы первого ичетвертого элементов И и соответственно второ.9512 3го н третьего элементов И подключены ксоответствующим входам двенадцатого и тринадцатого элементов ИЛИ, выходы шестого,седьмого, восьмого, девятого, десятого, двенадцатого и тринадцатого элементов ИЛИ сое.динены с соответствующими входами выходногорегистра, выход которого является выходомустройства %,Недостатком устройства является узкаяобласть применения. Это обусловлено тем, 10что в вгяходном регистре результат операциимодульного умножения получается в кодетабличного умножения, а это не позволяетн,".пользовать его непосредственно в цепи последующих операций ЦВМ,15Цель изобретения - расширение области применения за счет получения результата умножения в.двоичном коде,Поставленная цель достигается тем, что устройство, содержащее первый и второй входные 20 регистры, входы которых являются первыми информационными входами устройства, первый и второй дешифраторы, коммутатор, три группы элементов ИЛИ, пять элементов ИЛИ, . три группы элементов И, выходной регистр, выходы которого являются выходом устройства, входы первого и второго дешифраторов подключены к выходам соответствующих регистров, а 1-ый и (Р - 1)-ый выходы (1 = О, 1, 2, Р - 1) подключены соответственно к первому и вто. 30 рому входам 1-ого элемента ИЛИ ( = 1, 2, (Р - 1)/2) соответственно первой и второй групп, первые группы к-х выходов (1 с =О, 1, 2, (Р - 1)/2) соответственно первого и второго дешифраторов подключены к входам соответ. ственно первого и второго элементов ИЛИ, вторые группы г-ых выходов (г=(Р+1) /2, Р - 1) соответственно первого и второго дешифраторов подключены к входам соответственно третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих элементов И первой и второй групп, вторые входы которых объединены и являются управляющим входом устройства, а выходы подключены соот-, ветственно к первой и второй группам входов коммутатора, содержит первый и второй элементы И, четвертую и пятую группы элементов И, шифратор, сумматор, по модулю Р, причем, первые входы элементов И третьей группы объединены с первыми входами соответствующих элементов И, четвертой группы и подключены к соответствующим выходам шифратора, входами подключенного к выходам комму- тато-ч. первые входы элементов И пятой группы55 являются третьим информацион 5 ым Входом устройства, вторые входы элементов И третьей, четвертой и пятой групп объединены и подключены к выходу пятого элемента ИЛИ, первый 96 4и второй входы которого подключены к вы.ходам первого и второго элементов И соответ.отвеяно, первые входы которых подключены к выходам первого и третьего элементов ИЛИ соответственно, а вторые вхоДы - к выходам третьего и четвертого элементов ИЛИ соответственно, вьгходы элементов И четвертой и пятой групп подключены соответственно к первой и второй группам входов сумматора по модулю Р, группа выходов которого подключена к первым входам элементов ИЛИ третьей группы, выходы элементов И третьей группы подключены соответственно к вторым входам элементов ИЛИ третьей группы, выходы которых подключены к соответствующим входам выходного регистра, выход которого является выходом устройства.В предложенном устройстве используются свойства симметрии арифметической таблицы относительно диагонали, вертикали и горизонтали, проходящих между величинами (Р - 1)/2 и (Р+1)/2, где Р - модуль таблицы. Это и определяет возможность реализации в схеме табличного умножения только 0,25 таблицы (табл, 1, для Р:11).Операция модульного умножения выполняется в коде табличчого умножения (табл, 2).Алгоритм получения результата операции определяется следующим соотношением: если два числа Х и У заданы по модулю в кодетабличного умножения Х:( ), х),- (Э, у), то для того, чтобы получить произве.дение этих чисел по модулю Р, достаточно по.лучить произведение х (под Р) в коде таб.личного умножения и инвертировать его индексв случае, если отлично от Яу,где 3 3" - индексы кода табличного умно. жения,о есьи ок-(р-д/2,ЭХ ( 1,Если (Р+Ц 2 ХРНа чертеже представлена блок - схема устройства.Блок схема включает первый и второйвходные регистры 1 и 2, первый и второйдешифраторы 3 и 4, первую, вторую и третьюгруппы элементов ИЛИ 5, б и 7, первый, второй,третий, четвертый и пятый элементы ИЛИ 8 - 12,первую, вторую, третью, четвертую и пятуюгруппы элементов И 13 - 17, коммутатор 18,шифратор 19, сумматор по модулю Р 20, выходной регистр 21, первый и второй элементыИ 22 и 23,Устройство работает следующим образом.Операнды в двоичном коде поступают навходные регистры 1 и 2, С выходов регистров 1 и 2 операнды чисел поступают на своидешифраторы 3 и 4, Сигналы с выходов дешифраторов 3 и 4 одновременно поступают5 95129 на элементы ИЛИ первой и второй группы 5 и 6 и .элементы ИЛИ 8 - 11. Сигналы с вы.ходов элементов ИЛИ первой и второй группы 5 и 6 через элементы И первой и второй групп 13 н 14 поступают на входы коммутатора 18.Управляющий сигнал от устройства управления ЦВМ открывает по вторым входам элементы И первой и второй группы. Белие, - ;, тогда элементы И 22 и 23 закрыты (сигналы одно. временно присутствуют на выходных шинах 1 О первого 11 третьего или второго и четвертого элементов ИЛИ 8 - 11) и таким образом, выходной сигнал элемента ИЛИ 12 отсутствует, элементы И четвертой и пятой групп 16 и 17 закрьпы, а третьей группы 15 открыты. Сигнал,15 определяииций результат операции модульного умножения, по одной из выходных шин ком.мутатора 18 поступает на вход шифратора 19.С выхода шифратора 19 результат операции модульного умножения (в двоичном коде) че реэ открытые элементы И третьей группы 15, группу элементов ИЛИ 7 поступает на вход выходного регистра 21. Если Щс Ф 3"у, тогда-х 1У 6 7 10 7 8 9 3 б 7 10 2 5 6 10 3 10 4 5 б8 10 11 45 9 29 3 82 8 36 2 910 7 43 1 107 б 5 7 1 4 10 1 8 9 6 6 4 3 2 10 10 Таблица 2 Цифра Код в двоичномпредставлении в десятичном представлении 001 0 010 0 0010 б 9 8 2 10 41 7 3 10 5 2 7 5 9 8 6 6открыт один 1 ю элементов И 22 или 23 (сигналы одновременно присутствуют на выходных шинах первого и четвертого или второго и третьего элементов И 8 - 11, и на выходе элемента ИЛИ 12 присутствует сигнал. Этот сигнал открывает элементы И пятой группы 17, четвертой группы 16 и закрывает элементы И первой группы 15. Таким образом, с выхода шифратора 19 на вторую группу входов сум. матора 20 поступает результат операции (в дво. ичном коде) модульного умножения, а на вто. рую группу входов сумматора 20 по третьему входу поступает число Р в двоичном коде.Результат операции модульного сложения (т.е. инвертированное по модулю Р значение реэуль. тата операции модульного умножения) через третью группу элементов ИЛИ 7 поступает на вход регистра 21.Таким образом, введение в устройство двух элементов И, двух групп элементов И, шифратора, сумматора по модулю Р и соот. ветствующих связей позволяет получить резуль тат модульного умножения в двоичном коде.Таблица 1951296 продолжение табл. 2 Цифра Символ Код в десятичномпредставлении в двоичномпредставлении 0011 0 011 0100 0 0101 0 101 101 0100 100 0111 011 1000 010 1001 1010 10 Формула изобретения устройство для умножения по модулю, содержащее первый и второй входные регистры, входы которых являются первым и вторым информационными входами устройства, первый и второй дешифраторы, коммутатор, три группы элементов ИЛИ, пять элементов ИЛИ, три группъ элементов И, выходной регистр, вы. ходы которого являются выходом устройства, входы первого и второго дешифраторов подключены к выходам соответствующих входных регистров, а -й и (р - )-й выходы (1 = О, 1, , р - 1; р - модуль) подключены соответ. ственно к первому и второму входам 1-го зле. мента ИЛИ (1 = 1, 2, (р - 1)/2) соответственно первой и второй групп, первые группъ к х выходов (М = О, 1, 2(р - 1)/2) соответственно первого и второго дешифраторов подключены ко входам соответственно первого и второго элементов ИЛИ, вторые группы г-х выходов (г = (р+1)/2) р - 1) соответственно первого и второго дешифргторов попилю. чены ко входам соответственно третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих элементов И .первой и второй групп, вторые входы кото. рых обьединены и являются управляющим входом устройства, а выходы - подключены соответственно к первой и второй группам входов коммутатора, о т л и ч а ю щ е е с ятем, что, с целью расширения области применения за счет получения результата умножения вдвоичном коде, оно содержит первый и второйэлементы И, четвертую и пятую группы злемен.тов И, шифратор, сумматор ло модулю р, при.35чем первые входы элементов И третьей грчтпы объединены с первыми входами соответствующих элементов И четвертой групг.ы иподключены к соответствующим выходамшифратора, входами подключенного к выходамкоммутатора, первые входы элементов И пятойгруппы являются третьим информационным, входом устройства, вторые входы элементов Итретьей, четвертой и пятой групп объединеныи подключены к выходу пятого элемента ИЛИ, 45первый и второй входы которого подключенык выходам первого и второго элементов Исоответственно, первые входы которых подключены к выходам первого и третьего элементовИЛИ соответственно, а вторые входы - к выхо.дам третьего и четвертого элементов ИЛИ соответственно, выходы элементов И четвертой ипятой групп ,подключены соответственно кпервой и второй группам входов сумматорапо модулю р, группа выходов которого под.ключена к первым входам элементов ИЛИтретьей группы, выходы элементов И третьейгруппы подключены соответственно ко вторымвходам элементов ИЛИ третьей группы, выходы которых подключены к соответствуюцим9 951296 аказ 5948/55 Тираж 731 Подписное ВНИ илиал ППП "Пагент", г, Ужтород, ул. Проекгная,4 входам выходного регистра, выход которогоявляется выходом устройства. Источники информации,принятые во внимание при экспертизе10 1, Авторское свидетельство СССР Иф 550636,кл. 6 06 Р 7/52, 1977. 2, Авторское свидетельство СССР но заявке У 2675156/18 - 24, кл. 6 06 Е 7/39, 1979 5 (прототип) .