Устройство для умножения произвольных элементов полей галуа gf (р @ )
Изобретение относится к прикладной вычислительной технике и может быть использовано'в специализированных вычислительных устройствах и микропроцессорахдля умножения, формирования, исследования свойств элементов расширенных полей 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>&ю
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (s>>s G 06 F 7/49
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
flO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 900281
{21) 4756245/24 (22) 03.11.89 (46) 30.01.92, Бюл. N 4 (72) И.И,Сныткин, И.Д,Горбенко и
В,И,Дмитриев (53) 681,325 (088.8) (56) Авторское свидетельство СССР
И 900281, кл. 6 06 Р 7/49, 1979. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПРОИЗВОЛЬНЫХ ЭЛЕМЕНТОВ ПОЛЕЙ ГАЛУА
GF(P") (57) Изобретение относится к прикладной вычислительной технике и может быть использовано в специализированных вычислительных устройствах и микропроцессорах
Изобретение относится к прикладной вычислительной технике и может быть использовано в специализированных вычислительныхустройствах и микропроцессорах для умножения. формирования, исследования свойств элементов расширенных полей
GF(P"), а также в системах кодирования, обнаружения и исправления ошибок кодов, построение которых базируется на теории полей Галуа GF(P ).
Цель изобретения — расширение функциональных возможностей за счет формирования мультипликативных групп задаваемых и производных полей Галуа.
На фиг. 1 — 4 представлены функциональные схемы устройства; блока умножения и блоков формирования.
Устройство содержит модульные блоки
1-3 умножения по модулю(а(х), P), блоки 4-6 формирования частичных произведений, 5U„„ 1709297 А2 для умножения, формирования, исследования свойств элементов расширенных полей
GF(P), а также в системах кодирования, обнаружения и исправления ошибок кодов, построение которых базируется на теории полей Галуа GF(P") и является усовершенствованием основного изобретения по авт. св.
СССР N 900281. Целью изобретения является расширение функциональных возможностей за счет формирования мультипликативных групп задаваемых и производных полей Галуа GF(P"), которая достигается введением блока микропрограммного управления и блока формирования компоНеНТоВ и элементов мультипликативных групп. 1 з.п.ф., 4 ил., 1 табл. блоки 7 — 9 суммирования по модулю Р, блок
10 формирования полиномов и элементов мультипликативных групп и блок 11 микропрограммного управления 11.
Функциональная схема блока умножения по модулю (а(х), P), представленная на фиг. 2, содержит группы 12-14 по (Р— 1) логических узлов по, ai элементов И в каждом узле, субблоки 15 — 17 суммирования по модулю Р, логические узлы 18-20 группы 12, элементов И, входные шины коэффициентов полиномов а(х), А (х) и выходные шины к
: коэффициентов полиномов А (х). к+1
Функциональная схема блока формирования частичных произведений, представленная на фиг. 3, содержит группы 21 — 23 элементов И по (Р-1) линеек по (P-1) элементов И в каждой линейке; входные шины коэффициентов полинома элементов А (х), к входную шину коэффициентов полинома
1709297 элемента В(х), выходные шины коэффициентов полинома, представляющего собой частичное произведение (А (х), В), I<
Функциональная схема блока 16 формирования полиномов и элементов мульти- 5 пликативных групп, представленная на фиг.
4, содержит четыре коммутатора 24 — 27, два элемента ИЛИ 28 и 29, пять элементов И
30 — 34, элемент HE 35 и четыре регистра хранения коэффициентов полиномов Зб-39. 10
Блок 11, также предст-вленный на фиг.
4. содержит триггер 40, циклический регистр 41, счетчик 42, элемент И 43, генератор 44 тактовых импульсов и схему 45 ввода данных (клавиатуру), 15
Сущность алгоритма работы устройства заключается в следующем.
Из теории полей Галу- GF(P ) известно, что если 19 — первообразный элемент поля
GF(P"), то все элементы поля GF(P") являют- 20 ся степенями 0, т.е.
GF(P") = (0; 8, О „„6 ) (modd а(х), Р).
При этом а(х) является первообразным неприводимым над GF(P ) полиномом степени и, а(0) =О. Таким образом, любой А -й 25 элемент поля GF(Pn) может быть найден путем возведения х = 19в степень (1-1) и приведения А = х по гподб(а,(х), Р), Если известен А -й элемент поля, то для нахох l I-1 мент поля умножить нв х и результат привести по modd!3(x), p), т.е, A1= A 1х modcI а(х)Р, Как видно эта операция тождественна сдвигу влево полинома предыдущего элемента (т.е. увеличение на единицу степени 35 х каждого члена полинома и, если наибольшая степень при х равна и, из результата необходимо вычесть пол ином а(х) столько раз, чтобы результат Bblчитания не имел степени х равной и, а затем результат привести 40 по модулю). Из данной методики вытекает другое более упрощенное рекуррентное правило вычисления элементов полей GF(P"), Это рекурентное правило сводится к следующему: коэффициенты каждо о по- 45 + следующего полинома — элемента А поля вычисляются с использованием коэффициентов предыдущего полинома — элемента А к и первообразного полинома а(х) по правилу А Ак — 1 а (mod Р), 50 An — ) = An — 1 31+ А — 1(mod Р, . Данное правило лежит е основе построения и функционирования блока умножения по модулю (3(х), P), представленного на 55 фиг.2. Данный блок осуществляет умножение полинома — элемента А -ro íà х и прик ведение результата no modd (а(х}, Р), а следовательно, получение элемента А * -го. Действительно, группы 12-14 ло; ических узлов, каждый из которых состоит из Bj элементов:4, acу1дествляет умно<кение коэффициен. а А„ --1 полинома А-го соответстК ВЕННО HB КОЭффиЦИЕНтЫ Зо, Bi: „., Bn-1 ПУТЕМ рBBìHoæåí «я каждого входа Входной шины. ОтзбоажаюЩЕЙ коэффиЦиент An — 1 В 31 Раз к в логических узлах каждой группы 12 — 14 к злемен oB И, Если An — 1 = i — 1, тс сигнал существует на Р— 1 входах шины А," — 1 и т.д. Если 3} = 2, то сигнал существует на первых двух входах шин, отображающей коэффициент BI и т,д. Таким образом, число активных (H3 ко —оры,х ",существуют сигналы) выходов каждой группы элементов И равно произведени:-о активных входов шин А, —, и BI. Т3к . Bк любой коэффициент BI че и ревы шает P — 1, 3 коэффициент Ai не превышает Р— 1, I< то ч icno всех выходов каждой группы в общем случае не превышает I j < (Р— 1) . Суб2 бло:ки 15-",7 суммирования по модул1О P (фиг. 2) представляют по сути дела дешифраторь, так как осугцествля,от операцию поеобразования сигналов HB своих Входах в cи "HBëû на своих выходах. Для субблока 15 - исло входоB определяется лишь числом Bûходов групп элементов И, для субблока 16 ЧИСЛО ВХОДОВ ДОПОЛНЯЕТСЯ ЧИСЛОМ ВХОДОВ К шУ1нь. А,, дл субблока 17 число входов допол н я ется числом axop oa li1 HHh! А., — 2. 1исК ло Выходов суббло<ов 15-17 равно Р— 1. ,:аким образом, суболо <и 15 и 10 Дополни:-ельно осуществляют операцию сложения результата умножения К An — 1. 3j С А1 — 1. Режимы раооты устройства. .. умножение произвольных элементов А(х) и В(х) полей 6Е(Р"). 3) г ри формировачии элемента А(х) и изменяюгцемся элемен е B(x}; б) при фиксированном элементе Р(х) и изменяющемся A(x); в) при изменяющихся элементах А(х) и "-(х} 2. Формирование элементов полей ГBлуа G F(P). а) при IëcïonüBOBBHèè результатов,множения, элементов С(х), в качестве элементов В(х, и изменя:ощемся элементе А(х}; б) при испсльзоВании элементов (х} в качестве элементов Б(х} и изменяющемся элементе А(х). 3. Формирование неинверсно-изоморфных полей GF(P ), т,е. изменение первообР3ЗНЫХ HPПРИВОДИМЫХ ПОЛИНСМСВ B(X) BO всех указакных вь ше режимах. 1709297 и разрядов, т.е. на выходах регистра 37 окажутся коэффициенты следующего полинома В(х). После того, как произойдет сдвиг íà и разрядов, т,е, генератор 44 выдает п тактовых импульсов, счетчик 42 выдает импульс. который приводит триггер 40 в единичное состояние, производит сдвиг программы в регистре 41 и сбрасывает счетчик 42 нулевое состояние. Нулевой потенциал инверс0 ного выхода триггера 40 закрывает элемент И 43, прекращая поступление тактовых импульсов для сдвига коэффициентов полиномов, Единичный импульс с прямого выхода триггера 40, открывает коммутаторы 25-27. В результате на входы первых групп блоков 1 — 3 умножения по модулю а(х), поступают с выхода коммутатора 27 коэффициенты первообразного неприводимого полинома а(х), с коммутатора 25 — коэффициенты полинома A(x), а по третьей выходной шине — коэффициенты полинома В(х). После этого происходит умножение элементов А(х) и В(х), Умножение двух полиномов элементов А(х) и B(x} можно осуществить путем суммирования по mod P частичных произведений полинома А(х) на слагаемые полиномы В(х), т.е. произведение вида А(х) = А(х)- В(х), приведенных по modd (а(х), Р). Умножение А(х) на Х и приведение результата по modd (а(х), P) осуществляется посредством одного рассмотренного блока умножения по модулю (а(х), Р), а умножение А(х) на х (равнозначно умножению А (x) на Х) и приведение реь1 зультата по модулю modd (а(х), P) осуществляется посредством цепочки, состоящей из 1 блоков умножения по модулю (а(х), Р), выходы каждого предыдущего при этом соединяются с входами каждого последующего из блоков. Умножение произведения А(х) Х приведенного по modd (а(х), P) на коэффициент В> можно осуществить посредством блоков 4.-6, функциональная схема которых представлена на фиг, 3. Данная операция осуществляется путем размножения каждого входа шины AI — 1 и В1 посредством j-й группы элементов И. К каждой j-й группе элементов И подведено (P — 1) входов. отображающих коэффициент А и (P — 1) входов, отображающих коэффициент Вь при этом каждая i-я группа элементов И имеет (P — 1) групп по (P — 1) выходов, отображающих произведение коэффициентов А Вь каждый 1-й узел элементов И имеет и групп элементов И и, следовательно и шин по (Р— 1) выходов в каждой шине. Таким образом, выходные шины каждого i-го узла элементов И, к которому подведены входные шины, отображающие Bi полинома В(х) и входные Выбор режимов работы устройства происходит автоматически и определяется программой, записанной в циклическом регистре 41 хранения программы.(см, таблицу). 5 Для работы устройства в различных режимах блок 10 должен выдать: 1) по первому групповому выходу — коэффициенты первообразного неприводимого полинома а(х); 1 2) по второму групповому выходу — коэффициенты полинома элемента А(х); 3) по третьему групповому выходу — коэффициенты.полинома элемента В(х) для режима умножения или результата умножения — 15 элементы С(х) для режима формирования элементов поля. Блок 10,формирования полиномов и элементов мультипликативных групп совместно с блоком 11 микропрограммного уп- 20 равления работает следующим образом. На клавиатуре 45 оператором набирается программа работы устройства, коэффициенты первообразного неприводимого полинома а(х), коэффициенты полинома — 25 элемента А(х) и коэффициенты полинома— элемента В(х). Программа работы устройства записывается в циклической регистр 41 хранения программы и состоит из набора единиц и нулей (см. таблицу . 30 Коэффициенты первообразного неприводимого полинома а(х). коэффициенты полинома — элемента А(х), коэффициенты полинома — элемента В(х) записываются в соответствующие регистры 37 — 39 хранения 35 коэффициентов полиномов, причем эта запись происходит одновременно во все ячейки регистров 37-39. а считывание происходит с последних и ячеек этих регистров. 40 После этого с выхода клавиатуры 45 выдается импульс "Начало работы", который поступает на вход генератора 44 тактовых импульсов, который начинает генерировать тактовую последовательность импульсов, 45 поступающую на вход счетчика 42 через элемент И 43, который открыт единичным потенциалом, поступающим на его вход с инверсного выхода триггера 40, находящегося в нулевом состоянии. Тактовые импуль- 50 сы, поступающие с выхода элемента И 43 (рассматривается режим работы устройства. описанный под номером 1а), поступают на входы элементов И 32 — 34. в соответствии с режимом работы открытым оказывается 55 лишь один элемент И 32 и тактовые импульсы, проходя через этот элемент, поступают на тактовый вход регистра 37 хранения коэффициентов полиномов B(x) и циклически сдвигают записанную в нем информацию на 1 > 09 39 7 шины, отобража ощие произведение А(х) = = А(х) х tmodd (а(х), Р)) отображают частичное произведение А(х) (Bl х). Суммирование по mod Р частичных произведений осуществляется в блоках ";-9 суммирования по модулю 3. При этом к входам блока 7 подведены первые выходные шины блоков 4-6, к входам блока 8 — вторые выходные шины блоков 4 — 6, а к входам блока 9 — (P — 1)-е вь>ходные шины блоков 4-6, Первые выходные шины блоков 4 — 6 отображают коэффициенты частичных произведений при степени Х, вторые выходные шины блоков 4-6 — коэффициенты частичных произведений при степени X и т,д, Таким обра1, зом, блок " осуществляет суммирование (приведение) по модулю Р коэффициентов при Х всех частичных произведений, блок 8 — суммирование по модулю Р коэффициентов при Х всех частичных произведений, а 1 блок 9 — коэффициентов при Х" всех частичных произведений. Блоки 7-9 тоже являются дешифраторами. функциональное построение которых аналогично субблокам суммирования по модулю Р, Выходные шины (по Р— 1) выходов блоков 7 — 9 отображают коэффициенты полинома С(х), представляющего собой результат умножения по modd (a(x), Р), полиномов элементов А(х) и В(х) поля 6Р(Р"). Этот оезультат по выходным шинам устройств-, поступает на выходы блока 10 и далее записывается в регистре 36 хранения коэффициентов полиномов С(х) и поступает на входы элемента ИЛИ 29, на выход которого образуется единичный потенциал, который является разрешающим импульсом для записи результата в регистре 36 и и реводит триггер 40 в нулевое состояни"". В результате оказыва,отся закрытыми злементь> И 30 и 31 и коммутаторы 25 и 27, а элемент И 43 ока"-ывается открытым, и тактовые импульсы в соответствии с режимом работы циклически сдвигают информацию в одном или нескольких регистрах 37 — 39, Одновременно тактовые импульсы подсчитываются счетчиком 42, Как только будет произведено и сдвигов, т.е. на выходах регистров 37-39 окажутся коэффициенты полинома А(х), В(х) или С(х), счетчик 42 выдает импульс, по которому процесс работы блока повторяется, но уже в д,>yI.ov. режиме, записанном в Оегистре 41 и сдвинутом ранее поступившим импульсом переполнения со счетчика 42. Выбор режима работы устройства Определяется состоянием выходов регистра 41. Единичное состоян le его выхода говорит о том, что происходит изменение тех коэффициентов полинома А(х), В(х) или непоиводимого полинома а(х), к входу регистра хранени>-; одного из которых 37 или 38 или 39 через соответствующие элементы И 32 — 34 го, соединен этот выход. При реализации 5 !e-:.«има формирования полей GF(P") регистр 41 должен выдать также единичный потенциал, который через открытый алеман- И 31 открывает Kîìмутатор 24 и на ретьи выходы блока 10 вместо коэффици10 ентов полинома В(х), поступают коэффициенты результата умножения, т.е. устройство работает в режиме формирования полей GЕ(Р" ), Если, кроме того, происходит циклический сдвиг информации в регистре 39 че15 рез отк-ытый элемент И 34 соответствующего выхода регистра 41, то устройство формирует неинверсно-иэоморфные поля GF(P ), Формула изобретения 20 1, Устройство для умножения произвольных эгементов полей Галуа GF(P") по авт. св.1Ж900281, отл и чаю щеес я тем, -;то, с целью расширения функциональных возм>О»<ностей путем формирования мульти25 плика ивнь х групп задаваемых и производных полей Галуа GF(P ), в него введены блок микропрограммного управления и блок 4opI ирования полиномов и элементов >«I уl>: ьтипл и.<а > >и вн ых груп и, выходы г>ервои 30 третье ..-рупп которого соединены соответ:.:. венно с входами пе>двых групп модульных блоK09 умножения, входами первой группы перв:=го блока формирования частичных произведений, входами второй групгы пер35 вого:.::-.дульногo блока умноже>-,.>ия I входами второй гр /ппы кажДого . блока формирования частичнь.х произведений, и>-,формаци>оннь1е входы первой — третьей групг блока формирования полиномов "Oe40 диненof соответственно с выходами первой— третьей групп блока микропрсграммного управления, первый —:-етвертый выходы которого соединены соответственно с одчоименными входами выбора режима работы 45- блока формирования полиномов и элементов мультипликативных групп, информационные входы четвертой группы которого соединены соответственно с выходами f3iloI 50 блока микропрограммного управления — соответственно с тактовым входом и управляющим входом блока формирования полиномов и элементеl:óëüòèIIлиKативнь>х ip>>oп, уп равл яюгций выход которого соеди55 нен с входом блока микропрограммного управления. 2. Устройство по и. 1, о т л и ч а ю щ е ес я тем, !To блок формирования oo>!I>IHot408 и элементов мультипликативных гр.>пп содержи; четыре коммутатора, два элгмента 1709297 Таблица программ работы устройства для умножения произвольных элементов расширенных полей Галуа 5 6 7 8 9 жим аботы стр-ва 5. 6 7 Выход 1-го разряда 0 0 Выход 2" го разряда 1 0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 Выход 3-го разряда 0 1 Выход 4-го разряда 0 0 П р и м е ч а н и е. Режимы работы устройства: программа 1 - умножение произвольных элементов А(х) и Ъ (х) полей GF (P" ) при A(x) = const, В(х) = vac; программа 2 " умножение произвольных элементов А(х) и В(х) полей GF(P ) при В(х) = const, А(х) = vac; программа 3 - умножение произвольных элементов А(х) и В(х) полей GF. (Р") при А(х) = час; В(х) = vac; программа 4 - формирование элементов полей Галуа GF(Р") при использовании результатов умножения, элементов С(х) и качестве элементов В(х) и неизменяющемся элементе; программа 5 - формирование элементов полей Галуа GF(P ) при использовании элементов С(х) в качестве элементов В(х) и изменяющихся A(x), А(х) = vac; программа 6 - формирование неинверсно-изоморфньгх полей Галуа и умножение А(х) и В(х) при А(х) = const, В(х) = vac; программа 7 - формирование неинверсно-изоморфных полей Галуа и умноже1 ИЛИ, пять элементов И, четыре регистра хранения коэффициентов полиномов и элеьи.нт НЕ, причем информационные входы рервой — третьей групп блока соединены оответственно с информационными входа- 5 ми первого — третьего регистров хранения коэффициентов полиномов, выходы кото-. рых соединены соответственно с информационными входами первого — третьего коммутаторов, информационные входы чет- 10 вертай группы блока соединены с входами первого элемента ИЛИ и информационными входами четвертого регистра хранения коэффициентов полиномов, вход разрешения записи которого соединен с выходом 15 первого элемента ИЛИ и управляющим выходом блока, выходы первой — третьей групп которого соединены соответственно с выходами первого и второго коммутаторов и второго элемента ИЛИ, входы первой и второй 20 rpynп которого соединены соответственно с выходами третьего и четвертого коммутаторов, управляющий вход блока соединен с управляющими входами первого и второго коммутаторов и первыми входами первого и второго элементов И, выходы которых соединены с управляющими входами третьего и четвертого коммутаторов, первый — третий входы выбора режима работы блока — соответственно с первыми входами третьего— пятого элементов И, выходы которых соединены с входами разрешения записи соответственно первого — третьего регистров хранения коэффициентов полиномов, а вторые входы — с тактовым входом блока, четвертый вход выбора ре кима работы которого соединен с вторым входом второго элемента И и через элемент НЕ с вторым входом первого элемента И, информационные входы четвертого коммутатора соединены с выходами четвертого регистра хранения коэффициентов полиномов. 1709297 2 ние А(х) иВ(х) при А(х) = vac, В(х) = const; пограмма 8формирование иеинверсно-изоморфных полей Галуа и умножение А(х) и B(x) при А(х) = vac, В(х) = vac; программа 9 - формирование неинверсно-изоморфных полей Галуа и формирование элементов при А(х) = const, B(x) С(х), программа 10 — формирование неинверсно-изоморфных полей Галуа и формирование элементов при A(x) = vac, В(х) С(х). 1709297 4" 4 т к-1 Ал-1 фиг.2 1709297 1709297 Составитель И.Сныткин Техред М,Моргентал Корректор С.Шевкун Редактор Л.Пчолинская Производственно-издательский комбинат "Патент"; г. Ужгород, ул.Гагарина. 101 Заказ 425 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035. Москва, Ж-35, Раушская наб., 4/5
