Матричный умножитель по модулю чисел Ферма Советский патент 1992 года по МПК G06F7/49 

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

Известны матричные умножители с приведением результата по модулю (авт. св. № 1170450, кл. G 06 F 7/49, авт. св. № 1179322, кл. G 06 F 7/52, авт. св. № 1244662, кл. G 06 F 7/52; авт. св. № 1160398, кл. G 06 F 7/49).

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

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

блок формирования частичных произведений и блок суммирования частичных произведений.

Недостатком известного устройства является невозможность его использования для вычисления произведений (п-И)-разряд- ных чисел по модулю чисел Ферма Ft 2п+1, n 2l, t 04.

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

,п 21л 04.

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

со ел

со

щий из треугольной матрицы п(п+2}/2 элементов И, первый вход (1, j)-ro элемента И матрицы которого соединен с входом j-ro разряда множимого устройства (I - номер строки матрицы; j - номер столбца матрицы; I, j - 1,.... п), вход 1-го множителя которого соединен с вторым входом (i, j)-ro элемента И матрицы блока формирования частичных произведений, выходы (1. j)-x элементов И матрицы которого соединены соответствен- но с входам переноса (I, 1)-х одноразрядных сумматоров матрицы, кроме (1. 1}то одноразрядного сумматора, входы которого соединены соответственно с выходами (2, j)-x элементов И матрицы блокад формирова- ния частичных произведений, выход суммы (i, k)-ro одноразрядного сумматора матрицы блока суммирования соединен с первым входом (i, одноразрядного сумматора матрицы блока суммирования (k 1

п-1), выход переноса (k. m)-ro одноразрядного сумматора матрицы которого соединен с входом переноса (k+ 1, m+ 1)-го одноразрядного сумматора матрицы блока суммирования, в блок формирования частичных произведений введены п(п+ 1)/2 элементов ИЛИ-НЕ в виде треугольной матрицы и (п-И) элементов НЕ, а в блок суммирования введены (п+ 1} элементов И, (п-1) элементов ИЛИ-НЕ и элемент ИЛИ. причем в блоке формирования частичных произведений входы (п+1) элементов НЕ соединены соот- ветствен но с входами р-х разрядов множителя устройства (р 1 п+ 1). выход I

элемента НЕ (I 2 п+ 1) соединен с

первыми входами (I- )-х элементов ИЛИ-НЕ матрицы, вторые входы которых соединены соответственно с входами j-x разрядов множимого устройства, вход (п+ 1)-го разряда множимого которого соединен с третьими входами всех. п(п+1)/2 элементов ИЛИ-НЕ0 матрицы и первыми входами (п-1) элементов ИЛИ-НЕ блока суммирования, выходы элементов И матрицы и элементов ИЛИ-НЕ матрицы блока формирования частичных произведений соединены с входами соответствующих весов одноразрядных сумматоров матрицы блока суммирования, а в блоке суммирования выход переноса (n, k)- го одноразрядного сумматора матрицы соединен с вторым входом k-ro элемента ИЛИ-НЕ, выход которого соединён с входом переноса (1, k+1)-ro одноразрядного сумматора матрицы, выходы переносов 0с, п-1)-го и (k, n)-ro одноразрядных сумматоров мат

рицы соединены соответственно с вторым входом (k+1, n-1)-ro и входом переноса (k+1, п)-го одноразрядного сумматоров матрицы, третий, четвертый и пятый входы первого элемента ИЛИ-НЕ соединены сбответствен0 5 0

5 о

5

о с

0

5

но с выходами Первого, второго и третьего элементов И, первые входы первого, второго и четвертого элементов И соединены с выходом первого элемента НЕ, выход второго элемента НЕ соединен с первым входом третьего элемента И и вторыми входами второго и четвертого элементов И, выход третьего элемента НЕ соединен с вторыми входами первого и третьего элементов И и третьим входом четвертого элемента И, выход q-ro элемента И (w - 4, .,„ п) соединен с третьим входом (q-2)-ro элемента ИЛИ-НЕ и первым входом (q+1)-ro элемента И, второй вход которого соединен с четвертым входом (q-2)-ro элемента ИЛИ-НЕ и выходом q-ro элемента НЕ блока формирования частичных произведений, выход (п+1)-го элемента И соединен с третьим входом (п.1)-го элемента ИЛИ-НЕ и вторым входом элемента ИЛИ, выходы суммы (i,n)-x одноразрядных сумматоров матрицы соединены с выходами п разрядов результата устройства, выход (п-И)-го разряда результата устройства которого соединен с выходом элемента ИЛИ, вход логического нуля устройства соединен с вторым входом (1. п-1)-го одноразрядного сумматора матрицы.

На фиг. 1 приведена общая структурная схема умножения по модулю чисел Ферма; на фиг, 2 - функциональная схема блока формирования частичных произведений; на фиг. 3 -функциональная схема блока суммирования частичных произведений.

