Устройство для умножения двух элементов конечного поля gf(2 @ )
Изобретение относится к вычислительной технике и может найти применение при разработке схем кодирования и декодирования. Цель изобретения - расширение функциональных возможностей за счет умножения двух произвольных элементов поля GF/2<SP POS="POST">N</SP>/. Устройство содержит N N-мерных линейных комбинационных схем 2<SB POS="POST">0</SB>-2<SB POS="POST">N-1</SB>, N N - входовых элементов И 5<SB POS="POST">0</SB>-5<SB POS="POST">N-1</SB> и N - N входовых сумматоров по модулю два 6<SB POS="POST">0</SB>-6<SB POS="POST">N-1</SB>. 1 ил.
сс»к13 col(I тг;ких
С(1l(ИА 1И(.!И lг СКИХ
Р е с11у т» (1и к (s I Is G 06 Г 7/49 госуд/((стиг-н11ь(и комитгт
110 ИЗОГ»РГ f Нит1М И O I ÊI I»11 ИЯМ
1!ПИ (КН1 СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4691078/24 (22) 11.05.89 (46) 23.08.91. Бюл. N 31 (71) Казанский государственный университет им. B.È.Óëüÿíoeà-Ленина (72) Ш.P. Нурутдинов и Е.Л. Столов (53) 681.325(088,8) (56) Авторское свидетельство СССР
¹ 824202, кл. G 06 F 7/49, 1980.
Гилл А. Линейные последовательные машины. — М.: Наука, 1974, с.251-255, рис.7.3, „„Я) ÄÄ 1672438 Al (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ
ДВУХ ЭЛЕМЕНТОВ КОНЕЧНОГО ПОЛЯ
G F(2п) (57) Изобретение относится к вычислительной технике и может найти применение при разработке схем кодирования и декодирования. Цель изобретения — расширение функциональных возможностей за счет умножения двух произвольных элементов поля GF(2"), Устройство содержит и п-мерных линейных комбинационных схем 2o — 2л-l, и п-входовых элементов И 5Π— 5П-1 и и п-входоBblx сумматоров по модулю два 6(I-6п 1. 1 ил.
1672438
Э<1 Э1) ... 31n
А1 э 21 э„1 ...а, 001
А= 101
010
Тогда
010
А= 011
101,;»
» 1
А
Изобретение пт»<понтся к вычислительIIoIz! TE xI1I1êå и може<»<ли<и применение при
Рэзр;<ботке схем кодирования и декодироnr3 < I ».1я.
lI» ëüþ изобретения является расширение функциональных возможностей за счет умножения двух произвольных элементов поля G 1» (2"), Метод получения произведения двух 10 пг<пизпппьных элемеI Элементы конечного поля G F (2") задаются н матричном представлении. При 15 этом любому ненулевому элементу поля G Р (2п) становится в соответствие степень А i< (0 1 2" 2), где А сопровождающэч матрица примитивного многочлена г(х) x»»11 х < .. ГГ»» 1х < Гхп с коэффици 20 ентэми из Г F (2п), Изоморфизм с векторным предст;1! Т ЕЕ ПЕРВЫЙ СтОЛбЕЦ (а11, aZ1,....an1) . ДЛЯ ПЕремножения элементов а(а), а<...., а,-1) и jJ (h»n h1,, bn 1), ГХ,/) GF(2")НадО НайтИ Матрицы В1 и Bz, первыми столбцами которых являются Гх и/) .перемножить матрицы В1 ,т т и Bz и выделить первый столбец из произ- 35 ведения, Первыи столбец произведения матриц равен произведению первой матрицы нэ первый столбец второй матрицы. Таким образом, отпадает необходимость поиска Bz, а чтЬбь< вычислить ГХ /3 доста- 40 точно вычислить В 1/) . Покажем, как можно т нэити матрицу В1. Непосредс<венным подсчетом можно убедит ься <то первые столбцы мат 1иц I, А А,....А" 1оавны (1. 0,...,0), (О. 1,,0) ... (О. 0,,0,1) соответст- 45 венно. Поэтому первый стппбец матрицы С=:а а1А ° „, » э, 1 1 раВЕН (aî, Э1,....ап 1) . Э1Г) ОЗНЭ <Э» Т, ЧТО Най- 50 денная по формуле (1) мэт рицэ (совпадает с В1. 1эким образ»,м произведение ПРОИЗВОЛЬНЫХ Г<ПЕМPHТ»1B пг (Э„..... an-1) i1/) (h,- .... 1», I) мож <о»<;I,:. <о 1»<рмуле Начертежепр дс<пвп нэфункционэльная схема устроис In;I Устройство содержи< 1 разрядный вход 1 первого сомножи<еля ус i ройства, и п-мерНЫХ ЛИНЕЙНЫХ КОМбИНЭЦИОННЫХ СХЕМ 2„--2п.i, и-разрядный вход 3 второго сомножителя устройства, и-разрядный выход 4 результата устройства, п и-входовых элементов И 5о — 5п 1 и п Il âõîÄîâûõ сУмматоРов 6,- 6п 1 по модулю два. Каждая из линейных комбинационных схем Ki состоит из совокупности Il fl-входовых сумматоров по модулю два и реализует умножение входного вектора Р соответстт венно на матрицы 1, А...„А" Элементы Ui управляются разрядами а ), al,...,э, 1 вектора а. Сумматоры 6,-6,-1 осуществляют суммирование по модулю два сигналов с соответствующих выходов разрядов линейных комбинационных схем Ко, К1„...К„1, Устройство работает следующим образом. На п-разрядный вход 1 подается п-разрядный сигнэп, соответствующий первому СОМНОжИтЕЛЮ/3= (Ьо, b1,..., Ьп-1), На П-раэрядный вход 3 подается и-разрядный сигнал, соответствующий второму сомножителю a= (ао, à1,.... а -1). При этом в линейной комбинационной схеме К» происходит умножение вектора Р на матрицу А, 1 = О, п-1 т I соответственно, п-разрядные результаты умножений подаются на и-разрядные входы элементов Иь через которые и-разрядный сигнал проходит (если соответствующая компонента вектора а равна единице, то есть а = 1) или не прохоидт (если соответствующая компонента вектора а равна нулю, то есть ai = О). Разряды и-разрядного результата умножения получаем на выходах соответствующих сумматоров бо-6п-1 по модулю два. Пример. Пусть задано поле 6 F (2з) с модулярным многочленом 1тх) = 1 + х + х . Сопровождающая матрица Вычислим произведение элементов поля G F (2З) a= (1, 1, О) и P= (1, 1, 1). Им соответствуют матрицы 1612438 ответствующими входами первои и-мерной линейной комбинаl ионнои схемы, о тл и ч а ю щ е е с я тем. «ro, <: целью расширения функциональных возможностей за 5 счет умножения двух произвольных элементов поля G F (2"), в него введены (и-1) и мерных линейных комбинационных схем. и и (и 1)-разрядных элементов И, причем разрядный вход первого сомножителя устрой10 ства соединен с соотвегствующими входами каждой из (n-1) и-мерных линейных комбинационных схем, вход f-го разряда второго сомножителя устройства (i -- О„„,п-1) соединен соответственно с первым входом 15 i-го (и+1)-разрядного элемента И. входы с второго по(п+1)-й которо о соединены соответственно с выходами разрядов i-й и-мерной линейной комбинационной схемьi, I-й выход каждого (и+1)-разрядно о элемента И соединен с соответствующим пхолпм i-го ивходового сумматора по модулю два, выход которого соединен с выходом I-ro разряда результата устройства. 1 О 1 1 1 1 011 111 110 и А в Найдем их произведение. А А = А А. 3. в в причем матрице А соответствует элемент (О, 1, О), С другой стороны элементам а и /3соответствуют многочлены (1 x) и (1 + х + х ). Найдем их произведение: (1 + x).(1 + х + x ) = 1 + х . Остаток от деления на много2 3 член г(х) =- 1 + х + х равен х, по которому з соответствует вектор (О, 1, О). Таким образом а - /) = (0, 1, О). Формула изобретения Устройство для умножения двух элементов конечного поля G F (2"). содержащее первую и-мерную линейную комбинационную схему и и и-входовых сумматоров по модулю два, причем разрядный вход первого сомножителя устройства соединен с соСоставитель Е.Мурзина Техред М,Моргентал Производственно-издательский комбинат Патент", Г, Ужгород, ул I н; пцн,) Редактор О.Юрковецкая Корректор А.Осаулг Заказ 2840 Тираж 373 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям пр1 I l i f! ССГПО 113035, Москва, Ж-35, Раушская наб., 4/5
