Устройство для умножения в конечных полях

 

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В ПОЛЯХ, содержащее первый, второй и третий регистры сдвига, первую и вторую группы элементов ИЛИ, первую группу элементов И, первую группу сумматоров по модулю два, причем первые входы элементов ИЛИ первой группы соединены соответственно с входами коэффициентов множителя устройства, выходы разрядов третьего регистра сдвига являются выходами устройства, выходы элементов ИЛИ первой группы соединены соответственно с входами разрядов первого регистра сдвига, выход (N-l)-ro разряда первого регистра сдвига соединен с вторым входом (N-2)-rO элемента ИЛИ первой группы , выход нулевого разряда первого регистра сдвига соединен с вторым входом (N-l)-ro элемента ИЛИ первой группы, с первыми входами элементов И первой группы , выходы которых, соединены соответственно с первымивходами сумматоров по модулю два первой группы, вторые входы которых соединены соответственно с выходами разрядов третьего регистра сдвига, выходы сумматоров по модулю два первой группы соединены соответственно с входами разрядов третьего регистра сдвига, первые входы элементов ИЛИ второй группы соединены соответственно с входами коэффициентов множимого устройства, выходы элементов ИЛИ второй группы соединены соответственно с входами разрядов второго регистра сдвига, выходы разрядов второго регистра сдвига соединены соответственно с вторыми входами элементов И первой группы , отличающееся тем, что, с целью расщирения области применения за счет обеспечения умножения полиномов в поле, порожденном любым неприводимым многочленом , степень которого не превышает заданной , в него введены регистры многочлена, блок определения старшего нулевого разряда , вторая и третья группы элементов И, N переключателей, вторая группа сумматоров по модулю два, причем входы разрядов регистра многочлена соединены соответственно с входами неприводимого многочлена устройства, выходы регистра многочлена соединены соответственно с входами блока определения старшего ненулевого разряда , выходы разрядов с первого по I ( Ы-1)-й регистра многочлена соединены соответственно с первыми входами элементов (П И второй группы, выходы разрядов с нулевого по (К1-2)-й второго регистра сдвига соединены соответственно с первыми входами элементов И с первого по (М-1)-й третьей группы и первыми информационными входами переключателей с первого по (Н-1)-й выход (N-l)-ro разряда второго регистра сдвига соединен с первым информационным входом N-ro переключателя, О5 второй информационный вход которого соединен с шиной нулевого потенциала устройства , выход N-ro переключателя соединен с вторым входом (N-l)-ro элемента 00 И второй группы и вторым информацион4 ным входом (N-l)-ro переключателя, выход первого переключателя соединен с вторым входом нулевого элемента ИЛИ второй группы, выходы элементов И второй и третьей групп соединены соответственно с первыми и вторыми входами сооответствующих сумматоров по модулю два второй группы , выходы сумматоров по модулю два с первого по (М-1)-й второй группы соединены соответственно с вторыми входами элементов ИЛИ с первого по Ы-1)-й второй группы, выходы блока определения старшего нулевого разряда соединены соответствен

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИН

Зцр G 06 F 7/49

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

С:

CO

СВ

С О

4ь

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3442128/18-24 (22) 24.05.82 (46) 15.12.83. Бюл. № 46 (72) Е. В. Егоров, Е. М. Зверев, А. И. Корнилов и А. В. Хмыров (53) 681.325 (088.8) (56) 1. Авторское свидетельство СССР № 824202, кл. G 06 F 7/49, 1981.

2. Блох Э. Л., Зяблов В. В. Обобщенные каскадные коды. М., «Связь», 1976, с. 99, р. 3.30 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В КОНЕЧНЫХ ПОЛЯХ, содержащее первый, второй и третий регистры сдвига, первую и вторую группы элементов ИЛИ, первую группу элементов И, первую группу сумматоров по модулю два, причем первые входы элементов ИЛИ первой группы сое. динены соответственно с входами коэффициентов множителя устройства, выходы разрядов третьего регистра сдвига являются выходами устройства, выходы элементов

ИЛИ первой группы соединены соответственно с входами разрядов первого регистра сдвига, выход (N-1)-го разряда первого регистра сдвига соединен с вторым входом (N-2) -го элемента ИЛИ первой группы, выход нулевого разряда первого регистра сдвига соединен с вторым входом (N-1) -го элемента ИЛИ первой группы, с первыми входами элементов И первой группы, выходы которых, соединены соответственно с первыми входами сумматоров по модулю два первой группы, вторые входы которых соединены соответственно с выходами разрядов третьего регистра сдвига, выходы сумматоров по модулю два первой группы соединены соответственно с входами разрядов третьего регистра сдвига, первые входы элементов ИЛИ второй группы соединены соответственно с входами коэффициентов множимого устройства, выходы элементов ИЛИ второй группы соединены соответственно с входами разрядов второго регистра сдвига, выходы разрядов второго регистра сдвига соединены соответственно

