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

элемента В(х), выходные шины коэффициентов полинома, представляющего собой частичное произведение (А (х), В), Функциональная схема блока 10 формирования полиномов и элементов мультипликативныхгрупп, представленная на фиг. 4, содержит четыре коммутатора 24-27, два элемента ИЛИ 28 и 29, пять элементов И 30-34, элемент НЕ 35 и четыре регистра хранения коэффициентов полиномов 36-39. Блок 11, также представленный на фиг. 4, содержит триггер 40, циклический регистр 41, счетчик 42, элемент И 43, генератор 44 тактовых импульсов и схему 45 ввода данных (клавиатуру), Сущность алгоритма работы устройства заключается в следующем. Из теории полей Галуа GF(P) известно, что если в- первообразный элемент поля GF(P), то все элементы поля GF{P) являются степенями в, т.е.. GF(P) {0; ..,f (modd а(х), Р). При этом а(х) является первообразным неприводимым над GF(P) полиномом степени п, а(0) 0, Таким образом, любой А-й элемент поля GF(P) может быть найден путем возведения х в степень (i-1) и приведения А по modd(a,{x), Р). Если известен А -и элемент поля, то для нахож,1.1-1 . дения А-го элемента достаточно А -и элемент поля умножить Не X и результат привести nomodd(a(x), Р), т,е. А А х modd а(х)Р, Как видно эта операция тождественна сдвигу влево полинома предыдущего элемента (т,е. увеличение на единицу степени X каждого члена полинома и,если наибольшая степень при х равна п, из результата необходимо вычесть полином а(х) столько раз, чтобы результат вычитания не имел степени X равной п, а затем результат привести по модулю). Из данной методики вытекает другое более упрощенное рекуррентное правило вычисления элементов полей GF(P), Это рекурентное правило сводится к следующему: коэффициенты каждх го последующего полинома - элемента А поля вычисляются с использованием коэффициентов предыдущего полинома - элемента А и первообразного полинома а(х) по правилу А| , зо (mod Р), . А| ± А - 1 aj + Af- 1 (mod Р). Данное правило лежит в основе построения и функционирования блока умножения по модулю (а(х), Р), представленного на фиг.2. Данный блок осуществляет умножение полинома - элемента на х и приведение результата по modd (а(х), Р). а следовательно,получение элемента А -го. Действительно, группы 12-14 логических злов, каждый из которых состоит из а) злементов И, осуществляет умко-кение коэффйциентй An - 1 полинома А-го соответственно на коэффициенты ао, aian-i путем рйзмножен /1Я каждого входа входной шины, отображающей коэффициент An - i в ai раз 3 логических узлах каждой группы 12-14 злементов И. Если An - 1 Р - 1, то сигнал существует на Р - 1 входах шины Ап - i и т.д. Если aj 2, то сигнал существует на первых двух входах шин, отображающей коэффициент aj и т.д. Таким образом, число активных (на которых существуют сигналы) выходов каждой группы элементов И равно произведению активных входов шин Ап - 1 и З. Так как любой коэффициента не превь1шает Р 1.3 коэффициент AI не превышает Р - 1, -гjQ чу;сло всех выходов каждой группы в общем случае не превышает i-J (Р - 1) . Суб17 суммирования по модулю Р (фиг. 2) представляют по сути дела дешифраторы, так как осуществляют операцию преобразования сигналов на своих входах в сигналы из своих выходах. Для субблока 15 число входов определяется лv1шь числом выходов групп элементов И, для субблока 16 число входов, дополняется числом входов шины АО, для субблока 17 число входов дополняется числом входов шинь АП -2. Число вв1ходоЕз субблоков 15 17 равно Р - 1. Таким образом, субблоки 15 и 16 дополнительно осуществляют операцию сложен я результата умножения An -1-aj с 1. Режимы работы устройства. 1.Умножение произвольных элементов А1х)и В(х) полей GF(P). а)при формировании элемента А(х) и изменяющемся элементе В(х); б)при фиксированном элементе В(х) и изменяющемся А(х); в)при изменяющихся элементах А(х) и В(х). 2.Формирование элементов полей Галуа GF(P). а)при использовании результатов умножения, элементов С(х), в качестве элементов В(х} и изменяющемся элементе А(х); б)прм использовании элементов С(х) в качестве элементов В(х) и изменяющемся элементе А(х). 3.Формирование неинверсно-изоморфных полей GF(P), т,е. изменение первообразных неприводи.мых полиномов а(х) во всех указанных выше режимах.

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

