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

 

Изобретение относится к вычислительной технике и предназначено для перемножения (п+ 1}-разрядных двоичных чисел с приведением результата по модулю чисел Ферма Ft 2 + t, fi 2. что может быть использовано в спецпроцессорах теоретико-числовых преобразований по модулю чисел Ферма. Цель изобретения - расширение функциональных возможностей путем выполнения умножения (п-Н)-разрядных двоичных чисел по модулю чисел Ферма Ft 2 +1, , ,4. Матричный умножитель по модулю чисел Ферма содержит блок формирования частичных произведений и блок суммирования частичных произведений. В блок формирования частичных произведений , состоящий из треугольной матрицы п(п+ 1)/2 элементов И, введены п(п+1}/2 элементов ИЛИ-НЕ в виде треугольной матрицы и (п+ 1) элементов НЕ, а в блок суммирования, содержащий матрицу из п« х п одноразрядных сумматоров, введены (п+1) элементов И, (п-1) элементов ИЛИ-НЕ и элемент ИЛИ. 3 ил.

({9) (!!) СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

{5!)5 G 06 F 7/49

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬС ГВУ

1 (21) 4869772/24 (22) 26.09.90 (46) 23.12.92. 6юл. % 47 (71) Научно-исследовательский институт радиотехнической аппаратуры (72) А.С.Горйков (56) Авторское свидетельство С(. С.Р

М 1244662, кл, G 06 F 7/52, 1984.

Авторское свидетельство СССР

Q 1160398, кл. 6 06 F 7/49, 1983, (54) МАТРИЧНЫЙ УМНОЖИТЕЛЬ ПО МОДУЛЮ ЧИСЕЛ ФЕРМА (57) Изобретение относится к вычислительной техйике и предназначено для йеремножейия (и+ 1)-разрядных двоичных чисел с приведением результата по модулю чисел

Ферма Р! =.2" + 1, и = 2, что может был ь использовано в спецйроцессорах теоретиI

Изобретение относится к вычислительной технике и предназначено для перемно. жения (и+ 1)-разрядных чисел с приведением результата по модулю чисел

Ферма F = 2 "+1, п-2, что может быть использовано в спецпроцессорах теоретико-число- вых преобразований с числами Ферма.

Известны матричные умножители с приведением результата по модулю (авт. св, f4

1170450, кл. 6 06 F 7/49, авт. св. М 1179322, кл. 6 06 Р 7/52, авт. св. М 1244662, кл. 6 06

F 7/52; авт, св, М 1160398, кл. G 06 F 7/49).

В известных устройствах результат приводится по модулю чисел вида 2"-1, где n— простое.

Наиболее близким к изобретению по технической сущности является матричное множительное устройство, содержащее

2 ко-числовых преобразований пб модулю чисел Ферма. Цель изобретения —. расширение функциональных возможностей путем выполнения умножения (n+1)-разрядных двоичных чисел rio модулю чисел Ферма F<

= 2" +1, и =2, t =0,4. Матричный умножитель по модулю чисел Ферма содержит блок формирования частичных произведений и блок суммйрования частичных и )оизведений. 8 блок формирования частичных произведений; состоящий из треугольной матрицып(п+ 1)/2 элементов И., введены п(п+1)/2 элемейтов ИЛИ-HE в виде треугольной матрицы и (и+ 1) элементов НЕ, а в блок суммирования. содержащий матрицу из й» х и одноразрядйых сумматоров, введены (и+1) элементов И, (и-1) элементрв ИЛИ-HE и элемент ИЛИ. 3 ил. блок формирования частичнйх произведений и блок суммирования частичных произведений.

Недостатком известного устройства является невозможность его использования для вычисления произведений(п+1)-разрядных чисел Do модулю чисел Ферма F! - 2 "+1, и =2, t =0....,4.

Цель изобретения — расширение функциональных возможностей путем. выполнения умножения (и+ 1)-разрядных двоичных чисел по модулю чисел Ферма

F 2"+1, n=2,t-0, ...,4.

Указанная цель достигается тем, что в матричном умножителе, содержащем блок суммирования, состоящий из матрицы п х п одноразрядных сумматоров, и блок формирования частичных произведений, состоя1783513

3 . 4 щий из треугольной матрицы n(n+2)/2 эле- но с выходами первого, второго и третьего ментов И, первый вход (l, j)-ro элемента И, элементов И, первые входы первого, второ- . матрицы которого соединен с входом J-го го и четвертого элементов И соединены с разряда множимого устройства (! — номер выходом первого элемента НЕ, выход второ строкиматрицы;!-номерстолбцаматрицы; 5 го элемента НЕ соединен с первым входом

l, J =;;. и}, вход !-го множителя которого третьего элемента И и вторыми входамйвтосоединен с вторым входом (l, -го элемента рого и четвертого элементов И, выход третьИ матрицы блока формирования частичных его элемента НЕ соединен с вторымй произведений, выходы (1, ))-х элементов И входами первого и третьего элементов И и матрицы которого соединены соответствен- 10 третьим входом четвертого злемейта И, вына". с входами переноса (l, 1)-х одйоразряд- ход q-ro элемента И (w = 4, ..., n) соединей с ных сумматоров матрицы, кроме (1, 1)-го третьим входом (q-2)-го элемента ИЛИ-НЕ и одноразрядного сумматора, входы которого первым входом (ц+1)-го элемента И; второй соединены еоответственно с выходами (2,: входкоторагасоединенс четвертым входом

j)-хэлементовИ матрицыблокаформирава- 15 (q-2)-го элемента ИЛИ-НЕ и выходом q-го нйя частичных произведений, вых6д суммы злемейта НЕ блока формиравания частич(!, k)-го одноразрядного сумматора магрицы ных произведений; выход (n+1)-.ro элемента блока суммирования соединен с первым И соединен с третьим входом (n-1)-ro элевходом(1. 1+1)-го одноразрядного суммато- . мента ИЛИ-HE и вторым входом элемента ра матрицы блока суммирования (k = 1, .... 20 ИЛИ, выходы суммы (!,и)-х одноразрядных п-1), выходперенаса(К m)-гоодноразрядна- сумматоров матрицы соединены с выходаго сумматора матрицы которого сбединен с ми п разрядбв результата устройства, выход входом переноса (k+ 1, m+ 1)-го одноразряд- (n+1)-ro разряда результата устройства коного сумматора матрицы блоКа суммирова- торого соединен с выходом элемента ИЛИ, ния, в блок формирования частичных 25 входлогического нуля устройства соединен, произведений введены n(n+ 1)/2 элементов с вторым входом (1, и-1)-го одноразрядйого

ИЛИ-НЕ в виде треугольной матрицы и (и+1) сумматора матрицы. элементов НЕ, а в блок суммирования вве- . Нефиг. 1 приведена общая структурная дены (и+ 1) элементов И, (n-1) элементов схема умножения по модулю чисел Ферма;

ИЛИ-НЕ и элемент ИЛИ, причем s блоке 30 на фиг, 2 — функциональная схема блока формирования частичных произведений формирования частичных произведений; на входы (n+1) элементов НЕ. соединены соат- фиг. 3-функциональная схема блока сумми-: ветственна с входжи:р -х разрядов мнажи- роваиия частичных произведений. тепя ус.грайства (р - 1, ..., n+ 1), выход Матричный умножитель по модулю чи- . элемента НЕ (! - 2, ..., n+ 1) соединен с 35 сел Ферма содержит блок 1 формирований перв! !ми входами(1- j)-x элементов ИЛИ-HE частичных произведений, выходы которого матрйцы, вторые входы которых соедйнены соединены с входами блока 2 суммирования соответственно с входами j-x разрядов мно- частичных произведений (фиг. 1). жимога устройства, вход (n+ 1)-ro разряда " Ьлок 1 формирования частичных промножимого которого соединен с третьими 40 изведений (фиг. 2) содержит m элементов входами всех n(n+1)/2 элементов ИЛИ-HP 31-3 И, m элементов 4!-4П1 ИЛИ-НЕ, где: матрицы и первыми входами(n-1) элементов fA= п(п+ 1)/2, а также (и+1) инверторов

ИЛИ-НЕ блока Суммйрования; выходы зле- 5>-5n+>. входы которых подключейы к вхоментов И матрицы и элементов ИЛИ-HE дам (и+1) разрядов множителя и первым матрицы блока формйрования" чаСтичных 45 вхадам(п+1-!) элементов 31 — Зв Й, а ихвыхопроизведений соединены с входами соот- ды — к первым входам (l-1) элементов 41-4

" ветствующих весов одноразрядных сумма- ИЛИ-НЕ (! — номер разряда множителя, где торов матрицы блока суммирования, а в j=j+(n-1);j-входыразрядовмножимого,где блоке суммирования выхоД переноса (п, К)- J = 1-п), подключены к вторым входам(п+1-!) го одноразрядного сумматора матрйцы сое-: элементов 31-3 И и вторым входам.j элединен с вторым входом k-ro элемента ментов 41-4п ИЛИ-НЕ, третьи входы

ИЛИ-НЕ, выход которого соединен с входом n(n+1)/2 элементов 41-4п ИЛИ.-НЕ подклюпереноса (1; 1+1)-го одноразрядного сумма-: йены к. входу (и+1)-го разряда множимого.

" тора матрицы, выходы переносов(k, п-1)-го . Выходы элементов 314 И и 41- 4 ИЛИи (k, n)-го одноразрядных сумматоров мат- .55 НЕ, соответствующие !-разряду множимого. рицы соединены соответственно с вторым являются выходами (!+)-1)mod и-разрядов !входом (k+1, и-1)-го и входом переноса (k+1,: частичного произведения.

n)-го одноразрядного сумматоров матрицы. 8 блоке 2 суммирования частичных протретий; четвертый и пятый входы первого изведений (фиг. 3) J-разряды 1-частичных элемента ИЛИ-НЕ соединены саатветствен-. произведений {! = 1-3) подключены соответ1783513 ственно к )-входам одноразрядных сумматоров 61,), j-разряды I-частичных произведений (i = 4-n) подключены соответственно к вторым входам одноразрядных сумматоров

