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

(прототип). 24юл. У 4 е свидетельст 06 Р 7/68, 19 свидетельство 06 Р 7/52, 1 ССР2 е ине. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ 19 Т 0 РСОУ Свидетелст(54) (57) 1, УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЭЛЕМЕНТОВ КОНЕЧНЫХ ПОЛЕЙ, содержащее дваю -разрядных регистра сомножителей, блок многовходовых сумматоров, щ групп элементов И," (е) блоков матричного преобразовании, причем входы регистров сомножителей являются входами соответствующих сомножителей устройства, первые входы элементов И в каждои группе обь д ны и соединены с соответствующим выходом регистра первого сомножителя, выходы регистра второго сомножителя соединены с вторыми входами соответствующих элементов И первой группы, входы первого блока матричного преобразования соединены с соответствующими выходами регистра вто рого сомножителя, выходы "го блока матричного преобразования соединены с вторыми входами соответствующих элементов И (1+1)-й группы и соответствующими входами (1+1)-го блока матричного преобразования, выход р-го элемента И -й группы соединен с -м входом р-го многовходового сумматора блока, выходы К младших многовходовых сумматоров являются младшими выходами устройства, о т л и ч а ю щ е е с я тем, что,801124 91 с целью расширения функциональныхвозможностей устройства за счет обес.печения возможности изменения образующего многочлена и разрядности двоичного представления элементов поля, оно содержит (сп-В) двухвходовых сумматоров по модулю два, (ф-%) элементов ИЛИ, в-разрядный регистр образующего многочлена, (в+1)-ую группу из (в-М) элементов И, причем вход задания режима работы устройства соединен с входом регистра образующего многочлена, выходы которого с первого по (в)-й соединены с -соответствующими управР ляющими входами первой группы каждо го блока матричного преобразования, выход в-го разряда регистра образующего многочлена соединен с первьщи входами (е-к)-х элемента ИЛИ и сумматора по модулю два, с первым управляющим входом второй группы каждого блока матричного преобразования, управляющие входы второй группы с ффффф второго по (е+1)-й которого соеди- М иены соответственно с выходами сумма Ь торов по модулю два с первого по Ьф (в-В)-й, выходы регистра образующего многочлена с Й-го по (в)-й подсое- . фаза динены к первьи входам элементов ИЛИ соответственно с первого по Ь-М)-й и второму входу (щ-В)-ого элемента ИЛИ, выход )-го элемента ИЛИ соединен с первым входом 1-го сумматора фр, по модулю два и с вторьии входами (1 -1 Ф-х элемента ИЛИ и=сумматора по модулю два, первые входы элементов И (А%1)"й группы соединены с выходами соответствующих старших многовходовых сумматоров блока, выходы элементов ИЛИ с второго по Ьв-%)-й1124291 30 и выход старшего разряда регистра образующего многочлена соединены соответственно с вторыми входами элементов И (в+1)-й группы, выходы которых являются старшими выходами устройства, где 1,1,2(ю): 3 =1, 2(Фс), р, 1 фф 1 .,ю, щ - максимальная размерность двоичного представления сомножителей, % - минимальная размерность двоичного представления сомножителей).2, Устройство по п,1, о т л и ч а" ю щ е е с я тем, что блок матричного преобразования содержит две группы элементов И по (м) элементу в первой группе и (ь+1) элементу во второй группе, элемент ИЛИ, группу из (щ) сумматоров по модулю два, причем выходы сумматора группы являются Ь) старшими выходами блока матричного преобразования, первые . Изобретение относится к вычислительной технике и может быть применено при построении специализированных вычислителей для кодирования и декодирования корректирующих ошибки кодов.Известно устройство для умножения элементов конечного поля, содержащее два регистра сомножителей, группы элементов И, группы элементов ИЛИ, регистр адреса, накапливающий сумматор и блок управления1Недостатком данного устройства являются низкие функциональные воэможности, обусловленные умножением элементов только одного поля.Наиболее близким к изобретению по технической сущности является устройство для умножения элементов конечных полей, содержащее два регистра сомножителей, входы которых являются входами первого и второгосомножителей устройства, р. многовходовых сумматоров, выходы которых являются выходами результата устройства, группы элементов И, первые входы которых в каждой группе объединеныи подключены к соответствующему выходу регистра первого сомножителя, а выходы регистра второвходы сумматоров группы соединены соответственно с выходами элементовИ первой группы, первые входы которых являются первой группой управля 1 ощих входов блока, вторые входы сумматоров группы соединены соответственно с входами блока матричного преобразования со смещением на один всторону младших разрядов, входы старших 0 я-М+ 1) разрядов блока матричного преобразования соединены с пер,выми входами элементов И второй группы, вторые входы которых являются второй группой управляющих входов блока матричного преобразования, авыходы соединены с соответствующимивходами элемента ИЛИ, выход которогоподключен к вторым входам элементов И первой группы и является младшим выКодом блока матричного преобразования. го сомножителя соединены с вторымивходами соответствующих элементов Ипервой группы, блоки матричногопреобразователя, входы первого иэ 5 которых соединены с соответствующими входами регистра второго сомножителя, а выходы -го блока матричного преобразования соединены с вторыми входами соответствующих элемен О тов И (1+1)-й группы и соответствую- щими входами (1+1)-го блока матричного преобразования, выходы одноименных элементов И каждой группы подключены к соответствующим входам одноименного многовходового сумматора, блок матричного преобразованиясодержит сумматоры по модулю два,причем в разрядах, соответствующихненулевым значениям коэффициентов образующего многочлена поля, входыблока матричного преобразования подключены к первым входам сумматоровпо модулю два, вторые входы которыхсоединены с входом старшего разрядаи с выходом младшего разряда блока,в разрядах, соответствующих нулевымзначениям коэффициентов многочлена поля, входы блока соединены с еговыходами со сдвигом на один разряд в сторону старших разрядов 2 Х40 Недостатком данного устройства является выполнение функций с элементами только одного конечного поля при фиксированной разрядности двоичного представления элементов.Целью изобретения является расши- рение функциональных возможностей устройства за счет обеспечения возможности изменения образующего многочлена и разрядности двоичного представления элементов конечного поля.Поставленная цель достигается тем, что устройство для умножения элементов конечных полей, содержа- . щее два п-разрядных регистра сомно 15 жителей, блок многовходовых сумматоров, н групп элементов И, 6 п) блоков матричного преобразования, причем входы регистров сомножителей являются входами соответствующих сомножителей устройства. первые входы элементов И в каждой группе объединены и соединены с соответствующим выходом регистра первого сомножителя, выходы регистра второго сомножителя соединены с вторыми входами соответствующих элементов И первой группы, входы первого блока матричного преобразования соединены с соответствующими выходами регистра второго сомножителя, вы 30 ходы -го блока матричного преобразования соединены с вторыми входами соответствующих элементов И (+1)-й группы и с соответствующими входами (1+1)- го блока матричного преобразования, выход р -го элементаИ 1 -й группы соединен с -м входом р-го многовходового сумматора блока, выходы К младших многовходовык сумматоров являются младшими выходами устройства, содержит (в-) двухвходовых сумматоров по,.модулю два, (шс) элементов ИЛИ, ш-разрядный РегистР обРазУюшего многочлена,(ш+1) . группу из (ш-к) элементов И, причем 45вход задания режима работы устройства соединен с входом регистра образующего многочлена, выходы которого спервого по (в)-й соединены с соответствующими управляющими входами 50первой группы каждого блока матричного преобразования, выход М-горазряда регистра образующего многочлена соединен с первыми входами(в-М)-х элемента ИПИ и сумматора 55по модулю два, с первым управляющимвходом второй группы каждого блокаматричного преобразования, управляющие входы второй группы с второго по (в+1)-й которого соединены соответственно с выходами сумматоров по, модулю два с первого по Ь 1-%)-й выходы регистра образующего многогочлена с-го по (ш) -й подсоединеныФк первым входам элементов ИЛИ соответственно с первого по М-1)-й и второму входу (е-)-го элемента ИЛИ, выход -го элемента ИЛИ соединен с первым входом -го сумматора по модулю два и с вторыми входами ( -1)-х элемента ИЛИ и сумматора пог модулю два, первые входы элементов И (ш+1)-й группы соединены с выходами соответствующих старших многовходовых сумматоров блока, выходы элементов ИЛИ с второго по (в-М)-й и выход старшего разряда регистра образующего многочлена соединены соответственно с вторыми входами элементов И (в+1)-й группы, выходы которых являются старшими выходами, устройства, где 1 =1,2 (ш); 1=1,2 м(В-%) 3 р 0 =1,.4 а, в, г - максимальная и минимальная размерность двоичного представления сомножите- . лей соответственно.Кроме того, блок матричного преобразования содержит две группы элементов И по (в) элементу в первой группе и(а+1) элементу во второй группе, элемент ИЛИ, группу из (щ) сумматоров по модулю два, выходы сумматоров группы являются (ь) старшими выходами блока матричного преобразования, первые входы сумматоров группы соединены соответственно с выходами элементов И первой группы, первые входы которых являются первой группой управляющих входов блока, вторые входы сумматоров группы соединены соответственно с входами блока матричного преобразования со смещением на один в сторону младших разрядов, входы старших Ь+ 1) разрядов блока матричного преобразования соединены с .первыми входами элементов И второй группы, вторые входы которых являются второй группой управляющих входов бло" ка матричного преобразования, а выходы соединены с соответствующими входами элемента ИЛИ., выход которого подключен к вторым входам элементов И первой группы и является кпадшим выходом блока матричного пре/образования.На фиг.1 приведена блок-схемаустройства для умножения элементов. конечных полей; на фиг.2 - схемаблока матричного преобразования.Устройство для умножения злемердов конечных полей содержит дваЪ-разрядных регистра сомножигелей 1 и 2, в-разрядный регистробразующего многочленаполя, блоки 4 матричного преобразования, группы 5 элементов И, блок6 многовходовых сумматоров, элементы ИЛИ 7, сумматоры 8 по модулю два,группу 9 элементов И,Блок 4 матричного преобразованиясодержит группу 10 элементов И,группу 11 сумматоров по модулю два,группу 12 элементов И, элемент ИЛИ13, первую 14 группу управляющихвходов, вторую 15 группу управляющихвходов.Устройство для умножения элементов конечных полей работает следую-.щим образом.Два сомножителя 7=(7п)П=(Б ПП) , Оп ш 71=01=0при 3 п, вводятся в регистры 1 и соответственно регистр 2В регистр образующего многочлена 3 вводится и коэффициентов образующего многочлена (Р(х)-1). Многочлен Р(х) является неприводимымдвоичным многочленом, определяющимэлементы выбранного конечного поля,которому принадлежат введенные врегистры 1 и 2 сомножители,Сигналы с выходов регистра 3 непосредственно, а также после преобразования на элементах ИЛИ 7,и сумматорах 8 по модулю два образуют три различных вида управляющих сигналов. Первой группой таких сигналов являются сигналы на выходах с первого по (х) й разряд регистра 3. Эти сигналы соответствуют коэффициентам образующего многочлена за исключением в-го коэффициента,.когда нсвти поступают через первые группы управляющих входов 14 на входы группы 10 элементов И каждого блока матричного преобразования. На выходах элементов ИЛИ 7 и на выходе в-го разряда регистра 3 формируются единичные сигналы на тех выходах, которые соответствуют.и -му и меньшим разрядам, и нулевые сигналы для других разрядов. Единичные сигналы на е-м выходе ре 55 дающим с сигналом в п -м входномразряде.Так как блоки матричного преобразования 4 соединены друг с другом 5 10 15 20 25 30 35 ф) 45 гистра 3 и выходах элементов ИЛИ 7, соответствующих разрядам от (1+ 1)-го до Ь)-гопоступающие на первые входы элементов И 9, разрешают прохождение на выход устройства сигналов с выходов соответствующих многовходовых сумматоров. При этом выходы многовходовых сумматоров 6, соответствующих разрядам большим 1 Ъ отключены от выхода устройства, так как на первые входы соответствующих им элементов И 9 поступают нули. С учетом того, что выходы многовходовых сумматоров 6; соответствующих % младшим разрядам, соединены с выходами устройства непосредственно, обеспечивается такая же разрядность на выходе устройства, что и разрядность образующего многочлена.В группе выходов, состоящей из выхода в -го разряда регистра 3 и выходов всех сумматоров 8 по модулю два, обеспечивается наличие всегда только однои единицы. Причем единица всегда присутствует на выходе, соответствующем и-му разряду регистра 3, поэтому одиночная единица во второй группе 15 управляющих входов блока матричного преобразования разрешает прохождение только одного входного сигнала (притом в п-и разряде) через элементы И 12 на вход элемента ИЛИ 13 и далее с его выхода на объединенные входы группы элементов И 10 и на выход младшего разряда блока 4, Поданные на другие входы элементов И 10 сигналы по управляющей группе входов 14, соответствующие коэффициентам образующего многочлена конечного поля, разрешают прохождение входного сигнала блбка 4 в п-м разряде через те элементы И 10, которым соответствуют ненулевые коэффициенты образующего многочлена, на первые входы соответствующих сумматоров по модулю два 11. Сигнал с входа 1-го разряда блока 4 проходит на (1+1)-йвыход блока 4 без изменения, если соответствующий ему 1-й коэффициент многочлена (Р(х)-1) нулевой, и в виде суммы по модулю два с сигналом с выхода элемента ИЛИ 13, совпа15 последовательно, то на выходе 1-го блока матричного преобразования 4 присутствуют сигналы, соответствую.,И 1-1 1-1 1-1 щие выражению Ь -(Бл,0+б 130.+1 01,1, при ИЫп. 5Сигналы с выходов всех щ разрядов регистра 2 и блоков 4 матрично. го преобразования проходят на входы многовходовых сумматоров 6 лишь через те блоки 5 элементов И, в которых на вторые объединенные входы элементов И подается единичный сигнал с выхода соответствующего регистра первого сомножителя 1. При этомъ Гпри и меньшем ш на последние (ш-и) блоков элемейтов И 5 с выходов регистра 1,всегда поступают нули, и поэтому сигналы с выходов матричных преобразователей 4 на входы сумматоров 6 не проходят, Таким образом, 21 в и первых многовходовьи сумматорах получается сумма сигналов с выходов первыхразрядов тех из (-1) блоков матричного преобразования 4, а также и регистра 2, которьи соответствуют единичные сигналы на разрядных выходах регистра первого сомножителя 1, являющаяся результатом перемножения сомножителей.Умножение производится за один такт работы устройства.Расширение функциональных возможностей однотактного устройства дпя умножения элементов конечных полей позволяет упростить по сравнению с известным устройством построение универсального вычислительного сред" ства выполнения вычислений в различных конечных полях, например для кодирования и декодирования различных блоковых корректирующих ошибки кодов,: -ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5