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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социапнстических

Республик (и)922732 (б1) Дополнительное к авт. свнд-ву (22) Заявлено 24. 03. 80 (21) 2904755/18-24 с присоединением заявки М (23 ) Приоритет. (51)М. Кл.

G 06 F 7/52 (ввуаврстванный квинтет

СССР вв делам изобретений н открытий

Опубликовано 23.04.82. Бюллетень ЭВ 15 (53) УДК 681.325 (088. 8) Дата опубликования описания 23. 04. 82

М.П. Батура и В.А. Птичкин (72) Авторы изобретения

Я

Минский радиотехнический институт "" (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПОЛИНОМОВ. МНОГИХ ПЕРЕМЕННЫХ

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

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

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

3 92273 с четвертым выходом блока управления, пятый выход KOTopol o соединен с первым входом первого блока регистров, выход которого соединен с вторым входом блока сравнения, первый выход арифметического блока соединен с вторым входом третьего блока памяти,второй вход блока управления является входом запуска устройства,23.

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

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

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

Зо

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

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

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

9227 и элемент И 30.

Блок 3 регистров служит для хранения показателей степеней переменных вычисляемого одночлена результирующего полинома в процессе функционирования устройства.

Блок 3 регистров содержит п регистров 31-1-31-и и два дешифратора

32 и 33.

Блок 4 сравнения содержит и схем

34-1 — 34-п и и-входовой элемент ИЛИ 35.

Блок 1 счетчиков содержит пять счетчиков 36-10, из которых первый

36 и второй 37 с управляемым коэфФициентом пересчета, схему управления счетчиком 39, которая содержит элемент И 41, триггер 42, элемент

И 43 и элемент М задержки. Первый счетчик 36 предназначен для Формирования адресов чтения из блока 2 памяти показателей степеней переменных исходных полиномов, второй счетчик

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

5 входом пятого элемента И, первый вход восьмого триггера соединен с выходом девятого элемента И, второй вход восьмого триггера соединен с выходом десятого элемента И, второй вход которого соединен с первым выходом восьмого триггера, вторым входом восьмого элемента И, первый вход седьмого триггера соединен с выходом восьмого элемента И, четвертый вход 10 девятого элемента И соединен с вторым выходом воСьмого триггера, выход четвертого элемента И является пятым выходом блока управления, выход второго элемента И соединен с вторым 15 входом второго триггера, выход шес того элемента И соединен с входом шестого триггера, вторыми входами чет" вертого, пятого и седьмого триггеров, третьим входом третьего триггера,вы- 2 ходы первого, второго и шестого элемента И объединены и являются первым выходом блока управления, выходы седьмого и восьмого элементов И и восьмого триггера объединены и яв- 25 ляются третьим выходом блока управления, выходы девятого и десятого элементов И объединены и являются вто. рым выходом блока управления, выход шестого триггера является четвертым выходом блока управления.

При этом арифметический блок содержит два входных регистра, умножитель, элемент задержки, триггер,сумматор, выходной регистр, причем информационные входы первого и второго входных регистров объединены и являются первым входом. арифметического блока, управляющий вход второго входного регистра соединен с входом эле- 40 мента задержки, выход которого соединен с управляющим входом триггера и первым управляющим входом выходного регистра, выход которого соединен с первым входом сумматора и является первым выходом арифметического блока, информационный вход триггера соединен с управляющим входом первого входного регистра, выход которого соединен с первым входом умножителя„ второй вход которого соединен с выходом второго входного регистра, выход. умножителя соединен с вторым входом сумматора, выход которого соединен с информационным входом выходного ре55 гистра, выход триггера является вторым выходом арифметического блока, управляющие входы первого и второго входных регистров,.второй управляю32 6 щий вход выходного регистра объединены и являются вторым входом арифметического блока.

На фиг. 1 представлена структурная схема предлагаемого устройства; на фиг. 2 - структурная схема блока управления; на фиг. 3 - функциональная схема блока регистров; на фиг.4Функциональная схема блока сравнения, на Фиг. 5 - функциональная схема блока счетчиков; на фиг. б -, функциональная схема второго блока памяти; на фиг. 7 - функциональная схема третьего блока памяти; на

Фиг. 8 - функциональная схема арифметического блока.

Устройство содержит блок 1 счетчиков, блок 2 памяти, блок 3 регист-, ров, блок 4 сравнения, блок 5 регистров, сумматор б, схему 7 сравнения, блоки 8 и 9 памяти, арифметический блок 10, блок ll управления.

Блок 11 управления предназначен для выработки сигналов управления и тактирующих импульсов.

Блок 11 управления содержит генератор 12 тактовых импульсов, триггер 13, элементы И 14-16,триггер 17, элемент И 18, триггеры 19-20, элемент К 21, триггер 22, элемент И 23, триггер 24, элементы И 25 и 26, триггер 27, элемент И 28, триггер 29 вательный вариант - показатели степеней переменных одного одночлена хранятся в группе ячеек no r показателей в каждой; последовательный вариант — в одной ячейке хранится один показатель степени.

Блок 4 сравнения предназначен для сравнения показателей степеней переменных, считываемых из блока 2

1о памяти и блока 3 регистров. Блок 4 сравнения содержит набор схем сравнения по количеству параллельно считываемых из блока 2 памяти и блока 3 регистров показателей степеней переменных и w-входовой элемент ИЛИ. Выходы схем сравнения поступают на входы элемента ИЛИ, выход которой является выходом блока

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

Блок 5 регистров включает два не связанных между собой регистра,пер35 вый иэ которых предназначен для хранения в процессе функционирования устройства номера вычисляемого одночлена результирующего полинома, а второй — для хранения кода.количества коэффициентов исходных полиномов, участвующих в образовании вычисляемого коэффициента результирующего полинома. ,Сумматор 6 служит для формирова45 ния адресов считывания информации из блока 8 памяти. В качестве сумматора

6 можно испольэовать любой известный комбинационный сумматор.

Схема 7 сравнения предназначена для фиксирования момента окончания

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

В устройстве первый выход блока 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 и выходом триггера l3, второй вход элемента И 15 является четвертым входом блока 11 управления, ; третий вход элемента И.14 соединен с первым выходом триггера 20, второй выход которого соединен с вторым входом элемента И 21, а первый вход - с выходом элемента И 16,первым входом триггера 17 и является шестым выходом блока 11 управления, третий вход элемента И 15 соединен с первым выходом триггера 17, второй выход которого соединен с вторым входом элемента И 16 и первым входом элемента И 18, выход триггера 19 соединен с вторым входом элемента И 23, третий вход которого соединен с выходом триггера 22, первый вход которого подключен к выходу элемента И 21 и является седьмым выходом блока 11 управления, первый вход. элемента И, 25 соединен с вторым входом элемента И 28 и является третьим входом блока 11 управления, а второй вход является пятым входом блока ll управления, третий вход элемента И 28 соединен с первым выходом триггера 27, второй выход которого соединен с третьим входом элемента И 21, первый вход триггера 29. соединен с выходом элемента И 28, второй вход триггера 29 соединен с выходом элемента И 30, второй вход которого соединен с первым выходом триггера 29, вторым входом элемента И 26, первый вход триггера 27 соединен с выходом элемента И 26, четвертый . вход элемента .И 28 соединен с вторым выходом триггера 29, выход элемента И 18 является пятым выходом блока ll управления, выход элемента И 15 соединен с вторым входом триггера 17, выход элемента И 23 соединен с входом триггера

24, вторыми входами триггеров 20,22 и 27, третьим входом триггера 19, выходы элементов И 14, 15 и 26 объединены и являются первым выходом блока 11 управления, выходы weментов И 25 и 26 и триггера 29 объединены и являются третьим выходом блока 11 управления, выходы элемен9 92273 ключен к первому входу блока 1 счетчиков, третий выход которого соединен с первым входом блока 8 памяти, выход блока 9 памяти соединен с первым входом арифметического блока 10, второй вход которого соединен е вторым выходом блока 11 управления, третий выход которого соединен с вторым входом блока 8 памяти и первым входом блока 9 памяти, третий вход te блока 8 памяти соединен с четвертым выходом блока 11 управления, пятый выход которого соединен с первым входом блока 3 регистров, выход которого соединен с вторым входом блока 15

4 сравнения, первый выход арифметического блока 10 соединен с вторым входом блока 9 памяти, второй вход блока ll управления является входом запуска устройства, выход блока 2 рв памяти соединен с вторым входом блока 3 регистров, .выход блока сравнения соединен с вторым входом блока

1 счетчиков, третий выход которого соединен с третьим входом блока 3 ре- д5 гистров, выход блока 8 памяти соединен с третьим входом блока 9 памяти, второй вход арифметического блока 10 соединен с третьим входом блока l счетчиков, второй выход арифметического блока 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 сое2732 12

Здесь А„={а„р, ак,... < 1р ) — коэффициенты первого полинома сомножителя;

Р. =(4 4,."аМ ) —. Коэф фициенты второго полинома сомножите5 ля, AA% хд30 а3.1, °,. а 3р ) - коэффициенты результирующего полинома; . Х„, Хх, .....,Х „ - независимые переменные;

11-,1 ц,.....,1 nj — показатели степеней переменных при j-м коэффициенте полинома;

II, - число независимых перемен15

3S

1 П

ll 5

11 92 тов И 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.

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

Пусть необходимо умножить полино-. мы

r-=À Х "= Х "0Х""О-Х" п0+ц Х ".X «хх

1 1п=

I а4 +- +a ° 4 - Х Qj..X " + +4 X" " X 99. Х

n "

" î "aC.. по+ =А Х„=g

Ф

1п1 111 i1}i 1п3 щ хЪ% ххХ y...+6 .X „.Х, -Xn +.;.еа,„Х„.Х

n " j ных;

II,ц,Й вЂ” число коэффициентов (одночленов) в первом, втором исходных и результирующем полиноиах соответственно;

k<, k<, k3 - наивысшие суммарные показатели степеней переменных при одном коэффициенте соответственно первого, второго и третьего полиномов;

Х - вектор-столбец одночленов и по переменным Х„,X,....,Õ,, суммарная степень которых не превышает ky, аналогичный смысл. имеют и векторстолбцы Х„", Х,1 .

Переменные в каждом одночлене вектор-столбцов Х„", Х „, Х„ распок к3 лагаются в одном и том же порядкеХ 1х Х х ° ° i ° е хХпе

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

m cI1

Х"„= (X Х", Х (1) Например, при k„=1, kg=2, kg=3 и п=2 вектор-столбцы упорядоченные по правилу (1), имеют вид

1 пя

-.- X n т.е. получить Ь F1% Ч где

Р.Д Х 2 Х«Х ..Х " +а X" " Х "-Х"" "

3 3 и 301 Q. n 311:Ъ

И; 11д 1Ы пЕ

+4 Х, Х, "Х„ ...х 6 Х Х g "Х п

ХХс,Х,ХХ) ; ХХ-(AIX@IXq ХХ,Х„ХХ,ХХ), 50 3„(l 3 Ч. l 37

Х = 1,ХХ},Х„,.Х„,Х,Х„Х,},К„,Х Д„Х,Х .

