Устройство для умножения полиномов Советский патент 1990 года по МПК G06F17/10 G06F7/544 

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

Цель изобретения - повышение быстродействия устройства,

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

Устройство содержит п регистров 1 коэффициентов, п умножителей 2, п блоков 3 регистров сдвига, коммутатор 4, первый регистр 5, первую и вторую группы суммирующих ячеек 6, второй регистр 7, формирователь 8

импульсов и генератор 9 тактовых импульсов.

Суммирующая ячейка 6 (фиг.2) со- держит схему 10 сравнения, четыре группы элементов ИИ, три коммутатора 12, сумматор 13 по модулю два и

сумматор 14.

Устройство предназначено для умножения полиномов. Полином Р(х) а

ел оо со со со

,-f,

m

а.х 1 задается списком пар, состоящих из нулевого коэффициента и соответствующего ему показателя степени переменнойо

При умножении полинома Р(х) п

и QOO

Z Ь.х

1г.

,„представленного

списком пар

Ь,гч), (bj.r,,).....,,,),

результате получаем полином

к А(х)

Z с,,

|Ч

Т

который представляется списком пар (cf hf) (°2 пг.)««о (ск.пд) ,i,K.

При умножении двух разреженных полиномов, представленных списком пар, находят произведения пар и располагают их по величине показателей степени (по вторым компонентам пар)( объединяя все члены с одинаковыми показателями.

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

Перед началом работы устройства в регистры 1 коэффициентов записываг ются коэффициенты полинома множителя Q(x), в формирователь 8-импульсов - число К е пыг (не показано),где m - порядок полинома множимого;, п - порядок полинома Q(х).

В соответствии с частотой f генератора 9 тактовых импульсов через информационный вход устройства на входы умножителей 2 последовательно поступают коэффициенты первого полинома Р(х), заданные в .виде списка пар ненулевых коэффициентов и соответствующих показателей степеней Пары коэффициентов второго полинома хранятся в регистрах 1 коэффициентов. Каждый из регистров 1 разделен на две чайти, соответствующие разрядам коэффициента и разрядам показателя степени,, В умножителях 2 реализуется умножение пар коэффициентов, т „во каждый умножитель 2 состоит из двухвходового умножителя двух чисел и сумматора. При этом сумматор реализует сложение показателей степеней соответствующих парв Результаты умножения, т.е. пары чисел последовательно записываются в ре вистры 3 в соответствии с частотой генератора 9 тактовых импульсов

На вход формирователя 8 импульсов импульсы поступают с частотой nrf, рде п - порядок полинома множителя; f - тактовая частота поступления коэффициентов полинома множимого, а на выходе появляются импульсы с частотой , где К «nun.

Таким образом, через m тактов работы устройства на управляющий вход коммутатора 4 с выхода формиро- вателя 8 поступает импульс логического О длительностью

«Н-.П- -JL-

0

5

0

5

0

5

0

45

0

5

В результате этого информация с выходов группы сдвигающих регистров 3 поступает через коммутатор 4 на входы регистра 5. На следующем (т+1)-м такте информация записывается в регистр 5 и поступает дальше в группу ячеек 6. На этом же такте с выхода формирователя 8 на управляющий вход коммутатора 4 поступает сигнал логической 1 (начальное состояние)t в результате которого выходы второй группы ячеек 6 соединяются через коммутатор 4 с входами регистра 50

Процесс формирования результирующего полинома А(х), т,е0 процесс расположения пар коэффициентов по величине показателей степени (по вторым компонентам пар) с объединением всех членов с одинаковыми показателями происходит в первой и второй группах суммирующих ячеек 6.

Суммирующая ячейка работает следующим образом.

Схема 10 сравнения осуществляет сравнение показателей степеней двух пар. Если первый показатель больше второго, то на выходе схемы 10 сравнения появляется комбинация 10, в противном случае на выходе схемы сравнения - комбинация 01. Если показатели степени равны между собой, на выходе схемы сравнения 1 0 - комбинация 11. В случае равенства показателей степеней соответствующих пар на первом выходе разряда коэффициентов суммирующей ячейки присутствует двоичный код суммы соответствующих коэффициентов, а на первом выходе разряда показателя степени ячейки - код показателя степени, на втором выходе разряда коэффициентов и разряда показателя степени ячейки - О. В противном случае на первый выход разряда коэффициентов ячейки поступает коэффициент с большим показателем степени, а на второй выход ячейки - коэффициент с меньшим показателем. На оба выхода разрядов показателей степеней поступает коц показателя степени,- соответствующий коэффициенту, появившемуся на выходе разряда коэффициента .

Первый 5 и второй 7 регистры, стощие на выходах соответственно первой и второй групп суммирующих ячеек 6, необходимы для функционирования устройства в фазе сортировки0 Фаза I множения полиномов осуществляется за га тактов. Фаза сортировки (с использованием той же частоты f) осуществляется за m-n тактов Тогда для получения на выходе устройства результирующего полинома необходимо m+m-n тактов.

Для организации работы устройства в конвейерном режиме увеличивают частоту работы в фазе сортировки в п раз, т.е. f c n-f. Следовательно, на выходе устройства результирующий полином получают через m+m тактов после поступления на вход устройства первой пары коэффициентов полинома Р(х).

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

Формула изобретения

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

товых импульсов соединен с входом формирователя импульсов и синхровхода- ми первого и второго регистров, выходы

коммутатора подключены к информационным входам первого регистра,,1-й и (1+1)-й выходы которого (,4, К-2, , где m - порядок полинома множимого) соединены соответст-

венно с первым и вторым входами j-й суммирующей ячейки первой группы ( ., .К/2-1), первый и второй выходы

которой соединены соответственно с i-м и (i+l)-M информационными входа- 5 ми второго регистра, первый и К-и информационные входы которого соединены соответственно с первым и К-м выходами первого регистра, r-й и (,г+1)-й выходы второго регистра (,3.5,.К-1) соединены соответственно с первым и вторым входами j-й суммирующей ячейки второй группы (j l.,,.К/2) а

5

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

0 сумматор по модулю два, три коммутатора, причем первые группы разрядов первого и второго информационных входов ячейки соединены соответственно с первыми входами элементов И первой

, и второй групп, вторые входы которых соединены соответственно с первым и вторым выходами схемы сравнения, вторые группы разрядов первого и второго информационных входов ячейки соедине0 ны соответственно с первыми и вторыми входами схемы сравнения и первого коммутатора, управляющий вход которого соединен с управляющими входами второго и третьего коммута5 торов, с первым входом сумматора по модулю два и с вторым выходом схемы сравнения, первый выход которой соединен с вторым входом сумматора по модулю два, выход которого соединен

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

5 к первому и второму входам второго коммутатора, выход которого соединен с вторыми входами эпементов И третьей группы, выход третьего коммутатора соединен с вторыми входами элементов И четвертой группы, выходы элементов И первой и второй групп соединены с первым и вторым входами

ход ячейки, вторые группы разрядов 7| второго и первого информационных входов ячейки соединены соответственно

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

сумматора, выход которого и выход пер-, с первым и вторым входами третьего вого коммутатора образуют первый вы- коммутатора.

«

jLLjpjnJ

ЕИч

т

ЁР

&н

IB/toff

Р Е

гвюд

fue.l

2 ВыхаЗ