Устройство для умножения полиномов Советский патент 1988 года по МПК G06F17/10 G06F15/17 

41

00

ьо

ел

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

Целью изобретения является расширение класса решаемых задач за счет возможности умножения разреженных

; полиномов.

; На.фиг,1 представлена структурная

(схема устройства для умножения полиIНОМОВ} на фиг.2 - схема суммирующе|го блока на фиг.З - схема суммирую-

|щей ячейки.

Устройство содержит М регистров

|1 коэффициентов, М умножителей 2,

|М групп регистров 3, М элементов И 4

:М элементов ИЛИ 5, генератор 6 им-

Iпульсов, М схем 7 сравнения и сумми руюпщй блок 8.

; Суммирующий блок 8 (фиг,2) содер|жит К групп суммирующих 9 (К

), при этом i-H группа сумми-

:рующих ячеек содержит 2

1-1

суммирую|щих ячеек, где ,К. : Суммирующая ячейка 9 (фиг. 3) со- :держит схему 10 сравнения, коммутатор 11, два ключа 12 и сумматор 13, ал : Устройство предназначено для ум- -. ножения полиномов.

ii

Полином Р(х) У а X задаетi t

:СИ списком пар, состоящих из ненуле- 35 вого коэффициента и соответствующего ему показателя степени переменной х

(а, J,), (а, j,).. (а„, j«,), ; где j удовлетворяет условиям 40 Y К, 1 е N, JK Je,

1 i 4М,

45

.i; 3 LSVvSSs

При умножении полинома Р(х) и по

.KI

muiotia Q(x) . b . х , представлен1 1,ного списком пар

