Устройство для умножения элементов конечных полей Советский патент 1984 года по МПК G06F7/52 

и выход старшего разряда регистра образующего многочлена соединены соответственно с вторыми входами элементов И ()-й группы, выходы которых являются старшими выходами устройства, где 1«1,2,..., (т-1): j 1, 2,... ,(m-1e), Р Т,. ...т, m - максимальная размерность двоичного представления сомножителей, /It - минимальная размерность двоичного представлеиия ссшкокителей).

2, Устройство по п.1, о т л и ч аю щ е е с я тем, что блок матричного преобразования содержит две группы злементов И по (т-1) элементу в первой группе и () элементу во второй группе, элемент ИЛИ, группу из (т-1) сумматоров по модулю два, причем выходы сумматора группы являются (т-1) старшими выходами блока матричного преобразования, первые .

входы сумматоров группы соединены соответственно с выходами элементов И первой группы, первые входы которых являются первой группой управля1ощих входов блока,, вторые входы сумматоров группы соединены соответственно с входами блока матричного преобразования со смещением на один в сторону младщих разрядов, входы старших (tn-k+1) разрядов блока матричного преобразования соединены с пер.вьми входами злементов И второй груп пы, вторые входы которых являются второй группой управляющих входов блока матричного преобразования, а выходы соединены с соответствую1цими входами элемента ИЛИ, выход которого подключен к вторым входам элементов И первой группы и является младшим выКодом блока матричного преобразования.

1. УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЭЛЕМЕНТОВ КОНЕЧНЫХ ПОЛЕЙ, содержащее два.т -разрядных регистра сомножителей, блок многовходовых сумматоров, m групп элементов И, (т-1) блоков матричного преобразования, причем входы регистров сомножителей являются входами соответствующих сомножителей устройства, первые входы элементов И в каждой группе объединены и соединены с соответствующим выходом регистра первого сомножителя, выходы регистра второго сомножителя соединены с вторыми входами, соответ.ствующих элементов И первой группы, входы первого блока матричного преобразования соединены с соответствующими выходами регистра второго сомножителя, выходы -го блока матричного преобразования соединены с вторыми входами соответствующих элементов И (+1)-й группы и соответствующими входами (i+1)-ro блока матричного преобразования, выход р-го элемента И |-й группы соединен с -м входом р-го многовходово- го сумматора блока, выходы К младших многовходовых сумматорюв являются младшими выходами устройства, о т -л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения возможности изменения образующего многочлена и ра:зрядности двоичного представления элементов поля, оно содержит (m-k) двухвходовых сумматоров по модул два, (т-1) элементов ИЛИ, tn-разрядный регистр образующего многочлена, (т+О-ую группу из (n-k) элементов И, причем вход задания режима рабочы устройства соединен с входом регистра образующего многочлена, выходы которого с первого по (т-1)-и соединены с соответствующими управляющими входами первой группы каждого блока матричного преобразования, (Л выход т-го разряда регистра образующего многочлена соедтаен с первыми входами (m-1t)-x элемента ШШ и сумматора по модулю два, с первым § управляюнщм входом второй группы каждого блока матричного преобразования, управляющие входы второй группы с ю второго по (т-Н+О-й которого соеди4ib нены соответственно с выходами суммаN9 торов по модулю два с первого по (т-Х)-й, выходы регистра образующего ;о многочлена с k-ro по (т-1)-и подсое-и динены к перв входам элементов ИЛИ соответственно с первого по (т-1«-1)-й и второму входу (m-lc)-oro элемента ИЛИ, выход j-ro элемента ИЛИ соединен с первым входом j-ro сумматора по модулю два и с вторьми входами (j-O-x элемента ШШ н-сумматора по модулю два, первые входы элементов И ()--й группы соединены с выходами соответствующих старших многовходовых сзгмматоров блока, выходы элементов ИЛИ с второго по (m-k)-и

Изобретение относится к вычислительной технике и может быть примен но при построении специализированны вычислителей для кодирования и деко дирования корректирующих ошибки кодов. Известно устройство для умножения злементов койечного поля, содер жащее два регистра сомножителей, группы элементов И, группы элементо ИЛИ, регистр адреса, накапливающий сумматор и блок управления 13Недостатком данного устройства являются низкие функциональные возможности, обусловленные умножением злементов только одного поля. Наиболее близким к изобретению по технической сущности является устройство для умножения злементов конечных полей, содержащее два регистра сомнпжителей, входы которых являются входами первого и второго сомножителей устройства, ч многовходовых сумматоров, выходы которых являются выходами результата устройства, группы элементов И, первые входы которых в каждой группе объединены и подключены к соответствующему выходу регистра первого сомножителя, а выходы регистра второго сомножителя соединены с вторыми входами соответствующих элементов И первой группы, блоки матричного преобразователя, входы первого из которых соединены с соответствующими входами регистра второго сомножителя , а выходы i-го блока матричного преобразования соединены с вторыми входами соответствующих элементов И (1Ч-1)-й группы и соответствую-, щими входами (i+l)-ro блока матричного преобразования, выходы одноименных элементов И каждой группы подключены к соответствзтощим входам одноименного многовходового сумматора, блок матричного преобразования содержит сумматоры по модулю два, причем в разрядах, соответствующих ненулевым значениям коэффициентов образующего многочлена поля, входы блока матричного преобразования подключены к первым входам сумматоров по модулю два, вторые входы которых соединены с входом старшего разряда и с выходом младшего разряда блока, в разрядах, соответствующих нулевым значениям коэффициентов многочлена поля, входы блока соединены с его выходами со сдвигом на один разряд в сторону старших разрядов Г 20. Недостатком данного устройства является выполнение функций с элеме тами только одного конечного поля при фиксированной разрядности двоичного представлейия элементов. Целью изобретения является расши р.ение функциональных возможностей устройства за счет обеспечения возможност изменения образующего многочлена и разрядности двоичного пре ставления элементов конечного поля. Поставленная цель достигается устройство для умножения элементов конечных полей, содержа- . щее два т-раарядных регистра сомног жителей, блок многовходовых сумматоров, m групп элементов И, (т-1) блоков матричного преобразования, причем входы регистров сомножителей являются входами соответствующих сомножителей устройства, первые входы элементов И в каждой группе объединены и соединены с соответствующим выходом регистра первого сомножителя, выходы регистра второго сомножителя соединены с вторыми входами соответствующих элементов И первой группы, входы первого блока матричного преобразования соединены с соответствующими выходами регистра второго сомножителя, вы- . ходы i-rp блока матричного преобразования соединены с вторыми входами соответствующих элементов И ()-й группы и с соответствующими входами (i+1)- то блока матричного преобразования, выход р-го И -й группы соединен с -м вхоДом р-го многовходового сумматора блока, выходы К младших многовходо- 8ЫХ сумматоров являются младшими выходами устройства, содержит (т-1) двухвходовых сумматоров по.л одулю два, (m-k) элементов ИЛИ, т-разрядны регистр образующего многочлена,(щ+.1) - группу из (in-t:) элементов И, причем вход задания режима работы устройст ва соединен с входом регистра образ ющего многочлена, выходы которого с первого по (т-Т)-и соединены с соот ветствующими управляющими входами первой группы каждого блока матричного преобразования, выход п-го разряда регистра образующего многочлена соединен с первыми входами {m-k)-x элемента ИЛИ и сумматора по модулю два, с первым управляющим входом второй группы каждого блока матричного преобразования, управляю щие входы второй группы с второго по (т-Ь+О-й которого соединены соответственно с выходами сумматоров по , модулю два с первого по (п1-1с)-й, выходы регистра образующего многочлена ck-ro по (т-1)-й подсоединены к первым входам элементов ИЛИ соответственно с первого по 0 1-К-1)-й и второму входу (m-k)-го элемента ИЛИ, выход j-ro элемента ИЛИ соединен с первым входом j-ro сумматора по модулю два и с вторьми входами (j-l)-x элемента ИЛИ и сумматора помодулю два, первые входы элементов И (т+1)-й группы соединены с выходами соответствукяцих старших многовходовых сумматоров бл6|са, выходы элементов ИЛИ с второго по (m-k)-и и выход старшего разряда регистра образующего многочлена соединены соответственно с вторьми входами элементов И (т+1)-й группы, выходы которых являются старшими выходами устройства, где ,2,. . ,(тп-1); ,2,, ,.,., (tn-i:) ; р, е 1,...т; т, k - максимальная и минимальная размерность двоичного представления сомножятелей соответственно. Кроме того, блок матричного преобразования содержит две группы элементов И по (т-1) элементу в первой группе и (т-k+1) элементу во второй группе, элемент ИЛИ, группу из (т-1) сумматоров по модулю два, выходы сумматоров группы являются (tn-1) старшими выходами блока матричного преобразования, первые входы сумматоров группы соединены соответственно с выходами элементов И первой группы, первые входы которых являются первой группой управляющих входов блока, вторые входы сумматоров группы соединены соответственно с входами блока матричного преобразования со смещением на один в сторону младших разрядов, входы старших (m-k+1) разрядов блока матричного преобразования соединены с первыми входами элементов И второй группы, вторые входы которых являются второй группой управляющих входов блока матричного преобра.зования, а выходы соединены с соответствующими входами элемента ИЛИ, выход которого подключен к вторым входам элементов И первой группы и является младшим выходом блока матричного преобразования. S1 На фиг.1 приведена блок-схема устройства для умножения элементов конечных полей; на фиг.2 - схема блока матричного преобразования. Устройство для умножения элеме ов конечных полей содержит два ,; п-разрядных регистра сомножителей 1 и 2, п -разрядный регистр 3 образующего многочлена поля, блоки 4 матричного преобразования, группы 5 элементов И, блок 6 многовходрвькСумматоров, элементы ИЛИ 7, сумматоры 8 по модулю два группу 9 элементов И. Блок 4 матричного преобразования содержит группу 10 элементов И, группу 11 сумматоров по модулю два, группу 12 элементов И, элемент ИЛИ 13, первую 14 группу управляющих входов, вторую 15 группу управляющи входов. Устройство для умножения элементов конечных полей работает следующим образом. Два сомножителя V(V,V,...,Vn) U(U,U2,...,U), , при , вводятся в регистры 1 и ответственно регистр 2; В регистр образующего многочлена 3 вводится п коэффициентов образующего многочлена (F{x)-1), Многочлен F(x) является неприводимым ДВОИЧН.ЫМ многочленом, определяющим элементы выбранного конечного поля которому принадлежат введенные в регистры 1 и 2 сомножители. Сигналы с выходой регистра 3 непосредственно, а также после преобразования на элементах ИЛИ 7. и сумматорах 8 по модулю два образуют три различных вида управляющих сигналов. Первой группой таких сигналов являются сигналы на выходах с первого по (т-1) и разряд регистра 3, Эти сигналы соответствуют коэффициентам, образующего многочлена .за исключением т-го коэффициента, когда ncpfi, и поступают через первые группы управляющих входов 14 на входы группы 10 элементов И каждого блока матричного преобразования. На вькодах элементов ИЛИ 7 и на выходе т-го разряда регистра 3 формируются единичные сигналы на тех выходах, которые соответствуют п-му и меньшим разрядам, и нулевые сигналы для других разрядов. Единичные сигналы нат-м выходе регистра 3 и выходах элементов ИЛИ 7, соответствующих разрядам от ()-го до (тп-1)-го,поступающие на первые входы элементов И 9, разрешают прохождение на выход устройства сигналов с выходов соответствующих многовходовых сумматоров. При этом выходы многовходовых сумматоров 6, соответствующих разрядам больщим П. отключены от выхода устройства, так как на первые входы соответствующих им элементов И 9 поступают нули. С учетом того, что ыходы многовходовых сумматоров 6, соответствующих младщим разрядам, соединены с выходами устройства непосредственно, обеспечивается такая же разрядность на выходе устройства, что и разрядность образующего многочлена. В группе выходов, состоящей из выхода m-го разряда регистра 3 и выходов всех cyм {aтopoв 8 по модулю два, обеспечивается наличие всегда только одной единицы. Причем единица всегда присутствует на выходе, соответствующем п-му разряду регистра 3, поэтому одиночная единица во второй группе 15 управляющих входов блока матричного преобразования разрешает прохождение только одного входного сигнала (притом в п-м разряде) через элементы И 12 на вход элемента ИЛИ 13 и далее с его выхода на объединенные входы группы элементов И 10 и на выход младшего разряда блока 4;. Поданные на другие входы элементов И 10 сигналы по управляющей группе входов 14, соответствующие -коэффициентам образующего многочлена конечного поля, разрешают прохождение входного сягнала блока 4 в п-м разряде через те элементы И 10, которым соответствуют ненулевые коэффициенты образующего многочлена, на первые входы соответствующих сумматоров по модулю два 11. Сигнал с входа i-го.разряда блока 4 проходит на (1Ч-1)-й выход блока 4 без изменения, если соответствующий ему :i-й коэффициент многочлена (F{x)-1) нулевой, и в виде суммы по модулю два с сигналом с выхода элемента ИЛИ 13, совпадающим с сигналом в п-м входном разряде. .I Так как блоки матричного преобразования 4 соединены друг с другом

последовательно, то на выходе i-ro блока матричного преобразования 4 присутствуют сигналы, соответствующие выражению l/(,+f ,.

. при ц1.п.

Сигналы с выходов всех т разрядов регистра 2 и блоков 4 матричного преобразования проходят на входы многовходовьрс сумматоров 6 лишь через те блоки 5 элементов И, в которых на вторые объединенные входы элементов И подается единичный сигМал с вькода соответствующего регисра первого сомножителя 1. При этом

при п меньшемш на последние (m-n) блоков элементов И 5 с выходов регистра 1 .всегда поступают нули, и поэтому сигналы с выходов матричных преобразователей 4 на входы сумматоров 6 не проходят. Таким образом, в п первых многовходовых сумматорах

получается сумма сигналов с выходов первых п разрядов тех из (1-1) блоков матричного преобразования 4, а также и регистра 2, которьм соответствуют единичные сигналы на разрядных выходах регистра первого сомножителя 1, являющаяся результатом перемножения сомножителей.

Умножение производится за один такт работы устройства.

Расширение функциональных возможностей однотактного устройства для умножения элементов конечных полей позволяет упростить по сравнению с известным устройством построение универсального вычислительного средства вьшолнения вычислений в различных конечных полях, например дпя кодирования и декодирования различных блоковых корректирующие ошибки кодов.

ITT

/4

Pus.2