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

Союз СоветскихСоциал истнчесинаРеспублни ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и 90028г(5 )М. Кд. С 06 Г 7/49еввудаЮееххы квинтет СИР хв девает хзабретемнй н етерытнВ(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПРОИЗВОЛЬНЫХ ЭЛЕМЕНТОВ ПОЛЕЙ ГАЛУА СГ(р") Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных устройствах и микропроцессорах для умножения элементов расширения полей СГ(Р"), а также в системах ф кодирования, ус,тройствах обнаружения и исправления ошибок кодов, построение которых базируется на теории полей СГ(Р").Известны умножители элементов поля СГ(2 ), построение которых основывается на специальных уравнениях полей СГ(2 ) и базируется яа разделении элементов поля СГ(21") нри помощи генератора полиномов СГ(2 ) (.13 .Однако данные умножители представляют значительную сложность и неприспособленность к большим полям СГ(2 ) и не позволяют умножать произвольныеЮ элементы расширенных полей при любом простом Р = 2, т,е. полейРи)где и = 1,2,3 Наиболее близким по технической сущности к предлагаемому является устройство для умножения произвольных элементов полей Галуа СГ(Р), при Р = 2, которое обеспечивает систематический комбинационнологический подход к умножению произвольных элементов Г(х) иР(х) (Г(х)=1, ф, Р(х)=Р ф1=0,1 ш) поля СГ(2 ффф) с первообраэным полиномом 9(х)=9 х (1==0,1В)Это устройство содержит (в) упорядоченных блоков умножения. На первый иэ них поступают сигналы элемента Г(х) поля, а на остальные подаются выходные сигналы предшествующих. В каждом блоке умножения вход умножается на Х для создания результирующего сигнала с модулем 9(х). На вход 1-го формирователя частичных произведений соединенного с (1-1)-,1 блоком умножения, поступают сигналы х Г(х),ф 1-й формирователь частичных произве 900281едакт ппова Ревет аказ 12 ВНИИП 3/66 Госу по 1130л 35 Моск Раущская наб. д. 4/52. уБ адтштФилиал ППП "Патент , г. Ужгород, ул. Проектная, 4 арственн зобретени ва Жль В, Березкин Надь Коррект Подписи та СССР900283дений осуществляет логическое умножение на Р и выдает частичное произведение Р)". Выходные сигналы а формирователей частичных произведений поступают на входы ш суммирующих блоков для образования сигналов, соответствующих произведению Р)( Г по модулю 9(х). Каждый суммирующий блокоперирует с соответствующими компонентами частичных произведений логи- щческих схем 121.Недостатком известного устройстваявляется то, что оно не позволяетумножить произвольные элементы расширенных полей СР(Р) при произвольньсхпростом Р 2 и и, а также любых перво- .образных неприводимых над СГ(Р) полиномов степени и.Цель изобретения - расширениефункциональных возможностей за счетобеспечения умножения произвольиьасэлементов А(х) и В(х) расширенныхполей Галуа СР(Р ) при произвольныхпростых Рт 2 ои и различных производящих полиномах а(х), где а(х)=Ь.) х 4, д0,1,е 1 А(х)щА х(, 0(х) Ве хе,1=0,1 аа 1 АА, В , ас:0,1, ,Р; Р"пРостое число,36Эта цель достигается тем, что в устройстве для умножения произвольных элементов полей Галуа СГ(р), содержащем и модульных блоков умножения, и блоков формирования частичных произведений и и блоков суммирования, причем входы первых групп модульных блоков умножения соединены со входами производящего полинома устройства, входы второй группы первого модульного блока умножения соединены со входами первой группы первого блока формирования частичных произведений и со входами первой группы нроизвольных элементов полей Галуа СР(р") устройства, выходы каждого ) - го ( 3 - 1 , и) модульного блока умножения соединены со входами первой группы Ц+1)-го блока формирования частичных произведений, входы второй группы каждого блока формиро- фо вания частичных произведений соединены с соответствующими входами второй группы произвольных элементов полей Галуа 61(р ) устройства, входы каждого к-го (к=ап) блока суммирования соединены с к-ми выходами блоков Формирования частичных произведений выходы блоков суммирования яв) 4ляются выходами устройства, каждый вход производящего полинома и каждый вход первой и второй групп произвольных элементов полей Галуа 61(р") устройства содержит (р) шин, каждый вход и выход каждого модульного блока умножения, блока формирования частичных произведений и блока суммирования содержит (р) шин, каждый модульный блок умножения является блоком умножения по модулю а (х), Р, где а(х) 1 а хе 1 10,1еаА щ 0,1р, каждый блок формирования частичных произведений содержит и узлов формирования частичных произведений, выполненных в виде матриц элементов И, первые входы которых соединены с шинами соответствующего входа первой группы узла формирования частичных произведений, а вторые входы соединены с шинами входа второй группы узла формирования частичных произведений, каждый блок суммирования является сумматором по модулю рНа фиг, 1 представлена Функциональ - ная схема устройства; на Фиг. 2 - схема модульного блока умножения; на фиг. 3 - схема блока формирования частичных произведений; на фиг. 4- схема модульного блока умножения по модулю а(х) Р для поля СР(3) и а(х) х-а х-а х -ах" -ас; на фиг. 5- то же, по модулю а(х)( Р для поля СР(Зф) и а(х)=х;а х"-а х-а хЗ-а 1 х 1-а; на фиг. 6 - то же по модуА лю а(х) Р для поля СЕ(5 ) и а(х)еах-ахф-ах"-а , на фиг. 7 - то же по модулю а(х) Р для поля СГ(ЗЗ) и а(х)х -х; на Фиг, 8 представлена схема блока суммирования по модулю три для поля СГ(3 ). Устройство для умножения произвольных элементов расширенных полей Галуа СГ(Р") (фиг. 1) содержит модульные блоки 1-3 умножения по модулю 1(х) Р, блоки 4-б формирования частичных произведений, блоки 7-9 суммирования по модулю Р, входы 10 производящего полинома а(х), входы 11 и 2 произвольных элементов А(х) и В(х), выходы 13, на шины которых поступают коэффициенты полннома элемента С(х) =А(х)В (х) (п)о(Ы а (х) Р) .Модульный блок 1, 2 или 3 умножения по модулю а(х) Р (фиг.2) содержитгруппы 14-1 б логических узлов 7-19, элементы И 20, блокй 21-235 900-суммировапия по модулю Р, при этомкаждая группа 14, 15 пли 16 содержиг(р) логических узлов 17-19 каждый из которых содержит а с элементов И 20.5Узел формирования частичных произведений (фиг. 3) содержит матрицы 24-26 элементов И 27,Модульный блок 1, 2 нли 3 умножения по модулю а(х)4 Р для поля СГ(3 ) 10и а(х)=х"-а х -ах"-ах -а(фиг. 4)содержит группы 28-31 логическихузлов элементов И, блоки 32-35 суммирования по модулю три.Модульный блок 1, 2 или 3 умножения по модулю а(х) Р для поляСГ (35 ) и а (х) =х-а х" -а х 5 -а х -а 1х-а (фиг. 5) содержит группы 36-40логических узлов элементов И и блоки 41-45 суммирования по модулю три. 20Модульный блок 1, 2 или 3 умножения по модулю а(х)4 Р для поляСГ (5 ) и а(х)=х-а х"-а 1 х -а(фиг. 6)содержит группы 46-48 логическихузлов элементов И, а также блоки 49- д 551 суммирования по модулю пять.Мод (льный блок 1, 2 или 3 умножения по модулю а(х) Р для поляСГ(3 ) и а(х)=х-х(фиг.7) содер -жит группу 52 элементов И 53-56,группу 57 элементов И 58 и 59 иблоки 60 и 6 суммирования по модулю три.Блок 7, 8 или 9 суммирования помодулю три для поля СГ(3 ) (фиг.8)содержит элементы И 62-64, элементыИЛИ 65-68, элементы запрета 69 и 70.Из теорииполей СГ(Р ) известно,что если Э - первообразный элементполя СГ(Р ), то все элементы поля 40СГ(Р) являются степенями 9, т.е.СГ(Р )= 9 О 9 68;неприводимым над СГ(Р) полиномом степени и и а (6) =О. 30 Например, коэффициенты полинома А вычисляются следующим обпазом. ЦИ 3 ВХ Ф Ю Ы А =Аа а=2 А 1 - -А а 1+Ап =2 А=А а +Аф О. Коэффициенты полинома А С выи числяются следующим образом: А =А, а =4 р 1(пюс 3), А 1 =Аа+А.5 И 2 С0 - гг а 1 =3=0(пюс 3), А =Ага+А =2,Таким образом, любой А"-й элемент .поля СГ(Р") может быть найден путем возведения Х=8 в степень 1-1 и приведения Л =Х по пюсда(х) Р, т.е.50 двойному модулю. В случае, если известен А 4 " -й элемент поля, то для нахождения А 4-го элемента достаточно А -й элемент умножить на х и55 результат привести по пюсса(х)Р, т. е. А:Ах(пюсйа(х)4 Р).Элементы поля СГ(3 ) вычислены согласно формулам, приведенным выше. 81 ЬС Г (35 ), Р=3, п=З, а (х) =х -х- Й,ао=2, а=1, а=О.А 1 А"с =х+ А"9 =х +2 х+1А =х Ан =х+х А =2 х +2 х+2Аз =х" А =хс+х+2 А =2 х +х+1А" =х+2 А 4.с =х+2 А =х +1А =х" +2 х А" =2 А 5 =2 х+2А =2 х +х+2 А =2 х . А =2 х +2 хА =х+х+ А 6 =2 х 4 А 5 =2 х +2 х+А =х "+2 х+2 А 1 =2 х+1 А 2 х +1Аф =2 х +2 Аф =2 х+х6Например, 6-Й элемент А вычисляется путем умножения элемента АС нах и приведения результата по двойномумодулю а(х)=х -хР=З АС х(х"+ 2 х)к х=х 1.2 х н 2 х . к+2 (пюд с а (х) Р ) .Таким образом, для отыскания всехэлементов (полиномов)поля СГ(Р ")необходимо рекуррентно умножать ра- .нее вычисленный предшествующий элемен; (полином) на х и результат приводить по пюдда(х) Р. Эта операциятождественна сдвигу влево полпномапредыдущего элемента (т.е, увеличение на единицу степени х каждого членаполинома) и, если наибольшая степень прих равна п, то из результата необходимо вычитать полином а(х) столько раэ,чтобы результат вычитания не имелстепени х равной и, а затем результат привести по модулю Р.Существует более упрощенное рекуррентное правило вычисления элементовполей СГ(Р ). Рассмотрим некоторыепримеры на поле СГ(3 ).зЧтобы получить значения коэффициентов при степенях хх"хэлемента,А(т.е. А , А , А ) достаточнопровести следующие операции с коэффициентами А, , А , А элемента Аьи аа 1 а 1 первообразного полиномаа(х), умножая А иа ао и приводя реСзультат по модулю Р=З, получаемА = (А а =4 я (пюс 3), умножая Ана а 1 и прибавляя к результату Ас)получаем (после приведения по модулюР=З) А 1 =1(А. а, -А =4:1(пюдЗ)умножая А на а и прибавляя к результату А 4 (после приведения по моСдулю Р=З) получаем А =1 (Аа 1 А 1 =1),6г. 1Таким образом, А =х +к+1.9002 В состф Выходы входы 1 20 О1 0011 00 00 0 1 2 0 О1 О 1 1 0 0 О О 1 1 1 0 3 0 О О1 1 4 0 0 0 0 1 1 0 3 4 5 6 7 1 1 1 01 Таким образом, данное рекуррентное правило сводится к тому, что ко" зффициенты каждого последующего поли- . нома-элемента А"+поля 6 Г(Р ") вычисляются с использованием коэффициен тов предыдущего полинома-элемента А и первообразного, полинома а(х) по правилуА -А а (падр),А А,. а + ф А 1 1 (пюдр), вДанное правило лежит в основе построения и функционирования модульного блока 1, 2 или 3 умножения по модулю а(х) Р. Данный блок осуществляет умножение полинома-элемента 1 А -го на х н приведение результата Кпо аодда(х) Р, тем самым осуществляется получение элемента А"+" -го. Действительно, группы 14-16 логических узлов 17-9, каждый иэ которых сос тоит иэ аэлементов И 2 О, осущек ствляют умножение коэффициента А полииома А -го на коэффициентыкае, а,а, путем размножения каждого входа входной шины, отобра жающей коэффициент А, в а раз в логических узлах 17"9 каждой группы 14-16. Если А2, то сигнал сукществует на первых двух входах ши" ны А, если А 1 фРто сигнал 1 И на Р"1 входах шины Аи т,д, ЕслииФа) 2, то сигнал существует иа первых двух входах шины, отображающей коэффициент а и т.д.Таким образом,. число активных (на которых существуют сигналы) выходов каждой группы 14-16 равно произведению активных входов шин Ами а. Так как любой коэффициент А не превышает Р"1, а коэффициечт а о не превышает Р"1, то число всех выходов кэждой группы в общем случае не превышает 1,4(Р).Блоки 21-23 суммирования по модулю Р (фиг. 2) представляют дешиф 81 8раторы, так как осуществляют операцию преобразования сигналов на своих входах в сигналы на своих выходах. Для блока 21 число входов определяется лишь числом выходов группы 4, для блока 22 число входов дополняется числом входов шины А,,для блока 23 число входов дополняется числом входов шины А" . Числовыходов блоков 21-23 равно Р. Та:ким образом, блоки 21-23 дополнительно осуществляют операцию сложениярезультат умножениякК,А ф 1 с Афункциональные схемы модульныхблоков 1, 2 или 3 умножения по модулю а(х)1 Р для различных конкретныхполей 6 Г(3")са(х)х"-а х -,а хф-а х"-а,6 Г(Зф)са(х)ах-а х"-а 4 х 1-а хф-а х 13 а л-а; 6 Г(5)са(х)щхд "ах-ах" -а,представлены на фиг. 4-6, Эти функциональные схемы отображают конкретное построение для конкретных полей6 Г функциональной схемы общего случая, представленной на фиг. 2. Для поля 6 Г(3) с а(х)=х-х(фиг. 7) функциональная схема модульного блока 1, 2 или 3 умножения по модулю а(х)хф-х, Р=З. Так как а О, то группа элементов И, осуществляющая умножение А на а =0 отсутствует, отсутствует из-за ненадобности и третий блок суммирования по модулю Р=З. Так как а 2, то группа 52 содержит четыре элемента И 53-56, а группа 57 - два элемента И 58 и 59, Блоки суммирования 7-9 по модулю Р для любых полей 6 Г(Р") представляют дешифраторы, Схема блока суммирования по модулю Р3 для поля 6 Г(3) (фиг. 8) реализует приведение по модулю три сигналов на своихчетырех входах в сигналы на своих двух выходах (см, таблицу),Устройство для умножения произволь ных элементов полей Галуа СГ(Р )содержащее и модульных блоков умножения, и блоков формирования частичных произведений и и блоков суммирования, причем входы первых групп модульных блоков умножения соединенысо входами производящего полинома устройства, входы второй группы первого модульного блока умножения соединены со. входами первой группы первого блока формирования частичных произведений и со входами первой группы произвольных элементов полей Галуа СГ(Р) устройства, выходы каждого 1-го (1=и) модульного блока умножения соединены со входами первой группы (1+1)-го блока Формирования частичных произведений, входы второй группы каждого блока формирования частичных произведений соединены с соответствующими входами второй группы произвольных элементов полей Галуа СГ(р") устройства, входы каждого к-го (1=1 и) блока суммирования соединены с к-ми выходами блоков формирования частичных произведений, выходы блоков суммирования являются выходами устройства, о т - л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения функциональных возможностей устройства за счет обеспечения умножения произвольных элементон полей Галуа СГ(р") при произвольных прос 9 9 ОО 28Рассмотрим процедуру умножения двух любых элементов А х и В(х)поля СГ(Р ), Умножение двух полиномэлементов А(х) и В(х) можно осуществить путем суммирования по пюд Р частичных произведений полинома А(х) на слагаемые полинома В(х), т. е. произведений вида А"(х)=А(х)В х ), приведенных по пюдда(х) Р Умножение А(х) на х и приведение 10 результата по пюдда(х) Р осуществлено при помощи одного модульного блока 1 умножения по модулю а(х) Р, а умножение А(х) на х (равнозначно умножению А(х) на х) и приведение 15 результата по пюдда(х)1 Р, осущестнляется при помощи цепочки, состоявшей иэ модульных блоков 2 и 3 умноже. ния по модулю а(х) Р, выходы каждого предыдущего при этом соединяются 20 со входами каждого последующего,Умножение произведения А(х)х", приведенного по пюдса на коэффициент В можно осуществить при помощи блоков 4-6 Формирования частичных 25 проиэнедений, функциональная схема которых представлена на фиг. 3. Данная операция осуществляется путем размножения каждого входа шины А( 1 В 1 раэ 1-й матрицей 24-26 элементов И 2750 К каждой 1-й матрице 24-26 элементов И 27 подведено Ршин, отобра - жающих коэффициент А) и Ршин, отображающих коэффициент В при этом каждая 1-я матрица 24-26 элемен 35 тов И 27 имеет (Р) групп, по (Р) выходов, отображающих произведение коэффициентов А 1 ф В. Каждый 1-й блок 4-6 имеет и матриц 24-26 элементов И 27 и тем самым - и вы 40 ходов по (Р) шин в каждом выходе.Таким образом, выходные шины каждого 1-го блока 4-6 отображают частичное произведение А(х)(В х).Суммирование по пюд р частичных произведений осуществляется в блоках 7-9 суммирования по модулю Р. При этом ко входам блока 7 подведены первые выходы блоков 4-6, ко входам блока 8 - вторые выходы блоков 4-6,50 а ко входам блока 9 и выходы блоков 4-6. Первые выходы блоков 4-6 отображают коэффициенты частичных произведений при степени х, вторые выход 11 блоков 4-6 - коэффициенты55 частичных произведений при степених и т.д.Таким образом, блок 7 осуществляетсуммирование (привсдение) по мо 1 10дулю Р коэффициентов при хф нсех частичных произведений, блок 8 осуществляет суммирование по модулю Р коэффициентов при х" всех частичных произведений, а блок 9 - коэффициентов при х" " всех частичных произведений.Блоки 7-9 могут быть выполнены в виде дешифраторов. Выходы блоков 7-9 отображают коэффициенты соответственно Со, С Сь 1 полинома, представляющего собой результат умножения по пюсда(х) Р полиномов-элементов А(х) и В(х) поля СГ(Р").Предлагаемое устройство обеспечивает умножение произвольных элементов А(х) и В(х) полей СГ(Р") при любых значениях простого числа Р, .степени и и первообразных неприврдимых полиномов а(х). Формула изобретения11 900281 12тых р 2 и и и различных производящих ды которых соединены с шинами соотполиномах, каждый вход производящеДР ветствующего входа первой группыполинома и каждый вход первой и вто- узла формирования частичных произверой групп произвольных элементов по- дений, а вторые входы соединены слей Галуа ОГ(р) устройства содержит ф шинами входа второй группы узла фор(р"1) шин, каждый вход и выход каждого мнрования частичных произведений, каж -модульного блока умножения, блока дый блок суммирования является сумформирования частичных произведений матором по модулю Р,и блока суммирования содержит (р)вин, каждый модульный блок умножения 10 Источники информации,является блоком умножения по модулю принятые во внимание при экспертизеа(х),р, где а(х) а хф; 1 0,1 1. 8 агйее Т. С, апд 5 сЬпе 1 дег О. 2.п; ащ 0,1р, каждый блок СоерийаФ 1 оп и 1 йп Г 1 пойе Г 1 е дэ.формирования частичным произведений 1 ц 1 огвай 1 оп аль Сопйго 1, 61, 1963,содержит и узлов формирования час- и рр. 79-98.тичиых произведений, выполненных в 2. Патент США В 4037093,виде матриц элементов И, первые вхо- кл, 235-164, 1977 (прототип).