Устройство для умножения элементов конечного поля размерности 2 @

Устройство для умножения элементов конечного поля размерности 2 @

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советскик

Социалистических

Республик (u>,959077 (6$) Дополнительное к авт. свид-ву(22) Заявлено 121280 (21) 3229562/18-24 (%1) М. Кд.з с присоединением заявки Ìo—

G 06 F 7/68

Государственный комитет

СССР но делам изобретений и открытий . (23) Приоритет— (331УДК 681. 325 (088.8) Опубликовано 150982. Бюллетень Мо 34

Дата опубликования описания. 15.09.82 (72) Авторы изобретения

Ю.В. Сулимов, В.И. Котов и В.Н. Стальнов г

1 л (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЭЛЕМЕНТОВ

КОНЕЧНОГО ПОЛЯ РАЗМЕРНОСТИ 2m

Ч 2в.2 6 бит.

4М 10

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

Недостаткбм .такого устройства является большая затрата машинного времени при реализации его программныья средствами.

Наиболее близким техническим решением к данному является табличное устройство для модульного умножения в системе остаточных классов, содержащее 2 и-разрядные параллельные регистры множимого и множителя, первую и вторую группы элементов И по

2тн элементов И s каждой и блок памяти (2g.

При использовании известного устройства для умножения элементов конечного поля размерности 2уипотребуется блок памяти с объемом, равным

В случае перемножения чисел большой разрядности, что необходимо, например, при формировании помехозащищенных кодов, объем блока памяти возрастает настолько, что становится практически нереализуемым. Таким образом, недостатком устройства является значительное увеличение объема блока памяти при увеличении разрядности перемножаемых чисел.

Цель изобретения — уменьшение объема оборудования.

Поставленная цель достигается тем, что в устройство дополнительно введены параллельный тн-разрядный регистр, первая.и вторая группы элементов ИЛИ, по vn элементов ИЛИ в каждой, третья, четвертая, пятая и шестая группы элементов И no vn

20 элементов И в кдой, парельй

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

30 входами элементов И второй группы, выходы е-разрядного параллельного регистра соединены соответственно с первыми входами элементов И третьей.группы, вторые входи Vn IIepвых элементов И первой группы объединены и соединены с выходом перво- 5 го элемента ИЛИ блока управления, вторые входы остальных элементов И первой группы объединены и соединены с выходом второго элемента ИЛИ блока управления, вторые входы и пер- )Ц .вых элементов И второй группы объединены и соединены с выходом третьего элемента ИЛИ блока управления, вторые входы остальных элементов И второй группы объединены и соединены с выходом четвертого элемента ИЛИ блока управления, вторые входи элементов И третьей группы объединены и соединены с первым выходом распре- делителя тактовых сигналов блока управления и с объединенньпчи вторымн @ входами элементов И четвертой группы, выходы ь первых элементов И первой группы соединены соответственно с первыми входа1и элементов ИЛИ первой группы, выходи остальных элементов И первой группы соединены соответственно со вторыми входами элементов ИЛИ первой группы, выходы элементов И третьей группы соединены соответственно с третьими входами элементов ИЛИ первой групп, выходы ю первых элементов И второй групи1 соединены соответственно с первыми входами элементов ИЛИ второй группы, выходы остальных элементов И $5 второй группы соедичены соответственно со вторыми входами элементов

ИЛИ второй группы, выходы элементов И четвертой -группы соединены соответственно с третьими входами злемен- 4ц тов ИЛИ второй группы, выходы элементов ИЛИ первой группы соединены соответственно с м первыми входами регистра адреса, выходы элементов ИЛИ второй группы соединены соответствен-45 но с остальными входами регистра адреса, выходы которого соответствен« но соединены с адресными входами бло« ка памяти, выходы которого соединены соответственно с первыми входами элементов И пятой и шестой групп, 5@ вторые входь1 элементов И пятой группы объединены и соединены с выходс}м пятого элемента ИЛИ блока управления, вторые входы элементов И шестой группы объединены и соединены с выходом шестого элемента ИЛИ блока управления, выходы элементов И пятой и шестой групп соединены соответственно с информационными входами накапливающего сумматора,. вы- 69 ходы д первых разрядов которого соединены соответственно с первыми ,-входами элементов И четвертой группы и являются w первыми разрядами выходной шины устройства, а остальные выходы накапливающего сумматора являются соответствующими разрядами выходной шины устройства, второй выход распределителя тактовых сигналов блока управления соединен с первыми входами первого, третьего и пятого элементов ИЛИ блока управления, первый выход распределителя тактовых сигналов блока управления соединен с первым входом шестого элемента ИЛИ блока управления, третий выход распределителя тактовых сигналов блока управления соединен с первым входом четвертого элемента ИЛИ и со вторыми входами первого и пятого элементов ИЛИ блока управления, четвертый выход распределителя тактовых сигналов блока управления соединен с первым входом второго элемента ИЛИ, вторым входом третьего элемента ИЛЙ и третьим входом пятого элемента ИЛИ блока управленияр пятый выход распределителя тактовых сигналов блока управления соединен со вторыми входами второго, четвертого и шестого элементов ИЛИ блока управления.

На чертеже изображена функциональная схема устройства.

Устройство содержит 2в-разрядные параллельные регистры 1, 2 множимого и множителя, 2 m элементов 3 И первой группы, 2 и элементов 4 И второй группы, блок 5 памяти, параллельный ж-разрядный регистр 6, 1и элементов 7 ИЛИ первбй группы, вч элементов 8 ИЛИ второй группы, щ элементов 9 И третьей группы„ vn элементов 1О И четвертой группы, 11 элементов 11 И пятой группы,;; элементов 12 И шестой группы, параллельный 2ю-разрядный регистр 13 адреса, накапливающий сумматор 14-и блок 15 управления, содержащий шесть элементов 16 ИЛИ и распределитель 17 тактовых сигналов.

Устройство реализует возможность формирования произведения элементов поля размерности 21 1путем последовательного использования операций над элементами поля размерности ю, на которые разлагаются 2 pàçðIIäные числа множимого и множителя благодаря чему значительно уменьша( ется объем матрицы. Указанная возможность основана на том что любой М элемент A поля GF(2 } можно представить в виде линейного многочлена вида а„ х + а, коэффициенты которого а и а являются как элементами поля GF{2 ), так и его подполя GF(2""}, при этом элемент А может быть представлен в виде 2ит-разрядной двоичной комбинации, а компоненты а и a - в виде 1"-разрядных двоичных комбинаций. Сложение двух элементов А и В поля GF(2- }

959077 можно производить как сложение двух многочленов:

А + В = (а x + а } + (Ь„ х + Ь }

{а .+ Ь )х + (а + b ).

При этом сложение производится по модулю два. Произведение двух элементов поля ОЕ(2 } может быть выполнено как произведение двух соответствующих многочленов по мо- . дулю ненриводимого квадратного многочлена F(x) над полем GF(2 " ). В . 10 качестве многочлена F(x) может быть использован многочлен вида

F(x) = х - + x + c, где с - элемент поля 6Г(2 ). Поэтому имеем:

A В = (а х+ a<)(b„x+ Ь } l5 а„Ь x + (a< Ь + a b< )x .+ атЬа а, Ь, x + (а Ь + а„Ь1 )x + а Ь. +

+ а Ь F(x) = (а Ь + а Ь + а Ь,.) х +

+ а Ь + са„Ь„.

Устройство осуществляет умноже- О ние за пять тактов работы распреде- лителя 17 тактовых сигналов и работает следующим образом.

Два .перемножаемых элемента A и В поля GF(2 ) в виде 2И -разрядных двоичных комбинаций в исходном состоянии хранятся в параллельных ре-. гистрах 1,2 множимого и множителя.

В первый такт работы распределителя 17 тактовых сигналов блока 15 управления управляющий сигнал с выходов первого, третьего и пятого эле ментов 16 ИЛИ блока 15 управления поступает на вторые входы tn -первых элементов 3 И первой группы, ю -первых элементов 4 И второй группы и элементов 11 И пятой группы, разрешая прохождение компоненты ц„ с ь первых выходов регистра 1 множимого через элементы 7 ИЛИ первой группы на н первые входы регистра 13 адре- 40 са, а компоненты 33< — с и первых вы — . ходов регистра 2 множителя через элементы 8 ИЛИ второй группы на остальные входы регистра 13 адреса. Регистр

13 адреса по компонентам ef и 5 выби- 45 рает ячейку в блоке 5 памяти, в которой записано произведение этих компонент и считывает содержимое этой ячейки, которое в виде ы -разрядного двоичного числа через элементы 11 И пя- щ той группы поступает на М первые информационные входы накапливающего сумматора 14.

Во втором .такте работы распреДели" теля 17 тактовых .сигналов блока 15 управления управляющий сигнал с первого выхода распределителя 17 посту- пает на вторые входы элементов 9 И третьей группы и элементов 10 И четвертой группы, а с выхода шестого элемента 16 ИЛИ блока 15 управления на вторые входы элементов 12 И шес.той группы, разрешая прохождение компоненты .а с выходов параллельного регистра 6 через элементы 7 ИЛИ первой группы на rn первые входы регистра 13 адреса, а произведения а Ь с m первых выходов накапливающего сумматора 14 через элементы 8 ИЛИ второй группы на остальные входы регистра 13 адреса. С помощью регистра 13 адреса из блока 5 памяти считывается произведение а Ь„ с, которое через элементы 12 И шестой группы поступает на остальные информационные входы накапливающего сумматора 14.

В третьем такте работы распределителя 17 тактовых сигналов блока

15 управления управляющий сигнал с выходов первого, четвертого и пятого элементов 16 ИЛИ блока 15 управления поступает на вторые входы ьи первых элементов 3 И первой группы, остальных элементов 4 И второй груп.пы и элементов 11 И пятой группы, разрешая прохождение компоненты а„ c m первых выходов регистра 1 мйожимого через. элементы 7 ИЛИ первой группы на и первые входы регистра 13 адреса, а компонентЫ Ь вЂ” с остальных выходов регистра 2 множителя через элементы 8 ИЛИ второй группы на остальные входы регистра

13 адреса. С помощью регистра 13 адреса из блока 5 памяти считывается произведение а., Ь, которое через элементы 11 И пятой группы поступает иа rn первые входы накапливающего сумматора 14, .суммируясь в нем с произведением а„Ь . Таким образом, после третьего такта работы устройства, в m первых разрядах накапливающего сумматора 14 зафиксировано число (а„ Ь„ + а, Ь ).

3 четвертом такте работы управляющий сигнал с выходов второго, третьего и пятого элементов 16 ИЛИ блока 15 управления поступает на вторые входы остальных элементов 3 И первой группы, м первых элементов 4 И второй группы и элементов 11 И пятой группы, разрешая прохождение компонент а и Ь„ на входы регистра 13 адреса, а следовательно, и считывание из блока 5 памяти произведения а Ь, которое поступает через элементы 11 И пятой группы в ю первые разряды накапливающего сумматора 14.

Таким образом, после четвертого такта работы устройства в ит первых разрядах накапливающего сумматора 14 записана сумма.(a Ь,, + а,,Ь + а. Ь,,).

В пятом такте работы управляющий сигнал с выходов второго, четвертого и шестого элементов 16 ИЛИ блока 15 управления поступает на вторые входы остал7 нйх элементов 3 И первой группы, остал ных элементов 4 H второй группы и элементов 12 И шестой группы, разрешая прохождение компонент а.2 и Ь на входы регистра 13 адреса, а следовательно, и считывание из блока 5 памяти произведения

a b,которое через элементы 12 И шес959077

f5 ветстжнно со вторыми входами элементов ИЛИ первой группы, выходы эле10

V = 2m 2 — - бит, ба ходы остальных элементов И второй группы соединены соответственно со

25 вторыми входами эЛементов ИЛИ второй

Ч

Ч I

= — ° 2

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

Устройство для умножения элементов конечного поля размерности 2m, содержащее параллельные 2m-разрядные регистры множимого и множителя, первую и вторую группы элементов И по 2в элементов И в каждой„ блок памяти, о т л и ч а ю щ е е с я тем„ что, с целью уменьшения объема оборудования, в устройство введены параллельный в-разрядный регистр, первая и, вторая группы элементов ЙЛИ.. 40 по е элементов ИЛИ в каждВй, третья, четвертая, пятая и шестая группы элементов И .по а элементов И в каждой, параллельный 2m-разрядный ре гистр .адреса,,накапливающий сумма- 45 ,тор и блок управления, содержащий . распределитель тактовых сигналов и шесть элементов ИЛИ, причем выходы регистра множимого соединены соответственно с первыми входами элементов И первой группы, выходы регистра множителя соединены соответственно с первыми входами элементов И второй гуппи, выходы параллельного и-разряфяого регистра соединены соответственно с первыми входами элементов И третьей группы, вторые входы ю первых элементов И первой группы объединены и соединены с выходом пер вого элемента ИЛИ блока управления, вторые входы остальных элементов И первой группы .объединены и соединены с выходом второго элемента ИЛИ блока управления, вторые входы ти первых элементов И второй группы объединены и соединены с выходом третьего той группы поступает в остальные разряды накапливающего сумматора 14.

Таким образом, после пятого такта работы устройства в фи первых разрядах накапливающего сумматора 14 зафиксирована компонента (а„ Ь + а Ь +

+ а,, Ь ), а в остальных разщщах— компонента (а Ь + с,,а,,Ь., ) произведения АВ..

Устройство по сравнению с прототипом обеспечивает выигрыш в объеме памяти для хранения произведений, а также в разрядности перемножаемых чисел.

Если в прототипе объем памяти составляет то в данном устройстве он составит

Ч = m ° 2 бит, к и таким образом выигрыш в памяти данного, устройства по сравнению с прототипом элемента ИЛИ блока управления, вторые входы остальных элементов И второй группы объединены и соединены с выходом четвертого элемента ИЛИ блока управления, вторые входы элементов И третьей группы объединены и соединены с первым выходом распределителя тактовых сигналов блока управления и с объединенными вторыми входами элементов И четвертой группы, выходы vn первых элементов И первой группы соединены соответственно с первыми входами элементов ИЛИ первой группы, выходы остальных элементов И первой группы соединены соотментов И третьей группы соединены соответственно с третьими входами элементов ИЛИ первой группы, выходы П1 первых элементов И второй группы соединены соответственно с первыми.входами элементов ИЛИ второй группы, выгруппы, выходы элементов И четвертой группы соединены соответственно с третьими входами элементов ИЛИ второй группы, выходы элементов ИЛИ первой группы соединены соответственно с ю первыми входами регистра адреса, выходы элементов ИЛИ второй группы соединены соответственно с остальными входами регистра адреса, выходы которого соответственно соединены с адресными входами блока памяти, выходы которого соединены соответственно с первыми входами элементов И пятой и шестой групп, вто.рые входы элементов И пятой группы объединены и соединены с выходом пятого элемента ИЛИ блока управления, вторые входы элементов И шестой группы объединены и соединены с выходом шестого элемента ИЛИ блока управления, выходы элементов И пятой и, шестой групп соединены соответственно с информационными входами накапливающего .сумматора, выходы и пер,вых разрядов которого соединены соответственно с первыми входами эле ментов И четвертой группы и являются и первыми разрядами выходной шины устройства, а остальные выходы накапливающего сумматора являются соответствующими разрядами выходной шины устройства, второй выход распределмтеля тактовых сигналов блока управления соединен с первыми входами первого, третьего и пятого элементов ИЛИ блока управления, первый выход распределителя тактовых сигналов блока управления соединен с первым входом шестого. элемента ИЛИ блока управления, третий выход распределителя тактовых. сигналов блока управления соединен с первым входом

959077

ВНИИПИ Заказ 7018/66 Тираж 731 Подписное

Филиал ППП,"Патент, г. Ужгород, ул.Проектная,4 четвертого элемента ИЛИ и со вторыми входами первого и пятого элементов ИЛИ блока управления, четвертый выход распределителя тактовых сигналов блока управления соединен с первым входом второго элемента HJIH, 5 вторым входом третьего элемента ИЛИ и третьим входом пятого элемента ИЛИ блока управления, пятый выход распре делителя тактовых сигналов блока управления соединен со вторыми входа- 10 мй второго, четвертого, и шестого элементов ИЛИ блока управления.

Источники информации, принятые во внимание при экспертизе

1. Блох Э.Л., Зяблов В.В. Обобщенные каскадные коды. Я., "Связь", 1976, с. 99.

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

9 550636, кл. G 06 F 7/52,1971 (прототип).