Размерности рд, к векторов д „, А

А 3 определяются величинами k„,k,} З соответственно, количеством переменных и и вычисляются по формуле, апример для k n „.,! п К " 1 1

32 соответствующий вектор-столбцу Х > и являющийся общим для полиномов

Г1 ?. F 3

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

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

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

К моменту начала вычисления j-го коэффициента четыре первых счетчика блока 1 счетчиков находятся в нулевом состоянии. В пятом счетчике блока 1 счетчиков и втором регистре блока 5 регистров записано число

S .1-1, где S . „ - количество коэффициентов полиномов F „ и Еа, участвующих в образовании j-1-"го коэффициента полинома Fy. В первом регистре блока 5 регистров записано число, равное j. В блоке 3 регистров по адресам О - n-1 записаны показатели степеней переменных при

j-м одночлене.

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

При этом на каждом цикле по адресам, формируемым первым счетчиком

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

Если в результате анализа оказывается, что показатели степеней перемвнных очередного одночлена, считываемые на данном цикле из блока 2 памяти, не превышают показателей степеней соответствующих пере50

13 9227

Полиномы F1 Fi, F3 представляются в виде таблицы

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

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

Векторы А „ и А расширяются до размерности вектора An за счет вставки нулевых коэффициентов при од ночленах, суммарные показатели степеней переменных при которых выше 15

