Устройство для умножения по модулю М=2 @ -1 Советский патент 1988 года по МПК G06F7/49 

оо с

00

оо со со

Изобретение относится к вычисли тельной технике и информационно из - мерительным системам и может быть ис- пользовано в устройствах для цифро

вой обработки, сигналов, в частности, для цифровой обработки изображений , а также в устройствах кодирования, принцип действия которых базируется на теории конечных колец и полей Га- луа.

Цель изобретения - повышение бысг родействия устройства.

На фиг.1 приведена функциональная схема устройства для умножения по мо дулю W-2 -1; на фиг.2 - функциональ- ная схема многовходового (п-входово- го) одноразрядного сумматора; на фиг. 3 функциональная схема комму татора;на фиг.4 и 5 -функциональная схема блока формирования частичных произведений; на фиг.6 - функциональная схема узла приоритета; на фиг. 7 фу1лсциональная схема сдвигателя; на фиг. 8 - схеМ) умножителей на степе- ни двойки; на фиг.9 функциональная схема блока суммирования частичных произведений; на фиг. 0 - функцио- нальная схема блока коррекции.

Устройство для умножения по моду- лго 1 (фиг.1) содержит группу входов 1,, 1,,...,1„ прямого значения операнда Ь,, Ь,..., Ь,, группу входов 2,, 2j,..., 2 инверсного значения операнда Ь, , Ь ,.. ., Ь, груп- пу входов ЗУ , 3j ,..., 3 (прямого зна чения) второго операнда а

а, ком гутатор А, блок 5 формирования частичных произведений, блок 6 суммирования частичных произведений, блок 7 коррекции, коммутатор 8, мно- говходовой одноразрядньй сумматор 9, группу элементов НЕ 10,, 10,...,10 вых:оды 11,, 11,..., ll,, Значения операндов могут быть выбраны из ре- гистров (при этом прямые и и нверсные вьгл;оды одного регистра могут быть соединены с входами 1,,..,, 1„и2,, ...,2), и в регистр же может быть занесено значение результата с выхо- дов 1 1,..., 11 п. Сумматор 9 своими входами 12,, 122,..., 12„ соединен с входами 1,., 1,..., In а выходом 13 старшего разряда - с управляющими входами KOhiMyTaTOpoB 4 и 8. Инфор- мационные входы коммутатора 4 соединены с входами 14, 1)И 2,, 22,..., 2„, а выходы 14,, 14,..., 14 - с первой группой входов блока 5,

вторая группа входов которого соеди нена с входами 3,, 32, ходы 15,, ISj,..., 15X (где k п, п+1

, 3, а вы при п

четном, k

при

п - нечетном) подключены к входам блока 6, выходы 16,, 16,,..., 16 .которого подключены к входам блока 7, выходы 17|, 17 ,.. ., 17 которого соединены с входами элементов НЕ Ю lOj,..., 10„ и первой группой информационных входов коммутатора 8, вторая группа входов которого подключена к выходам элементов НЕ Ю,, 10,

п

Многовходовой одноразрядный сум-

матор 9 (фиг.2) построен на двоичных сумматорах 18.

Коммутатор 4 (фиг.З) содержит эле мента И 19,, 19,..., 19„, 20,, 20, ..., 20, ИЛИ 21,, 21,,..., 21„, НЕ 22. Коммутатор 8 строится аналогично.,

Блок 5 формирования частичных про изведений (фиг.4 и 5) содержит узлы 23,, 23, 23,..., 23ц приоритета, группы сумматоров 24 по модулю два, сдвигатели 254, 25ц. Совокупности узлов 23 и сумматоров 24 определяют управляющие коды, которые поступают на зшравляющие коды сдвига- телей 25, на информационные входы которых подается с входов 3,, 3,..., 3 код операнда а, aj,..., а„. Каждый S-й узел 23 (фиг.6), где 6 1, 2, ..., k, имеет входы 26д,,..., 2б5к и выходы 27,у.. ., 27g,j . Узел 23д содержит элементы НЕ 28,,..., 28,, И 29, ,..., 29.,.

Каждьй сдвигатель 25 (фиг.7) содержит группы элементов И 30, умножители 31 на степени двойки и группу элементов ИЛИ 32.

