Устройство для умножения двух элементов конечного поля gf(2 )

Номер патента: 1672438

Авторы: Нурутдинов, Столов

ZIP архив

Текст

(54) УСТРОЙС ДВУХ ЭЛЕМЕ (;Е(2")(57) Изобретени ной технике и м разработке схе вания, Цель и функциональны ножения двух и ля ОЦ 2"), Устро линейных комб п-входовых эле вых сумматоров ТВО ДЛЯ УМ НТОВ КОНЕЧН ЕНИЯ ПОЛЯ 31арственный-Ленинаи Е,Л,Столо ислительнение при екодиро- ширение ерси ьство СССР9, 1980,последова1974, с.2 чет умтов по(56) Авторское свидетМ. 824202, кл. 6 06 ГГилл А. Линейнмашины. - М,: Наурис,7,3,е относится к выч ожет найти приме м кодирования и д зобретения - рас х возможностей з роизвольных элем йство содержит и инационных схем ментов И 5 оп.1 и по модулю два боВ;с) а,; . " п 1 ) 1 л Изобретени птпс.ится к вычислительной тг хике и може 1 гаии применение при разработке схегл кодирования и декодированля 5( лью изобретения является расширение Функциональных возможностей за счет умножения двух произвольных элементов поля 6 с (2"),Метод получения произведения двух 10 с 1 рпизпппьсых элементов поля 6 Г (2"), положессыи н основу работы устройства, закп очлется в следующем.Элементы конечного поля 6 Г (2") задаются н матричном представлении. При 15 этом любому ненулевому элементу поля 6 Р (2 "1 становится в соответствие степень А С (Г 1, 1 22), где А сопровождающач млтриса примитивного многочлена г(х) х 21 хс и 1 х+ Гхп с коэффици 20 ентами из 6 Г(2 ), Изоморфизм с векторным представлением мпжнО усановь, сопоставив матрице ЕЕ ПЕРВЫЙ СтОЛбЕц (а 11, а 21дп 1) . ДЛя ПЕ ремножения элементов а(ао, а 1, а,-1) и (1 (бсь О 1,., Оп 1), ГХ,/1 6 Г(2 )НадО НайтИ Матрицы В 1 и В 2, первыми столбцами которых являются Гх и/3 .перемножить матрицы В 1,т ти В 2 и выделить первый столбец из пРоиз ведения, Первыи столбец произведения матриц равен произведению первой матрицы на первый столбец второй матрицы. Таким образом, отпадает необходимость поиска В 2, а чтЬбы вычислить сХ /3 доста точно вычислить В 1/1, Покажем, как мОжнОтнаити матрицу В 1 Непосредс 1 венным подсчетом можно убеди 1 ься что первые столбцы мат 1 иц 1, А А, А" 1 оавны (1, 00), (О, 10)(О, 00,1) соответст венно. Поэтому первый стгпбец матрицы С =: аОа 1 А. Я, си 1 1Равен (ап, а 1, .ап 1) . Эго О 1 начает, что най денная по Формуле (1) матрица С совпадает с В 1. 1 аким Образом произведение произвольных элеглент 1 в 2 (аап 1) И (г (б, , 1 глиж Осл; и по, ОрмулЕ На чертеже пр 11 спвп на Функциональ. ная схема устроисьпУстройство сод 1 рки ч разрядный вход 1 первого сомножигеля ус с ройства, и п-мерных линейных комбинационных схем 2, - 21 1, и-разрядный вход 3 второго сомножителя устройства, п-разрядный выход 4 результата устройства, п и-входовых элементов И 5 оп 1 И П П-ВХОДОВЫХ СУММатоРОВ бо-бппо модулю два,Каждая из линейных комбинационных схем К; состоит из совокупности и и-входовых сумматоров по модулю два и реализует умножение входного вектора 3 соответсттвенно на матрицы 1, АА"Элементы О управляются разрядами ао, а 1ап.1 ВЕКтОРа а.Сумматоры б,-бп.1 осуществляют суммирование по модулю два сигналов с соответствующих выходов разрядов линейных КОМбИНацИОННЫХ СХЕМ Ко, К 1 Кп,Устройство работает следующим образом.На п-разрядный вход 1 подается п-разрядный сигнал, соответствующий первому СОМНОжИтЕЛЮ/3=(Эо, Ь 1 Ьп), На П-раэрядный вход 3 подается и-разрядный сигнал, соответствующий второму сомножителю а= (ао, а 1 ап), При этом в линейной комбинационной схеме К происходит умножение вектора 3 на матрицу А, 1 = О, п тсоответственно, п-разрядные результаты умножений подаются на и-разрядные входы элементов Иь через которые и-разрядный сигнал проходит (если соответствующая компонента вектора Гх равна единице, то есть а = 1) или не прохоидт (если соответствующая компонента вектора а равна нулю, то есть а = О). Разряды и-разрядного результата умножения получаем на выходах соответствующих сумматоров бо-бп 1 по модулю два,П р и м е р, Пусть задано поле 6 Е (2 з) смодулярным многочленом гтх) = 1 + х + х, Сопровождающая матрица Вычислим произведение элементов поля 6 Р (2 з)(1, 1, О) и Р= (1, 1, 1),Им соответствуют матрицы1 т 1 72438 ответствующими входал 1 и первой и-мерной линейной комбинаион нои схг мы, о тл и ч а ю щ е е с я тел 1 что, ; целью расширения функциональных возможностей за 5 счет умножения двух произвольных злелентов поля 6 Е (2"), в него введены (и) и мерных линейных комбинационных схем. и и (и 1)-разрядных элементов И, причем разрядный вход первого сомножителя устрой ства соединен с соответствующимивходами каждой из (и) и-мерных линейных комбинационных схем, вход -го разряда второго сомножителя устройства ( - О,п) соединен соответственно с первыл входом 15 )-го (и+1)-разрядного элемента И. входы свторого по(п+1)-й которото соединены соответственно с выходами разрядов -й и-мерной линейной комбинационной схемы, -й выход каждого (и+1)-раэрядното элемента И соединен с соответствующим входом -го пвходового сумматора по модулю два, выход которого соединен с выходом )-го разряда результата устройства 101 111 011 111 1001 0 и А 5Найдем их произведение А А = А А,3, 5 8причем матрице А соответствует элемент (О, 1, 0), С другой стороны элементам а и /3 соответствуют многочлены(1х) и (1 + х + х ).Найдем их произведение: (1 + х) (1+ х +х ) . - . 1 + х, Остаток от деления на много 2 3член г(х)1 + х + х равен х, по которомузсоответствует вектор (О, 1, 0), Таким образома /)=(0,1,0),Формула изобретения Устройство для умножения двух элементов конечного поля С Г (2"), содержащее первую и-мерную линейную комбинационную схему и и и-входовых сумматоров по модулю два, причем разрядный вход первого сомножителя устройства соединен с соСоставитель Е.МурзинаТехред М,Моргентал Производственно-издательский комбинат "Патент", г, Ужгород, уллз 1 пн,Редактор О.Юрковецкая Корректор А ОсаулпнкоФЗаказ 2840 Тираж 373 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям иптГГГ113035, Москва, Ж, Раушская наб, 4/5

Смотреть

Заявка

4691078, 11.05.1989

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. В. И. УЛЬЯНОВА-ЛЕНИНА

НУРУТДИНОВ ШАМИЛЬ РАМИЛОВИЧ, СТОЛОВ ЕВГЕНИЙ ЛЬВОВИЧ

МПК / Метки

МПК: G06F 7/49

Метки: двух, конечного, поля, умножения, элементов

Опубликовано: 23.08.1991

Код ссылки

<a href="https://patents.su/3-1672438-ustrojjstvo-dlya-umnozheniya-dvukh-ehlementov-konechnogo-polya-gf2.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для умножения двух элементов конечного поля gf(2 )</a>

Похожие патенты