k, ky соответственно.

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

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

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

1) Анализируются последовательно, начиная с нулевого по j-й одночлены вектор-столбца Х „ по отношению к

И

1-му одночлену. При этом происходит. запоминание в порядке возрастания номеров тех одночленов, степени переменных при которых не превышают степеней соответствующих переменных при j-м одночлене. Обозначим коли-. чество таких номеров через S>, 2) Вычисляется коэффициент 6 llgтем сложения S попарных произведений элементов вектора А с номера-. ми, зафиксированными на предыдущем этапе и расположенными в порядке возрастания на элементы вектора А с теми же номерами, но расположенными по убыванию.

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

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

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

922732

16 вается с выхода четвертого счетчика

39 код Б -1, первый, второй, третий и четвертый счетчики 36-39 устанавливаются в нулевое состояние. Первая область блока 8 памяти переключается с режима записи на режим чтения, а вторая область блока 8 памяти с режима чтения на режим записи для приема адресов коэффициентов полиномов F и F,oáðàçóþùèõ коэффициент a >+

Второй этап вычисления коэффициента а у включает S ° циклов,на каждом из которых происходит чтение по адресу, поступающему с выхода пятого счетчика 40 из первой области блока 8 памяти адреса, по которому из первой области блока 9 памяти считывается и передается в арифметический блок 10 коэффициент первого менных 1-го одночлена, считываемых с блока 3 регистров, то код из счетчика 38, определяющий номер очередного одночлена и являющийся адресом в блоке 9 памяти коэффициента, соответствующего этому одночлену, по сигналу конца цикла заносится по адресу, определяемому четвертым счет чиком 39, в первую область блока 8 памяти, после чего состояние третьего и четвертого счетчиков увеличивается на единицу.