(bi. К,), (b,j, Кр,...,(Ь, Kf,), 50

в результате получают полином

р

А(х) - P(x).Q(x) с;

1-1

которьй представляется списком пар 55

(с,, h), (с, h),..,, (Ср, hp) где hj 7 h I,., , i 1,Р,

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

В соответствии с частотой генератора 6 импульсов на информационный вход устройства последовательно поступают коэффициенты первого полинома Р(х), заданные в виде списка пар ненулевых коэффициентов и соответствующих показателей степеней. Пары коэффициентов второго полинома Q(x) хранятся в регистрах 1 коэффициентов Каждый из регистров 1 поделен на две части, соответствующие разрядам коэффициента и разрядам показателя степени. Во время поступления на инфор- мационньй вход устройства пар первого полинома на управляющий вход устройства подается сигнал логической 1. После поступления пар коэффициентов на управляющий вход устройства подается сигнал О, Каждая групп регистров 3 состоит из п последовательно соединенных регистров, где п - число пар первого полинома, В умножителях 2 реализуется умножение пар коэффициентов, т.ё, каждый умножител 2 состоит из двухвходового умножителя двух чисел и сумматора. При этом сумматор реализует сложение показателей степеней соответствующих двух пар. Результаты умножения, т.е. пары чисел, последовательно записьюаются в регистры 3 групп в соответствии с частотой генератора 6, Регистры в группе расположены последовательно. В каждом такте работы устройства в суммирующем блоке 8 осуществляется суммирование коэффициентов, записанных в группах регистров 3, которые имеют одинаковые показатели степени. Процесс суммирования (слияния) коэффициентов начинается от максимального показателя степени с коэффициентом, отличным от нуля. Суммирующий блок работает в параллельно-последовательном режиме и состоит из суммирующих ячеек У.

Суммирзпощая ячейка работает следующим образом.

Схема 10 сравнения осуществляет сравнение показателей степеней двух пар. Если первый показатель больше второго, то на выходе схемы 10 сравнения появляется комбинация Ш, в противном случае на.выходе присутствует комбинация 0.1, Когда показатели степени равны между собой, на выходе схемы 10 сравнения появляется

комбинация 11. В случае равенства показателей степеней соответствующих пар на вьрсоде коэффициентов суммирующей ячейки присутствует двоич- ньй код суммы соответствующих коэффициентов. В противном случае на выход ячейки поступает коэффициент с максимальным показателем степени, а на выход порядка - собственно код этого показателя степени. В схемах 7 сравнения параллельно осуществляется сравнение показателей степеней пар, хранящихся в п-х (выходных) регистрах 3 (в разрядах показателя степени групп, с показателем степени вьиис- ленного в данном такте коэффициента полинома, поступающего с выхода порядка суммирующего блока 8. В случае

подключены к выходам групп разрядов порядка п-х регистров соответствующих групп, где п - порядок полинома множителя, выход генератора импульсов соединен с вторыми входами всех элементов И, вторые входы всех элементов ИЛИ соединены с входом разрещения загрузки устройства, выход j-ro ре- гистра каждой группы, где j 1, 2, ..., п-1, соединен с информационным входом (j+1)-ro регистра той же группы, причем блок суммирования содержит К групп суммирующих ячеек, где К log М, при этом в i-й группе суммирующих ячеек содержится 2 суммирующих ячеек, где i 1,2,...,К, входы первого и второго коэффициентов 1-й суммирующей ячейки

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных комплексах и специализированных устройствах, в частности в устройствах цифровой обработки сигналов.Цель изобретения - расширение класса решаемых задач. Устройство для умножения полиномов содержит М регистров коэффициентов, суммирующий блок, гене- - ратор импульсов, М умножителей, М групп регистров, М схем сравнения, М злементов И и М элементов ИЛИ. Данное устройство реализует операцию умножения полиномов, представленных в виде списка пар, состоящих из ненулевого козффициента и соответствзто- щего ему показателя степени переменной. 3 ил. iS (Л

авенства происходит сдвиг информации 20 Р-й

1 вет (21суммперв сумм нены венн ячее и вт рующ ... пы р ров груп ков соот дами К-й ки п вход коэф ки с вани ячей ключ кото сумм вход отве дами ячей втор мута соед го к нени ход нен

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

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

Устройство для умножения полиномов, содержащее М регистров коэффициентов, где М - порядок полинома множимого, суммирующий блок и генератор импульсов, причем выход суммы суммирующего блока соединен с выходом устройства, отличающееся тем, что, с целью расширения области применения за счет умножения разреженных полиномов, в него введены М умножителей, М групп регистров, М элементов И, М элементов ИЛИ и М схем сравнения, причем информационный вход устройства соединен с первыми входами всех умножителей, вторые входы Которых соединены с выходами соответствующих регистров коэффициентов, выходы всех умножителей соединены с информационными входами первых регистров соответствующих групп, входы синхронизации регистров которых объединены и подключены к выходам соответствующих элементов И, первые входы которых соединены с выходами соответствующих элементов ИЛИ, первые входы которых соединены с выходами соответствующих схем сравнения, первые входы которых

0 Р-й

5

5

О

0

5

0

5

группы, где р 1, 2,..., К-1, 1 1, 2,..., 2 , соединены соответственно с выходом коэффициента (211)-й и выходом коэффициента 21-й суммирующих ячеек (р+1)-й группы, первый и второй входы порядков 1-й суммирующей ячейки р-й группы соединены с вьЕХодами порядков соответственно (21-1)-и и 21-й суммирующих ячеек (р+1)-й группы, входы первого и второго коэффициентов S-й суммирующей ячейки К-й группы, ,2,..., ...,2 , соединены с выходами группы разрядов коэффициентов п-х регистров соответственно (2S-1)-x и 2S-X груп п, выходы групп разрядов порядков п-х регистров которых соединены соответственно с первым и вторым входами порядков S-й суммирующей ячейки К-й группы, выход порядка первой ячейки первой группы соединен с вторыми входами всех схем сравнения, выход коэффициента первой суммирующей ячейки соединен с выходом блока суммирования, причем каждая суммирующая ячейка содержит схему сравнения, два ключа, сумматор и коммутатор, выход которого соединен с выходом порядка суммирующей ячейки, первьй и второй входы порядков которой соединены соответственно с первым и вторым входами схемы сравнения суммирующей ячейки и соответственно с первым и вторым информационными входами коммутатора, управляю1ций вход которого соединен с управляющим входом первого ключа и первым выходом схемы сравнения суммирующей ячейки, второй выход схемы сравнения которой соединен с управляющим входом второго клю5 14325546

ча, информационные входы первого и иены соответственно с входами rfep- Bl-oporo ключей соединены с входами , вого и второго слагаемых сумматора, соответственно первого и второго ко- выход которого соединен с выходом эффициентов суммирующей ячейки, вы- коэффициента суммирующего блока. хЬды первого и второго ключей соеди иг,1

уффф

УУХУ W

фф ф)

w

LiL

W

Ф

Ф У

м

ш

:iL

-ff

9иг. 2

Вы)(од Риг.З