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

 

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ) ! !, !», !. ! (61) Дополнительное к авт. саид-ву (53)М. Кл.

Ы 06 Р 15/34 (22) Заявлено22.02.78 (21) 2571455/18-24 с присоединением заявки Ж

Говудврстввкиык комитет (23) Приоритет оо делам нзвбретеиий и открытий

Опубликовано15.05.80. Бюллетень М 18 (53) УДК681.14 (088.8) Дата опубликования описания 18.05.80 (72) Авторы изобретения

В. П. Емельянов, B. С. Калашников, B. И. Матвеев и В. И. Тихомиров (7I) Заявитель (54) УСТРОЙСТВО ДЛЯ Вь1ЧИСЛЕНИЯ

КОЭФФИЦИЕНТОВ ПОЛИНОМА .

Изобретение относится к цифровой вычислительной технике и может быть использовано в автоматических системах управления.

Известны устройства, которые последовательно формируют все необходимь!е для вычисления коэффициента комбинации ,Х Х ...Х,.Х. У У .,У..у. 1 g в). l5 34 J2 " l5 )п-K I

Коэффициент ат, в этом случае можно вычислить в соответствии с формулой к и-к

xт1 х и у г. где суммирование выполняется по всем возможным приведенным выше комбина15 ц3тям. Эти устройства содержат генератор импульсов, элементы задержки, блок элементов И, регистратор информации, блок анализа числа импульсов, логический сум20 матор и переключатель с соответствуюшими связями (1)

Недостатками данных устройств являются низкая производительность и избыточность аппаратуры, необходимой для вычисления коэффипиентов.

Известно также устройство для вычиси К .ленин коэффициентов полинома 2 o„Kt

О K. o

= > (y;+v;1), содержащее генератор, последовательно соединенные блок ввода, блок памяти переменных, блок умножения, сумматор, блок паметти результатов, блок регистрации и устройство управления, соединенное с указанными блоками (2)

Работа этого устройства основана на вычислении правых частей равенств коэффициентов нри одинаковых степенях независимой переменной 1 °

Так, например, при и =4 эти равенст ва имеют вид:

О - 4 Х4 Y4y2 394+ 4 2 3 4 4 2у3 4 т

4.1, 2

=ЬУХ Х+УХ У ) ХУУХ УХХУ

42 42 3< 4 234 4234 4 2 34

I - Х Ч К ь + Х х У У

34 4234 а =ухх х+кьх х3)ему„Ухххх у

43 4 2 3 4 42 3 4 " 3 4 g х т4

t !

Q - Х Х Х

44 423

Реелизация этого соотношения обеспечивает решение поставленной задачи на tl -ом шаге реккурсин (1 = И ).

3 73471

Время работы устройства является значительным и с ростом и производительность устройства резко падает. Уже при 5 ) 10 решение задачи автоматичес-, кого управления в некоторых системах. становится практически невозможным.

