Устройство для умножения полиномов

 

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

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

СОЦИАЛИСТИЧЕСНИХ ! ЕСПУБЛИК щ) э G 06 F 15/31

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

QcvQAPc TBEHHblA ксмитет пс изОБРетениям и ОткРытиям

IlPH ГКНТ СССР

1 (21) 4608496/24-24 (22) 24.11.88 (46) 07.08.90.Бюл. !! - 29 (71) Физико-механический институт им.Г.В.Карпенко (72) А.Е.Батюк, В.В.Грицык . и В.П.Кожан (53) 68!,325 (088.8) (56) Авторское свидетельство СССР

Р 997039, кл. G 06 F 15/31, !983.

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

У 1432554, кл. G 06 Р 15/31, 27.10.87. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПОЛИНОМОВ (57) Изобретение относится к вычислительной технике и может быть испольИзобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных ма-. шинах и специализированных устройствах, Цель изобретения — повышение быстродействия устройства, На фиг.l представлена структурная схема устройства для умножения полина. мов;.,на фиг,2 — схема суммирующей ячейки, Устройство содержит и регистров I коэффициентов, и умножителей 2, и блоков 3 регистров сдвига, коммутатор 4, первый регистр 5, первую и вторую группы суммирующих ячеек 6, второй регистр 7, формирователь 8

„„SU, 1583939. А1

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

1 з.п.ф-лы, 2 ил. импульсов и генератор 9 тактовых импульсов.

Суммирующая ячейка 6 (фиг.2) со-... держит схему 1.0 сравнения, четыре группы элементов И ll, три коммутатора 12, сумматор !3 по модулю два и сумматор 14, Устройство предназначено для умно" жения полиномов. Полином Р(х) ffl (.К а.х задается списком пар, сос а! таящих из нулевого коэффициента и соответствующего ему показателя степени переменной.

При умножении полинома. Р(х) и и. 0 (х) Х Ь . х,, представленного

1«1 1

1583939 списком пар (b(yг„) (bg yйg)) ° ° ° y(Ърругя) в результате получаем полином к

А(х) * gсх р Э который представляется списком пар (с, ° 1, ) э ( э (с к в 1 к) s > 1 в К

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

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

Перед началом работы устройства в регистры 1 коэффициентов записыва-, ются коэффициенты полинома множителя

Q(x), в формирователь 8 импульсов— число К m n (не показано),где. ш - порядок полинома множимого;, n - порядок полинома Q(x)

В соответствии с частотой f генератора 9 тактовых импульсов через информационный вход устройства на входы умножителей 2 последовательно поступают коэффициенты первого полинома

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

° коэффициентов,. т.е. каждый умножитель

2 состоит из двухвходового умножите.ля двух чисел и сумматора. При этом сумматор реализует сложение показателей степеней соответствующих пар., Результаты умножения, т.е. пары чисел, :.последовательно записываются в ре-.. вистры 3 в соответствии с частотой генератора 9 тактовых импульсов.

На вход формирователя 8 импульсов импульсы поступают с частотой n f, аде n -. порядок полинома множителя;

f - тактовая частота поступления коэффициентов полинома множимого, а иа выходе появляются импульсы с .частотой n f/К, где К *чв.в, Таким образом, через m тактов работы устройства на управляющий вход коммутатора 4 с выхода формиро-1 вателя 8 поступает импульс логичес" кого "0" длительностью Я„ „= 1

2nf

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

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

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

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

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

5 158

Первый 5 и второй 7 регистры, стоящие на выходах соответственно первой и второй групп суммирующих ячеек 6,. необходимы для функционирования устройства в фазе сортировки. Фаза

„множения полиномов осуществляется за а тактов. Фаза сортировки (с использованием той же частоты f) осуществляется за ш и тактов. Тогда для получения на выходе устройства результирующего полинома необходимо

m+m и тактов.

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

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

3939

25

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

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

55 товых импульсов соединен с входом формирователя импульсов и синхровходами первого и второго регистров, выходы коммутатора подключены к информацион ным входам первого регистра,,ь-й и (i+1)-й выходы которого (i=2,4, К-2, K=n. m, где m — порядок полинома множимого) соединены соответственно с первым и вторым входами j""й суммирующей ячейки первой группы (j l...K/2-1), первый и второй выходы которой соединены соответственно с

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

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

583939

1hwnd

Р Ачхое

Фиа Р

Составитель Л Логачева

Редактор И.Шулла Техред Л.Сердюкова Корректор С ШекмаР

Заказ .2256 Тираж 568 Подписное

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

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

Производственно-издательский комбинат "Патент", r.Ужгород, ул. Гагарина,101 ментов И четвертой группы, выходы элементов И первой и второй групп соединены с первым и вторым входами сумматора, выход которого и выход первого коммутатора образуют первый выв ход ячейки, вторые группы разрядов . второго и первого информационных входов ячейки соединены соответственно с первым и вторым входами третьего коммутатора,