Матричный умножитель по модулю чисел Ферма содержит блок 1 формирований частичных произведений, выходы которого соединены с входами блока 2 суммирования частичных произведений (фиг. 1).

Блок 1 формирования частичных произведений (фиг. 2) содержит т элементов 3i-3m И, гл элементов 4i-4m МЛИ-НЕ, где m n(n+ )/2, а также (п+1) инверторов 5t-5tvH. входы которых подключены к входам (п+1) разрядов множителя и первым входам (n+1-l) элементов 3i-3m И, а их выходы - к первым входам (1-1) элементов 4i-4m ИЛИ-НЕ (I - номер разряда множителя, где (n-1); j - входы разрядов множимого, где j 1-n), подключены к вторым входам (n+1-j) элементов 3i-3m И и вторым входам j элементов 4i-4m ИЛИ-НЕ, третьи входы п(п+1)/2 элементов 4i-4m ИЛИ-НЕ подключены к входу (п+1)-го разряда множимого. Выходы элементов 3i-3m И и 4i-4m ИЛИ- НЕ, соответствующие 1-разряду множимого, являются выходами (f+j-1)mod п-разрядов I- частичного произведения.

В блоке 2 суммирования частичных произведений (фиг. 3) j-разряды 1-частичных произведений (I 1-3) подключены соответственно к i-входам одноразрядных сумматоров 6ij, j-разряды l-частичных произведений (I 4-п) подключены соответственно к вторым входам одноразрядных сумматоров 6i-2, j, j-разряды (п+1)-го частичного произве- дения подключены соответственно к вторым входам одноразрядных сумматоров 6n,j, 0 )- Выходы переносов одноразрядных сумматоров 6k, n (k 1-()) подключены соответственно к первым входам k-элемен- тов 1-7п-1 ИЛИ-НЕ, выходы которых подключены соответственно к входам переносов одноразрядных сумматоров 6k+i,i, выходы переносов одноразрядных сумматоров 6n-i,j 0 1-(п-1}) подключены к первому входу одноразрядных сумматоров

6n-1, J+1.

В ыходы переносов одноразрядных сумматоров 6n, j подключены соответственно к входам переносов одноразрядных суммато- ров 6П. j-t-i. Вторые входы элементов 7i-7n-i ИЛИ-НЕ подключены к входу (п+ 1)-го разряда множимого. Третий, четвертый и пятый входы элемента 7i ИЛИ-НЕ подключены к выходам элементов 8i, 82, 83 И, входы кото- рых попарно подключены к выходам инверторов 5i, 62, 5з. подключенных также к трем входам элемента 84 И. Выходы элементов И подключены соответственно к третьим входам элементов ИЛИ-НЕ и первым входам элементов 8s-8n И соответственно. Вторые входы элементов И подключены соответственно к четвертым входам элементов 72-7п-2 ИЛИ-НЕ и соответственно к выходам инверторов . Выход элемента 8п+1 И подключен к третьему входу элемента 7п-1 ИЛИ-НЕ и первому входу элемента 9 ИЛИ, второй вход которого подключен к входу (п+ 1)-го разряда множимого, а выход является вы- ходом (п+ 1)-го разряда результата. Выходы одноразрядных сумматоров 6п, 1, 6n. n являются выходами j-разрядов результата. Второй вход одноразрядного сумматора 6п-1, 1 подключен к входу логи- ческого нуля устройства.

Устройство функционирует следующим образом.

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

Чтобы упростить реализацию устройства для формирования результата операции Х А х В mod Ft, Ft 2n + 1, n 2l. множитель В поступает в обычном двоичном коде в кольце целых чисел по модулю числа Ферма Ft, а множимое А - в коде с уменьшением на единицу в кольце Ft:

A-(A-1)mod Ft.

В этом случае умножение на степень двух выполняется посредством циклического сдвига на показатель этой степени влево с инверсией вновь вдвигаемых разрядов, а при суммировании в случае отсутствия переноса из старшего разряда к результату необходимо прибавить единицу. В случае поступления нулевого операнда (лог. 1 в (л+1)-м разряде, остальные разряды - лог. 0) операция суммирования прерывается.

Различие представления множимого А и множителя В не влияет на универсальность применения такого устройства, так как, как правило, множимое поступает из вычислительной системы, в которой используется такое же перекодированное представление, а ранее вычисленный множитель хранится в ПЗУ. Результат также представлен с уменьшением на единицу.

Нулевой результат образуется либо в случае Ап-и 1, остальные разряды А равны лог. 0, либо все разряды множителя равны лог. р. В этом случае все частичные произведения равны нулю, все переносы блокируются и на выходе образуется нулевое значение n разрядов результата Xi-Xn, разряд Хп+1 1.

При поступлении множителя с Вп+1 1, Bi... (число минус один в кольце Ft) необходимо просто проинвертировать разряды множимого. Это выполняется обнулением первых n частичных произведений и пропуском на выход только (п+1)-го частичного произведения.

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

„ АлАзАгАч

64636281

A4BiA3BiA2BiAiBi 4- А4В2АзВ2А2В2А1В2

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

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

