Устройство для умножения многочленов Советский патент 1980 года по МПК G06F7/44 

(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МНОГОЧЛЕНОВ

Изобретение относится к области вычислительной техники и может быть применено, например, в специализированных вычислительных устройствах для нахождения произведения операндов, представленных многочленами. Известны вычислительные устройства для формирования коэффициентов многочлена .|. ,равного произведению многЬ Рлена 5. на мно гочлен S ВьХ 11 . Эти устройства представляют собо универсальные ЦВМ, а в дчисление ко в фициентов многочлена устройствах выполняется путем реал зации соответствующей программы. Однако программному способу вычисле ния присущи такие недостатки, как низкое быстродействие и сравнитель но большие аппаратурные затраты на реализацию универсальной ЦВМ при о нобительно низкой эффек1 ивности их использования. Наиболее близким к заявляемому является устройство , содержащее п+1 регистров коэффициентов первог многочлена, п-И регистров коэффициентов второго мйбгочлена и п+1 накапливающих сумматоров, имеющих цепи сдвига, регистры результата блок анализа разрядов операндов, блок сдвига, коммутатор и блок управления 2 . Это устройство.лишено недостатков, присущих устройствам 1 так как операция умножения многочленов реализована в нем аппаратно. Однако известное устройство также имеет невысокое быстродействие, которое можно определить по формуле Ti (n+l)p (t +tc|i) n - степень перемножаемых многочленовр - разрядность А; и время сдвига tt- время суммирования. Цель изобретения - увеличение быстродействия известного устройст Поставленная |цель достигается тем, что в устройство для умножения многочленов, содержащееП+1 регистров коэффициентов первого многочлена, регистров коэффициентов второго многочлена и П+1 накапливающих сумматоров, введены п+1 дешифраторов, входами связанных с выходами разрядов накапливающих сумматоров, и распределитель сигналов, соединенный с

управляющими входами всех регистров и накапливающих сумматоров. Выходы каждого i-ro регистра ,..., п+1) по;дключены к информационным входам i-TO, i+l-ro, i+2-го,..,, n+l-го накапливающего сумматора, входная шина каждого i-ro коэффициента первого и второго многочленов устройства подключена к первому управляющему входу соответсавующего регистра и к управляющему входу i-ro, i-tl-ro, ,.., , n+l-го накапливающего сумматора, тактирующая шина усзтройства соединена со вторыми управляющими входами накаплива ощих сумматоров.и распределителя, а выходные шины устройства связаны с выходами дегМфраторов.

На фиг.1 изображена структурная схема устройства для умножения многочленов; на фиг.2 показано выполнение дешифратора.

Устройство содернсит (n-t-1) разрядных регистров Ij - lj, коэффициентов первого многочлена, (п+1) разрядных регистров 2-t - 2п-н коэффициентов второго многочлена, {п+1) накапливающих cyMi jaторов 3 - , (ri+1) дешифраторов 4 - 4 ч , распределитель 5 сигналов, входные шине коэффициентов первого многочлена 6-1 и второго многочлена 7i - 7f|. , выходные шины 8 - и тактирующую шину 9.

Регистры 1 и 2 обладают свойствами многовходовых реверсивньох счетчиков „ Каждый i-й накапливающий cyNiMaтор 3 ,..,, п+1) содержат . разрядов, где - функция округления до большего целого. Выход j-ro разряда ,...,p ) распределителя 5 сигналов соединен со входом j+1-го разряда каждого регистра. Выход j-ro разряда 1-го регистра 1 и 2 подведен ко входу {3+.og, )-го разряда (,..., n+l)m-ro накапливающего сумматора. Дешифратор 4 представляет собой дешифратор второго рода и -может, быть реализован в виде комбинационной схемы, содержащей логические элементы, связанные с прямыг-ч и инверсными выходами трех первых разрядов накапливающего сумматора 3 в соответствии с системой переключательных-фvикций fi а (.a,jaij V a,j,a) , f.l a-i (a,a .) ,