Для работы устройства в различных режимах блок 10 должен выдать:

1)по первому групповому выходу - коэффициенты первообразного неприводимого полинома а(х);

2)по второму групповому выходу - коэффициенты полинома элемента А(х);

3)по третьему групповому выходу - коэффициенты.полинома элемента В(х)для режима умножения или результата умножения элементы С(х) для режима формирования элементов поля.

Блок 10 .формирования полиномов и элементов мультипликативных групп совместно с блоком 11 микропрограммного управления работает следующим образом.

На клавиатуре 45 оператором набирается программа работы устройства, коэффициенты первообразного неприводимого полинома а(х), коэффициенты полинома элемента А(х) и коэффициенты полинома элемента В{х). Программа работы устройства записывается в циклической регистр 41 хранения программы и состоит из набора единиц и нулей (см. таблицу.

Коэффициенты первообразного неприводимого полинома а(х). коэффициенты полинома - элемента А(х), коэффициенты полинома - элемента В(х) записываются в соответствующие регистры 37-39 хранения коэффициентов полиномов, причем эта запись происходит одновременно во все ячейки регистров 37-39, а считывание происходит с последних п ячеек этих регистров.

После этого с выхода клавиатуры 45 выдаётся импульс Начало работы, который поступает на вход генератора 44 тактовых импульсов, который начинает генерировать тактовую последовательность импульсов, поступающую на вход счетчика 42 через элемент И 43, который открыт единичным потенциалом, поступающим на его вход с инверсного выхода триггера 40, находящегося в нулевом состоянии. Тактрвые импульсы, поступающие с выхода элемента И 43 (рассматривается режим работы устройства, описанный под номером 1а), поступают на входы элементов И 32-34, в соответствии с режимом работы открытым оказывается лишь один элемент И 32 и тактовые импульсы, проходя через этот элемент, поступают на тактовый вход регистра 37 хранения коэффициентов полиномов В(х) и циклически сдвигают записанную в нем информацию на

п разрядов, т.е. нз выходах регистра 37 окажутся коэффициенты следующего полинома В(х). После того, как произойдет сдвиг на п разрядов, т.е. генератор 44 выдает п тактовых импульсов, счетчик 42 выдает импульс, который приводит триггер 40 в единичное состояние, производит сдвиг программы в регистре 41 и сбрасывает счетчик 42 нулевое состояние. Нулевой потенциал инверсного выхода триггера 40 закрывает элемент И 43, прекращая поступление тактовых импульсов для сдвига коэффициентов полиномов. Единичный импульс с прямого выхода триггера 40, открывает коммутаторы 25-27,

5 В результате на входы первых групп блоков 1-3 умножения по модулю а(х), поступают с выхода коммутатора 27 коэффициенты первообразного неприводимого полинома а(х), с коммутатора 25 - коэффициенты полинома

0 А(х), а по третьей выходной шине - коэффициенты полинома В(х). После этого происходит умножение элементов А(х) и В(х). Умножение двух полиномов элементов А(х) и В(х) можно осуществить путем суммирова5 ния по mod Р частичных произведений полинома А(х) на слагаемые полиномы В(х), т.е. произведение вида А (Х) А(х) В(х), приведенных по modd (а(х), Р). Умножение А(х) на X и приведение результата по modd (а(х), Р)

0 осуществляется посредством одного рассмотренного блока умножения по модулю (а(х), Р), а умножение А(х) на х (равнозначно умножению ) на X) и приведение результата по модулю modd (а(х), Р) осуществляется посредством цепочки, состоящей из i блоков умножения по модулю (а(х), Р), выходы каждрго предыдущего при этом соединяются с входами каждого последующего из блоков. Умножение произведения А(х)-Х

0 приведенного по modd (а(х), Р) на коэффициент Bf можно осуществить посредством блоков 4-6, функциональная схема которых представлена на фиг. 3. Данная операция осуществляется путем размножения каждого входа шины А - i и Bi посредством J-й группы элементов И. К каждой J-й группе элементов И подведено (Р - 1) входов, отображающих коэффициент А и (Р - 1) входов.

