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

 

Изобретение относится к вычислительной технике, выполняет операцию умножения двух элементов конечных полей за один такт его работы и может быть использовано в кодирующих и декодирующих устройствах двоичных кодов, оперирующих данными как элементами различных конечных полей 2 т п GF(2), образованных различными неприводимыми многочленами, где п - граничная степень m расширения поля GF (2Ш). Целью изобретения является расширение функциональных возможностей устройства за счет обеспечения выполнения им за один такт работы операции умножения элементов произвольных конечных полей GF (2m). Устройство содержит регистры 1-4, блок 5 формирования частичных произведений, дешифратор 6, блок 7 формирования младших коэффициентов, блок 8 формирования старших коэффициентов, блок 9 формирования степеней примитивного элемента, блок 10 выравнивания коэффициентов, блок 11 запрета и блок 12 суммирования. 3 з.п.ф-лы, 9 ил. ч Ё

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

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

РЕСПУБЛИК (51)5 G 06 F 7/49

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4852200/24 (22) .1 7.07,90 (46) 23.08.92. Цюл. N 31 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) И.И.Ковалев (56) Авторское свидетельство СССР

М 1061134, кл, G 06 F 7/49, 1982.

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

N .1013950, кл. G 06 F 7/52, 1982, (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ 3ЛЕМЕНТОВ КОНЕЧНЫХ ПОЛЕЙ GF(2") (57) Изобретение относйтся к вычислительной технике, выполняет операцию умноже-.. ния двух элементов конечных полей за один такт его работы и может быть использовано в кодирующих и декодирующих устройствах двоичных кодов, оперирующих данными как элементами различных конечных полей

„„JIB 1756883 А1

2 m

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

Устройство содержит регистры 1 — 4, блок 5 формирования частичных произведений, дешифратор 6; блок 7 формирования младших коэффициентов, блок 8 формирования старших коэффициентов, блок 9 формирования степеней примитивного элемента, блок

10 выравнивания коэффициентов, блок 11 .: запрета и блок 12 суммирования. 3 з.п. ф-лы, 9 ил, 3

1756883

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

2

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

2 =т ï работы (где 2, n — граничная (наибольшая) степень расширения полл GF (2). при которой устройство умножения элементов конечных полей еще выполнит операцию умноженйя над конечнаыхмх полем полиномов GF (2") m"- ñòåéåíü расширения поля G F (2), при Мотхорохй устройство умноже: (; ния элементов" конечных полей выполняет операцию умйожения над полем полйномов

GF(2 ), m ==2,3..;n; f(x) = f x +f -1x 1+...+fo — неприводимый многбчлен, образующий поле CG(2 ).

На фиг. 1 изображеьнах функциональная схема устройства умнохженйя элемейтов конечны х и олей, на фиг. 2 — блок ф ормирования частичных произведений "на фиг.»3— блок формирьования"младших коэффициентов; на фиг, 4 — блок старшvix ôîðìèðîâàíèÿ коэффициентов; на фиг. 5 — функциональная схема блока формирования степеней примитивного элемента; на фиг. 6 — блокхвыравнивания коэффициентов; на фиг, 7 — блок запрета; на фиг, 8 — функциональная схема преобразователя сигналов блока формирования степеней примитивного элемента; на фиг. 9 — функциональная, схехма субблока преобразования сигналов.

Устройство умножения элементов конечных полей GF (2") (фиг, 1) содержит регистры 1-4, блок 5 формирования частичных произведений, дешифратор 6, блок 7 формирования младших коэффициентов, блок 8 формирования старших коэффициентов, блок 9 формирования степеней примитивного элемента, блок 10 выравнивания коэффициентов, блок 11 запрета и блок 12 суммирования.

Блок 5 формирования частичных произведений (фиг, 2) содержит п2 элементов И

13, образующих и групп 14 по и элементов

И 13 каждая.

Блок 7 формирования младших коэффициентов (фиг. 3) содержит п-1. многовходовые сумматоры.15 по модулю два, блок 8 формирования старших коэффициентов

5 (фиг, 4) — n-2 многовходовых сумматоров 16 по модулю два.

Блок 9 (фиг, 5) содержит источник 17 сигнала высокого уровня и и-2 преобразователей 18 сигналов.

10 Блок 10 выравнивания коэффициентов (фиг. 6) содержит п (n+1)/2) элементов И 19 и (n-1) элементов ИЛИ 20 с числами входов, Равными числам d) = и-i+1; где I — номер элемента 20t ИЛИ в блоке 10,! = 1,2...п-1.

15 Блок 11 запрета (фиг. 7) содержит (п-1) субблоков 21 запрета и многовходовых сумматоров 22 по модулю два, поеобразователь

18 сигналов (фиг.8) блока 9 — и-1 ключей 23 и и-1 субблоков 24 преобразования, 20 Субблок 24 преобразования (фиг, 9) содержит демультиплексор 25, сумматор 26 по модулю два и мультиплексор 27, Принцип работы устройства умножения элементов конечных полей (фиг. 1) базирует25 ся на следующих математических зависимостях, Если a(x) = а -1х 1 + ...а1х + ao и b(x) =

m 1 х

bm-1x + ...b1x+ bo первый и второй элементы поля полиномов 6Г (2) образованного

30 неприводимым многочленом f(x) = fmx +

+1п)-1 х + ... 11х+ 10 при а=х, где аь b1, f)

m-1

GF (2), а — примитивный элемент поля GF (2 ) и x — фиктивная переменная, использующаяся для записи элементов полл GF (2 )

35 в форме полиномов, то произведение с(х) первого и второго элементов поля GF (2 ) вычисляется по формуле:

40 С(х)=С1(Х) Ь(Х1mOd1(Х)={О„Х +„,+QX+Q )x (Ь,x +...+ Ь;х+Ь,)mode(v)=

=((;о . а Ь ) х ) mor3E(x) =

45 „» < ., цп,. }

= 0„(а,Ь )х +((, а,Ь„) х )»

m-f Q(vn. 1) пий(х)=, (а Ь )х . (Z,à Ь )а, = О P+5- ). М Р 5-1

Введем обозначения

55 k1 = „>, apbq, где t = 0,1,2,...m-1, — младр + g = шие коэффициенты произведения;

1756883

m — 1 2 (m — 11 с(х)=. . kIx + : ki а =си-1х +

I =0 l =m ответствующего числа, а низкого уровня— нулю.

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

5 зом.

Процедура 1.

В исходном состоянии устройства на его входы коэффициентов первого и второго ... + С1х+ Со. сомножителей, на входы коэффициентов не10 приводимого многочлена и на входы степерегистрах1 — 3осуществляется прием, ни m РасшиРениЯ полЯ, а значит на хранение и выдача коэффициентов а, Ь!, 1 информационные входы регис ров1-4 по соответственно. В регистре 4 осуществляет- аютсЯ сигналы низких УРовней. КРоме того, ся прием, хранение и выдача двоичного. регистры "— 4 сброшены в нулевое сйстояпредставления числа nl (степени Расшире 15 ние посредством подачи импульсных сигнания поля полиномов дР (2 ), над которым JIQB BblcoKNx /POBHBA H3.flePBblA N BTOPOA осуществляется операция умножения). Входы сбРоса УстРойства, после Iего "à пеРB блоке 5 ОсущестВляется попарное ум . Вый ВТороА ВХОДЫ сбрОса устроЙства пОД ножение аР bq над полем GF (2) всех коэф- аются сигналы низких уровней, фициентов первого и второго сомножителей 20 При этом на выходах всех регистров 1-4 соответственно, сформированы сигналы низких уровней, а

В дешифраторе 6 осуществляется фор- значит, сигналы низких УРовней сфоРмиРомирование сигнала Высокого уровня на m- ваны также на всех выходах первой и второй ом выходе, соответствующему двоичному гРУпп выхоДов блока 5 ФОРмированиЯ часпредставлению числа а 25 тичных произведений на выходах блоков 7

В блоках 7 и 8 осуществляется форми- 10 и 11, го, в свою очередь, приводит к рование сигналов, соответствующих Ь и Формированию сигналов низких уровней на старшим!<, коэффициентам произвед ния.. выходах Ус ройства коэффициентов РезУльВ блоке 9 осуществляется Формирование на его Выходах сигналов, соответствую- 30 ПРОЦеДУРа 2. щих степеням примитивн"o элемента поля ПеРеД началом Работы УстРойство Ум1 . ножения элементов конечных полей настраивается на поле GF (2 ), элементы которого

В блоке 10 осуществляется фо ми оваВ б 10 ущ-с ляе ся формирова- устройство будетумножать. ние на его выходах сигналов, соответствую- 35 акая настройка производится путем щих сигналам на его первой группе входов, Р РУ д В подачи импульсногО сигнала на второй вход смещенных на n-m выходов в сторон выходов с меньшими номерами.

Р У в о сброса устройства, а затем подачи на каждый I-й вход устройства (1 = 1,2,:;.,п-1) коэфВ блоке 11 запрета осуществляется орми ование на его выходах сигналов, сор ущ фициентов неприводимого многочлена отвегствующих сумме, > ki а . B блоке 12 ни m расширения поля — ймпульсных осуществляется формирование на его выхо- сигналов, соответствУющих двойчномУ дах сигналов, соответствующих коэффици- представлению числа т, причем )-й вход 0 ентам с произведения. 45 1,2;...,)io9 (+1) С ) соответствУет )™У

