Матричный умножитель по модулю чисел ферма

(я)з 6 06 Г 7/49 ТВЕННОЕ ПАТЕНТНОЕО СССРТ СССР ГОСУДАР ВЕДОМС (ГОСПАТЕ)АНИЕ ИЗОБРЕТ ИЯ ОП К АВТ СКОМУ СВИДЕТЕЛЬСГВУ 1 2(21) 4869772/24ко-числовых преобразований по модулю чи(22)26,09,90 .:, .. сел Ферма. Цель изобретения - . расшире(46) 23.12.92. 6 юл, % 47 в: . ниефункциональных возможностей путем(71) Научно-исследовательский институт ра- выполнения умножения (и+1)-разрядныхдиотехнической аппаратуры . двоичных чисел по модулю чисел Ферма Р(56) Авторское свидетельство СССР по модулю чисел Ферма содержит блок форМ 1244662, кл, 6 06 1- 7/52, 1984, "мирования частичных пройзвевдений и блокАвторское свидетельство СССР суммйрования частичных произведений; 8В 1160398, кл, О 06 )= 7/49, 1983,- блок формирования частичных произведе(54) МАТРИЧНЫЙ УМНОЖИТЕЛЬ ПО МО-: ний; состоящий из треугольной матрицыДУЛЮ ЧИСЕЛ ФЕРМА: . и(и+ 1)/2 элементов И., введены и(и+1)/2(57) Изобретение относится к вычислитель-элементов ИЛИ-НЕ в виде треугольнойной техйике и предназначено дляперемно- . матрицы и (и+ 1) элементов НЕ, а в блокжейия (и+ 1)-разрядных двоичных чисел с суммирования. содержащий матрицуиз йприведением результата по модулю чисел х и одноразрядйых сувмвмэторов, введеныФерма Р 1 =.2" + 1, и = 2, что может быть, (и+1) элементов И, (и) злементрв ИЛИ-НЕиспользойано в спецйроцессорах теорети- и элемент ИЛИ. 3 ил. И ной т)= 7/5 оди рос техни множ зобретение относится к вычислительехнике и предназначено для перемноя (и+ 1)-разрядных чисел с дением результата ио модулю чисел а Р =2"+1, и, что может быть исиольо в сиецпроцессорах теоретико-числореобразований с числами Ферма.звестны матричные умножители с ириием результата по модулю (авт. св, ЬЬ 50, кл. О 06 Р 7/49, авт. св.)ч. 1179322, 06 Р 7/52, авт. св. М 1244662, кл. О 06 2; авт, св, М 1160398, кл. 0 06 Р 7/49). известных устройствах результат прися ио модулю чисел вида 2"-1, где и - ое.аиболее близким к изобретению по ческой сущности является матричное ительное устройство, содержащее блок формирования частичнйх произведений и блок суммирования частичных произведений.Недостатком известного устройства является невозможность его использования для вычисления произведенийв(и+1)-разрядных чисел по модулю чисел Ферма. Р - 2 "+1, и=2,т=О, ,4.Цель изобретения - расширение функциональных возможностей путем выполнения умножения (и+ 1-разрядных двоичных чисел по модулю чисел Ферма Г 2"+1, и=2,1-0, ,4.Указанная цель достигается тем, что в матричном умножителе, содержащем блок суммирования, состоящий из матрицы и х и одноразрядных сумматоров, и блок формирования частичных произведений, состоя1783513 34щийиз треугольной матрицы п(п+2)/2 эле- но с выходами Фтервого, второгои третьего ментов И, первый вход (, -го элемента И, элементов И, первые входыпервого, второ- .матрицы которого соединен с входом )-го го и четвертого элементов И соединены с разряда множимого устройства ( - номер выходом первого элемента НЕ; выход второ строкиматрицы;)-номерстолбцаматрицы; 5 го элемента НЕ соединен с первым входом, ) = 1,; и), вход -го множителя которого третьегоэлементаИ и вторыми входамйвтосоединен с вторым входом (, -го элементарого и четвертого элементов И, выходтреть- И матрицы блока формирования частичных его элемента НЕ соединен с вторымй произведений, выходы (1, -х элементов И входами первого и третьего элементов И и матрицы которого соединены соответствен третьим входом четвертого злемейта И, вына".свходами переноса (, 1)-х одйоразряд- ход ц-го элемента И (а = 4, , и) соединей с ных сумматоров матрицы, кроме (1, 1)-го третьим входом (а)-го элемента ИЛИ-НЕ и одноразрядного сумматора, входы которого первым входом (ц+1)-го элемента И; второй соединены еоответственно с выходами (2, . входкоторагасоединенсчетвертым входом -хэлементовИ матрицы.блока формирава (ц)-го элемента ИЛИ-НЕ и выходом ц-гонйя частичных произведений, выход суммы злемейта НЕ блока формирования частич(, К)-го одноразрядного сумматора матрицы ных произведений; выход (и+1)-.го элемента блока суммирования соединен с первым И соединен с третьим входом (п-.1)-го элевходом(. 1+1)-гоодноразрядногосуммато- мента ИЛИ-НЕ и вторым входом элемента ра матрицы блока суммирования (К = 120 ИЛИ, выходы суммы (,и)-х одноразрядных п), вМходперенаса(К гп)-гоодноразрядна- сумматоров матрицы соединены с выходаго сумматора матрицы каторбго соединен с ми п разрядбв результата устройства, выход входом переноса ф+ 1, в+ 1)-го одноразряд- (и+1)-го разряда результата устройства коного сумматора матрицы блокасуммирова- торого соединен с выходом элемента ИЛИ, ния, в блок формированиячастичных 25 входлогическогонуляустройствасоединен .произведений введены п(п+ 1)/2 элементовс вторым входом (1, и)-гоодноразрядйого ИЛИ-НЕ в виде треугольной матрицы и (и+1)сумматора матрицы.элементов НЕ, а в блок суммирования вве- . На фиг. 1 приведена общая структурная дены (и+ 1) элементов И, (и) элементов схема умножения по модулю чисел Ферма; ИЛИ-НЕ и элемент ИЛИ. причем в блоке 30 на фиг, 2 - функциональная схема блока формирования частичных произведений формирования частичных произведений; на входы (и+1) элементов НЕ. соединены соат- Фиг, 3-функциональнаясхемаблокасумми-: ветственна с входнойр-х разрядовмнажи- рования частичных произведений.теля усграйства (р - 1 п+ 1), выходМатричный умножитель по модулю чиэлемента НЕ ( - 2, , и+ 1) соединен с 35 сел Ферма содержит блок 1 формирований первьми входами(- Д-х элементов ИЛИ-НЕ частичных произведений, выходы. которогоматрйцы, вторые входы которых соедйнены соединены с входами блока 2 суммированиясоответственно с входами)-х разрядов мно- частичных произведений (фиг. 1).жимога устройства, вход (и+ 1)-го разряда " Ьлок 1 формирования частичных промножимого которого соединен с третьими 40 изведений (фиг, 2) содержит в элементов входами всех п(п+1)/2 элементов ИЛИ-НР 31-Зп И, гп элементов 41-4 ИЛИ-НЕ, где: матрицы и первыми входами(п) элементов а= п(п+ 1)/2, а также (и+1) инверторав ИЛИ-НЕ блока Суммйрования выходы зле-5+з, входы которых подключейы.к вхо ментов И матрицы и элементов ИЛИ-НЕ. дам (и+1) разрядов множителя и первымматрицы блока формйрования чаСтичных входам(п+1-) элементов 31 - 3 Й, а их выхопроизведений соединены с входами соот- ды - к первымвходам (-1) элементов 41-4 п 1" ветствующих весов одноразрядных сумма- ИЛИ-НЕ ( - номер разряда множителя, гдеторов матрицы блока суммирования, а в)=)+(й);З-входыразрядовмножимого,где блоке суммирования выход переноса (и, К)- ) = 1-п), подключены к вторым входам(п+1- го одноразрядного сумматора матрйцы сое-: элементов 31-3 И и вторым входам,3 элединен с вторым входом -го элемента ментов 41-4 п ИЛИ-НЕ, третьи входы50ИЛИ-НЕ, выход которого соединен с входом п(п+1)/2 элементов 41-4 ИЛИ-НЕ подклюпереноса (1; Е+1)-го одноразрядного сумма-: чены к входу (и+1)-го разряда множимого." тора матрицы, выходы переносов(с, и)-го . Выходы элементов 31-Ы И и 41-4 ИЛИи (К и)-го одноразрядных сумматоров мат НЕ, соответствующие -разряду множимого.рицы соединены соответственнос вторым являются выходами (+3-1)аоб и-разрядов - входом (1+1, и)-го и входом переноса (1+1,частичного произведения.и)-го одноразрядного сумматоров матрицы, В блоке 2 суммирования частичных протретий; четвертый и пятый входы первого изведений (фиг. 3) )-разряды 1-частичных элемента ИЛИ-НЕ соединены сОатветствен-. произведений ( = 1-3) подключены соответственно к 1-входам одноразрядных сумматоров бц, -разряды 1-частичных произведений ( = 4-и) подключены соответственно к вторым входам одноразрядных сумматоров бь 2, , )-разряды (и+1)-го частичного произведения подключены соответственно к вторым входам одноразряДных сумматоров бп ( = 1-и). Выходы переносов одноразрядных сумматоров бк, и (К = 1-(иподключены соответственно к первым входам 1-элементов 71-7 пИЛИ-НЕ, выходы которых подключены соответственно к входам переносов одноразрядных сумматоров 6+1,1, выходы переносов одноразрядных сумматоров бп-ц= 1-(иподключены к первому входу одноразрядных сумматоров бп, 1+1.В ыходы переносов одноразрядных сум- МатОРОВ бп, 1 ПОДКЛЮЧЕНЫ СООтВЕтетВЕННО К входам переносов одноразрядных суммато- рОВ бп, 1+1. ВтОрЫЕ ВХОдц ЭЛЕМЕНТОВ 71 - 7 пИЛИ-НЕ подключены к входу (и+ 1)-го разряда множимого. Третий, четвертый и пятый. входы элемента 71 ИЛИ-НЕ подключены к выходам элементов 81, 82, 8 з И, входы которых попарно подключены к выходам инверторов 51, 52, 5 з, подключенных также к трем входам элемента 84 И. Выходы элементов 84-8 п И ПадКЛЮЧЕНЫ СООтВЕтСтВЕННО К третьим входам элементов 72 - 7 пИЛИ-НЕ и первым входам элементов 85 - 8 п И соответственно. Вторые входы элементов 85-8 п И подключены соответственно к четвертым ВХОдаМ ЭЛЕМЕНТОВ 72-7 пИЛИ-НЕ И СООтветственно к выходам инверторов 54 - 5 п, ВЫХОД ЭЛЕМЕНта 8 п+1 И ПОДКЛЮЧЕН К трЕтЬЕМу ВХОду ЭЛЕМЕНта 7 пИЛИ-НЕ И ПЕРВО- му входу элемента 9 ИЛИ, второй вход которого подключен к входу (и+ 1)-го разряда множимого, а выход является выходом (и+ 1)-го разряда результата.Выходы одноразрядных сумматоров бп,1, бп, и являются выходами )-разрядов результата, Второй вход одноразрядного СуММатсра бп, 1 ПОДКЛЮЧЕН К ВХОду ЛОГИ- ческого нуля устройства,Устройство функционирует следующим образом.Умножение выполняется, как и в обычном умножителе, "в столбик", но с учетом операций сдвига и сложения по модулю Ферма.Чтобы упростить реализацию устройства для формирования результата операции Х= А х В вод Гь Р 1 = 2 п + 1. п = 2, множитель В поступает в обычном двоичном коде в кольце целых чисел по модулю числа Ферма Еь а множимое А- в коде с уменьшением на единицу в кольце Р 1, А -(А) п 1 об Р 1 х А 4 АЗА 2 А 1 В 4 ВзВ 2 В 1 в обы 45 А 4 В 1 АзВ 1 А 2 В 1 А 1 В 1чномумножителе 50А 4 В 1 АЗВ 1 А 2 В 1 А 1 В 1 в умнажитЕлЕАЗВ 2 А 2 В 2 А 1 В 2 А 4 В 2 по мОдулю чисА 2 ВзА 1 ВзА 4 ВзАзВр ла Ферма Е 2= 17А 1 В 4 А 484 АзВ 4 АгВ 4 55Таким образом, также используютсяблок 1 формирования частичных произведений и блок.2 суммирования частичных произведений. При этом в блоке 1 оставшиеся на месте относительно обычного умножитеВ этом случае умножение на степеньдвух выполняется посредством циклическо 5, го сдвига на показатель этой степени влевос инверсией вновь вдвигаемых разрядов, апри суммировании в случае отсутствия переноса из старшего разряда к результатунеобходимо прибавить единицу, В случае10 поступления нулевого операнда (лог, 1 в(и+1)-и разряде, Остальные разряды - лог. Я)операция суммирования прерывается,Различие представления множимого А имножителя В не влияет на универсальность15 применения такого устройства, так как, какправило, множимое поступает из вычислительной системы, в которой используетсятакое же перекодированное представление,а ранее вычисленный множитель хранится в20 ПЗУ, Результат также представлен с уменьшением на единицу,Нулевой результат образуется либо вслучае Ап+1 = 1, остальные разряды А равнылог. , либо все разряды множителя равны25 лог. , В этом случае все частичные произведения равны нулю, все переносы блокируются и на выходе образуется нулевоеЗНаЧЕНИЕ П раэрядОВ рЕЗуЛЬтата Х 1-Хп, раэряд Хп+1= 1.При поступлении множителя с Вп+1= 1,В 1=.Вп= ф(число "минус один" в кольце Р 1)необходимо просто проинвертировать разряды множимого, Зто выполняется обнулекием первых и частичных произведений и35 пропуском на выход только (и+1)-го частичного произведения.Соответствие между обычным матричным умножителем и предложеннь 1 м устройством можно проиллюстрировать для40 п=4:ля разряды частичных произведений формируются элементами 31-Зп И, а вновьвдвигаемые" - с помощью элементов 41-4 пИЛИ-НЕ и инверторов 51-5 п+1,На третьи входы элементов ИЛИ-НЕ41-4 п поступает (и+ 1)-разряд множимогодля обнуления всех выходов частичныхпройзведений, если множимое представ.лено нулевым значением, как отмечено выше,. Далее суммирование частичных произведений производится матрицей сумматоров блока 2 с учетом необходимостиприведения двоичных сумм по модулю числа Ферма. Первые три частичных произведения подаются на входы первой группысумматоров 61,1-61,п, остальные - на следующие (и) группы сумматоров 6 К 1- бк,п, где1 = 4-и. Последнее частичное произведение,соответствующее инверсии всех разрядовмножимого, поступает на последнюю группу сумматоров бп,1 - бп,п,Поскольку промежуточные разрядысумм передаются параллельно с поразряд: ными переносами, сложение итогового слова сумм и слова переносов происходит нагруппе сумматоров бп,1-бп,п, переносы вкоторый подключены, как в обычном сумматоре, Сумматоры бп,1 - бп;и производят окончательную .коррекцию. результатаприбавлением инвертированного переносапри ненулевом множимом и множителе. неравном "нулю" йли "минус единице" в коль-.це Еь либо только пропускают инверсныеразряды ненулевого множимого на выход вслучае, если множитель равен "минус единице",Если Ап+1= 1, либо В 1= В 2= . = Вп= , тоэлементами 71- 7 пи 81-8 п+1 блокируютсявсе переносы и обеспечивается нулевой результат на входах последней группы сумматоров бп.1-6 п,п. В противном случаеэлементами 71-7 побеспечивается передача инвертированного переноса на вход переноса сумматоров следующей группы,ЧЕРЕЗ ЭЛЕМЕНтц 8-8 п+1 ОбЕСПЕЧИВаЕтСя ПЕредача разрешения суммирования с учетомпереноса, если очередное частичное произведение не равно нулю (соответствующий. ему разряд множителя равен лог. 1), а такжеесли результат предыдущего промежуточного суммирования не равен нулю;Таким образом, устройство обеспечивает выполнение перемножения двоичных чисел по модулю соответствующего числаФерма, если множимое представлено в коде с уменьшением на единицу по этому модулю. При этом результат будет совпадать срезультатом обычного двоичного умножения, если только множимое и множитель в сумматоре содержат не более и двоичныхразрядов,Формула изобретения 5, .Матричный умножитель по модулю чисел Ферма, содержащий блок суммирования, состоящий из матрицы и х и одноразрядных сумматоров, и блок формирования частичйых произведений, состоя щий из треугольной матрицы п(п 1)/2элементов И, первый вход 0- Д-го элемента И матрицы которого соединен с входом )-го разряда множимого устройства ( - номер строки матрицы, 1 - номер столбца матрицы, 15 1, 1 = 1, , п), вход 1-го разряда множителякоторого соединен с вторым входом (1, Д-го элемента И матрицы блока .формирования частичных произведений, выходы (1;Д-х элементов И матрицы которого соединены со О ответственно с входами переноса (1, .1)-ходноразрядных сумматоров матрицы блока суммирования, первые входы (1, 1)-х одноразрядных сумматоров матрицы, кроме (1, 1)-го Одноразрядного сумматора, соедине ны соответственно с выходами (2, Д-х элементов И матрицы блока формирования частичных произведений, выход суммы (1, 1+)-го одноразрядного сумматора матрицы блока суммирования соединен с первым 3 О входом (1, 1+1)-го одноразрядного сумматора матрицы блока суммирования (М = 1, , п), выход переноса(к, в)-го одноразрядного сумматора матрицы которого соединен с входом переноса (+11 п+1)-го однораз-, 35 рядного сумматора матрицы блока суммирования, о т л и ч а ю щ и й с я тем, что, с целью расширения функционайьных возможностей путем выполнения умножения (и+1)-разрядных двоичных чиеел по модулю 4 О чисел ферма Р= 2 п+1, п - 2 в блок формирования частичных произведений введены п(п+1)/2 элементов ИЛИ-НЕ в виде треугольной матрицы и и+1 элементов НЕ, а,в блок суммирования введены и+1 элементов 5 И, иэлементов ИЛИ-НЕ и элемент ИЛИ,причем в блоке формирования частичных произведений входы и+1 элементов НЕ соединены соответственно с входами р-х разрядов множителя устройства (р 1 п+1); ВыхОД 1-го элемента НЕ (1 2, , и+1) соеДИ- нен с первыми входами (1. Д-х элементов ИЛИ-НЕ матрицы, вторые входы которых соединены соответственно с входами )-х разрядов множимого устройства, вход (и+1)- 55 го разряда множимого которого соединен свходами всех п(п+1)/2 элементов ИЛИ-НЕ матрицы и первыми входами иэлементов ИЛИ-НЕ блока суммирования, выходы элементов И матрицы и элементов ИЛИ-НЕ матрицы блока формирования частичных1783513 10 9произведений соединены с входами соот- второго и четвертого элементов И, выход ветствующих весов одноразрядных сумма- третьего элементаНЕ соединен с вторыми торов матрицы блока суммирования, а в входами первого и третьего элементов И и блоке суммирования выход переноса (и, к)- третьим входом четвертого элемента И, выго одноразрядного сумматора матрицы сое ход ф-го элемента И (1 = 4, , и) соединен с динен с вторым входом к-го элемента третьим входом(й)-го элемента ИЛИ-НЕ и ИЛИ-НЕ, выход которого соединен с входом . первым входом (с+1)-го, элемента И, второй переноса (1, +1)-го одноразрядного сумма- вход которого соединен с четвертым входом тора матрицы,"входы переносов (К и)-го и. ф 2)-го элемента ИЛИ-НЕ и выходом т-го эле- (К и)-го одноразрядных сумматоров матри мента НЕ блока формирования частичных цы соединены соответственно с вторым вхо- произведений, выход (и+1)-го элемента И дом (1+1, и)-го и входом переноса (1+1, . соединенстретьим,входом(п)гоэлемента и)-го одноразрядных сумматоров матрицы, ИЛИ-НЕ и вторым входом элемента ИЛИ, третий, четвертый и пятый входы первого выходы суммы(1, и)-х одноразрядных сумэлемента ИЛИ-НЕ соединены соответствен маторов матрйцы соединеныс выходами и но с выходами первого, второго и третьего: разрядов результата устройства, выход элементов И, первые входы первого; второ- (и+ 1)-го разряда результата которого соего и четвертого элементов И соединены с динен с выходом элемейта ИЛИ, вход ловыходом первого элемента НЕ, выход вто- гического нуля устройства соединен с рого элемента НЕ соединен с первым вхо вторым входом (1, и)-го одноразрядного дом третьего элемента И и вторыми входами сумматора матрицы.. вдатклтор Г.Бельскагя оизаодстееннто-издательскийкомбинат "патент", г. ужгород, ул.Гагарина, 101 Заказ 4516 : .: Тираж,:;:.Подписное ВНИИПИ Государственногокомитетеат по.изобретениям и открытиям при ГКЙТ СССР 113035; Москва, Ж, Раушская наб 4/5