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

 

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)-и

..SU„„1124 91

СОЮЗ СОВЕТСНИХ

Р.И

РЕСПУБЛИН з<д> С 06 F 7/52

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬПЧФ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ н датоИМОМЮ СвидктеЛьСтВ З

i. (21) 3615200/24-24 (22) 06.07.83 (46) 15 ° 11.84. Бюл. У 42 (72) Ю.В.Суликов (53) 621.325(088.8) (56) 1. Авторское свидетельство СССР

Ф 959077, кл. G 06 Р 7/68, 1980.

2. Авторское свидетельство СССР

У 1013950, кл. G 06 F 7/52, 1982 (прототип). (54) (57) 1. УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ

ЭЛЕМЕНТОВ КОНЕЧНЫХ ПОЛЕЙ, содержащее два,rn -разрядных регистра сомножителей, блок многовходовых сумматоров, m групп элементов И," (m-1) блоков матричного преобразовании, причем входы регистров сомножителей являются входами соответствующих сомножителей устройства, первые входы элементов И в каждой группе обьедине. ны и соединены с соответствуюшим выходом регистра первого сомножителя, выходы регистра второго сомножителя соединены с вторыми входами соответствующих элементов И первой группы, входы первого блока матричного преобразования соединены с соответствующими выходами регистра вто. рого сомножителя, выходы i-го блока матричного преобразования соединены с вторыми входами соответствующих элементов И (1+1)-й группы и соответствующими входами (1+1)-ro блока матричного преобразования, выход р-ro элемента И 3-й группы соединен с -м входом р-ro многовходового сумматора блока, выходы К младших многовходовых сумматоров являются младшими выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет обес.печения возможности изменения образующего многочлена и разрядности двоичного представления элементов поля, оно содержит (m-В) двухвходовых сумматоров по модулю два, (-1c) элементов ИЛИ, tn--разрядный регистр образующего многочлена, (я+1)-ую группу из (m-1с) элементов

И, причем вход задания режима работы устройства соединен с входом регистра образующего многочлена, выходы которого с первого по (m-1)-й соединены с -соответствующими управФ ляющими входами первой группы каждо- Я го блока матричного преобразования, выход m-ro разряда регистра образующего многочлена соединен с первьаки входами (е-k)-x элемента ИЛИ и сумматора по модулю два, с первым управляющим входом второй группы каж2 дого блока матричного преобразования, управляющие входы второй группы с второго по (щ-1 +1)-й которого соеди- М иены соответственно с выходами сумма- фЬ торов по модулю два с первого по (Я (m-3c)-й, выходы регистра образующего многочлена с %-ro по (в-1)-й подсое--: gaea динены к первьм входам элементов ИЛИ соответственно с первого по (пт-k-1)-й и второму входу (rn-Ì)-ого элемента

ИЛИ, выход )-го элемента ИЛИ соединен с первым входом j-ro сумматора ф» по модулю два и с вторьии входами () -13-z элемента ИЛИ и=сумматора по модулю два, первые входы элементов

И (вФ1) и группы соединены с выходами соответствующих старших многовходовых сумматоров блока, выходы эле ментов ИЛИ с второго по (в-%)-й

1124291

30 и выход старшего разряда регистра образующего многочлена соединены соответственно с вторыми входами элементов И (в+1)-й группы, выходы которых являются старшими выходами устройства, где i, 1,2,...,(ю-1): j =1, 2,...,(m-1с), p, t *1,...,ю, в — максимальная размерность двоичного представления сомножителей, if< — минимальная размерность двоичного представления сомножителей).

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

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

Известно устройство для умножения элементов конечного поля, содержащее два регистра сомножителей, группы элементов И, группы элементов

ИЛИ, регистр адреса, накапливающий сумматор и блок управления (1 )..

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

Наиболее близким к изобретению по технической сущности является устройство для умножения элементов конечных полей, содержащее два регистра сомножителей, входы которых являются входами первого и второго сомножителей устройства, «р. многовходовых сумматоров, выходы которых являются выходами результата устройства, группы элементов И, первые входы которых в каждой группе объединены и подключены к соответствующему выходу регистра первого сомножителя, а выходы регистра второвходы сумматоров группы соединены соответственно с выходами элементов

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

