Устройство для умножения произвольных элементов полей галуа gf(р @ )

 

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

Социал истнчесине

Республни

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ i»90028l (6!) Дополнительное к авт. свнд-ву (22)Заявлено 30.07.79 (21) 2801892/18-24 с присоединением заявки М (23) Прнорнтет—

Опубликовано 23 ° 01 ° 82 ° Бюллетень 16 3

Дата опубликования описания 25,01.82 (5I)M. Кл.

G 06 F 7/49 Э®3®Фст ы11 кенхтет

CCCP ие аман хзабретехнй н етехытнй

I (53) УДК 681. .3(088.8) В.И. Долгов, И.Д. Горбенко, И.И. Сныткин,l

Н.В. Александров и Б.Я. Осипов

F (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПРОИЗВОЛЬНЫХ

ЭЛЕМЕ1- ТОВ ПОЛЕЙ ГАЛУА GF(pè) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных устройствах и микропроцессорах для умножения элементов расширения полей GF(P"), а также в системах кодирования, ус,тройствах обнаружения и исправления ошибок кодов, построение которых базируется на теории полей GF(Pn)

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

Однако данные умножители представляют значительную сложность и неприспособленность к большим полям GF(2 ) и не позволяют умножать произвольные

Ю элементы расширенных полей при любом простом P = 2, т.е. полей

GF(P"), где n = 1,2,3...

Наиболее близким по технической сущности к предлагаемому является устройство для умножения произвольных элементов полей Галуа ГГ(Р ), при P = 2, которое обеспечивает систематический комбинационнологический подход к умножению произвольных элементов F(х) и

Р(х}(F(x)=, х, Р(х)=p,х, i=0,1,..., m-1) поля GF(2 } с первообраэным полиномом g(x)=g x (i=

=0,1,... m).

Это устройство содержит (m-1) упорядоченных блоков умножения. На первый иэ них поступают сигналы элемента F(x) поля, а на остальные подаются выходные сигналы предшествующих.

B каждом блоке умножения вход умножается на Х для создания результирующего сигнала с модулем g(x). На вход

i-го формирователя частичных произведений соединенного с (i-1)-. 1 блоком умножения, поступают сигналы х F(x), t

I-й формирователь частичных произве90028

3 дений осуществляет логическое умножение на P и выдает частичное произведение Px F. Выходные сигналы m формирователей частичных произведений поступают на входы m суммирующих блоков для образования сигналов, соответствующих произведению Р)(F 1Io модулю g(x). Каждый суммирующий блок оперирует с соответствующими компонентами частичных произведений логи- щ ческих схем 121.

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

Цель изобретения — расширение функциональных возможностей за счет обеспечения умножения произвольиьас элементов A(x) и В(х) расширенных полей Галуа GF(P ) при произвольных простых Рт2 ои и различных производящих полиномах а(х), где a(x)=bj x, д

)-О, I,...n; А(х)- Я, х(, В()- В„х1, 1=0, 1,... n-1, А1, 8., Qj, =О,l,...р" 1; р"простое число, 36

Эта цель достигается тем, что в устройстве для умножения произвольных элементов полей Галуа GF(p ), содержащем и модульных блоков умножения, и блоков формирования частичных произведений и и блоков суммирования, причем входы первых групп модульных блоков умножения соединены со входами производящего полинома устройства, входы второй группы первого модульного блока умножения соединены со входами первой группы первого блока формирования частичных произведений и со входами первой группы произвольных элементов полей Галуа GF(p") устройства, выходы каждого j — ro (J I,..., n-1} модульного блока умножения соединены со входами первой группы (j+I)-ro блока формирования частичных произведений, входы второй группы каждого блока формирования частичных произведений соединены с соответствующими входами второй группы произвольных элементов полей

Галуа GF(p ) устройства, входы каждого к-го (к=l,...,n) блока суммирования соединены с к-ми выходами блоков формирования частичных произведений выходы блоков суммирования яв) 4 ляются выходами устроиства, каждыи вход производящего полинома и каждый вход первой и второй групп произвольных элементов полей Галуа GF(p") устройства содержит (р-1) шин, каждый вход и выход каждого модульного блока умножения, блока формирования частичных произведений и блока суммирования содержит (р-1) шин, каждый модульный блок умножения является блоком умножения по модулю а (х), р, где a(x) la х"; 1=0,1,...,n-1; а 0,1,...,р-l, каждый блок формирования частичных произведений содержит и узлов формирования частичных произведений, выполненных в виде матриц элементов И, первые входы которых соединены с шинами соответствующего входа первой группы узла формирования частичных произведений, а вторые входы соединены с шинами входа второй группы узла формирования частичных произведений, каждый блок суммирования является сумматором по модуЛЮ ре

На фиг. 1 представлена функциональ ная схема устройства; на фиг. 2 — схема модульного блока умножения; на фиг. 3 — схема блока формирования частичных произведений; на фиг. 41 схема модульного блока умножения по модулю a(x)„P для поля GF (34) и а(х) х -à d-а х -а„x" -ao; на фиг. 5то же, по модулю а(х)(Р для поля бг(З ) и а(х)=к ;а х"-а х -à х у

-а1х(-а; на фиг. 6 — то же по модуФ лю а(х)1 P для поля GF(5 ) и а(х}= х -a õ -а х"-а ; на фиг. 7 — то же по модулю а(х) P для поля GF(33) и а(х) х -х-2; на фиг. 8 представлена схема блока суммирования по модулю три для поля 6Р(3 ).

Устройство для умножения произвольных элементов расширенных полей

Галуа GF(P") (фиг. 1) содержит модуль— ные блоки 1-3 умножения по модулю

f (х)1 Р, блоки 4-6 формирования частичных произведений, блоки 7-9 суммирования по модулю Р, входы 10 производящего полинома а(x), входы

1l и 12 произвольных элементов A(x) и В(х), выходы 13, на шины которых поступают коэффициенты полннома элемента С(х)=A(x) ° 8(х) (modd а(х)1 P).

Модульный блок 1, 2 или 3 умножения по модулю а(х)1 P (фиг.2) содержит группы 14 — 16 логических узлов

17-19, элементы И 20, блокй 21-23

5 900- суммировапия по модулю P при этом каждая группа 14, 15 пли 16 содержиr (р-1) логических узлов 17-19> каждый из которых содержит а с элементов И 20.

Узел формирования частичных произведений (фиг. 3) содержит матрицы 24-26 элементов И 27.

Модульный блок 1, 2 нли 3 умножения по модулю а(х)» P для поля GF(3 ) )О

l( и a(x)=x"-а х -a x"-a„x -а„(фиг. 4) содержит группы 28-31 логических узлов элементов И, блоки 32-35 суммирования по модулю три.

Модульный блок 1, 2 или 3 умно- is жения по модулю а(х)« Р для поля

GF (3 ) и а (х) =х -а„x"-а х -а х -а» ° х3 !. «

-a (фиг. 5) содержит группы 36-40 логических узлов элементов И и блоки 41-45 суммирования по модулю три. щ

Модульный блок 1, 2 или 3 умножения по модулю а(х)» P для поля

GF (5 ) и а (x) =x -а х -а» х -а (фиг. 6) содержит группы 46-48 логических узлов элементов И, а также блоки 49- д5

51 суммирования по модулю пять.

Модульный блок 1, 2 или 3 умножения по модулю а(х)» P для поля

GF(3 ) и а(х)=х -x-2 (фиг. 7) содер— жит группу 52 элементов И 53-56, группу 57 элементов И 58 и 59 и блоки 60 и 61 суммирования по модулю три.

Блок 7, 8 или 9 суммирования по модулю три для поля Сг(3 ) (фиг.8) содержит элементы И 62-64, элементы

ИЛИ 65-68, элементы запрета 69 и 70.

Из теории полей GF(P ) известно, что если — первообразный элемент поля GF(P ), то все элементы поля 40

GF(P ) являются степенями 9, т.е.

GF(P )= (8, 8, 9", 6, ° ° °,e>

, (modda (х) Р) .

При этом a(x) является первообразным ,неприводимым над GF(P) полиномом степени и и а (6) =О.

Например, коэффициенты полинома

А вычисляются следуюшим обпазом.

2s Ъ и 3.\ a2. W И ы

А> =Аа-aq=2„А» — -Аа а»+Ад =2«A =А а

+A О. Коэффициенты полинома А С вы4 и числяются следующим образом: А

=А . а =421 (пюд3), А» =А ° а„+А.

g5 2С И 2С

=3 0(mod3), А =Аг ° а +А =2.

Таким образом, любой А"-й элемент

:поля GF(P ) может быть найден путем возведения X=8 в степень 1-1 и приведения A =X по modda(х) Р, т.е.

1 1-» 50 двойному модулю. В случае, если известен А» " -й элемент поля, то для нахождения А» -ro элемента достаточно А« -й элемент умножить на х и

55 результат привести по modda(x)„P, т. е.

А =А x(modda(x)» P) .

Элементы поля GF(3 ) вычислены согласно формулам, приведенным выше.

81 6

GF (3S ), P=3, n=3, а (х) =х! -x- R, ао=2, а„=1, а =О.

А1 — ) A "î o=х+! А»9 =х +2х+1 и

А =х Ан =х +х А =2х +2х+2

А> =х" А =хс+х+2 А =2x +х+1

А" =х+2 А» =хс+2 А =х +1

А =х" +2х А« « =2 А =2х+2

А =2х +x+2 A»+ =2х- А =2х +2х

А =x +x+! A«C =2х А =2х +2х+!

А =х "+2х+2 А" =2х+) А 2х +1

А =2х +2 А =2х+х

Например, 6-Й элемент А вычисляется путем умножения элемента АС на х и приведения результата по двойному модулю а (x) =xS -x-2» Р=З А x(xi+ 2х)» к x=x 4-2х = 2x x+2 (пюсЫа (х)» P ) .

Таким образом, для отыскания всех элементов (полиномов)поля ОГ(Р") необходимо рекуррентно умножать ра- . нее вычисленный предшествующий эле-мен. (полином) на х и результат приводить no modda(x)» P. Эта операция тождественна сдвигу влево полпнома предыдущего элемента (т.е. увеличение на единицу степени х каждого члена полинома) и, если наибольшая степень при х равна п, то из результата необходимо вычитать полином a(x) столько раэ, чтобы результат вычитания не имел степени х равной и, а затем результат привести по модулю P.

Существует более упрощенное рекуррентное правило вычисления элементов полей GF(P ). Рассмотрим некоторые примеры на поле GF(3 ) . з

Чтобы получить значения коэффициентов при степенях х x«õ элемента ,А (т. е. А„, А„, А ) достаточно провести следующие операции с коэффициентами А«,, А„, А элемента А ь и а а»а1 первообразного полинома

a(x), умножая А иа ао и приводя реС зультат по модулю Р=З, получаем

« ,А =1(А а =4 (mod 3), умножая А на а1 и прибавляя к результату А с

1 получаем (после приведения по модулю

Р=З) А» =1(А ° а, «-А =4=1(mod3) умножая А на а и прибавляя к реC зультату А» (после приведения по моС дулю P=3) получаем А =1 (A ° à 1-А« =1), С

»

Таким образом, А =х +x+1.

9002

Ф сост ф Выходы входы

1 2

0 О

1 0

1 1

1 0

0 0

0 0

1 2

0 О

1 0

l 1

О 0

О О

1 1

1 0

О

0

1

4

0

0

1

3

5

1 1

1 0! 1

Таким образом, данное рекуррентное правило сводится к тому, что ко" зффнциенты каждого последующего поли- . нома-элемента А" поля GF(P ") вычисляются с использованием коэффициен- S тов предыдушего полинома-элемента А и первообразного, полинома а(х) по правилу

Ao," М"„, ° a (modp),A уА„,. а +

А)» (ДР) . 1в

Данное правило лежит в основе построения и функционирования модульного блока l 2 или 3 умножения по модулю а(х)» P. Данный блок осуществляет умножение полинома-элемента 1э

А -ro на х и приведение результата

К по modda(x) Р, тем самым осуществляется получение элемента А"+" -го. Действительно, группы 14-16 логических узлов 17-19, каждый иэ которых сос- 26 тоит иэ а элементов И 2О, осущек ствляют умножение коэффициента А„«» полинома А -ro на коэффициенты к ар, a».. °,a„, путем размножения каждого входа входной шины, отобра- 2З жающей коэффициент А„», в а! раз в логических узлах 17" 19 каждой группы

14-16. Если А„ *2, то сигнал сук ществует на первых двух входах шины А„, если А, 1 Р-1„ o с На 36 к на Р-l входах шины А„ и т.д. Если к

Ф а!*2, то сигнал существует иа первых двух входах шины, отображающей коэффициент aj и т.д.

Таким образом,. число активных (на которых существуют сигналы) выходов каждой группы 14-16 равно произведению активных входов шин A -< и а1. Так как любой коэффициент А не превышает Р"1, а коэффициечт aj 4o не превышает Р"1, то число всех выходов кэждой группы в общем случае не превышает 1,)А(Р-1)

Блоки 21-23 суммирования по модулю P (фиг. 2) представляют дешиф81 8 раторы, так как осуществляют операцию преобразования сигналов на своих входах в сигналы на своих выходах. Для блока 21 число входов определяется лишь числом выходов группы 14, для блока 22 число входов дополняется числом входов шины А ,для блока 23 число входов дополняется числом входов шины А"„ . Число выходов блоков 21-23 равно P-l. Та:ким образом, блоки 21-23 дополнительно осуществляют операцию сложения результат умножения к, к

А ф! с А

Функциональные схемы модульных блоков 1, 2 или 3 умножения по модулю а(х)1 P для различных конкретных полей GF(3")ca(x)х"-a> x -.а х -а x а, GF(3 )cs{x)x<-а х>-а хз -а х -à х<3 л

-ае; GF (5 ) ñà (х) х "а х -а„х" -а, представлены на фиг. 4-6. Эти функциональные схемы отображают конкретное построение для конкретных полей

GF функциональной схемы общего случая, представленной на фиг. 2.

Для поля GF(3>) с а{к)=х -х-2 (фиг. 7) функциональная схема модульного блока l, 2 или 3 умножения по модулю а(х)х -х-2, Р=З. Так как а О, то группа элементов И, осуществляющая умножение А на а =0 отсутствует, отсутствует из-за ненадобности и третий блок суммирования по модулю P=3. Так как а 2, то группа 52 содержит четыре элемента

И 53-56, а группа 57 — два элемента

И 58 и 59. Блоки суммирования 7-9 по модулю Р для любых полей 6Г(Р") представляют дешифраторы. Схема блока суммирования по модулю P 3 для поля GF(3 ) (фиг. 8) реализует приведение по модулю три сигналов на своих четырех входах в сигналы на своих двух выходах (см. таблицу) .

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

Галуа GF(P ) устройства, выходы каждого j-го (j=l,...,n-!) модульного блока умножения соединены со входами первой группы (j+1)-го блока формирования частичных произведений, входы второй группы каждого блока формирования частичных произведений соединены с соответствующими входами второй группы произвольных элементов полей Галуа GF(p") устройства, входы каждого к † (k-=1,...,п} блока суммирования соединены с к-ми выходами блоков формирования частичных произведений, выходы блоков суммирования являются выходами устройства, о т— л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения функциональных возможностей устройства за счет обеспечения умножения произвольных элементон полей

Галуа GF(p") при произвольных прос9 9ОО28

Рассмотрим процедуру умножения двух любых элементов А х и В(х)поля

GF(P ). Умножение двух полиномэлементов A(x) и 8(х) можно осуществить путем суммирования по mod Р частичных произведений полинома

A(x) на слагаемые полинома В(х), т.е. произведений вида А"(х)=А(х)»

< В - x ), приведенных по modda(x)< P., Умножение А(х) на х и приведение 10 результата по modda(x)< P осуществлено при помощи одного модульного блока 1 умножения Во модулю а(х)! P а умножение А(х) на х (равнозначно умножению А " (x) на x) и приведение результата по modda(х)! Р, осущестнляется при помощи цепочки, состоявшей иэ модульных блоков 2 и 3 умножения по модулю а(х) Р, выходы каждого предыдущего при этом соединяются 20 со входами каждого последующего.

Умножение произведения А(х)х", приведенного по modda, на коэффициент В можно осуществить при помощи блоков 4-6 формирования частичных 25 произнедений, функциональная схема которых представлена на фиг. 3. Данная операция осуществляется путем размножения каждого входа шины А !,ЗВ1 раэ 1-й матрицей 24-26 элементов И 27 0

К каждой j é матрице 24-26 элементов И 27 подведено P-l шин, отобра— жающих коэффициент А) и P-1 шин, отображающих коэффициент В1, при этом каждая j ÿ матрица 24-26 элемен35 тов И 27 имеет (Р-1) групп, по (Р-1) выходов, отображающих произведение коэффициентов А1 В . Каждый

i †и блок 4-6 имеет и матриц 24-26 элементов И 27 и тем самым — и выа 0 ходов по (P-1) шин в каждом выходе.

Таким образом, выходные шины каждого i-го блока 4-6 отображают частичное произведение A(x)-(В х ).

Суммирование по mod р частичных произведений осуществляется в блоках

7-9 суммирования по модулю P. При этом ко входам блока 7 подведены первые выходы блоков 4-6, ко входам блока 8 — вторые выходы блоков 4-6, 50 а ко входам блока 9 и-6 выходы блоков 4-6. Первые выходы блоков 4-6 отображают коэффициенты частичных произведений при степени х, вторые выходй блоков 4-6 — коэффициенты

55 частичных произведений при степени х" и т.д.

Таким образом, блок 7 осуществляет суммирование (привсдение) по мо1 !О дулю P коэффициентов при х нсех частичных произведений, блок 8 осуществляет суммирование по модулю P коэффициентов при х" всех частичных произведений, а блок 9 — коэффициентов при х" " всех части- ных произведений.

Блоки 7-9 могут быть выполнены в виде дешифраторов. Выходы блоков

7-9 отображают коэффициенты соотнетственно Со, С„,..., Сь полинома, представляющего собой результат умножения rro modda(x)< P полиномов-элементов А(х) и В (х) поля GF (Р" ) .

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

A(x) и B(x) полей GF(P") при любых значениях простого числа Р, .степени и и первообразных неприврдимых полиномов а(х).

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

11 900281 12 тых р>2 и и и различных производящих ды которых соединены с шинами соотполиномах, каждый вход производящеф9 ветствующего входа первой группы полинома и каждый вход первой и вто- узла формирования частичных произверой групп произвольных элементов по- дений, а вторые входы соединены с лей Галуа GF(p ) устройства содержит шинами входа второй группы узла фор(р-1) шин, каждый вход и выход каждого мнрования частичных произведений, каж— модульного блока умножения, блока дый блок суммирования является сумформирования частичных произведений матором по модулю P. и блока суммирования содержит (р-1) ,шин, каждый модульный блок умножения tO Источники информации, является блоком умножения по модулю принятые во внимание при экспертизе а(х),р, где а(х)(а х ; i O,l,..., i Bartee Т.С, and Schneider D.2. и-1; а 0,1,...,р-1, каждый блок Computation witn Finote Fie ds. формирования частичных произведений 1 u formation and Controi, 61, 1963, содержит и узлов формирования час- ts рр. 79-98. тичиых произведений, выполненных в 2. Патент США Ф 4037093, виде матриц элементов И, первые вхо- кл. 235-164, 1977 (прототип).

900281

lip к

I н

Составитель В, Березкин

Редактор Л. Филиппова Техред М. Надь Корректор Г. Реюетник

Заказ 12183/66 Тираж 731 Подписное

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

113035 Москва Ж-35 Ра ская наб. д. 4/5 к Х А

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