Устройство для вычисления полиномов

Союз Советскнх Социалистических Республик(51)М. Кл 22) Заяв 0206.78 (21) 2623220/18-24ием заявки йо с присоедине (23) Приорите 06 Р 15/32 арствеииыи ком СССР делам изобретеи и открытий(7) Заявител 54) УСТРОИСТВО Д ИСЛЕНИЯ ПОЛИНОИО вхооИзобретение относится к вычислительной технике и предназначенодля вычисления алгебраических полиномов с высокой скоростью.Известны устройства, содержащиерегистры, сумматоры и счетчики (11,Однако эти устройства при повышенных требованиях к быстродействию не могут обеспечить необходи"мую скорость вычисления алгебраических полнномов,Наиболее близким по техническойсущности и достигаемому результатук предлагаемому является устройство, содержащеепервый регистр, выход которого подключен к входу множителя первого умножителя, входмножимого которого соединен с выходом второго регистра, первый входкоторого подключен к первому выходутретьего регистра, вход которого соединен с выходом первого сумматора,первый вход которого подключен квыходу первого умножителя, счетчикциклов, первый вход которого соединен с первым входом устройства,а выход счетчика циклов подключенк первому выходу у:тройства (2.Недостатком такого устройстваявляется низкое его бы т родеиствие.кий институт им, В, Ч. Калмыкова среднего специального я РСФСРЦелью предполагаемого изобретенявляется повышение быстродействия,Поставленная цель достигаетсятем, что в устройство для вычисления полиномов, содержащее первый регистр, выход которого подключен к входу множителя первого умножителя, вход множимого которого соединен с выходом второго регистра, первый вход которого подключен к первому выходу третьего регистра, вход которого соединен с выходом первого сумматора, первый вход которого подключен к выходу первого 15 умножителя, счетчик циклов, первыйвход которого соединен с первым входом устройства, а выход - соеди не н с пе рвым выходом ус т ройс т в а, введены три умножителя, три сумма тора, регистры, блок задания количества циклов, четыре блока памяти блок управления записью, формирователь начального адреса, причем выходы блока управления записью соединены соответственно с первыми входами блоков памяти, вторые входы которых подключены к второму ду устройства, и к входу четверт го регистра, выход первого блока 30 памяти соединен со вторыми входамивторого регистра и первого сумматора, выход второго блокапамяти соединен с первыми входами пятого регистра и второго сумматора, первый выход которого соединен через шестой регистр со вторым входом пятого регистра, выход первого регистра соединен с первыми входами второго, третьего и четвертого умножителей, выходы которых соединены соответственно со вторым входом второго сумматора и первыми входами третьего и четвеютого сумматоров, первые выходы которых подключены соответственно к входам седьмого.и восьмого регистров, выход тюетьего блока памяти соединен с первыми входами девятого регистра и вторым входом третьего сумматора, второй выход которого соединен со вторым входом четвертого сумматора, выход седьмого регистра соединен со вторым входом девятого регистра, первый и второй выходы восьмого юегистра подключены соответственно к второму выходу устройства и к пеювому входу десятого регистра, выход четвертого блока памяти соединен со вторым входом десятого регистра и с третьим входом четвертого сумматора, первый выход второго. Умножителя соединен с вторым входом второго сумматора, второй выход котоюого подключен к. третьему входу третьего сумматора, второй выход третьего регистра соединен с третим входом второго сумматора, первый выход четвертого регистра и выход пятого регистра соединены соответственно со вторым и третьим входами второго умножителя, второй выход которого подключен ко входу пеювого регистра, второй выход четвертого регистра - к второму и третьему входу четвертого умножителя и ко второму входу третьего умножителя, выход четвеютого умножителя соединен с третьим входом третьего умножителя, четвертым и пятым входами второго умножителя и со входом одиннадцатого регистра, выход которого соединен с четвертым входом третьего умножителя, пятый вход которого подключен к выходу девятого регистра, второй выход третьего умножителя соединен через двенадцатый юегистр с четвертым входом четвертогЬ умножителя, пятый вхсщ которого соединен с выходом девятого регистра, третий вход устройства соединен через тринадцатый регистр с входами формирователя начального адреса и блока задания количества циклов, выходы которых соединены соответственно со входом блока управления записью и вторим входом счетчика циклон.На Фиг.1 представлена блок-схема устройства для вычисления плиномов; на Фиг,2 - размещение коэффициентов.60 65 Счетчик 29 циклов служит для определения момента окончания вычисления полинома,Работа устройства (на примере вычисления полинома степени и=10) заключается в следующем. полинома степени и=15; на фиг, 3размещение коэффициентов в ячейкахблоковУстройство для вычисления полимонов содержит регистры 1 и 2, умножитель З,сумматор 4, регистры 5умножитель В, сумматор 9, регистры,10-12, умножитель 13, сумматор 14,регистр 15-17, умножитель 18, сумматор 19, регистр 20, блоки 21-24 памяти, блок 25 управления записью,формирователь 26 начальгого адреса,регистр 27, блок 28 задания количества циклов, счетчик 29 циклов,входы 30-32 устройства, выходы 33-34устройства,В устройстве иолиномы видаи и У=ах +а и- х ++ах +а ргде У - значение вычисляемогополинома;а, а., аар - коэффициенты поли-х - независимая перемен-.ная,п а 15 - степень полинома,целое положительное число, разбива 2 Б ются на четыре ветви,в которых вычисляются значения У. , Уг ,У ,У 4сумма которых равна У,Причем значения УУУЗ У 4 вычисляются одновременно. В устЗО ройстве могут вычисляться полиномы любой степени я 415. При и 4 15коэффициенты при отсутствующихстарших степенях х(аа,4,а+1)полагаются равными нулю. КоэффициЗ 5 енты аа , а,ар поступаютиз памяти на вход 30 устройства иразмещаются. в блоках 21 - 24В случае, когда п 15 отсутствующие коэффициенты заменяются в ячейках блоков памяти нулями, При этом,если отсутствуют все коэффициенты,занимающие первые ячейки блоков памяти, то все оставшиеся коэффициентысмещаются в своих блоках на однуячейку вверх до тех пор, пока хотя45 бы в одном из блоков первая ячейкабудет содержать ненулевой код коэфФициента, Изменение положения коэффициентов в ячейках блоков памятисовмещается с их загрузкой с помощью5 блоков 26 и 25.Определение количества цикловработы устройства, необходиьвх длявычисления полинома заданной степени, осуществляется блоком 28. Количество циклов 1 определяется в зависимости от степени заданного полинома п следующим образом1=2 при 1 п 71=3 при 8 и 111=4 при 12 п 415Вычисление полинома начинается с того, что в регистр 27 по входу 31 устройства поступает порядок заданного полинома, Блок 28 определяет необходимое количество циклов вычисления п=3, которое Фиксируется в счетчике циклов 29, Блок 26 определяет адрес ячейки, начиная с которого поступающие в устройство коэффициенты полинома размещаются в блоках памяти. Адрес с выхода блока 26 поступает в блок 25 управления записью. По входу 30 устройства поступают значения независимой переменной х, которые записываются в регистр б; и затем коэффициеиты полинома а,р,аэ,а, а(,ао. Коэффи 1 циенты поступают в устройство в порядке уменьшения их номеров и по сигналам с выходом блока 25 управления записью размещаются в ячейках блоков 21-24 (фиг. 3) . 20Значение независимой переменной х с второго выхода регистра б поступает на первые входы множимого и множителя умножителя 18 и на первый вход множимого умножителя 13, Значение х , 25 полученное в умножителе 18, с первого его выхода записывается в регистр 11 и поступает на третий вход множителя умножителя 13 и на первые входы множимого и множителя умножителя 8, 3 р Полученное на первом выходе умножителя 13 значение х записывается в регистр 16. На первом выходе умножителя 8 получается значение х 4, которое записывается в регистр 1, Одновременно, из блоков 21-24.считываются значения коэффициентов, находящихся в первых ячейках, и записываются.соответственно в регистры 2, 7, 12, 17. Выход регистра 1 подключается к входу множителя умножителя 3 и к входам 40 умножителей 8, 13, 18, а к входам множимого умножителей 3,8, 13, 18 подключаются соответственно выходы регистров 2,7,12, 17, Затем во всех умножителях одновременно выполняется 4 операция умножения, Результаты умножения с выхода умножителя 3 и с вторых выходов умножителей 8, 13, 18 поступают соответственно на первые входы сумматоров 4, 9, 14, 19, на вторые входы которых подаются значения коэффициентов, считанные иэ вторых ячеек блоков памяти, Результат с первых выходов сумматоров. записывается в регистры 5, 10, 15, 20 и далее на них передается через вторые входы в регистры 2, 7, 12, 17, После чего из задержимого счетчика 29 циклов сигналом, поступающим по входу 32 устройства, вычитается единица. На этом заканчивается первый 60 цикл вычисления, в результате выпол" нения которого в регистре 2 находится значение ах +а,в регистое 74значение ах 4+а, .в регистре 12 значение з,о х 4+а, н регистре 17 - 65 значение а и в счетчике циклов 29- значение 1=2.Второй цикл вычисления выполняется аналогично первому за исключением того, что оезультат из регистра 5 не передается в регистр 2, а хранятся так,. до следующего цикла, После выполнения второго цикла вычисления в регистре 5 находится значение (а 8 х 4+ ах +ао , в регистре 7 - значение (ах 4+а)хф+а, в регистре 12 - значение (,а ох +а)х+а, в регистре 17 - значение ах 4+аз и в счетчике циклов 29 - значение 1=1.При 1=1 выполняется завершающийцикл вычисления, в котором первыйвыход регистра 6 подключается к второму входу множителя умножителя 8, к третьему входу множимого которого подключен выход регистра 7, выход регистра 11 подключается к четвертому входу множителя умножителя 13, пятый вход множимого которого соединен с выходом регистра 12, выход регистра 16 подключается к четвертому входу умножителя 18, пятый вход которого соединен с выходом регистра 17, второй выход регистра 5 подключается к третьему входу сумматора 9, первый вход которого соединен с вторым выходом умножителя 8,второй выход сумматора 9 подключается к третьему входу сумматора 14, первый вход которого соединен с вторым выходом умножителя 13, второй выход сумматора 14 подключается к второму входу сумматора 19, первый вход которого соединен с вторым выходом умножителя 18. Полученное на первом выходе умножителя 8 значение (а х +4о ах +а)х поступает на первый вход сумматора 9 и суммируется там с операндом (ах +ад)х +а, поступающим4 4на третий вход сумматора с второго выхода регистра 5. Сумма с второго выхода сумматора 9 поступает на третий вход сумматора 14 и суммиру 4 4 ется там с произведением (а ох +а) х аф) х, поступающим с первого выхода умножителя 13, Сумма с второго выхода сумматора 14 поступает на тре.тий вход сумматора 19, на первый вход которого поступает произведение (аъх+аДх с первого выхода ум 3ножителя 18. С выхода сумматора 19 значение вычисляемого полинома записывается в регистр 20. Из содержимого счетчика циклов 29 вычитается единица, после чего в устройство управления по второму выходу 34 выдается сигнал 1=0, по которому вычисление полинома заканчивается и результат с первого выхода регистра 20 по первому выходу 33 выдается иэ устройства.Применение предлагаемого устройства позволяет увеличить скорость вы 81344 3числения алгебраических полиномов в4 раза.Формула изобретенияУстройство для вычисления полиномов, содержащее первый регистр, выход которого подключен к входу множителя первого умножителя, вход множимого которого соединен с выходом второго регистра, первый вход которого подключен к первому выходу третьего регистра, вход которого соединен с выходом первого сумматора, первый вход которого подключей к выходу первого умножителя, счетчик циклов, первый вход которого соединен с первым входом устройства, а выход - соединен с первым выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия,в него введены три умножителя, три сумматора, регистры, блок задания количества циклов, четыре блока памяти, блок управления записью, формирователь начального адреса, причем выходы блока управления записью соединены соответственно с первыми входами блоков памяти, вторые входы которых подключены к второму входу устройства, и к входу четвертого регистра, выход первого блока памяти соединен со вторыми входами второго регистра и первого сумматора, выход второго блока памяти соединен с первыми входами пятого регистра и второго сумматора,первый выход которого соединен через иестой регистр со втопым входом пятого регистра, выход первого регистра соединен с первыми входами второго, третьего и четвертого умножителей, выходы которых соединены соответственно со вторым входом второго сумматора и первыми входами третьего и четвертого сумматоров, первые выходы которых подключены соответственно к входам седьмого И восьмого регистров, выход третьего блока памяти соединен с первыми входами девятого регистра и вторым входом третьего сумматора, второй выход которого соединен со вторым входомчетвертого сумматора, выход седьмогорегистра соединен со втогым входомдевятого регистра, первый и второйвыходы восьмого регистра подключены 5соответственно к второму выходу устройства и к первому входу десятогорегистра, выход четвертого блока памяти соединен со вторым входом десятого регистра и с третьим входом четвертого сумматора, первый выход второго умножителя соединен. с вторымвходом второго сумматооа, второй выход которого подключен к третьемувходу третьего сумматора, второй выход тпетьего регистра соединен с.15 третьим входом второго сумматора,первый выход четвертого регистра ивыход пятого регистра соединены соответственно со вторым и третьимвходами второго умножителя, второй 20 выход которого подключен ко входупервого регистра, второй выход четвертого регистра - к второму и третьему входу четвертого умножителя ико второму входу третьего умножите ля, выход четвертого умножителя,соединен с третьим входом третьего умножителя, четвертым и пятым входамивторого умножителя, и со входом одиннадцатого регистра, выход которогосоединен с четвертым входом третьегоумножителя, пятый вход которого подключен к выходу девятого регистра,второй выход третьего умножителя соединен через двенадцатый регистр счетвертым входом четвертого умножителя, пятый вход которого соединенс выходом десятого регистра, третийвход устройства соединен через тринадцатый регистр с Входами формирователя начального адреса и блока за дания количества циклов, выходы которых соединены соответственно совходом блока управления записью и.вторым входом счетчика циклов,45 Источники инФормации,принятые во внимание при экспертизе1. Авторское свидетельство СССР9 556446, кл. 6 06 Р 15/32 1976,2, Патент США У 3978326,кл. 235-152, 1970 (прототип).813443 тель Н.ПалееваМ.Табакович . КорректорГ.Решетн Сост Техр Редактор И.Ка Заказ 775 6 3 130 илиал ППППатент , г,Ужго п,Проектная, 4 НИИПИ Гпо де Москв раж 745ударственногом изобретенийЖ, Раушск омитотк наб Подписноа СССРтийд. 4/5