где индексы аргументов соответствуют номерам разрядов .сумматора 3, а нндексы функций - номерам выходов де.пифратора 4 .

Пример выполнения дешифратора 4 на элементах И 10 и ИЛИ 11 показан на фиг.2. Каладая i-я хоцная шина 6 подведена к управляющему входу i-ro регистра 1 и к цепям приема кода k-r регистра 2 (,..., n-i+2) на (l+k-l)-a накапливаюйщй сумматор 3. й-малогичным образом 1-я входная шина

7связана с управляющим входом 1-го регистра 2 и с цепями приема кода k-ro регистра 1 (k-1,..,, n-i+2) на

{i+k-l)-й накапливающий сумматор 3. Тактирующая шина 8 соединена с управляющими входами накапливающих сумматоров 3 и распределителя 5 сигналов.

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

В исходном состоянии в регистрах 0 1 и 2 и в сумматорах 3 записаны нули.

8каждом q-M цикле вычисления на выходе распределителя сигналов единица находится в q + 1-м разряде (первыми разрядами всюду будем считать старшие) , В первом такте q-ro на каждую i-ю входную шину б поступает цифра коэффициента Aj,., , имеющая вес 2, которая управляет приемом кода распределителя 5 на 1-й регистр 1 и

Q .приемом кода k-ro регистра 2 на

{i+k-l)-й cytviMaTOp 3 следующим образом.

Если цифра q-ro разряда А-,.. равна единице, то в q-i-1-й разряд i-ro регистра 1 прибавляется единица, а на {i+k-l)-й сумматор 3 выдается прямой код k-ro регистра 2, если эта цифра равна минус единице, то из q+1-го разряда регистра 1 вычитается единица, а на указанные сумматоры 3

0 выдается дополнительный код соответствующих регистров 2, если цифра равна нулю, то содержимое регистра 1 не изменяется, а код указанных регистров 2 на соответст1зующие сум.;аторы

S 3 не выдается, Вс втором такте q-ro .цикла цифра q-ro разряда коэффициента В;.1 , 1 меющая вес и поступающая на 1-ю входную шину 7, аналогичным образом управляет прибавлением

д (вычитанием) единицы в q+1-й разряд регистра 2 и выдачей кодов k-x регистров 1 на (i-l-k-l)-й суглматор 3.

В результате анализа трех старших разрядов 1-го накапливающего сумматора 3 i-й дешифратор 4 формирует очё редную цифру i-1-го коэффициента многочлена , имеющую вес 2Р йг 1 по следуйнТему правилу. Цифра результата равна плюс единице, если содержимое трех старших разрядов накапли0 ваквдего сумматора 3 равно 001 или 01,0, минус единице - если содержимое трех старших разрядов равно 110 или 101, нулю - в остальных случаях. Цифры окончательного результата,

5 сформулированные дешифраторшли 4, поступают на выходные шины.