В противном случае по сигналу конца цикла происходит только увеличение на единицу состояния третьего счетчика 37.

Затем цикл анализа повторяется для следующего одночлена, номер которого сформирован в третьем счетчике 38.

На j-м (последнем) цикле формирования коэффициента d y код состояния третьего счетчика 38 и код, хранимый в первом регистре блока

5 регистров, совпадают, в результате чего в блок 11 управления поступает, сигнал с выхода схемы 7 сравнения. Ilo окончании j-ro цикла происходит запись кода 1 по адресу S -1 в блок 8 памяти, увеличение состояния третьего счетчика 38 на единицу.

Далее происходит цикл перезаписи показателей степеней переменных при

j+1 коэффициенте, считываемых из блока 2 памяти по адресам, формируемым первым счетчиком 36 в блок 3 регистров по адресам, формируемым вторым счетчиком 37. По окончании перезаписи с выхода второго счетчика 37 поступает импульс конца цикла, по которому код j+1 с выхода третьего счетчика.38 переписывается в первый регистр блока 5-регистров, после чего блок 11 управления анализирует состояние арифметического бло ка 10. Если в арифметическом блоке 10 не завершился второй этап вычисления предыдущего коэффициента 4 ь ql, который начался одновременно с первым этапом образования коэффициента a> ° происходит ожидание его окончания.

При фиксировании свободного арифме-. тического блока 10 начинается второй этап вычисления коэффициента 6 и первый этап образования коэффициента

Этому предшествуют следующие операции: во второй регистр блока 5 регистров и пятый счетчик 40 записы5

35

