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

(й)5 О 06 Г ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ КОМУ СВИДЕТЕЛЬСТВУ ВТ(22) .17,07,90 ОЕ(2 ), образованных различными (46) 23.08.92. Цюл. М 31 неприводимыми многочленами, где п - гра- (71) Научно-исследовательский институт бы- ничная степень в расширения поля ОР (2 ), товойрадиоэлектроннойаппаратуры Целью изобретения является расширение (72) И.И.Ковалев функциональных возможностей устройства (56) Авторское свидетельство СССР за счет обеспечения выполнения им за один М 1061134, кл, О 06 Р 7/49, 1982, такт Работы операцйи умножения элеменАвторскОе свидетельство СССР тов произвольных конечных полей ОГ (2). М 1013950, кл. О 06 Е 7/52, 1982 Устройство содержит регистры 1-4, блок 5 (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЗЛЕ- . формирования частичных произведений, МЕНТОВ КОНЕЧНЫХ ПОЛЕЙ ОЯ 2") . дешифРатоР 6; блок 7 фоРмиРованиямлад- (57) Изобретение относйтся к вычислитель- . ших коэффициентов, блок 8 формирования ной технике, выполняет операцию умноже-старших коэффициентов, блок 9 формирова. ния двух элементов конечных полей за одинния степеней примитивного элемента, блок такт его работы и может быть использовано 10 выравнивания коэффициентов, блок 11 в кодирующих и декодирующих устройствах запрета и блок 12 суммирования, 3 з,п. ф-лы,3йдвоичных кодов, оперирующих данными какэлементами различных конечных полейответствующего числа, а низкого уровня -нулю.Устройство для умножения элементовконечных полей работает следующим обра5 зом,Процедура 1.В исходном состоянии устройства наего входы коэффициентов первого и второго+ С 1 Х+ Со сомножителей, на входы коэффициентов не 10 приводимого многочлена и на входы степерегистрах 1 - 3 осуществляется прием, ни гп РасшиРениЯ полЯ, а значит нахранение и выдача коэффициентов а, Ь, , информационные входы регистров 1-4 подсоответственно. В регистре 4 осуществляет-; аются сигналы низких уровней. Кроме того,ся прием, хранение и выдача двоичного регистры 1-4 сброшены в нулевое сбстояпредставления числа в (степени расшире ние посРедством подачи импульсных сигнания поля полиномов СЕ (2 П), над которым лов высоких уровней на первый и второйосуществляется операция умножения), входы сбРоса устройства, после чего на перВ блоке 5 осуществляется попарное ум- вый и второй входы сброса устройства подножение ар Ь над полем СЕ(2) всех коэф- аются сигналы низких уровней,фициентов первого и второго сомножителей .20 При этом на выходах всех регистров 1-4соответственно,сформированы сигналы низких уровней, аВ дешифраторе 6 осуществляется фор- значит, сигналы низких УРовней сфоРмиРомирование сигнала высокого уровня на гп- ваны также на всех выходахпервой и второйом выходе, соответствующему двоичноМУ групп выходов блока 5 формирования часпредставлению числа п 1. 25 тичных произведений на выходах блоков 7,В блоках 7 и 8 осуществляется форми и 11, что, в свою очередь, приводит крование сигналов, соответствующих ь и . форированию сигналов низких уровней настаршимс, коэффициентам произведения, вьходах устройства коэффициентов резульВ блоке 9 осуществляется формирование на его выходах сигналов, соответствую Процедура 2.щих степеням примитивного элемента поля ПеРед началом Работы УстРойство Ум 1 ножения элементов конечных полей настраивается на поле ОЕ (2 ), элементы которогоВ блоке 10 осуществляется фо ми оваВ б 10 ущ с ляе ся формирова- устройство будет умножать.ние на его выходах сигналов, соответствую-35 акая настройка производится путемщих сигналам на его первой группе входов,Р РУ д в подачи импульсного сигнала навторой входсмещенных на и-гп выходов в сторон выходов с меньшими номерами.д Р У в о . сброса устройства, а затем подачи на каждый 1-й вход устройства ( = 1,2,:;п) коэфВ блоке 11 запрета осуществляетсяорми ование на его выходах сигналов, соР Ущ фициентов неприводимого многочленаответствующих сумме , 11 а. В блоке 12ло" ни п 1 расширения поля - ймпульсныхосуществляется формирование на его выхо- сигналов, соответствующих двойчномудах сигналов, соответствующих коэффици- представлению числа т, причем)-й вход О =ентамс 1 произведения 45 "2 3 о 92 +1)) соответствует 1-муПри описании принципа действия уст- разряду двоичного првдставления числа п 1.ройства умножения элементов конечных по- . ПРи этом на том. 1-ом выходе регистра 3лей (фиг. 1) необходимо учитывать, что. и на том)-ом выходе регистра 4, для которыхвысокий уровень сигнала на входе или вы- и ". )-ый Разряд двоичного представленияходе функционального элемента или уст числа гп равны единице, формируются сигройства определяет истинное значейИЕ налы высокогоуровнясоответственно.величины, а низкий уровень - ложное. Значит, на т-ом выходе дешифратора 6,КРОме ТОГО, Единице в двсичном прЕд- на п 1-Ом вхОдЕ втсрОй группы вхсдОв блокастаблении какого-либо числа соответствует 10 и на (п 1-1)-ом входе (при п 11) второй. сигнал высокого уровня на соответствую группы входов блока 9 формируется сигналщем входе или выходе, а нулю - низкого высокого уровня, На выходах блока 9, а зна- .уровня и наоборот, сигнал высокого уровня чит на второй гРУппе входов блока 11 форна каком-либо входе или выходе соответст- мируются сигналы, зависящие от сигналоввует единице в двоичном представлении со- на первой и второй группах входов блока 9в соответствиис принципом действия блока9,Процедура 3,Для выполнения умножения элементовП 1 1конечного поля ОГ (2") а(х) =,Я аяхр ир=ОВЬ(х) = ; Ьяхч необходимо на каждыйа=о(и-гп+1+р)-й вход устройства коэффициентов первого сомножителя и на каждый (ц+1)-й вход устройства коэффициентов второго сомножителяподать импульсные сигналы, соответствующие коэффициентам ар и Ьп соответственно, а на остальные входы устройства - подать сигналы низких уровней. При этом, на (и-п 1+1+р)-тых выходахрегистра 1 и (о+1)-тых выходах регистра 2; для которых ар и Ья равны единице, сформируются сигналы высоких уровней соответственно.Дальше на выходах блоков 5,7, 8, 10, 11 и 12 формируются сигналы, соответствующие логике их работы.Процедура 4,Для выполнения устройством операции умножения элементов тото же поля ОГ (2"), на которые уСтройство настроено, необходимо сначала сбросить в нулевое состояние регистры 1 и 2 путем подачи импульсных сигналов на первый вход сброса устройства, а затем выполнить процедуру 3,Процедура 5,Для выполнения устройством операции умножения элементов другого поля, отличного от поля, над которым устройство выполняло операции умножения ранее, необходимо выполнить йроцедуры 2 и 3,Формула изобретения1. Устройство для умножения элементов конечных полей ОГ(2"), содержащее первый и второй и-разрядные регистры, блок формирования частичных произведений и блок суммирования, выходыкоторого соединены с выходами коэффициентов произведения устройства, входы коэффициентов первого и второго сомножителей которого соединены соответственно с информационными входами первого и второго и-разрядных регистров, выходы которых соединены с соответствующими. входами блокаформирования частичных произведений, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет выполнения операцииумножения произвольных конечных полей ОГ (2") (где 2ти), образовлнных различными непри 5 10 водимыми многочленами за один такт работы, в него введены третий (и)-разрядный регистр, четвертый ( 1 1 оц 2(п+1))-разрядный регистр, дешифратор, блок формирова-. ния степеней примитивн.ого эл.емента, блоки формирования старших и младших коэффициентов произведения, блок выравнивания коэффициентов и блок запрета, выходы которого соединены с входами первой группы блока суммирования, входы. второй группы которого соединены с выходами блока выравнивания коэффициентов, входы первой группы которого соединены с выходами блока формирования младших коэф-15 фициентов произведения, входы которогосоединены с выходами первой группы выходов блока формирования частичных произведений, выходы второй группы которого соединены с входами блока формирования 20 старших коэффициентов произведения, выходы которого соединены с входами первой группы блока запрета, входы второй группы которого соединены с в 11 ходами блока формирования степеней примйтивного элемен та, входы- первой группы которогосоединены с выходамй третьего (и)-разрядного регистра, информационные входы которого соединены с входами коэффициен-тов неприводимого многочлена устройства, 30 входы степени а расширения поля которогосоединены с информационными входами четвертого (3 1 оц 2(п+1) )-разрядного реги-.стра, выходы которого соединены с входами дешифратора, выходы которого 35 соединены с входами второй группы блока. выравнивания коэффициентов и блокаформирования степеней примитивного элемента, входы сброса первого и второго и-разрядных регистров соединены с пер вым входом сброса устройства, второйвход сброса которого соединены с входами сброса третьего (и)-разрядного и четвертого ( 3оц 2(п+1) Г )-разрядногорегистров.45 2,Устройствопоп,1,отличающеес я тем, что блок формирования степеней примитивного элемента содержит источник сигнала высокого уровня и (и) преобразователей сигналов, причем )-йые входы пер вой группы .=1 п) каждого 1-гопреобразователя сигналов (1=1,п) и )- ные входы (и)-го преобразователя сигналов соединены с соответствующими выходами блока, входы первой группы кото рого соединены с входами второй группыкаждого )-го преобразователя сигналов и +1) входами первой группы первого преобразователя сигналов, первый вход первой группы которого соединен с выходом источника сигнала высокого уровня, входы вто10 1756883 Фиг рой группы блока соединены с входами соединены с управляющими входами сооттретьей группы каждого 1-го преобразовате- ветствующих ключей, информационный ля сигналов, выходы 1-го преобразователя . вход-гоключасоедйненс(+1)-нымвходом сигналов соединены с входами первой груп- первой группы преобразователя сигналов, пы (+1)-го преобразователя сигналов 5 4, Устройство по и. 3, о тл и ч а ю ще в(=1(п-З. с я тем; что каждый субблок преобразова 3; Устройство по и. 2, о т л и ч а ю щ ее- ния сигналов содержит демультиплексор, с я тем, что каждый преобразователь сигна-сумматор по модулю два и мультиплексор, лов содержит (и) ключей и (л) субблоков выход которого соединен с выходом субблопреобразования сигналов, выходы всех 10 ка преобразования сигналов, первый вход ключей и первые входы всех субблоков пре- которого соединенс первым входом сумма- образования сигналов обьединены и соеди- тора по модулю два,второй вход которого нены с первым выходом преобразователя соединен с первым выходом демультиплексигналов, (и) следующих выходов которого,сора, информационный вход которого соесоединены соответственно с выходами(п) 15 динен с вторым входом субблока субблоков преобразования сигналов; вто- преобразования сигналов, третий вход корые входы которых и информационный вход торого соединен с управляющими входами (л)-го ключа соединены с соответствующй-: демультиплексора и мультиплексора, перми входамипервой группы преобразовате- вый и второй информационные входы котоля сигналов, третьи входы всех субблоков 20 рого соединены соответственно с выходом преобразователя сигналов соединенц с вхо-сумматора по модулЮ 4 Фа и вторым выходом дами второй группы" преобразователя " демультиплексора.сигналов, входы третьей группы которого,.Составитель Е.МурзинаРедактор О.Хрипта Тех ред М.Моргентал Корреаказ 3088 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Раушская наб., 4(5 оизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 10