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

О П И С А Н И Е 11922732ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциапнстическихРеспублик,(51)М. Кл. С 06 Р 7/52 Государственный квинтет СССР вв делам изобретений н открытийДата опубликования описания 23. 04. 82 М,П. Батура и В.А. Птичкин(72) Авторы изобретения ЕМинский радиотехнический институтщ4(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПОЛИНОМОВИзобретение относится к вычислительной технике, предназначено для умножения полиномов нескольких независимых переменных и может быть использовано при построении специализированных вычислительных устройств и систем для автоматического управления и регулирования.Известно устройство для пакетного умножения чисел, содержащее блоки пакетного вероятностного кодирования,10 генератор тактовых импульсов, блок схем совпадения, делитель импульсов, блок реверсивных счетчиков, блок выходных схем, генератор случайных чисел, входной регистр, схемы сравне 15 ния чисел, схемы И, выходной регистр и переключатель 1). Недостатком этого устройства является невозможность умножения в нем двух полиномов нескольких независимых переменных, что существенно сужает область применения устройства. Наиболее близким техническим решением к изобретению является устройство для умножения, содержащее три блока памяти, арифметический блок, первый блок регистров, блок сравнения, блок счетчиков и блок управления, причем первый выход блока счетчиков соединен с входом первого блока памяти, выход которого соединен с первым входом блока сравнения, второй выход блока счетчика соединен с первым входом блока управления, первый выход которого подключен к первому входу блока счетчиков, третий выход которого соединен с первым входом второго блока памяти, выход третьего. блока памяти соединен с первым входом арифметического блока, второй вход которого соединен с вторым выходом блока управления, третий выход которого соединен с вторым входом второго блока памяти и первым входом третьего блока памяти, третий вход второго блока памяти соединен22732 20 5 10 15 20 25 19 9ступает сигнал готовности на второйи третий входы элементов И 25 и 28соответственно, Триггер 29 находитсяв нулевом состоянии, поэтому очередной тактовый импульс проходит черезэлемент И 28,Низкий уровень, поступающий спервого выхода триггера 29, обеспечивает выборку информации из блока8 памяти по адресу, поступающему с,выхода пятого счетчика 40, и считывание коэффициента первого полиномаиз первой области блока 9 памяти.По импульсу с выхода элемента И 28 этот коэффициент принимаетсяв арифметический блок 10, а триггер29 устанавливается в единичное состояние. При этом сигнал готовностив арифметическом блоке 10 снимается,Поступающий с первого выхода триггера 29 высокий сигнал обеспечиваетвыборку информации по адресу, Формируемому сумматором:6, из блока 8памяти и выборку коэффициента второго полинома из второй области блока9 памяти,Поступающий очередной тактовыйимпульс проходит на выход элемента30, чем обеспечивает прием коэффициента второго полинома в арифметический блок 10, уменьшение состояния пятого счетчика 40 на единицуи установка триггера 29 в нулевоесостояние.К моменту окончания последнегоцикла с выхода счетчика 40 поступает сигнал, фиксирующий его нулевоесостояние, на первый вход эле- .мента И 25,а на второй вход поступает сигнал готовности арифметическогоблока 10. Поступающий с выхода элемента И 25 высокий уровень обеспечивает в блоке 8 памяти выбор ячейки в соответствии с кодом Я -1, поступающим с выхода сумматора б, и выбор третьей области блока 9 памяти. Очередной тактовый импульс проходит. через элемент И 26, обеспечивая при этом запись полученного коэффициента результирующего полинома, и устанавливает триггер 27 в нулевое состояние, фиксирующее окончание второго этапа,После завершения первого этапа вычисления последнего 3 -го коэффициента результирующего полинома сос 30 35 40 45 50 5 У тояние первого счетчика 36 блока 1счетчиков достигает значения 3, равного коэффициенту пересчета, поэтомуна его выходе вырабатывается импульсокончания последнего этапа, который,поступая на четвертый вход блока 11управления (второй вход триггера 13),устанавливает триггер 13 в нулевоесостояние, запрещающее прохождениеимпульсов через элемент И 14 и выработку сигналов, обеспечивающихвыполнение первого этапа. Нулевойуровень с выхода триггера 13 поступает также на второй вход (П-вход)триггера 19, поэтому по импульсу свыхода элемента И 23, запускающемуустройство на выполнение второгоэтапа вычисления последнего коэффициента, триггер 19 устанавливаетсяв нулевое состояние. Это запрещаетв дальнейшем выработку сигнала навыходе элемента И 23 и работу устройства после окончания выполнениявторого этапа вычисления последнего3-го коэффициента результирующегополинома до поступления следующегосигнала на вход "Запуск". Показатели степеней переменныхмогут располагаться последовательнопо одному в каждой ячейке блока 2памяти. При этом разрядность блока2 памяти определяется разрядностьюпоказателей степеней переменных,количество регистров блока 3 регистров равно количеству переменных, аблоксравнения содержит одну. схемусравнения,Таким образом, по сравнению сизвестным в предлагаемом устрой 1стве повышается быстродействие засчет исключения выполнения рхохп операций сложения показателей степенейпеременных; исключения многократного сдвига содержимого третьего блокапамяти, так как отпадает операцияприведения подобных одночленов; исключения операций сравнения суммарныхпоказателей степеней переменных приодночленах результирующего полиномасо значением И 3 в случае задания точности результата 1 с 3 (Е+ 1; совмещения во времени. операций сравненияпоказателей степеней переменных и вычисления коэффициентов результирующего полиномаВ предлагаемом устройстве достигается экономия дбъема памяти на21 922732 22пх(р+ц)-ч ячеек, так как отпадает линомах сомножителях, Здесь ч, - конеобходимость хранения массивов пока. личество ячеек блока 8 памяти. Оно зателей степеней переменных при по- значительно меньше пх(р+ф .4 Г 13я 11 Е .Е пЕ Вектор А 1 Вектор А . Ректор А 10 С 11 Е Формула изобретения 15 Степенипеременных 10 10по 1Е."п 1. Устройство для умножения полиномов многих переменных, содержащеетри блока памяти, арифметическийблок, первый блок регистров, блоксравнения, блок счетчиков и блокуправления, причем первый выходблока счетчиков соединен с входомпервого блока памяти, выход которогосоединен с первым входом блока срав- инения, второй выход блока счетчйковсоединен с первым входом блока управления, первый выход которого подключен к первому входу блока счетчиков, третий выход которого соединен с пер- Зо вым входом второго блока памяти, вы.ход третьего блока памяти соединен с первым входом арифметического блока, второй вход которого соединен с вторым выходом блока управления,35 третий выход которого соединен с вторым входом второго блока памяти и первым входом третьего блока памя- ти, третий вход второго блока памяти соединен с четвертым выходом блока управления, пятый выход которого соединен с первым входом первого бло. ка регистров, выход которого соединен с вторым входом блока сравнения, первый выход арифметического блока45 соединен с вторым входом третьего блока памяти, второй вход блока управления является входом запуска устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстром0 действия, в него введены второи блок регистров, сумматор и схема срав" нения, причем выход первого блока памяти соединен с вторым входом первого блока регистров, выход блока сравнения соединен с вторым входом55 блока счетчиков, третий выход которого соединен с третьим входом первого блока регистров, выход второго блока памяти соединен с третьим входом третьего блока памяти, второйвход арифметического блока соединенс третьим входом блока счетчиков,второй выход арифметического блокасоединен с третьим входом блока управления, четвертый выход блокасчетчиков соединен с первыми входами второго блока регистров, схемысравнения и четвертым входом второго блока памяти, выход схемы сравнения соединен с четвертым входом блока управления, пятый вход которогозсоединен с пятым выходом блока счетчиков, первым входом сумматора ипятым входом второго блока памяти,шестой вход которого соединен с .выходом сумматора, шестой выход блокасчетчиков соединен с вторым входомвторого блока регистров и седьмымвходом второго блока памяти, второйвход схемы сравнения соединен с. первым выходом второго блока регистров,второй выход которого соединен свторым входом сумматора, шестой выход блока управления соединен стретьим входом второго блока регистров, четвертый вход которого соединен с седьмым выходом блока управленияи четвертым входом блока счетчиков,2. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок управления содержит генератор тактовыхимпульсов, восемь триггеров, десятьэлементов И, причем выход генераторатактовых импульсов соединен с первымивходами первого, пятого, шестого,восьмого, девятого и десятого элементов И, первцй вход первого триггера соединен с первым входом третьеготриггера и является вторым входомблока управления, второй вход первого триггера соединен с первымивходами второго и третьего элементов И и является первым входом бло23 92273 ка управления, второй вход третьего триггера соединен с вторым входом первого элемента И и выходом первого триггера, второй вход второго элемента И является четвертым входом блока управления, третий вход первого элемента И соединен с первым выходом четвертого триггера, второй выход которого соединен с вторым входом пятого элемента И, а 10 первыйвход - с выходом третьего элемента И, первым входом второго триггера и являетсяшестым выходом блока управления, третий вход второго элемента И соединен с первым выходом 1 ю второго триггера, второй выход которого соединен с вторым входом третьего элемента И и первым входом четвертого элемента И, выход третьего триггера соединен с вторым входом ро шестого элемента М, третий вход которого соединен с выходом пятого триггера, первый вход которого подключен к выходу пятого элемента И и является седьмым выходом блока уп- т равления, первый вход седьмого элемента И соединен с вторым входом девятого элемента И и является третьим входом блока управления, а второй вход является пятым входом блока управления, третий вход девятого элемента И соединен с первым выходом седьмого триггера, второй выход которого соединен с третьим входом пятого элемента И, первый вход восьмого триггера соединен с выходом девятого элемента И, второй вход восьмого триггера соединен с выходом десятого элемента И, второй вход которого соединен с первым выходом восьмого триггера, вторым входом восьмого элемента И, первый вход седьмого триггера соединен с выходом восьмого элемента И, четвертый вход девятого элемента И соединен с вторым выходом восьмого триггера, выход четвертого элемента И является пятым выходом блока управления, выходвторого элемента И соединен с вторым входом второго триггера, выход шестого элемента И соединен с входом шестого триггера, вторыми входами четвертого, пятого и седьмого триггеров, третьим входом третьего триггера, выходы первого, второго и шестого элементов И объединены и являются первым выходом блока управления,выходы седьмого, восьмого элементов И и восьмого триггера объединены и являются третьим выходом блокауправления, выходы девятого и десятого элементов И объединены и являются вторым выходом блока управления, выход шестого триггера является четвертым выходом блока управления,3. Устройство по п.1, о т л ич а ю щ е е с я тем, что арифметический блок содержит два входныхрегистра, умножитель, элемент задержки, триггер, сумматор, выходнойрегистр, причем инФормационные входы первого и второго входных регистров объединены и являются первым входом арифметического блока, управляющий вход второго входного регистра соединен с входом элемента задержки, выход которого соединен суправляющим входом триггера и первым управляющим входом выходного регистра, выход которого соединен спервым входом сумматора,и являетсяпервым выходом ариФметического блока, инФормационный вход триггера,соединен с управляющим входом,первого входного регистра, выход которого соединен с первым входом;умножителя, второй вход которогосоединен с выходом второго входногорегистра, выход умножителя соединенс вторым входом сумматора, выход которого соединен с инФормационнымвходом выходного регистра, выходтриггера является вторым выходомариФметического блока, управляющие-входы первого и второго входных регистров, второй управляющий входвыходного регистра объединены иявляются вторым входом ариФмети.ческого блока.Источники инФормации,принятые во внимание при экспертизе1. Авторское свидетельство СССРМ 150168; кл. С 06 Г 7/52, 197 М.2. Авторское свидетельство СССРпо заявке й 2598893/18-2 Й,кл, С 06 Р 7/39, 1978 (прототип),922732 Составитель Л Техред И, Гайд едведева Корректор М. Коста актор В. Данк Заказ 258 лиал ППП "Патент", г. Ужгород, ул. Проектн Тираж 732 ВНИИПИ Государстве по делам изобре 3035, Москва, Ж, ного к ений и Раушск Подписноемитета СССРоткритийя наб., д. /53 92273с четвертым выходом блока управления,пятый выход которого соединен с первым входом первого блока регистров,выход которого соединен с вторымвходом блока сравнения, первый выходарифметического блока соединен с вторым входом, третьего блока памяти,второй вход блока управления являетсявходом запуска устройства ,23,Однако в данном устройстве после 10каждой операции перемножения двух.коэффициентов полиномов следуют операции сложения показателей степенейпеременных и приведения подобныходночленов в результирующем полиноме, Эти операции не могут быть совмещены во времени. Кроме того, операция приведения подобных одночленовприводит к необходимости многократного сдвига содержимого третьего блока памяти. Эти факторы существенноснижают быстродействие устройства.Недостатком данного устройстваявляется также большой объем памяти,необходимый для хранения показателей 25степеней переменных каждого полиномасомножителя и результирующего полинома.Цель изобретения - повышение быстродействия устройства.30Поставленная цель достигаетсятем, что в устройство введены второйблок регистров, сумматор и схемасравнения, причем выход первого блокапамяти соединен с вторым входом первого блока регистров, выход блокасравнения соединен с вторым входомблока счетчиков, третий выход которого соединен с третьим входом первого блока регистров, выход второгоблока памяти соединен с третьим входом третьего блока памяти, второйвход арифметического блока соединенс третьим входом блока счетчиков,второй выход ариФметического блокасоединен с,третьим входом блока управления, четвертый выход блока счетчиков соединен с первыми входамивторого блока регистров, схемы сравнения и четвертым входом второго бло 50ка памяти, выход схемы сравнениясоединен с четвертым входом блокауправления; п,тый вход которого соединен с пятым выходом блока счетчиков, первым входом сумматора и пя 55тым входом второго блока памяти,шестой вход которого соединен с выходом сумматора, шестой выход блокасчетчиков соединен с вторым входом 2второго блока регистров и седьмым входом второго блока памяти, второй вход схемы сравнения соединен с первым выходом второго блока регистров, второй выход которого соединен с вторым входом сумматора, шестой выход блока управления соединен с третьим входом второго блока регистров, четвертый вход которого соединен с седьмым выходом блока управления и четвертым входом блока счетчиков.Кроме того, блок управления содержит генератор тактовых импульсов, восемь триггеров, десять элементов И, причем выход генератора тактовых импульсов соединен с первыми входами первого, пятого, шестого, восьмого, девятого и десятого элементов И, первый вход первого триггера соединен с первым входом третьего триггера и является вторым входом блока управления, второй вход первого триггера соединен с первыми входами второго и третьего элементов И и является первым входом блока управления, второй вход третьего триггера соединен с вторым, входом первого элемента И и выходом первого триггера, второй вход второго элемента И является четвертым входом блока управления, третий вход первого элемента И соединен с первым выходом четвертого триггера, второй выход которого соединен с вторым входом пятого элемента И, а первый. вход с выходом третьего элемента И,первым входом второго триггера и является шестым выходом блока управления, третий вход второго элемента И соединен с первым выходом второго триггера, второй выход которого соединен с вторым входом третьего элемента И и первым входом четвертого элемента И, выход третьего триггера соединен с вторым входом шестого элемента И, третий вход которого соединен с выходом пятого триггера, первый вход которого подключен к выходу пятого элемента И и является седьмым выходом блока управления, первый вход седьмого элемента И соединен с вторым входом девятого элемента И и является третьим входом блока управления, а второй вход является пятым входом блока управления., третий вход девятого элемента И соединен с первым выходом седьмого триггера, второй выход которого соединен с третьим9227 и элемент И 30Блок 3 регистров служит для хранения показателей степеней переменных вычисляемого одночлена результирующего полинома в процессе функционирования устройства.Блок 3 регистров содержит п регистров 31-1-31-и и два дешифратора 32 иБлок 4 сравнения содержит и схем 31-1-3 М-и и и-входовой элемент ИЛИ 35.Блок 1 счетчиков содержит пять счетчиков 36-10, из которых первый 36 и второй 37 с управляемым коэфФициентом пересчета, схему управления счетчиком 39, которая содержит элемент И 11, триггер 12, элемент И 43 и элемент М задержки. Первый счетчик 36 предназначен для Формирования адресов чтения из блока 2 памяти показателей степеней переменных исходных полиномов, второй счетчик 37 формирует адреса выборки из блока 3 регистров показателей степеней переменных вычисляемого одночленач результирующего полинома, третии 5входом пятого элемента И, первыйвход восьмого триггера соединен с выходом девятого элемента И, второйвход восьмого триггера соединен с выходом десятого элемента И, второйвход которого соединен с первым выходом восьмого триггера, вторым входом восьмого элемента И, первый входседьмого триггера соединен с выходомвосьмого элемента И, четвертый вход 1 Одевятого элемента И соединен с вторым выходом воСьмого триггера, выходчетвертого элемента И является пятымвыходом блока управления, выход второго элемента И соединен с вторым 15входом второго триггера, выход шес того элемента И соединен с входом шестого триггера, вторыми входами чет"вертого, пятого и седьмого триггеров,третьим входом третьего триггера,выходы первого, второго и шестого элемента И объединены и являются первым выходом блока управления, выходы седьмого и восЪмого элементов Ии восьмого триггера объединены и являются третьим выходом блока управления, выходы девятого и десятогоэлементов И объединены и являются вторым выходом блока управления, выходшестого триггера является четвертымвыходом блока управления,При этом арифметический блок содержит два входных регистра, умножитель, элемент задержки, триггер,сумматор, выходной регистр, причем инФормационные входы первого и второговходных регистров объединены и являются первым входом арифметическогоблока, управляющий вход второго входного регистра соединен с входом элемента задержки, выход которого соединен с управляющим входом триггера ипервым управляющим входом выходногорегистра, выход которого соединенс первым входом сумматора и являетсяпервым выходом арифметического блока, информационный вход триггерасоединен с управляющим входом первоговходного регистра, выход которогосоединен с первым входом умножителявторой вход которого соединен с выходом второго входного регистра, выход.умножителя соединен с вторым входомсумматора, выход которого соединен синформационным входом выходного ре"55гистра, выход триггера является вторым выходом арифметического блока,управляющие входы первого и второговходных регистроввторой управляющий вход выходного регистра объединены и являются вторым входом арифметического блока.На фиг, 1 представлена структурная схема предлагаемого устройства; на Фиг. 2 - структурная схема блока управления; на фиг. 3 - функциональная схема блока регистров; на фиг.4 . функциональная схема блока сравнения; на Фиг. 5 - функциональная схема блока счетчиков; на фиг, б -,функциональная схема второго блока памяти; на Фиг. 7 - функциональнаясхема третьего блока памяти; на Фиг, 8 - функциональная схема арифметического блока,Устройство содержит блок 1 счетчиков, блок 2 памяти, блок 3 регист-,ров, блок 1 сравнения, блок 5 регистров, сумматор б, схему 7 сравнения, блоки 8 и 9 памяти, арифметический блок 10, блок 11 управления.Блок 11 управления предназначендля выработки сигналов управленияи тактирующих импульсов.Блок 11 управления содержит генератор 12 тактовых импульсов, триггер 13, элементы И 11-16,триггер 17,элемент И 18, триггеры 19-20, элемент К 21, триггер 22, элемент И 23,триггер 21, элементы И 25 и 26,триггер 27, элемент И 28, триггер 29вательный вариант - показатели степеней переменных одного одночленахранятся в группе ячеек по г показателей в каждой; последовательныйвариант - в одной ячейке хранитсяодин показатель степени.Блок 4 сравнения предназначендля сравнения показателей степенейпеременных, считываемых из блока 21 о памяти и блока 3 регистров. Блок 4сравнения содержит набор схем сравнения по количеству параллельносчитываемых из блока 2 памяти иблока 3 регистров показателей сте 15 пеней переменных и Ы-входовой Элемент ИЛИ. Выходы схем сравненияпоступают на входы элемента ИЛИ, выход которой является выходом блока4 сравнения. Если поступающий наро первый вход любой схемы сравнениякод из блока 2 памяти больше кода,поступающего на второй вход этой жесхемы сравнения из блока 3 регистров, то на выходе схемы сравненияг 5 вырабатывается сигнал, который поступает и на вход блока 4 сравнениячерез схему ИЛИ. При последовательном варианте хранения показателей степеней переменных в блоке 2 .эо памяти блок 4 сравнения содержит однусхему сравнения, выход которой иявляется выходом блока сравнения.Блок 5 регистров включает два несвязанных между собой регистра,пер 35вый иэ которых предназначен для хранения в процессе функционированияустройства номера вычисляемого одночлена результирующегополинома, авторой - для хранения кода.количества коэффициентов исходных полиномов,участвующих в образовании вычисляемого коэффициента результирующегополинома,,Сумматор 6 служит для Формирова 45ния адресов считывания информации изблока 8 памяти. В качестве сумматора6 можно испольэовать любой известныйкомбинационный сумматор.Схема 7 сравнения предназначенадля Фиксирования момента окончания5 Опервого этапа вычисления искомогокоэффициента полинома результата.В устройстве первый выход блока 1счетчиков соединен с входом блока 2памяти, выход которого соединен спервым входом блока 4 сравнения,второй выход блока 1 счетчиков соединен с первым входом блока 11 управления, первый выход которого под.7 922732счетчик 38 - адреса коэффициентоводночленов исходных полиномов,участвующих в образовании вычисляемогоодночлена результирующего полинома,четвертый счетчик 39 - адреса, покоторым в блок 8 памяти записываютсяадреса, формируемые третьим счетчиком 38, пятый счетчик 40 служит дляформирования адресов чтения информации иэ. блока 8 памяти. Блок 8 памятислужит для накапливания адресов,записанных в блоке 9 памяти, коэффициентов при одночленах исходныхполиномов, участвующих в вычисленииодного коэффициента результирующегополинома, и выдачи их в процессефункционирования устройства.Блок 8 памяти содержит (Фиг.б) дваодинаковых оперативных запоминающихустройства 45 и 46, назовем их соответственно первой и второй областьюблока 8 памяти, три.идентичных коммутатора 47-49, два элемента И 50 и51, инвертор 52 и элемент ИЛИ 53.блок 9 памяти служит для хранения коэффициентов исходных и результирующего полиномов, разделен натри области, в первую и вторую изкоторых записываются перед началомработы устройства коэффициенты исходных полиномов, в третью - вычисляемые коэффициенты результирующегополинома.Блок 9 памяти содержит фиг.7)три запоминающих устройства 54-56,названных областями памяти.Арифметический блок 10 преднаэ"начен для вычисления суммы попарныхпроизведении коэффициентов исходныхполиномов при вычислении каждого коэффициента результирующего полинома,Арифметический блок 10 содержитвходные регистры 57 и 58, умножитель59, комбинационный сумматор 60, выходной регистр 61, триггер 62 л элемент 63 задержки,Блок 2 памяти служит для хранения массива показателей степенейпеременных полиномов сомножителей исодержит вход адреса и выход информации, При этом возможны три варианта хранения показателей, от которыхзависит реализация блока 1 счетчиков,первого блока 3 регистров и блока 4сравнения, а также и быстродействиеустройства в целом, Параллельный вариант - все показатели степеней переменных одного одночлена записаныв одной ячейке; параллельно-последо2 10динен с первым входом триггера 19 иявляется вторым входом блока 11 управления, второй вход триггера 13соединен с первыми входами элементов И 15 и 16 и является первым входом блока 11 управления, второй входтриггера 19 соединен с вторым входомэлемента И 14 и выходом триггера 13,второй вход элемента И 15 являетсячетвертымвходом блока 11 управления, ; третий вход элемента И.14 соединен спервым выходом триггера 20, второйвыход которого соединен с вторымвходом элемента И 21, а первыйвход - с выходом элемента И 16,первым входом триггера 17 и являетсяшестым выходом блока 11 управления,третий вход элемента И 15 соединенс первым выходом триггера 17, второйвыход которого соединен с вторымвходом элемента И 16 и первым входомэлемента И 18, выход триггера 19 соединен с вторым входом элемента И 23,третий вход которого соединен с выходом триггера 22, первый вход которого подключен к выходу элемента И 21 и является седьмым выходом.блока 11 управления, первый вход.элемента И, 25 соединен с вторым входом элемента И 28 и является третьимвходом блока 11 управления, а второйвход является пятым входом блока 11управления, третий вход элемента И 28 соединен с первымвыходомтриггера 27, второй выход которогосоединен с третьим входом элемента И 21, первый вход триггера 29.соединен с выходом элемента И 28,второй вход триггера 29 соединен свыходом элемента И 30, второй входкоторого соединен с первым выходомтриггера 29, вторым входом элемента И 26, первый вход триггера 27соединен с выходом элемента И 26, четвертый вход элемента И 28 соединен с вторым выходом триггера 29, выход элемента И 18 является пятымвыходом блока 11 управления, выход элемента И 15 соединен с вторым входом триггера 17, выход элемента И 23 соединен с входом триггера 24, вторыми входами триггеров 20,22 и 27, третьим входом триггера 19, выходы элементов И 14, 15 и 26 объединены и являются первым выходом блока 11 управления, выходы элементов И 25 и 26 и триггера 29 объединены и являются третьим выходом блока 11 управления, выходы элемен 9 92273 ключен к первому входу блока 1 счет. чиков, третий выход которого соединен с первым входом блока 8 памяти, выход блока 9 памяти соединен с первым входом арифметического блока 10, второй вход которого соединен о вторым выходом блока 11 управления, третий выход которого соединен с вторым входом блока 8 памяти и первым входом блока 9 памяти, третий вход 10 блока 8 памяти соединен с четвертым выходом блока 11 управления, пятый выход которого соединен с первым входом блока 3 регистров, выход которого соединен с вторым входом блока 15 4 сравнения, первый выход арифметического блока 10 соединен с вторым входом блока 9 памяти, второй вход блока 11 управления является входом запуска устройства, выход блока 2 ро памяти соединен с вторым входом блока 3 регистров, выход блока сравнения соединен с вторым входом блока 1 счетчиков, третий выход которого соединен с третьим входом блока 3 ре- д 5 гистров, выход блока 8 памяти соединен с третьим входом блока 9 памяти, второй вход арифметического блока 10 соединен с третьим входом блока 1 счетчиков, второй выход арифметического блока 10 соединен с третьим вхо. дом блока 11 управления, четвертый выход блока 1 счетчиков соединен с первыми входами блока 5 регистров, схемы 7 сравнения и четвертым входом блока 8 памяти, выход схемы 7 сравнения соединен с четвертым входом блока 11 управления, пятый вход которого соединен с пятым выходом бло,- ка 1 счетчиков, первым входом сумматора 6 и пятым входом блока 8 памяти, шестой вход которого соединен с выходом сумматора 6, шестой выход блока 1 счетчиков соединен с вторым входом блока 5 регистров и седьмым входом блока 8 памяти, второй вход схемы 7 сравнения соединен с первым выходом блока 5 регистров, второй выход которого соединен с вторым входом сумматора 6, шестой выход блока 11 управления соединен с третьим вхо дом блока 5 регистров, четвертый вход которого соединен с седьмым выходом блока 11 управления и четвертым входом блока 1 счетчиков. В бло 55 ке 11 управления выход генератора 12 тактовых импульсов соединен с входами элементов И 14,21,23,26,28 и 30, первый выход триггера 13 сое14 соответствующий вектор-столбцу Хи являющийся общим для полиномовРф .В блоке 9 памяти в первую и в торую области записываются коэффи ци енты исходных поли номов сомножителей ,упорядоченные согласно с расположением соответствующих им показателейстепеней переменных в блоке 2 памяти .Для первого и второго счетчиков блока 1 счетчиков устанавливаютсякоэффициенты пересчета 3 и и соотв етств енно , все остальные сч етч- к и блока 1 счетчиков и регистры бло ка 5 регистров устанавливается в нулевое состояние .Коэффициенты реэуль тирующе го поли нома Рвыч исляются последовательно , начиная с нулевого до 3 - го .К моменту начала вычисления- го коэффициента четыре первых счетчика блока 1 счетчиков находятся в нуле" вом состоянии . В пятом счетчике блока 1 счетчиков и втором регистре блока 5 регистров записано число Я.-1, где Я - количество коэффициентов полиномов Р и Р, участвующих в образовании 3-1-"го коэффициента полинома Р. В первом регистре блока 5 регистров записано число, равное . В блоке 3 регистров по адресам О - п,-1 записаны показатели степеней переменных при-м одночлене.Первый этап образования коэффициента бвключает +1 цикл сравнения показателей степеней переменных одночленов столбца Х ,начиная с нулевого до-го с показателями степеней соответствующих переменных -го одночлена.При этом на каждом цикле по адресам, формируемым первым счетчиком 36 из блока 2 памяти, считывается .показатели степеней переменных очередного одночлена. Одновременно из блока 3 регистров считываются показатели степеней переменных -го одночлена по адресам, формируемым вторым счетчиком 37. В блоке 4 сравнения происходит их анализ, По достижении вторым счетчиком 37 состояния ивырабатывается сигнал окончания цикла.Если в результате анализа оказывается, что показатели степеней перемвнных очередного одночлена, считываемые на данном цикле из блока 2 памяти, не превышают показателей степеней соответствующих пере 50 13 9227Полиномы Р, Г, Рэ представляютсяв виде таблицыПервая строка таблицы - векторстолбец Х,одночленов результируюКщего полинома, сформированный по 5правилу (1) и представляет соббймассив показателей степеней переменных при одночленах,Как видно, массив показателей яв.ляется общим для всех полиномов, оВекторы Аи Арасширяются доразмерности вектора Ао. за счетвставки нулевых коэффициентов при одночленах, суммарные показатели степеней переменных при которых выше 151, 1 с соответственно.Таким образом, любой из полиномовпредставлен только вектором коэффициентов, которые упорядочены в соответствии с одним массивом показателей 2 остепеней переменных.Алгоритм умножения полиномов осно вывается на. закономерности, вытекаацейиз упорядоченного по правилу (1)расположения одночленов в полиномах,и построен так, что вычисление коэффициентов результирующего полинома(элементов вектора АЗ) осуществляется последовательно, начиная с нулевого и по 3 -й, 30Процедура получения каждого б -гоэлемента вектора Асостоит из двухэтапов:1) Анализируются последовательно,начиная с нулевого по -й одночленывектор-столбца Хпо отношению кИ-му одночлену. При этом происходит.запоминание в порядке возрастанияномеров тех одночленов, степени переменных при которых не превышаютстепеней соответствующих переменныхпри -м одночлене, Обозначим коли-.чество таких номеров через Я.2) Вычисляется коэффициент б йутем сложения Я попарных произведений элементов вектора А с номера-.ми, зафиксированными на предыдущемэтапе и расположенными в порядкевозрастания на элементы вектора Ас теми же номерами, но расположенными по убыванию.Работа алгоритма заканчиваетсяпосле вычисления 4 М -.го коэффициента результирующего полинома.Алгоритм в устройстве реализуетсяследующим образом,Перед началом в блок 2 памятизаносится в упомянутом порядке массив показателей степеней переменных,25 30 сложение результата с ранее накопленной суммой попарных произведений,Состояние пятого счетчика 10 на каждом цикле уменьшается на единицу и35пробегает значения от Я -1 до 0.Сумматор 6 на каждом цикле осуществляет вычитание из кода Я, записанного во втором регистре блока 5регистров, текущего состояния пято 40го счетчика 40, в результате чего наего выходе последовательно формируютсяадреса от 0 до Я. Этимобеспечивается выборка в соответствиис описанным алгоритмом из первойобласти блока 9. памяти коэффициен 45тов полинома Р в порядке убыванияих номеров, а из второй области блока 9 памяти коэффициентов полиномаР в порядке возрастания их номеров,По прохождению Б циклов заверша 4ется вычисление коэффициента а 3в арифметическом блоке 10 как суммыБ попарных произведений. Ло адресуБ, поступающему с выхода сумматора 6, с первой области блока 8 памяти считывается адрес, равный 1,по которому полученный коэффициентОиз арифметйческого блока 10 менных 1-го одночлена, считываемых с блока 3 регистров, то код из счетчика 38, определяющий номер очередного одночлена и являющийся адресом в блоке 9 памяти коэффициента, соответствующего этому одночлену, по сигналу конца цикла заносится по адресу, определяемому четвертым счет чиком 39, в первую область блока 8 памяти, после чего состояние третьего и четвертого счетчиков увеличивается на единицу.В противном случае по сигналу конца цикла происходит только увеличение на единицу состояния третьегосчетчика 37Затем цикл анализа повторяется для следующего одночлена, номер которого сформирован в третьем счетчике 38.На -м (последнем) цикле формирования коэффициента б 3 код состояния третьего счетчика .38 и код, хранимый в первом регистре блока 5 регистров, совпадают, в результате чего в блок 11 управления поступает. сигнал с выхода схемы 7 срав. нения, По окончании 1-го цикла происходит запись кода 1 по адресу Я -1 в блок 8 памяти, увеличение состояния третьего счетчика 38 на единицу. Далее происходит цикл перезаписи показателей степеней переменных при 1+1 коэффициенте, считываемых из блока 2 памяти по адресам, формируемым первым счетчиком 36 в блок 3 регистров по адресам, формируемым вторым счетчиком 37. По окончании перезаписи с выхода второго счетчика 37 поступает импульс конца цикла, по которому код +1 с выхода третьего счетчика 38 переписывается впервый регистр блока 5-регистров,после чего блок 11 управления анализирует состояние арифметического блока 10.Если в арифметическом блоке 10 не завершился второй этап вычисления предыдущего коэффициента 4 ь 1, который начался одновременно с первым этапом образования коэффициента а происходит ожидание его окончания. При фиксировании свободного арифме-. тического блока 10 начинается второй этап вычисления коэффициента 63 и первый этап образования коэффициента 1Этому предшествуют следующие операции: во второй регистр блока 5 регистров и пятый счетчик 10 записывается с выхода четвертого счетчика 39 код Б -1, первый, второй, третий и четвертый счетчики 36-39 устанавливаются в нулевое состояние. Первая область блока 8 памяти переключается с режима записи на режим чтения, а вторая область блока 8 памяти с режима чтения на режим записи для приема адресов коэффициентов полиномов Р и Р,образующих коэфФициент 4 + полинома Р 3.Второй этап вычисления коэффициента а 3 включает Я циклов,на каждом из которых происходит чтение по адресу, поступающему с выхода пятого счетчика 10 из первой области блока 8 памяти адреса, по которому из первой области блока 9 памяти считывается и передается в арифметический блок 10 коэффициент первого полинома сомножителя, а по адресу,Формируемому на выходе сумматора 6,происходит чтение из первой областиблока 8 памяти сумматора, по которо"му из второй области блока 9 памятисчитывается и передается в арифмети-ческий блок 10 коэффициент второгополинома сомножителя. В арифметическом блоке 10 производится перемножение переданных коэффициентов и18 1 счетчиков, увеличивает его состояние на единицу. единичное состояниетриггера 17 разрешает прохождениечерез элемент И 18 импульсов с .выхода элемента И 14, поступающих натретий вход блока 3 регистров и обеспечивающих перезапись в него поступающих с выхода блока 2 памятипоказателей степеней переменных при1+1 коэффициенте, Поступающий напервый вход элемента И 16 следующийимпульс конца цикла проходит на выход элемента и устанавливает триггер.17 в нулевое состояние, триггер 20в единичное, а также, поступая натретий вход блока 5 регистров, обеспечивает.запись кода 1+1 в первыйрегистр. Единичное состояние триггера 20 запрещает прохождение импульсов через элемент И 14 и говоритоб окончании первого этапа вычисления 1-го коэффициента.Окончание второго этапа вычисле-,ния 1-1-го коэффициента Фиксируетсянулевым состоянием триггера 27.Приусловии окончания выполнения первогоэтапа вычисления 1-го коэффициентаи второго этапа вычисления 1-1-гокоэффициента на второй и третий входы элемента И 21 поступают разрешающие уровни, вследствие чего очередной тактовый импульс проходит на выход элемента И 21, который, поступая в блок 1 счетчиков и блок 5 регистров, обеспечивает запись в пятый счетчик 40 и второй регистр кода 5-1 с выхода четвертого счетчика су и устанавливает триггер 22 в единичное состояние, что разрешает прохождение тактового импульса через элемент И 23, по которому производит ся установка в нулевое состояние первого, второго, третьего и четвертого счетчиков 36-39 блока 1 счетчиков, триггеров 20 и 22, установка в единичное состояние триггера 27 и переключение в противоположное состояние триггера 24. Триггер 24 управляет режимами работы первойи второй области блока 8 памяти. После этого начинается первый этап вычисления 1+1-го коэффициента, который протекает аналогично первому этапу вычисления 3-го коэффициента, а также начинается второй этап вычисления 1-го коэффициента. При этом после окончания каждого цикла второго этапа вычисления 3-го коэффициента из арифметического блока 1 О по 55 17 922732записывается,в третью область блока9 памяти.Момент окончания Я циклов фиксируется нулевым состоянием пятогосчетчика 40,5При выполнении первого этапО вычисления последнего коэффициентаФ полинома Г первый счетчик достигает состояние , в результатечего с шестого выхода блока 1 счет Очиков в блок 11 управления поступает сигнал. После этого в арифметическом блоке 10 выполняется второйэтап вычисления коэффициента б, ипроцесс умножения полиномов заканчивается.При этом коэффициенты результирующего полинома записаны в третьейобласти блока 9 памяти в порядке,соответствующем правилу 1). 2 ОБлок 11 управления функционируетследующим образом.Устройство начинает работать после подачи импульса на вход 3 ("Запуск") блока 11 управления. При этом 25триггеры 13 и 19 устанавливаются вединичное состояние, чем разрешается выработка блоком 11 управлениясигналов, обеспечивающих выполнениеустройством описанных последователь;ностей операций на первом и второмэтапах вычисления коэффициентов результирующего полинома.К моменту начала выполнения первого этапа вычисления 1-го коэффициента результирующего полинома исовпадающего с ним момента началавыполнения второго этапа вычисления1-1-го коэфФициента триггеры 17,20,22 и 29 находятся в нулевом состоянии триггер 27 - в единичном состояИ 14нии. При этом на выходе элемента И 1вырабатывается последовательностьтактовых импульсов, поступающих насчетные входы .первого и второгосчетчиков 36 и 37 блока 1 счетчиков,обеспечивающих Формирование адресовчтения информации из блока 2 памятии блока 3 регистров. В момент выполения 1-го цикла первого этапа напервый вход элемента И 15 с выхода.схемы 7 сравнения поступает сигналлогической единицы. Поэтому поступающий по окончании этого цикла свыхода второго счетчика 37 сигналокончания цикла проходит на выходэлемента И 15, устанавливает триггер17 в единичное состояние и, поступаяна вход третьего счетчика 38 блока