„„SU„„1061134 A с вторыми входами элементов И первой группы, отличающееся тем, что, с целью расширения области применения за счет обеспечения умножения полиномов в поле, порожденном любым неприводимым многочленом, степень которого не превышает заданной, в него введены регистры многочлена, блок определения старшего нулевого разряда, вторая и третья группы элементов И, N переключателей, вторая группа сумматоров по модулю два, причем входы разрядов регистра многочлена соединены соответственно с входами иеприводимого миогочлеиа устройства, выходы регистра миогочлеиа соединены соответственно с входами блока определения старшего ненулевого разряда, выходы разрядов с первого по (N-1)-й регистра многочлена соединены соответственно с первыми входами элементов

И второй группы, выходы разрядов с нулевого по (N-2)-й второго регистра сдвига соединены соответственно с первыми входами элементов И с первого по (N-1)-й третьей группы и первыми информационными входами переключателей с первого по (N-1) -й выход (N-1) -го разряда второго регистра сдвига соединен с первым информационным входом N-го переключателя, второй информационный вход которого соединен с шиной нулевого потенциала устройства, выход N-го переключателя соединен с вторым входом (N-1-)-го элемента

И второй группы и вторым информационным входом (N-1) -го переключателя, выход первого переключателя соединен с вторым входом нулевого элемента ИЛИ второй группы, выходы элементов И второй и третьей групп соединены соответственно с первыми и вторыми входами сооответствующих сумматоров по модулю два второй группы, выходы сумматоров по модулю два с первого по (N-1)-й второй группы соединены соответственно с вторыми входами элементов ИЛИ с первого по N-1)-й второй группы, выходы блока определения старшего нулевого разряда соединены соответствеи1061134

45 причем входы разрядов регистра многочлена соединены соответственно с входами неприводимого многочлена устройства, выходы регистра многочлена соединены соно с управляющими входами переключателей, управляющие входы переключателей с первого по (N-1)-й соединены соответственно с вторыми входами элементов И с перИзобретение относится к вычислительной технике и предназначено для выполнения операции перемножения многочленов в конечных полях.

Известно устройство для умножения в конечных полях, содержащее первый, второй и третий регистры, блок умножения и группу элементов И (1).

Недостатком этого устройства является невозмож ность перемножения многочленов в каком-либо ином поле, кроме того, которое порождается поли номом, и навсегда определенном при построении устройства.

Наиболее близким по технической сущности к данному изобретению является устройство умножения в конечных полях, содержащее первый, второй и третий регистры сдвига, первую и вторую группы элементов ИЛИ, первую группу элементов И, первую группу сумматоров по модулю два, причем первые входы элементов ИЛИ первой группы соединейы соответственно с входами коэффициентов множителя устройства, выходы разрядов третьего регистра сдвига являются выходами устройства, зыходы элементов ИЛИ первой группы соединены со-. ответственно с входами разрядов первого регистра сдвига, выход (N-1) -го разряда первого регистра сдвига соединен с вторым входом (N-2)-го элемента ИЛИ первой группы, выход нулевого разряда первого регистра сдвига соединен с вторым входом (N-1)-го элемента ИЛИ первой группы„ с первыми входами элементов И первой группы, выходы которых соединены соответственно с первыми входами сумматоров по модулю два первой группы, вторые входы которых соединены соответственно с выходами разрядов третьего регистра сдвига, выходы сумматоров по модулю:два первой группы соединены соответствеййо с входами разрядов третьего регистра сдвига, первые входы элементов ИЛИ второй группы соединены соответственно с входами коэффициентов множимого устройства, выходы элементов ИЛИ второй группы соединены соответственно с входами разрядов второго регистра сдвига, выходы разрядов второго регистра сдвига соединены соответственно с вторыми входами элементов И первой группы (2) .

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

Зо

40 вого по (N-1) -й второй группы, тактовые входы первого, второго и третьего регистров сдвига соединены с тактовым входом устройства. которое продолжается полиномом, раз и навсегда заданным при построении устройства, так как цепь для деления на порождающий полином поля неизменяема.

Цель изобретения — расширение области применения за счет обеспечения умножения полиномов в поле, порожденном любым неприводимым мйогочленом, степень которого не превышает задайной.