Блок 6 суммирования частичных произведений (фиг.9) имеет k п-разряд- ных входов и содержит двоичные су( маторы 33 и узел 34 ускоренного переноса.

Блок 7 коррекции (фиг.10) содержит двоичные сумматоры 35, узел 36 ускоренного переноса и элемент И 37. В совокупности блоки 6 и 7 Лредставля- ют собой сумматор k чисел по модулю М.

, Произведением чисел а и Ь по модулю М Q а-Ь (mod М) называется остаток от деления обычного произведения а«Ь на значение модуля М.

Принцип быстрого умножения заклю чается в следующем.

Для М 2 - 1 справедливо равенст во: а, т.е. отрицательное число в кольце 2ц (множество целых чисел Го, 1, 2,..., М- П с рассматриваемы ми на нем операциями сложения и умно жения по модулю М), представленное в двоичной системе счисления, получает ся в результате инверсии соответст- вующего ему положительного числа. От рицательные числа оказываются зако дированными целыми числами, большими

М,

. Например, для Z, Z- можно записать соответствие: , 1,, , , 5---2, б--1. В двоич-- ной системе счисления эти числа мож но представить, трехразрядными двоич- ными числами: 1 1 О 6; 101 5; 011 100 - 4, значит умножение можно проводить по следующее му выражению:

а-Ь (mod M) () (mod М). (1)

Результат умножения по модулю М 2 1 имеет число разрядов, равное числу разрядов каждого из сомножите лей.

Очевидно, что инверсия одного из сомножителей согласно (1) целесооб разна лишь в том случае, если этот сомножитель (в выражении (1) число Ь) имеет больше половины единиц в значащих.разрядах. Управление работой коммутатора 4 осуществляется с помощью п-входового одноразрядного с.умматора 9, на котором формируется сумма разрядов множителя. Если число единиц в разрядах множителя больше п/2, значение разряда на выхо

де сумматора 9 (т , где

скобки обозначают округление до ближайшего большего целого числа) равно единице. Значения младших раз рядов не используются. Значение ряда сумматора 9 является управляю щим сигналом для коммутатора 4. С выходов коммутатора 4 прямое или ин- вареное значение множителя подается на входы блока 5, на другие входы которого подается множимое с входов 3, 3j,..., 3„. Блок 5 формирует k слов частичных произведений, которые по- даются на выходы J 5, , 15,..., 15 , (каждый выход поразрядный). Слова частичных произведений суммируются

, Q

5

0

5

30

35

с помощью блока 6 и корректируются блоком 7, на выходах 17, 17,... , 17j которого формируются разряды слова суммы частичных произведений. С этих выходов прямое значение слова суммы частичных произведений посту пает на первые входы коммутатора 8. Кроме того, сло-во суммы частичных произведений инвертируется с помощью элементов НЕ 10,, 10,..., 10„ и по- . дается на вторые :входы коммутатора 8. Управляется последний с помощью того же управляющего сигнала, что и коммутатор 4. Таким образом, если произ водится инверсия множителя с помощью коммутатора 4, осуществляется инверсия результата умножения с помощью коммутатора 8, как того требует выражение (1). С выходов коммутатора 8 значение произведения по модулюМ 2 -1 подается на выходы 1 1 устройства.

Пример. При работе блока 5 пусть необходимо умножить два числа а 1101011 (п 7 и М 2 1) и b 0011011. Умножение проводится согласно (1). Значит слово а подается на входы 3,, 3,..., 3, инверсное слово b 1100100 подается на выходы 14j, 14;,..., 14„. Первые (младшие) k разрядов поступают на входы узла 23. Задачей узла 23 является выбор единицы, которая встречается впервые в слове, поступающем на входы этого уз-

50

55

ла. На входы 26,,, 26

12

26,

(7 + 1)/2 4) узла 23, подается слово 0010. На выходах 27