5 которых соединены с соответствующими входами регистра второго сомножителя, а выходы i-ro блока матричного преобразования соединены с вторыми входами соответствующих элемен1О тов И (i+1)-й группы и соответствующими входами (i+1)-го блока матричного преобразования, выходы одноименных элементов И каждой группы подключены к соответствующим входам од15 ноименного многовходового сумматора, блок матричного преобразования содержит сумматоры по модулю два, причем в разрядах, соответствующих ненулевым значениям коэффициентов образующего многочлена поля, входы блока матричного преобразования подключены к первым входам сумматоров по модулю два, вторые входы которых соединены с входом старшего разряда и с выходом младшего разряда блока, в разрядах, соответствующих нулевым значениям коэффициентов многочлена поля, входы блока соединены с его выходами со сдвигом на один разряд в сторону старших разрядов Р2 3.

1124291

Недостатком данного устройства является выполнение функций с элементами только одного конечного поля при фиксированной разрядности двоичного представления элементов.

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

Поставленная цель достигается тем, что устройство для умножения элементов конечных полей, содержа- . щее два п -разрядных регистра сомно15 жителей, блок многовходовых сумматоров, н групп элементов И, (rn-1) блоков матричного преобразования, причем входы регистров сомножителей являются входами соответствующих сомножителей устройства. первые входы элементов И в каждой группе объединены и соединены с соответствующим выходом регистра первого сомножителя, выходы регистра второго сомножителя соединены с вторыми входами соответствующих элементов

И первой группы, входы первого блока матричного преобразования соединены с соответствующими выходами регистра второго сомножителя, вы30 ходы j-го блока матричного преобразования соединены с вторыми входами соответствующих элементов И (+1)-й группы и с соответствующими входами (i+1)- го блока матричного преобразования, выход р -го элемента

И 0 -й группы соединен с -м вхо дом р-го многовходового сумматора блока, выходы К младших многовходоВык сумматоров являются младшими выходами устройства, содержит (rn-%) двухвходовых сумматоров по,.модулю два, (m-k) элементов ИЛИ, m-разрядный регистр образуюшего многочлена,(ш+1) ю

- группу из (m-k) элементов И, причем 45 вход задания режима работы устройства соединен с входом регистра образующего многочлена, выходы которого с первого no (rn-1)-й соединены с соответствующими управляющими входами 50 пефвой группы каждого блока матричного преобразования, выход М-го разряда регистра образующего многочлена соединен с первыми входами

{tn-Ì)-х элемента ИПИ и сумматора 55 по модулю два, с первым управляющим входом второй группы каждого блока матричного преобразования, управляющие входы второй группы с второго по (m-k+1)-й которого соединены соответственно с выходами сумматоров по, модулю два с первого по (я1-%)-й, выходы регистра образующего многог члена ck-го по (m-1) -й подсоединены к первым входам элементов ИЛИ соответственно с первого по 9 k-1)-й и второму входу (rn-к)-го элемента

ИЛИ, выход .j-го элемента ИЛИ соединен с первым входом j-ro сумматора по модулю два и с вторыми входами (-1)-х элемента ИЛИ и сумматора по . г модулю два, первые входы элементов

И (ш+1)-й группы соединены с выходами соответствующих старших многовходовых сумматоров блока, выходы элементов ИЛИ с второго по (tn-k)-й и выход старшего разряда регистра образующего многочлена соединены соответственно с вторыми входами элементов И (в+1)-й группы, выходы которых являются старшими выходами, устройства, где 1=1,2,...,(m-1); j=1,2, ° ° ., (tn-%); р, Р =1, ° . 4а, п, г — мак« симальная и минимальная размерность двоичного представления сомножите- . лей соответственно.

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

1124291

На фиг.1 приведена блок-схема устройства для умножения элементов . конечных полей; на фиг.2 — схема блока матричного преобразования.

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

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

6 многовходовых сумматоров, элементы ИЛИ 7, сумматоры 8 по модулю два, группу 9 элементов И.

