Устройство для вычисления полиномов с фиксированными коэффициентами

СОЮЗ СОВЕТСКИСОЦИАЛИСТ ИЧРЕСПУ БЛИН И зРЕТЕНИЯ ГВУ(54)(57) 1, УСТРОЙСТВО ДЛЯ ВЬЗЧИСЛЕНИПОЛИНОИОВ С ФИКСИРОВАННЬЙИ КОЭФФИЦИ"ЕНТАИИ, содержащее восемь блоков регистров, четыре блока умножителейи четыре сумматора, причем выходпервого блока регистра является вы"ходом устройства, о т л и ч а ю щ е ес я тем, что, с целью повышения скорости вычисления алгебраических полиномов с Фиксированными коэффициентами, в него введены первый, второй итретий элементы И и блок управленияпричем выход первого блока регистраподключен к первому входу множимогоблока первого умножителя, второй вхомножимого которого связан с выходомпервого сумматора, с первым входоммножителя блока первого умножителяи с первым входом блока первого регистра, выход блока первого умножителя соединен с вторым входом блокапервого регистра и с первым входомблока второго регистра, второй входкоторого подключен к выходу первого ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРпо ДЕлю изоБРетений и отеътий ПИСАНИЕ ИЗ(56) 1. Авторское свидетельство ССС575648, кл, О 06 Г 7/38, 1975.2. Авторское .свидетельство СССРЬ" 556446, кл, О 06 Г 15/32, 1975,3. Авторское свидетельство СССРй 813443, кл. 6 06 Г 7/38, 1979(прототип). 80.1 0194 элемента И, а выход подключен к пер-.вому входу первого сумматора, второйвход которого является первым информационным входом устройства, выходблока третьего регистра соединен свторым входом множителя блока первого умножителя и с первым входоммножимого блока второго умножителя,выход которого связан с первыми входами блоков третьего и четвертогорегистров, второй вход блока четвертого регистра подключен к выходувторого элемента И, а выход соединенс первым входом второго сумматора,второй вход которого является вторым информационным входом устройстваа выход подключен к входу множителя,.второму входу множимого блока второго умножителя и к второму входу блокатретьего регистра, первый вход блока пятого регистра связан с выходом блокатретьего умножителя и с первым входом блока шестого регистра, второйвход которого подключен к выходутретьего элемента И, а выход соединен с первым входом третьего сумматора, второй вход которого является третьим информационным входомустройства, а выход подключен к первому входу множимого, к входу множителя блокатретьего умножителяи .к второму входу блока пятого регистра, выход которого соединен свторым входом множимого блока третьего умножителя и с первым входоммножителя блока четвертого умножителя, выход которого подключен кпервому входу блока седьмого регистра, выход которого соединен стретьим входом множителя блока первого умножителя и с первым входом019456 а=1 Составитель В.БерезкинТехред А,Бабинец Корректор М.йароши Редактор Р. Цицика Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 Заказ 370 б/44 Тираж 706 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва Ж, Раушская наб., д. 4/51019 Ь 56 умножителя. множимого блока четвертого умножителя, а второй вход связан с вторыми входами множителя и множимогоблока четвертого умножителя и с выходом четвертого сумматора, первыйвход которого соединен с выходомблока восьмого регистра, первый входкоторого связан с выходом блока четвертого умножителявторой вход четвертого сумматора является четвертыминформационным входом устройства,второй вход блока восьмого регистрасвязан с первыми входами первого,второго, третьего элементов И и с пятыминформационным входом устройства,выходы блока управления с первогопо восьмой подключены к управляющимвходам блоков первого, второго, третьего, четвертого, пятого, шестого,седьмого и восьмого регистров соответственно, выходы блока управленияс девятого по двадцатый подключенык первым, вторым и третьим управляющим входам блоков первого, второго,третьего и четвертого умножителейсоответственно, выходы блока управления с двадцать первого по двадцатьтретий, подключены к вторым входампервого, второго и третьего элементов И, двадцать четвертый выход блока управления является выходом признака окончания операции устройства,первый и второй входы синхронизацииблока управления являются первым ивторым входами синхронизации устройства, .первый информационный входблока управления является первымвходом устройства, каждый блок регистра содержит мультиплексор и регистр, причем первый й второй входы блока регистра являются первым и Изобретение относится к вычислительной технике и предназначено для вычисления алгебраических полиномов с высокой скоростью.Известно устройство для вычисления значения полиномов а-й степени, содержащее три регистра сдвига, три элемента И счетчик переноса, сумматор и блок управления, причем вторым информационными входами мультиплексора, управляющий вход которого связан с управляющим входом блокарегистра, а выход соединен с входомрегистра, выход которого является выходом блока регистра, каждый блок умно"жителя содержит два мультиплексораи умножитель, причем первый и второйвходы множимого блока умножителя соединены с соответствующими информационными входами первого мультиплексора,первый, второй и третий входы множителей блока умножителя подключены ксоответствующим информационным входамвторого мультиплексора, первый и вто-.рой управляющие входы которого явля" ются соответствующими управляющими входами блока умножителя, управляющий вход первого мультиплексора подключен к третьему управляющему входу блока умножителя, вцходы первого и второго мультиплексоров соединены с входами множимого и множителя умножителя, выход которого является выходом блока 2. Устройство по и. 1, о т л и ч аю щ е е с я тем, что блок управления содержит счетчик адреса, увел памяти, регистр микрокоманд, причем первые входы счетчика адреса и узла памяти являются первым и вторым входами синхронизации блока управления соответственно, информационный вход которого является вторым входом счетчика адреса, выход которого подключен к второму входу узла памяти выход которого связан с входом регистра микрокоманд, двадцать четыре выхода которого являются соответствующими выходами блока управления. выходы первого и второго регистровсдвига через первый элемент И исчетчик переноса подключены к первому входу сумматора, второй входкоторого связан с выходом третьегорегистра, а выход через второй элемент И соединен с входом первого регистра, выход которого через третийэлемент И связан с его входом, к1 О 15 20 25 30 35 40 50 55 управляющим входам трех регистров сдвига, счетчика переноса, сумматора, трех элементов И 1.Однако это, устройство не может обеспечить необходимую скорость вычисления алгебраических полиномов.Известно устройство для вычисления полиномов, содержащее сумматоры, регистр, реверсивный счетчик, схему сравнения, элемент задержки, группу пар элементов И, три пары элементов И, причем сумматоры соединены последовательно через соответствующую пару элементов И группы, входы первого сумматора через пару элементов И группы соединены с выходом регистра, первый и второй выходы схемы сравнения соединены с первыми входами соответствующих элементов И всех трех пар, третий выход схемы сравнения соединен с вторыми входами элементов И первой пары, второго элемента И второй пары, первого элемента И третьей пары и входом элемента задержки, выходы элементов И первой пары соединены с входом схемы сравнения, второй вход которого соединен с вторыми входами первого элемента И второй пары и второго элемента И третьей пары, третий вход схемы сравнения соединен с входом устройства, выходы элементов И.второй пары соединены с входами соответствующих элементов И нечетных пар группы,а выходы элементов И третьей пары соединены с входами соответствующих элементов И.четных пар группы 2 1.Однако такое устройство не может обеспечить необходимую скорость вычисления алгебраических полиномов; Наиболее близким к изобретению является устройство для вычисления полиномов, содержащее блок первого регистра, вход которого соединен с выходом первого сумматора, первый вход которого подключен к первому выходу блока первого умножителя, второй вход первого сумматора, подключен к выходу первого буферного запоминающего устройства, третий вход первого сумматора соединен с первым выходом второго сумматора, первый вход которого связан с первым выходом блока второго умножителя, второй вход подключен к выходу второго блока буферного запоминающего устройства, второй выход соединен с входом блока второго регистра,а третий вход связан с первым выходом третьего сумматора, первый вход которого подключен к первому выходу блока третьего умножителя, второй вход - к выходу третьего блока буферного запоминающего устройства, второй выход связан с входом блока третьего регистра, а третий вход соединен с первым выходом блока четвертого регистра, вход которого подключен к выходу четверто" го сумматора, первый вход которого связан с выходом блока четвертого умножителя, а второй вход с выходом четвертого блока буферного запоминающего устройства, второй выход блока второго умножителя подключен к входу блока пятого регистра, выход которого1 соединен с первым входом множимого блока первого умножителя, первыйвход множителя которого связан с выходом блока шестого регистра, первыйвход которого подключен к выходупервого блока буферного запоминающего устройства, а второй вход соединенс первым выходом блока первого регистра, второй выход которого является первым выходом устройства, второй выход блока первого умножителясвязан с входом блока седьмого регистра, первым входом множимого блока второго умножителя, первым входом множимого и первым входом множителя блока третьего умножителя,выход блока седьмого регистра подключен к второму входу множимого бло"ка второго умножителя, первый входмножителя которого соединен с выходомвторого блока буферного запоминающего устройства, а второй вход подключенк выходу блока второго регистра,первый выход блока девятого регистрасвязан с вторым входом множителяблоков второго и первого умножителей, а также с вторым входом множимого блока первого умножителя, второй выход блока девятого регистрасоединен с вторым входом множимогоблока третьего умножителя,первыйвход блока десятого регистра подклю"чен к выходу третьего блока буферного запоминающего устройства,второй вход связан с выходом блокатретьего регистра, а выход соединен с вторым входом множителя блока третьего умножителя, 1019456второй выход которого подключен квходу блока одиннадцатого регистра,выход которого связан с третьими.входами множимого блоков первого,второго и третьего умножителей, а также с входом множимого блока четвертого умножителя, вход.множителя которого соединен с выходом блока двенадцатого регистра, первый вход которого подключен к выходу четвертого блока буферного запоминающего устройства, а второй вход связан с вторым выходом блока четвертого регистра, первый выход блока управления записью подключен к первому. входу первого блока буферного запоминающего устройства, третий выхол - к первому входу третьего блока буФерного запоминающего устройства; второй выход - к первому входу второго блока буферного запоминающего устройства; четвертый выход - к первому входу буферного запоминающего устройства, первый вход устройства соединен с вторыми входами первого, второго, третьего и четвертого блоков буферного регистра, второй вход устройства является входом блока тринадцатого регистра, выход которо" го подключен к входам схемы определения количества циклов и блока.: определения начального адреса, выход которого соединен с входом блока управления записью выход схемы определения количества циклов подключен к первому входу счетчика циклов, второй вход которого является треть" им входом устройства, а выход является вторым выходом устройства, в блоках регистров их первые и вторые входы являются первыми и вторыми информационными входами первых мультиплексоров, выходы которых соединены с входами регистров, выходы которых являются выходами блоков ре" гистров, в блоках умножителей первые и вторые входы множимых соединены с соответствующими информационными входами вторых мультиплексоров, первые, вторые и третьи входы множителей подключены к соответствующим информационным входам третьих мультиплексоров, выходы вторых и третьих мультиплексоров соединены с входами множимого и множителя умножителей, выходы которых являются выходами бло ков умножителей 3.Недостатком известного устройства является его низкое быстродействие. Целью изобретения является повы"шение скорости вычисления алгебраических полиномов с фиксированнымикоэффициентами,Поставленная цель достигается тем,что в устройство, содержащее восемьблоков регистров, четыре блока умножителей и четыре сумматора, причемвыход первого блока регистра является первым выходом устройства, введе 1 О ны первый, второй и третий элементыИ и блок управления, содержащий счетчик, адреса, запоминающее устройствои регистр микрокоманд, причем выходпервого блока регистра подключен кпервому входу множимого блока первого .умножителя, второй вход множимогокоторого связан с выходом первогосумматора, с первым входом множителя блока первого умножителя и спервым входом блока первого регистра,выход блока первого умножителя соединен с вторым входом блока первогорегистра и с первым входом блокавторого регистра, второй вход которого подключен к выходу первого эле- вмента И, а выход подключен к первомувходу первого сумматора, второй входкоторого является первым информаци"онным входом устройства, выход блокатретьего регистра соединен с вторымвходом множителя блока первого умножителя и с первым входом множимогоблока второго умножителя, выход которого связан с первыми входами блоков третьего и четвертого регист. 35ров, второй вход блока четвертого регистра подключен к выходу второгоэлемента И, а выход соединен с первымвходом второго сумматора, второйвход которого является вторым информационным входом устройства, авыход подключен к входу множителя,второму входу множимого блока второго умножителя и к второму входублоха третьего регистра, первый45 вход блока пятого регистра связанс выходом блока третьего умножителяи с первым входом блока шестого регистра, второй вход которого под"ключен к выходу третьего элемента50 И, а выход соединен с первым входом третьего сумматора, второй вход которого является третьим информа-. ционным входом устройства, а выход подключен к первому входу множимого,55 к входу множителя блока третьего умножителя и к второму входу блока пятого регистра, выход которого сое7 10191 динен с вторым входом множимого бло" ка третьего умножителя и с первым входом множителя блока четвертого умножителя, выход которого подклю 1чен к первому входу блока седьмого регистра, выход которого соединен с третьим входом множителя блока первого умножителя, и с первым входом множимого блока четвертого умно- жителя, а второй вход связан с вто О рыми входами множителя и множимого блока четвертого умножителя и с выходом четвертого сумматора, первый вход которого соединен с выходом блока восьмого регистра, первый вход ко торого связан с выходом блока четвертого умножителя., второй вход четвертого сумматора является четвертым информационным входом устройства, второй вход блока восьмого регистра 2 О связан с первыми входами первого, второго и третьего элементов И и с пятым информационным входом устройства, выходы блока управления с первого по восьмой подключены к управ" ляющим входам блоков первого, второго, третьего, четвертого, пятого, шесто" го, седьмого и восьмого регистров соответственно, выходы блока управления с девятого по двадцатый подключе-Зо ны к первым, вторым и третьим управ.ляющим входам блоков первого, второго, третьего и четвертого умножителей, выходы блока управления с двадцать первого по двадцать третий35 подключены к вторым входам первого, второго и третьего элементов И, двадцать четвертый выход блока управления является выходом признака окончания операции устройства, пер О вый и второй входы синхронизации блока управления являются первым и вторым входами синхронизации уст-, ройства, первый информационный вход блока управления является первым вхо,. дом устройства, каждый блок регистра . оодержит мультиплексор и регистр, причем первый и второй входы блокарегистра являются первым и вторым информационными входами мультиплек сора, управляющий вход которого связан с управляющим входом блока ре" гистра, а выход соединен с входом регистра, выход которого является выходом блока регистра, каждый блок 55 умножителя содержит два мультиплексора и умножитель, причем первый и второй входы множимого блока умножителя соединены с соответствующимиинформационными входами первогомультиплексора, первый, второй итретий входы множителей блока умножителя подключены к соответствующиминформационным входам второго мультипленсора, первый и второй управляющие входы которого являются соответствующими управляющими входамиблока умножителя, управляющий входпервого мультиплексора подключен ктретьему управляющему входу блокаумножителя выходы первого и второгомультиплексоров соединены с входамимножимого и множителя, выход которого является выходом блока умножителя.Блок управления содержит счетчикадреса, узел памяти, регистр минрономанд, причем первые входы счетчикаадреса и узла памяти являются первыми вторым входами синхронизации блонауправления соответственно, информа-ционный вход которого является вторым входом счетчика адреса, выходкоторого подключен к второму входуузла памяти, выход которого связанс входом регистра микрокоманд, двадцать четыре выхода которого являютсясоответствующими выходами блока управления,На фиг.1 приведена. структурнаясхема устройства для вычисления полиномов; на Фиг.2 - схема блбка регистра; на фиг.3 - схема блока умножителя; на Фиг.4 - схема блокауправления; на фиг.5 .- порядокпоступления коэффициентов,полиномана информационные входы устройствав общем случае; на фиг.6 - то же,для случая, когда степень полиномав = 13Устройство содержит блок 1 первого регистра, первый выход 2, блок 3 первого умножителя, первый сумма- .тор ч, блок 5 второго регистра, первый информационный вход 6, блок 7 третьего регистра, блок 8 второго умножителя, блон 9 четвертого ре" гистра, второй сумматор 10, второй информационный вход 11, блок 12 пятого регистра, блок 13 третьего умножителя, блок 14 шестого регистра, третий сумматор 15, третий информационный вход 16, блок 17 четвертого умножителя, блок 18 седьмого регистра, четвертый сумматор 19, блок 20 восьмого регистра, четвер910194 тый информационный вход 21 первый элемент И 22, второй элемент И 23, третий элемент И 24, пятый информационный вход 25, блок 26 управления, выход 27 признака окончания операции, первый вход 28 синхронизации устройства, второй вход 29 синхрони- зациИ устройства, первый вход 30 устройства, мультиплексоры 31, регистры 32, мультиплексоры 33, муль О типлексоры 34, умножители 35, счетчик адреса 36, узел 37 памяти, запоминающее устройство, регистр 38 микрокоманд. 20 Выход блока первого регистрасоединен с первым выходом 2 устройства и с первым входом множимогоблока первого умножителя 3, вто:рой вход множимого которогосвязан с выходом первого сум",матора 4 с первым входом множителя блока первого умножителя3 и с первым входом блока первогорегистра 1, выход блока первого множителя 3 соединен с вторым входомблока первого регистра 1 и с первымвходом блока второго регистра 5,выход которого подключен к первомувходу первого сумматора 4, второй З 0вход которого является первым информационным входом устройства 6, выходблока третьего регистра 7 соединенс вторым входом множителя блока пер вого умножителя 3 и с первым входоммножимого блока второго умножителя 8,выход которого связан с первыми входами блоков третьего 7 и четвертого9 регистров, выход которого соединен с первым входом второго сумматора 4010, второй вход которого являетсявторым информационным входом устройства 11, а выход подключен к входумножителя, второму входу множимогоблока второго умножителя 8 и квторому входу блока третьего регистра 7, первый вход блока 12пятого регистра связан- с выходомблока 13 третьего умножителя ис первым входом блока 14 шестого регистра, выход которого сое 50динен с первым входом третьего сумматора 15, второй вход которогоявляется, третьим информационным выходом 16 устройства, а выход подклю- .чен к первому входу множимого, к входу множителя блока 13 третьего умножителя и к второму входу блока 12пятого регистра, выход которого сое 10динен с вторым входом множимого блока 13 третьего умножителя и с первым входом множителя блока 17 четвертого умножителя, выход которого подключен к первому входу блока 18 седьмого регистра, выход которого соединен с третьим входом множителя блока 3 первого умножителя и с первым входом множимого блока 17 четвертого умножителя, а второй вход связан с вторыми входами множителя и множимого блока 17 четвертого умно- жителя и с выходом четвертого сумматора 19, первый вход которого соединен с выходом блока 20 восьмого регистра, первый вход которого связан с выходом блока 17 четвертого умно- жителя, второй вход .четвертого сумматора 19 является четвертым информационным входом 21 устройства; второй вход блока 20 восьмого регистра связан с первыми входами первого 22, второго 23. и третьего 24 элементов И и с пятым информационным входом 25 устройства, первые восемь выходов блока 26 управления подклю-, чены к управляющим входам блоков первого 1, второго 5, третьего 7, четвертого 9, пятого 12, шестого 14, седьмого 18 и восьмого 20 регистров, следующие двенадцать выходов подключены к первым,. вторым и третьим управляющим входам блоков первого 3, второго 8, третьего 13 и четвертого 17 умножителей соответственно, следующие три выхода подключены к вторым входам первого 22, второго 23 и третьего 24 элементов И, последний выход блока управления является выходом 27 признака окончания операции устройства, первый и второй входы синхронизации блока управления являются первым 28 и вторым 29 входами синхронизации устройства, первый вход блока управления является первым входом 30 устройства. В блоках регистров. первые и вторые входы являются первыми ивторыми информационными входами первых мультиплексоров 31, управляющие входы которых связаны с управляющими входами блоков регистров, а выходы соединены с входами регистров 32, выходы которых являются выходами блоков регистров, в блоках умножителей первые и вторые входы множимых соединены с информационными входами вторых мультиплексоров 33, первые,25 Введение новых элементов и связей позволяет увеличить быстродействие устройства при вычислении полиномов с Фиксированными коэффициентами. Время вычисления полинома степени и на известном устройстве определяютТ= й+ 13 10194того 9, шестого 14 и восьмого 20 подключены к входам первого 4, второго10, третьего 15 и четвертого 19 сумматоров. При этом на выходах названных сумматоров образуются соответственно выражения о, х+г, х+Р д х+Р .Содержимое второго сумматора 1 о(так, как он содержит выражение х+т)эаписыва.ется в блок третьего регистра 7.Содержимое третьего 15 и четвертого19 сумматоров поступает на входымножимых и множителей третьего 13 ичетвертого 17 блоков умножителейсоответственно, возводится в квадрат и записывается в блоки шестого14 и восьмого 20 регистров, Затем15на первый 6, второй 11, третий 16 ичетвертый 21 информационные входыустройства поступают коэффициентыОВ = 1, а к, ц,.ц в соответствиис порядком, показанным на фиг.4. На20выходах сумматоров 4, 10, 15 и, 19образуются выражения 1, Ои,(ХФР 6++ 9, (Х+Р 5)+ ф Результаты первого 4, третьего 15 и четвертого 19сумматоров записывается в первый1 пятый 12 и седьмой 18 блоки регистров. Результат второго сумматора 10 ап поступает на вход множитепявторого блока умножителя 8 и умножется на содержимое третьего регистра 7. Полученный результат а(х+)записывается в третий регистр 7.Во втором, третьем (Ю)-"мциклах, где с - количество циклов,устройство работает следующим обра- З 5эом,Через пятый информационный вход25 устройства и через первый 22, второй 23 и третий 24 элементы И в блоки второго 5, четвертого 9, шестого4014 и восьмого 20 регистров записывается переменная х. На первый 6,второй 11, третий 16, четвертый 21информационные входы устройства поступают козффициенты полинома Р Р, 45Р , Р соответственно, которые напервом 4, втором 10, третьем 15 ичетвертом 19 сумматорах складываютсяс переменной х. Результаты сложениявозводятся в квадрат на первом 3, 50втором 8, третьем 13 и четвертом17 блоках умножителей, Полученныерезультаты записываются в блокивторого 5, четвертого 9, шестого14 и восьмого 20 регистров. Затем 55на первый 6, второй 11, третий 16и четвертый 2 1 информационные входыустройства поступают коэффициенты 56 14Ч, Ч, ц, ц 1,которые складываютсяна первом 4, втором 10, третьем 15,четвертом 19 сумматорах, на выходахкоторых образуются суммы (Х Ф 4) 4,(Х+Р)ф +, (Х+Р)с, (Ъ+ Р,Р + сьПолученные результаты умножаются насодержимое блоков первого 1, третьего 7, пятого 12; седьмого 18 регистров в блоках первого 3, второго 8,третьего 13, четвертого 17 умножителей. Полученные результаты И+Р 4)и 4,Ь+Р)" (ХМ")а,(Х Р,)"Ъ 3(Х+Р,)Ъ+1,(+р)фц, ц(ФР )+, записываются в соответствующие. блоки первого 1,третьего 7, пятого 12, седьмого 18регистров,В заключительном. 1-м цикле содержимое блока третьего регистра 7 умножается на содержимое блока первого регистра 1 в блоке первого умножителя 3. Результат помещается в блок первого регистра 1. Одновременно содержимое блока пятого регистра 12:умножается на содержимое блока седьмого регистра 18 в блоке четвертого умножителя 17. Результат заносится в блок седьмого регистра 18. Затем содержимое блока первого регистра 1 умножается на содержимое блока седьмого регистра 18 в блоке первого умножителя 3. Результат умножения, который является. результатом операции, записывается в блок первого регистра иэ которого поступает на первый выход 2 устройства. Одновременноблок управления 26 Формирует сигнал, который поступает с двадцать четвертого выхода блока управления 26 на выход 27 признака окончания операции устройства. После этого устройство готового к вычислению нового полинома. где й = 2 й - время, необходимое1 УМдля получения степеней х ф, ххнезависимой переменной х;