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

 

Г. УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЭЛЕМЕНТОВ КОНЕЧНЫХ ПОЛЕЙ, содержащее два регистра сомножителей, входы которых являются входами первого .и второго сомножителей устройства, мн.оговходовые сумматоры, выходы которых являются выходами результата устройства, группы элементов И, первые входы которых в каждой группе объединены и подключены к соответствующему выходу регистра первого «Умножителя , а выходы регистра второго сомножителя соединены с вторыми входами соответствуквдих элементов И первой группы, отличающеес я тем, что,с целью-упрощения устройства путем уменьшения количест ва многовходовых сумматоров, устройство содержит блоки матричного преобразования , входы первого из которых соединены с соответствующими выходами регистра второго сомножителя , а выходы 1-гр блока матричного преобразования соединены с вторыми вхрдами соответствукицих элементов И ().+1)-й группы и соответствующими входами ( блока матричного преобразования, выходы одноименных элементов И каждой группы подключены к соответствующим входам Одноименного многовходового сумматора. 2. Устройство ПОП.1, отличающееся тем, что блок матричного преобразования содержит сумматоры по модулю два, причем в.разрядах , соответствующих ненулевым О) значениям коэффициентов многочлена поля, входы блока матричного пре-. образования .подключены к первым входам сумматоров по модулю два, вторые вхрды которых соединены с входом старшего разряда ,и с выходом младшего разряда блока, а в разрядах , соответствующих нулевым значениям коэффициентов многочлена поля, входы блока соединены с его выходами со сдвигом на один разряд в сто00 QD О1 рону старших разрядов.

СОЮЗ COBETCHHX

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

y(5)) G 06 F 7/52

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

OllHCAHHE ИЗОБРЕТЕНИЯ

К АВТОРСКОМ .Ф СВИДЕТЕЛЬСТВУ

1 .г. ! (21) 3381784/18-24 (22) 12.01.82 (46) 23.04.83. Бюл.915 (72) Ю.В. Сулимов и В.Н. Стальнов (53) 681.325(088.8) (56) 1. Блох Э.Л., Зяблов В.В. Обобщенные каскадные коды. М., "Связь", 1976, с.99

2. Bartee Th.Ñ., Schneider О.!.

Computation uith F inite F ieRds In-

ll

formation and .Control, vol.6 92, Jane,1963, fig.3, р.85 (прототип). (54)(57) 1. УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЭЛЕМЕНТОВ КОНЕЧНЫХ ПОЛЕЙ, содержащее два регистра сомножителей, входы которых являются входами первого и второго сомножителей устройства, многовходовые сумматоры, выходы которых являются выходами результата устройства, группы элементов И, первые входы которых в каждой группе объединены и подключены к соответствующему выходу регистра первого сомножителя, а выходы регистра второго сомножителя соединены с вторыми входами соответствующих элементов И первой группы, о т л и ч а ю щ е ес я тем, что, с целью .Упрощении . устройства путем уменьшения количества многовходовых сумматоров, устрой„„SU„„1013950 A ство содержит блоки матричного преобразования, входы йервого из которых соединены с соответствующими выходами регистра второго сомножителя, а выходы i --ro блока матричного преобразования соединены с вторыми входами соответствующих элементов

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

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

Ю

Ф входом старшего разряда .и с выходом младшего разряда блока, а в разрядах, соответствующих нулевым значениям коэффициентов многочлеиа поля, (" входы блока соединены cего выходами сО сдВиГОм на Один разряд В. стО рону старших разрядов. Яф

1013950

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

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

Недостатком этого устройства является низкое быстродействие.

Наиболее близким к предлагаемому является устройство для быстрого умножения элементов конечных палей, содержащее два регистра, многовходовые сумматоры, выходы которых являются выходами устройства, группы двухвходовых элементов И, причем 20 первые входы каждой группы объединены и подключены к соответствующими| выходам первого регистра,, каждый выход второго регистра подключен к соответствующим по порядку объе- 25 диненным вторым входам групп элементов И„ выходы которых подключены через комбинаторную схему ко входам многовходовых сумматоров (2 1.

Недостатком известного устройства 30 является значительная сложность, определяемая сложностью сумматоров с большим числом входов.

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

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

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

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

Устройство содержит регистр 1 первого сомножителя, элементы И 2, объединенные в группы 3, многовходовые сумматоры 4, регистр 5 второго сомножителя, блоки 6 матричного преобразования, выходы 7 устройства, входы

8 и 9 первого и второго сомножителей сумматоры 10 по модулю два.

Устройство работает следующим образом.

Сигналы с выхода регистра 5 второго сомножителя поступают на последовательную цепочку блоков 6 матричного преобразования и на первые входы элементов И 2 первой группы 3, причем первый разряд регистра 5 второго сомножителя соединен со входом первого элемента И 2, второй разряд— со входом второго элемента И и т.Z(, Для образования сдвигов числа, хра- . нимого в регистре 5, используются блоки, 6 матричного преобразования, Для получения последующего сдвига используется результат предыдущего преобразования. При этом произведение двух сомножителей 0=(О,Ц,..Я,) иV=(VqVz.-, 4) являющихся элементами конечного поля, определяется как и =(2,2g.," 2и1"- Е V;(g М" "), где суммирование проводится .по модулю два, умножение — как логическое умножение; М вЂ” матрица преобразования.

Данная матрица задается выбранным неприводимым многочленом, определяющим элементы конечного поля. .Преобразование реализуется путем циклического сдвига всех разрядов с суммированием по модулю два старшего разряда.с разрядами, определяемыми ненулевыми коэффициентами многочлена поля. При .выборе прими-fl q тивного многочлена поля вида Q=X+X q для реализации блока б матричного преобразования требуется лишь один двухвходовой сумматор по модулю два.

Выходы блоков,6 матричного преабразования поразрядно подключаются. ко вторым входам элементов И 2, 1013950

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

И 2 в группах 3, сигнал на втором выходе — результатом сигналов с вы- щ ходов вторых элементов И 2 в группах

3 и т.д. Таким образом, с выходов многовходовых сумматоров 4 получаем результат перемножения содержимого регистров сомножителей. Так же как и известное предлагаемое устройство выполняет. умножение двух сомножителей за один такт.

Такое построение устройства требует для реализации многовходовых сумматоров и блоков матричнбго преобразования наличия максимум (2и -3 и +1) двухвходовых сумматоров по модулю два. В то. же время количество двухвходовых сум-" . маторов для реализации многовходовых сумматоров в известном устройстве может достичь величины (n>-È ) . При определенном выборе многочлена )F (} э>и же величины могут быть. уменьшены до величины (н -1) в предлагаемом устройстве и до 1,5(H)B известном.

При и=8 и образующем многочлене

F(g)=X +Х4+)(X - для реализации предлагаемого устройства требуется 157 элементарных функциональных элементов (77 двухвхздовых сумматоров по модулю . два, 64 двухвходовых схем И и 16 триггеров), для известного - 221 элемент . (141 двухвходовых .сумматоров по модулю два, 64 двухвходовых схем И и 16

;триггеров) .

1013950 . Составитель Н. Захаревич

Редактор Н. Егорова Техред К.Мыцьо Корректор С. Шекмар

Заказ 3006/58 Тираж .704 Подписное

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

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

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