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

СООЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК АНИЕ ИЗОБРЕТ СВИДЕТЕЛЬСВ Т ДВТОРСН 1 ил. ГОСУДАРСТВЕННЫЙ КОМИТЕТ С ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТК(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ И ВОЗВЕДЕНИЯ В СТЕПЕНЬ ДВУХ ЭЛЕМЕНТОВВ ПОЛЕ ГАЛУА СР(2 )(57) Изобретение относится к вычислительной технике и предназначено для 801236457 А 1 использования в качестве логическогомодуля при синтезе дискретных устройств, Целью изобретения являетсярасширение его функциональных воэможностей за счет реализации вычисления выражений вида А В Ос щ 1, 2 - ).Устройство содержит входные и выходные шины, элементы И и сумматорыпо модулю два. Работа устройства основана на том, что в поле ГалуаСР (2") можно одновременно с помощью комбинационных схем выпол. -нять операции возведения в сте-.пень и умножения двух элемен1 О а = аа +а =а+ а=ааО + атьа +а+а8 оаа аУмножение дв аух элементов поля ВА. = А В + А,В, + А В + А В;ВАт =АВ +Авс+АВ. ьАВ +АВ Изобретение относится к вычислительной технике и предназначено для использования в качестве логического модуля при синтезе дискретныхустройств, а также в качестве блокапреобразователя при построении универсальных логических устройств,Цель изобретения - расширениефункциональных возможностей за счетреализации вычисления выражений вида А В (1 с = 1, 2 - 1).На чертеже приведена схема устройства для случая щ = 3 и вычисления выражения А - В.Устройство содержит сумматорыно модулю два, коммутаторы 2, группы 3 двухвходовых элементов И 42группы 5 щ-входовых элементов И б,управляющие входы 7, информационныевходы 8, входы 9 настройки, выходы10, коммутационное поле 11 заданиялогических функций,Устройство работает следующимобразом.Работа устройства основана на том,что в поле Галуа СГ (2 ) можно одновременно с помощью комбинационныхсхем выполнять операции возведенияв степень и умножение двух элементов,Известно, что поле Галуа СР(2 )содержит 2 - 1 различных элементов,которые образуют циклический код,Среди них щ элементов являются линейно независимыми, Путем линейнойкомбинации этих элементов можнополучить остальные, Элементы поляможно получить с помощью неприводимых полиномов щ-й степени. Так прищ = 3 таким полиномом является3х + х + 1, а линейно независимымиэлементами поля при щ = 3 являютсяа = 100; а = 00 и а = 001.С помощью этих элементов любойэлемент в поле Галуа СГ(2 ) можнопредставить в виде А = А,а + А, а ++ Ага , а другой элемент отличаетсяот элемента А значениями коэффициентов А А, и А , т.е, элемент2В = В,а + В, а + В,а, причем коэффициенты А,А,Аг В,гВ и Вгв двоичной системе счисления принимают значения 0 или 1,Если элемент а является корнемполинома х г + х + 1, получаютаз + а += О, отсюда а = а +а = 110; а" = а а = а + а выполняется путем прямого умноженияэлементов, представленных в ниде О полинома: АВ = (А,а + А а ++ Атв ) Обозначив коэффициенты при а,а и а 2 соответственно через С С,25 и С , получаютСс АоВо + Авг + Атв 9 Эб + АВПри А = В из выражений (1) получают выражения для возведения элемента поля СЕ(2 ) в квадратеС=А,А, А,А, +А,А, =А,;А + А,;С," = А.А, + АА. + А Ат + АгА +т 2 2 4 п Путем итерации получают выражения для возведения элемента А в куб,так как А = А АС, =А, +А, +А,+ААС=АА, +АА, +А,;45 С-= АА +А и так далее вплоть до шестой степени,Приняв выражения для умножения двух элементов поля и возведения в степень как исходные, получают выражения для одновременного возведения в степень и умножения двух элементов которые аппаратно реализуются в устройстве при помощи групп 3 и 5 элементов И, коммутационного поля и сумматора 1 по модулю два:3 236457 4ВА =АБ +АВ, +АВ, +ЛВ +АВ, +АБ,ВАо =АоВ +АВ +АВ +ААВ +ААВ +ААВ +ЛБ +А.В +ЛВВА=А,Б, +А,В, +А,А,В, +А,А,В, +А,Л,В, +ЛАВ +ЛВ +А,АБ, +АВВА = АоВ + А, В + А,А,В, + А А В, + А А Б + А Б + А Л Б + А А Б + А В5и так далее, вплоть до 6 степени, .-го коммутатора, ьыход которого соНапример, пусть даны элементы единен с 1-и вьходом устройства, -йВ = а = 110 и А = а = 111, Необхо- вход задания показателя степени устздимо вычислить ВЛИмеем В, = 1; Ройства соединен с 1.-ми управляющимиВ 1 = 1; В = 0; Л, = 1; А = 1 и О входами каждого коммутатора, о тА = . Подставляя эти коэффициенты л и ч а ю щ е е с я тем, что, св выражения для вычисления ВА , полу- целью расширения функциональныхзчим ВА = 0 ВА = 0 ВА = 1. В ре- возможностей за счет реализации вью Ф 1 фКзультате получаем элемент а = 001; числения выражений вида А Втак как (А ) = а = (а ) а =(а")" 5 = 1, 2 - 1), в него введены п 1 группа =а на а=а5йиз щ щ-входовых элементов И, и коммутационное поле задания функций,В устройстве выбор одного из выра- причем -й информационный вход устжений В А проводится при помощи ком- Ройства ( = 1, щ) соединен с первыммутаторов 2 путем подачи соответст входом каждого двухвходового элеменвующего кода на входы задания пока- та И 1-й группы и 1-м входом каждогозателя степени 7 устройства, щ-входового элемента И 1 (1.-1)и (1. + 1) п групп, х-й входФ о р м у л а и з о б р е т е н и я настройки устройства соединен свторыми входами -х двухвходовыхУстройство для умножения и возве- элементов И каждой группы и 1-м входения в степень двух элементов в по- дом щ-входового элемента И 1-йле Галуа СР(2 ), содержащее 2 - 1 группы ( - 1 р щ) Входы каждогогрупп из щ сумматоров по модулю два, двухвходовых элементов И каждойщ коммутаторов и щ групп из щ двух- ЗО группы и выходы каждого щ-входово-входовых элементов И, причем выход го элемента И каждой группы соедине 1-го сумматора по модулю два ( ны через коммутационное поле задат1, щ) 1-й группы (1 = 1, 2 - 1) ния функций с входами сумматоровсоединен с 1-и информационным входом гРупп.123645/ Составитель С., МорозТехред М.Ходанич Редакто Корректор В.Бутяга Заказ 309)/ ного к те ч 5 ска роизводственно-полиграфическое предприятие, г, Ужгород, ул, Проект 51 Тираж ВНИИПИ Государств по делам изобре 113035, Москва, Ж-Э 5, итеткрытнаб Подписиа СССРий