Устройство для умножения многочленов
с
Союз Советских
Социалистических
Республик пп783791
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 05.01.79 (21) 2707093/18-24 с присоединением заявки № (23) Приоритет
Опубликовано 301180 Бюллетень ¹ 44 51 М „з
G 06 F 7/39
Государственный комитет
СССР по делам изобретений н открытий (53) УДК 681. 325 (088.8) Дата опубликования описания 30.1180 (72) Авторы изобретения
В.И. Жабин, В.И. Корнейчук, A.Â. Супрун, В.П. Тарасенко и A.A. Щербина (71) За яв ител ь
Киевский ордена Ленина политехнический институт им.50-летия
Великой Октябрьской социалистической революции (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МНОГОЧЛЕНОВ
Изобретение относится к области вычислительной техники и может быть применено, например, в специализированных вычислительных устройствах для нахождения произведения операндов, представленных многочленами, Йзвестны вычислительные устройства для формирования коэффициентов многочлена .Ф С Х, равного проA 3 изведению много Рлена 7. И Х на многочлен g В Х (1) .
Эти устройства представляют собой универсальные ЦВМ, а вычисление коэффициентов многочлена Д СгХ в этих устройствах выполняется путем реализации соответствующей программы.
Однако программному способу вычисления присущи такие недостатки, как низкое быстродействие и сравнительно большие аппаратурные затраты на реализацию универсальной ЦВМ при относительно низкой эффект Hвнoсти ихиспользования.
Наиболее близким к заявляемому является устройство, содержащее п+1 регистров коэффициентов первого многочлена, n+1 регистров коэффициентов второго мйоГочлена и и+1 накапливающих сумматоров, имеющих цепи сдвига, регистры результата, блок анализа разрядов операндов, блок сдвига, коммутатор и блок управления (2).
Это устройство лишено недостатков, 5 прис „их устройствам (1) так как опе рация умножения многочленов реализована в нем аппаратно. Однако известное устройство также имеет невысокое быстродействие, которое можно определить по формуле
Т„=(+ар (+
n — степень перемножаемых многочленов;
15 р — разрядность А; и В;; время сдвига; время суммирования.
Цель изобретения — увеличение быстродействия известного устройстЭ) ва.
Цоставленная цель достигается тем, что в устройство для умножения многочленов, содержащее тт+1 регистров коэффициентов первого многочлена, 25 h+1 регистров коэффициентов второго многочлена и и+1 накапливающих сумматоров, введены П+1 дешифраторов, входами связанных с выходами разрядов накапливающих сумматоров, и расЗр пределитель сигналов, соединенный с
783791 управляющими входами всех регистров и накапливающих сумматоров. Выходы каждого i--ro регистра (i=1 n+l) пс>дключены к информационным входам
i-го, i+1-го, i+2-ro...,, п+1-го накапливающего сумматора, входная шина каждого 4-го коэффициента первого и второго многочленов устройства подключена к первому управляющему входу соответствующего регистра и к управляющему входу 1-го, 1+1-го, i+7-го,..., n+1-ro накапливающего сумматора, тактирующая шина устройства соединена со HTopbIMH управляющими входами накапливающих сумматоров .и распределителя, а выходные шины устройства связаны с выходами дешифраторов.
На фиг.l изображена структурная схема устройства для умножения многочленов; на фиг.2 показано выполнение дешифратора.
Устройство содержит (n+1) разрядных регистров 1 - 1>+ коэффициенТсВ первогo многочлена, (n+1) разрядных регистров 2 — 2п+ коэффициентов второго многочлена, (n+1) накапливающих сумматоров 3 — 3 + (и+1) дешифраторов 4 — 4»+, распределитель 5 сигналов, входные шины коэффициентов первого многочлена б| — бм и второго многочлена
71 — 7„„,1, выходные шины 81 — 8» и тактирующую шину 9.
Регистры 1 и 2 обладают свойствами многовходовых реверсивных счетчиков. Каждый i-й накапливающий сумматор 3 (i=1...„, и+1) содержит
3+р+(Вog,1) разрядов, где () — функция округления до большего целого.
Выход j-ro разряда (j=l,. ° .,р ) распределителя 5 сигналов соединен со входом j+ -го разряда каждого регистра. Выход j-ro разряда i-горегистра 1 и 2 подведен ко входу (3+ (og Дешифратор 4 представляет Собой дешифратор второго рода и может быть реализован в виде комбинационной схемы, содержащей логические элементы, связанные с прямым и инверсными выходами трех первых разрядов накапливающего сумматора 3 в соответствии с системой переключательных-.фчнкций iq == а1 (а а ч а а ), f = а (а а а а ), где индексы аргументов соответствуют номерам разрядов сумматора 3, а индексы функций — номерам выходов,цеьифратора 4. Пример выполнения дешифратора 4 на элементах И 10 и ИЛИ 11 показан на фиг.2. Каждая i-я хоцная шина б подведена к управляющему входу i-го регистра 1 и к цепям приема кода k-го регистра 2 (k=1,..., n-1+2) на (i+k-1)-й накапливающий сумматор 3. алогичным образом i-я входная шина 7 связана с управляющим входом 1-ro регистра 2 и с цепями приема кода k-го регистра 1 (k=-l,..., n-i+2) на (3.+k 1) -й накапливающий су>матор 3. Тактирующая шина 8 соединена с управляющими входами накапливающих сумматоров 3 и распределителя 5 сигналов. Устройство работает следующим образом. В исходном состоянии в регистрах 36 1 и 2 и в сумматорах 3 записаны нули. В каждом q-м цикле вычисления на выходе распределителя сигналов единица находится в q+1-м разряде (первыми разрядами всюду будем считать старj$ шие). В первом такте q-го цикла на каждую i-ю входную шину б поступает цифра коэффициента А„, имеющая вес 2"Ъ, которая управляет приемом кода распределителя 5 на i-й регистр 1 и приемом кода k-го регистра 2 на (i+k-1)-й сумматор 3 следующим образом. Если цифра q-го разряда А„. равна единице, то в q+1-й разряд i-го регистра 1 прибавляется единица, а на (i+k-1) -й сумматор 3 выдается прямой код k-го регистра ?, если эта цифра равна минус единице, то из q+1-ro разряда регистра 1 вычитается единица, а на укаэанные сумматоры 3 3G выдается дополнительный код соответствующих регистров 2, если цифра равна нулю, то содержимое регистра 1 не изменяется, а код укаэанных регистров 2 на соответствующие сумматоры 35 3 не выдается. Вс втором такте ц-го .цикла цифра q-го разряда коэффициента В„ q, имеющая вес 2 Ч и поступающая на i-ю входную шину 7, аналогичным образом управляет прибавлением g() (вычитанием} единицы в q+1-й разряд регистра 2 и выдачей кодов k-x регистров 1 на (1+К-1)-й сумматор 3. В результате анализа трех старших разрядов 1.-го накапливающего сумматора 3 i. — é дешифратор 4 формирует очередную цифру i — 1-го коэффициента многочлена @ С>-Х, имеющую вес 2 (0@ Ы" 1 Ф О по следующему правилу ° Цифра результата равна плюс единице, если содержимое трех старших разрядов íàкапливающего сумматора 3 равно 001 или 01,0, минус единице — если содержимое трех старших разрядов равно 110 или 101, нулю - в остальных случаях. Цифры окончательного результата, сформулированные дешифраторами 4, поступают на выходные шины. В третьем такте по сигналу в тактирующей шине 9 происходит сдвиг вправо на один разряд единицы в распределителе 5 сигналов и сдвиг влево на один разряд содержимого накапливающих сумматоров 3, причем содержимое третьего разряда каждого накапливаюmего сумматора при сдвиге заносится 783791 не только во второй разряд, но и в первый разряд. Для вычисления и коэффициентов многочлена % С .Х с точностью до р 1 "-в разрядов после запятой необходимо выполнить (Eog (n+1)) +2+p циклов вычисления. Рассмотрим работу вычислительного устройства на следующем примере. Пусть необходимо вычислить первые три коэффициента многочлена, получен- (О ного в результате перемножения многочленов Ap+A Х+А Х и В +В1 Х+ Х )ь где Аз=0,1111; A„=0,1101; +=01111; В =О, »»; В =О, »11; В =О,1ОО1 ° Для данных значений коэффициентов процесс вычисления иллюстрируется таблицей состояний регистров устройства. Прокомментируем по таблице работу устройства, например, в третьем . цикле вычисления. Перед началОм ццкла в каждом из регистров Q, 1 и 1 находится чис ло 11, в регистрах 2, 2 и 2 записаны числа 11, 11 и 10, в накап- 25 ливающих сумматорах 3, 3 и 35 находятся числа 11001000,:110010000 и 0011000000 соответственно. В первом такте третьего цикла вычисления в четвертые разряды регистров 1, gp 1у и 1 заносятся третьи цифры коэффициенioa Ap, A< и А9: 1, О и 1; Минус единица, поступающая по шине 6„, управляет выдачей дополнительного кода содержимого регистра 2, взятого со знаком минус на накапливающий сумматор 3, дополнительного кода содержимого регистра 2, взятого со знаком минус, на накапливающий сумматор 3 и дополнительного кода содержимого регистра 2, взятого со знаком минус, на накапливающий сумматор 3 . Поскольку в шийе 6 находится нуль, выдача содержимого регистра 2 на накапливающий сумматор 3> и содержимого регистра 4$ 2 на накапливающий сумматор 3 не происходит. ° Единица в шине 6 управляет выда" чей содержимого регистра 2 на накапливающий сумматор 3 . Во втором 50 такте третьего цикла в четвертые разряды регистров 2„, 2 и 2 заносятся третьи цифры коэффициентов В, В и В9 (1,1 и О). Единица в шине 71 управляет выдачей содержимого регистра 1 на накапливающий сумматор 31, содержимого регистра 1 на накапливающий сумматор 3 и содержимого регистра 1ь на накапливающий сумматор 3 . Единица в шине 7 управляет выдачей содержимого регистра lg на накапливающий сумматор 3 и содержимого регистра 1 на накапливающий сумматор 33 ° Поскольку в шине 7 находится нуль, то выдача содержимого регистра 1 на накапливающий сумматор Зь не происходит. После сложения указанных кодов дешифраторы 41, 4 и 4>, анализируя три старших разряда накапливающих сумматоров 3, 3 и 3> соответственно, формулируют третьи цифры коэффициентов С1, С(и С1 (0,1 и 1), котоГые поступают на выходные шины 8. Затем по сигналу в тактирующей шине 9 происходит сдвиг вправо единицы в распределителе 5 сигналов и сдвиг влево содержимого накапливающих сумматоров 31, 3 и 3 . Для получения результата с точностью до пяти цифр после запятой описанный цикл вычисления необходимо повторить (Sog<(п- 1))+2+р=8 раз Как вредно иэ примера, данное устройство позволяет вычислять значения n+1 коэффициентов многочлена у С -Х, авного произведению многочлейа АуХ на многочлен 9 В Х 1", с точйостью до р цифр после запятой за время T =((бодо (и 1) )+2+р) (2Q+Qg . Можно принять щ = 0,5t тогда данное устройство превосходит известное по быстродейс тв ию в Ъ (и+1) Р 5(PLOTS,(n+<) y+p) Например, при разрядности р=32 данное устройство позволяет вычислять коэффициенты многочлена 3-й степени в 2,14 раз быстрее известного, 7-й степени — в 4,15 раз быстрее, 15-й степени — в 9,6 раз быстрее. 783791 t: 1 1 4 (Г Цикл 1 1 Исходноеое сос то я иие 00000 1 01000 00000 00000 О 01000 01000 О 000000000 000001000 О 000010000 О 000001000 00001000 000001100 l100l000 11110100 1 ОО1ОО1ООО l1ОО1ОаОО lll1l0100 000000000 1 110011010 1 000001110 00001110 000001101 111110101 1 OO1OiOOiO 110100100 001001000 1 110010000 О 1 000100000 1 О 001000000 00100101 1100101О 00100000 Формула изобретения Устройство для умножения многочленов, содержащее n+1 регистров коэффициентов первого многочлена, n+1 регистров коэффициентов второго многочлена и п+1 накапливающих сумматоров, о т л и ч а ю щ е е с я тем, что,.с целью увеличения быстродействия, в устройство введены n+1 дешифраторов, входами связанных с выходами старших разрядов накапливающих сумматоров, и распределитель сигналов, соединенный с управляющими входами всех регистров и накапливающих сумматоров, выходы каждого i-го регистра (1=1,..., n+1) подключены к информационным входам i-ro, i+1-ãî, 1+2-ro,..., n+1-го накапливающего сумматора, входная шина каждого i-го 2 01100 01100 01100 Э OiO1O Oi iOO Oi iiO 4 01011 01101 01111 00O000l000 000000)000 000000 1000 000000)000 ОООаО011ОО l1lllll000 001101111О 0000001111 1111110011 0000001011 1111101101 ll01101000 111010ОООО 42 31 41 3 21 2 2 00000000 00000 00000 00000 00000000 00001000 01000 01000 01000 00001100 01100 01100 01000 ОООО1О1О OiilO OlliO О1ООО 00001011 ollll Îliîi 01001 коэффициента первого и второго много членов устройства подключена к первому управляющему входу соответствующего регистра и к управляющему входу i-ro i+1-ro, i+2-го,..., n+1-ãî накапливающего сумматора, тактирую 40 щая шина устройства соединена со вторыми управляющими входами накапливающих сумматоров и распределителя, а выходные шины устройства связаны с выходами дешифратора. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР У 451088, кл, С 06 Г 15/20, 1974. 2. Авторское свидетельство СССР Р 495663, кл, G 06 Г 7/38, 1975 (прототип) 783791 г„+, и Ф Ягяl Составитель В. Кайданов Редактор И. Грузова Техред А.Щепанская Корректор,М. Шарсыи Заказ 8550/52 Тираж 751 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Рауюская наб., д. 4/5 Филиал ППП Патент, г. Ужгород, ул. Проектная, 4