Ло полинома сомножителя, а по адресу, Формируемому на выходе сумматора 6, происходит чтение из первой области блока 8 памяти сумматора, по которо" му из второй области блока 9 памяти считывается и передается в арифмети- i ческий блок 10 коэффициент второго полинома сомножителя. В арифметическом блоке 10 производится перемножение переданных коэффициентов и

Зо сложение результата с ранее накопленной суммой попарных произведений.

Состояние пятого счетчика 40 на каждом цикле уменьшается на единицу и

Э5 пробегает значения от Я -1 до О.

Я Сумматор 6 на каждом цикле осуществляет вычитание из кода Я -1, записанного во втором регистре блока 5 регистров, текущего состояния пято40 го .счетчика 40, в результате чего на

его выходе последовательно формируются адреса от 0 до Я -1. Этим обеспечивается выборка в соответствии с описанным алгоритмом из первой области блока 9. памяти коэффициен45 тов полинома F в порядке убывания их номеров, а из второй области блока 9 памяти коэффициентов полинома

F в порядке возрастания их номеров.

Ilo прохождению S. циклов заверша4 ется вычисление коэффициента а в арифметическом блоке 10 как суммы

S попарных произведений. flo адресу

S -1, поступающему с выхода сумматора 6, с первой области блока 8 памяти считывается адрес, равный j„ по которому полученный коэффициент

0 у из арифметического блока 10

1 счетчиков, увеличивает его состояние на единицу. Единичное состояние триггера 17 разрешает прохождение через элемент И 18 импульсов с выхода элемента И 14, поступающих на третий вход блока 3 регистров и обес. печивающих перезапись в него поступающих с выхода блока 2 памяти показателей степеней переменных при

j+1 коэффициенте. Поступающий на первый вход элемента И 16 следующий импульс конца цикла проходит на выход элемента и устанавливает триггер.

17 в нулевое состояние, триггер 20 в единичное, а также, поступая на третий вход блока 5 регистров, обеспечивает.запись кода j+1 в первый регистр. Единичное состояние триггера 20 запрещает прохождение импульсов через элемент И 14 и говорит об окончании первого этапа вычисления j-ro коэффициента.

Окончание второго этапа вычисле-, ния j-1-го коэффициента фиксируется нулевым состоянием триггера 27.При условии окончания выполнения первого этапа вычисления j-го коэффициента и второго этапа вычисления j-1-ro коэффициента на второй и третий входы элемента И 21 поступают разрешающие уровни, вследствие чего очередной тактовый импульс проходит на выход элемента И 21, который, поступая в блок 1 счетчиков и блок 5 регистров, обеспечивает запись в пятый счетчик 40 и второй регистр кода

S -1 с выхода четвертого счетчика су и устанавливает триггер 22 в единичное состояние, что разрешает прохождение тактового импульса через элемент И 23, по которому производит. ся установка в нулевое состояние первого, второго, третьего и четвертого счетчиков 36-39 блока 1 счетчиков, триггеров 20 и 22, установка в единичное состояние триггера 27 и переключение в противоположное состояние триггера 24. Триггер 24 управляет режимами работы первой и второй области блока 8 памяти. После этого начинается первый этап вычисления j+1-го коэффициента, который протекает аналогично первому этапу вычисления j"ãî коэффициента, а также начинается второй этап вычисления j-го коэффициента. При этом после окончания каждого цикла второго этапа вычисления 3-го коэффициента из арифметического блока 10 по35

17 922732 записывается,в третью область блока

9 памяти.

Момент окончания S циклов фиксируется нулевым состоянием пятого счетчика 40.

При выполнении первого этапО вычисления последнего коэффициента

4 полинома Г первый счетчик достигает состояние 3, в результате чего с шестого выхода блока 1 счет- 10 чиков в блок ll управления поступает сигнал. После этого в арифметическом блоке 10 выполняется второй этап вычисления коэффициента ц, и .процесс умножения полиномов закан- 15 чивается.

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

Блок 11 управления функционирует следующим образом.

Устройство начинает работать после подачи импульса на вход 3 ("Запуск") блока ll управления. При этом 25 триггеры 13 и 19 устанавливаются в