0 отображающих коэффициент Bi, при этом каждая i-я группа элементов И имеет (Р - 1) групп по (Р - 1) выходов, отображающих

произведение коэффициентов AJ Bi, каждый i-й узел элементов И имеет п групп элементов И и, следовательно п шин по (Р - 1) выходов в каждой шине. Таким образом, выходные шины каждого i-ro узла элементов И, к которому подведены входные шины, отображающие Bi полинома В(х) и входные

шины, отображающие произведение А(х) -А(х).х modd (а(х), Р) отображают частичное произведение A(x)(Bi-x),

Суммирование по mod Р частичных произведений осуществляется в блоках 7-9 суммирования по модулю 3. При этом к входам блока 7 подведены первые выходные шины блоков 4-6, к входам блока 8 - вторые выходные шины блоков 4-6, а к входам блока 9 - (Р - 1)-е выходные шины блоков 4-6. Первые выходные шины блоков 4-6 отображают коэффициенты частичных произведений при степени Х°, вторые выходные шины блоков 4-6 - коэффициенты частичных произведений при степени Х t/; т.д. Таким образом, блок 7 осуществляет суммирование (приведение) по модулю Р коэффициентов при Х° всех частичных произведений, блок 8 - суммирование по модулю Р коэффициентов при Х всех частичных произведений, а блок 9 - коэффициентов при Х всех частичных произведений.

Блоки 7-9 тоже являются дешифраторами, функциональное построение которых аналогично субблокам суммирования по модулю Р. Выходные шины (по Р - 1) выходов блоков 7-9 отображают коэффициенты полинома С{х), представляющего собой результат умножения по modd (а(х), Р). полиномов элементов А(х) и В(х) поля GF(P). Этот оезультат по выходным шинам устройства, поступает на выходы блока 10 и далее записывается в регистре 36 хранения коэффициентов полиномов С(х) и поступает на входы элемента ИЛИ 29, на выходе которого образуется единичный потенциал, который является разрешающим импульсом для записи результата в регистре 36 и переводит триггер 40 в нулевое состояние.

В результате оказываются закрытыми элементы И 30 и 31 и коммутаторы 25 и 27, а элемент И 43 оказывается открытым, /i TaKtoBbte импульсы Б соответствии с режимом работы циклически сдвигают информацию в одном или нескольких регистрах 37-39. Одновременно тактовые импульсы подсчитываются счетчиком 42. Как только будет произведено п сдвигов, т.е. на вь ходах регистров 37--39 окажутся коэффициенты полинома А(х), В(х) или С(х}. счетчик 42 выдает импульс, по которому процесс работы, блока повторяется, но уже в другом режиме, записанном в рег11стре41 и сдвинутом ранее поступившим импульсом переполнения со счетчика 42.

