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

(53)5 О 06 Е 7 ОБР Е ЕЛЬСТВУ блоки ки 4-6 дений,1-3 ум форм ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ПИСАНИЕ К АВТОРСКОМУ С(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПРОИЗВОЛЬНЫХ ЭЛЕМЕНТОВ ПОЛЕЙ ГАЛУАОР(Р")(57) Изобретение относится к прикладнойвычислительной технике и может быть использованов специализированных вычислительных устройствах и микропроцессорах Изобретение относится к прикладной вычислительной технике и может быть использовано в специализированных вычислительныхустройствах и микропроцессорах для умножения. формирования, исследования свойств элементов расширенных полей О Е(Р"), а также в системах кодирования, обнаружения и исправления ошибок кодов, построение которых базируется на теории полей Галуа ОГ(Р"),Цель изобретения - расширение функциональных возможностей за счет формирования мультипликативных групп задаваемых и производных полей Галуа.На фиг, 1 - 4 представлены функциональные схемы устройства; блока умножения и блоков формирования.Устройство содержит модульныеножения по модулю(а(х), Р), бло ирования частичных произве Ы, 1709297 А 2 для умножения, формирования, исследования свойств элементов расширенных полей ОЕ(Р), а также в системах кодирования, обнаружения и исправления ошибок кодов, построение которых базируется на теории полей Галуа ОГ(Р") и является усовершенствованием основного изобретения по авт. св, СССР М 900281. Целью изобретения является расширение функциональных возможностей за счет формирования мультипликативных групп задаваемых и производ. ных полей Галуа ОЕ(Р"), которая достигается введением блока микропрограммного управления и блока формирования компонентов и элементов мультипликативных групп. 1 з.п.ф 4 ил 1 табл. блоки 7 - 9 суммирования по модула Р, блок 10 формирования полиномов и элементов мультипликативных групп и блок 11 микропрограммного управления 11.Функциональная схема блока умножения по модулю (а(х), Р), представленная на фиг. 2, содержит группы 12-14 по (Р - 1) логических узлов по, а элементов И в каждом узле, субблоки 15 - 17 суммирования по модулю Р, логические узлы 18-20 группы 12, элементов И, входные шины коэффициентов полиномов а(х), А (х) и выходные шиныккоэффициентов полиномов А (х).к+1Функциональная схема блока формирования частичных произведений, представленная на фиг. 3, содержит группы 21 - 23 элементов И по (Р) линеек по (Р) элементов И в каждой линейке; входные шины коэффициентов полинома элементов А (х),к входную шину коэффициентов полиномаэлемента В(х), вьходные шины коэффициентов полинома, представляющего собой частичное произведение (А (х), В),кФункциональная схема блока 10 формирования полиномов и элементов мультипликативных групп, представленная на фиг.4, содержит четыре коммутатора 24 - 27, дваэлемента ИЛИ 28 и 29, пять элементов ИЗО - 34, элемент НЕ 35 и четыре регистрахранения коэффициентов полиномов Зб, 10Блок 11, также представленный на фиг.4, содержит триггер 40, циклический регистр 41, счетчик 42, элемент И 43, генератор 44 тактовых импульсов и схему 45 вводаданных (клавиатуру) 15Сущность алгоритма работы устройствазаключается в следующем.Из теории полей Галуа 6 Г(Р") известно,что если 0 - первообразный элемент поляОГ(Р"), то все элементы поля ОГ(Р") являются степенями О, т.е.Рп) (О, д, О 1 г 7 -2) (п 10 бб а(х) РПри этом а(х) является первообразнымнеприводимым над СГ(Р ) полиномом степени и, а(0) =О, Таким образом, любой А-й 25элемент поля ОГ(Рп) может быть найден путем возведения х = О в степень (1-1) и приведения А = х по гподб(а,(х), Р), Еслиизвестен А -й элемент поля, то для нахожЬ 1.дения А-го элемента достаточно А -й эле1мент поля умножить на х и результатпривести погпобб(а(х), Р), т,е, А = А х гпобба(х)Р, Как видно эта операция тождественнасдвигу влево полинома предыдущего элемента (т,е. увеличение на единицу степени 35х каждого члена полинома и,если наибольшая степень при х равна и, из результатанеобходимо вычесть полином а(х) столькораз, чтобы результат вычитания не имел степени х равной и, а затем результат привести 40по модулю). Из данной методики вытекаетдругое более упрощенное рекуррентноеправило вьчисления элементов полейОГ(Р"), Это рекурентное правило сводится кследующему: коэффициенты каждого последующего полинома - элемента Аполявычисляются с использованием коэффициентов предыдущего полинома - элемента Аки первообразного полинома а(х) по правилуАК 1 АК - 1 а (глоб Р)50, А - 1=А, - 1 а+ А - 1(проб Р),Данное правило лежит В основе построения и функционирования блока умноженияпо модулю (а(х), Р), представленного на 55фиг.2. Данный блок осуществляет умножение полинома - элемента А -го на х и прикведение результата по гпобб (а(х), Р), аследовательно, получение элемента А.го.Действительно, группы 12-14 ло;.ических узлов, каждый из которых состоит из а) элементов 4, Осуществляет умножение коэффициен.а А 1 полинома А-го соответстквенно на коэффициенты ап, а 1 аппУтем размножен я каждого входа Входной шины, О;Обоажа 1 ОЩЕЙ коэффиЦиент Ап - 1 В д Разкв логических узлах каждой группы 12-14кэлементов И, Если Ап - 1 = - 1, тс сигнал существует на Р - 1 входах шины А," - 1 и т.д, Если а = 2, то сигнал существует на первых двух входах шин, отображающей коэффициент а 1 и т,д. Таким образом, число активных (на которь 1 х существуют сигналы) выходов каждой группы элементов И равно произведени:О активных входов шин А, - , и а. Так как любой коэффициент а не превышает Р - 1, а коэффициент А не превышает Р - 1,кто число всех выходов каждой руппы в общем случае не превышает(Р - 1), Суб 2 блоки 15-",7 суммирования по модулю Р (фиг. 2) представляют по сути дела дешифраторь, так как осуществля,от операцию поеобразования сигналов на свои ВХОдах В сигналы на своих выходах, Для субблока 15 число входов определяется лишь числом выХОдов групп элементов И, для субблока ЧИСЛО ВХОДОВ ДОПОЛНЯЕТСЯ ЧИСЛОМ ВХОДОВкдинь, А для субблока 17 число входов дополняется числом водов шины Ап - 2, 1 искло Выходов субблоов 15-17 равно Р - 1. ;а.им Образом, субблОи 15 и 10 ДОИОлни:ельно Осуществляют операцию сложения результата умножениякАп - 1 а с А - 1. Режимы раооты устройства.1. Умножение произвольных элементов А(х) и В(х) полей 5 Г(Р"),а) гри формировании элемента А(х) и изменяюшемся элемене 3(х);б) при фиксированном элементе Р(х) и изменяющемся А(х),в) при изменяющихся элементах А(х) и Р(х)2, Формирование элементов полей Галуа С Г(Р).а) при использовании результатов умножения, элементов С,х), в качестве элементсв В(х, и изменя:ощемся элементе А(х);б) при использования элементов С(х) в качестве элементов Б(х) и изменяющемся элементе А(х).3, Формирование неинверсно-изоморфных полей ОГ(Р ), т,е. изменение первообразных неприВОдимых полиномОВ а(х) ВО всех указанных Выше режимах.и разрядов, т.е. на выходах регистра 37 окажутся коэффициенты следующего полинома В(х). После того, как произойдет сдвиг на и разрядов, т,е, генератор 44 выдает п тактовых импульсов, счетчик 42 выдает импульс, который приводит триггер 40 в единичное состояние, производит сдвиг программы в регистре 41 и сбрасывает счетчик 42 нулевое состояние. Нулевой потенциал инверс ного выхода триггера 40 закрывает элементИ 43, прекращая поступление тактовых импульсов для сдвига коэффициентов полиномов, Единичный импульс с прямого выхода триггера 40, открывает коммутаторы 25-27, В результате на входы первых групп блоков 1 - 3 умножения по модулю а(х), поступают с выхода коммутатора 27 коэффициенты первообразного неприводимого полинома а(х), с коммутатора 25 - коэффициенты полинома А(х), а по третьей выходной шине - коэффициенты полинома В(х). После этого происходит умножение элементов А(х) и В(х), Умножение двух полиномов элементов А(х) и В(х) можно осуществить путем суммирования по щоб Р частичных произведений полинома А(х) на слагаемые полиномы В(х), т.е.произведение вида А(х) = А(х). В(х), приведенных по гпобб (а(х), Р). Умножение А(х) на Х и приведение результата по п 1 обб (а(х), Р) осуществляется посредством одного рассмотренного блока умножения по модулю (а(х), Р), а умножение А(х) на х (равнозначно умножению А (х) на Х) и приведение реь 1зультата по модулю глобб (а(х), Р) осуществляется посредством цепочки, состоящей из 1 блоков умножения по модулю (а(х), Р), выходы каждого предыдущего при этом соединяются с входами каждого последующего из блоков, Умножение произведения А(х) Х приведенного по еобб (а(х), Р) на коэффициент В можно осуществить посредством блоков 4.-6, функциональная схема которых представлена на фиг, 3, Данная операция осуществляется путем размножения каждого входа шины А 1 - 1 и В, посредством )-й группы элементов И. К каждой )-й группе элементов И подведено (Р - 1) входов. отображающих коэффициент А и (Р - 1) входов, отображающих коэффициент Вь при этом каждая -я группа элементов И имеет (Р - 1) групп по (Р - 1) выходов, отображающих произведение коэффициентов А Вь каждый 1-й узел элементов И имеет и групп элементов И и, следовательно и шин по (Р - 1) выходов в каждой шине. Таким образом, выходные шины каждого -го узла элементов И, к которому подведены входные шины, отображающие В полинома В(х) и входные Выбор режимов работы устройства происходит автоматически и определяется программой, записанной в циклическом регистре 41 хранения программы.(см, таблицу). 5Для работы устройства в различных режимах блок 10 должен выдать:1) по первому групповому выходу - коэффициенты первообразного неприводимого полинома а(х); 12) по второму групповому выходу - коэффициенты полинома элемента А(х);3) по третьему групповому выходу - коэффициенты.полинома элемента В(х) для режима умножения или результата умножения - 15 элементы С(х) для режима формирования элементов поля.Блок 10,формирования полиномов и элементов мультипликативных групп совместно с блоком 11 микропрограммного уп равления работает следующим образом.На клавиатуре 45 оператором набирается программа работы устройства, коэффициенты первообразного неприводимого полинома а(х), коэффициенты полинома -25 элемента А(х) и коэффициенты полинома - элемента В(х). Программа работы устройства записывается в циклической регистр 41 хранения программы и состоит из набора единиц и нулей (см. таблицу, 30Коэффициенты первообразного неприводимого полинома а(х). коэффициенты полинома - элемента А(х), коэффициенты полинома - элемента В(х) записываются в соответствующие регистры 37 - 39 хранения 35 коэффициентов полиномов, причем эта запись происходит одновременно во все ячейки регистров 37-39. а считывание происходит с последних п ячеек этих регистров, 40После этого с выхода клавиатуры 45 выдается импульс "Начало работы", который поступает на вход генератора 44 тактовых импульсов, который начинает генерировать тактовую последовательность импульсов, 45 поступающую на вход счетчика 42 через элемент И 43, который открыт единичным потенциалом, поступающим на его вход с инверсного выхода триггера 40, находящегося в нулевом состоянии. Тактовые импуль сы, поступающие с выхода элемента И 43 (рассматривается режим работы устройства. описанный под номером 1 а), поступают на входы элементов И 32 - 34, в соответствии с режимом работы открытым оказывается 55 лишь один элемент И 32 и тактовые импульсы, проходя через этот элемент, поступают на тактовый вход регистра 37 хранения коэффициентов полиномов В(х) и циклически сдвигают записанную в нем информацию нашины, отображающие произведение А(х) = = А(х) х (глог 1 с 1 (а(х), Р отображают частичное произведение А(х) (В х),Суммирование по гпоо Р частичных произведений осуществляется в блоках 7-9 суммирования по модулю 3. При этом к входам блока 7 подведены первые выходные шины блоков 4-6, к входам блока 8 - вторые выходные шины блоков 4-6, а к входам блока 9 - (Р - 1)-е вьходнье шины блоков 4-6, Первые выходные шины блоков 4 - 6 отображают коэффициенты частичных произведений при степени Х, вторые выходные шины блоков 4-6 - коэффициенты частичных произведений при степени Х и т,д, Таким обра 1,зом, блок 7 осуществляет суммирование (приведение) по модулю Р коэффициентов при Х всех частичных произведений, блок 8 - суммирование по модулю Р коэффициентов при Х всех частичных произведений, а1блок 9 - коэффициентов при Х" всех частичных произведений,Блоки 7-9 тоже являются дешифраторами, функциональное построение которых аналогично субблокам суммирования по модулю Р, Выходные шины (по Р - 1) выходов блоков 7-9 отображают коэффициенть полинома С(х), представляющего собой результат умножения по глоос 1 (а(х), Р), полиномоа элементов А(х) и В(х) поля ОЕ(Р"), Этот оезультат по выходным шинам устройства, поступает на выходы блока 10 и далее записывается в регистре 36 хранения коэффициентов полиномов С(х) и поступает на входы элемента ИЛИ 29, на выходе которого образуется единичный потенциал, который является разрешающим импульсом для записи результата в регистре 36 и переводит триггер 40 в нулевое состояние.В результате оказыва,отся закрытыми злементь И 30 и 31 и коммутаторы 25 и 27, а элемент И 43 оказывается открытым, и тактовые импульсь в соответствии с режимом работы циклически сдвигают информацию в одном или нескольких регистрах 37 - 39, Одновременно тактовые импульсы подсчитываются счетчиком 42, Как только будет произведено и сдвигов, т,е. на выходах регистров 37-39 окажутся коэффициенты полинома А(х), В(х) или С(х), счетчик 42 выдает импульс, по которому процесс работы блока повторяется, но уже в другом режиме, записанном в оегистре 41 и сдвинутом ранее поступившим импульсом переполнения со счетчика 42,Выбор режима работы устройства определяется состоянием выходов регистра 41, Единичное состояние его выхода говорит о том, что происходит изменение тех коэффициентов полинома А(х), В(х) или непоиводимого полинома а(х), к входу регистра хранения одного из которых 37 или 38 или 39через соответствующие элементы И 32 - 34и:дсоединен этот выход, При реализации5 режима формирования полей ОЕ(Р") регистр 41 должен выдать также единичныйпотенциал, который через открытый элемент И 31 Открывает коммутатор 24 и натретьи выходы блока 10 вместо коэффици 1 О ентов полинома В(х), поступают коэффициенты результата умножения, т.е, устройствоработает в режиме формирования полейСЕ(Р"), Если, кроме того, происходит циклический сдвиг информации в регистре 39 че 15 раз открытый элемент И 34соответствующего выхода регистра 41, тоустройство формирует неинверсно-иэоморфн ые поля СЕ(Рл),Формула изобретения20 1, Устройство для умножения произвольных згементов полей Галуа ОЕ(Р") поавт, св.1 Ж 900281, Отл и ча ю щ ее с я тем,что, с целью расширения функциональныхвозможностей путем формирования мульти 25 пликативнь х групп задаваемых и производны., полей Галуа СЕ(Р ), в него введены блокмикропрограммного управления и блокформирования полиномов и элементовмультипли.а ивных групп, выходы первои30 третьей групп которого соединены соответственно с входами первых групп модульныхблоков умножения, входами первой группыперв=го блока формиоования частичныхпроизведений, входами второй групгы пер 35 вого:-дульного блока умножения и входами второй Группы кажДого .блокаформирования частичных произведений,информационные входы пеовой - третьейгрупг блока формирования полиномоа сое 40 динены соответственно с выходами первой -третьей групп блока микропрсграммногоуправления, первый - етвертый выходы которого соединены соответственно с одчоименными входами выбора режима работы45 блошка формирования полиномов и элементов мультипликатианых групп, информационные входы четвертой группы которогосоединены соответственно с выходами блоков суммирования, пятый и шестой выходы50 блока микропрограммного управления - соответственно с тактовым входом и управляющим входом блока формированияполиномов и элементов :ультипликативныхгрупп, управляюгций выход которого соеди 55 нен с входом блока микропрограммного управления.2. Устройство по и. 1, о т л и ч а ю щ е ес я тем, что блок формирования полиномови элементов мультипликативных групп содержит четыре коммутатора, даа элемента10 1709297 Таблица программ работы устройства для умножения произвольных элементов расширенных полей Галуа10 4 5 6 7 жимаботыстр-в 4 5 Выход 1-го разряда 1 О зряда ыход О Выход 3-го разрядаВыход 4-го разря О Режимы работы устройствольных элементов А(х)А(х) = сопвс, В(х) = чизвольных элементов АВ(х) = сопвс, А(х) = чпроизвольных элементовА(х) = час; В(х) = часэлементов полей Галуататов умножения, элемеВ(х) и неизменяющемсярование элементов полении элементов С(х) в княющихся А(х), .А(х)неинверсно-изоморфньгхА(х) = сопят,неинверсно-и еца программаГалуа и у= час; профных полей час оле В(х омо 6 - формированиножение А(х) и грамма 7 - форГалуа и умножеВ(х) примирование ИЛИ, пять элементов И, четыре регистра хранения коэффициентов полиномов и элемент НЕ, причем информационные входы первой - третьей групп блока соединены соответственно с информационными входа ми первого - третьего регистров хранения коэффициентов полиномов, выходы кото-. рых соединены соответственно с информационными входами первого - третьего коммутаторов, информационные входы чет вертай группы блока соединены с входами первого элемента ИЛИ и информационными входами четвертого регистра хранения коэффициентов полиномов, вход разрешения записи которого соединен с выходом 15 первого элемента ИЛИ и управляющим выходом блока, выходы первой-третьей групп которого соединены соответственно с выходами первого и второго коммутаторов и второго элемента ИЛИ, входы первой и второй 20 групп которого соединены соответственно с выходами третьего и четвертого коммутаторов, управляющий вход блока соединен с управляющими входами первого и второго коммутаторов и первыми входами первого и второго элементов И, выходы которых соединены с управляющими входами третьего и четвертого коммутаторов, первый - третий входы выбора режима работы блока - соответственно с первыми входами третьего - пятого элементов И, выходы которых соединены с входами разрешения записи соответственно первого - третьего регистров хранения коэффициентов полиномов, а вторые входы - с тактовым входом блока, четвертый вход выбора режима работы которого соединен с вторым входом второго элемента И и через элемент НЕ с вторым входом первого элемента И, информационные входы четвертого коммутатора соединены с выходами четвертого регистра хранения коэффициентов полиномов. ва: программа 1 - умножение прои и Ъ(х) полей СГ(Р") при ас; программа 2 - умножение про(х) и В(х) полей СР(Р ) при ас; программа 3 - умножение А(х) и В(х) полей СР(Р") припрограмма 4 - формирование СГ(Р") при использовании резульнтов С(х) и качестве элементов элементе; программа 5 - формий Галуа СР(Р") при использоваачестве элементов В(х) и изме1709297 Юние А(х) и В(х) при А(х) = час, В(х) = сопз; пограмма 8- формирование иеинверсно-изоморфных полей Галуа и умножение А(х) и В(х) при А(х) = час, В(х) = час; программа 9 - формирование неинверсно-изоморфных полей Галуа и формирование элементов при А(х) = сопя, В(х)С(х), программа 10 - формирование неинверсно-изоморфных полей Галуа и формирование элементов при А(х) = час, В(х) С(х).1709297 рректор С.Шевкун Редактор Л.Пчолинская оизводственно-издательский ком Заказ 425 ВНИИПИ Г Составитель И.СныткиТехред М,Моргентал Тираж Подписноеарственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 ат "Патент"; г. Ужгород, ул,Гагарина, 10