Устройство для умножения полиномов многих переменных Советский патент 1982 года по МПК G06F7/52 

(k} УСТРОЙСТВО для УМНОЖЕНИЯ полиномов

. многих ПЕРЕМЕННЫХ

1

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

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

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

Наиболее близким техническим решением к изобретению является устройство для умножения, содержащее три блока памяти, арифметический блок, первый блок регистров, блок сравнения, блок счетчиков и блок управления, причем первый выход блока счетчиков соединен с входом первого блока памяти, выход которого соединен с первым входом блока сравнения, второй выход блока счетчика соединен с первым входом блока управления, первый выход которого подключен к первому входу блока счетчиков, третий выход которого соединен с первым

ts входом второго блока памяти, выход третьего, блока памяти соединен с первым входом арифметического блока, второй вход которого соединен с вторым выходом блока управления, третий

20 выход которого соединен с вторым входом второго блока памяти и первым входом третьего блока памяти, третий вход второго блока памяти соединен

с четвертым выходом блока управления пятый выход которого соединен с первым входом первого блока регистров, выход которого соединен с вторым входом блока сравнения, первый выход арифметического блока соединен с вторым входом j-peTbero блока памяти,второй вход блока управления является входом запуска устройства 23.

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

Недостатком данного устройства является также большой объем памяти, необходимый для хранения показателей степеней переменных каждого полинома сомножителя и результирующего полинома .

Цель изобретения - повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство введены второй блок регистров, сумматор и схема сравнения, причем выход первого блок памяти соединен с вторым входом первого блока регистров, выход блока сравнения соединен с вторым входом блока счетчиков, третий выход которого соединен с третьим входом первого блока регистров, выход второго блока памяти соединен с третьим входом третьего блока памяти, второй вход арифм.етического блока соединен с третьим входом блока счетчиков, второй выход арифметического блока соединен с .третьим входом блока управления, четвертый выход блока счетчиков соединен с первыми входами второго блока регистров, схемы сравнения и четвертым входом второго блока памяти, выход схемы сравнения соединен с четвертым входом блока управления,- пьтый вход которого соединен с пятым выходом блока счеЧчиков, первым входом сумматора и пятым входом второго блока памяти, шестой вход которого соединен с выходом сумматора, шестой выход блока счетчиков соединен с вторым входом

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