Цель изобретения - сокращение времени, требуемого для вычисления всей последовательности коэффициентов с пи (к =

04, 01 полинома Е „„1 =и (v +x,t), и увеличение производительности устройства.

Поставленная цель достигается тем, что устройство для вычисления коэффициентов полинома, содержащее генератор 15 импульсов, блок ввода, блок памяти переменных, блок умножения, сумматор, первый блок памяти результата, блок р»- гистрации, причем выход блока ввода подсоединен к первому входу блока памяти переменных, первый выход первого блока памяти результата подключен к первому входу блока умножения, второй выход первого блока памяти результ»та подключен ко входу блока регистрации, содержит узел формирования первого импульса пос-. ледовательности, семь элементов задержки, счетчик переменных, первый и второй счетчики, элемент НЕ, семь элементов И, три элемента ИЛИ, блок сравне30 ния, второй блок памяти результата, блок буферной памяти, причем выход геНератора импульсов подсоединен ко входу узла формирования первого импульса поI

35 следовательности, первому входу счетчика переменных и первому входу первого элемента И, выход узла формирования первого импульса последовательности подключен к первому входу первого эле»

40 мента ИЛИ, вторые входы счетчика переменных и первого элемента ИЛИ соединены с выходом первого элемента И, а третий вход счетчика переменных подключен к другому выходу блоке ввода, вы45 ход счетчика переменных подключен ко второму входу первого элемента И и второму входу блока памяти переменных, выход блока сравнения подключен ко входу элемента НЕ, третьему входу первого элемента И и первому входу второго эле50 мента И, выход первого элемента ИЛИ подсоединен ко входу первого элемента задержки, второго элементе задержки, . первому входу третьего элемента И и

55 первому входу второго элемента ИЛИ, группы выходов первого и второго счетчика подключены к соответствующим вхо дам блок» сравнения, нулевой вход первого счетчика подсоединен к первому выходу третьего элемента задержки, а единичный вход связан с выходом четвертого элемента задержки, выход первого счетчика подсоединен ко второму входу второго элемента И, выход второго элемента ИЛИ подсоединен ко входу четвертого и пятого элемента задержки, выход пятого элемента задержки подключен к первому входу четвертого элемента И, второй вход которого соединен с выходом элемента НЕ, а выход — с первым входом третьего элемента ИЛИ, выход блока памяти переменных подключен ко второму входу третьего элемента И, выход третьего элемента

ИЛИ соединен со входом блока умноже ния, выход которого подключен ко входу пятого элемента И, второй вход которого и шестого элемента задержки подсоединены к выходу первого элемента задержки, а выход шестого элемента задержки — к первому входу шестого элемента И, вто рой вход которого связан с выходом сумматора, а выход — со входом блока буфер ной памяти, с первым входом первого блока памяти результата и вторь.м входом второго элемента ИЛИ, выход третьего элемента задержки соединен с первым входом седьмого элемента И и вторым входом второго блока памяти результата, выход которого соединен с первйм" входом первого блока памяти результата, выход блока буферной памяти подключен ко второму входу седьмого элемента И, выход которого соединен со вторым входом первого блока памяти результата, выход пятого элемента И соединен со входом сумматора, выход второго элемента задержки подключен к третьему входу второго элемента И, выход которого подсоединен ко входам третьего и седьмого элементов задержки, а выход седьмого элемента задержки подключен ко входу второго счетчика.

Это позволяет вычислять значения коэффициентов на основе реккурентного соотношения: а.,„. = к;а,, „+ v.,à.,,.; -4 l ... rl 1=о l .. i а =a =а - - =а =o.

О-Л О(О2 00

I / а - о -О дю всех 2=-о ... и оо г-к 1

I а =о пси гс&.

3 в

734714

Так чри n = 3 будет иметь:

О =yà +ya =у a -xa ьа =х; л,о л о,-л л оо лю л,л л оаъ л ол л а х а +Ya =Чу го глл г ло л21 а =Ха уа =уХлХy2л г ло 2. лл л г л гF 5 с =ya +уа гг г лл г «г л 2>

- 4Э =Х а +ЬО =УУ У

Э,О Э г,-л 5 го л 2 3 > аЭ = Хэа Уза =Ь V-Х ++yX Ь.ХЬЬ

Э,л Ъ го Э гл л 2 э л 2Э лгэ 10 3 г "э гл з гг лх2Х + Л X эз X XË, 1 о =х а уа =хх х ъл- ъахх ъагъ- Лхз

Пов 1шение производительности устройства обеспечивается за счет принципиального сокращения числа операций умножения и сложения, необходимых для вычисления всей последовательности коэффициентов О1, (К 0 1у n )

На чертеже представлена функциональная схема одного из вариантов устройства о для вычисления коэффициентов полинома

% a„„h"= n (v, х.ц1

1=Л

Устройство имеет блок 1 ввода, предназначенный для параллельного приема переменных из аппаратуры АСУ и ввода переменнь х в блок 2 памяти переменных.

Для обеспечения возможности автоном. ной работы устройства в блок 1 ввода введено устройство перевода вводимых значений переменных из десятичной системы счисления в двоичную. Блок 1 ввода соединен со счетчиком 3 переменных, предназначенным дли подсчета введенных переменных. Этот счетчик является ревер- 5 сивным, т.е. считает от 0 до и и от до О. В предлагаемом варианте и < 100.

Сч тчик выполнен на интегральных схемах 133 серии.

Блок памяти 2 переменных предназна40 чен для хранения переменных Х и У и представляет собой две памяти: память

Х и память У с устройствами управления. Памяти выполнены на интегральных схемах 134 серии.

Блок 2 памяти переменных через элемент 4 И, элемент 5 ИЛИ соединен с блоком 6 умножения, который предназначен для умножения множимого на все разряды множителя, начиная со старшего.

56

В качестве множимого берутся переменные Х и У, а в качестве множителя — содержимое двух ячеек блока 7 памяти результата. Причем блок 6 пред$5 назначен для параллельного умножении

Х1а) л иь;С1, где Х1 и У! переменные из блока памяти переменных

2, а а„л и — значения соответствуюших ячеек блока 7 памяти результатов (сыч „и с1,, ). Блок 6 умножения выполнен на интегральных схемах 133 серии.

Блок умножения соединен через элемент 8 И с сумматором 9. Сумматор 9 параллельного действия выполнен на интегральных схемах 133 серии. Сумматор

9 соединен через .элемент 10 И с блоком 11 буферной памяти, Блок 11 буферной памяти выполнен аналогично блоку

7 памити результатов на регистрах и соединен с блоком 7 памяти результатов через элемент 12 И.

Выход генератора 13 импульсов соединен с узлом 14 формирования первого импульса. Этот узел представляет собой триггер, элемент И и элемент задержки.

Причем первый вход элемента И является входом узла 14 формирования первого импульса, второй вход элемента И соединен с единичным выходом триггера, а вход элемента И узла — с -единичным выходом триггера. Выход элемента И через элемент задержки соединен с нулевым входом триггера и является также выходом узла 14 формирования выдачи первого импульса. Он соединен через элемент 15 ИЛИ, через элемент 4 И с блоком 6 умножеиия; через элемент 16 задержки и элемент 8 И с сумматором

9; через элемент 17 задержки и элемент 10 И вЂ” с блоком 11 буферной памяти и единичным входами блока 18 счетчиков памяти результатов и первым входом элемента 19 ИЛИ.

Блок 18 счетчиков памяти результатов предназначен для управления выдачей результатов из двух соседних ичеек блока

7 памяти на блок 6 умножения и представляет собой два счетчика, один из которых предназначен для определения ячейки для умножения ее содержимого на X, a другой - для определения ячейки для умножения ее содержимого на У

Второй вход элемента 19 ИЛИ соединен с выходом элемента 15 ИЛИ и через элемент 20 задержки с первым входом элемента 21 И разрешения копирования, который представляет собой трехвходовой элемент И. Выход элемента 19 ИЛИ соединен через элемент 22 задержки, элемент 23 И, элемент 5 ИЛИ с блоком умножении 6 и, через элемент 24 задержки с единичным входом счетчика 25 циклов, представляющего собой счетчик, выходы которого . соединены с блоком

26 сравнения и через второй вход эле734714

7 мента 21 И разрешения копирования, элемент 27 задержки с регистром 28 счетчика.

Выход блока 26 сравнения соединен с третьим входом элемента 21 peapeure 5 ния копирования, а также через элемент

29 HE со вторым входом элемента 21 И.

Выход элемента 21 И разрешения копирования, кроме того, соединен через элемент 30 задержки с нулевыми входа10 ми счетчика 25 циклов блока 18 счетчиков памяти результатов и вторым входом элемента 12 И, Выход блока 7 памяти результатов соединен с блоком 31 регистрации.

Блок 31 регистрации служит для сопряжения с аппаратурой АСУ, если информация используется в следуюших устройствах или для отображения информации средствами индикации, выполненными на

20 элементах ИН-17.

Для обеспечения возможности автономной работы устройства в блоке регистрации 31 введено устройство перевода ре25 зультата из двоичной систем,r счисления в десятичную.

Выход генератора 13 соединен также с первым входом элемента 32 И разрешения прохождения импульсов, второй вход

30 которого соединен с блоком 26 сравнения, а третий вход с выходом счетчика 3 переменных. Выход элемента 32 И разрешения прохождения импульсов соединен С входом элемента 15 ИЛИ. Элемент 32

И разрешения прохождения импульсов

35 представляет собой трехвходовую схемуИ.

Конструктивно устройство вычисления коэффициентов полинома выполнено в виде элемента АСУ, я также как автономное

40 устройство, представляк атее собой спецвычисл итщ ь, В рамках предлагаемого изобретения возможны и другие технические решения предлагаемых блоков. Например, в блоках

45 памяти Mol+ быть исполb3oBGHbf магнитные пленки, блок регистрация может содержать элекгрофицированную пи-, шушую машинку (например, типа Консул" j, дисплей (например, CHfl-1000 или ЕС50

7О66) с блоками управления. В схемах

И, ИЛИ, счетчиках и других блоках могут бьггь использован интегральные элемент ы других серн и (например, 1 37, 1 87 серии).

Устройство работает следучошим образом.

Перед началом работ. сигналом с синхронизатора лСУ ус|ройство .rpwoдится в исходное состояние, а именно: в блоке 2 памяти переменных, в блоке

11 памяти (результатов 7) во все ячейки записываются нули, в блоке 7 памяти результатов во вторую ячейку записывается единица, а во все остальные ячейки —; счетчик 25 циклов и счетчик

3 переменных устанавливается в нуль; в блоке 18 счетчиков памяти результатов счетчик 7 управления блоком памяти результатов, предназначенный для реалисиции операции умножения с использованием переменной Х, устанавливается в нуль, я счетчик 7 управления блоком памяти результатов, предназначенный для реализации огерации умножения с использованием переменной у, устанавливается в единицу; в регистр 25 счетчикаа GH K JIG B записывается цифра "2 и триггер узла 14 формирования первого импульса последовательности устанавливается в 1 .

Через блок 1 ввода в блок 2 памяти переменных вводятся значения У. и У .

Одновременно на счетчике 3 переменных устанавливается их число.

По окончании ввода переменных включается генератор 13. Импульсы с генератора 13 поступают на узел 14 формирования первого импульса последовательности. Этот элемент пропускает только один первый импульс, который, проходя через элементы 15 ИЛИ, 4 И, 5 ИЛИ, копирует состояние перв 1х ячеек блока

2 памяти переменных в блоке 6 умножения. На блок 6 умножения поступает также информация из 1-оН и 2-ой ячеек блока 7 памяти результатов, после чего выполняются операции умножения Х О„и С1, где Cl,1 и Q - содержимое соответствуют их ячеек блока памяти результатов 7, а h и У, — содержание первь.х ячеек блока 2 памяти переменных.

Этот же импульс через элемент 16 задержки и элемент 8 И пересылает результат из блока 6 умножения на сумматор

9. В сумматоре 9 производится сложение результатов, полученных в блоке 6 умножения, и через элемент 17 задержки и элемент 10 И производится копирование результата суммирования на блок 11 буферной памяти. Этот же импульс поступает на блок 3 8 счетчиков памяти результатов и через элемент 19 ИЛИ, элемент

24 задержки — Hà c÷ñ.ò÷èê 25 циклов,а через элемент 32 зедержки, элемент 23

И и 5 ИЛИ вЂ” на копирование состояния

7347

° 9 ячеек на блок 6 умножения, причем с

1 блока 7 памяти результатов поступает информация 2-ой и 3-ей ячеек и выполняются операции Хлц и у а Затем з производится суммирование и запись результата суммирования в блок 11 буферной памяти. Импульс копирования результата суммирования на блок 11 буферной памяти добавляет единицу к счетчику 25 циклов. Блок 26 сравнения выдает сигнал <9 сравнения, который разрешает элементу

32 И разрешения прохождения импульсов пропустить импульс с генератора 13. Этот импульс вычитает из счетчика 3 переменн).х единицу и, проходя через элементы 15 и 19 ИЛИ, элемент 24 задержки, прибавляет единицу к счетчику 25 циклов, а также через элемент 21 И разрешения копирования, элемент 27 задержки, а также записывает новое состояние 20 счетчика 25 пиклов на регистр 28 счетчика. Этот же импульс через элемент 30 задержки устанавливает в нуль счетчик