Блок 4 матричного преобразования содержит группу 10 элементов И, группу 11 сумматоров по модулю два, группу 12 элементов И, элемент ИЛИ

13, первую 14 группу управляющих входов, вторую 15 группу управляющих входов.

Устройство для умножения элементов конечных полей работает следую-. щим образом.

Два сомножителя V=(V>,V>,.,Чп), U=(U„,U<,...,U„), k nп, вводятся в регистры 1 и соответственно регистр 2

В регистр образующего многочлена 3 вводится и коэффициентов образующего многочлена (F(x)-1). Йногочлен Р(х) является неприводимым двоичным многочленом, определяющим элементы выбранного конечного поля, которому принадлежат введенные в регистры 1 и 2 сомножители.

Сигналы с выходов регистра 3 непосредственно, а также после преобразования на элементах ИЛИ 7.и сумматорах 8 по модулю два образуют три различных вида управляющих сигналов. Первой группой таких сигналов являются сигналы на выходах с первого по (tn-1) и разряд регистра 3. Эти сигналы соответствуют коэффициентам образующего многочлена за исключением tn-го коэффициента, . когда n m, и поступают через первые группы управляющих входов 14 на входы группы 10 элементов И каждого блока матричного преобразования. На выходах элементов ИЛИ 7 и на выходе m-го разряда регистра

3 формируются единичные сигналы на тех выходах, которые соответствуют .и -му и меньшим разрядам, и нулевые сигналы для других разрядов.

Единичные сигналы нам-м выходе ре5

45 гистра 3 и выходах элементов ИЛИ 7, соответствующих разрядам от (1<+ 1)-ro до (в-1)-го,поступающие на первые входы элементов И 9, разрешают прохождение на выход устройства сигналов с выходов соответствующих многовходовых сумматоров. При этом выходы многовходовых сумматоров 6, соответствующих разрядам большим tl отключены от выхода устройства, так как на первые входы соответствующих им элементов И 9 поступают нули. С учетом того, что выходы многовходовых сумматоров 6; соответствующих % младшим разрядам, соединены с выходами устройства непосредственно, обеспечивается такая же разрядность на выходе устройства, что и разрядность образующего многочлена.

В группе выходов, состоящей из выхода rn --ro разряда регистра 3 и выходов всех сумматоров 8 по модулю два, обеспечивается наличие всегда только однои единицы. Причем единица всегда присутствует на выходе, соответствующем и-му разряду регистра 3, поэтому одиночная единица во второй группе 15 управляющих входов блока матричного преобразования разрешает прохождение только одного входного сигнала (притом в и-и раз— ряде) через элементы И 12 на вход элемента ИЛИ 13 и далее с его выхода на объединенные входы группы элементов И 10 и на выход младшего разряда блока 4. Поданные на другие входы элементов И 10 сигналы по управляющей группе входов 14, соответствующие .коэффициентам образу— ющего многочлена конечного поля, разрешают прохождение входного сигнала блока 4 в п-м разряде через те элементы И 10, которым соответствуют ненулевые коэффициенты образующего многочлена, на первые входы соответствующих сумматоров по модулю два 11. Сигнал с входа 1-го разряда блока 4 проходит на (l+1)-й выход блока 4 без изменения, если соответствующий ему j-й коэффициент многочлена (Г(х)-1) нулевой, и в виде суммы по модулю два с сигналом с выхода элемента ИЛИ 13, совпа55 дающим с сигналом в и --м входном разряде.

Так как блоки матричного преобра зования 4 соединены друг с другом

1124291

15 последовательно, то на выходе -го блока матричного преобразования 4 присутствуют сигналы, соответствую.Ai 1-t 1-1 i-1 щие выражению г -(U„,U„+f> U

U". +f „0,1, при ИЫп. 5

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

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

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

1124291

Составитель А.Клюев

Редактор Н.Швццкая Техред М.Надь Корректор М.Pозман..4

Заказ 8280/37 Тираж 698 Подписное

: -ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППН "Патент", г. Ужгород, ул. Проектная, 4