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

(50 4 С 06 Г 7 ПО ПИСАНИЕ ИЗОБРЕТЕНИЯ ВТОРСНОМУ Сви(21) (22) (46) (72) (53) (56) СССР97 1.ССР1983. 54) УСТРОЙСТВ АНИЯ ЧИСЕЛ ПО ОДУЛЮ Р УДАРСТВЕННЫЙ КОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ 3852110/2 05.02.85 23.09.86. В.А.Краси 681.325.5 Авторское 6056, кл.Авторское с 68934, кл. Бкд. У 35 обаев (088.8) свидетельст С 06 Р 7/72,видетельство С 06 Г,7/72 801259255 А 1(5) Изобретение относится к областиавтоматики и вычислительной техники.Цель изобретения - расширение функциональных воэможностей эа счет получения результата операции модульногоумножения. Это достигается за счетиспользования свойства следующегоравенства: АВ = (А + В)- (А + В) 1/А.Изобретение целесообразно испольэовать в системах и устройствах, функционирующих в системе остаточныхклассов. 2 ил.1 12592Изобретение относится к автоматике и вычислительной технике и можетбыть использовано в системах и устройствах, функционирующих в системеостаточных классов. 5Цель изобретения - расширениефункциональных возможностей за счетобеспечения возможности получениярезультата операции умножения чиселпо модулю Р.На фиг.1 и 2 представлена структурная схема предлагаемого устройства.устройство содержит первый информационный вход 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разрешения операции сложения - признак операции (А + В) шос 1 Р, вход 26разрешения операции вычитания - признак операции (А " В)шой Р, второйкольцевой сдвигающий регистр 27, вход28 разрешения операции умножения - 40признак операции АВ(шой Р), вторуюгруппу элементов И 29, четвертыйэлемент ИЛИ 30, выход 31 результатавычитания - значение операции (А -- В)шод Р, первый и второй квадраторы 32 и 33, вычитатель 34, группусумматоров 35, шины 36 констант КР(К = 0-3), пятый элемент ИЛИ 37, делитель 38 и выход 39 результата умножения - значение операции АВ(шой Р), 50Умножитель 15 частоты в и=1 о 8 (р - 1 Ц + 1 раз увеличиваетколичество выходных импульсов генератора 12.Количество разрядов КСР 6 и 27 55равно количеству возможных остатковпо исходному модулю Р. Каждый разрядКСР 6 и 27 состоит из и двоичных.паз 552рядов. Первый КСР в разряд осуществляет сдвиг содержимого разрядов в положительном (против часовой стрелки) направлении, а второй КСР 27 осуществляет сдвиг в отрицательном (по часовой стрелке) направлении.Первый 32 и второй 33 квадраторы осуществляют соответственно операции с= (А - В)тпой Р 3 тпос 1 Р и оС = (А + + В)шос Ршос 1 Р.Вычитатель 34 определяет результат операциис = 4 А В(шос 1 Р) =(о -оС )шос 1 Р,э 2Количество сумматоров 35 равно количеству шин 36 и равно четырем. На первые входы сумматора 35 подается значение ст. , на вторые входы - соответствующие значения ЕтРЬ =0-3). С выхода того сумматора 35, для которого значение Ы + 1 сР = 4 ш, т.е.зкратное четырем, сигнал через эле-. мент ИЛИ 37 поступает на вход делителя 38.Делитель 38 производит операцию деления значения 4 тп на четыре, т.е. полученное частное ш = АВ(шой Р) и будет результатом модульного умножения двух операндов.Работу .устройства удобно рассматривать в трех режимах.Режим определения (А + В)шос 1 Р, присутствует сигнал шины 25, Первый операнд А в двоичном коде по шине 1 через регистр 2 поступает на вход дешифратора 3, с выхода которого операнд А в унитарном коде поступает на первый вход соответствующего ключевого элемента 4. Второй операнд В в двоичном коде по шине 9 поступает во второй регистр 10. Сигнал шины 11 запускает генератор 12, с выхода которого импульсы через открытые элементы И 13 и 14 поступают на входы соответственно умножителя 15 частоты и счетчика 16. С выхода умножителя ,15 через открытый элемент И 23 импульсы сдвигают содержимое регистра6 на В и двоичных разрядов влево, Одновременно при совпадении содержимого регистра 10 и счетчика 16 схема 17 сравнения выдает сигнал, который закрывает элементы И 13 и 14, открывает ключевые элементы 4 и элемент И 18, выходной сигнал которого открывает соответствующий (А+ 1)-й-элемент И 5, через который содержимое (А + + 1)-го разряда регистра 6 через эле 1259255мент ИЛИ 7 поступает на выход 8 устройства.Режим определения (А-В)шод Р, присутствует сигнал шины 26. С выхода умножителя 15 через открытый элемент И 24 импульсы сдвигают содержимое регистра 27 на В и двоичных разрядов вправо. Сигнал с выхода элемента И 19 открывает (А+1)-й элемент И 29, через который содержимое (А + + 1)-го разряда регистра 27 через элемент ИЛИ 30 поступает на выход 31 устройства.Режим определения АВ(шод Р), присутствует сигнал шины 28. В этом случае одновременно открыты (А+1)-вые элементы И 5 и 29. Таким образом, на входы квадраторов 32 и 33 поступают сигналы, соответствующие значениям (А-В)шой Р и (А+В)шод Р. Вы читатель 34 определяет результат операциисЕ = Г(А+В)шой Р пюс 1 Р - (Аз2.- В)восо Р 1 шод Р) шос 1 Р. 5 0 5 Сумматоры 35 производят операциюФ д- + Е Р для соответствующих констант О, Р, 2 Р, ЗР, поступающих по шинам Зб, С выхода того сумматора 35, для которого д. + КР = 4 ш (сум ма кратна четырем), сигнал, соответствующий значению 4 АВ(шос 1 Р), через элемент ИЛИ 37 поступает на вход делителя 38 на четыре, с выхода которого значение АВ(щось Р) поступает: З 5 на выход 39 устройства. Формула изобретения Устройство для сложения и вычита ния чисел по модулю Р, содержащее первый н второй входные регистры, дешифратор, группу ключевых элементов, первую группу элементов И, первый кольцевой сдвигающий регистр, первый и второй элементы И, генератор импульсов, схему сравнения, умно- житель частоты, суммирующий счетчик, причем информационный вход первого входного регистра является первым , 50 информационным входом устройства, выход первого входного регистра соединен с информационным входом дешифратора, выходы которого подключены к информационным входам соответствующих ключевых элементов группы, выходы которых подключены к первшм входам соответствующих элементов И первой группы, выходы которых соединены с соответсгвующими входами элемента ИЛИ, второй информационный вход устройства подключен к входу второго входного регистра, управляющий вход генератора импульсов соединен с входом запуска устройства, а выход соединен с первыми входами первого и второго элементов И, выход второго элемента И соединен с информационным входомумножителя частоты, выход первого элемента И соединен с информационным входом суммирующего счетчика, выход которого соединен с первым входом схемы сравнения, выход которого соединен с вторыми входами первого элемента И, второго элемента И и управляющими входами ключевых элементов группы, выходы разрядов первого кольцевого сдвигающего. регистра соединены с вторыми входами элементов И первой группы, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности получения результата операции умножения чисел по модулю Р, в устройство введены третий, четвертый, пятый и шестой элементы И, второй, третий, четвертый и пятый элементы ИЛИ, вторая группа элементов И, второй кольцевой сдвигающий регистр, первый и второй квадраторы по модулю Р, вычитатель, делитель и группа сумматоров, причем выход второго входного регистра подключен к второму входу схемы сравнения, вы" ход которой соединен с первыми входами третьего и четвертого элементов И, к вторым входам. которых подключены выходы соответственно второго и третьего элементов ИЛИ, выход умножителя частоты подключен к первым входам пятого н шестого элементов И, вход разрешения операции сложения устройства соединен с первым входом второго элемента ИЛИ и с вторым входом пятого элемента И, выход которого подключен к управляющему входу первого кольцевого сдвигающего регистра, вход разрешения операции вычитания устройства соединен с первым входом третьего элемента ИЛИ и с вторым входом шестого элемента И, выход которого подключен к управляющему входу второго кольцевого сдвигающего регистра, вход разрешения операции умножения устройства под 5 1259255 фключенвторым входам второго и сложения устройства, выходы первого третьего элементов ИЛИ, выходы клю- и второго квадраторов подключены чевых элементов группы подключены к соответственно к первому и второму первым входам соответствующих эле- информационным входам вычитателя, выментов И второй группы, к вторым ход которого подключен к первым вховходам которых подключен выход чет- дам сумматоров группы, к вторым вховертого элемента И, а к третьим дам которых подключены соответствую- входам - соответствующие разряды вто- щие входы констант устройства, выхорого кольцевого сдвигающего регис- ды сумматоров группы через пятый тра, выход третьего элемента И под О элемент ИЛИ подключены к входу деключен к третьим входам элементов И лителя, установочные входы нерпервой группы, выходы элементов И вого и второго кольцевых сдвивторой группы через четвертый эле- гающих регистров соединены межмев"1 ИЛИ подключены к входу первого ду собой и являются входом квадратора и выходу результата вычи установки и исходное состояние тания устройства, выход первого эле- устройства, выход делителя являет- мента ИЛИ подключен к входу второго ся выходом результата умножения квадратора и к выходу результата устройства.1259255 К Редактор О.Юрковецкая ор Е,Ро з 5122/ дписСР д. 4/5 Производственно-полиграфическое предприятие, г,узгород, ул.Проектная,ставитель М.Ксехред И. Попович Тирам 671 ВНИИПИ Государственного ко по делам изобретений и 113035, Москва, Ж, Рауш