Поставленная цель достигается тем, что устройство, содержащее первый, второй и третий регистры сдвига, первую и вторую группы элементов ИЛИ, первую группу элементов И, первую группу сумматоров по модулю два, причем первые входы элементов ИЛИ первой группы соединены соотвественно с входами коэффициентов множителя устройства, выходы разрядов третьего регистра сдвига являются выходами устройства, выходы элементов ИЛИ первой группы соединены соответственно с входами разрядов первого регистра сдвига, выход (N-1)-ro разряда первого регистра сдвига соединен с вторым входом (N-2) -ro элемента ИЛИ первой группы, выход нулевого разряда первого регистра сдвига соединен с вторым входом (N -1) -го элемента ИЛИ первой группы с первыми входами элемей* тов И первой группы, выходы которых соединены соответственно с первыми входами сумматоров по модулю два первой группы, вторые входы которых соединены соответственно с выходами разрядов третьего регистра сдвига, выходы сумматоров по модулю, два первой группы соедийейы соответственно с входами разрядов третьего регистра сдвига, первые входы элементов

ИЛИ второй группы соедийейы соответственно с входами коэффициентов мйожимого устройства, выходы элементов ИЛИ второй группы соединены соответственйо с входами разрядов второго регистра сдвига, выходы разрядов второго регистра сдвига соединены соответственйо с вторыми вхо-: дами элементов И первой группы, введены регистры многочлена, блок определения старшего ненулевого разряда, вторая и третья группы элементов И, N переключателей, вторая группа сумматоров по модулю два, 1061134 ответственно с входами блока определения старшего нулевого разряда, выходы разрядов с первого по (N-1)-й регистра многочлена соединены соответственно с первыми входами элементов И второй группы, выходы разрядов с нулевого по (N-2)-й и второго регистра сдвига соединены соответственно с первыми входами элементов И с первого по (N-1)-Й третьей группы и первыми информационными входами переключателей с первого по (N-1)-й, выходы (N-1)-го ð разряда второго регистра сдвига соединен с первым информационным входом N-го переключателя, второй информационный вход которого соединен с шиной нулевого потейциала устройства, выход N-го переключателя соединен с вторым входом (N-1)-го 15 элемента И второй группы и вторым информационным входом (N-1) -го переключателя, выход первого переключателя соединен с вторым входом нулевого элемента

ИЛИ второй группы, выходы элементов И второй и третьей группы соединены соот- ветственно по модулю два второй группы, выходы сумматоров по модулю два с первого по (N-1)-й второй группы соединены соответственно с вторыми входами элементов ИЛИ с первого по (N-1)-й второй груп- 25 пы, выходы блока определения старшего нулевого разряда соединены соответственно с управляющими входами переключателей, управляющие входы переключателей с первого по (N-1) -й соединены соответственно с вторыми входами элементов И gp с первого по (N-1)-й второй группы, тактовые входы первого, второго и третьего регистров сдвига соединены с тактовым вхо дом устройства.

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 — функциональ- 35 ная схема блока определения старшего ненулевого разряда.

Устройство содержит регистр 1 сдвига, содержащий N разрядных ячеек 2 — 5, регистр 6 сдвига, содержащий N разрядных „ ячеек 7 — 10, регистр 11 сдвига, содержащий N разрядных ячеек 12 — 15, регистр.

16 многочлена, содержащий. N разрядных ячеек 17 — 20, группу элементов HJlH 21—

24, группу элементов ИЛИ 25 — 28, группу элементов И 29-32, группу элементов 45

И 33 — 35, группу элементов И 36 — 38, группу сумматоров 39--42 по модулю два, группу сумматоров 43 — 45 по модулю два, блок 46 определения старшего ненулевого разряда, переключатели 4? — 50, входы

51 — 54 коэффициентов множителя уст- 50 ройства, входы 55 — 58 коэффициентов множимого устройства, входы 59 — 62 неприводимого многочлена устройства, выходы 63—

66 устройства, тактовый вход 67 устройства.

Один из входов элементов И 33 — 35 выполнены инверсными.

Блок 46 определения старшего ненулевого разряда состоит из элементов И 68 — 75.

Один из входов элементов И 69 — 75 выполнены инверсными. Входы 76 — 79 являются входами блока 46. Выходы 80 — 83 являются выходами блока 46. Вход 84 является входом логической единицы.

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

Рассмотрим поле GF(2 ), порождаемое неприводимым многочленом: f(x) степени m с коэффициентами. из поля GF (2), т. е.

