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

ОЮЗ СОВЕТСНИХОЦИАЛИСТИЧЕСНИХРЕСПУ БЛИН 19) (И) А 4 С 06 Р 15/31 САНИЕ ИЗОБРЕТ Я(57) Изобретениелительной техник пользовано в цифровых вычислительных комплексах и специализированных устройствах, в частности в устройствахцифровой обработки сигналов. Цель изобретения - расширение класса решаемых задач. Устройство для умножения полиномов содержит М регистров коэффициентов, суммирующий блок, гене- . ратор импульсов, М умножителей, М групп регистров, М схем сравнения, М элементов И и М элементов ИЛИ. Данное устройство реализует операцию умножения полиномов, представленных в виде списка пар, состоящих из ненулевого коэффициента и соответствуют щего ему показателя степени перемен ной. 3 ил.Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных ма.шинах и специализированных устройст 5 вах, в частности в устройствах цифровой обработки сигналов.Целью изобретения является расширение класса решаемых задач за счет возможности умножения разреженных 10 полиномов.На .Фиг.1 представлена структурная схема устройства для умножения полиномов, на фиг.2 - схема суммирующе:го блока, на фиг.З - схема суммирующей ячейки.Устройство содержит М регистров 1 коэффициентов, М умножителей 2, М групп регистров 3, М элементов И 4, М элементов ИЛИ 5, генератор 6 импульсов, М схем 7 сравнения и суммирующий блок 8.Суммирующий блок 8 (фиг,2) содержит К групп суммирующих ячеек 9 (К =1 о 8 М), при этом -я группа суммиЭрующих ячеек содержит 2суммирующих ячеек, где =1,К.Суммирующая ячейка 9 (Фиг.3) содержит схему 10 сравнения, коммутатор 11, два ключа 12 и сумматор 13.Устройство предназначено для умножения полиномов.мС -Полином Р(х) =а; х задается списком пар, состоящих из ненуле вого коэффициента и соответствующего ему показателя степени переменной х1) э (аэ 3) Ф9 (ав 316)1где 1; удовлетворяет условиям 40 ЬфК,1 е Ю, З 5 ем.1 (м45При умножении полинома Р(х) и полинома Я(х) " .Е б; х , представлен 1=1,ного списком парЬ 1 К ) ( Кт)ЬЬ К 11) 50в результате получают полнномРА(х)Р(х) Я(х) -.с; х1=1который представляется списком пар(с 11 11) 1 (с11 (ср 1 1 р)где Ь; ) Ь; ,= 1,Р. Устройство работает следующим образом.В соответствии с частотой генератора 6 импульсов на информационный вход устройства последовательно поступают коэффициенты первого полино" ма Р(х), заданные в виде списка пар ненулевых коэффициентов и соответствующих показателей степеней. Пары коэффициентов второго полинома Я(х) хранятся в регистрах 1 коэффициентов. Каждый из регистров 1 поделен на две части, соответствующие разрядам коэффициента и разрядам показателя степени. Во время поступления на информационный вход устройства пар первого полинома на управляющий вход уст" ройства подается сигнал логической "1". После поступления пар коэффициентов на управляющий вход устройства подается сигнал "0". Каждая группа регистров 3 состоит из и последовательно соединенных регистров, где и - число пар первого полинома. В умножителях 2 реализуется умножение пар коэффициентов, т.е. каждый умножитель 2 состоит из двухвходового умножителя двух чисел и сумматора. При этом сумматор реализует сложение показателей степеней соответствующих двух пар. Результаты умножения, т,е. пары чисел, последовательно записываются в регистры 3 групп в соответствии с частотой генератора б. Регистры в группе расположены последовательно. В каждом такте работы устройства в суммирующем блоке 8 осуществляется суммирование коэффициентов, записанных в группах регистров 3, которые имеют одинаковые показатели степени. Процесс суммирования (слияния) коэффициентов начинается от максимального показателя степени с коэффициентом, отличным от нуля. Суммирующий блок работает в параллельно-цоследовательном режиме и состоит из суммирующих ячеек У.Суммирующая ячейка работает следующим образом.Схема 10 сравнения осуществляет сравнение показателей степеней двух парЕсли первый показатель больше второго, то на выходе схемы 10 срав" нения появляется комбинация "10", в противном случае на,выходе присутствует комбинация "0,1". Когда показатели степени равны между собой, на выходе схемы 10 сравнения появляется3 14 комбинация "11", В случае равенства показателей степеней соответствующих пар на выходе коэффициентов суммирующей ячейки присутствует двоичный код суммы соответствующих коэффициентовВ противном случае на выход ячейки поступает коэффициент с максимальным показателем степени, а на выход порядка - собственно код этого показателя степени, В схемах 7 32554 сравнения параллельно осуществляетсясравнение показателей степеней пар,хранящихся в и-х (выходных) регистрах 3 (в разрядах показателя степени)групп, с показателем степени вычисленного в данном такте коэффициентаполинома, поступающего с выхода порядка суммирующего блока 8. В случаеравенства происходит сдвиг информациив соответствующей группе регистров 3В следующем такте суммирующий блок 8реализует вычисление следующего коэффициента полинома и соответствующего показателя степени. Таким образом, на выходах суммирующего блокапоявляются двоичные коды пар произведения двух полиномов. 55 формула изобретения Устройство для умножения полиномов, содержащее М регистров коэффициентов, где М - порядок полинома множимого, суммирующий блок и генератор импульсов, причем выход суммы суммирующего блока соединен с выходом устройства, о т л и ч а ю - щ е е с я тем, что, с целью расширения области применения за счет умножения разреженных полиномов, в него введены М умножителей, М групп регистров, М элементов И, М элементов ИЛИ и М схем сравнения, причем информационный вход устройства соединен с первыми входами всех умножителей, вторые входы Которых соединены с выходами соответствующих регистров коэффициентов, выходы всех умножителей соединены с информационными входами первых регистров соответствующих групп, входы синхронизации регистров которых объединены и подключены к выходам соответствующих элементов И, первые входы которых соединены с выходами соответствующих элементов ИЛИ, первые входы которых соединены с выходами соответствующих схем сравнения, первые входы которых 10 15 20 25 30 35 40 45 50 подключены к выходам групп разрядов порядка и-х регистров соответствующих групп, где п - порядок полинома множителя, выход генератора импульсов соединен с вторыми входами всех элементов И, вторые входы всех элементов ИЛИ соединены с входом разрешения загрузки устройства, выход 1-го регистра каждой группы, где - 1, 2. . . и, соецинен с инфор" мационным входом (1+1)-го регистра той же группы, причем блок суммирования содержит К групп суммирующих ячеек, где К = 1 ое М, при этом в 1-й группе суммирующих ячеек содержится 2суммирующих ячеек, где ). =1,2,,К, входы первого и второго коэффициентов 1 - й суммирующей ячейки р-й группы, где р = 1, 2 К,р 1 = 1, 2 2 Р , соединены соответственно с выходом коэффициента (21- 1)-й и выходом коэффициента 21-й суммирующих ячеек (р+1)-й группы, первый и второй входы порядков 1-й суммирующей ячейки р-й группы соединены с выходами порядков соответственно (21-1)-й и 21-й суммирующих ячеек (р+1)-й группы, входы первого и второго коэффициентов Я-й суммирующей ячейки К-й группы, 8=1,2 ,2 , соединены с выходами группы разрядов коэффициентов и-х регистров соответственно (2 Б)-х и 28-х групп, выходы групп разрядов порядков и-х регистров которых соединены соответственно с первым и вторым входами порядков Б-й суммирующей ячейки К-й группы, выход порядка первой ячейки первой группы соединен с вторыми входами всех схем сравнения, выход коэффициента первой суммирующей ячейки соединен с выходом блока суммирования, причем каждая суммирующая ячейка содержит схему сравнения, два ключа, сумматор и коммутатор, выход которого соединен с выходом порядка суммирующей ячейки, первый и второй входы порядков которой соединены соответственно с первым и вторым входами схемы сравнения суммирующейячейки и соответственно с первым ивторым информационными входами коммутатора, управляющии вход которогосоединен с управляющим входом первого ключа и первым выходом схемы сравнения суммирующей ячейки, второй выход схемы сравнения которои соединен с управляющим входом второго клю 5 14325546ча, информационные входы первого и нены соответственно с входами первторого ключей соединены с входами , вого и второго слагаемых сумматора, соответственно первого и второго ко- выход которого соединен с выходом эффициентов суммирующей ячейки, вы- коэффициента суммирующего блока. ходы первого и второго ключей соедиИнр. др 0 д1432554 Составитель А.Зоринецкая Техред А.Кравчук Корректор О.Кравцов РеДЙктор О Заказ 5443/4 к 4/5,ая Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная,Тираж.704 ВНИИПИ Государственного по делам изобретений 3035, Москва, Ж, Раув