Кроме того, блок управления содержит генератор тактовых импульсов, восемь триггеров, десять элементов И причем выход генератора тактовых импульсов соединен с первыми входами первого, пятого, шестого, восьмого, девятого-и десятого элементов И, первый вход первого триггера соединен с первым входом третьего триггера и является вторым входом блока управления, второй вход первого триггера соединен с первыми входами второго и третьего элементов Ни является первым входом блока управления, второй вход третьего триггера соединен с вторым,входом первого элемента И и выходом первого триггера, второй в.ход второго элемен ра И является четвертым входом блока управления, третий вход первого элемента И соединен с первым выходом четвертого триггера, второй выход которого соединен с вторым входом пятого элемента И, а первый, вход с выходом третьего элемента И,первым входом второго триггера и является шестым выходом блока управления, третий вход второго элемента И соединен с первым выходом второго триггера , второй выход которого соединен с вторым входом третьего элемента И и первым входом четвертого элемента И, выход третьего триггера соединен с вторым входом шестого элемента И, третий вход которого соединен с выходом пятого триггера, первый вход которого подключен к выходу пятого элемента И и является седьмым выходом блока управления, первый вхо седьмого элемента И соединен с вторым входом девятого элемента И и является третьим входом блока управления, а второй вход является пятым входом блока управления., третий вход девятого элемента Исоединен с первым выходом седьмого триггера,второй выход которого соединен с третьим ВХОДОМ пятого элемента И, первый вход восьмого триггера соединен с ходом девятого элемента И, второй вход восьмого триггера соединен с ходом десятого элемента И, второй вход которого соединен с первым выхо дом восьмого триггера, вторым входом восьмого элемента И, первый вход седьмого триггера соединен с выходом восьмого элемента И, четвертый вход девятого элемента И соединен с вторым выходом восьмого триггера , вуход MeTseptjaro элемента И является пятым выходом блока управл ения, выход второго элемента И соединен с вторым входом второго триггера, выход шестого элемента W соединен с входом ше того триггера, вторЫми входами чет вертого, пятого и седьмого триггеров третьи 1 входом треть.его триггера,выходы первого, второго и шестого элемента И объединены и являются первым выходом блока управления, седьмого и восьмого элементов И и восьмого триггера объединены и являются третьим выходом блока управления, выходы девятогоИ десятого элементов И объединены и являются вт рым выходом блока управления, выход шестого триггера является четвертым выходом блохауправления. При 3toM арифметический блок содержит два входных ре гистра, умножитель, элемент задержки, триггер,сунматор, выходной регистр, причем информационные входь первого и второго входных регистров объединены Si являются первым ВХОДОМ арифметического блока, управляющий вход второго вход ного регистра соединён с входом элемента задержки, выход которого соеди нен с управляющим входом триггера и первым управляющим входом выходного регистра, выход которого соединен с первым входом сумматора и является первым выходом арифметического блока, информационный вход триггера соединен с управляющим входом первог входного регистра, выход которого соединен с первым входом умножителя,, второй вход которого соединен с выхо дом второго входного регистра,выход умножителя соединен с вторым входом сумматора, выход которого соединен с информационным входом выходного регистра , выход триггера является erciрым выходом арифметического блока, управляющие входы первого и второго входных регистров, второй управляющий вход выходного регистра объединены и являются вторым входом арифметического блока. На фиг, 1 представлена структурная схема предлагаемого устройства; на фиг, 2 - структурная схема блока управления; на фиг, 3 - функциональная схема блока регистров; на фиг. функциональная схема блока сравнения; на фиг. 5 - функциональная схема блока счетчиков; на фиг. 6 -, функциональная схема второго блока памяти; на фиг. 7 - Функциональная схема третьего блока памяти; на фиг. 8 - функциональная схема арифметического блока, Устройство содержит блок 1 счетчиков, блок 2 памяти, блок 3 регистт ров, блок i сравнения, блок 5 регистров, сумматор 6, схему 7 сравнения, блоки 8 и 9 памяти, арифметический блок 10, блок 11 управления. Блок 1 управления предназначен для выработки сигналов управления и тактирующих импульсов. Блок 1Т управления содержит генератор 12 тактовых импульсов, гер 13, элементы И 14-16,триггер 17 элемент И 18, триггеры 19-20, элемент И 21, триггер 22, элемент И 23, триггер 2, элементы И 25 и 26, триггер 27, элемент И 28, триггер 29 и элемент И ЗИ. Блок 3 регистров служит для хранения показателей степеней переменных вычисляемого одночлена результирующего полинома в процессе функционирования устройства. Блок 3 регистров содержит п регистров 31-1--31-П и два дешифратора 32 и 33. Блок t сравнения содержит п схем 3i4-1-34-п и п-входовой элемент ИЛИ 35. Блсж 1 счетчиков содержит пять счетчиков , из которых первый 36и второй 37 с управляемь м коэффициентом пересчета, схему управления счетчиком 39, которая содержит элемент И k , триггер 42, элемент И 43 и элемент 44 задержки,Первый счетчик 36 предназначен для формирования адресов чтения из блока 2 памяти пoкaзateлeй степеней переменных исходных полиномов, второй счетчик 37формирует адреса выборки из блока 3 регистров показателей степеней переменных вычисляемого одночлена результирующего полинома, третий счетчик 38 - адреса коэффициентов одночленов исходных полиномов,участ вующих в образовании вычисляемого одночлена результирующего полинома, четвертый счетчик 39 - адреса, по которым в блок 8 памяти записываютс адреса, формируемые третьим счетчиком 38, Пятый счетчик 0 служит для формирования адресов чтения информа ции из блока 8 памяти. Блок 8 памят служит для накапливания адресов, записанных в блоке 9 памяти, коэффициентов при одночленах исходных полиномов, участвующих в вычислении одного коэффициента результирующего полинома, и выдачи их в процессе функционирования устройства. Блок 8 памяти содержит (фиг.6) д одинаковых оперативных запоминающих устройства 5 и 46, назовем их соот ветственно первой и второй областью блока 8 памяти, три идентичных коммутатора , два элемента И 50 и 51, инвертор 52 и элемент ИЛИ 53Блок 9 памяти служит для хранения коэффициентов исходных и резуль тирующего полиномов, разделен на три области, в первую и вторую из которых записываются перед началом работы устройства коэффициенты исход ных полиномов, в третью - вычисляемые коэффициенты результирующего полинома. Блок 9 памяти содержит (фиг.7) три запоминающих устройства , названных областями памяти. Арифметический блок 10 предназначен для вычисления суммы попарных произведении коэффициентов исходных полиномов при вычислении каждого коэ фициента результирующего полинома. Арифметический блок 10 содержит входные регистры 57 и 58, умножитель 59) комбинационный сумматор 60, выходной регистр б1, триггер 62 и элеме(нт 63 задержки. Блок 2 памяти служит для хранения массива показателей степеней переменных полиномов сомножителей и содержит вход адреса и выход информации. При этом возможны три варианта хранения показателей, от которых зависит реализация блока 1 счетчиков первого блока 3 регистров и блока k сравнения, а также и быстродействие устройства в целом. Параллельный вариант - все показатели степеней переменных одного одночлена записаны в одной ячейке; параллельно-последо28вательный вариант - показатели степеней переменных одного одночлена хранятся в группе ячеек по г показателей в каждой; последовательный вариант - в одной ячейке хранится один показатель степени. Блок k сравнения предназначен для сравнения показателей степеней переменных, считываемых из блока 2 памяти и блока 3 регистров. Блок 4 сравнения содержит набор схем сравнения по количеству параллельно считываемых из блока 2 памяти и блока 3 регистров показателей степеней переменных и w-входовой элемент ИЛИ. Выходы схем сравнения поступают на входы элементаИЛИ, выход которой является выходом блока Ц сравнения. Если поступающий на первый вход любой схемы сравнения код из блока 2 памяти больше кода, поступающего на второй вход этой же схемы сравнения из блока 3 регистров , то на выходе схемы сравнения вырабатывается сигнал, который поступает и на вход блока Ц сравнения через схему ИЛИ. При последовательном варианте хранения показ.ателей степеней переменных в блоке 2 памяти блок сравнения содержит одну схему сравнения, выход которой и является выходом блока сравнения. Блок 5 регистров включает два не связанных между собой регистра,первый из которых предназначен для хранения в процессе функционирования устройства номера вычисляемого одночлена;результирующего полинома, а второй - для хранения кода количества коэффици енТов исходных полиномов, участвующих в образовании вычисляемого коэффициента результирующего полинома. .Сумматор 6 служит для формирования адресов считывания информации из блока В памяти. В качестве сумматора 6 можно использовать любой известный комбинационный сумматор. Схема 7 сравнения предназначена для фиксирования момента окончания первого этапа вычисления искомого коэффициента полинома результата. 8 устройстве первый выход блока 1 счетчиков соединен с входом блока 2 памяти, ВЫХОД которого соединен с первым входом блока k сравнения, второй выход блока 1 счетчиков соединен с первым входом блока 11 управления, первый выход которого подключей к первому входу блока 1 счетчиков, третий выход которого соединен с первым входом блока 8 памяти, выход блока 9 памяти соединен с первым входом арифметического блока 10, второй вход которого соединен о вторым выходом блока 11 управления, третий выход которого соединен с вто- , рым входом блока 8 памяти и первым входом блока 9 памяти, третий вход блока 8 памяти соединен с четвертым выходом блока 11 управления, пятый выход которого соединен с первым входом блока 3 регистров, выход которого соединен с вторым входом блока k сравнения, первый выход арифметического блока 10 соединен с вторым входом блока 9 памяти, второй вход блока 11 управления является входом запуска устройства, выход блока 2 памяти соединен с вторым входом блока 3 регистров, выход блока сравнения соединен с вторым входом блока 1 счетчиков, третий выход которого Соединен с третьим входом блока 3 ре гистров, выход блока 8 памяти соединен с третьим входом блока 9 памяти, второй вход арифметического блока Ю соединен с третьим входом блока 1 счетчиков, второй выход арифметического блока 10 -соединен с третьим вхо дом блока 11 управления, четвертый выход блока 1 счетчиков соединен с первыми входами блока 3 регистров, схемы 7 сравнения и четвертым входом блока 8 памяти, выход схемы 7 сравнения соединен с четвертым входом блока 11 управления, пятый вход которого соединен с пятым выходом блО,КЗ 1 счетчиков, первым входом сумматора 6 и пятым входом блока 8 памяти шестой вход которого соединен с выходом сумматора 6, шестой выход блока 1 счетчиков соединен с вторым входом блока 5 регистров и седьмым входом блока 8 памяти, второй вход схемы 7 сравнения соединен с первым выходом блока 5 регистров, второй вы ход которого соединен с вторым входом сумматора 6, шестой выход блока 11управления соединен с третьим вхо дом блока 5 регистров, четвертый вход которого соединен с седьмым выходом блока 11 управления и четвертым входом блока 1 счетчиков. В блоке 1 1 управления выход генератора 12тактовых импульсов соединен с входами элементов И 1,21,23,26,28 и 30, первый выход триггера 13 соединен с первым входом триггера 19 и является вторым входом блока 11 управления, второй вход триггера 13 соединен с первыми входами элементов И 15 и 16 и является первым входом блока 11 управления, второй вход триггера 1$ соединен с вторым входом элемента И И и выходом триггера 13, второй вход элeмeнta И 15 является

четвертым входом блока 11 управления, третий вход элемента И 1 соединен с первым выходом триггера 20, второй выход которого соединен с вторым входом элементу И 21, а первый

вход - с выходом элемента И 16,первым входом триггера 17 и является шестым выходом блока 11 управления, третий вход элемента И 15 соединен с первым выходом триггера 17, второй

выход котсч ого соединен с вторым входом элемента И б и первым входом элемента И 1в, выход триггера 19 соединен с вторым входом элемента И 23, третий вход которого соединен с выходом триггера 22, первый вход которого подключен к выходу элемента И 21 и является седьмым выходом блока 11 упраепения, первый вход; элемента И 25 соединен с вторым вхоДО элемента И 28 и является третьим входом блока И управления, а второй вход является пятым входом блока 11 управления, третий вход элемента И 28 соединен с первым выходом триггера 27, вtopoй выход которого соединен -с третьим входом элемента И 21, первьи) вход триггера 29 соединен с выходом элемента И 28, второй вход триггера 29 соединен с выходом элемента 14 30, второй вход которого соединен с первым выходом триггера 29, вторым входом элемента И 2б, первый вход триггера 27 соединен с выходом элемента И 2б, четвертый вход элемента И 28 соединен с вторым выходом триггера 29, выход элемента И 18 является пятым выходом блока 11 управления, выход элемента И 15 соединен с вторым входом триггера 17, выход элемента И 23 соединен с входом триггера 2, вторыми входами триггеров 20,22 и 27, третьим входом триггера 19, выходы элементов И 1, 15 и 26 объединены и являются первым выходом блока 11 управления, выходы элементов И 25 и 26 и триггера 29 объединены и являются третьим выходом блока 11 управления, выходы элементов и 28 и 30 объединены и являются вторым выходом блока 11 управления, выход триггера 24 является четвертым выходом блока 11 управления. В арифметическом блоке 10 информационные входы входных регистров 57 и 58 объединены и являются первы входом арифметического блока 10, управляющий вход регистра 58 соединен с входом элемента 63 задержки, выход которого соединен с управляющим входом триггера 62 и первым управляющим входом выходного регистра 61, выход которого соединен с первы входом сумматора 60 и является первым выходом арифметического блока 10, информационный вход триггера 62 соединен с управляющим входом входн го регистра 57, выход которого соединен с первым входом умножителя 59, второй вход которого соединен с выходом входного регистра 58, выход умножителя 59 соединен с вторым входом сумматора 60, выход которого соединен с информационным входом выходного регистра 61, выход триггера 62 является вторым выходом ари метического блока 10, управляющие входы входных регистров 57 и 58 ивторой управляющий вход выходного регистра 61 объединены и являются вторым входом арифметического блока 10. Устройство работает следующим об разом . Пусть необходимо умножить полино V- ,x;. С--,Г - Vi- r