f (х) = 1+ f,+ f x... + f х Я EGF (2),i = 0,1..., m — 1), f =1. аждыйэлементполяGF(2 ) представляют в виде многочлена над GF(2), степень которого меньше m, тогда умножение элементов поля друг на друга выполняется по правилам умножения, представляющим эти элементы многочленов по модулю образующего многочлена f (x) . Пусть а (х) =

=а,+a, (х)+...+а z x, а; EGF(2), i=

=0,1, „m — 1 — множимое в(х) =an+a,x+

+ вщ,x в GF (2) i = 0 l,...,m — 1 — множитель, когда их произведение с(х) с,+с,х

+...cm-, x c> е GF(2), i =0,1,...,m — 1 равно с(х) =в(х) а(х) modf(x). т. е. с(х) =в,U, (х)

+a U (x) +-"+в - U -< (х), где U; =

= х "а (х) modf(x).

В предлагаемом устройстве степень многочлена f(x) m может быть любой, но не больше, чем разрядность регистров 1, 6, 11, 16.

В исходном соястоянии регистр находится в нулевом состоянии. На входы устройства 51О, 52,, 53н-z, 54к-1 подаются одновременно коэффициенты многочлена в (x) в„в,, ..., в,, причем условию в; =1 соответствует единичный потенциал íà соответствующем входе, а условию в; =0— нулевой потенциал на соответствующем входе. При этом, если m

imam. Аналогичным образом на входы 591, 60, 61 g, 62 1 устройства подаются коэффициенты многочлена f(x), а на входы 55, 561, 571 2. 581 — коэффициенты многочлена а(x) и запоминаются в регистрах

16 и 6 соответственно.

После того, как в регистр 16 записаны коэффициенты многочлена f(x), на входах блока 46 определения старшего ненулевого разряда появляется слово, состоящее из нулей, кроме разряда, соответ твующего крайней правой единице в слове, составленном из коэффициентов многочлена f (x) .

Переключатели 47 — 50, на управляющий вход которых подается эта единица, соединяют выход соответствующей разрядной ячейки регистра 6 со своим входом. На управляющие входы остальных переключателей 47 — 50 поступают нули, и они устанавливаются в положение, при котором выход каждого последующего переключателя 47—

50 соединен с выходом предыдущего. Таким образом разрядные ячейки регистра 6, переключатели 47 — 50 элементы 33 и 38 И и сумматоры 43 и 45 по модулю два, стоящие левее этого выделенного переключателя 47 — 50 вместе с ним образуют цепь ум1061134

S иожеиия на х по модулю f(x), иа входы же сумматоров 43 — 45 по модулю два, стоящих правее выделенного переключателя

47 — 50, поступают только нули, поэтому соответствующие разрядные ячейки регистра 6 всегда обнулены.

При поступлении иа тактовый вход 67 устройства тактового импульса происходит сдвиг в регистрах 1 и 6, при этом содержащееся в регистре 6 слово из коэффициентов миогочлеиа а(х) умножается Hà х по мо- 1Н дулю f(x), одновременно иа входы элементов И 29 — 32 поступает значение коэфФициента в,, а в регистре 11 записывается слово. из коэффициентов в а(х). На вторые входы элементов И 29 — 32 теперь поданы коэффициенты многочлена ха(х) modf(x). 15

Легко видеть, что иа i-м шаге, т. е. при поступлении i-го тактового импульса, в ячейках регистра 2 образуется миогочлеи

U (х), иа выходах элементов И 29-32 и появляется миогочлен a; U; (х), а в регистр.

11 записывается многочлен в, U< (х) +

+ B f U$ (x) + ... + в; q Ul -< (х) . После т-го тактового импульса в регистре 11 будет содержаться результат умножения с (х) =

=в(x)а(х)mod (х). Дальнейшее поступление тактовых импульсов не будет влиять иа содержимое регистра ll, поскольку старшие разряды в (х) равны нулю, в1 — — О, при i>m.

Таким образом, предложенное устройство выгодно отличается от прототипа, так как с его помощью можно производить умножение в поле, порожденном любым неприводимым многочленом. Для этого достаточно загрузить коэффициенты этого многочлена в регистр 16. Ограничение накладывается только на степень образующего многочлена поля, которая не должна превышать разрядности устройства. Это особенно удобно в тех случаях, когда устройство реализуется в интегральном исполнении или входит в состав БИС, когда доступ к цепи деления на порождающий многочлен невозможен, 1061134

78

° 1 ° фиг. 2

Редактор К. Волощук

Заказ 10041/51

Составитель Л. Медведева

Техред И. Верес Корректор О. Билак

Тираж 706 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Филиал ППП «Патент», г. Ужгород, уя. Проектная, 4