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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 1 с Союз Советских Социалистических Республик(23) ПриоритетОпубликовано 30,1180 Бюллетень Мо 44 51)М Кз 6 06 Р 7/39 Государственный комитет СССР по делам изобретений н открытийДата опубликования описания 30,1180(71) Заявитель Киевский ордена Ленина политехнический институт им.50-летия Великой Октябрьской социалистической революции(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МнОГОЧлеНОВ Изобретение относится к области вычислительной техники и может быть применено, например, в специализированных вычислительных устройствах для нахождения произведения операндов, представленных многочленами,Йзвестны вычислительные устройства для формирования коэффициентов многочлена .Ф ОсХ , равного провЗфизведению многочлена 5 АгХ на многочленВ Х 1 .Эти устройства представляют собой универсальные ЦВМ, а вычисление коэффициентов многочлена Д СгХ в этих устройствах выполняется путем реализации соответствующей программы, Однако программному способу вычисления присущи такие недостатки, как низкое быстродействие и сравнительно большие аппаратурные затраты на реализацию универсальной ЦВМ при относительно низкой эффективности их. использования.Наиболее близким к заявляемому является устройство , содержащее п+1 регистров коэффициентов первого многочлена, и+1 регистров коэффициентов второго мйоГочлена и и+1 накапливающих сумматоров, имеющих цепи сдвига, регистры Результата,блок анализа разрядов операндов,блок сдвига, коммутатор и блок управления 2).Это устройство лишено недостатков,присущих устройствам 1) так как операция умножения многочленов реализована в нем аппаратно, Однако известное устройство также имеет невысбкоебыстродействие, которое можно определить по формулеТ 1 = (и+1) Р ("+сдф) фи - степень перемножаемых многочленов;15 р - РазРядность А; и Всв. время сдвига;время суммирования.Цель изобретения - увеличениебыстродействия известного устройст О ва.Цоставленная цель достигается тем,что в устройство для умножения многочленов, содержащее тт +1 регистровкоэффициентов первого многочлена, 25 й+1 регистров коэфФициентов второгомногочлена и и+1 накапливающих сумматоров, введены П+1 дешифраторов,входами связанных с выходами разрядов накапливающих сумматоров, и расЗр пределитель сигналов, соединенный суправляющими входами всех регистрови накапливающих сумматоров. Выходыкаждого З.-го регистра (1=1 п+1)подключены к информационным входам1-го, 1+1-го, 1+2-го п+1-гонакапливающего сумматора, входнаяшина каждого 4-го коэффициента первого и второго многочленов устройства подключена к первому управляющему входу соответствующего регистра и к управляющему входу 1-го,1+1-го, 1+2-го и+1-го накапливающего сумматора, тактирующая шинаустройства соединена со вторыми управляющими входами накапливающихсумматоров и распределителя, а выходные шины устройства связаны с выходами дешифраторов.На Фиг.1 изображена структурнаясхема устройства для умножения многочленов; на Фиг.2 показано выполнение дешифратора,Устройство содержит (п+1) разрядных регистров 1 - 1+ коэффициентов первого многочлена, (п+1) разрядных регистров 2 - 2 п+ коэффициентов второго многочлена, (и+1) накапливающих сумматоров 3 - 3+(и+1) дешифраторов 4 - 4,., распределитель 5 сигналов, входные шины коэффициентов первого многочленаб - бпла и второго многочлена71 - 7,1, выходные шины 81 - 8и тактирующую шину 9. Регистры 1 и 2 обладают свойствами многовходовых реверсивных счетчиков. Каждый 1-й накапливающий сумматор 3 (3.=1, и+1) содержит3+р+И.од,1) разрядов, где ( 3- функция округления до большего целого.Выход 3-го разряда (3=1,..,р ) распределителя 5 сигналов соединен совходом 3+1-го разряда каждого регистра. Выход 3-го разряда 1-го регистра 1 и 2 подведен ко входу(3+(одп)+3)-го разряда (в=1п+1)т-го накапливающего сумматора,Дешифратор 4 представляет Собой дешифратор второго рода и может бытьреализован в виде комбинационной схемы, содержащей логические элементы,связанные с прямым и инверсными выходами трех первых разрядов накапли"вающего сумматора 3 в соответствиис системой переключательных-.фчнкцийЙ: - а 1 (а 1 а ч аа),Г= а (аа а а),где индексы аргументов соответствуютномерам разрядов сумматора 3, а индексы Функций - номерам выходов,цешифратора 4,Пример выполнения дешифратора 4на элементах И 10 и ИЛИ 11 показанна Фиг,2. Каждая 1.-я хоцная шина бподведена к управляющему входу 1-горегистра 1 и к цепям приема кода Е-горегистра 2 (К=1 п.+2) на(1+):-1)-й накапливающий сумматор 3.аналогичным образом 1-я входная шина 7 связана с управляющим входом 1-горегистра 2 и с цепями приема кода(1+К) -й накапливающий сущатор 3.Тактирующая шина 8 соединена с управляющими входами накапливающих сумматоров 3 и распределителя 5 сигналов.Устройство работает следующим образом.В исходном состоянии в регистрах 1 О 1 и 2 и в сумматорах 3 записаны нули,В каждом -м цикле вычисления на выходе распределителя сигналов единицанаходится в с 1+1-м разряде (первымиразрядами всюду будем считать стар Я шие). В первом такте с 1-го цикла накаждую 1-ю входную шину б поступаетцифра коэффициента А , имеющая вес2"Ъ, которая управляет приемом кодараспределителя 5 на 1-й регистр 1 иприемом кода Е-го регистра 2 на(3.+К)-й сумматор 3 следующим образом.Если цифра с 1-го разряда А равна единице, то в с 1+1-й разряд 1-горегистра 1 прибавляется единица, ана (3.+К) -й сумматор 3 выдаетсяпрямой код Е-го регистра , если этацифра равна минус единице, то из1+1-го разряда регистра 1 вычитаетсяединица, а на укаэанные сумматоры 3 3 выдается дополнительный код соответствующих регистров 2, если цифра равна нулю, то содержимое регистра 1 неизменяется, а код указанных регистров 2 на соответствующие сую аторы 35 3 не выдается. Вс втором такте с 1-го.цикла цифра с 1-го разряда коэффициента В 1, имеющая вес 2 Ч и поступающая на 1-ю входную шину 7, аналогичным образом управляет прибавлением 40 (вычитанием) единицы в (+1-й разрядрегистра 2 и выдачей кодов К-х регистров 1 на (1+К) -й сумматор 3.В результате анализа трех старшихразрядов 1.-го накапливающегосумматора 3 1-й дешифратор 4 формирует очередную цифру 1-1-го коэффициента многочлена 6 С.Х, имеющую вес 2 (УфФФФИ-опо следующему правилу, Цифра результата равна плюс единице, если содержимое трех старших разрядов накапли вающего сумматора 3 равно 001 или01,0, минус единице - если содержимое трех старших разрядов равно 110или 101, нулю " в остальных случаях.Цифры окончательного результата,сформулированные дешифраторами 4,поступают на выходные шины,В третьем такте по сигналу в тактирующей шине 9 происходит сдвиг впра. во на один разряд единицы в распреде" лителе 5 сигналов и сдвиг влево на один разряд содержимого накапливающих сумматоров 3, причем содержимое третьегО разряда каждого накапливаю. шего сумматора при сдвиге заноситсяне только во второй разряд, но и в первый разряд.Для вычисления икоэффициентов многочлена % С"Х с точностью до р разрядов после запятой необходимо выполнить Под(п+1) +2+р циклов вычисления.5Рассмотрим работу вычислительного устройства на следующем примере. Пусть необходимо вычислить первые три коэффициента многочлена, получен ного в результате перемножения многочленов Ао+А 1 Х+А 1 Х и Во+В, Х+ ХЗьгде Ао=0,1111; А =0,1101; А =01111;0 1111 у В 0 1111 у В 1 0 1001Для данных значений коэффициентов процесс вычисления иллюстрируется таблицей состояний регистров устройства.Прокомментируем по таблице работу устройства, например, в третьем цикле вычисления.Перед началОм ццкла в каждом из регистров Е,11 и 1 находится чис ло 11, в регистрах 2, 2 и 2 Ь за- писанычисла 11, 11 и 10, в накап ливающих сумматорах 3, 3 и 35 находятся числа 11001000,:110010000 и 0011000000 соответственно. В первом такте третьего цикла вычисления в четвертые разряды регистров 1, рр 1 у и 1 заносятся третьи цифры коэффициентов Ао, А и А 9. 1, 0 и 1; Минус единица, поступающая по шине 6, управляет выдачей дополнительного кода содержимого регистра 2, взятого со знаком минус на накапливающий сумматор 3, дополнительного кода содержимого регистра 2, взятого со знаком минус, на накапливающий сумматор 32 и дополнительного кода содержимого регистра 2, взя того со знаком минус, на накапливающий сумматор 3 . Поскольку в шийе 6 й находится нуль, выдача содержимого регистра 2 на накапливающий сумматор 3 и содержимого регистра 4 Я 2 на накапливающий сумматор 3 не происходит.ФЕдиница в шине 6 управляет выда" чей содержимого регистра 2 на накапливающий сумматор 3. Во втором 50 такте третьего цикла в четвертыеразряды регистров 21, 22 и 2 заносятся третьи цифры коэфФициентовВ, В 1 и В 9 (1,1 и О),Единица в шине 71 управляет выдачей содержимого регистра 1 нанакапливающий сумматор 31, содержимого регистра 1 на накапливающийсумматор 3 и содержимого регистра1 на накапливающий сумматор 3.Единица в шине 7 управляет выдачейсодержимого регистра 1 на накапливающий сумматор 3 и содержимого регистра 1 на накапливающий сумматорПоскольку в шине 7 находится нуль,то выдача содержимого регистра 1, нанакапливающий сумматор Зь не происходит. После сложения указанных кодов дешифраторы 41, 4 и 4, анализируя три старших разряда накапливающих сумматоров 3, 3 и 35 соответственно, формулируют третьи цифрыкоэффициентов С 1, С( и С 1 (0,1 и 1),котоГые поступают на выходные шины8. Затем по сигналу в тактирующей шине 9 происходит сдвиг вправо единицыв распределителе 5 сигналов й сдвигвлево содержимого накапливающих сумматоров 31, 3 и 3. Для получениярезультата с точностью до пяти цифрпосле запятой описанный цикл вычисления необходимо повторитьВод(п.ф 1+2+р=8 разКак видно иэ примера, данное устройство позволяет вычислять значенияи+1 коэффициентов многочлена у С-Хф,авного произведению многочлейаА Х на многочленВ Х ф; с точйостью до р цифр после запятой завремяТ= ( бодо (и Н ) ) +2+р) (2+ .Можно принять д= 0,51, тогдаданное устройство превосходит известное по быстродейс тв ию вЪ (и+1) рт 5 тбО (11 Р) РазНапример, при разрядности р=32данное устройство позволяет вычислятькоэффициенты многочлена 3-й степенив 2,14 раз быстрее Известного, 7-йстепени - в 4,15 раз быстрее, 15-йстепени - в 9,6 раз быстрее.783791 1"з 1 4,14 Цикл 1 1 Исходноесос то яние 0000000100101 11001010 00010100 00101000 11010000 00100000 Формула изобретения Устройство для умножения многочленов, содержащее и+1 регистров коэфФициентов первого многочлена, и+1 регистров коэффициентов второго многочлена и п+1 накапливающих сумматоров, о т л и ч а ю щ е е с я тем, что,.с целью увеличения быстродействия, в устройство введены и+1 дешифраторов, входами связанных с выходами старших разрядов накапливающих сумматоров, и распределитель сигналов, соединенный с управляющими входами всех регистров и накапливающих сумматоров, выходы каждого 1-го регистра (1=1 п+1) подключены к информационным входам 1-го, 1+1-го, 1+2-го и+1-го накапливающего сумматора, входная шина каждого 1-го 1. Авторское р У 451088, кл, С 2. Авторское Р 495663, кл, 6 тотип)2 01100 01100 01100 э а)о)о аоо о)1)о1 0000000000 0000000000 0000000000 0000000000 0000001000 0000001000 000000)000 0000011000 0000110000 000000 1000 0000001000 оооооофоаа оооаоаоо 0000001100 0000000000 0001100000 0011000000 1111111000 0000000000 0000001100 0000001110 0000001100 0011011110 1110111100 0000001000 0000001110 0000001100 0000001111 1111110011 0000001011 1111101101 1111011010 1110110100 1101101000 0011010000 0)ааааа 42 222 00000000 ааааа 00000 0000000000000 00001000 01000 01000 01000 00001100 01100 01100 01000 оооо)о о 11 оо) о)оо) коэффициента первого и второго много членов устройства подключена к первому управляющему входу соответствующего регистра и к управляющему входу 1-го, 1.+1-го, .)+2-го.п+1-го накапливающего сумматора, тактирую щая шина устройства соединена со вторыми управляющими входами накапливающих сумматоров и распределителя, а выходные шины устройства связаны с выходами дешифратора. Источники информации,принятые во внимание при экспертизе783791 Составитель В. Кайдановова Техред А,Щепанская Корректор ,М. Шарсыи едактор И. Заказ 8550/52ВНИ П Патентф, г. Ужгород, ул. Проектная, 4 Филиал Тираж 751 И Государственного делам изобретений 5, Москва, Ж, Ра