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

(я)5 6 06 Р 7/ КОМИТЕТИ ОТКРЫТИ ГОСУДАРСТВЕННПО ИЗОБРЕТЕНИ.ПРИ ГКНТ СССР ИЕ ИЗОБРЕ ПИСА АВТОРСКОМ ВУ У СВИДЕТЕЛЬ стеме остаточных классов. Цель изобретения - уменьшение количества оборудования, Цель достигается за счет уменьшения Экста, количества блоков умножения на.константупо модулю путем введения группы элементов ИЛИ 7, элемента ИЛИ 8, элемента НЕ 10, двух блоков 9, 11 элементов И, второго 12 блока элементов ИЛИ, Сущность изобретения состоит в выполнении операции модульного умножения при помощи сокращенного числа блоков умножения на Я ЧИ- . константу за счет использования соотношения А(п)-В)аодгп=(гл-АВ)гпоба (А, В - опеи авто- ранды, и) - модуль операции), Количество может блоков умножения по модулю"сокращено с маши-(56) Авторское свидетельство СССРВ 1187161, кл. 6 06 Р 7/49, 1983.Авторское свйдетельство СССР1 ч) 1617439, кл. 6 06 Е 7/72, 1988(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИСЕЛ ПО МОДУЛЮ(57) Изобретение относится к облаетматики и вычислительной техники ибыть использовано в вычислительныхнах и устройствах, функционирующи ЧИзобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных мащийах и устройствах, функционирующих в системе остаточных классов.Известно устройство (аналог) для умножения в системе остаточных классов, содер.: жащее входные и выходной регистр, дешифраторы, группы ключей, группу узлов табличного;формирования разрядов результата, группы элементов И, сумматор по модулю Р, сумматор по модулю два, элементы И и ИЛИ. Недостаток устройства- большое. количество используемого оборудования,Близким по технической сущности (аналогом) к предлагаемому изобретению является устройство, которое содержит. первый и второй входные регистры, дешифраторы, группы элементов ИЛИ, группы элементов енты И и ИЛИ, табличный вычислиифратор, выходной регистр, Недоустройства - большое количествозуемого оборудования,Наиболее близким по технической сущности (прототипом) к изобретению является устройство, которое содержит группу блоков умножения на константу по модулю, дешифратор, группу блоков элементов И, блок элементов ИЛИ.Недостаток прототипа - большое количество блоков умножения на константу по модулю, причем их число существенно зависит от модуля операции. Также число этих блоков тесно связано с количеством блоков элементов И; входящих в группу. Это приводит к увеличению количества элементов И, необходимых для реализации устройства.соединен с выходом второго блока элементов И, а выход является выходом устройства, вход преобразователя кода соединен с выходом первого блока элементов ИЛИ, а . выход - с первым входом второго блока элементов И.Сущность изобретения состоит в следующем, Рассмотрим табл. 1, в которой отражены результаты операции А В(аоб 5) (А, В - операнды),Отметим следующую закономерностьпри А либо В равном нулю А В(аоб 5)=0, при В=1 А В(аоб 5)=А, следовательно, необходимо реализовать три строки при В.=2, 3, 4, Однако можно использовать соотношениеА(а-В)аоб а=(а - А В)аоб п 1, где а - модуль. При этом для реализации устройствадостаточно одного. блока умножения на константу по модулю, Изобразим в табл; 2 результат его работы для В=2(А - результат)./ 40 45 Цель изобретения - уменьшение количества оборудования.Поставленная цель достигается тем, что в устройство, содержащее дешифратор, группу блоков элементов И и первый блок 5 элементов ИЛИ, группу блоков умножения на константу по модулю, причем вход второго сомножителя устройства соединен с вторым входом первого блока элементов И группы и с входами блоков умножения на 10 константу по модулю группы, выход К-го (К=1 - (гп)/2, а - значение модуля) блока.умножения на константу по модулю группы , соединен с. вторым входом (К+1)-го блока элементов И группы, выходы которого сое динены с соответствующими входами первого блока элементов ИЛИ, введены группа элементов ИЛИ, элемент ИЛИ, элемент НЕ, два блока элементов И,.второй блок элементов ЙЛИи преобразователь обратного кода 20 по модулю, причем вход первого сомножителя устройства соединен с входом дешифратора, выходы которого, кроме младшего, соедийены попарно с первыми и вторыми входами элементов ИЛИ группы, выходы ко торых соединены соответственно с первыми входами блокьв элементов И группы,а - 1выходы ( - + 1)-е дешифратора (п 1 - мо 2дулъ устройства) (1=1, - ) соединены са - 1 302соответствующими 1-ми входами элемента ИЛИ, выход которого соединен с вторым входом второго блока элементов И, а через. элемент Н Е с вторым входом первого блока . элементов И, первый вход которого соединен с выходом первого блока элементов ИЛИ, а выход - с первым входом второго блока элементов.ИЛИ, второй вход которого В общем случае потребуется (п 1-3)/2блока умножения на константу по модулюНеобходимо также отслеживать, в первойили второй половине диапазона находитсяоперанд В. Если 0 ( В-- (ув =:0 ), тои - 1работа устройства происходит при помощисуществующих блоков умножения на константу по модулю (если а,=5, то один блок),а+1При -В а (ув =1),согласно соотношению.и результатам таблицы 1 необходимо произвести инверсию промежуточного результата операции по модулю уст-ройства, выполняемую при помощи преобразователя кода, Изобразим в табл. 3результат его работы.Коммутация операнда В отмечена в таб- .лице 1. Одновременно с сокращением блоков умножения на константу по модулюпроисходит и уменьшение числа блоков эле-,ментов И,Возможность достижения положительного эффекта от использования данногоизобретения состоит в уменьшении количества оборудования ввиду уменьшения количества блоков умножения на константу помодулю,На чертеже представлена структурнаясхема устройства, где: 1 - вход второго сомножителя устройства, 2 - группа блоковэлементов И, 3 - группа блоков умноженияна константу по модулю, 4 - первый блокэлементов ИЛИ, 5 - вход первого сомножителя устройства, 6- дешифратор, 7- группаэлементов ИЛИ, 8- элемент ИЛИ,9- второйблок элементов И, 10 - элемент НЕ, 11 первый блок элементов И, 12 - второй блокэлементов ИЛИ, 13 - выход устройства, 14 преобразователь кода. Вход 1 второго сомножителя устройства соединен с вторым входом первого блока элементов И 2 группы и с входами блоков . умножения на. константу по модулю 3 группы, выход К-го (К=1-(гп)/2, а - значение модуля) блока умножения на константу по модулю 3 группы соединен с вторым входом (К+1)-го блока элементов И 2 группы, выходы . которых. соединены с соответствующими: входами первого блока 4 элементов ИЛИ, вход 5 первого сомножителя устройства соединен с входом дешифратора 6, выходы которого, кроме младшего, соединены попарно с первыми и вторыми. входами элементов ИЛИ 7 группы, выходы .которых соединены соответственно с первыми вхо-, дами блоков элементов И 2 группы, выходы а - 1) соединены с соответствующими 1-ми входами элемента ИЛИ 8, выход которогосоединен с вторым входом второго 9 блока элементов И, а через элемент НЕ 10 - с вторым входом первого блока 11 элементов И, первый вход которого соединен с выходом первого блока 4 элементов ИЛИ, а выход - с первым входом второго блока 12 элементов ИЛИ, второй вход которого соединен с выходом второго блока 9 элементов И, а. выход является выходом 13 устройстаа, вход преобразователя 14 кода соедийен с выходом первого блока 4 элементов ИЛИ, а выход - с первым входом второго блока 9 элементов И.Устройство работает следующим образом. Сомножитель В с входа 5 поступает на вход дешифратора 6. При В=О на выходах,кроме младшего, дешифратора. 6 нулевые значения. Следовательно, все блоки 2 эле- ментов И закрыты, и на их выходах, а следовательно и на выходе первого блока 4 элементов ИЛИ; нулевое значение; которое 25в виде нулевого результата операции поступает, на выход 13 устройства. При .Ос а - 1В- сигнал с выхода дешифратора26 через соответствующий элемент группы 30 элементов ИЛИ 7 открывает соответствующий.значению В блок элементов И 2. Сомножитель А поступает со входа 1 устройства на.входы блоков 3 умножения на константу по модулю и на второй вход первого блока 2 35 элементов И группы. В блоках 3 умножения формируются соответствующие произведеа - 1ния А =А К(К=2- ) по модулю. Через2открытый блок 2 элементов И группы соответствующее произведение Апоступит на вход первого 4 блока элементов ИЛИ и с его выхода (сигнал на выходе элемента ИЛИ 8.; отсутствует, ув=О) на вход первого 11 блока. элементов И, на второй вход которого по ступает сигнал с выхода элемента НЕ 10 и далее через второй блок 12 элементов ИЛИ . нр выход 13 устройства. При А=О значение А (см. табл, 2) также равно нулю, что приводит к формированию нулевого произведения.Если -В (а - 1(ув =1), тоа+12работа устройства происходит, как и в предыдущем случае, но сигнал на выходе эле мента ИЛИ 8 присутствует, поэтому промежуточный результат операции поступает на вход преобразователя 14 кода и значение результата модульного умножения через открытый второй 9 блок элементов И и далее через второй 12 блок элементов ИЛИ поступает на выход 13 устройства,Рассмотрим примеры конкретного выполнения операции при а=5.П р и м е р 1. Пусть необходимо определить результат модульного умножения для А=2, В=2 (А, В - операнды).На вход дешифратора 6 поступает число В=010, на вход 1 -число А=010. Сигнал на выходе элемента ИЛИ 8 отсутствует (ув=О), Сигнал с второго выхода дешифратора 6 поступает на второй вход первого элемента ИЛИ 7 группы, которая в этом случае состоит из двух элементов. С выхода первого элемента ИЛИ 7 сигнал поступает на первый вход блока умножения 2 на константу по модулю (см. табл. 2), на другой вход которого поступает А=010. Результат операции Ак Ваоб 5=100 поступает через первый блок 4 элементов ИЛИ, первый блок 11 элементов И, второй блок 12 элементов ИЛИ на выход 13 устройства.П р и м е р 2, Пусть необходимо определить результат модульного умножения для А=2, В=4 (А, В - операнды),В этом случае путь операнда А аналогичен первому примеру. Сигнал на выходе элемента ИЛИ 8 присутствует, Сигнал с четвертого выхода дешифратора 6 поступает на второй вход второго элемента ИЛИ 7 группы, с выхода которого поступает на второй вход первого блока 2 элементов И группы,На выходе первого 4 блока элементов ИЛИ будет число 010, которое поступит на вход преобразователя 14 кода, с выхода которого (см; табл. 3) число 01 1. через открытый второй 9 блок элементов И и второй 12 блок элементов ИЛИ поступит на выход 13 устройства,Рассмотрим, какой выигрыш достигается при реализации данного изобретения. Прототип содержит (а - 2) блоков умножения на константу по модулю, изобретение- (а)/2. Следовательно вьигрыш Я составита - 28=2 - , при а 1 й-+2.а - 3Формула изобретения Устройство для умножения чисел по модулю, содержащее дешифратор, группу блоков элементов И и первый блок элементов ИЛИ, группу блоков умножения на константу по модулю, причем вход второго сомножителя устройства соединен с первым входом первого блока элементов И группы и входами блоков умножения на константу по модулю группы, выход К-го (К=1-(а)/2, а - значение. модуля) блока умножения на1716511 Таблица 2 Таблица 3 20 константу по модулю группы соединен с первым входом (К+1)-го блока элементов И группы, выходы которых соединены с соответствующими входами первого блока элементов ИЛИ, вход первого сомножителя устройства соединен с входом дешифратора, о т л и ч а ю щ е е с я тем, что, с целью уменьшения количества оборудования в него введены группа элементов ИЛИ, элемент ИЛИ, элемент НЕ, два блока элементов И, второй блок элементов ИЛИ и преобразова. тель обратного кода по модулю, причем выходы дешифратора, кроме младшего, соединены попарнос первыми и вторыми входами элементов ИЛИ группы, выходы которых соединены соответственно с вторыми входами .блоков элементов И группы,щ - 1) соединены с соответствующими 1-ми 5 входами элемента ИЛИ, выход которого соединен.с первым входом первого блока элементов И и через элемент НЕ - с первым входом второго блока элементов И, второй вход которого соединен с выходом первого 10 блока элементов ИЛИ и входом преобразователя обратного кода по модулю, выход которого соединен с вторым входом первого блока элементов И, выход которого соединен с первым входом второго блока элемен тов ИЛИ, второй вход которого соединен свыходом второго блока элементов И, а выход - с выходом результата устройства.Таблица 1