1 единичное состояние, чем разрешается выработка блоком 11 управления сигналов, обеспечивающих выполнение устройством описанных последователь; ностей операций на первом и втором этапах вычисления коэффициентов результирую4 его полинома.

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

j-1-ro коэффициента триггеры 17 20, 22 и 29 находятся в нулевом состоянии триггер 27 - в единичном состоят

И 14 нии. При этом на выходе элемента И вырабатывается последовательность тактовых импульсов, поступающих на счетные входы .первого и второго счетчиков 36 и 37 блока 1 счетчиков, обеспечивающих формирование адресов чтения информации из блока 2 памяти и блока 3 регистров. В момент выпол- ения j-го цикла первого этапа на первый вход элемента И 15 с выхода. схемы 7 сравнения поступает сигнал логической единицы. Поэтому поступающий по окончании этого цикла с выхода второго счетчика 37 сигнал окончания цикла проходит на выход элемента И 15, устанавливает триггер

17 в единичное состояние и, поступая на вход третьего счетчика 38 блока

22732 20

19 9 ступает сигнал готовности на второй и третий входы элементов И 25 и 28 соответственно. Триггер 29 находится в нулевом состоянии, поэтому очередной тактовый импульс проходит через элемент И 28.

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

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

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

29 устанавливается в единичное состояние. При этом сигнал готовности в арифметическом блоке 10 снимается.

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

9 памяти.

Поступающий очередной тактовый импульс проходит на выход элемента

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

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

Поступающий с выхода элемента

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

После завершения первого этапа вычисления последнего 3 -го коэффициента результирующего полинома сос30

5$ тояние первого счетчика 36 блока 1 счетчиков достигает значения 0, равного коэффициенту пересчета, поэтому на его выходе вырабатывается импульс окончания последнего этапа, который, поступая на четвертый вход блока 11 управления (второй вход триггера 13), устанавливает триггер 13 в нулевое состояние, запрещающее прохождение импульсов через элемент И 14 и выработку сигналов, обеспечивающих выполнение первого этапа. Нулевой уровень с выхода триггера 13 поступает также на второй вход (D-вход) триггера 19, поэтому по импульсу с выхода элемента И 23, запускающему устройство на выполнение второго этапа вычисления последнего коэффициента, триггер 19 устанавливается в нулевое состояние. Это запрещает в дальнейшем выработку сигнала на выходе элемента И 23 и работу устройства после окончания выполнения второго этапа вычисления последнего

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

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

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

Таким образом, по сравнению с известным в предлагаемом устрой1 стве повышается быстродействие за счет исключения выполнения pxqxn one. раций сложения показателей степеней переменных; исключения многократного сдвига содержимого третьего блока памяти, так как отпадает операция приведения подобных одночленов; исключения операций сравнения суммарных показателей степеней переменных при одночленах результирующего полинома со значением k > в случае задания точности результата k 3 (k + k „; совмещения во времени. операций сравнения показателей степеней переменных и вычисления коэффициентов результирующего полинома °

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

21 922732 22

av(p+q)-v ячеек, так как отпадает линомах сомножителях. Здесь v, - конеобходимость хранения массивов пока- личество ячеек блока 8 памяти. Оно зателей степеней переменных при по- значительно меньше ax(p+q)

4) ly »1 ) 1% 1И Ч

Вектор А1

Вектор А . Ректор А

10!

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

Степени переменных 10 10 по 1 1М. t1

1. Устройство для умножения полиномов многих переменных, содержащее три блока памяти, арифметический блок, первый блок регистров, блок сравнения, блок счетчиков и блок управления, причем первый выход .. блока счетчиков соединен с входом первого блока памяти, выход которого соединен с первым входом блока срав- 25 нения, второй выход блока счетчиков соединен с первым входом блока управления, первый выход которого подключен к первому входу блока счетчиков, третий выход которого соединен с пер- 30 вым входом второго блока памяти, вы.ход третьего блока памяти соединен с первым входом арифметического блока, второй вход которого соединен с вторым выходом блока управления, 35 третий выход которого соединен с вторым входом второго блока памяти и первым входом третьего блока памя- ти, третий вход второго блока памяти соединен с четвертым выходом блока управления, пятый выход которого соединен с первым входом первого блока регистров, выход которого соединен с вторым входом блока сравнения, первый выход арифметического блока