25 циклов, счетчики 18 блоков счетчиков памяти результатов, и через элемент

12 И копирует информацию из блока 11 буферной памяти на блок 7 памяти результатов. Тот же импульс со схемы 32 разрешения прохождения импульсов через схему 15 ИЛИ копирует содержимое яче- З0 ек х и У из блока 2 буферной памяти через элемент ы 4 И и 5 ИЛИ на блок

6 умножения, где выполняются операпии умножения х C и У О . Результат умножения пересылается на сумматор 9 Ç5 и после суммирования в блок 11 буферной памяти. Работа устройства продолкается аналогично огисанному выше, но число циклов будет на единипу больше, то есть три. Затем происходит разреше- 4 ние прохождения следуюшего импульса с генератора 13 и работа устройства повторяется, причем при каждом следуюшем повторении число пиклов будет увеличи- . ваться на единицу до тех пор, пока счет4 чик 3 переменных не станет равным нулю.

После этого происходит запрещение прохождения импульсов с генератора 13 и вычислен ия заканчиваются.

Результат вычисления коэффипиентов

i* Л,2 ..., П j =0Л,..., i j а =а =а .=...=a =о, о-л Ол о) " ou

I о -л а =о для ьсех Р=ал ., v оо а л I !" У

1 а =О МИ )с&