6i-2, ), J-разряды (n+1)-го частичного произведения подключены соответственно к вторым входам одноразрядных сумматоров

6n,), (j = 1-n). Выходы переносов одноразрядных сумматоров 6k, n (k = 1-(и-1)) подключены соответственно к первым входам k-элементов 71-7П-1 ИЛИ-НЕ, выходы которых подключены соответственно к входам переносов одноразрядных сумматоров

6k+1,1, выходы переносов одноразрядных сумматоров бп-1,) (j = 1-(n-1)) подключены к первому входу одноразрядных сумматоров бп-1, )+1.

В ыходы переносов одноразрядных сумматоров án, ) подключены соответственно к входам переносов одноразрядных сумматорОВ 6 . )+1. ВтОрЫЕ ВХОДЫ ЭЛЕМЕНТОВ 71 — 7n-1

ИЛИ-НЕ подключены к входу (п+ 1)-го разряда множимого. Третий, четвертый и пятый. входы элемента 71 ИЛИ-НЕ подключены к выходам элементов 81, 82, 8з И, входы которых попарно подключены к выходам инверторов 51, 52, 5з, подключенных также к трем входам элемента 84 И. Выходы элементов

84-8п И ПадКЛЮЧЕНЫ СООтВЕтСтВЕННО К третьим входам элементов 72 — 7П-2 ИЛИ-WE и первым входам элементов 8ь — 8 И соответственно. Вторые входы элементов 85-8л