В третьем такте по сигналу в тактирующей шине 9 происходит сдвиг -впра0 во на один разряд единигда в распределителе 5 сигналов н сдвиг влево на один разряд содержимого накапливающих сумматоров 3, причем содержимое третьего разряда каждого накапливаю5 шего cy шaтopa при сдвиге заносится не только во второй разряд, но и в первый разряд. Для вычисления пкоэффициентов с точностью до р многочлена S , разрядов посЯе запятой необходимо выполнить Bogj (п+1) +2+р циклов вы числения. Рассмотрим работу вычислительног устройства на следующем примере. Пусть необходимо вычислить первые три коэффициента многочлена, получе ного в результате перемножения многочленов Ao+A X+AjX И BO+B, Х+ВпХ где ,1111; ,1101; ,1111 ,1111; ,1111; ,1001. Для данных значений коэффициенто процесс вычисления иллюстрируется таблицей состояний регистров устрой ства. Прокомментируем по таблице работу устройства, например, в третьем цикле вычисления. Перед началом цикла в каждом из регистров LJ , 112 и Ij находится чис ло 11, в регистрах 2, 2 и 2 о, записанычисла 11,11 и 10, в накапливающих сумматорах 3 , 3tj и 35 находятся числа 11001000, аЮОЮООО и 0011000000 соответственно. В первом такте третьего цикла вычисления в четвертые разряды регистров If , 1у и 1 заносятся третьи цифры коэф фициентов Ад , А и 1, О и i Минус единица, поступающая по шине 6, управляет вьадачей дополнительно го кода содержимого регистра 2 , взятого со знаком минус на накапливающий сумматор 3/, дополнительного кода содержимого регистра 2, взятого со знаком минус, на накапливаю щий сумматор 3 и дополнительного кода содержимого регистра 2, взятого со знаком минус, на накапливаю щий сумматор . Поскольку в шине G находится нуль, выдача содержимого регистра 2 на накапливающий суг1матор 3jj и -содержимого регистра 2; на накапливаклций сумматор 3 не происходит. Единица в шине б™ управляет выда чей содержимого регистра 2 на накапливающий сумматор З,. Во втором такте третьего цикла в четвертые разряды регистров 2, , 2г и 2, заносятся третьи цифры коэффициентов Вф, BI и Bij (1,1 и 0) . Единица в шине 7- управляет выдачей содержимого регистра 1 на накапливанхций сумматор 3 , содержимого регистра 1 на накапливающий сумматор 3 и содержимого регистра IT, на накапливающий сумматор Зо,. Единица в шине IQ управляет выдачей содержимого регистра 1/ на накапливающий сумматор 3( и содержимого регистра Ij на накапливающий сумматор Поскольку в шине 7п, находится нуль, то выдача содержимого регистра 1 на накапливающий сумматор З не происходит. После сложения указанных кодов дешифраторы 4 , 4,j и 4 , анализируя три старших разряда накапливгиощих сумматоров 3, Зп и Зг соответственно, формулируют третьи цифры коэффициентов С, С и С (0,1 и 1), которые поступают на выходные шины 8. Затем по сигналу в тактирующей шине 9 происходит сдвиг вправо единицы в распределителе 5 сигналов и сдвиг влево содержимого накапливгиощих сумматоров 3, З и 3. Для получения результата с точностьКз до пяти цифр после запятой описанный цикл вычисления необходимо повторить Bog,j(n-4) раз Как В/1ДНО из примера, данное устройство позволяет вычислять значения п+1 коэффициентов многочлена Cf , равного произведению л ногочлён АкХ на многочлен с точр цифр после запятой за нсхзтью до время Т5;(вод,()+2+р) (. Можно принять Ьйд p,5tj, тогда данное устройство превосходит известное по быстродействию в - 7.()р TO. 5(reogf {« -i a p) Например, при разрядности данное устройство позволяет вычислять коэффициенты многочлена 3-й степени в 2,14 раз (быстрее известного, 7-й степени - в 4,15 раз быстрее, 15-й степени - в 9,6 раз быстрее.

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

. Устройство для умножения многочленов, содержащее п+1 регистров коэффициентов первого многочлена, п+1 регистров коэффициентов второго многочлена и п+1 накапливающих сумматоров, Отличающееся тем, что,.с целью увеличения быстродействия, в устройство введены п+1 дешифраторов, входами связанных с выходами старших разрядов накапливающих сумматоров, и распределитель сигналов , соединенный с управляющими входами всех регистров и накапливающих сумматоров, выходы каждого i-ro pa-, гистра (,..., n+i) подключены к информационным входам i-ro, i+1-го, i+2-го,..., n+l-го накапливающего сумматора, входная шина каждого i-ro

коэффициента первого и второго много членов устройства подключена к первому управляющему входу соответствую щего регистра и к управляющему входу 1-го, i+1-го, i+2-го,..., П+1-ГО накапливающего cy лмaтopa, тактирующая шина устройства соединена со вторыми управляющими вxoдa п накапливающих cyr/ff.iaTopOB и распределителя, а выходные шины устройства связаны с выходами дешифратора.

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

№ 495663, кл. G 06 F 7/38, 1975 (прототип) .