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

(50 ОП АНИЕ ИЗОБРЕТЕНИ СТВУ РСКОМУ СВ рных е 11 гз. 19 06 Г СССР979.НИЯ ОПЕРАЕЛЕНИЯ ИПОЛЕ ГАЛУА к вычисличено для ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) 1,онз В,А. апй отпег.1 аг-аггау щц 11 хр 1 ес 1. Гог С1 ЕЕЕ Тгапзас 1 оп оп Сощрп 1ч, 20, В 12, р. 573,Патент США Ф 3805037, к1/02, опублик. 974.Авторское свидетельствоУ 875408, кл. С 06 Р 7/00,(54) УСТРОЙСТВО ДЛЯ ВЫПОЛЙЦИЙ ВОЗВЕДЕНИЯ В СТЕПЕНЬ, ДУМНОЖЕНИЯ ДВУХ ЭЛЕМЕНТОВ ВСР (2 )(57) Изобретение относитсятельной технике и предназн использования в качестве специализированной ячейки для реализации операций одновременного возведения в сте-пень, деления и умножения двух элементов в поле Галуа СР (2 ). Цельизобретения - увеличение функциональных возможностей ячейки за счет. выполнения операций одновременного возведения в степень и деления двух элементов в поле Галуа СР (2). Поставленная цель достигается тем, что устройство содержит 2 щ умножителей,коммутационное поле задания вычисляемых Функций, сумматоры, а мультиплексоров. В устройстве происходит вычисление выражений Е/А (1=1,6) и АВ+С .в поле СР (2 ) путем реализации соответствующих аналитических выражений,содержащих операции умножения и сложения.ил.1236458 модуля при синтезе дискретных устройств, а также в качестве блока припостроении процессоров, оперирующихнад элементами в поле Галуа СУ (2 ).Цель изобретения - увеличениефункциональных возможностей ячейкиза счет выполнения операций одновременного возведения в степень и деление двух элементов в поле ГалуаСР (2 ),На чертеже приведена структурнаясхема устройства для случая вычисления выражений В/А и АВ+С при ш=З,где ш - число переменных.Устройство содержит шины 1-3 записи делимого в поле Галуа СГ (2 ),шины 4-6 записи делителя в поле Галуа СР (2 ), первую группу -15 умно 1жителей, вторую группу 16-24 умножителей, коммутационное поле 25 заданиявычисленных функций, первую группусумматоров 26-28, вторую группу сумматоров 29-31, третью группу сумматоров 32-34, мультиплексоры 35-3, управляющие входы 38 мультиплексоров,выходные шины 39 устройства, шины40-42 записи слагаемого в поле ГалуаСР (2 ), входы 43 мультиплексоров.В качестве примера рассматриваютсоединение выходов умножителей с входами сумматоров 32-34 для вычиспениявыражения В/А , Подключение выходов5умножителей к входам сумматоров 3234 осуществляется через коммутационное поле 25 задания функций, Связидля вычисления остальных выраженийтипа В/А , В/А , В/А , В/Аи В/А"получают из аналитических выражений.Подключение выходов умножителей квходам соответствующих сумматоров32-34 осуществляется через поле 25.Выходы сумматоров 32-34 по модулю. дваподключены к входам мультиплексоровтак, что при заданном коде, подавае- .мом на управляющие входы 38, на выАРВо+А 1 В,+А 2 ВР+Ал А 2 В, +А, А,В, +АВ+АР В Аналитические выражения, с помощьюкоторых строятся схемы для аппаратнойреализации выражений В/А , В/АВ/А , В/А , В/А , В/А, имеют следующий вид:, +1.А, В,+А Б Изобретение относится к вычислительной технике и предназначено для использования в качестве логического О 5 2 О 25 ЗО 35 4 О ходных шинах 39 вычисляется одно извыражений В/А" . Выходы сумматоров 2628 по модулю два соединены с первымивходами сумматоров 29-31 по модулюдва, выходы которых подключены к входам мультиплексоров 35-3, на выходах39 которых получают решения выражений типа АВ+С и В/А .Элементы поля Галуа А, В.и С приш=З представлены в виде А=А а +А,а +=С.а +С,а +С 1 а 2, где знак + - суммирование по модулю два.Поле Галуа СГ (2 ) содержит 2 +1различных элементов которые образуют циклический код, среди которых шэлементов этого поля являются линейно независимыми. Путем линейной комбинации этих элементов получают остальные. Так при ш=З элементами поляГалуа С 1" (2 ) будут а=100; а =ОО;а =001; а =110; а"=011; а=111 иа =101,Схема умножения двух элементов поля Галуа для ш=З А и В описываютсяследующими аналитическими выраженияМИ: (АРВ,+АлВ 2+А 2 В 1) - КОЭффнцИЕНтпри а; (А.В +А,В,+А, В,+А В, +А,В,)коэффициент при а; (А,В,+А,В, +А В, ++А В ) - коэффициенты при а 2,Известно,что деление элемента Вна элементы А выполняется путем умно жения элементов В на элемент А , ко"торый является инверсным к элементу1 оА, причем АА =А =. Для данного элеМента А=Аа+Аа +А а в поле ГалуаСУ (2 ) аналитические выражения длявычисления инверсного элемента Аимеют вид А, =А +А, +А,+А, А,; ААоА 1+А 2 А 2 Ао АР+А +А 2 илиА3 236458 4ВоАо+Во Аю +Во А 2+Вд А А 7+В 1 АоА 7 +В 2 А 1 +ВВ,А, +В А А+В, А, +ВА+В 1 А, + ВА +В, А, А +ВА,А +ВА, +В Ац о 1 о 7 о ( 1 О7 1 1 2 Т 7 2 1 В/А" В А +В А А еВ А +В А,В,А,+В.А,+В,А+В, А,+В,А,В/А Для вычисления выражения В/А выходы умножителей, на которых вычисля- ются необходимые произведения, где коммутационное поле 25 заданияфункций, подключаются к входам трех сумматоров 32-34, на выходах которых образуются три слагаемых суммы, соответствующие В/А Напримерм для В=а =111 и А=а = =110, имеем В, =В, =В =1, А,=А, =1 и А =О, Подставляя значения этих коЯэффициентов в аналитические выраженияф для вычисления В/А , получают О 1=а При этом а/(а ) =а/а =а /а=а а ==а =а а =а , так как инверсным эле 77 7 4ментом для элемента а является элеб 30мент а Логическая ячейка работает следующим образом.На входы 1-3 подаются сигналы, соответствующие коду элемента В (коэффициенты В В В ) на входы 4-6 - сигналы, соответствующие коду элемента А (коэффициенты А А А ), При подаче двоичного кода на управляющие входы 43 выполняется передача резульао тата вычисления на выходы устройства с выходов сумматоров по модулю два,При ш=3 в устройстве содержатся шесть групп сумматоров по модулю два.7 Случай вычисления выражения В/А яв 7 о ляется тривиальным, так как А =А т,е. равно единичному элементу, Выражение АВ+С вычисляется при помощи схемы, состоящей из первой и второй групп сумматоров по модулю два подключенных через коммутационное поле 25 к выходам умножителей первой группы. Имея набор аналогичных устройств, можно создавать устройства для вычисленря совокупности всех выражений В/А , где д=1-6, и выражение АВ+С в данном поле.,Формула из обретения Устройство для выполнения операций возведения в степень, деления и умножения двух элементов в поле Галуа ОК (2 ), содержащее первую матрицу размером т 7 п умножителей, две группы из и сумматоров по модулю два, коммутирующее поле задания вычисляемых Функций, причем выходы умножителей первой группы через коммутирующее поле задания вычисленных Функций подключены к входам сумматоров по модулю два первой группы, выход -го сумматора по модулю два первой группы подкл 7 очен к первому входу д-го сумматора по модулю два (з.=1,2.,и) второй группы, второй вход которого подключен к -му входу слагаемого в поле Галуа ОГ (2 ) устройства, К-е входы делимого Ь=12 ,щ) и )-е входы делителя (Д=1,2,.. ш) подключены соответственно к первому и второму входам умножителя К-й строки 1-го столбца первой матрицы умножителей, о т л и ч а ю щ е ес я тем, что, с целью расширения Функциональных возможностей за счет выполнения операций возведения в степень и деления двух элементов в поле Галуа ОГ (2 ), в него введены вторая матрица размером шкш умножителей, с третьей по (2 +)-ю группы сумматоров по модулю два, 7 п мультиплексоров, первые и вторые входы умножителей Е-й строки -го столбца второй матрицы умножителей подключены соответственно Е-м входам делимого и -м входам делителя устройства, а их третьи входы - к ( 1+1)-м входам (.1=1,2 ,ш) делителя, третьи входы умножителей ш-го столбца второй матрицы подключены к первому входу делителя устройства, выходы умножителей первой и второй матрицы через коммутирующее поле задания вычисляемых функ1236458 Сми о авител ед И.Х он Корректор В, Бутя едактор Н, Гул аказ 3091/5 Тираж 6/1 ВНИИПИ Государственного комит по делам изобретений и отк 113035, Москва, Ж, РаущскаПодписита СССР ытии наб., д. 4/ Производственно-полиграфическое предприятие, г. Ужгор Проектная, 4 ций подключены к входам сумматоровпо модулю два с третьей по (2 +1)-югруппу, выходы -х =1,2 гй)сумматоров по модулю два, начиная свторой по (2 +1)-ю, групп подключены к информационным входам -х мультиплексоров управляющие входы которыхявляются входами кода операции устройства, а выходы - выходами результата устройства,