При Описании принципа Действия уст- разряду двоичного ПРЕдставления числа щ ройства умножения элементов конечных no-: При этом на том. 1-ом выходе рег стра 3 лей (фиг. 1) необходимо учитывать, что и на том)-ом выхоДе РегистРа 4, Длл отоРы

BblcoKvIA УРовень сигнала на входе. или вы- 1 и )-ый разряд двоичного представления ходе функционального элемента или уст- 50 числа m равны единице. Формируются си ройства определяет истинное значение . налы высокогоУРовнЯсоотве ствен о. величины, а низкий уровень — ложное.. Значит, "à m-ом выходе дешифратора 6, кроме того, единице В двоичном пред На П ОМ ВХОДЕ ВТОРОЙ ГРУПП" ВХОДОВ бЛОКа стаблении какого-либо числа соответствует . сигнал высокого уровня на соответствую 55 группы входов блока 9 формируется сигнал щем входе или выходе, а нулю — низкого высокого УРовнЯ, На выходах блока 9, а зна- . уровня и наоборот, сигнал высокого уровнй чит на второй группе входов блока 11 форна каком-либо входе или выходе соответст- миРУютсЯ сигналы, зависЯщие от сигналов вует единице в двоичном представлении со- на пеРвой и втоРой группах ВхоРОВ блока 9.

