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

 

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

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

СОЦИАЛИСТИЧЕСКИХ . РЕСПУБЛИК аи 4 С 06 F 15/31

ВСЕГО) @

13 ".

:,,.„73 7QJflHQ fQfg

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

М A BTOPCH0MY СВИДЕТЕЛЬСТВУ

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

ПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4230870/24-24 (22) 15.04.87 (46) 23.10.88. Бюл. У 39 (71) Физико-механический институт им. Г.В.Карпенко (72) В.В.Грицык, В.П.Кожан и P.М.Паленичка (53) 681.325 (088.8) (56) Авторское свидетельство СССР

В 997039, кл. G 06 F 15/31, 1981.

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

В 1067509, кл. 6 06 F 15/31 1983. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПОЛИБОМОВ (57) Изобретение относится к вычис" лительной технике и может быть ис„Л0„„4 2554 А1 пользовано в цифровых вычислительных комплексах и специализированных устройствах, в частности в устройствах цифровой обработки сигналов. Цель изобретения — расширение класса решаемых задач. Устройство для умножения полиномов содержит М регистров коэффициентов, суммирующий блок, гене-ратор импульсов, М умножителей, М групп регистров, М схем сравнения, М элементов И и М элементов ИЛИ. Данное устройство реализует операцию умножения полиномов, представленных в виде списка пар, состоящих из ненулевого коэффициента и соответствуют щего ему показателя степени переменР ной. 3 ил.

1432554

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

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

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

Устройство содержит М регистров

:1 коэффициентов, М умножителей 2,,N групп регистров 3, M элементов И 4, М элементов ИЛИ 5, генератор 6 им. пульсов, М схем 7 сравнения и сумми рующий блок 8.

Суммирующий блок 8 (фиг.2) содержит К групп суммирующих ячеек 9 (К =

log М), при этом i-я группа сумми- 25

1-1 рующих ячеек содержит 2 суммирующих ячеек, где i=1 K.

Суммирующая ячейка 9 (фиг. ° 3) содержит схему 10 сравнения, коммутатор 11, два ключа 12 и сумматор 13.

Устройство предназначено для умножения полиномов. м — )1

Полинам Р(х) = a; х задает>» t ся списком пар, состоящих из ненуле- 35 ваго коэффициента и соответствующего ему показателя степени переменной х

1)» (а2» 32)». ° ° » (+g j ) где j; удовлетворяет условиям 40

f K» 1 е Н» .1 < ф,3 м

1c (M

При умножении полинома Р(х) и по11 линома g(x) " .Е б; х, представлен1=1 ,нога списком пар (Ь1 g К1) g (Ь2» К2)» ° фе»(Ь11 g К11) g 50 в результате получают полинам

А(х) - Р(х) ° q(x) = . с; х

1=1 который представляется списком пар (c1» h<)» (с2» 4<)» (ср» Ьр) где h; ) h;<, i = 1,Р.

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

В соответствии с частотой генератора 6 импульсов на информационный вход устройства последовательно поступают коэффициенты первого полинома Р(х), заданные в виде списка пар ненулевых коэффициентов и соответствующих показателей степеней. Пары коэффициентов второго палинома g(x) хранятся в регистрах 1 коэффициентов.

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

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

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

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

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

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

Схема 10 сравнения осуществляет сравнение показателей степеней двух пар ° Если первый показатель больше второго, то на выходе схемы 10 срав" нения появляется комбинация "10", в противном случае на.выходе присутствует комбинация "0.1". Когда показатели степени равны между собой, на выходе схемы 10 сравнения появляется

3 14 комбинация "11". В случае равенства показателей степеней соответствующих пар на выходе коэффициентов суммирующей ячейки присутствует двоичный код суммы соответствующих коэффициентов ° В противном случае на выход ячейки поступает коэффициент с максимальным показателем степени, а на выход порядка — собственно код этого показателя степени. В схемах 7 сравнения параллельно осуществляется сравнение показателей степеней пар, хранящихся в ll х (выходных) регистрах 3 (в разрядах показателя степени) групп, с показателем степени вычисленного в данном такте коэффициента полинома, поступающего с выхода порядка суммирующего блока 8. В случае равенства происходит сдвиг информации в соответствующей группе регистров 3 °

В следующем такте суммирующий блок 8 реализует вычисление следующего коэффициента полинома и соответствующего показателя степени. Таким образом, на выходах суммирующего блока появляются двоичные коды пар произведения двух полиномов.

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

Устройство для умножения полиномов, содержащее M регистров коэффициентов, где М вЂ” порядок полинома множимого, суммирующий блок и генератор импульсов, причем выход суммы суммирующего блока соединен с выходом устройства, о т л и ч а ю— щ е е с я тем, что, с целью расширения области применения за счет умножения разреженных полиномов, в него введены M умножителей, M групп регистров, M элементов И, М элементов ИЛИ и M схем сравнения, причем информационный вход устройства соединен с первыми входами всех умножителей, вторые входы которых соединены с выходами соответствующих регистров коэффициентов, выходы всех умножителей соединены с информационными входами первых регистров соответствующих групп, входы синхронизации регистров которых объединены и подключены к выходам соответствующих элементов И, первые входы которых соединены с выходами соответствующих элементов ИЛИ, первые входы которых соединены с выходами соответствующих схем сравнения, первые входы которых

32554

50 подключены к выходам групп разрядов порядка и-х регистров соответствующих групп, где п — порядок полинома множителя, выход генератора импульсов соединен с вторыми входами всех элементов И, вторые входы всех элементов ИЛИ соединены с входом разрешения загрузки устройства, выход j-горегистра каждой группы, где — 1, 2, ..., n-1, соецинен с информационным входом (j+1)-го регистра той же группы, причем блок суммирования содержит К групп суммирующих ячеек, где К = log И, при этом в

i-й группе суммирующих ячеек содержится 2 суммирующих ячеек, где i

=1,2, ° ..,К, входы первого и второго коэффициентов 1 — и суммирующей ячейки р и группы, где р = 1, 2 ..., К-1, р-1

1 = 1, 2,..., 2 Р, соединены соответственно с выходом коэффициента (21- 1)-й и выходом коэффициента 21-й суммирующих ячеек (р+1)-й группы, первый и второй входы порядков 1-й суммирующей ячейки р-й группы соединены с выходами порядков соответственно (21-1)-й и 21-й суммирующих ячеек (р+1)-й группы, входы первого и второго коэффициентов S-й суммирующей ячейки К-й группы, S=1,2,..., . ...,2, соединены с выходами группы разрядов коэффициентов п-х регистров соответственно (2S-1)-х и 2S-х групп, выходы групп разрядов порядков п-х регистров которых соединены соответственно с первым и вторым входами порядков S-й суммирующей ячейки

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

6 ча, информационные входы первого и нены соответственно с входами первторого ключей соединены с входами . вого и второго слагаемых сумматора, сОответственно первого и второго ко- выход которого соединен с выходом эффициентов суммирующей ячейки, вы- коэффициента суммирующего блока. ходы первого и второго ключей соедиИнр. диод

1432554

Фиг. 2

1432554

f ìя gppP

Составитель A.Çîðèí

Ре КТор О.фрковецкая Техред А.Кравчук Корректор 0.Кравцова

Заказ 5443/43

Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, r, Ужгород, ул. Проектная, 4