Т Q передается в блок регистрапии 31.

14 10

Опенка технико-зкономического эффек- та от использования изобретения проводилась теоретически и методом матъ. матического моделирования.

Результаты теоретического расчета и математического моделирования показывают, что использование предлагаемого устройства позволяет вычислять коэффициенты сл, „полинома X o „ = и (у,+) Я реккурентно. При этом сокрашается число выполненных операций, что обеспечивает увеличение скорости вычисления коэффициентов полинома и повышение производительности специализированности АСУ. Так

Ф например, уже при и =5 число операпий, выполняемых в известном устройстве, составляет; умножения — 128, сложения—

26, а в предлагаемом устройстве - соответственно 12 и 6. При этом время вычисления сокрашается примерно в 10 раз.

При n = 100 получить результат с использованием исэвестного устройства практически невозможно, так как время решения будет составлять годы, а в предложенном устройстве время решения задачи занимает менее 1 мин. формула изобрет ен ия

Устройство для вычисления коэффициентов полино ма, содержаше е генератор импульсов, блок ввода, блок памяти переменных, блок умножения, сумматор, первый блок памяти результата, блок регистрации, причем выход блока ввода подсоединен к первому входу блока памяти переменнь)х, первый выход первого блока памяти результата подключен к первому блоку умножения, второй выход первого блока намяти результата подключен ко входу блока регистрации, отл ичаюш еес я тем, что, с целью увеличения производительности, оно содержит узел формирования первого импульса последовательности, семь элементов задержки, счетчик переменных, первый и второй счетчик, эле мент НЕ, семь элементов И, три элемента ИЛИ, блок сравнения, второй блок памяти результата, блок буферной памяти, причем выход генератора импульсов подсоединен ко входу узла формирования первого импульса последовательности, первому входу счетчика переменных и первому входу первого элемента И, выход узла формирования первого импульса последовательности подключен к первому входу первого элемента ИЛИ, вторые входы