1756883 в соответствии с принципом действия блока

9.

Процедура 3, Для выполнения умножения элементов

m — 1 конечного поля GF (2") а(х) =,>, aqxp u р=О

Ь(х) = „ ; Ьяхч необходимо на каждый

q=О (n-гп+1+р}-й вход устройства коэффициентов первого сомножителя и на каждый (ц+1)-й вход устройства коэффициентов второго сомножителя подать импульсные сигналы, соответствующие коэффициентам ар и Ьч соответственно, а на остальные входы устройства — подать сигналы низких уровней.

При этом, íà (n-m+1+p)-тых выходах регистра 1 и (q+1)-тых выходах регистра 2; для которых ар и bq равны единице, сформируются сигналы высоких уровней соответственно.

Дальше на выходах блоков 5,7, S, 10, 11 и 12 формируются сигналы, соответствующие логике их работы.

Процедура 4.

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

Процедура 5.

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

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

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

< m < n), образованных различными непри5

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

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

20 старших коэффициентов произведения, выходы которого соединены с входами первой группы блока запре1.а, входы второй группы которого соединены с в11ходами блока формирования степеней примйтивного элемен25 та, входы- первой группы которого соединены с выходамй третьего (n-1)-разрядного регистра, информационные входы которого соединены с входами коэффициентов неприводимого многочлена устройства, 30 входы степени m расширения поля которого соединены с информационными входами четвертого (j lagz(n+1) L )-разрядного регистра, выходы которого соединены с входами дешифратора, выходы которого

35 соединены с входами второй группы блока . выравнивания коэффициентов и блока формирования степеней примитивного элемента, входы сброса первого и второго и-разрядных регистров соединены с пер40 вым входом сброса устройства, второй вход сброса которого соединены с входами сброса третьего (n-1)-разрядного и четвертого (3 logy(n+1) j )-разрядного регистров.

45 2,Устройствопоп,1,отличаю щеес я тем, что блок формирования степеней примитивного элемента содержит источник сигнала высокого уровня и (n-2) преобразователей сигналов, причем j-йые входы пер50 вой группы (J=-1...„n) каждого l-го преобразователя сигналов (i=1Ä... n-2) и jные входы (и-2)-го преобразователя сигналов соединены с соответствующими выходами блока, входы первой группы кото55 рого соединены с входами второй группы каждого J-го преобразователя сигналов и

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

1756883

Фиг.2 рой группы блока соединены с входами соединены с управляющими входами сооттретьей группы каждого I-го преобразовате- ветствующих ключей, информационный ля сигналов, выходы 1-го преобразователя . вход i-го ключа соедйнен с(!+1)-ным входом сигналов соединены с входами первой груп- первой группы преобразователя сигналов, пы (I+1)-го преобразователя сигналов 5 4, Устройство по п.3, о тл и ч а ю ще в(!=1,...,(п-3}). с я тем; что каждый субблок преобразова3; Устройство по и. 2. о т л и ч а ю щ е е- ния сигналов содержит демультиплексор, с я тем, что каждый преобразователь сигна- сумматор по модулю два и мультиплексор, лов содержит (n-1) ключей и (л-1) субблоков выход которого соедийен с выходом субблопреобразования сигналов. выходы всех 10 ка преобразования сигналов, первый вход ключей и первые входы всех субблоков пре- которого соединен с первым входом суммаобразования сигналов объединены и соеди- тора по: модулю два, второй вход которого нены с первым выходом преобразователя соединен с первым выходом демультиплексигналов, (и-1) следующих выходов которого . сора, информационный вход которого соесоединены соответственно с выходами {n-1) 15 динен с вторым входом субблока субблоков преобразования сигналов; 870 преобразования сигналов, третий вход корые входы которйх и информационный вход торого соединен с управляющими входами (и-1)-го ключа соединены с соответствующи-: демультиплексора и мультиплексора, перми входами первой группы преобразовате- вый и второй информационные входы котоля сигналов, третьи входы всех субблоков 20 рого соединены соответственно с выходом преобразователя сигналов соединены с вхо- .. сумматора по модулЮДва и вторым выходом дами второй группы" преобразователя " демультиплексора. сигналов, входы третьей группы которого..

1756883

3756883

1756883

П- 1 бала У

Составитель Е.Мурзина

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

Редактор О.Хрипта

Производственно-издательский комбинат "Патент". r. Ужгород, ул.Гагарина, 101

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

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

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