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

 

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

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

РЕСПУБЛИК

l (51)5 G 06 F 7/49

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

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

1 (21) 4798980/24 (22) 05.03.90 (46) 30.01.92; Бюл. М 4 (71) Научно-исследовательский институт бйтовой радиоэлектронной аппаратуры (72) И.И.Ковалив (53) 681.325 (088.8) (56) Мак-Вильямс Ф.Дж„.Слоен H.Äæ.À. Теория .кодов, исправляющих ошибки. М.:

Связь, 1979, рис. 3.6, с. 98. Авторское свидетельство СССР

М 1226445, кл. 6 06 F 7/52, 1984.

{54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЭЛЕМЕНТОВ КОНЕЧНОГО ПОЛЯ GF(2 ) „!Ж„„ 1709300 А1 (57) Изобретение относится к специализированным устройствам вычислительной техники и может использоваться в устройствах передачи данных, в кодирующих и декодирующих устройствах, работающих с элементами конечного поля полиномов GF(2 ) при

m = 2. Цель изобретения — уменьшение аппаратурных затрат, Устройство содержит первый 1 и второй 2 регистры, матричный преобразователь 3, мультиплексор 4 с двумя группами информационных входов, группу 5 блоков элементов И, блок 6 сумматоров по модулю два и элемент НЕ 7. 1 ил, 1709300

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

GF(2 ), которое является одним из полей Галуа GF(2 ) при m = 2.

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

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

Известно также устройство для деления элементов полей Галуа, содержащее первый и второй сдвиговые регистры один элемент И, один элемент ИЛИ-НЕ, декодер, кодер и умножитель, при этом информационные входы первого и второго сдвиговых регистров являются входами устройства коэффициентов полинама-делителя и полинома-делимого соответственно, выходы подсоединены к входам декодера и к первой группе входов умножителя соответственно, а тактовые входы — объединены и подсоединены к выходу элемента И, первый вход которого является тактовым входом устройства, а второй вход — подсоединен к выходу элемента ИЛИ-НЕ, входы которого обьединены с второй группой входов умно жителя и подсоединены к выходам кодера, входы которого подсоединены к выходам декодера, при этом выходы умнажителя являются выходами коэффициентов результирующего полинома.

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

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

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

55 второго блока сумматора по модулю двэ, выходы которого подсоединены к второй группе входов третьего мультиплексора и к первой группе входов второй группы блоков элементов И, выходы которой подсоединены к входам первого блока сумматоров по модулю два. при этом выходы первого мультиплексора подсоединены к информационным входам второго регистра, выходы которого подсоединены к входам матричнаго преобразования, выходы которого подсоединены к -",эьединенным группам входов первой и второй группы блоков элементов

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

Блок синхронизации содержит триггер. (m-1)-разрядный регистр сдвига. блок зле1709300 ментов задержки, четыре элемента И, два элемента ИЛИ-НЕ и инвертор.

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

Для достижения поставленной цели в устройстве для умножения элементов конечного поля G.F(22), содержащим первый и второй регистры, мультиплексор, матричный преобразователь, группу элементов И, блок сумматоров по модулю два и элемент

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

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

G F(22), Устройство умножения над полем GF(2 ) содержит первый и второй регистры 1 и 2 соответственно, матричный преобразователь 3, мультиплексор 4 с двумя группами информационных входов, группу 5 блоков элементов И, блок 6 сумматоров по модулю два и инвертор 7, причем два выхода первого регистра 1 подсоединены к одноименным двум входам матричного преобразователя

3. четыре выхода которого подсоединены к соответствующим четырем входам первой группы входов группы 5 блоков элементов

И, четыре выхода которой подсоединены к соответствующим четырем входам блока 6 сумматоров по модулю два, при этом два

Кроме того, термины папином и элемент

40 поля — идентичны.

Устройство умножения над полем GF(2 )

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

Исходное состояние устройства не определяется и состояние первого и второго

45 регистров 1 и 2 могут быть произвольными.

Устройство может выполнять две операции над конечным полем полиномов GF(2 ): операцию умножения двух элементов поля и операцию определения обратного элемента

50 для ненулевого элемента поля.

При выполнении устройством операции умножения двух элементов поля GF(2 ) на тактовый вход и вход режима работы устройства подаются сигналы низкого уровня, 55 на входы устройства коэффициентов первого и второго полиномов-сомножителей подаются сигналы, соответствующие значениям коэффициентов первого и второго полиномов-сомножителей соответственно, а затем на тактовый вход устройства

35 выхода второго регистра 2 подсоединены к одноименным двум входам второй группы входов группы 5 блоков элементов.И, а тактовые входы регистров 1 и 2 — объединены и являются тактовым входом устройства причем информационные два входа первого регистра 1 объединены с одноименными двумя информационными входами первой группы информационных входов мультиплексора 4 и являются входами устройства коэффициентов первого полинома-cQMHQжителя, два информационные входы второй группы информационных входов мультиплексора 4 являются входами устройства коэффициентов второго полинома-сомножителя, а два выходы подсоединены к двум одноименным информационным входам второго регистра 2, при этом первый управляющий вход мультиплексора 4 объединен е входом инвертора 7 и является входом признака режима работы устройства, а второй управляющий вход мультиплексора 4 подсоединен к выходу инвертора 7, причем два выхода блока 6 сумматоров по модулю два являются выходами устройства коэффициентов результирующего полинома, При описании принципа действия устройства умножения над полем GF(2.) выбиг рают в качестве параметра сигналов на соответствующих входах и выходах устройства или его функциональных элементов напряжение, уровни которого определяются как для "положительной логики". Таким образом, высокий уровень сигнала определяет истинное значение в булевой алгебре величины, приписываемой данному сигналу, а низкий уровень — ложное.

1709300

10

20

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

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

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

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

GF(2 ) выполняется предлагаемым устройством, как и прототипом, за один такт его работы, При выполнении предлагаемым устройством операции определения обратного элемента для ненулевого элемента поля 40

GF(2 ) на тактовый вход устройства подается сигнал низкого уровня, на вход режима работы устройства — сигнал высокого уровня, на входы устройства коэффициентов первого полинома-сомножителя — сигналы, 45 соответствующие обращаемому полиномуэлементу поля GF(2 ); при этом сигналы на входах устройства коэффициентов второго . полинома-сомножителя могут быть произвольными, а затем на тактовый вход устрой- 50 ства подается тактовый импульсный сигнал высокого уровня, после чего на входы устройства коэффициентов первого и второго полиномов и вход режима работы устройства можно подавать сигналы произвольных 55 уровней.

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

Следовательно. по переднему фронту тактового импульсного сигнала высокого уровня,. поступающего на тактовый вход устройства, регистры 1 и 2 установятся в одинаковые состояния, соответствующие коэффициентам обращаемого полинома, и, значит, по аналогии с операцией умножения устройством двух элементов поля GF(2 ), на выходах устройства коэффициентов результирующего полинома сформируются сигналы, соответ твующие полиному, равному квадрату обращаемого полинома — ненулевого элемента поля GF(2 ), Если обозначить через В значение обра-щаемого элемента поля GF(2 ), где m N, то обратный ему элемент 8 из этого поля мо-1 жет быть вычислен по формуле

В =В

8 нашем случае m = 2, значит, обратный элемент для ненулевого элемента из поля

GF(2 ) может быть вычислен по следующей зависимости, 81 В -2 82 и следовательно, как квадрат обращаемого полинома из поля GF(2 ).

Предлагаемое устройство выполняет операцию определения обратного элемента для ненулевого элемента поля GF(2 ), как и прототип, за-один такт его работы. Таким образом, работоспособность устройства не нарушается, Работоспособность предлагаемого устройства по сравнению с прототипом при

m =2 обеспечивается меньшимиаппаратурными затратами.

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

Аппаратурные затраты предлагаемого устройства составляют два регистра, один мультиплексор на две группы информационных входов, один матричный преобразователь, одну группу блоков элементов И. один блок сумматоров по модулю два и ин10

1709300

Таким образом, предлагаемое устройство по сравнению с прототипом имеет в своем составе меньше на два IK-триггера, три

О-триггера, два инвертора, два сумматора по модулю два, два двухвходовые элемента

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

ИЛИ, т.е. всего .на 36 логических элемента меньше.

Уменьшением аппаратурных затрат предлагаемого устройства по сравнению с прототипом при сохранении его функциоСоставитель И.Ковалив

Техред М.Моргентал

Редактор M.Òîâòèí

Корректор Т.Малец

Заказ 425 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", r, Ужгород, ул.Гагарина, 101 вертор. По сравнению с прототипом предлагаемое устройство по аппаратурным затратам имеет меньше на один регистр, два мультиплексора на три группы информационных входов каждый, одну группу блоков элементов И, один блок сумматоров по модулю два и блок синхронизации без инвертора.

Рассмотрим состав функциональных элементов прототипа.

Регистр прототипа при m - 2 состоит из двух IK-триггеррв и двух инверторов. Мультиплексор на трй,группы информационных входов состоит из шести двухвходовых эле.ментов И и двух трехвходовых элементов

ИЛИ.

Группа Ьлоков элементов И состоит из четырех двухвходовых элементов.И. Блок сумматоров по модулю два состоит из двух двухвходовых сумматоров по модулю два.

Блок синхронизации состоит из инвертора, трех 0-триггеров, пяти двухвходовых элементов И и двух двухвходовых элементов

ИЛИ-HE. нальных возможностей достигается цель изобретения.

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

° Устройство для умножения элементов

5 конечного поля GF(2 ), содержащее первый и второй регистры, мультиплексор, матричный преобразователь, группу элементов И, блок сумматоров по модулю два и элемент

НЕ, причем выходы разрядов первого реги10 стра соединены с соответствующими входами матричного преобразователя, выходы которого соединены с первыми входами соответствующих элементов И группы, выходы которых соединены с соответствующими

15 входами сумматоров по модулю два блока, а вторые входы — с соответствующими выходами разрядов второго регистра, тактовый вход которого соединен с тактовыми входами первого регистра и устройства, информа20 цион.ные входы первой и второй групп мультиплексора соединены соответственно с входами коэффициентов первого и второго полиномов-сомножителей, о т л и ч а ю щее с я тем, что, с целью сокращения аппара25. турных затрат, вход элемента HE соединен с входом признака режима устройства и первым управляющим входом мультиплексора, второй управляющий вход которого соединен с выходом элемента НЕ, а выходы—

30 соответственно с информационными входами второго регистра, информационные входы первого регистра — с входами коэффициентов первого полинома-сомножителя устройства, выходы коэффициентов

35 результирующего полинома которого соединены с выходами сумматоров по модулю два блока.