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

(Ь г) э (1 э) е в(ъррвгя) ев результате получаем полином к А(х)сх ркоторый представляется списком пар(ср 91) ф (с1)90609 (ск 1 р) х 1 рКюПри умножении двух разреженныхполиномов, представленных спискомпар, находят произведения пар и располагают их но величине показателейстепени (по вторым компонентам пар)объединяя все члены с .одинаковымипоказателями.Устройство работает следующим об 20разом.Перед началом работы устройствав регистры 1 коэффициентов записыва-,ются коэффициенты полинома множителя0(х), в формирователь 8 импульсов -число К ш и (не показано),где.а - порядок полинома множимого;,п " порядок полинома Я(х)В соответствии с частотой Ю генератора 9 тактовых импульсов через информационный вход устройства на входыумножителей 2 последовательно поступают коэффициенты первого полиномаР(х), заданные в виде списка пар иену"левых коэффициентов и соответствую." 35щих показателей степеней. Пары коэффициентов второго полинома хранятся врегистрах 1 коэффициентов. Каждый изрегистров 1 разделен на две части,соответствующие разрядам коэффициента "и разрядам показателя степени. В умножителях 2 реализуется умножение паркоэффициентов,. т.е. каждый умножитель2 состоит из двухвходового умножите.ля двух чисел и сумматора. При этомсумматор реализует сложение показателей степеней соответствующих пар..последовательно записываются в ре-.,вистры 3 в соответствии с частотойгенератора 9 тактовых импульсов.На вход Формирователя 8 импульсовимпульсы поступают с частотой п Ю,аде а ". порядок полинома множителя;Й - тактовая частота поступлениякоэффициентов полинома множимого,а иа выходе появляются импульсы с.частотой паяй/К, где К чв.а,Таким образом, через ш тактовработы устройства на управляющийвход коммутатора 4 с выхода формиро.вателя 8 поступает импульс логичес"кого 0 длительностью ьд=В результате этого информация с выходов группы сдвигающих регистров 3поступает через коммутатор 4 ра входы регистра 5, На следующем (ш+1)-мтакте информация записывается в регистр 5 и поступает дальше в группу,ячеек 6, На этом же такте с выходаФормирователя 8 на управляющийвход коммутатора 4 поступает еигналлогической "1" (начальное состояние)в результате которого выходы второйгруппы ячеек 6 соединяются через коммутатор 4 с входами регистра 5,Процесс формирования результирующего полинома А(х), т.е, процессрасположения пар коэффициентов повеличине показателей степени (по вторым компонентам пар) с объединениемвсех членов с одинаковыми показателя"ми происходит в первой и второй группах суммирующих ячеек 6,Суммирующая ячейка работает следующим образом.Схема 10 сравнения осуществляетсравнение показателей степеней двухпар. Если первый показатель большевторого, то на выходе схемы 10.сравнения появляется комбинация 10, впротивном случае на выходе схемысравнения - комбинация 01. Если показатели степени равны между собой,на выходе схемы сравнения 10 - комби-.нация 11. В случае равенства показате-,лей степеней соответствующих пар напервом выходе разряда коэффициентовсуммирующей ячейки присутствует двоичный код суммы соответствующих коэффициентов, а на первомвыходе разряда показателя степени ячейки - код.показателя степени, на втором выходеразряда коэффициентов и разряда показателя степени ячейки - "0", В противном случае на первый выход разряда коэффициентов ячейки поступаеткоэффициент с большим показателемстепени,. а на второй выход ячейки -коэффициент с меньшим показателем,На оба выхода разрядов показателейстепеней поступает код показателя степени, - соответствующий коэффициенту,появившемуся на выходе разряда коэффициента.5 158Первый 5 и второй 7 регистры, стоящие на выходах соответственно первой и второй групп суммирующих ячеек 6 необходимы для функционирования устройства в фазе сортировки. Фаза множения полиномов осуществляется за а тактов. Фаза сортировки (с использованием той же частоты Г) осуществляется за ш и тактов. Тогда для получения на выходе устройства результирующего полинома необходимо ш+ш и тактов.Для организации работы устройства н конвейерном режиме увеличивают частоту работы в Фазе сортировки в и раз, т.е. Г с = и1. Следовательно, на выходе устройства результирующий полином получают через ш+ш тактов после поступления на нход устройства первой пары коэффициентов полинома Р(х).Предлагаемое устройство обладает увеличенным быстродействием по сравнению с известным, что дает возможность применять его для работы в режиме реального времени. Кроме того, устройство обладает также меньшими аппаратными затратами. 3939 10 15 20 формула изобретения 1. Устройство для умножения полиномов, содержащее и регистров коэфФициентов (и - порядок полинома множителя), и умножителей, и блоков регистров сдвига, две группы суммирующих ячеек и генератор тактовых им, пульсов, первый выход которого соединен с тактовыми входами и блоков регистров сдвига, информационные входы которых соединены соответственно выходами и умножителей, первые и вторые инйормационные входы которых соединены соответственно с выходами и регистров коэффициентов и информационными входами устройства, о т л и ч а ю щ е е с я тем, что, с .целью повышения быстродействия, в него введены коммутатор, два регист" ра и формирователь импульсов, выход которого соединен с управляющим входом коммутатора, к первой группе информационных входов которого подключены выходы и блоков регистров сдви" га, а к второй группе информационных входон - выходы суммирующих ячеек пер. вой группы, являющиеся и выходами уст-. ройства, второй выход генератора так 30 35 40 45 50 55 товых импульсов соединен с входом формирователя импульсов и синхровходами первого и второго регистров, выходы коммутатора подключены к информацион ным входам первого регистраь-й и (ь+1)-й ныходы которого (д=2,4, К, К=и.ш, где ш - порядок полинома множимого) соединены соответственно с первым и вторым входами "й суммирующей ячейки первой группы (1 1 К/2-1), первый и нторой выходы которой соединены соответственно с 1.-м и (+1)-м информационными входами второго регистра, первый и К-й информационные входы которого соединены соответственно с первым и К-м выходами первого регистра, г-й и 1,г+1)-й выходы второго регистра (г=1,3,5.;.К) соединены соответственно с первым и вторым входами 1-й суммирующей ячейки второй группы (1=1К/2)2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что суммирующая ячейка содержит схему сравнения, четыре группы элементов И, сумматор, сумматор по модулю два, три коммутатора, причем первые группы разрядов первого и второго информационных входон ячейки соединены соответственно с первыми входами элементов И первой и второй групп, вторые входы которых соединены соотнетственно с первым и вторым выходами схемы сравнения, вторые группы разрядов первого и второго информационнагх входов ячейки соединены соответственно с первыми и вторыми входами схемы сравнения и первого коммутатора, управляющий вход которого соединен с управляющими входами второго и третьего коммутаторов, с первым входом сумматора по модулю .два и с вторым выходом схемы сравнения, первый выход которой соединен с вторым входом сумматора по модулю два, выход которого соединен с первыми входами элементов И третьей и четвертой групп, выходы которых образуют второй выход ячейки, первые группы разрядов первого и второго инФормационных входон ячейки подключены к первому и второму входам второго коммутатора, выход которого соединен с вторыми входами элементов И третьей группы, выход третьего коммутатора соединен с вторыми входами элеl йгиЮ Фие Составитель ЛЛогачеваРедактор И.Шулла Техред Л.Сердюкова Корректор С.Шекмар Заказ .2256 Тираж 568 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 313035,. Москва, Ж, Раушская наб., д. 4/5 одственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 10 Пр ментов И четвертой группы, выходыэлементов И первой и второй группсоединены с первым и вторым входамисумматора, выход которого и выход первого коммутатора образуют первый вы" вход ячейки, вторые группы разрядов . второго и первого информационных входов ячейки соединены соответственно с первым и вторым входами третьего коммутатора,