Выбор режима работы устройства определяется состоянием выходов регистра 41. Единичное состояние его выхода говорит о том, что происходит изменение тех коэффициентов полинома А(х), В(х) или непоиводимого полинома а(х), к входу регистра хранения одного из которых 37 или 38 или 39 через соответствующие элементы И 32-34 подсоединен этот выход. При реализации режимз формирования полей GF(P) регистр 41 должен выдать также единичный потенциал, (соторый через открытый элемент И 31 открывает коммутатор 24 и на третьи выходы блока 10 вместо коэффициентов полинома В(х), поступают коэффициенты результата умножения, т.е. устройство работает в режиме формирования полей GF(P). Если, кроме того, происходит циклический сдвиг информации в регистре 39 через открытый элемент И 34 соответствующего выхода регистра 41, то устройство формирует неинверсно-изоморфные поля GF(P).

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

1.Устройство для умножения произвольных элементов полей Галуа GF{P) по 381. ев, N 900281, отличающееся тем, что, с целью расширения функциональных возможностей путем формирования мультипликативных групп задаваемых и производных полей Галуа GF(P), в него введены блок микропрограммного управления и блок формирования полиномов и элементов иу.пьтипл1л.ативных групп, выходы первой третьей групп которого соединены соответственно с входами первых групп модульных 6.ПОКОЗ умножения, входами первой группы первого блока формирования частичных произведений, входами второй группы первого мс,цульного блока умножения и входеми Б г о Р о и группы каждого .блока формирования частичных произведений, информационные входы первой - третьей групп Блока формирования полиномов соединены соответственно с выходами первой третьей групп блока микpoпpoгpa 7мнoгo управления, первый - втвертый выходы которого соединены соответственно с одноименными входами выбора режима работы блока формирования полиномов и элементов мульт1/1пликативных групп, информационные входы четвертой группы которого соединены соответственно с выходами блоков суммирования, пятый и шестой выходы блока М1лкропрограммного управления - соответственно с тактовым входом и управляющим входом блока формирования полиномов и элементоя г/льтиппикативных групг, управляющий выход которого соединен с входом блока микропрограммного управления.

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

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

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

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

Изобретение относится к прикладной вычислительной технике и может быть использовано'в специализированных вычислительных устройствах и микропроцессорахдля умножения, формирования, исследования свойств элементов расширенных полей GF(P), а также в системах кодирования, обнаружения и исправления ошибок кодов, построение которых базируется на теории полей Галуа GF(P") и является усовершенствованием основного изобретения по авт. св. СССР № 900281. Целью изобретения является расширение функциональных возможностей за счет формирования мультипликативных групп задаваемых и производных полей Галуа GF(P"), которая достигает- 'ся введением блока микропрограммного управления и блока формирования компонентов и элементов мультипликативных групп. 1 З.П.Ф., 4 ил., 1 табл.(ЛсИзобретение относится к прикладной вычислительной-технике и может быть использовано в специализированных вычислительных устройствах и микропроцессорах для умножения, формирования, исследования свойств элементов расширенных полей GF(P"), а также в системах кодирования, обнаружения и исправления ошибок кодов, построение которых базируется на теории полей Галуа GF(P").Цель изобретения - расширение функциональных возможностей за счет формирования мультипликативных групп задаваемых и производных полей Галуа.На фиг. 1-4 представлены функциональные схемы устройства; блока умножения и блоков формирования.Устройство содержит модульные блоки 1-3 умножения по модулю (а(х), Р), блоки 4-6 формирования частичных произведений.блоки 7-9 суммирования по модулю Р, блок 10 формирования полиномов и элементов мультипликативных групп и блок 11 микропрограммного управления 11.Функциональная схема блока умножения по модулю (а(х), Р), представленная на фиг. 2, содержит группы 12-14 по (Р - 1) логических узлов по, ai элементов И а каждом узле, субблоки 15-17 суммирования по модулю Р, логические узлы 18-20 группы 12, элементов И, входные шины коэффициентов полиномов а(х), А (х) и выходные шины •коэффициентов полиномов А'^^\Х).Функциональная схема блока формирования частичных произведений, представленная на фиг. 3, содержит группы 21-23 ^Элементов И по (Р-1) линеек по (Р-1) элементов И в каждой линейке, входные шины коэффициентов полинома элементов А*^(х), входную шину коэффициентов полиномаXIОю ю ю XI>&ю

П Режимы работы устройства; программа 1 - умножение произвольных элементов А(х) и Ь(х) полей GFCP) при А(х) const, В(х) vac; программа 2 - умножение произвольных элементов А(х) и В(х) полей GF(p) при В(х) const, А(х) vac; программа 3 - умножение произвольных элементов А(х) и В(х) полей GFCP) при А(х) vac; В(х) vac; программа k - формиррвание элементов полей Галуа GFC) при использовании результатов умножения, элементов С(х) и качестве элементов В(х) и неизменяющемся элементе; программа 5 - формирование элементов полей Галуа GFCF) при использовании элементов С(х) в качестве элементов В(х) и изменяющихся А(х),.А(х) vac; программа 6 - формирование неинверсно-изоморфных полей Галуа и умножение А(х) и В(х) при А(х) const, В(х) vac; программа 7 - формирование неинверсно-изоморфных полей Галуа и умножение A(x) иВ(х) при А(х) vac, В(х) const; пограмма 8 формирование иеинверсно-изоморфных полей Галуа и умножение А(х) и В(х) ПРИ А(х) vac,B(x) vac; программа 9 формирование неинверсио-изоморфных полей Галуа и формирование элементов при А(х) const, B(x)-vC(x), программа 10 - формирование неинверсно-изоморфных полей Галуа и формирование элементов при А(х) vac, В(х)С(х).

М

« /1-0

л

Ля

.

0f/2.2

«i

- с ч:

4

y-у

I «2

i.

« ч

-5;

- t:

Ssl

«« 5s

.L

-

«M