Параллельное устройство для умножения в конечных полях

, 1383336 Р 7/49 9) ИЕ ИЗОБРЕТЕН б Вул ФЯЙф фт1, 1 г,1 чи инф олитех в,.П ССС 981. ССР 982. льство 54 НОЖЕНИЯ В (57) Изобрлительной ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОМУ СВИДЕТЕЛЬСТВ(71) Институт проблем передмации АН СССР и Пензенскийнический институт(56) Авторское свидетельствР 824202, кл. С 06 Р 7/49,Авторское свидетеУ 900281, кл, С 06 Р 7/49,АЛЛЕЛЬНОЕ УСТРОЙСТВО ДЛЯОНЕЧНЫХ ПОЛЯХтение относится к вычи ехнике и может быть ис пользовано для построения спецвычислителей произведения в конечых полях Цель изобретения - расширение области применения за счет возможности умножения элементов поля Галуа СГ(Р ), представленных в нормальном базисе. Предложенное устройство содержит и регистров 1, и блоков 2 умножения на примитивный элемент, и блоков 3 формирования частичных произведений, каждый из которых содержит и умножителей 4, и и блоков 5 суммирования с соответствующими связями. Блок 2 умножения на примитивный элемент содержит и групп по и элементов И и п сумматоров по модулю Р с соответствующими связями. Устройство про изводит умножение элементов поляиГалуа СР (Р ), представленных в нормальном базисе. 1 з.п. ф-лы, 2 ил.Изобретение относится к вычислительной технике и может быть использовано для построения спецвычислителей произведения в конечных полях.Цель изобретения - расширение области применения за счет возможности умножения элементов поля Галуа СР (Р ), представленных в нормальном базисе, 10На фиг,1 представлена структурная схема параллельного устройства для умножения в конечных полях; на фиг.2-структурная схема блока умножения на примитивный элемент. 15Устройство содержит и регистров 1, и блоков 2 умножения на примитивный элемент, п блоков З.формирования частичных произведений, каждый из которых содержит п умножителей 4, и и 20 блоков 5 суммирования, причем каждый блок 5 суммирования содержит и входных шин, каждая из которых содержит Рцепей, и входных шин первой группы первого блока 2 умножения на при митивный элемент соединены соответственно с первой группой информационных входов устройства, а и входных шин первой группы каждого блока 2 умножения на примитивный элемент, начи ная с второго, соединены с первой группой информационных входов устройства с циклическим сдвигом на один разряд в сторону старших разрядов, группы с второй по (и+1)-ю входных шин п блоков 2 умножения на примитивный элемент соединены соответственно с и выходами каждого из и регистров 1, каждый информационный вход второй группы устройства соединен с первыми 40 входами и умножителей 4 соответствующего блока 3 формирования частичных произведений, вторые входы которых соединены с выходами соответствующих блоков 2 умножения на прими тивный элемент, 1-й выход 3-го блока 3 формирования частичных произведений соединен с 3-м входом 1 с-го блока 5 суммирования (1=1,..,п; 3 - 1п; 1 с = +3-1 при 3.+1 ( и+1;1 с=ь 3-п-, при +3и+1), выходные шины блоков 5 суммирования являются выходом параллельного устройства для умножения в конечных полях.Влок 2 умножения на примитивный элемент содержит и групп по и элементов И 6 и и сумматоров 7 по модулю Р, причем каждая из входных шин первой группы блока 2 соединена с первыми входами и элементов И 6 соответствующей группы, вторые входы которых являются группами входных шин от второй до (п+)"й блока 2, выход го элемента И 6 1-й группы (1 =1и; 1=1п) соединен с 3-м входом 1 с-го сумматора 7 по модулю Р (1 с=1+1-1, при +1 ( и+1; 1 с=+3-п, при 1+1 ( и+1), выходы сумматора 7 по модулю Р являются выходами блока 2 умножения на примитивный элемент.Устройство работает по следующему алгоритму.Множимое и множитель обозначаютсяв -1-1А(х)аха;х и В(х)ах Ь;х (1)-О ах 0где Р - характеристика;и - степень расширения поля.Тогда произведение имеет вид А(х)В(х)= х )а;х ВСх =(г)а х В(х РПроизведение хВ(х) может быть представлено в виде, Ь,х (3) 1=0В регистрах 1 записаны произведе" ния базисных элементов на примитивный элемент, т.е, элементы ХР " (=0,1и), выходы которых соединены с 3-й группой входов блоков 2 умножения, куда подается величина)+Х . Содержимое регистров меняется при смене представления элементов поля. Компоненты элементов поля, поступающие на первую группу входов блока 2 умножения, умножаются на элементах И 6 на Х " , в результате чего получают члены произведения (3), которые суммируются в сумматорах 7 и в соответствии с (3) на выходе бло-. ка 2 формируются произведения, поступающие на вход элемента на элементы ХНа первую группу входов параллель" ного устройства подается множитель А(х), а на вторую - множитель В(х). В связи с приведенным сначала по пер. вой группе входов на первый блок 2 подана величина В(х), на второй блок 2 - 1 В(х) , а на п-й блок 2 -Р-а -а 1В(х)Д , На выходе первого блока 2 формируется ХаВ (х), на выходе вто 1383338рого блока 2 - Х В (х)1 , на выхо де и-го блока 2 - Х 1 В(х)1 . В блоках 3 формирования частичных произведений полученные величины умно 5 жают на соответствующие разряды множителя А(х). Полученные произведения с выхода схем умножения блоков формирования частичных произведений подаются на блоки 5 суммирования. 1 ОПараллельное устройство для умножения в конечных полях по сравнению с известным позволяет производить умножение элементов поля Галуа СГ(Р ). представленных в нормальном базисе, 15 что существенно упрощает декодирующее устройство с исправлением ошибок. Формула изобретения201. Параллельное устройство для умножения в конечных полях, содержащее и блоков формирования частичньвс произведений и и блоков суммирования, причем каждый блок суммирования со держит и входных шин, каждая иэ которьпс содержит Рцепей, а выходные шины блоков суммирования являются выходом параллельного устройства дЛя умножения в конечных полях, где Р и 30 и - соответственно характеристика и размерность поля Галуа СР(Р"), о тл и ч а ю щ е е с я тем, что, с целью расширения области применения за счет возможности умножения элементов поля Галуа СР (Р ), представ 35 ленных в нормальном базисе, в него введены и регистров и п блоков умножения на примитивный элемент, причем и входных шин первой группы пер .вого блока умножения на примитивный элемент соединены соответственно с первой группой информационных входов устройства, а и входных шнн первойгруппы каждого блока умножения напримитивный элемент, начиная с второго, соединены с первой группой информационных входов устройства с циклическим сдвигом на один разряд всторону старших разрядов, группы свторой по (и+1)-ную входных шин иблоков умножения на примитивный элемент соединены соответственно с ивыходами каждого из и регистров, каждый информационный вход ьторой группы устройства соединен с первыми входами п умножителей соответствующегоблока формирования частичных произведений, вторые входы которых соединены с выходами соответствующихблоков умножения на примитивный элемент, -й выход 3-го блока формирования частичных произведений соединенс 3-.м входом 1 с-го блока суммирования (=1,п; 3=1п; 1 с=+3-1при д+1 6 и+1; 1 с=+3-ипри д+3и+1). 2. Устройство по п,1, о т л и - ч а ю щ е е с я тем, что блок умножения на примитивный элемент, содержащий и"групп по и элементов И и и сумматоров по модулю Р, причем каждая из входных шин первой группы. блока соединена с первыми входами и элементов И соответствующей группы, вторые входы которых являются группами входных шин от второй до (и+1)-й блока, выход -го элемента И 3-й группы (д=1п,1=1п) соединен с 3-м входом 1 с-го сумматора по модулю Р (1 с=+3-1 при д+ и+1; 1 с= =+3-ппри д+3 и+1), выходы сумматоров по модулю Р являются выходами блока.1383338 Составитель В,Гусеведактор Н.Бобкова Техред Л.Олийнык Корректор М.Демчи 7 П ак ое итета СССР рытии я наб., д. Производс твенно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 1297/47 Тира ВНИИПИ Государ по делам из 13035, Москва венного коретений иЖ, Рауш