Устройство для умножения по модулю м=2 -1

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИРЕСОУБЛИК 6 Р 749 ТЕНИЯ кии институт 8 ьство ССС /49, 1983 тво СССР /49, 1985 свидетел С 06 Р 7 идетельс С 06 Р 7(57) Изобреттельной и интехнике и мо ВО ДЛЯ УМНОБЕН ик вы е относит ерител зован ормационно-и ет быть испо ОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ ОПИСАНИЕ ИЗОБ К АВТОРСКОМУ СВИДЕТЕПЬСТ(56) АвторскоеУ 1160398, кл.Авторское свР 1254471, кл. 801383339 устройствах для цифровой обработкисигналов, в частности, для цифровойобработки изображений , а также вустройствах кодирования,. принципдействия которых базируется на теорииконечных колец и полей Галуа. Цельизобретения - повышение быстродействия. Устройство содержит группы входов 1, 2 прямого и инверсного значений одного операнда, группу входов 3другого операнда, коммутатор 4, блок5 формирования частичных произведений, блок б суммирования частичныхпроизведений, блок 7 коррекции, коммутатор 8, многовходовой одноразряд-.ный сумматор 9, группу элементов НЕ1 О, выходы 11, 1 з.п. ф-лы, 10 ил.1383339 В.Березк остав Н.Рогулич Корректор О. К хр Олейник а Подписномитета СССР и открытий кая наб., д. 4/5 а Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная,Реда Зака 7/47Тираж ВНИИПИ Государств по делам изобр 113035, Москва, Ж, 704 енног етениИзобретение относится к вычислительной технике и информационно-измерительным системам и может быть использовано в устройствах для цифро 5вой обработки сигналов, в частности,для цифровой обработки изображенийа также в устройствах кодирования,принцип действия которых базируетсяна теории конечных колец и полей Га-. 10луа,Цель изобретения - повышение быстродействия устройства.На фиг.1 приведена функциональнаясхема устройства для умножения по модулю М-1; на фиг.2 - функциональная схема многовходового (и-входового) одноразрядного сумматора; нафиг,3 - функциональная схема коммутатора; на фиг.4 и 5 - функциональная 20схема блока формирования частичныхпроизведений; на фиг.б - функциональная схема узла приоритета; на фиг.7 -функциональная схема сдвигателя; нафиг.8 - схемы умножителей на степени двойки; на фиг.9 - функциональнаясхема блока суммирования частичныхпроизведений; на фиг10 - функциональная схема блока коррекции.Устройство для умножения по модулю М=2 -1 (фиг.1) содержит группувходов 1 1 . . . 1 прямого значения операнда Ь Ь,Ь, группувходов 2 2 2 инверсного значения операнда Ь Ь Ь гРУи 35пу входов 3,3 3 (прямого зна-.чения) второго операнда а аа, коммутатор 4, блок 5 формирования частичных произведений, блок 6суммирования частичных произведений, 40блок 7 коррекции, коммутатор 8, многовходовой одноразрядный сумматор 9,группу элементов НЕ 10 1 О ,10 ь,выходы 11, 11 ,11. Значенияоперандов могут быть выбраны из регистров (при этом прямые и инверсныевыходы одного регистра могут бытьсоединены с входами 1, 1 и 22), и в регистр же может бытьзанесено значение результата с выходов 11 11. Сумматор 9 своимивходами 1212 12 соединен свходами 1 1 1, а выходом 13старшего разряда - с управляющимивхоцами коммутаторов 4 и 8. Информационные входы коммутатора 4 соединены с входами 1 1 . 1 и 2 эа выходы 14 1414 - с первой группой входов блока 5,вторая группа входов которого соедииена с входами 3 3 3, а выходы 15 15 15(где 1 с2= -- при и - четном М = --- при2и - нечетном) подключены к входам блока 6, выходы 16 16, 16.которого подключены к входам блока 7, выходы 17 17 ,, 17 которого соединены с входами элементов НЕ 10, 10 . , 1 О и первой группой информационных входов коммутатора 8, вторая группа входов которого подключена к выходам элементов НЕ 10, 1 Од,юМноговходовой одноразрядный .сум-фматор 9 (фиг.2) построен на двоичныхсумматорах 18.Коммутатор 4 (фиг,3) содержит элементы И 19 19; 19 , 20 20 22Коммутатор 8 строится аналогично.Блок 5 формирования частичных про"изведений (фиг.4 и 5) содержит узлы 23, 23 , 23 23 приоритета, группы сумматоров 24 по модулю два, сдвигатели 25 25 25. Совокупности узлов 23 и сумматоров 24 определяют управляющие коды, которыепоступают на управляющие коды сдвигателей 25, на информационные входы которых подается с входов 3 3 3 код операнда а а а. Каждый 8-й узел 23 (фиг.б), где В =1, 2.1 с, имеет входы 26 з , 26 зк и выходы 27,. , 27 зк, Узел 23 содержит элементы НЕ 28, 28 к-, И 29 эь 29 кКаждьп сдвигатель 25 (фиг.7) содержит группы элементов И 30, умножители 31 на степени двойки и группу элементов ИЛИ 32,Блок 6 суммирования частичных произведений (фиг.9) имеет 1 и-разрядных входов и содержит двоичные сумматоры 33 и узел 34 ускоренного переноса.Блок 7 коррекции (фиг.10) содержитдвоичные сумматоры 35, узел 36 ускоренного переноса и элемент И 37. В совокупности блоки 6 и 7 йредставляют собой сумматор 1 чисел по модулю М. , Произведением чисел а и Ъ по модулю М (1 = а Ь (во 1 М) называется остаток от делення обычного произведения аЬ на значение модуля М.Результат умножения по модулю М =н2 - 1 имеет число разрядов, равное числу разрядов каждого из сомножителей. 30Очевидно, что инверсия одного из сомножителей согласно (1) целесообразна лишь в том сЛучае, если этот сомножитель (в выражении (1) число Ъ) имеет больше половины единиц в значащих разрядах. Управление работой коммутатора 4 осуществляется с помощью и-входового одноразрядного сумматора 9, на котором формируется сумма разрядов множителя. Если число 40 единиц в разрядах множителя больше и/2, значение ш"го разряда на выхои г ае сумматора 9 (е = )1 оц - -, тае скобки 1 обозначают округление до ближайшего большего целого числа) равно единице. Значения младших разрядов не используются. Значение разряда сумматора 9 является управляющим сигналом для коммутатора 4. С выходов коммутатора 4 прямое или ин 50 версное значение множителя подается на входы блока 5, на другие входы которого подается множимое с входов 3 3 3. Блок 5 формирует 1 с слов частичных произведений, которые подаются на выходы 15, 15 у,р 15 к (каждый выход и-разрядный). Слова частичных произведений суммируются 35 Принцип быстрого умножения заключается в следующем.Для М = 2 - 1 справедливо равенство: -а = а, т.е. отрицательное число 5в кольце Ек (множество целых чиселО, 1, 2 Мс рассматриваемыми на нем операциями сложения и умножения по модулю М), представленное вдвоичной системе счисления, получает- Ося в результате инверсии соответствующего ему положительного числа. Отрицательные числа оказываются закодированными целыми числами, большимиМ,Например, для 2, = Е 7 можно записать соответствие: 0 О, 1- 1,2 2,3-е"3, 4- -3, 5 -2, 6 -1. В двоичной системе счисления эти числа можно представить трехразрядными двоич ными числами: -001 = 11 0 =. 6; -010 =101 = 5; -011 = 100 = 4, значит ум" ножение можно проводить по следующему выражению:а Ъ (тао 1 М) = (а Ь) (тос М), (1) с помощью блока 6 и корректируются блоком 7, на выходах 17, 17 17 которого формируются разряды сло. ва суммы частичных произведений. С этих выходов прямое значение слова суммы частичных произведений поступает на первые входы коммутатора 8, Кроме того, слово суммы частичных произведений инвертируется с помощью элементов НЕ 10 10 , , 10и подается на вторые входы коммутатора 8. Управляется последний с помощью того же управляющего сигнала, что и комму" татор 4. Таким образом, если производится инверсия множителя с помощью коммутатора 4, осуществляется инверсия результата умножения с помощью коммутатора 8, как того требует выражение (1). С выходов коммутатора 8л значение произведения по модулюМ=2 -1 подается навыходы 11 устройства.П р и и е р. При работе блока 5 пусть необходимо умножить два числа а = 1101011 (и = 7 и М = 2 - 1) и Ь = 0011011. Умножение проводится согласно (1), Значит слово а подается на входы 3 3,2 3, инверсное слово Ь =1100100 подается на выходы 14 14, 14 . Первые (младшие) 1 с разрядов поступают на входы узла 23. Задачей узла 23 является выбор еди 5ницы, которая встречается впервые в слове, поступающем на входы этого узла, На входы 26, 26, 26, (1 с =(7 + 1)/2 = 4) узла 23, подается слово 0010. На выходах 27 н. 27 Ф имеют 0010 (в этом слове только одна единица, поэтому входное значение совпадает с выходным). Это слово яв- ляется управляющим для сдвигателя 25, . На первые входы сумматоров 24- 24 ц по модулю два подается слово 010, а на вторые входы сумматоров 24-24, - слово 010 с выходов 27- 274 узла 23. На вход 26 а узла 23 подается эначенйе пятого разряда,т.е. нуль. Значит на сумматорах 24 -24 э суммируются по модулю два слова 010 и 010, что в результате дает слово 000. В результате на входах и выходах узла 23 имеют нулевое слово 0000, которое также является управляющим для сдвигателя 25. На первые входы сумматоров 24, -24 по модулю два подается слово 000 с выходов сумматоров 24 и 24 .первые два разряда и третий разряд с выхода 14. На вторые5 13833 входы сумматоров 24 д, -24подается слово 000 с выходов 27 -27 4 узла 23. На вход 264 узла 23подается значение шестого разряда, т,е. единица. Значит на сумматорах 24, -24 суммируются по модулю два слова 000 и 000, что в результате дает слово 000. В результате на входах узла 23 з находится слово 0001 и на выходе точно такое же слово 0001, которое является управляющим для сдвигателя 25. На первые входы сумматоров 24, -24по модулю два подается слово 001 с выходов сумматоров 24 и 24 зпервые два разряда и третий (1+2)-й разряд с выхода 14. На вторые входы сумматоров 24 з, -24 подается 001 с выходов 27, -27 узла 23 . На вход 2644 этого узла подается значение послед 44 него, т.е. седьмого разряда, равное единице. На сумматорах 24 з, -24 сум. мируются по модулю два слова 001 и 001, что в результате дает слово 000. В результате на входах узла 234 находится слово 0001 и на выходе точно такое же слово 0001, которое является управляющим для сдвигателя 254. Схема узла 23 осуществляет функцию выбора первой единицы в кодовом слове, которое поступает на входы 26 з, 26 з 26,. Умножители 31 на .степени двойки осуществляют умножение множимого на степень двойки по модулю М, что является обычным циклическим сдвигом и эти умножители представляют собой простую перекоммутацию проводов, На фиг.8 приведена такая перекоммутация для случая М = - 2 -1, Умножитель 31 на степеньЯ 40 двойки осуществляет умножение множимого на 2 , умножитель 3 в - на 2,умножитель 31- на 2" , причем умножение проводится по фмодулю М, В результате происходит циклический сдвиг множимого с помощью управляющего слова, поступающего на входыэлементов ИЛИ 32; 32 32Если в управляющем слове 1-й разрядравен единице, работает линейка элемен- . тов И 30 30 30, умножитель 31нн степень двойки который осуществляет умножения на 2 . Резул:ьтат умножения подается на выходы сдвигателя 25через элементы ИЛИ 32. На выходах остальных умножителей на 55 степени двойки (умножители 31 з, 3 1 52 ф3 1 э ) сигналысоответ ствующые значению логического нуля. 639Блок 6 реализует операцию суммы по модулю М 1 п-разрядных слов частичных произведений. Блок 7 коррекции устра" няет неоднозначность представления нуля 0 = 2 -1 (шов М = 2" - 1). В двоичной системе счисления нуль может представляться нулевым кодовым словом 0000, а также словом 1111 = 2" в , 1. Блок 7 коррекции преобразует единичное слово в нулевое.Формула изобретения1. Устроцство для умножения по модулю М = 2 - 1, содержащее блок формирования частичных произведений,блок суммирования частичных произведений и блок коррекции, причем группа входов одного из операндов устройства соединена с одной из групп вхо-дов блока формирования частичных произведений, выходы которого соединены с входами блока суммирования частичных произведений, выходы которого соединены с входами блока коррекции, отличающееся тем, что, с целью повьшения быстродействия, в него введены два коммутатора, многовходовой одноразрядный сумматор и группа элементов НЕ, причем другая группа входов блока формирования частичных произведений соединена с выходами первого коммутатора, первая и вторая группы информационных входов которого соединены соответственно с группой входов прямого значения и группой входов инверсного значениядругого операнда устройства, выходы блока коррекции соединены с первой группой информационных входов второго коммутатора и входами соответс 1- вующих элементов НЕ группы, выходы которых соединены с второй группой информационных входов второго коммутатора, выходы которого являются выходами устройства, а управляющий вход соединен с управляющим входом первого коммутатора и выходом старшегоразряда многовходового одноразрядного сумматора, входы которого соединены с первой группой входов информационных входов первого коммутатора.2, Устройство по п.1, о т л ич а ю щ е е с я тем, что блок формирования частичных произведений содержит 1 узлов приоритета, -1)групп сумматоров по модулю два и 1% 1и+1Е-- при и - нечетном; и - раз 25 рядность операндов), причем входы первого узла приоритета соединены с входами первой группы блока с первого по Е-й, входы -го узла приоритета (д щ 2 1 с) соединены с выходами сумматоров по модулю два (1.-1)-й группы и В+д)-м входом первой группы блока, первый вход 1-го сумматора по модулю два (-1)-й группы (31 1 с) соединен с Я+1)-м выходом (-1)-.го узла приоритета,второй вход 1-го сумматора по модулюдва второй группы соединен с (3+1)-мвходом первой группы блока, второйвход г"го сумматора по модулю два1-й группы (г = 1 1 сф 12,.., 1-1) соединен с выходом (г+1)-госумматора по модулю два (1-1)-й группы, выходы узлов приоритета соединены с управляющими входами соответствующих сдвигателей, информационныевходы которых соединены с входамивторой группы блока, а выходы - свыходами блока, 1383339