Устройство для умножения элементов конечных полей GF(2 @ ) Советский патент 1992 года по МПК G06F7/49 

8

11

п

ч|

ел о

00 00 00

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

2 m п

GF ( 2), образованных различными

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

2 т п

работы (где 2, п - граничная (наибольшая) степень расширения поля GF (2), при которой устройство умножения элементов конечных полей еще выполнит операцию умножения над конечным полем полиномов GF (2n); m - степень расширения поля GF(2), при которой устройство умножения элементов конечных полей выполняет операцию умножения над полем полиномов GF (2m), m 2,3...n; f(x) fmxm + fm-ixn 1 +...+f0 - неприводимый м ногбчлен, образующий поле CG (2т).

На фиг. 1 изображена функциональная схема устройства умножения элементов конечных полей; на фиг. 2 - блок формирования частичных произведений; на фиг. 3 - блок формирования младших коэффициентов; на фиг. 4 - блок1 старших формирования коэффициентов; на фиг. 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 формирования старших коэффициентов

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

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

Блок 10 выравнивания коэффициентов

(фиг. 6) содержит п (п+1)/2) элементов И 19 и (п-1) элементов ИЛИ 20 с числами входов, равными числам di n-l+1, где I - номер элемента 20 ИЛИ в блоке 10, I 1,2...п-1.

Блок 11 запрета (фиг. 7) содержит (п-1) субблоков 21 запрета и многовходовых сумматоров 22 по модулю два, преобразователь 18сигналов(фиг.8)блока9- п-1 ключей 23и п-1 субблоков 24 преобразования.

Субблок 24 преобразования (фиг, 9) содержит демультиплексор 25, сумматор 26 по модулю два и мультиплексор 27.

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

Если а(х) am-ixm 1 + ...aix + а0 и Ь(х) bm-ixm + ...bix + bo первый и второй элементы поля полиномов GF (2) образованного

неприводимым многочленом f(x) fmxm + 4-fm-i xm 1 + ... fix + f0 при a x, где ai, bi, fi GF (2), a- примитивный элемент поля GF (2m) и x - фиктивная переменная, использующаяся для записи элементов поля GF(2 )

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