45 соединен с вторым входом третьего блока памяти, второй вход блока управления является входом запуска ! устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстро50 действия, в него введены второи блок регистров, сумматор и схема сравнения, причем выход первого блока памяти соединен с вторым входом первого блока регистров, выход блока сравнения соединен с вторым входом

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

2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок управления содержит генератор тактовых импульсов, восемь триггеров, десять элементов И, причем выход генератора тактовых импульсов соединен с первыми входами первого, пятого, шестого, восьмого, девятого и десятого элементов И, первый вход первого триггера соединен с первым входом третьего триггера и является вторым входом блока управления, второй вход первого триггера соединен с первыми входами второго и третьего элементов И и является первым входом бло23 92273 ка управления, второй вход третьего триггера соединен с вторым входом первого элемента И и выходом первого триггера, второй вход второго элемента И является четвертым входом блока управления, третий вход первого элемента И соединен с первым выходом четвертого триггера, второй выход которого соединен с вторым входом пятого элемента И, а 10 первый вход - с выходом третьего элемента И, первым входом второго триггера и является шестым выходом блока управления, третий вход второго элемента И соединен с первым выходом >s второго триггера, второй выход которого соединен с вторым входом третьего элемента И и первым входом четвертого элемента И, выход третьего триггера соединен с вторым входом рВ шестого элемента И, третий вход которого соединен с выходом пятого триггера, первый вход которого подключен к выходу пятого элемента И и является седьмым выходом блока управления, первый вход седьмого weмента И соединен с вторым входом девятого элемента И и является третьим входом блока управления, а второй вход является пятым входом блока управления, третий вход девятого эле- . мента И соединен с первым выходом седьмого триггера, второй выход которого соединен с третьим входом пятого элемента И, первый вход восьмого триггера соединен с выходом девятого элемента И, второй вход восьмого триггера соединен с выхо-. дом десятого элемента И, второй вход которого соединен с первым выходом восьмого триггера, вторым входом восьмого элемента И, первый вход седьмого триггера соединен- с Выходом восьмого элемента И, четвертый вход девятого элемента И соединен с вторым выходом восьмого триггера, выход четвертого элемента И является пятым выходом блока управления, выход второго элемента И соединен с вторым входом второго триггера, выход шестого элемента И соединен с входом шестого триггера, вторыми входами четвертого, пятого и седьмого триггеров, третьим входом третьего триггера, выходы первого, второго и шестого элементов И объединены и являются первым выходом блока управления, выходы седьмого, восьмого элементов И и восьмого триггера объединены и являются третьим выходом блока управления, выходы девятого и десятого элементов И объединены и являются вторым выходом блока управления, выход шестого триггера является четвертым выходом блока управления.

3. Устройство по п.1, о т л и" ч а ю щ е е с я тем, что арифметический блок содержит два входных регистра, умножитель, элемент задержки, триггер, сумматор, выходной регистр, причем информационные Входы первого и второго входных регистров объединены и являются первым вхо дом арифметического блока, управляющий вход второго входного регистра соединен с входом элемента задержки, выход которого соединен с управляющим входом триггера и перВым управляющим ВхОдОм ВыхОднОГО ре гистра, Выход которого соединен с первым входом сумматора .и является первым выходом арифметического блока, информационный вход триггера, соединен с управляющим входом, первого входного регистра, выход которого соединен с первым входом

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

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

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

It 450168; кл. G 06 F 7/52, 1974.

2. Авторское свидетельство СССР по заявке У 2598893/18-24, кл. G 06 F 7/39, 1978 (прототип) .

922732

Составитель Л. Медведева

Техред И. Гайду Корректор М. Коста

Редактор В. Данко

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

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

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

Заказ 2581/63 филиал ППП "Патент", r. Ужгород, ул. Проектная,4