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

СОЮЗ СОВЕТСКИХСОЦИАЛ И СТИЧ Е СКИХРЕСПУБЛИК 7059 А 7 52 5 Ц 5 (э ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ Ре Релт(71) Научно - исследовательский институт бытовой радиоэлектронной аппаратуры (72) Л.В. Вариченко и В.И. Кодров (53) 681.325 (088.8)(56) Авторское свидетельство СССР Ь 1179322, кл. 8 06 Е 7/52, 1984, (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ДВУХ ЧИСЕЛ(57) Изобретение относится к вычислительной технике и радиотехнике и может быть .использовано в устройстве цифровой обработки сигналов, например, изображений и в устройствах, работающих в системе остаточных классов, а также в системах кодирования, принцип действия которых базируется на теории полей Галуа, Цель изобретения - расширение функциональных возможностей за счет обеспечения умножения двоичных целых чисел по трем взаимно простым модулям: М 1 = 2", М 2 = 2 - 1, Мз = 2" + 1. Устройство содержит регистры множимого 1 и множителя 2; блок 3 формирования частичных произведений, регистры младших 4. и старших 5 разрядов произведения, элемент НЕ 6, первую 7 и вторую 8 группы элементов И, и - разрядный сумматор 9, блок 10 коррекции результата, блок 11 синхронизации, блок 14 анализа сомножителей, блок 15 приведения по модулю, (и+ 1)-разрядный мультиплексор 12 и элемент ИЛИ 13. 3 ил.Изобретение относится к вычислительной технике и радиотехнике и может бытьиспользовано в устройствах цифровой обработки сигналов (в частности, для цифровойобработки изображений) и в устройствах, работающих в системе остаточных классов, атакже в системах кодирования, принципдействия которых базируется на теории полей Галуа.Целью изобретения является расширение функциональных возможностей за счетобеспечения умножения двоичных чисел потрем взаимно простым модулям: М 1 = 2 П,М 2 2" - 1, Мз = 2" + 1.На фиг, 1 представлена структурнаясхема устройства для умножения двух чисел; на фиг. 2 - структурная схема блокаанализа сомножителей; на фиг,3 - структурная схема блока приведения по модулю.Устройство для умножения двух чисел(фиг, 1) содержит регистры множимого 1 имножителя 2, блок 3 формирования частичных произведений, регистры младших 4 истарших 5 разрядов произведения; элементНЕ 6, первую 7 и вторую 8 группы элементовИ, п-разрядный сумматор 9, блок 10 коррекции результата, блок 11 синхронизации,, элементы НЕ 17, 18., элемент ИСКЛЮЧАЮ, ЩЕЕ ИЛИ 19,элементы И 20 - 23, и-разрядный мультиплексор 24, элементы ИЛИ 25 -27.Блок 15 приведения по модулю (фиг. 3); содержит элемент НЕ 28, элемент ИЛИ 29,и-разрядные мультиплексоры 30, 31, и-разрядные сумматоры 32, 33, элементы И 34 -37.Работа устройства для умножения двухчисел в зависимости от уровней сигналов навходах выбора режима возможна в одном изтрех режимов: при "1" на входах "Режим 1"и "Режим 2" устройство производит умно"жение по модулю М 1 = 2 П; при "О" на входе"Режим 1" и "1" на входе "Режим 2" устройство производит умножение по модулю М 2-2" 1; при "0" на входах "Режим 1" и"Режим 2" устройство производит умножение по модулю Мз = 2.,Устройство работает следующим образом.Разряды а 1, , ал множимого и Ь 1, , Ьпмножителя поступают на регистры 1 и 2соответственно, Далее они передаются навходы сомножителей блока 3, на выходахкоторого формируется. результат обычногоумножения, представляющий. собой число с2 п-двоичными разрядами, По сигналу приема младшие разряды заносятся в регистр4, а старшие в регистр 5. В режиме вычислений по модулю М 15 =2" на выходах элементов И первой группы появляются сигналы "0", Тогда на выходах 01 Оп и в разрядно мультиплексора 12 появляются младшие разряды произведения, а на выходах элемента ИЛИ 13 и элементов И второй группы, начиная со второго Оп+1, , 02 п - старшие разряды.В режиме вычисления по модулю М 2 = =2" 1 на выходах элементов И первой группы появляются сигналы "1", соответствующие старшим разрядам произведения, а на выходах элементов И второй группы сигналы "0". Сумматор 9 производит сложение 10 15 хО по модулю Мз соответствует результату обычного умножения. При умножении любых чисел а 1(а= 1,Мз) и Ь(Ь= 1, Мз) иэ кольца Е алгоритм умножения следующий: сначала производится обычное умножение, затем инвертированные старшие разряды произведения с младшими, Если в результате сложения перенос из старшего разряда равен единице, то результат корректируется прибавлением единицы, если перенос из старшего разряда равен нулю - к результату прибавляется двойка.В режиме умножения по модулю Мз = =2" + 1 устройство работает следующим образом.На входах элементов И,.второй группы присутствуют сигналы ".0", что приводит к 45 50 55 чисел, образованных младшими и старшимиразрядами. За время двух сложений (сложе 20 ние слагаемых и прибавление переноса) навыходах 01, , Оп сумматора 9 формируются разряды умножения по модулю М 2 = 2" ,После коррекции в блоке 10 через вторыевходы и - разрядного мультиплексора 12 ре 25 зультат умножения появляется на выходах01 0 устройства,В оежиме умножения по модулю Мз =2" + 1 работа устройства происходит по правилам модульной арифметики для чисел30 Ферма.Так как кольцо 2 чисел, участвующих воперациях по модулю М = 2"+1, имеет порядок и, то для представления и-го числа изЕм необходимо (и+1) разрядов. Из структуры35 модуля Мз = 2"+1 вытекает равенство Мз=- 2" = (-1) вод Мз, с учетом которого приумножении числа, равного Мз, кольца Ъна любое число Ь(Ь "Мз -1) из этого кольцарезультат получается в виде отрицательного40 числа Ь, При умножении двух чисел, равныхМз - 1, с учетом указанного равенства результат получается равным единице по модулю Мз, так как (-1)(-1) = 1. Умножение Ок.ннулевымсигналамна выходахОп+2, ,02. При "О" во всех разрядах множимого "О" с входа "Режим 2" переключаетмульти- ("0" на входах 1, , 1 и ап+1 блока) или плексор 12 на вывод результата из блока 15 множителя ("0" на входах б 1, ., б и Ь+1) при приведения по модулю на выходы 01, , СЬ "1" хотя бы в одном из разрядов множителя устройства и первый вход элемента ИЛИ 13, 5 ("1" хотя бы на одном из входов б 1, ., б или выход которого является выходом Ол+1 раз- . Ь+1 блока) или множимого ("1" хотя бы на ряда устройства, Таким образом, результат одном из входов 11, Ь или Ь+1 блока), т, е.умножения с выходов регистров 4 и 5, при- приумножениичиселО Ь приОЬМведенный по модулю Мз = 2 "+1 в блоке 15, или а 0 при 0а : Мна выходе элемента появляется на выходах 01, Ол+1 устройст И 23 (во втором случае, элемента И 22) появва, Блок 14 анализасомножителейпредназ- ляется сигнал "1", который формирует сигначен для анализа разрядов сомножителей налы блокировки по нулю("0") и блокировки и выработки сигналов управления блоком данных (."1") на соответствующих выходах 15 приведения по модулю. блока, а также обеспечивает появление сигБлок 14 анализа сомножителей (фиг.2) 15 налов "О" на выходах Ь 1, , Ь блока, такработает следующим образом. как на входе адреса п - разрядного мультиНа входы 11, ., 1 и и б 1, ., бп блока плексора 16 присутствуетсигнал "1",Навыпоступают младшие и разрядов множимого ходе 1 блока при этом присутствует сигнал и множителя соответственно. На входы ад+1 "0".и Ь+1 поступают старшие разряды множи При "О" на всех входах блока, т. е. при мого и множителя соответственно. При "1" отсутствии входных данных, на выходах ц, на выходах ао+1 и Ьп+1, т. е. при умножении 11., Ь,. Ь блока присутствуют сигналы чисел, каждое из которых равно (М+1), на "0", а на выходе К блока - сигнал "1". Блок выходе элемента И 21 формируется сигнал 15 приведения по модулю работает следую- "1", который через элемент ИЛИ 27 форми щим образом,рует на выходе К блока сигнал блокировки При "1" на входе К блока и - разрядные данных, а через элемент ИЛИ 26 поступает мультиплексоры 30, 31 переключаются в пона вход адреса разрядного мультиплексора ложение, обеспечивающее поступление 16. что поиводит к появлению на выходах сигналов с входов Ь, Ь блока на входы Ь 1 , Ь блока сигналов "0". "1" на выходе 30 первого слагаемого третьего и - разрядного элементаИ 21 являетсятакжесигналомкор- сумматора 32 и сигналов "0" - на входы рекции по старшим разрядам на выходе 1 второго слагаемого и - разрядного сумблока, При этом на выходе ц блока форми- матора 31. П ри "О" на входе К блока руется сигнал блокировки по нулю в виде п - разрядные мультиплексоры 30, 31 пе- "1",При "1" на одном из входов а+1 или Ьл+1 35 реключаются в положение, обеспечиваю- (например Оа + - 1, Оь =О, т. е. при щее поступление сигналов с входов в 1, умножении чисел а = (М) и 0ЬМ) ", щп и Р 1, , рп блока на входы соответэлемент ИСКЛЮЧАЮЩЕЕ ИЛИ 19 через ственно первого и второго слагаемых и. - элемент ИЛИ 27 формирует на выходе К разрядного сумматора 32, т. е, на входы блока сигнал блокировки данных в виде "1" 40 и-разрядного сумматора 32 поступают При этом на выходе ц . блока формируется младшие и инвертированные старшие раэсигнал блокировки по нулю в виде "1". Так ряды произведения. Результат сложения в как на входах элемента И 20 присутствуют и-разрядном сумматоре 32 поступает на сигналы "0", то на входе адреса и - разрядного входы первого слагаемого и - разрядного мультиплексора 24 появится сигнал "0", что 45 сумматора 33, на входы второго слагаемоприводит к передаче на выходы Ь, , Ьго поступают сигналы переносов из и - разблока инвертированных значений разрядов рядного сумматора 32 или с выхода множителя Ь 1, , Ь, так как на входе адреса элемента И 2 блока 14 анализа сомножии-разрядного мультиплексора 16 также при- телей при "1" на входе ц блока 15. При сутствует "0" с выхода элемента ИЛИ 26. При 50 сигнале переноса из и-разрядного сумма- обратной комбинации сигналов тора 32 "0" на вход второго слагаемого (Ъп+ = 0 и Оь+= 1, т, е, приумножении и - разрядного сумматора 33 поступает чисчисел 0а 1Ми Ь = (М) на выходах ло, равное двойке, при "1" на выходе пере- Ь, , Ьп появятся инвертированные зна- носа и-разрядного сумматора 32 (или чения разрядов множимогоа,.,ал,таккак 55 выходе элемента И 21 блока 14 анализа на входе адреса и - разрядного мультиплек- сомножителей) на вход второго слагаемого сора 24 присутствует с выхода элемента Ии-Разрядного сумматора 33 поступает чис сигнал "1". На выходе т блока при этом ло, равное единице. При "0" на входе 9 бло. присутствует сигнал "0",ка переносы запрещены.5 10 15 20 25 30 35 40 ЮЩЕЕ ИЛИ, входом первого элемента НЕ и 45 гистра множителя и инверсными входами 50 55 Формула изобретения Устройство для умножения двух чисел по авт, св, М 1179322, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения умножения двоичных целых чисел по трем взаимно простым модулям М 1=2, М 2=2 п Мз = 2", в него введеНы (и+1) - разрядныймультиплексор, элемент ИЛИ, блок анализа сомножителей, сг лежащий два элемента , НЕ, четыре элемента И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, три элемента ИЛИ и два и - разрядных мультиплексора, и блок приведенияпо модулю, содержащий два и - разрядных сумматора, четыре элемента И, элементИЛИ и элемент НЕ, причем в устройствевыход элемента ИЛИ соединен с выходомпервого старшего разряда произведения ус, тройства, выходы младших разрядов произ-ведения которого соединены соответственнос выходами разрядов (и+1)-разрядногомультиплексора, выход (и+1) - го разряда ко торого соединен с первым входом элемента , ИЛИ, второй вход которого соединен с вы ходом первого элемента И второй группы,второй вход установки режима работыустройства соединен с входом адреса (и+1) - разрядного мультиплексора, входстробмрования которого соединен с соот ветствующим выходом блока синхрониза-ции, вход нулевого потенциала устройствасоединен с информационным входом (и+1) -го разряда первой группы (и+1)-го разрядного мультиплексора, информационные входы и разрядов первой группы которого соединены соответственно с и выходами блока коррекции, а в блоке анализа сомножителей информационные входы первой группы первого и - разрядного мультиплек, сора соединены соответственно с выходамирегистра множимого и п инверсными входами первого элемента И, (и+1) - й инверсный вход которого соединен с первыми входами , второго элемента И и элемента ИСКЛЮЧАвходом (и+1) - го разряда множимого устройства, информационные входы второй группы первого и - разрядного мультиплексора соединены соответственно с выходами ретретьего элемента И, (и+1) - й инверсный вход которого соединен с вторыми входами второго элемента И и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, входом (и+1)-го разряда множителя устройства и первым входом четвертого элемента И, второй вход которого соединен с выходом первого элемента Н Е, а выход - с входом адреса первого и-разрядного мультиплексора, выходы которого Соединены соответственно с информационными входами первой группы второго и - разрядного мультиплексора, информационные входы второй группы которого соединены с входом единичного потенциала устройства, а вход адреса - с выходом первого элемента ИЛИ, первый вход которого соединен с первым входом второго элемента ИЛИ, входом второго элемента НЕ и входом третьего элемента ИЛИ, первый и второй входы которого соединены с выходами первого и третьего элементов И, второй вход первого элемента ИЛИ соединен с вторым входом второго элемента ИЛИ и выходом второго элемента И, выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с третьим входом второго элемента ИЛИ, входы стробирования первого и второго и - разрядных мультиплексоров соединены с соответствующими выходами блока синхронизации, а в блоке приведения по модулю информационные входы первой группы первого и - разрядного мультиплексора соединены соответственно с инверсными выходами второго и - разрядного мультиплексора блока анализа сомножителей, информационные входы второй группы первого и-разрядного мультиплексора соединены соответственно с выходами регистра младших разрядов произведения, вход адреса первого и - разрядного мультиплексора соединен с выходом второго элемента ИЛИ блока анализа сомножителей и входом адреса второго и-разрядного мультиплексора, информационные входы первой группы которого соединены с входом единичного потенциала устройства, выходы регистра старших разрядов произведения соединены соответственно с информационными входами второй группы второго и - разрядного мультиплексора, инверсные выходы которого соединены соответственно с входами первого слагаемого первого и - разрядного сумматора, входы второго слагаемого которого соединены соответственно с выходами первого и - разрядного мультиплексора, а выходы суммы - соответственно с входами первого слагаемого второго и-разрядного сумматора, выходы суммы которого соединены соответственно с инверсными входами первого элемента И и информационными входами и разрядов второй группы (и+1)-разрядного мультиплексора, информационный вход (и+1) - го разряда второй группы которОго соединен с выходом второго элемента И, первый вход которого соединен с выходом первого элемента И, а второй вход - с выходом переноса второго и-разрядного сумматора, вход первого разряда второго слагаемого которого соединен с выходом элемента ИЛИ, первый вход которогосоединен с выходом третьего элемента И, первый вход которого соединен с выходом переноса первого и-разрядного сумматора и входом элемента НЕ, выход которого соединен с первым входом четвертого элемента И, второй вход которого соединен с вторым входом третьего элемента И и выходом второго элемента НЕ блока анализа сомножителей, выход второго элемента И которого соединен с вторым входом элемента ИЛИ, выход четвертого элемента И соединен с входом второго разряда второго слагаемого второго и-разрядного сумматора, входы второго слагаемого, начиная с 5 третьего по и-ый разряд, которого соединены с входом нулевого потенциала устройства, входы стробирования первого и второго и-разрядных мультиплексоров соединены с соответствующими выходами блока синхро низации.1667059 Составитель Е. Мурзинаесивых Техред М,Моргентал Корректор .О. Кравцова дакто зводственно-издательский комбинат "Патент", г. Ужгоро гарина, 10 Заказ 2524 Тираж 396 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб., 4/5