«vio..jo,

-x:V..o,i4,......x.

vH

т.е. получить

Fa Ft Р-:

где

v; s/rC C-%c-4 «rF.4 - i -C- -.-««;-«T- ; л

х; (х;. х;.х;;).

(1)

Например, при , k(, и

бектор-столбцы упорядоченные по , правилу (1), имеют вид

1(,VV Ч) 1 (ji -t 1 Ч Уг а)

0. V й i ij-i f(г Л й Размерности p,q, 6 векторов А), Aij, . АЗ определяются величинами. k,ki2,k2 соответственно, ко/ ичеством переменных пи вычисляются по формуле, например .,

2 Здесь .A ( d,... c p ) - коэффициенты первого полинома сомножителя; (Ь, (ii--iv фициенты второго полинома сомножителя; а, ... а 38 )- коэффициенты результирующего полинома; Х, Х(2, независимые переменные; ; Д|у,.... .,i nj - показатели степеней переменных при j-м коэффициенте полинома; п - число независимых переменных;p,q, число коэффициентов (одночленов) в первом, втором исходных и результирующем полиномах соответственно;k, k(j, kj - наивысшие суммарные показатели степеней переменных при одном коэффициенте соответственно первого, второго и третьего полиномов; ,; Xj - вектор-столбец одночленов по переменным Х Д,.... ,Xj,, суммарная степень которых не превышает kj, аналогичный смысл имеют и векторстолбцы XJ, Х, Переменные в каждом одночлене вектор-столбцов , Х располагаются в одном и том же порядке Дтт -I 4} Необходимым условием выполнения алгоритма умножения полиномов п независимых переменных, реализуемого на предлагаемом устройстве, является расположение одночленов в векторстолбцах Х, , одном и том же порядке. При этом одночлены упорядочиваются таким образом, что при, п

Полиномы F , Frj, РЗ представляютс в виде таблицы

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

Как видно, массив показателей является общим для всех полиномов.

Векторы А и A(j расширяются до размерности вектора А за счет вставки нулевых коэффициентов .при од ночленах, суммарные показатели степеней переменных при которых выше k-|, k( соответственно.

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

Алгоритм умножения полиномов основывается на. закономерности, вытекающ из упорядоченного по правилу (1) расположения одночленов в полиномахj и построен так, что вычисление коэффициентов результирующего полинома (элементов вектора Aj) осуществляется последовательно, начиная с нулевого и по -и.

Процедура получения каждого элемента вектора Аз состоит из двух этапов:.

1)Анализируются последовательно, начиная с нулевого по j-й одночлены вектор-столбца Х по отношению к j-му одночлену. При этом происходит, запоминание в порядке возрастания номеров тех одночленов, степени переменных при которых не превышают степеней соответствующих переменных при J-M одночлене. Обозначим количество таких номеров через Sj.

2)Вычисляется коэффициент Qjj Путем сложения Sj попарных произведеНИИ элементов вектора 1 с номера-.

ми, зафиксированными на предыдущем этапе и расположенными в порядке возрастания на элементы вектора А(j с теми же номерами, но расположенными по убыванию.

Работа алгоритма заканчивается после вычисления коэффициента результирующего полинома.

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

Перед началом в блок 2 памяти заносится в упомянутом порядке массив показателей степеней переменных.

соответствующий вектор-столбцу Х и являющийся o6uiy(tA для полиномов Р, Р(З,И РЗв блоке 9 памяти в первую и вторую области записываются коэффициенты исходных полиномов сомножителей, упорядоченные согласно с расположением соответствующих им показателей степеней переменных в блоке 2 памяти

Для первого и второго счетчиков блока 1 счетчиков устанавливаются коэффициенты пересчета 6 и п соответственно, все осталь.ные счетч1ки блока 1 счетчиков и регистры блока 5 регистров устанавливаются в нулевое состояние.

Коэффициенты результирующего полинома F вычисляются последовательно, начиная с нулевого до Е-го.

К моменту начала вычисления j-ro коэффициента четыре первых счетчика блока 1 счетчиков находятся в нуле.вом состоянии. В пятом счетчике блока 1 счетчиков и втором регистре блока 5 регистров записано число S,-,-1, где S j., - количество коэффициентов полиномов р и Р(, участвующих в образовании j-1-го коэффициента полинома Pj В первом регистре блока 5 регистров записано число, равное j. Б блоке 3 регистров по адресам О - п-1 записаны показатели степеней переменных при J-M одночлене.

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

При этом на каждом цикле по адресам , формируемым первым счетчиком 36 из блока 2 памяти, счить1ваются показатели степеней переменных очередного одночлена. Одновременно из блока 3 регистров считываются показатели степеней переменных j-ro одночлена по адресам, формируемым вторым счетчиком 37- В блоке k сравнения происходит их анализ. По достижении вторым счетчиком 37 состояния п-1 вырабатывается сигнал окон|.)с1ния цикла.

Если в результате анализа оказывается, что показатели степеней переменных очередного одночлена, считываемые на данном цикле из блока 2 памяти, не превышают показателей степеней соответствующих переменных j-ro одночлена, считываемых с блока 3 регистров, то код из счет чика 38, определяющий номер очередного одночлена и являющийся адресом в блоке 9 памяти коэффициента, соот ветствующего этому одночлену, по сигналу конца цикла заносится по ад ресу, определяемому четвертым счетчиком 39) в первую область блока 8 памяти, после чего состояние третье го и четвертого счетчиков увеличива ется на единицу, В противном случае по сигналу ко ца цикла происходит только увеличение на единицу состояния третьего счетчика 37. Затем цикл анализа повторяется для следующего одночлена, номер которого сформирован в третьем счетчике 38. На J-M (последнем) цикле формирования коэффициента с« jj состояния третьего счетчика 38 и код, хранимый в первом регистре блока 5 регистров, совпадают, в результате Чего в блок 11 управления поступает сигнал с выхода схемы 7 сра нения. По окончании j-го цикла происходит запись кода j по адресу блок 8 памяти, увеличение состояния третьего счетчика 38 на единицу Далее происходит цикл перезаписи по .казателей степеней переменных при J+1 коэффициенте, считываемых из блока 2 памяти по адресам, формируемым первым счетчиком 36 в блок 3 регистров по адресам, формируемым вторым счетчиком 37. По окончании перезаписи с выхода второго счетчика 37 поступаетимпульс конца цикла по которому код J+1 с выхода третьего счетчика.38 переписывается в первый регистр блока 5 регистров, после чего блок 11 управления анали зирует состояние арифметического бл ка 10. Если в арифметическом блоке 10 н завершился второй этап вычисления предыдущего коэффициента , который начался одновременно с первым этапом образования коэффициента q. происходит ожидание его окончания. При фиксировании свободного арифме-: тичёского блока 10 начинается втсрой этап вычисления коэффициента cijj и первый этап образования коэффициента С11,Ц41) Этому предшествуют следующие операции: во второй регистр блока 5 регистров и пятый счетчик kO записы9.16 вается с выхода четвертого счетчика 39 код S:-1, первый, второй, третий А X м и четвертый счетчики 36-39 устанавливаются в нулевое состояние. Первая область блока 8 памяти переключается с режима записи на режим чтения, а вторая область блока 8 памяти с режима чтения на режим записи для приема адресов коэффициентов полиномов F И F(2,образующих коэффициент Я(|4,) полинома РЗВторой этап вычисления коэффициента включает Sj циклов,на каждом из которых происходит чтение по адресу, поступающему с выхода пятого счетчика +0 из первой области блока 8 памяти адреса, по которому из первой области блока 9 памяти считывается и передается в арифметический блок 10 коэффициент первого полинома сомножителя, а по адресу, формируемому на выходе сумматора 6, происходит чтение из первой области блока 8 памяти сумматора, по которому из второй области блока 9 памяти считывается и передается в арифмети- ческий блок 10 коэффициент второго полинома сомножителя. В арифметическом блоке 10 производится перемножение переданных коэффициентов и сложение результата с ранее накоп-, ленной суммой попарных произведений. Состояние пятого счетчика 0 на каждом цикле уменьшается на единицу и пробегает значения от Sj-1 до 0. Сумматор 6 на каждом цикле осуществляет вычитание из кода S;-1, записанного во втором регистре блока 5 регистров, текущего состояния пятого -счетчика 40, в результате чего на его выходе последовательно формируются адреса от О до Sj-1. Этим обеспечивается выборка в соответствии с описанным алгоритмом из первой области блока 9 памяти коэффициентов полинома F-) в порядке убывания их номеров, а из второй области блока 9 памяти коэффициентов полинома F ( в порядке возрастания их номеров. По прохождению Sj циклов завершается вычисление коэффициента cij/i в арифметическом блоке 10 как суммы Sj попарных произведений. По адресу Sj-1, поступающему с выхода сумматора 6, с первой области блока 8 памяти считывается адрес, равный j, по которому полученный коэффициент О Зл арифметического блока 10 записывается .в третью область блока 9 памяти. Момент окончания Sj циклов фиксируется нулевым состоянием пятого счетчика 40. При выполнении первого этапа вычисления последнего коэффициента jg полинома РЗ первый счетчик достигает состояние В, в результате чего с шестого выхода блока 1 счетчиков в блок 11 управления поступает сигнал. После этого в арифметическом- блоке 10 выполняется второй этап вычисления коэффициента t и процесс умножения полиномов заканчивается. . коэффициенты результирующего полинома записаны в третьей области блока 9 памяти в порядке, соответствующем правилу (1). Блок 11 управления функционирует следующим образом. Устрой-ство начинает работать пос ле подачи импульса на вход 3 (Запуск) блока 11 управления. При это триггеры 13 и 19 устанавливаются в единичное состояние, чем разрешается выработка блоком 11 управления сигналов, обеспечивающих выполнение устройством описанных последователь ностей операций на первом и втором этапах вычисления коэффициентов результирующего полинома. К моменту начала выполнения первого этапа вычисления j-ro коэффициента результирующего полинома и совпадающего с ним момента начала выполнения второго этапа вычисления J-1-го коэффициента триггеры 17,20, 22 и 29 находятся в нулевом состоянии , триггер 27 - в единичном состо нии. При этом на выходе элемента И вырабатывается последовательность тактовых импульсов, поступающих на счетные входы .первого и второго счетчиков 36 и 37 блока 1 счетчикое обеспечивающих формирование адресов чтения информации из блока.2 памяти и блока 3 регистров. 8 момент выпол нения j-ro цикла первого этапа на. первый вход элемента И 15 с выхода схемы 7 сравнения поступает сигнал логической единицы. Поэтому поступающий по окончании этого цикла с выхода второго счетчика 37 сигнал окончания цикла проходит на выход элемента И 15, устанавливает тригге 17 в единичное состояние и, поступа на вход третьего счетчика 38 блока 1 счетчиков, увеличивает его состояние на единицу. Единичное состояние триггера 17 разрешает прохождение через элемент И 18 импульсов с выхода элемента И 14, поступающих на третий вход блока 3 регистров и об.еспечивающих перезапись в него поступающих с выхода блока 2 памяти показателей степеней переменных при J+1 коэффициенте. Поступающий на первый вход элемента И 16 следующий импульс конца цикла проходит на выход элемента и устанавливает триггер. 17 в нулевое состояние, триггер 20 в единичное, а также, поступая на третий вход блока. 5 регистров, обеспечивает запись кода J+1 в первый регистр. Единичное состояние триггера 20 запрещает прохождение импульсов через элемент И 14 и говорит об окончании первого этапа вычисления j-ro коэффициента. Окончание второго этапа вычислет йия j-l-rp коэффициента фиксируется нулевым состоянием триггера 27..При условии окончания выполнения первого этапа вычисления j-ro коэффициента и второго этапа вычисления j-1-го коэффициента на второй и третий входы элемента И 21 поступают разрешающие уровни, вследствие чего очередной тактовый импульс проходит на выход элемента И 21, который, поступая в блок 1 счетчиков и блок 5 регистров, обеспечивает запись в пятый счетчик 40 и второй регистр кода Si.-1 с выхода четвертого счетчика 39 и устанавливает триггер 22 в единичное состояние, что разрешает прохождение тактового импульса через элемент И 23, по которому производится установка в нулевое состояние первого, второго, третьего и четвертого счетчиков 36-39 блока 1 счетчиков, триггеров 20 и 22, установка в единичное состояние триггера 27 и переключение в противоположное состояние триггера 24. Триггер 24 управляет режимами работы первой и второй области блока 8 памяти. После этого начинается первый этап вычисления j+1 -го коэффициента, который протекает аналогично первому этапу вычисления j-ro коэффициента, а также начинается второй этап вычисления j-ro коэффициента. При этом после окончания каждого цикла второго этапа вычисления j-ro коэффициента из арифметического блока 10 поступает сигнал готовности на второй и третий входы элементов И 25 и 28 соответственно. Триггер 29 находится в нулевом состоянии, поэтому очередной тактовый импульс проходит через элемент И 28.

Низкий уровень, поступающий с первого выхода триггера 29, обеспечивает выборку информации из блока

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

По импульсу с выхода элемента И 28 этот коэффициент принимается в арифметический блок 10, а триггер 29 устанавливается в единичное состояние. При этом сигнал готовности в арифметическом блоке 10 снимается Поступающий с первого выхода триггера 29 высокий сигнал обеспечивает выборку информации по адресу, формируемому сумматором 6, из блока 8 памяти и выборку коэффициента второго полинома из второй области блока

9памяти.

Поступающий очередной тактовый импульс проходит на выход элемента I 30, чем обеспечивает прием коэффициента второго полинома в арифметический блок 10, уменьшение состояния пятого счетчика 40 на единицу и установка триггера 29 в нулевое состояние.

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

Поступающий с выхода элемента И 25 высокий уровень обеспечивает в блоке 8 памяти выбор ячейки в соответствии с кодом S:-1, поступающим с выхода сумматора 6, и выбор третьей области блока 9 памяти. Очередной тактовый импульс проходит через элемент И 26, обеспечивая при этом запись полученного коэффициента результирующего полинома, и устанавливает триггер 27 в нулевое состояние, фиксирующее окончание второго этапа.

После завершения первого этапа вычисления последнего В-го коэффициента результирующего полинома состояние первого счетчика 36 блока 1 счетчиков достигает значения 5, равного коэффициенту пересчета, поэтому на его выходе вырабатывается импульс окончания последнего этапа, который, поступая на четвертый вход блока 11 управления (второй вход триггера 13), устанавливает триггер 13 в нулевое состояние, запрещающее прохождение

0 импульсов через элемент И I и выработку сигналов, обеспечивающих выполнение первого этапа. Нулевой уровень с выхода триггера 13 поступает также на второй вход (D-вход)

5 триггера 19, поэтому по импульсу с выхода элемента И 23, запускающему устройство на выполнение второго , этапа вычисления последнего коэффициента, триггер 19 устанавливается

в нулевое состояние. Это запрещает в дальнейшем выработку сигнала на выходе элемента И 23 и работу устройства после окончания выполнения второго этапа вычисления последнего

2-го коэффициента результирующего полинома до поступления следующего сигнала на вход Запуск.

Показатели степеней переменных могут располагаться последовательно

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

Таким образом, по сравнению с известным 6 предлагаемом устройстве повышается быстродействие за счет исключения выполнения pxqxn операций сложения показателей степеней переменных; исключения многократного сдвига содержимого третьего блока памяти, так как отпадает операция приведения подобных одночленов; исключения операций сравнения суммарных показателей степеней переменных при одночленах результирующего-полинома со значением k в случае задания точности результата k j k п + k ,; совмещения во времени, операций сравнения показателей степеней переменных и вычисления коэффициентов результирующеГО полинома.

В предлагаемом устройстве достигается экономия ббъема памяти на

2192273222

гсс(P+Q)У ячеек, так как отпадает линомах сомножителях. Здесь Vp - конеобходимость хранения массивов пока- личество ячеек блока 8 памяти Оно зателей степеней переменных при по- значительно меньше iix(p+q). Степени по И-1 Ч1 переменных ГЮ 10

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

блока памяти соединен с третьим входом третьего блока памяти, второй

15 вход арифметического блока соединен с третьим входом блока счетчиков, второй выход арифметического блока соединен с третьим входом блока управления, четвертый выход блока

0 счетчиков соединен с первыми входами второго блока регистров, схемы сравнения и четвертым входом второго блока памяти, выход схемы сравнения соединен с четвертым входом бло5к управления,пятый вход которого соединен с пятым выходом блока счеТчиков, первым входом сумматора и пятым входом второго блока памяти, шестой вход которого соединен с

0 выходом сумматора, шестой выход блока счетчиков соединен с вторым входом второго блока регистров и седьмым входом второго блока памяти,второй вход схемы сравнения соединен с пер5вым выходом второго блока регистров, второй выход которого соединен с вторым входом сумматора, шестой выход блока управления соединен с третьим входом второго блока регист0ров , четвертый вход которого соединен с седьмым выходом блока управления и четвертым входом блока счетчиков .

ка управления, второй вход третьего триггера соединен с вторым входом первого элемента И и выходом первого триггера, второй вход второго элемента И является четвертым входом блока управления, третий вход первого элемента И соединен с первым выходом четвертого триггера, второй выход которого соединен с вторым входом пятого элемента И, а первый вход - с выходом третьего элемента И, первым входом второго триггера и является шестым выходом блока управления, третий вход второго элемента И соединен с первым выходом второго триггера, второй выход которого соединен с вторым входом третьего элемента И и первым входом четвертого элемента И, выход третьего триггера соединен с вторым входом шестого элемента И, третий вход которЬго соединен с выходом пятого триггера, первый вход которого подключен к выходу пятого элемента И и является седьмым выходом блока управления, первый вход седьмого элемента И соединен с вторым входом девятого элемента И и является третьим входом блока управления, а второй вход является пятым входом блока управления, третий вход девятого элемента И соединен с первым выходом седьмого триггера, второй выход которого соединен с третьим входом пятого элемента И, первый вход восьмого триггера соединен с выходом девятого элемента И, второй вход восьмого триггера соединен с выходом десятого элемента И, второй вход которого соединен с первым выходом восьмого триггера, вторым входом восьмого элемента Hj первый вход седьмого триггера соединен с выходом восьмого элемента И, четвертый вход девятого элемента И соединен с вторым выходом восьмого триггера,выход четвертого элемента И является пятым выходом блока управления, выход второго элемента И соединен с вторым входом второго триггера, выход шестого элемента И соединен с входом шестого триггера, вторыми входами четвертого, пятого и седьмого триггеров, третьим входом третьего триггера, выходы первого, второго и шестого элементов И объединены и являются первым выходом блока управления, выходы седьмого, восьмого элементов И и восьмого триггера объединены и являются третьим выходом блока управления, выходы девятого и десятого элементов И объединены и являются вторым выходом блока управления, выход шестого триггера является четвертым выходом блока управления.

S управляющим входом триггера и первым управляющим входом выходного регистра, выход которого соединен с первым входом сумматора ,и является первым выходом арифметического бЛо0 ка, информационный вход триггера, соединен с управляющим входом первого входного регистра, выход которого соединен с первым входом умножителя, второй вход которого

5 соединен с выходом второго входного регистра, выход умножителя соединен с вторым ВХОДОМ-сумматора, выход которого соединен с информационным входом выходного регистра, выход

0 триггера является вторым выходом арифметического блока, управляющие входы первого и второго входных регистров, второй управляющий вход выходного регистра объединены и

5 являются вторым входом арифметического блока.

Источники информации, принятые во внимание при экспертизе

Фиг.2

Фиг. 6

Фиг.8