b(x modHxHa 1.(xm-ft..,

v го-. L v , L .1 г г.л

-П(ЛТ .. т

2(,

-(Л Sapbl

ьГо

- ,2(w«),

V./ V. J w V iV MILAyy jA.I,

k,xw-(T... + + b0)

/2(rn-(),..

2(Z4bJx mo №l T o

tn- ,, ,2ta },..

S 2.a,i,)v+z 2яАИ«

vp+ i j-№xp+(j

m-i, 2(«-0

«HW-Zz.vjxvz: s.apb,c(.

v oVp+(;i г г r

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

55 ki apbq, где I 0,1,2,...m-1. - младP + q i шие коэффициенты произведения;

kj X apbq, где j m, m+1,...2(m-1), p +q J

старшие коэффициенты произведения. Тогда

m - 1 2 (m - 1)

c(x) 2 kix + 2 J « cm-ix1™-)-...

I 0j m

... + C1X + Co.

В регистрах 1-3 осуществляется прием, хранение и выдача коэффициентов ai, bi, fi соответственно. В регистре 4 осуществляется прием, хранение и выдача двоичного представления числа m (степени расширения поля полиномов GF (2m), над которым осуществляется операция умножения).

В блоке 5 осуществляется попарное умножение ар bq над полем GF (2) всех коэффициентов первого и второго сомножителей соответственно.

В дешифраторе 6 осуществляется формирование сигнала высокого уровня на т- ом выходе соответствующему двоичному представлению числа т.

В блоках 7 и 8 осуществляется формирование сигналов, соответствующих ki и старшим kj коэффициентам произведения.

В блоке 9 осуществляется формирование на его выходах сигналов, соответствующих степеням примитивного элемента поля

d.

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

В блоке 11 запрета осуществляется формирование на его выходах сигналов, со2(т-1)

ответствующих сумме 2 B блоке 12

j m

осуществляется формирование на его выходах сигналов, соответствующих коэффициентам ct произведения.

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

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

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

Процедура 1.

В исходном состоянии устройства на его входы коэффициентов первого и второго сомножителей, на входы коэффициентов не- 10 приводимого многочлена и на входы степени m расширения поля, а значит на информационные входы регистров 1-4 подаются сигналы низких уровней. Кроме того, регистры 1-4 сброшены в нулевое сбстоя- 5 ние посредством подачи импульсных сигналов высоких уровней на первый и второй входы сброса устройства, после чего на первый и второй входы сброса устройства подаются сигналы низких уровней, 0 При этом на выходах всех регистров 1-4 сформированы сигналы низких уровней, а значит, сигналы низких уровней сформированы также на всех выходах первой и второй групп выходов блока 5 формирования час- 5 тичных произведений на выходах блоков 7, 10 и 11, что, в свою очередь, приводит к формированию сигналов низких уровней на выходах устройства коэффициентов результата. 0 Процедура 2.

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

устройство будет умножать. 5 Такая настройка производится путем подачи импульсного сигнала на второй вход сброса устройства, а затем подачи на каждый 1-й вход устройства (I 1.2п-1) коэффициентов неприводимого многочлена 0 импульсного сигнала, соответствующий коэффициенту f|, а на входы устройства степени m расширения поля - импульсных сигналов, соответствующих двоичному представлению числа т, причем j-й вход 0

5 1,( +1) ) соответствует j-му

разряду двоичного представления числа т. При этом на том i-ом выходе регистра 3 и на том j-ом выходе регистра 4, для которых fi и j-ый разряд двоичного представления 0 числа m равны единице, формируются сигналы высокого уровня соответственно.

Значит, на m-ом выходе дешифратора 6, на m-ом входе второй группы входов блока 10 и на (т-1)-ом входе (при т 1) второй 5 группы входов блока 9 формируется сигнал высокого уровня, На выходах блока 9, а значит на второй группе входов блока 11 формируются сигналы, зависящие от сигналов на первой и второй группах входов блока 9

ачхри

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

Процедура 3.

Для выполнения умножения элементов

m -1

конечного поля GF (2m) а(х) Ј

т -1

Ь(х) 2/ bqxq необходимо на каждый

(п-т-И+р)-й вход устройства коэффициентов первого сомножителя и на каждый (q-M)-tf вход устройства коэффициентов второго сомножителя подать импульсные сигналы, соответствующие коэффициентам ар и bq соответственно, а на остальные входы устройства - подать сигналы низких уровней. При этом, на (п-т+1+р)-тых выходах регистра 1 и (д+1)-тых выходах регистра 2, для которых ар и bq равны единице, сформируются сигналы высоких уровней соответственно.

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

Процедура 4.

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

Процедура 5.

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

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

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

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

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

0 входы степени m расширения поля которого соединены с информационными входами четвертого (3 Iog2(n+1) С)-рэзрядного регистра, выходы которого соединены с входа- ми дешифратора, выходы которого

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

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

преобразователя сигналов (1 1п-2) и jные входы (п-2)-го преобразователя сигналов соединены с соответствующими выходами блока, входы первой группы кото5 рого соединены с входами второй группы каждого j-ro преобразователя сигналов и ) входами первой группы первого преобразователя сигналов, первый вход первой группы которого соединен с выходом источника сигнала высокого уровня, входы второй группы блока соединены с входами третьей группы каждого 1-го преобразователя сигналов, выходы 1-го преобразователя сигналов соединены с входами первой группы (1+1)-го преобразователя сигналов

((п-3)).

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

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

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

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

П

Фиг. 2

Фиг.6

п-1

п

/г

ггг

и

21

п

21

w

Фие.7

Фиг 8

25

27