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

Номер патента: 981990

Авторы: Королев, Краснобаев

ZIP архив

Текст

981 990 ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛВСТВУ Союз СоветскихСоцнапнстнческикРеспублик(088.8) Опубликовано 15,12,82 Боллетень Мф 46 пе леван изабретеивй и втврыти 3Дата опубликования описания 1 7,02. 83. Известно устройство для модульногоумножения в системе остаточныхсодержащее дешифраюоры, вентили,.операционную матрицу, группы элеИЛИ, ферриюовые линейки, блок храненияарифметических таблиц, логические схемыи сооювеюсювуюшие связи 1 3.Недостаток устройства - ограниченные .функциональные возможности, заключающиеся в юом, чюо модульное умножениевыполняется только в области положительных чисел.Наиболее близким к изобретению юехническим решением является устройстводля умножения в системе остаточныхклассов, содержащее входные регистры,дешифраюоры, ключи, коммутатор, выходной регистр, а также сумматор по моду 2лю два, группы элементов ИЛИ, элеменюы И и ИЛИ, причем первый и второйвходные регистры последовательно черезсооювеюсювуюшие первый и второй дешиф раюоры, первую и вторую группы элеменюов ИЛИ и первый и второй ключи подключены соответственно к первой и второйгруппам входов коммутатора, первые ивторые группы входов первого и второгодешифраторов подключены соответственноко входам первого, второго и третьего,четвертого элементов ИЛИ, выходы которых подключены к сооювеюсювуюшим вхо дам сумматора по модулю два, управляюшие входы ключей являются входамиуправления устройства, первая группавходов коммутатора подключена ко входампятого элемента ИЛИ и первым входамшестого, седьмого, восьмого, девятого идесятого элементов ИЛИ, ко вторым входам которых подключена вторая группавыходов коммутатора и входу одиннадцатого элемента ИЛИ, выход которогоподключен к первым входам первого ивторогО элеменюов И, выход пятого элеменюа ИЛИ подключен к первым входам третьего и четвертого элементов И, вторые входы первого и третьего элементов И и981990 аших элементов И второй группы и подключены к соответствующим входам группы коммутатора, выходы первого и чепвертого, второго и третьего элементов ИЛИ подключены ко входам соответственно первого и второго элементов И, выходы которых подключены ко входам пятого элемента ИЛИ, вторые входы элементов И первой группы и элементов И второй группы объединены и подключены к выходу пятого элемента ИЛИ, а выходы " подключены соответственно к первым и вторым входам соответствующих элементов ИЛИ третьей группы, входы %-го эле- мента И третьей группы (=11 ) подклн- чены к 1 -му и-му выходам соответственно первого и второго дешифраторов ( 1= 1,2Р; 1 = 1,2, Р), для которых (АВ) = А; В;, где (А и В - исходные числа, ()-искусственная форма произведения, Х -искусст венная форма операнда Х), выходы элементов И третьей группы подключены ко входам шестого элемента ИЛИ, выход ,которого подключен к первым входам элементов И четвертой и патой групп, выходы выходного регистра подключены к соответствующим входам дешифратора, выходы которого подключены ко вторым входам соответствующих элементов И четвертой группы и к входам первой группы сумматора по модулю Р, вторая группа входов которого подключена к выходам соответствующих элементов И пятой группы, вторые входы которых объединены и являютса входом константы Р устройства,. выходы элементов И пятой группь 1 и сумматора по модулю Р подключены соответственно ко входам соответсгвуюших элементов ИЛИ четвертой грудпы, выходы которых являются выходом устройства.В схеме модульного умножения прототипа используется свойство симметрии арифметической таблицы коммутатора относительно диагоналей, вертикали и горизонтали, походяших между величинами - -1 и - +1. Это и определяетР2 2возможность реализации в схеме табличного умножения только 0,25 части таблипы.Алгоритм получения результата операции определяется соотношением, если два числа А и В заданы по модулю Р вкоде табличного умножения А = ( д ) В = (рг ф) то для того, чтобы полуев чить произведение этих чисел по модулк Р, достаточно получить произведение 3второго и четвертого элементов И подключены соответственно к нулевому и единичному выходам сумматора по модулю два, а выход первого и четвертого элементов. И и соответственно второго и третьего элементов И подключены к соответствующим входам двенадцатого и тринадцатого элементов ИЛИ, выходы шестого, седьмого, восьмого, девятого, десятого, двенадцатого, тринадцатого 10 элементов ИЛИ соединены с соответствующими входами выходного регистра, выход которого является выходом устройства 2 ) .Недостаток этого устройства также ограниченные функциональные возможнос ти, заключающиеся в том, что модульное умножение выполняется только в области положительных чисел.Цель изобретения - расширение функциональных возможностей устройства 20 путем перемножения как положительных, так и отрицательных чисел.Поставленная цель достигается тем, что устройство для умножения чисел по модулю, содержащее первый и второй входные регистры, первый и второй дешифраторы,. группу элементов И, первук, вторую и третью группы элементов ИЛИ, первую и вторую группу ключей, коммутатор, пять элементов ИЛИ, первый и второй 50 элементы И, выходной регистр, причем входы первого и второго входных регистров являются информационными входами устройства, а выходы подключены соответственно ко входам соответственно первого и второго дешифраторов, выходы35 первой и второй групп первого и второго дешифраторов подключены соответственно к первым и вторым входам элементов ИЛИ первой и второй групп и ко входам40 соответственно первого, второго, третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих ключей соответственно первой и45 второй групп, вторые входы которых объединеы и являются управляюшим входом устройства, а выходы подключены соответственно к первой и второй группам входов коммутатора, выходы элементов ИЛИ третьей группы подключены к соответст50 вуюшим входам выходного регистра, со.- держит два элемента И, четыре группы элементов И, шифратор, шестой элемент ИЛИ, че 1 вертую группу элементов ИЛИ, сумматор по модулю Р ( Р-модуль, по которому работает устройство), первые р входы элементов И первой группы объединены с первыми входами соответствуюПусть Р .= 2 К(К - натуральное число), Обозначаем Р= . Оперируем 1 е с числами, лежащими в диапазоне О 4 А Р. Принимаем в качестве нуля число Р, и представляем числа в виде А = Р+ А.В принятом представлении (искусственная форма) будем иметь дело с по ложительными числами. Однако числа в интервале 0, Р ) отображают отрицательные числа, а в интервале Р ,Р- положительные. Эго показано (для Р = 6) Зф в таба. 1,Т 1 Табл В данной схеме модульного умножения:также используются свойства симметрии,:лицы коммутаторов, реализующего операцию модульного умножения, используем.Н квадрант табл. 4. Числовые значения, ЗФйрисваиваемые схемам совпадения ИЭ.и размещение входных шин коммутатора:представляются табл. 5.Таблица 5 а блиц реализующего опе Зфожения, представ 6)Матрица коммутатрапию модульногодена втабл, 2 (Р абли Известно, что (АВ) =АВ В табл. 6 указан аз Р -6 (Р - 3). акие пары чисел Т а б. анализомчае табл.нимают в О, Р и Рможно не так как умножение ет ноль, н в этом сл ет выполнена быстрее операндов А и В. В Ж 1 и 2 преобраз ид (табл. % 3 и 4). ве ен ае простым .этом слууются и прн-.тов И в четвертой группе ству двоичных разрядов .в Сумматор 27 осуществляет по модулю Р операнда вых ра 25 и значения Р, пред двоичным кодом. суллмированидиого региставленных 981990 8 равно количе" записи числа Р,ДЫ возм ых различных пкак 5= Ср2Рэлемен мен 25 ваюстовыйобшейнтову парВ ментовеменчисел определяется+ +(Р - 2).В частном случае нашего примера 5= зС + 4 = 16, где С =т(чп) 5 пК + 1) - число размещений из т тов.Для четырех пар чисел (см, табл. 6) нет необходимости корректировать результат операции, так как по значениям опе рандов А и В из табл. 5 определяется А В = АВ, Для остальных операндог (двадцати) АВ + Р = А В.На чертеже представлена блок-схема устройства.Блок-схема устройства содержит первый и второй входные регистры 1 и 2, первый и второй дешифраторы 3 и 4, первая, вторая, третья и четвертая группы элементов ИЛИ 5 - 8, первая и.вторая группы ключей 9 и 10, коммутатор 11, первая, вторая, четвертая ипятая группы элементов И12 - 16,второй, третий, четвертый, пятый и шестой элементы ИЛИ17 - 22первый и второй элементыИ 23 и 24, выходной регистр 25, шифратор 26, сумматор 27 по модулю Р,вход 28 константы Р, выход 29 устройства, управляющий вход 30 устройстинформационные входы 31 и 32 устрой ваеКоммутатор 11 представляет ма ответов, состоящую из элементов И менты И, которым присвоен одинак результат операции, объединяются выходной шиной. Количество элеме И в первой группе равно количеств операндов, для которых (А В) = А (для Р = 6 в первой группе четыр мента И, табл. 6). Количество эле И третьей группы и количество эл 0 5 о 56 55 Устройство работает следующим образом.По входным шинам 31 и 32 операнв двоичном коде поступают на входные регистры 1 и 2, с которых операн= ды чисел поступают на свои дешифраторы 3 и 4. Операнды с выходов дешифраторов 3 в унитарном коде, поступают на соответствующие элементы 5 первой и 6 второй группы ИЛИ и на соответствующие элементы ИЛИ 17 - 20.Сигнал шины 30 открывает ключи 9 и.1.0 и операнды одновременно поступают на соответствующие входы коммутатора 11, Если ) =, то элементы И 23 и.24 закрыты и выходной сигнал с пятого элемента ИЛИ 21 отсутствует. Эле ы И 13 второй группы, а 1.2 перв группы открыты. Выходной сигнал результата операции с выхода коммутатора 11через элемент И 12 первой группы, через элемент ИЛИ 7 третьей группы поступает на соответствующий вход регистра 25. Если" фу, то выходной сигналкоммутатора через открытый элемент И13 второй группы, элемент ИЛИ 7 третьейгруппы поступает на соответствующийвход регистра 25, С выхода шифратора26 операнд в двоичном коде поступаетна вторые входы элементов И 15 четвертой группы и на вторые входы сумматора 27, Если для данных Аи В(А В) = А В, то на выходе шестогоэлемента ИЛИ 22 присутствует сигнал.Этот сигнал закрывает элементы И 16пятой группы и открывает элементы И15 четвертой группы. Операнд с выходашифратора 26 через открытые элементыИ 15 четвертой группы, через четвертуюгруппу элементов ИЛИ 8 поступает навыход 29 устройства. Если для даннойпары операндов (А В) = А В + Р, тосигнал с шестого элемента ИЛИ 22 отсутствует, Операнд с выхода шифратора26 поступает на один,из входов сумматора 27, на другой вход которого черезоткрытые элементы И 16 пятой группыпо шине 28 поступает значение Рв двоичном коде. С выхода сумматора 27 опьранд (А В + Р)водР в двоичном коде,через четвертую группу элементов ИЛИ8 поступает на выход 29 устройства,9 98Таким образом, введение в состав устройства двух элементов И, двух групп элементов И, шифратора, шестого элемента ИЛИ, группы элементов ИЛИ, сумматора по модулю Р, двух групп вентилей и соответствующих связей расширяет функциональные возможности устройства, т.е. позволяет выполнить умножение по модулю в положительном и отрицательном числовом диапазоне. 3 ю % торов ( 1 = 1,2Р;= 1,2 Р), для которых (А "В ) = А "В, (где А и В- исходные числа, () - йскусственная форма произведения, Х. -искусственная форма фф операнда Х), выходы элементов третьейгруппы подключены ко входам шестого элемента ИЛИ, выход которого подклюформула изобретения Устройство для умножения чисел по модулю, содержащее первый и второй входные регистры, первый и второй дешифраторы, группу элементов И, первую, вторую и третью группы элементов ИЛИ, первую и вторую группу ключей, коммутатор, пять элементов ИЛИ, первый и второй элементы И, выхсной регистр, . причем входы первого и второго входных регистров являются информационными входами устройства, а выходы подключены ко входам соответственно первого и второго дешифраторов, выходы первой и второй групп первого и второго дешифраторов подключены соответственно к первым и вторым входам элементов ИЛИ первой и второй групп и ко входам сосл-. ветственно первого, второго, третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих ключей соответственно первой и второй групп, вторые входы которых объединены и являются управляющим входам устройства, а выходы подключены соответственно к первой и второй группам входов коммутатора, выходы элементов ИЛИ третьей группы подключены к соответствующим входам выходного регистра, о т л и ч а ю ш е е с я тем, что, с целью расширения функцио-нальных возможностей путем перемножения как положительных так и отрицательных чисел, устройство содержит два элемента И, четыре группы элементов И, шифратор, шестой элемент ИЛИ, четвертую группу элементов ИЛИ, сумматор по модулю Р (Р -модуль, по которому ра 1990 10 ботает устройство), первые входы элементов И первой группы объединены с первыми входами соответствующих элементов И второй группы и подключены ксоответствующим выходам группы коммутатора, выходы первого и четвертого,второго и третьего элементов ИЛИ подключены по входам соответственно первого и второго элементов И, выходы которых подключены ко. входам пятогоэлемента ИЛИ, вторые входы элементовИ первой группы и элементов И второйгруппы объединены и подключены к выходу пятого элемента ИЛИ, а выходыподключены соответственно к первыми вторым входам соответствующих эльментов ИЛИ третьей группы, входы и-го элемента И третьей группы (к:1. ) ) подключены к 1 -му и-му выходам со ответственно первого и второго дешифрачен к первым входам элементов И четвертой и пятой групп, вьиоды выходного регистра подключены к соответствующим входам шифратора, выходы которого под ключены ко вторым входам соответствуюших элементов И четвертой группы и квходам первой группы сумматора по мо-.дулю Р, вторая группа входов которогоподключена к выходам соответствующихэлементов И пятой группы, вторые входы которых объединены и являются вхо-,дом константы Р устройства, вьиоды элементов И патой группы и сумматора по модулю Р подключены соответственноко входам соответствующих элементовИЛИ четвертой группы, выходы которых являются выходом устройства. Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР. М 550636, кл. 0.06 Р 7/52, 1977.12, Авторское свицетельство СССР поНИ ИПИ Заказ 1 илиал ППП "Пате Тираж 731 Поцписног, Ужгороц,ул. Проектна

Смотреть

Заявка

3247220, 10.02.1981

ХАРЬКОВСКОЕ ВЫСШЕЕ ВОЕННОЕ КОМАНДНОЕ УЧИЛИЩЕ ИМ. МАРШАЛА СОВЕТСКОГО СОЮЗА КРЫЛОВА Н. И

КРАСНОБАЕВ ВИКТОР АНАТОЛЬЕВИЧ, КОРОЛЕВ АНАТОЛИЙ ВИКТОРОВИЧ

МПК / Метки

МПК: G06F 7/49

Метки: модулю, умножения, чисел

Опубликовано: 15.12.1982

Код ссылки

<a href="https://patents.su/6-981990-ustrojjstvo-dlya-umnozheniya-chisel-po-modulyu.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для умножения чисел по модулю</a>

Похожие патенты