(k

н

27

14

имеют 0010 (в этом слове только одна 40 единица, поэтому входное значение

совпадает с выходным). Это слово яв-. ляется управляющим для сдвигатепя 25, . На первые входы сумматоров 24,,- 24,5 модулю два подается слово дс 010, а на вторые входы сумматоров

24„-24, - слово 010 с выходов

27,227, узла 23, . На вход 26. узла 23 подается значение пятого разряда,т.е. нуль. Значит на сумматорах 24„ -24, суммируются по модулю два слова 010 и 010, что в результате дает слово 000. В результате на входах и выходах узла 23j, имеют нулевое слово 0000, которое также является управляющим для сдвигателя 25. На первые входы сумматоров 242, гъ ° модулю два подается слово 000 с выходов сумматоров 24,2 и 24,3 первые два разряда и третий разряд с выхода 14с-, На вторые

входы сумматоров 2A,j -24, подается слово 000 с выходов 21 -27,,4 узла 23, На вход узла 23 подается значение, шестого разряда, т.е. единица. Значит на сумматорах 24, 24,3 суммируются по модулю два слова 000 и 000, что в результате дает слово 000, В результате на входах узла 23, находится слово 0001 и на выходе точно такое же слово 0001, которое является управляющим для сдвигателя 25,. На первйе входы сумматоров 24,, -24, по модулю два подается слово 001 с выходов сумматоров и первые ., два разряда и третий (k+2)-ft разряд с выхода 14g. На вторые входы сумма- . торов 24,, -24,5 подается 00-1 с выходов 27,2 27,4 узла 23,. На вход 2644 ,10

20

9ТОГО узла подается значение последнего, т.е. седьмого раяряда, равное единице. На сумматорах 24,, -24 суьг- мируются по модулю два слова 001 и 001, что в результате дает слово 000. В результате на входах узла 23 нахо-25 входами блока суммирования частич- дится слово 0001 и на выходе точно ных произведений, выходы которого такое же слово 0001, которое является управляющим для сдвигателя 25.

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

30

Схема узла 23 осуществляет функцию выбора первой единицы в кодовом слове, которое поступает на входы 265, , ,..., 26. Умножители 31 на-степени двойки осуществляют умножение множимого на степень двойки по модулю М, что является обычным циклическим сдвигом и эти умножители представляют собой простую перекоммутацию проводов. На фиг.8 приведена такая перекоммутация для случая М 2-1. Умножитель 31д, на степень двойки осуществляет умножение множимого на 2 , умножитель З. - на 2,

35

умножитель

31 - на

i-K-I

Присоединены с входами блока коррекции, отличающееся тем, что, с целью повьш1ения быстродействия, в него введены два коммутатора, многовхо- довой одноразрядный сумматор и группа элементов НЕ, причем другая группа входов блока формирования частичных произведений соединена с выходами первого коммутатора,первая и вторая группы информационных входов которого соединены соответственно с группой входов прямого значения и группой входов инверсного.значения другого операнда устройства, в| 1ходы блока коррекции соединены с первой группой информационных входов второго коммутатора и входами соответствующих элементов НЕ группы, выходы которых соединены с второй группой информационных входов второго коммутатора, выходы которого являются выходами устройства, а управляющий вход соединен с управляющим входом первого коммутатора и выходом старшего разряда многовходового одноразрядного сумматора, входы которого соединены с первой группой вхо.дов информационных входов первого коммутатора

чем умножение проводится по модулю М. В результате происходит циклический сдвиг множимого с помощью управляющего слова, поступающего на входь элементов ИЛИ 32;,, 32,-,..., 32,-. Если в управляющем слове j-и разряд равен единице, работает линейка элемен-

тов и 30, 31,

30 ,..., 30й1 умножитель нн степень двойки, который осуществляет умножения на . Результат умно.жения подается на выходы сдвигателя 25 через элементы ИЛИ 32. На выходах остальных умножителей на степени двойки (умножители 31sj , 3155, ЗЦц) - сигналы, соответствующие значению логического нуля.

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

Блок 6 реализует операцию суммы по модулю М kn-разрядных слов частичных произведений. Блок 7 коррекции устра- няВт неоднозначность представления нуля О (mod М 2 - I). В двоичной системе счисления нуль может представляться нулевым кодовым словом 000...О, а также словом 111...1 2 т 1. Блок 7 коррекции преобразует единичное слово в нулевое.

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

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

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

0

5

5

0

5

соединены с входами блока коррекции, отличающееся тем, что, с целью повьш1ения быстродействия, в него введены два коммутатора, многовхо- довой одноразрядный сумматор и группа элементов НЕ, причем другая группа входов блока формирования частичных произведений соединена с выходами первого коммутатора,первая и вторая группы информационных входов которого соединены соответственно с группой входов прямого значения и группой входов инверсного.значения другого операнда устройства, в| 1ходы ,. блока коррекции соединены с первой группой информационных входов второго коммутатора и входами соответствующих элементов НЕ группы, выходы которых соединены с второй группой информационных входов второго коммутатора, выходы которого являются выходами устройства, а управляющий вход соединен с управляющим входом первого коммутатора и выходом старшего разряда многовходового одноразрядного сумматора, входы которого соединены с первой группой вхо.дов информационных входов первого коммутатора.

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

сдвигателей (k -5- при n - четном 1

, п+1

к. при n - нечетном; п разрядность операндов), причем входы первого узла пр 1оритета соединены с входами первой группы блока с первого по , входы узла приоритета (i « 2,..., k) соединены с выходами . сумматоров по модулю два (1-1)-й группы и (k+i-l)-M входом первой группы блока, первый вход сум матера по модулю два (1-1)-й группы (J 1,..., k-1) соединен с (j+l)-M

выходом (i-l)-ro узла приоритета, второй вход сумматора по модулю два второй группы соединен с ) входом первой группы блока, второй вход сумматора по модулю два 1-й группы (г I,..., k-2 1 « 2, ..., k-1) соединен с выходом (г+1)-го сумматора по модулю два (1-1)-й группы, выходы узлов приоритета соедине- ны с управляющими входами соответствующих сдвигателей, информационные входы которых соединены с входами второй групшл блока, а выходы - с выходами блока.

и9.3

%/J

d Vлй

Л.Г о-

л

Фиг. 7

. й«-Н 4 t

2 %

Vuz.B

Фиг.9

Ф«г. Ю