Устройство для вычисления коэффициентов полинома Советский патент 1980 года по МПК G06F17/10 

Изобретение относится к цифровой вычислительной технике и может быть использовано в автоматических системах управления. Известны устройства, которые после..довательно формируют все необходимые для вычисления коэффициента комбинации (..r 5- n-к-- Коэффициент а п.к этом случае можно вычислить в соответствии с формулой к U-K П Х.П V, где суммирование выполняется по всем возможным приведенным выше комбина- Шягл. Эти устройства содержат генерато импульсов, элементы задержки, блок эле ментов И, регистратор информации, блок анализа числа импульсов, логический сум матор и переключатель с соответствующими связями |lj . Недостатками данных устройств являются низкая производительность и избы точность аппаратуры, необходимой для вычисления коэффициентов. Известно также устройство для вычис..ления коэффициентов полинома п (yj-vx-,t) , содержащее генератор, последовательно соединенные блок ввода, блок памяти переменных, блок умножения, сумматор, блок памяти результатов, блок регистрации и устройство управления, соединенное с указанными блоками . Работа этого устройства основана на вычислении правых частей равенств коэ(| фидиектов при одинаковых степенях независимой переменной t . . Так, например, при п 4 эти равенства имеют вид: Ал 5 v.sw,v/ v..; .,Y v. .У, 43 42 l г г А37Время работы устройства является значительным и с ростом п производительность устройства резко падает. Уже при t Ю решение задачи автоматичес кого управления в некоторых системах, становится практически невозможным. Цель изобретения - сокращение времени, требуемого для вычисления всей последовательности коэффициентов 01пк(к «ОД-уП) полинома %. (y,-vx,l) и увеличение производительности устройства. Поставленная пель достигается тем, что устройство для вычисления коэффициентов полинома, содержащее генератор импульсов, блок ввода, блок памяти пе- ременны;с, блок умножения, сумматор, первый блок памяти результата, блок fieгистрации, причем выход блока ввода под соединен к первому входу блока памяти переменных, первый выход первого блока памяти результата подключен к первому входу блока умножения, второй выход пер вого блока памяти результата подключен ко входу блока perHCTpauv.H, содержит узел формирования первого импульса последовательности, семь элементов задержки, счетчик переменных, первый и второй счетчики, элемент НЕ, семь элементов И, три элемента ИЛИ блок сравнения, второй блок памяти резулы-ата, блок буферной памяти, причем выход генератора импульсов подсоединен ко входу узла формирования первого импульса последовательности,, первому входу счетчика переменных и первому входу первого элемента И, выход узла формирования первого импульса последовательности подключен к первому входу первого элемента ИЛИ, вторые входы счетчика переменных и первого элемента ИЛИ соедине ны с выходом первого элемента И, а третий вход счетчика переменных подклю чен к другому выходу блока ввода, выход счетчика переменных подключен ко второму входу первого элемента И и вто рому входу блока переменных, выход блока сравнения подключен ко вход элемента НЕ, третьему входу первого элемента И и первому входу второго эле мента И, выход первого элемента ИЛИ подсоединен ко входу первого элемента задержки, второго элемента задержки, первому входу третьего элемента И и первому входу второго элемента ИЛИ, группы выходов первого и второтч счетчика подключены к соответствующим вхо« дам блока сравнения, нулевой вход пер4вого счетчика подсоединен к первому вълходу третьего элемента задержки, а единичный вход связан с выходом четвертого элемента задержки, выход первого счетчика подсоединен ко второму входу второго элемента И, выход второго элемента ИЛИ подсоединен ко Входу четвертого и пятого элемента задержки, выход пятого элемента задержки подключен к первому входу четвертого элемента И, второй вход которого соединен с выходом элемента НЕ, а выход - с первым входом третьего элемента ИЛИ, выход блока памяти переменных подключен ко второму входу третьего элемента И, выход третьего элемента ИЛИ соединен со входом, блока умножения, выход которого подключен ко входу пятого элемента И, второй вход которого и шестого элемента задержки подсоединены к выходу первого элемента задержки, а выход uiecToro элемента задержки - к первому входу шестого элемента И, второй вход которого связан с выходом сумматора, а выход - со Входом блока буфер- ной памяти, с первым входом первого блока памяти результата п вторым входом второго элемента ИЛИ, выход третьего элемента задержки соединен с первым входом седьмого элемента И и вторым входом второго блока памяти результата, выход которого соединен с первым входом первого блока паNJiяти результата, выход блока буферной памяти подключен ко второму входу седьмого элемента И, выход которого соединен со вторым входом первого блока памяти результата, выход пятого элемента И соединен со входом сумматора, выход второго элемента задержки подключен к третьему входу BTopoixj элемента И, выход которого подсоединен ко входам третьего и элементов задержки, а выход седьмого элемента задержки подключен ко входу второго счетчика. Зто позволяет вычислять значения коэффициентов на основе реккурентного соотношения: -,,ai.,.,y,a...,ji Wx;l,...,ni j.o,-i,...,,. ., ДЛ9 всех Е-о/,...,п) а О ПРИ г S. Реализация этого соот юшения обесечивает решение поставленной з/.щачи а П о-омшагч реккурсии ( i П ), Так при п 3 будет иметь: XQ +va 7.Vyа л-4 г 40 42 л- Ao lм- v v ,--,, а,, «Зд VaWiV «зг-- «aл V27-- s V2 vл; Повышение производительности устройства обеспечивается за счет принципиального сокращения числа операций умноже- ния и сложения, необходимых для вычисле ния всей последовательности коэффициентов Of, { К 0, 1, ..., П ). На чертеже представлена функциональная схема одного из вариантов устройства для вычисления коэффициентов полинома )К 0, у, Устройство имеет блок 1 ввода, пред- назначенный для параллельного приема переменных из аппаратуры АСУ и ввода переменнь.х в блок 2 памяти переменно1х. Для обеспечения возможности автоном . ной работы устройства в блок 1 ввода введено устройство перевода вводимых значений переменных из десятичной системы счисления в двоичную. Блок 1 ввода соединен со счетчиком 3 переменных, предназначеннь1м для подсчета введенных переменных. Этот счетчик является ревер сивным, т.е. считает от О до п и от h до О. В предлагаемом варианте П 10 Счетчик выполнен на интегральных схемах 133 серии. Блок памяти 2 переменных предназна чен для хранения переменных X и У и представляет собой две памяти: память X и память У с устройствами управле ния. Памяти выполнены на интегральных схемах 134 серии. Блок 2 памяти переменных через элемент 4 И, элемент 5 ИЛИ соединен с блоком 6 умножения, который предназначен для умножения множимого на все разряды множителя, со старшего. Б качестве множимого берутся переменные X и У , а в качестве множителя - содержимое двух ячеек блока 7 памяти результата. Причем блок 6 предназначен для параллельного умножения ,- НУ, О , где X. и V; переменные из блока гшмяти переменных 2, а CXj. д и - значения соответст- вуюших ячеек блока 7 памяти результатов (Onj. и Orv.j ). Блок 6 умножения выполнен на интегральных схемах 133 серии. Блок умножения соединен через элемент 8 И с сумматором 9. Сумматор 9 параллельного действия выполнен на интегральных схемах 133 серии. Сумматор 9 соединен через .элемент 1О И с блоком 11 буферной памяти. Блок 11 буферной памяти выполнен аналогично блоку 7 памяти результатов на регистрах и соединен с блоком 7 памяти результатов через элемент 12 И. Boixoa генератора 13 импульсов соединен с узлом 14 формирования первого импульса. Этот узел представляет собой триггер, элемент И и элемент задержки. Причем первый вход элемента И является входом узла 14 формирования первого импульса, второй вход элемента И сойдинен с единичным выходом триггера, а вход элемента И узла - с -еяиннчным выходом триггера. Выход элемента И через элемент задержки соединен с нулевым входом триггера и является также выходом узла 14 формирования выдачи первого импульса. Он соединен через элемент 15 ИЛИ, через элемент 4 И с блоком 6 умножения; через элемент 16 задержки и элемент 8 И с сумматором 9; через элемент 17 задержки и элемент 10 И - с блоком 11 буферной памяти и единичным входами блока 18 счетчиков памяти результатов и первым эходом элемента 19 ИЛИ. о 18 счетчиков памяти результатов предназначен для управления вьздачей результатов из двух соседних ячеек блока 7 памяти на блок 6 умножения и представляет собой два счетчика, один из которых предназначен для определения ячейки для умножения ее содержимого на X , а другой - для определения ячейки для умножения ее содержимого на У Второй вход элемента 19 ИЛИ соединен с выходом элемента 15 ИЛИ и через элемент 2О задержки с первым входом элемента 21 И разрешения копирования, который представляет собой трехвходовой элемент И. Выход элемента 19 ИЛИ соединен через элемент 22 задержки, элемент 23 И, элемент 5 ИЛИ с блоком умножения 6 и, через элемент 24 задержки с единичным входом счетчика 25 циклов, представляющего собой счетчик, выходы KOTOpoixi соединены с блоком 26 ср авнения и через второй вход эле- 77 мента 21 И разрешения копирования , элемент 27 задержки с регистром 28 счетчика. Выход блока 26 сравнения соединен с третьим входом элемента 21 разрешеВИЯ копирования, а также через элемент 29 НЕ со вторым входом элемента 21 И Выход элемента 21 И разрешения копирования, кроме того, соединен через элемент ЗО задержки с нулевыми входами счетчика 25 циклов блока 18 счет чиков памяти результатов и вторым входом элемента 12 И, Выход блока 7 памяти результатов соединен с блоком 31 регистрации. Блок 31 регистрации служит для сопряжения с аппаратурой АСУ, если гафор машш используется в следующих устройствах или для отображения информации средствами индикации, выполненными на элементах ИН-17. Для обеспечения возможности автоном ной работы устройства в блоке регистрации 31 введено устройство перевода результата из двоичной систем.1 счисления в десятичную. Выход генератора 13 соединен также с первым входом элемента 32 И разрешения прохождения импульсов, второй вхо которого соединен с блоком 26 сравнени а третий вход с выходом счетчика 3 пе ременных. Выход элемента 32 И разре шения прохождения импульсов соединен с входом элемента 15 ИЛИ. Элемент 32 И. разрешения прохождения импульсов представляет собой трехвходовую схему И Конструктивно устройство вычисления коэффициентов полинома выполнено в вид элемента АСУ, а гакле как автономное устройство, представлякадее собой спец-. вычислитель. В рамках предлагаемого изобретения возможны и другиетехнические региеняя федлагаемых блоков. Например, в блока памяти могут быть использованы тонкие магнитные плепкн, блок регистрации может содержать электрофицированную пи шушую машинку (например, типа Консул дисплей (например, СИД-1000 или ЕС- 7066) с блоками управления. В схемах И, ИЛИ, счетчиках и других блоках могу бьггь использованы интегральные элементы других серий (например, 137, 187 серии). Устройство работает следующим об разом. Перед началом работы сигналом с синхронизатора АСУ усгройство ариводктся в исходное состояние, а именно: в блоке 2 памяти переменных, в блоке 11 памяти ( результатов 7) во все ячейки записываются нули, в блоке 7 памяти результатов во вторую ячейку записьта- ется единица, а во все остальнь1е ячейки - нули; счетчик 25 циклов и счетчик 3 11еременнь1Х устанавливается в нуль; в-блоке 18 -счетчиков, памяти результатов счетчик 7 управления блоком памяти результатов, предназначенный для реализации операции умножения с использованием переменной X , устанавливается в нуль, а счетчик 7 управления блоком памяти результатов, предназначенный для реализации операции умножения с использованием переменной У , устанавливается в единицу; в регистр 25 счетчика циклов записывается цифра 2 , и триггер узла 14 формирования первого импульса последовательности устанавливается в . Через блок 1 ввода в блок 2 памяти переменных вводятся значения У. и У . Одновременно на счетчике 3 переменных устанавливается их число. По окончании ввода переменных включается генератор 13. Импульсы с генератора 13 поступают на узел 14 формирования первого импульса последовательности. Этот элемент пропускает TOJibko один первый импульс, который,проходя через элементы 15 ИЛИ, 4 И, 5 ИЛИ копирует состояние первых ячеек блока 2 памяти переменных в блоке 6 умножения. На блок 6 умножения поступает также информация из 1-ой и 2-ой ячеек блока 7 памяти результатов, после чего выполняются операции умножения и VA, «2 , где а и а - содержимое соответствующих ячеек блока памяти результатов 7, а У и У - содержание первых ячеек блока 2 памяти переменных. Этот же импульс через элемент 16 задержки и элемент 8 И пересылает результат из блока 6 умном;ения на сумматор 9. В сумматоре 9 прО{ зводится сложение результатов, полученных в. блоке 6 умножения, и через элемент 17 задержки и элемент Ю И производится копирование результата суммирования па блок 11 буферной памяти. же импульс поступает на блок 18 счетчиков памяти результатов и через элемент 19 ИЛИ, элемент 24 задержки - на счетчик 25 циклов,а через элемент 32 зедержки, элемент 23 И и 5 ИЛИ - на копирОЕйние состояния . 9.7 ячеек на блок 6 умножения, причем с блока 7 памяти результатов поступает информация 2-ой и 3-сй ячеек и выполняются операции Х 01 „ и v ct, . Затем производится суммирование и запись ре эультата суммирования в блок 11 буферной памяти. Импульс копирования результата суммирования на блок 11 буферной памяти добавляет единицу к счетчику 25 циклов. Блок 26 сравнения выдает сигнал сравнения, который разрешает элементу 32 И разрешения прохождения импульсов пропустить импульс с генератора 13. Это импульс вычитает из счетчика 3 переменных единицу и, проходя через элементы 15 и 19 ИЛИ, элемент 24 задержки, прибавляет единицу к счетчику 25 циклов, а также через элемент 21 И раз решения копирования, элемент 27 задерж ки, а также записывает новое состояние счетчика 25 циклов на регистр 28 счетчика. Этот же импульс через элемент 30 задержки устанавливает в нуль счетчик 25 циклов, счетчики 18 блоков счетчиков памяти результатов, и через элем«1т 12 И копирует информацию из блока 11 буферной памяти на блок 7 памяти результатов. Тот же импульс со схемы 32 разрешения прохождения импульсов через схему 13 ИЛИ копирует содержимое ячеек х и V из блока 2 буферной памети через элементы 4 И и 5 ИЛИ на блок 6 умножения, где выполняются операции умножения Х„ а и Результат умножения пересылается на сумматор 9 и после суммирования в блок 11 буферной памяти. Работа устройства продолжается аналогично описанному выше, но число циклов будет на единицу больше. то есть три. Затем происходит разреше- кие прохождения следующего импульса с генератора 13 и работа устройства повторяется, причем при каждом следующем повторении число циклов будет- увеличиваться на единицу до тех пор, пока счетчик 3 переменных не станет равным нулю После этого происходит запрещение прохождения импульсов с генератора 13 и вычисления заканчиваются. Результат вычислений коэффициентов . «M b,iM «i-Aji ,...,n j-0,л,..., ДА9все е-о/, U. Q О ПРИ Г 4 S передается в блок регистрации 31. 14 Оценка технико-акономическо) эффек- та от использования изобретения проводилась теоретически и методом математического моделирования. Результаты теоретического расчета и математического моделирования показывают, что использование предлагаемого устройства позволяет вычислять коэффициенты Of пoлинo Ja a V n () реккурентно. При этом сокращается число выпопненных операций, что обеспечивает увеличение скорости вычисления коэффициентов полинока и повышение производительности специализированности АСУ. Так, например, уже при п 5 число операций, выполняемых в известном устройстве, составляет: умножения - 128, сложения - 26, а в предлагаемом устройстве - соответственно 12 и 6. При этом время вычисления сокрйшеегся примерно в 10 раз. При п 10О получить результат с использован нем исэвестного устройства практически невозможно, так как время решения будет составлять годы, а в предложенном устройстве время решения задачи занимает менее 1 мин. Формула изобретения Устройство для вычисления козффициентов полинома, содержащее генератор импульсов, блок ввода, блок памяти переменных, блок умножения, сумматор, первый блок памяти результата, блок регистрации, причем вьжод блока ввода подсоединен к первому входу блока памяти переменнь1Х, первый выход первого блока памяти результата подключен к первому блоку умножения, второй выход первого блока па- мяти результата подключен ко входу блока регистрации, отличающееся тем, что, с целью увеличения производительности, оно содержит узел формирова- ния первого импульса последовательности, семь элементов задержки, счетчик переменных, первый и второй счетчик, элемёнт НЕ, семь элементов И, три элемента ИЛИ, блок сравнения, второй блок памяти результата, блок буферной памяти, причем выход генератора импульсов подсоединен ко входу узла формирования первого импульса последовательности, первому входу счетчика переменных и пер- вому входу первого элемента И, выход узла формирования первого импульса последовательности подключен к первому входу первого элемента ИЛИ, вторые вхоаы