A4BiA3BiA2BiAiBi в умножителе , АзВ2А2В2AJВ2А4В2 по модулю чис- AZВзА1 ВзА4ВзАзВз ла Ферма Fa 17

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

Таким образом, также используются блок 1 формирования частичных произведений и блок 2 суммирования частичных произведений. При этом в блоке 1 оставшиеся на месте относительно обычного умножителя разряды частичных произведений формируются элементами 3i-3m И, а вновь вдвигаемые - с помощью элементов 4i-4m ИЛИ-НЕ и инверторов 5i-5n-M.

На третьи входы элементов ИЛИ-НЕ 5 4i-4m поступает (п+ 1)разряд множимого для обнуления всех выходов частичных произведений, если множимое представ- лено нулевым значением, как отмечено выше.10

Далее суммирование частичных произведений производится матрицей сумматоров блока 2 с учетом необходимости приведения двоичных сумм по модулю числа Ферма. Первые три частичных произве- 15 дения подаются на входы первой группы сумматоров 6i.i-6i.ni остальные - на следующие (n-З) группы сумматоров 6k, 1- 6k.n, где k 4-п. Последнее частичное произведение, соответствующее инверсии всех разрядов 20 множимого, поступает на последнюю группу сумматоров 6n.1-6n.n.

Поскольку промежуточные разряды сумм передаются параллельно с поразрядными переносами, сложение итогового ело- 25 ва сумм и слова переносов происходит на группе сумматоров 6n-i.i-6n-i.n. переносы в который подключены, как в обычном сумматоре. Сумматоры 6п.1-6п,п производят окончательную коррекцию результата зо прибавлением инвертированного переноса при ненулевом множимом и множителе, не равном нулю или минус единице в кольце Ft, либо только пропускают инверсные разряды ненулевого множимого на выход в 35 случае, если множитель равен минус единице.

Если Ап-и 1, либо Bi 62 ... , то элементами 7i- 7п-1 и 8i-8n+i блокируются все переносы и обеспечивается нулевой ре- дп зультат на входах последней группы сумма- торов 6п.1-6п.п. В противном случае элементами 7i-7n-i обеспечивается передача инвертированного переноса на вход переноса сумматоров следующей группы. 4g Через элементы 8i-8n+i обеспечивается передача разрешения суммирования с учетом переноса, если очередное частичное произведение не равно нулю (соответствующий ему разряд множителя равен лог. 1), а также ,.« если результат предыдущего промежуточного суммирования не равен нулю.

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

55

5 0

5 о 5

п g «

5

сумматоре содержат не более п двоичных разрядов.

Формула изобретения Матричный умножитель по модулю чисел Ферма, содержащий блок суммирования, состоящий из матрицы n x n одноразрядных сумматоров, и блок формирования частичных произведений, состоящий из треугольной матрицы nfn+ 1)/2 элементов И, первый вход (j- j)-ro элемента И матрицы которого соединен с входом j-ro разряда множимого устройства (1 - номер строки матрицы, J - номер столбца матрицы, I, J 1, ..., п), вход 1-го разряда множителя которого соединен с вторым входом (I, J)-ro элемента И матрицы блока формирования частичных произведений, выходы (1,-j)-x элементов И матрицы которого соединены соответственно с входами переноса (i. 1)-x одноразрядных сумматоров матрицы блока суммирования, первые входы (I. 1)-х одноразрядных сумматоров матрицы, кроме (I, 1)-го одноразрядного сумматора, соединены соответственно с выходами (2, j)-x элементов И матрицы блока формирования частичных произведений, выход суммы (I, к)-го одноразрядного сумматора матрицы блока суммирования соединен с первым входом (i, k+1)-ro одноразрядного сумматора матрицы блока суммирования (к 1, .... п-1). выход переноса (k, mfro одноразрядного сумматора матрицы которого соединен с входом переноса (k+1m+1)-ro одноразрядного сумматора матрицы блока суммирования, отличающийся тем, что, с целью расширения функциональных возможностей путем выполнения умножения (п+1)-разрядных двоичных чисел по модулю чисел Ферма Ft 2n+1, n в блок формирования частичных произведений введены п(п+1)/2 элементов ИЛИ-НЕ в виде треугольной матрицы и п+1 элементов НЕ. а в блок суммирования введены п+1 элементов И, п-1 элементов ИЛИ-ЙЁ и элемент ИЛИ, причем в блоке формирования частичных произведений входы п+1 элементов НЕ соединены соответственно с входами р-х разрядов множителя устройства (р 1п+1),

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

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

второго и четвертого элементов И, выход третьего элемента НЕ соединен с вторыми входами первого и третьего элементов И и третьим входом четвертого элемента И, выход t-ro элемента И (t 4п) соединен с

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

втррым входом (1, п-1)-го одноразрядного сумматора матрицы.

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

А

t

X

h+i.

, 1

Ifff

М

Ъ

I

t s v

i v. v fe fc-fcMX