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

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

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

ZIP архив

Текст

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических Республик(22) Заявлено 021179 (21) 2838013/18-24с присоединением заявки йо(51 М. Кл.з С 06 Г 7/72 Госуяярственный комитет СССР по дедам изобретений и открытий(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ И СЛОЖЕНИЯ ЧИСЕЛ ПО МОДУЗПО Изобретение относится к вычислительной технике.Известно табличное устройство для модульного умножения в системе остаточных классов, содержащее дешифраторы, вентили, ключи, матрицу, элементы ЙЛИ, логические схемы 1.Недостаток известного устройства состоит в ограниченных функциональных воэможностях.Наиболее близким к предлагаемому является устройство для умножения в системе остаточных классов, содержащее входные регистры, дешифраторы, ключи, коммутатор, выходной регистр, 15 а также сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ, пр чем первый и второй входные регистры последовательно через соответствующи первый и второй дешифраторы, пер вую и вторую группы элементов, ИЛИ н первый и второй ключи подключены соответственно к первой и второй группам входов коммутатора, первые и вторые группы выходов первого и второго дешифраторов подключены соответствен-, но ко.входам первого, второго, третьего и четвертого элементов ЙЛИ, выходы которых подключены к соответствующим входам сумматора по модулю З 0 два, управляющие входы ключей являются входами управления устройства, первая группа выходов коммутатора подключена ко входам пятого элементаИЛИ и первым входам шестого, седьмого, восьмого, девятого и десятого элементов ИЛИ, ко вторым входам которых подключена вторая группа выходовкоммутатора и входы одиннадцатогоэлемента ИЛИ, выход которого подключен к первым входам первого н втОрого элементов И,.выход пятого элемента ИЛИ подключен к первым входам третьего и четвертого элеМентов И, вторые входы первого и третьего элементов И и второго и четвертого элемен"тов И подключены соответственно кнулевому и единичному выходам сумматора по модулю два, а выходы первогои четвертого элементов И и соответственно второго и третьего элементовИ подключены к соответствующим входам двенадцатого и тринадцатого элементов ИЛИ, выходы шестого, седьмого, восьмого, девятого, десятого,двенадцатого и тринадцатого элементов ИЛИ соединены с соответствующимивходами выходного регистра, выходкоторого является выходом устройства 2).Недостатком указанного устройстваявляются ограниченные функциональныевозможности, заключающиеся в невозможности выполнения данным устройством операции модульного сложения чисел, представленных в специальномкоде умножения. Этот недостаток обусловлен тем, что для выполнения операции модульного сложения операндовчисел, представленных в специальномкоде умножения, недостаточно использовать только 0,25 части арифметической таблицы модульного умножения,Цель изобретения - расширениефункциональных воэможностей за счетвыполнения операции сложения.Поставленная цель достигаетсятем, что устройство, содержащее входные регистры, дешифраторы, первуюгруппу элементов И, первый коммутатор, сумматор по модулю два, группыключей, группы элементов ИЛИ, элементы ИЛИ, выходной регистр, приэтом первый и второй входные регистры последовательно через соответствующие первый и второй дешифраторы,первую и вторую группы элементов ИЛИ,первую и вторую группы ключей подключены ко входам первого коммутатора, первые и вторые группы выхоцовпервого и второго дешифраторов подключены соответственно ко входампервого и второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, управ. ляющие входы ключей первой и второйгрупп соединены между собой и являются управляющим входом устройства, нулевой и единичный выходы сумматора по модулю два соединены соответственно. с первыми входами пер"вого, третьего и второго, четвертогоэлементов И первой группы, выходыпервого и четвертого элементов И.первой группы соединены со входамипятого элемента ИЛИ, а.выходы второго и третьего элементов И первойгруппы соединены со входами шестогоэлемента ИЛИ, вторые входыпервогои второго элементов И первой группысоединены между собой и с выходомседьмого элемента ИЛИ, вторые входытретьего и четвертого элементов Ипервой группы соединены между собойи с. выходом восьмого элемента ИЛИ,содержит вторую, третью, четвертую ипятую группы элементов И, третьюгрЖну элементов ИЛИ, шесть элементов И, два элемента Й-НЕ, второйкоммутатор, третью группу ключей,причем первая и вторая группы выходов первого коммутатора подключенысоответственно к первым входам элементов И четвертой и пятой групп,выходы 1 -ых иР)-ых ключей первой и второй групп (1 =1,2. ,Р;Р - Модуль) подключены ко входам соответствующих клюЧей третьей группы, выходы которых подключены ко входам второго коммутатора, первая и вторая группы Р(2 выходов которого псдключены к первым Рвходам соответственно седьмого и восьмого элементам ИЛИ, выходы 1 -ых и (Р-у)-ых элементов И четвертой группы подключены соответственно к первым .и вторым входам элементов ИЛИ третьей группы и ко вторым -4(2 входам седьмо го и восьмого элементов ИЛИ, выходы1-ых и (Р)-ых элементов И пятой группы подключены соответственно к третьим и четвертым входам элементов ИЛИ третьей группы и к третьим 15 Ч)Ъ. входам седьмого и восьмого элементов ИЛИ,1 -2) -ые и ( Р)-ые выходы второго коммутатора подключены соответственно к пятым и шестым входам соответствующих элементов ИЛИщ третьей группы, выходы которых подключены. к первым Р входам выходного регистра, первые входы элементов И второй и третьей группы объединеныи подключены соответственно к выходампятого и шестого элементов ИЛИ, управляющие входы ключей третьей группы объединены и подключены к выходупервого элемента И, к первому входувторого элемента И, ко вторым входампервого и четвертого элементов И, со- ЗО ответственно, второй и третьей групп,вторые входы вторых элементов И вто-.рой и третьей, и пятой групп объединены и являются "Умножение" устройства, вторые входы третьих элементов И 35 второй и третьей групп и первый входтретьего элемента И объединены и подключены к выходу четвертого элементаИ; первый вход которого подключен кпервому входу пятого элемента И ко що второму входу первого элемента И иявляется входом ПСложение" устройства,вторые входы четвертого элементаИ второй группы и первого элементаИ третьей группы объединены и подключены к выходу третьего элементаИ, второй вход которого объединен совторыми входами элементов И четвертой группы и подключен к выходу пятого элемента И, второй вход которого подключен к нулевому выходу сум- О матора по модулю два, выходы первого, второго, четвертого элементов Ивторой группы и выход третьего элемента И третьей группы подключеныко входам девятого элемента ИЛИ, вы ход которого подключен к первому входу первого элемента И-НЕ, выходытретьего элемента И второй группы ипервого, второго, четвертого элементов И третьей группы подключены ко що входам десятого элемента ИЛИ, выходкоторого подключен к первому входувторого элемента И-НЕ, выходы первого и второго элементов И-НЕ подключены соответственно к; Р+1)-му и Р+2)- му входам выходного регистра, вторые865999 В схеме модульного умножения используются свойства симметрии арифметической таблицы относительно левой и правой диагоналей, вертикали и горизонтали, проходящих между чис.", лами Рн Р+142В табл.1 показана реализация выполнения операции модульного умно- кения для Р.=11.Таблица 1 а 145 1 б 12 2 7 10 8 9 8 9 5,7 2 5 10 3 10 1 1 2 2 2 34 5 б 4 6 8 10 1 10б б 9 1 4 7 3 3 4 4 5 5 б 6 7 7 8 8 9 9 10 10 9 2 8 1 5 10 4 9 3 6 1 7 2 8 3 3 10 б 2 9 10 5 1 8 4 5 2 10 7 4 7 5 3 1 10 9 8 7 б 5 Продолжение табл, 2 5 4 3 2 1 1 1 1 1 1 б 7 8 9 10 Алгоритм получения результата операции модульного умножения определяется следующим образом. Если два числа А и В заданы по основанию Р.в коде табличного умножения А=Я, ал)В 17) то для того что бы получить произведение этих чисел по модулю Ъ 1, достаточно получить произведение оц 6 мод Р) в коде табличного умножения и инвертировать его индекс 44)" в случае, если ф отлично от у , где р,О, еслиОО 41, если - "- С 1 Р -4Р+ 5Ь схеме модульного сложения используются свойства симметрии арифметической таблицы модульного сложе . ния относительно левой диагонали. Это определяется коммутативностью операции сложения.В табл.3 показана реализация вполнения операции модульного слок ния для Р =11..Таблица 2 б 2 3 н- евходы первого и второго элементовИ-НЕ объединены и подкюпочены к выходу второго элемента И, первый входшестого элемента И подключен к выходу четвертого элемента ИЛИ, вторые входы второго и шестого элементов И объединены и подключены к выходу второго элемента ИЛИ, выход шестого элемента И подключен ко второму входу четвертого элемента И,Симметричность относительно левойДИаГОНаЛИ ОПРЕДс 2424 е 24;Я КОММУтатИВностью операции умножения, симмет- З 5ричность отсносительно правой диагонали определяется тем, чтоО"3 ИР-) = с 3 (модРСимметричность относительно вертикали и горизонтали определяется тем,что сумма симметричных чисел кратнаР, т.е.М +Ю Ж-М =-О(яоаР);Р,+Р -а;)-=о(подР)Это и определяет возможность реализации в схеме табличного умнокениятолько 0,25 части табл.1,Операция модульного. умножения выполняется в специальном коде умножения, представленном в табл,2. 4 2 Э.885999 Таблица 3 2 3 7 8 3 4 6 7 5 6 6 7 910 7 8 98 9 10 01 2 0 ность реалиложения 25 и условии, ожения выде умножерантов ариф 1 Ч Е н Это и определяет возмоэации в схеме табличноготолько 0,5 части табл.З пчто операция модульного сполняется в специальном кния.Определены номера квадметической таблицы:На чертеже представлена блок-схемапредлагаемого устройства.Устройство содержит входные регистры 1, дешифраторы 2, первая итретья группы элементов ИЛИ 3,4 и 5,первый, второй, третий, четвертый,пятый, шестой, седьмой, восьмой, девятый и десятый элементы ИЛИ 6-15,первая, вторая и третья группы ключей 16, 17 и 18, первый и второйкоюутаторы 19 и 20, первая, вторая,третья, четвертая и пятая группы элементов И 21-25, сумматор 26 по модулю два, первый, второй, третий, четвертый, пятый и шестой элементы И27-32, первый и второй элементы И-Н33 и 34, выходной регистр 35. 50Первый коммутатор 19 определяетрезультат модульного умножения табл,1и операции модульного сложения для 11 й ф квадрантов табл.З (т.е. для.30 0 р =О, фп =1,=1)В зависисти от кода операции (умноженияи и "сложения) первый коммутатор 19определяет результат модульного умножения или сложения, т,е. первыйкоммутатор совмещает выполнение двухопераций. 60Первая и вторая группы выходовпервого коммутатора 19 определяютрезультат модульного умножения, причем первая группа выходов определяет значения 1-: .ф - , а вторая Р 112-. 65 г-;Р.;- . Третья и четвертая группы вы-.ходов первого коммутатора 19 определяют результат модульного сложения для Ц и 111 квадрантов табл.З,причем третья группа, выходов определяет значение -; Р -2 , а чет,вертая Р 1 +/2-; Р,; -1.Величины 0 и Р не кодируются,так как при умножении на этивеличины результат равен нулю,и в этом случае операция выполняется быстрее простым аналйзом операндов, при сложении с этими величинами значение второго операнда неизменяется, он и определяет результат операции, при определении результата операции со второго коммутатора ( 1, 01 квадранты) выходная шина,объединяющая элементы И, которымприсвоен результат модульного сложения О и Р,; правая диагональ табл,З),подключается непосредственно к выхо"ду устройства. При необходимостизначения 0 и Р 1 могут быть такжевключены в табл,2,Второй коммутатор 20 определяет результат модульного сложения дляи Щ квадрантов (табл.З) . Перваягруппа выходов второго коммутатораопределяет значения -;Рф, а вторая Р+4(2-;Р-Первый 19 и второй 20 коммутаторы 1 матрицы ответов) представляютнабор элементов И. Количество элеметов И каждого коммутатора равно(Р -1)Ц, Элементы И, которым присвоен одинаковый результат операции,объединяются выходной шиной. В коммутаторах осуществляется операцияв унитарном коде. Результат операции также представляется в унитарном коде. Количество выходных шинвторого коммутатора 20 равно Р,он определяет результат модульного20 25 35 40 50 55 б 0 65 сложения дляиквадрантов. Первая группа выходов объединяет шины, которым присвоен результат модульного сложения -;Р-(2, а вторая группа Р 1+ (2-;Р 1- 1Количество выходных шин первого коммутатора 19 равно 2 (Р), так как коммутатор 19 определяет результат модульного умножения (первая и вторая группы выходов определяют, соответственно, значения ЬР-М 2 ,и 0+/2-;р,для умножения) и, результат модульного сложения для, и 1 квадрантов (третья и четвер"ая группы выходов определяют, соответственно, значения 1 + Р-.1 /2 и Р+ Ц 2-; Р,; - 1 для сложения ).Таким образом, каждому элементу И коммутатора 19 присваивается двазначения: результат модульного умножения и результат модульного сложения (дляи ч квадрантов).Количество элементов первой и второй, и третьей групп элементов ИЛИ 3, 4 и 5 равно Р 1 в 1 2 в каждой группе. Количество элементов И четвертой 24 и пятой 25 групп элементов И равно Р 1 -1 в каждой группе.Выход элемента ИЛИ 14 определя= ет значение 3" =1, а выход элемента ИЛИ 15 -=О.Устройство работает следующим образом.Первый режим работы - определение результата модульного умножения. На входные регистры 1 заносятся операнды и последовательно через дешифраторы 2, группы элементов ИЛИ 3 и 4 и,группы ключей 16 и 17 поступают на коммутатор 19. Ключи 16 открываются сигналом с управлякщего входа устройства. Одновременно присутствует сигнал фумножение" устройства. Выходной сигнал коммутатора 19 через один из элементов И 25 пятой группы поступает на один из шести входов определенного элемента ИЛИ 5 третьей группы. С выхода этого элемента сигнал поступает на соответствующий вход выходного регистра 35. Элементы 12, 13, 21, 10, 11, 22, 23, 14, 15, 33 и 34 служат для опрецеления индекса у в записи результата модульной операции. Коммутатор 20 закрыт, так как отсутствует сигнал "Сложение" устройства.Второй режим работы - определение результата операции модульного сложения дляи Я квадрантов таблицы модульного сложения ( т.е.Я,=ур -"О и фС= р =1). В этом случае сигнал "Сложение" устройства присутствует. Коммутатор 20 закрыт, так как отсутствует сигнал с единичного выхода сумматора 26 по модулю иваДО+фр" фО(и 03)элемент И 27 закрыт. и, следовательно, ключи 18 третьей группы закрыты. Группа элементов И 25 пяток группы закрыта (отсутствие сигнала "Умножение" устройства). Выходной сигнал коммутатора 19 по третьей и четвертой группам выходов (по одной из шин этих групп) через один из элементов И 24 четвертой группы, элемент ИЛИ 5 третьей группы поступает на выходной регистр 35.Третий режим работы - определение результата операции модульного сложения для 1 иквадрантов таблицы модульного сложения (т.е. для 7 с - О=1 и " =1, Я =О) . Сиг- нал фСложение" устройства присутствует, а сигнал "Умножением устройства отсутствует. Коммутатор 20 открыт, а на выходных шинах коммутато ра 19 отсутствует выходной сигнал, так как элементы И 24 и 25 четвертой и пятой групп закрыты. Ключи 18 третьей группы открытына выходе элемента И 27 присутствует сигнал) и коммутатор 20 определяет результат модульного сложения дляи П квадрантов. Для=1,=О значение индекса у в записи результата модульного сложения определяется с выходов элементов ИЛИ 14 и 15. Для 0 с=О, Я=1 значениеопределяется ийвертированием выходных сигналов элементов ИЛИ 14 и 15.Таким образом, изобретение совмещает выполнение операций модульного умножения и сложения в коде табличного умножения (табл.2), При этом таблица реализующая операцию умножения, может быть конструктивно уменьшена в четыре раза, а таблица, реализующая операцию сложения - в два раза.Если для реализации операции умножения и сложения без применения специального кода умножения необходимо 2 (Р-Ц элементов табл.1 и 3, то с применением кода (табл.2). в (Р 1-Р 2 элементов таблиц. При применении специального кода умножения сокращается также количество элементов входных, выходных регистров и дешифраторов.Формула изобретенияУстройство для умножения и сложения чисел по модулю, содержащее первый и второй входные регистры, дешифраторы, первую группу элементов И, первый коммутатор, сумматор по модулю два, группы ключей, группы элементов ИЛИ, элементы ИЛИ, выходной регистр при этом первый и второй выходные регистры последовательно через соответствующие первый и второйдешифраторы, первую и вторую группыэлементов ИЛИ, первую и вторую группы ключей подключены ко входам первого коммутатора, первые и вторыегруппы выходов первого и второго де 885999шифраторов подключены соответственноко входам первого и второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулюдва, управляющие входы ключей первойи второй групп соединены между собойи являются управляющим входом устройства, нулевой и единичный выходысумматора по модулю два соединены соответственно с первыми входами первого, третьего и второго, четвертогоэлементов И первой группы, выходы первого и четвертого элементов И первой группы соединены со входами пятого элемента ИЛИ, а выходы второгои третьего элементов И первой группы 15соединены со входами шестого элемента ИЛИ, вторые входы первого и второго элементов И первой группы соединены между собой и с выходом седьмого элемента ИЛИ, вторые входы третье-.20го и четвертого элементов И первойгруппы соединены между собой и с выходом восьмого элемента ИЛИ, ол и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет выполнения операции сложения, оно содержит вторую,третью, четвертую и пятую группы элементов И, третью группу элементовИЛИ, шесть элементов И, два элемента И-НЕ, второй коммутатор, третьюгруппу ключей, причем первая и вторая группы выходов первого коммутатора подключены соответственно к первым входам элементов И четвертой ипятой групп, выходы 1 -ых и (Р)-ыхключей первой и второй групп=1,2Р; Р - модуль) подключены ко,входам соответствующих ключей третьей группы, выходы которых подключены ко входам второго коммутатора, 40первая и вторая группы Р2 выходов которого подключены к первым4 ф входам соответственно седьмого и восьмого элементов ИЛИ, выходы ,1 -ых иР)-ых элементов И 4четвертой группы подключены соответственно к первым и вторым входам элементов ИЛИ третьей группы и ко вторым Р 2 входам седьмого и восьмого элементов ИЛИ выходыых иОР- Ф)-ых элементов И пятой группыподключены соответственно к третьими четвертым входам элементов ИЛИтретьей группы и к третьим Рвхода седьмого и восьмого элементовИЛ, ( Ф -2)-ые и ( Р-)-ые выходыв рого коммутатора подключены соответственно к пятым и шестым входам соответствующих элементов ИЛИ третьейгруппы, выходы которых подключены к первым Р входам выходного регистра,первые входы элементов И второй и третьей группы объединены и подключенысоответственно к выходам пятого и шестого элементов ИЛИ, управляющие входы ключей третьей группы объединеныи подключены к выходу первого элемента И, к первому входу второго элемента И, ко вторым входам первого и четвертого элементов И, соответственно,второй и третьей групп, вторые входывторых элементов И второй и третьей,и пятой групп объединены и являются"УмнЬжение" устройства, вторые входытретьих элементов И второй и третьейгрупп и первый вход третьего элемента И объединены и подключены к выходучетвертого элемента И, первый входкоторого подключен к первому входу пятого элемента И, ко второму входу первого элемента И и является входом"Сложение" устройства, вторые входычетвертого элементаИ второй группыи первого элемента И третьей группыобъединены и подключены к выходу третьего элемента И, второй вход которого объединен со вторыми входамиэлементов И четвертой группы и подключен к выходу пятого элемента И, второй вход которого подключен к нулевому выходу сумматора по модулю два,выходы первого, второго, четвертогоэлементов И второй группы и выходтретьего элемента И третьей группыподключены ко входам девятого элемента ИЛИ, выход которого подключен кпервому входу первого элемента И-НЕ,выходы третьего элемента И второйгруппы и первого, второго, четвертого элементов И третьей группы подключены ко входам десятого элемента ИЛИ,выход которого подключен к первомувходу второго элемента И-НЕ, выходыпервого и второго элементов И-НЕ подключены соответственно кР+1) -му и( Р+2) -му входам выходного регистра,вторые входы первого и второго элементов И-НЕ объединены и подключенык выходу второго элемента И, первыйвход шестого элемента И подключен квыходу четвертого элемента ИЛИ, вторые входы второго и шестого элементов И объединены и подключены к выходу второго элемента ИЛИ, выход шес 1 того элемента И подключен ко второму входу четвертого элемента И.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРР 550636, кл. С 06 Г 7/52, 1977.2. Авторское свидетельство СССРпо заявке В 2675156/18-24,кл. 6 06 Г 7/49, 1978 (прототип)

Смотреть

Заявка

2838013, 02.11.1979

ВОЙСКОВАЯ ЧАСТЬ 11284

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

МПК / Метки

МПК: G06F 7/72

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

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

Код ссылки

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

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