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

Изобретение относится к вычислительной технике и может быть применено при построении специализирован ных вычислителей для кодирования и декодирования кодов, корректирующих ошибки. Известно устройство для умножения элементов конечного поля, содержащее кольцевой регистр, регистр с обратными связями, блок элементов И и выходной накопительный регистр Cl1Недостатком этого устройства является низкое быстродействие. Наиболее близким к предлагаемому является устройство для быстрого умножения элементов конечных полей, содержащее два регистра, многовходо вые сум латоры, выходы которых являются выходами устройства, группы двухвходовых элементов И, причем первые входы каждой группы объединены и подключены к соответствующим выходам первого регистра,/ каждый выход второго регистра подключен к соответствукнцим по порядку объединенным вторым входам групп элемен тов И выходы которых подключены через комбинаторную схему ко входам многовходовых сумматоров 2. Недостатком известного устройств является значительная сложность, определяемая сложностью сумматоров с большим числом входов. Целью изобретения является упрощение устройства за счет уменьшения количества многовходовых сумматоров Для достижения поставленной цели устройство для умножения элементов .конечных полей, содержащее два реги ра сомножителей, входы которых яв.ляются входами первого и второго сомножителей устройства, многовходо вые сумматоры, выходы которых являются выходами результата устройства группы элементов И, первые входы которых в каждой группе объединены и подключены к соответствующему выходу регистра первого сомножителя а выходы регистра в горого сомножителя соединены со вторыми входами соот ветствующих элементов И первой группы, содержит блоки матричного преобразования, входы первого из которых соединены с соответствующими выходами регистра второго сомножителя, а выходы -t-го блока матричного преобразования соединены со вторыми входами соответствующих элементов И i+l)-tt группы и соответствующими входами Ci+l;-го-блока матричного . преобразования, выходы одноименных элементов И каждой группы подключены к соответствующим входам одноименног многовходового сумматора. Кроме того, блок матричного преобразования содержит сумматорь по мо дулю два, причем в разрядах, соответствующих ненулевым значениям коэффициентов многочлена поля, входы блока матричного преобразования подключены к первым входам сумматоров по модулю два, вторые входы которых соединены со входом старшего разряда и с выходом младшего разряда блока, а в разрядах, соответствуклцих . нулевым значениям коэффициентов многочлена поля, входы блока соединены с его выходами со сдвигом на один разряд в сторону стараих разрядов. На фиг.1 изображена схема устройCTBaj на фиг,2 - схема блока матричного преобразования. Устройство содержит регистр 1 первого сомножителя, элементы И 2, объединенные в группы 3, многовходовые сумматоры 4, регистр 5 второго сомножителя, блоки б матричного преобразования, выходы 7 устройства, входы 8 и 9 первого и второго сомножителей сумматоры 10 по модулю два. Устройстве работает следующим образом. Сигналы с выхода регистра 5 второго сомножителя поступают на последовательную цепочку блоков 6 матричного преобразования и на первые входы элементов И 2 первой группы 3, причем первый разряд регистра 5 второго сомножителя соединен со входом первого элемента И 2, второй разряд со входом второго элемента И и т.д. Для образования сдвигов числа, хра- . нимого в регистре 5, используются блоки, б матричного преобразования. Для получения последующего сдвига используется результат предыдущего преобразования. При этом произведение двух сомножителей U (P-(.f, ,iVi.-.,Vn) являющихся элементами конечного поля, определяется как r--U,22....7v,.), где суммирование проводится ,по модулю два умножение - как логическое умножение; М - Матрица преобразования. Даннаяматрица задается выбранным неприводимым многочленом, определяющим элементы конечного поля. Преобразование реализуется путем циклического сдвига всех разрядов с суммированием по модулю два старшего разряда с разрядами, определяемыми ненулевыми коэффициентами многочлена поля. При.выборе прими-, тивного ,многочлена поля вида для реализации блока б матричного преобразования требуется лишь один двухвходовой сумматор по модулю два. Выходы блоков ,б матричного преобразования поразрядно подключаютсяко вторым входам элементов И 2,

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

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

Такое построение устройства требует для реализации многовходовых сумматоров и блоков матричного преобразования наличия максимум ( и+1) двухвходовых сумматоров по модулю-два. В то. же время количество двухвходовых cyw- маторов для реализации многовходовых

0 сумматоров в известном устройстве мо жет достичь величины (и-й) . При определенном выборе многочлена |F (х) эти же величины могут быть, уменьшены до величины и -1) в предлагаемом

5 устройстве и до 1,5( известном.

При и образующем многочлене F(K)-X 1-/. для реализации предлагаемого устройства требуется 157 элементарных функциональных элементов (77 двухвхэдовых сумматоров по модулю

0 два, 64 двухвходовых схем И и 16 триг- repoBJ, для известного - 221 элемент 1141 двухвходовых сумматоров по модулю два, 64 двухвходовых схем И и 16 5 .триггеров/ .

фиг 2

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