И подключены соответственно к четвертым входам элементов 72-7п-2 ИЛИ-НЕ и соответственно к выходам инверторов 54 — 5n, Выход элемента 8П+1 И подключен к третьему входу элемента 7 -1 ИЛИ-НЕ и первому входу элемента 9 ИЛИ, второй вход которого подключен к входу (и+ 1)-ro разряда множимого, а выход является выходом (n+ 1)-го разряда результата.

Выходы одноразрядных сумматоров бп, 1, 6п. являются выходами j-разрядов результата, Второй вход одноразрядного

СуММатсра án-1, 1 ПОДКЛЮЧЕН К ВХОду ЛОГИческого нуля устройства, Устройство функционирует следующим образом.

Умножение выполняется, как и в обычном умножителе, "в столбик", но с учетом операций сдвига и сложения по модулю

Ферма.

Чтобы упростить реализацию устройства для формирования результата операции

X= А х В mod Рь Е1 = 2" + 1. n = 2 . множитель

В поступает в обычном двоичном коде в кольце целых чисел по модулю числа Ферма

F, а множимое А — в коде с уменьшением на единицу в кольце F1..

А -(А-1) (nod г=1

„. А4АЗА2А1

В4ВЗВ2В1 в обы45 А4В 1АЗВ1А2В 1А1 В1.+ А4В2АзВ2А2В2А1В2

А4вздзВзА2взА1вз

А4В4АзВ4А2В4А1В4 чном умножителе

А4В1АЗВ1А2В1А1В1 в умнажитЕлЕ

АзВ2АгВ2А182А4В2 по модулю чисА2ВЗА1ВЗА4ВЗАзВЗ ла Ферма F2= 17

А1 В4А4З4Аз В 4А2 В4

Таким образом, также используются блок 1 формирования частичных произведений и блок.2 суммирования частичных произведений. При этом в блоке 1 оставшиеся на месте относительно обычного умножите4

В этом случае умножение на степень двух выполняется посредством циклическо5, го сдвига на показатель этой степени влево с инверсией вновь вдвигаемых разрядов, а при суммировании в случае отсутствия переноса из старшего разряда к результату необходимо прибавить единицу, В случае

10 поступления нулевого операнда (лог, 1 в (и+1)-и разряде, остальные разряды — лог. Я) операция суммирования прерывается.

Различие представления множимого А и множителя В не влияет на универсальность

15 применения такого устройства, так как, как правило, множимое поступает из вычислительной системы, в которой используется такое же перекодированное представление, а ранее вычисленный множитель хранится в

20 ПЗУ, Результат также представлен с уменьшением на единицу, Нулевой результат образуется либо в случае А,+1 = 1, остальные разряды А равны лог. $, либо все разряды множителя равны

25 лог. ф, В этом случае все частичные произведения равны нулю, все переносы блокируются и на выходе образуется нулевое значение и разрядов результата Х1-Х, разряд Xn+1- =1.

При поступлении множителя с Bn+1= 1, В1= ... Bn= — р (число "минус один" в кольце F<) необходимо просто проинвертировать разряды множимого. Зто выполняется обнулекием первых и частичных произведений и

35 пропуском на выход только (и+1)-го частичного произведения.

Соответствие между обычным матричным умножителем и предложенным устройством можно проиллюстрировать для

40 n=4:

1783513 ля разряды частичных произведений формируются элементами 31-3m И, а вновь вдвигаемые" — с помощью элементов 4>-4m

ИЛИ-НЕ и инверторов 5i-5ï+I.

На третьи входы элементов ИЛИ-НЕ

41-4m поступает (n+ 1)-разряд множимого для обнуления всех выходов частичных пройзведений, если множимое представ. лено нулевым значением, как отмечено выше, . Далее суммирование частичных произведений производится матрицей сумматоров блока 2 с учетом необходимости приведения двоичных сумм по модулю числа Ферма. Первые три частичных произведения подаются на входы первой группы сумматоров 6i,1-61,п, остальные — на следующие (n-3) группы сумматоров 6,1- бк,п, где

k = 4-п. Последнее частичное произведение, соответствующее инверсии всех разрядов множимого, поступает на последнюю группу сумматоров 6п,1 — 6п.п, Поскольку промежуточные разряды сумм передаются параллельно с поразряд: ными переносами, сложение итогового слова сумм и слова переносов происходит на группе сумматоров 6п-1,1-6п-1.п, переносы в который подключены, как в обычном сумматоре. Сумматоры бп.1 — 6n.п производят окончательную .коррекцию. результата прибавлением инвертированного переноса при ненулевом множимом и множителе. не равном "нулю" йли "минус единице" в коль-. це Еь либо только пропускают инверсные разряды ненулевого множимого на выход в случае, если множитель равен "минус единице", Если Ап+1= 1, либо В 1= B2= „. = Bn= JII, то элементами 7i- 7п-> и 8>-8п+1 блокируются все переносы и обеспечивается нулевой результат на входах последней группы сумма торов бп,1-6n,ï. В и ротивном случае элементами 71-7п-1 обеспечивается передача инвертированного переноса на вход переноса сумматоров следующей группы.

Через элементы 81-8п+1 обеспечивается передача-разрешения суммирования с учетом переноса, если очередное частичное произведение не равно нулю (соответствующий ему разряд множителя равен лог. 1), а также если результат предыдущего промежуточного суммирования не равен нулю;

Таким образом, устройство обеспечивает выполнение перемножения двоичных чисел по модулю соответствующего числа

Ферма, если множимое представлено в коде с уменьшением на единицу по этому модулю. При этом результат будет совпадать с результатом обычного двоичного умножения, если только множимое и множитель в сумматоре содержат не более и двоичных разрядов.

Формула изобретения

5, .Матричный умножитель по модулю чисел Ферма, содержащий блок суммирования, состоящий из матрицы и х п одноразрядных сумматоров, и блок формирования частичйых произведений, состоя10 щий из треугольной матрицы n(n+ 1)/2 элементов И, первый вход (J- J)-ro элемента

И матрицы которого соединен с входом J-ro разряда множимого устройства (! — номер строки матрицы, J — номер столбца матрицы, I, J = 1, ..., п), вход I-го разряда множителя которого соединен с вторым входом (1, ))-го элемента И матрицы блока .формирования частичных произведений, выходы (1;Д-х элементов И матрицы которого соединены со2п ответственно с входами переноса (I..1)-õ одноразрядных сумматоров матрицы блока суммирования, первые входы (i, 1)-õ одноразрядных сумматоров матрицы, кроме (i, 1)-го одноразрядного сумматора; соедине25 ны соответственно C выходами (2, J)-х элементов И матрицы блока формирования частичных произведений, выход суммы (i, !

+го одноразрядного сумматора матрицы блока суммирования соединен с первым

3Q входом (I, k+1)- ro одноразрядного сумматора матрицы блока суммирования (k = 1, ..., п-1), выход переноса(к, m)-го одноразрядного сумматора матрицы которого соединен с входом переноса (k+1, m+1)-ro однораз-.

35 рядного сумматора матрицы блока суммирования, отличающийся тем, что, с целью расширения функционайьных возможностей путем выполнения умножения

{n+1)-разрядных двоичных чиеел по модулю

4О чисел Ферма F 2"+1, п - 2 в блок формирования частичных произведений введены

n(n+1)/2 элементов ИЛИ-НЕ е виде треугольной матрицы и n+1 элементов НЕ,.а,в блок суммирования введены и+1 элементов

45 И, и-1 элементов ИЛИ-НЕ и элемент ИЛИ, причем е блоке формирования частичных произведений входы и+1 элементов НЕ соединены соответственно с входами р-х разрядов множителя устройства (р 1, ..., n+1); выход I-го элемента НЕ (i 2, ..., n+1) соединен с первыми входами (I. J)-x элементов

ИЛИ-НЕ матрицы, вторые входы которых соединены соответственно с входами )-х разрядов множимого устройства, вход (и+1)го разряда множимого которого соединен с входами всех n(n+1)/2 элементов ИЛИ-НЕ матрицы и первыми входами и-1 элементов

ИЛИ-НЕ блока суммирования, выходы элементов И матрицы и элементов ИЛИ-НЕ матрицы блока формирования частичных

1783513

9 произведений соединены с входами соот- второго и четвертого элементов И, выход ветствующих весов одноразрядных сумма- третьего элемента HE соединен с вторыми торов матрицы блока суммирования, а в входами первого и третьего элементов И и блоке суммирования выход переноса (n, k)- третьим входом четвертого элемента И, выго одноразрядного сумматора матрицы сое- 5 ход t-ro элемента И (t = 4, ..., n) соединен с динен с вторым входом k-ro элемента третьим входом(t-2)-го элемента ИЛИ-НЕ и

ИЛИ-НЕ. выход которого соединен с входом первым входом (с+1)-го, элемента И, второй переноса (1, 1+1)-го одноразрядного сумма- вход которого соединен с четвертым входом тора матрицы,"входы переносов (k, n-1)-го и. (t-2)-го элемента ИЛИ-НЕ и выходом t-ro эле(k, n)-ro одноразрядных сумматоров матри- 1р мента HE блока формирования частичных цы соединены соответственно с вторым вхо- произведений, выход (n+1)-го элемента И дом (k+1, и-1)-го и входом переноса (k+1, . соединенстретьим,входом(п-1)-гоэлемента и)-ro одноразрядных сумматоров матрицы, ИЛИ-НЕ и вторым входом элемента ИЛИ, третий, четвертый и пятый входы первого выходы суммы(1, n)-х одноразрядных сумэлемента WIN-HE соединены соответствен- 15 маторов матрйцы соединены с выходами и но с выходами первого, второго и третьего: разрядов результата устройства, выход элементов И, первые входы первого; второ- (и+ 1)-го разряда результата которого соего и четвертого элементов И соединены с динен с вьаодом элемейта ИЛИ, вход ловыходом первого элемента НЕ, выход вто- гического нуля устройства соединен с рого элемента НЕ соединен с первым вхо- 2р вторым входом (1, и-1)-го одноразрядного дом третьего элемента И и вторыми входами сумматора матрицы.

1783513

Oq

1783513, « Ъ !

Составитель А.Горшков редактор Г.Бельская Техред М.Моргент«ал . Корректор О.Густи

Заказ 4516 :: Тираж,:: . :: :,:: - Подписное

ВНИИПИ Государственного комитета по.изобретениям и открытиям при ГКЙТ СССР

113035; Москва, Ж-35; Раушская наб„4/5

Производственно-издательский комбинат "Патент", r, Ужгород, ул.Гагарина, 101 .-" 5