11 .счетчика переменных и первого элемента

ИЛИ соединены с выходом первого элемента И, а третий вход счетчика переменных подключен к другому выходу блока ввода, выход счетчика переменных 5 подключен ко второму входу первого элемента И и второму входу блока памяти переменных, выход блока сравнения подключен ко входу элемента НЕ, третьему, входу первого элемента И и первому входу второго элемента И, выход первого элемента ИЛИ подсоединен ко входу первого элемента задержки, второго элемента задержки, первому входу третьего элемента И и первому входу второго элемента ИЛИ, группы выходов первого и второго счетчика подключены к соответствуюшим входам блока сравнения, нулевой вход первого счетчика подсоединен к первому выходу третьего элемента задержки, 20 а единичный вход связан с выходом чет« вертого элемента задержки, выход первого счетчика подсоединен ко второму входу второго элемента И, выход второго элемента ИЛИ подсоединен ко входу четвертого и пятого элемента задержки, выход пятого элемента задержки подключен к первому входу четвертого элемента И, второй вход которого соединен с выходом элемента НЕ, а выход — с первым входом Зо третьего элемента ИЛИ, выход блока памяти переменных подключен ко второму входу третьего элемента И, выход третьего элемента ИЛИ соединен со входом блока умножения, выход которого подклю- >

12 чен ко входу пятого элемента И, игорой вход которого и шестого элемента задержки подсоединены к выходу первого элемента задержки, а выход шестого элемента задержки - к первому входу шестого элемента И, второй вход которого связан с выходом сумматора, а выход - со входом блока буферной памяти, с первым входом первого блока памяти результата и вторым входом второго элемента

ИЛИ, выход третьего элемента задержки соединен с первым входом седьмого элемента И и вторым входом второго блока памяти результата, выход которого соединен с первым входом первого блока памяти результата, . выход блока буферной памяти подключен ко второму входу седьмого элемента И, выход которого соединен со вторым входом первого блока памяти результата, выход пятого элемента

И соединен со входом сумматора, выход второго элемента задержки подключен к третьему входу второго элемента И, выход которого подсоединен ко входам третьего и седьмого элементов задержки, а выход седьмого элемента задержки подключен ко входу второго счетчика.

Источники информации, принятые во, внимание при экспертизе

1. Авторское свидетельство СССР

¹ 378840, кл. б 06 F 77//0000, 1973.

2. Авторское свидетельство СССР

N 374606, кл. Cj 06 I- 7/00, 1973 (прототип) .

ЦНИИПИ Заказ 2226/13

Тираж 751 Подписное

Филиал ППП Патент, г.ужгород, ул, Проектная,4