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

О

о -xj

о

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

Цель изобретения - расширение функциональных возможностей устройства путем вычисления коэффициентов интерполирующего полинома от п-переменных.

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

S1I S2I Snl

Р ( АхХ1 хХ2хХп), (1)

где S1I, S2I, Snl - показатели степени при коэффициенте А.

В устройстве применяется следующая стандартная форма обобщенного полинома. Предполагается, что, если 51макс, 32Макс, .... Зпмакс максимальные показатели степени в полиноме (1) при аргументах Х1, Х2, ..., Хп, то для любых S1, S2, ..., Sn таких

ЧТО 0 S1 51макс, 0 S2 52макс

0 Sn Зпмакс всегда найдется только один коэффициент AI (быть может равный нулю),

S1I S2i Snl

такой, что А х Х1 х Х2, ..., х Хп является слагаемым в выражении (1). Отсюда следует, что в полиноме (1) имеется N (51Макс + +1) х (32макс + 1) х ... х (Зпмакс + 1) слагаемых.

Исходными данными для определения значений коэффициентов А является последовательность значений аргументов Х1, Х2,

.... Хп и функции F(X1, X2Хп), значения

которой упорядочены в лексикографическом порядке, т.е., если аргумент Х1 принимает значения из множества X11, Х12, ...,

ХШ, Х2 - Х21, Х22X2k2 Хп - Хп1,

Хп2, ..., Xnkn, то каждому значению функции F(X111, X212,..., Xn1n) однозначно соответствует число 1п ... 1211, составленное из индексов значений аргументов, причем

1 11 ki, 1 I п. Лексикографический порядок означает, что если значению функции F1 соответствует число 1п ... 1211, а значению функции F2 соответствует число bn ... Ь2Ы. то f К f2 тогда и только тогда, когда 1п ... 1211 bn ... Ь2Ы. Например, значения функции f (Х1, Х2, ХЗ, Х4), причем Х1 принимает значения из множества Х11, Х12, Х13, Х14, Х2 - Х21, Х22, ХЗ - Х31, Х32, ,Х42,Х43 лексикографически упорядочены следующим образом: f(X11, Х21, Х31, Х41), f(X12, X21, Х31, Х41), f(X13, Х21, Х31. Х41), f(X14, X21, X31. X41), f(X11, X22, X31, X41), f(X12. X22, X31, X41), f(X13. X22, X31, X41), f(X14, X22, X31, X41). f(X11,

X21.X32.X41), f(X12.X21.X32.X41)f(X11,

X22, X32, X43), f(X12, X22, X32. X43), f(X13, X22, X32, X43), f(X14, X22, X32, X43). Общее число значений функции f равно 4x2x2x3

48. Вычисление коэффициентов интерполирующего полинома такой функции выполняется в четыре этапа.

На первом этапе значения функции f разбиваются на 12 областей, по каждой из

которых производится одна выборка с шагом, равным 1, состоящей из четырех значений функции f и соответствующих им значений аргумента Х1, По значениям функции и аргумента вычисляются коэффициенты интерполирующего полинома, которые записываются вместо значений функций f и являются исходными данными для следующего этапа вычислений. Аналогично, на втором этапе множество значений полученных

коэффициентов разбивается на 8 областей, по каждой из которых производятся 4 выборки с шагом, равным 4, состоящие из двух значений коэффициентов и соответстующих им значений аргумента Х2 и т.д.

Устройство (фиг.1) содержит четыре

счетных узла 1-4, элемент И 5, пять блоков 6-10 памяти, блок 11 формирования адресов, ключ 12, триггеры 13 и 14, операционный блок 15, вход 16 запуска устройства,

вход 17 количества аргументов устройства, синхровход 18устройства, выход 19 окончания работы устройства.

Счетный узел 1 (фиг.2) содержит счетчик 20 и элемент И 21. Счетные узлы 2-4 (фиг.З)

содержат счетчик 22, элемент И 23 и элемент ИЛИ 24.

Блок 11 формирования адресов (фиг.4) содержит сумматоры 25-30. умножители 31 и 32, регистр 33.

Операционный блок 15 (фиг.5)содержит вычислитель 34, блоки 35-37 памяти, регистр 38, элемент И 39, дешифраторы 40-44, коммутаторы 45 и 46.

Работу устройства рассмотрим на примере вычисления коэффициентов интерполирующего полинома функции f(X1, X2, ХЗ, Х4), причем Х1 Х11, Х12, Х13. Х14, Х2 Х21, Х22, ХЗ Х31, Х32, Х4 Х41. Х42,

Х43. Значения функции f упорядочены в лексикографическом порядке в блоке 10 памяти.

Перед началом работы в блоке 8 хранятся числа К, где Kj (J 1, 4) - уменьшенное на

1 количество значений j аргумента функции f К1 3, К2 1, КЗ 1, К4 - 2. В блоке 7 хранятся числа Bj, равные 0, 3, 7, 15 где Bj (j 1,4)- уменьшенное на 1 количество выборок на J этапе вычисления коэффициентов интерполирующего полинома. В общем случае, когда функция F зависит от п аргументов, используется выражение:

О

1-1

, при j 1

в |-1 +П(К1 +1), при ,n

В блоке 8 хранятся значения QJ, равные 11,5, 1,0, где QJ 0 1. 4)- уменьшенное на 1 число областей на j-м этапе вычислений. В общем случае используется выражение

Q|

-1 +П(К1 + 1), при j 1,п-1

+ 1 О, при j п

Каждое из чисел KJ, Bj, Oj хранится по адресу n -J + 1. В блоке 9, начиная с адреса 0. хранится массив значений аргументов, упорядоченный в виде Х11, Х12, Х13, Х14, Х21, Х22, Х31, Х32, Х41, Х42, Х43,

По сигналу запуска 18 в узел 1 с входа 17 количества аргументов устройства записывается число этапов вычислений, равное 4, в узлы 2-4 с выхода блоков 6-8 записываются значения 01, В1, К1, равные 11, О, 3 соответственно, триггеры 13 и 14устанавли- ваются в лог. 1, блок 11 формирования адресов устанавливается в исходное состояние. За счет подачи на второй вход блока 15 сигнала лог.Г с выхода триггера 14 блок 15 настраивается на прием значений функции и аргументов.

С синхровхода 18 устройства через элемент И 5 на блоки устройства поступают синхроимпульсы. Блок 11 формирования адресов вычисляет функции адреса Ау и Ах значений функции и аргумента в блоках 10, 9 в зависимости от состояния выходов узлов 2-4 и блоков 7; 8 памяти.

Функции адреса Ау и Ах имеют вид:

Ay qi x (Bj + 1) (Kj + 1) + Ы + ki (В + 1) (BJ + 1)x(qlx(KJ+1) + kl) + bl

j - 1 Ax Ј (K1 + 1) + kl.

I - 1 где j - номер этапа j 1, 4;

qi - текущая область интерполяции (выход узла 2)qi О, QJ;

BJ - уменьшенное на 1 число выборок в области на j этапе вычислений (выход блока 7 памяти);

Kj - уменьшенное на 1 число значений аргумента на этапе вычислений (выход блока 8 памяти); К(-1) -1 ;

ki - номер элемента в выборке (выход узла 4) kl 0, kj;

Ы - текущая выборка (выход узла 3) Ы 0, Bj.

На тактах 1-4 блок 11 формирует адреса 47, 78, 45, 44 для блока 10 и адреса 3,2,1,0

для блока 9. По этим адресам на тактах 1-4 в блок 15 записываются пары значений функции и аргумента: f(X14, Х22, Х32, Х43), Х14; f(X13, Х22, Х32, Х43). Х13; f(X12, X22. Х32. Х43), Х12; f(X11, Х22, Х32. Х43). Х11. Ключ 12

0 в зависимости от состояния триггера 13 пропускает синхроимпульсы на один из двух разрядов выхода. На тактах 1-4 синхроимпульсы поступают на первый разряд выхода ключа 12 и разрешают чтение значений из

5 блока 10 и запись в блок 15.

На 2-4 тактах по переднему фронту синхроимпульса из узла 4 вычитается 1. По достижении узлом 4 на четвертом такте нулевого значения при низком уровне синх0 роимпульса происходит сброс триггера 13 в состояние , а также запись состояния триггера 13 в триггер 14.

Триггер 14 сбрасывается в состояние лог.О, блокируя прохождение синхроим5 пульсов через элемент И 5 и запуская вычислитель 34 блока 15.

Операционный блок 15 выполняет вычисление коэффициентов А47.1, А46.1. А45.1. А44.1 интерполирующего полинома

032

А47.1хХ1 + А46.1хХ1 +А 45,UX1 + A44.1

После окончания вычислений блок 15 вырабатывает синхронизированный сигнал окончания работы, который устанавливает

5 триггер 14. В результате этого через элемент И 5 вновь поступают синхроимпульсы. На пятом такте по переднему фронту синхроимпульса в узел 4 из блока 8 памяти вновь записывается значение 3.

0 Ключ 12 пропускает синхроимпульсы на второй разряд своего выхода и разрешает на тактах 5-8 запись значений А47.1, А46.1, А45.1, А44.1 в блок 10 памяти и чтение их из блока 15.

5 На тактах 9-12 в блоке 11 формируются адреса 43, 42. 41, 40 (на диаграмме показан только адрес 43). В блок 15 записываются пары значений функции и аргумента: f(X14, Х21, Х32, Х43), Х14; f(X13. X21, Х32. Х43).

0 Х13; f(X12, Х21, Х32. Х43), Х12; f(X11. X21, X32, X43), X11. После вычислений блоком 15 коэффициентов А43.1, А42.1, А41.1, А40.1 интерполирующего полинома 32

5 A43.lxX1+A42.1xX + A41.1xX1 + А40.1, они записываются на тактах 13-16 на места переданных значений функции.

После ряда аналогичных циклов на тактах 89, 90, 91. 92 в блок 15 записываются пары значений: f(X14. Х21, Х31, Х41), Х14;

f(X13. X21, X31, X41), X13; f(X12, X21, X31, X41), X12; f(X12, X21, X31, X41), X11..no которым вычисляются коэффициенты А3.1, A2.1, A1.1, A0.1 интерполирующего полинома, Так как на такте 96 и узлах 2-4 находятся О, то передний фронт с выхода триггера 13 транслируется счетчиками узлов 2-4, и вычитание единицы происходит из счетчика узла 1. Содержимое его становится равным 3 и начинается второй этап интерполяции.

В начале второго этапа в счетчики узлов 2-4 с выходов блоков 6-8 записываются числа Q2, В2, К2 равные 5, 3,1 соответственно. На тактах 97, 98 блок 11 формирует адреса 47, 43 для блока 10 и 5, 4 для блока 9. В блок 15 записываются пары значений коэффициентов, полученных на предыдущем этапе, и аргумента Х2:А47.1, Х22: А43.1, Х21. После вычисления блоком 15 коэффициентов интерполирующего полинома: А47.2 х Х2 + А43.2 на тактах 99, 100 производится их запись в блок 10.

Аналогично выполняются другие циклы второго этапа, пока не будут обработаны выборки из всех областей, а затем циклы третьего и четвертого этапов. Обрабатывая последнюю выборку четвертого этапа, на тактах 379, 380, 381 блок 11 формирует адреса 32, 16.0. В блок 15 записываются пары значений коэффициентов, полученных на третьем этапе, и аргумента Х4; А32.3, Х43; А16.3.Х42; АО.З.Х41. На тактах 382, 383, 384 вычисленные коэффициенты А32.4, А16.4, АО.4 записываются в блок 10. На такте 384 в счетчиках узлов 2-4 находятся 0, передний фронт с выхода триггера 13 транслируется счетчиками узлов 2-4 и вычитание единицы происходит из счетчика узла 1. Содержимое счетчика узла 1 становится равным 0. Второй выход 19 окончания работы устройства становится равным лог.О. Пои этом через элемент И 5 блокируется прохождение синхроимпульсов, устройство переходит в состояние останова и возможно считывание коэффициентов полинома из блока 10 памяти.

Формула изобретения

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

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

n-переменных, в него введены второй, третий, четвертый и пятый блоки памяти, ключ, первый и второй триггеры и элемент И, причем первый выход первого счетного узла соединен с адресными входами второго,

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

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

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

5 триггера и с первым входом сброса первого триггера, вход данных которого соединен с вторым выходом четвертого счетного узла и с входом строба второго триггера, выход которого соединен с вторым входом сброса первого триггера, с четвертым входом

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

Изобретение относится к автоматике, вычислительной технике и средствам обработки экспериментальной информации. Целью изобретения является расширение области применения устройства за счет вычисления коэффициентов интерполирующего полинома от N - переменных. Устройство содержит четыре счетных узла 1 - 4, элемент И 5, пять блоков 6 - 10 памяти, блок 11 формирования адреса, ключ 12, триггеры 13, 14, операционный блок 15, вход 16 запуска, вход 17 количества аргументов, синхровход 18, выход 19 окончания работы. Значения интерполируемой функции, промежуточные и окончательные результаты хранятся в блоке 10 памяти, в блоке 9 памяти хранятся значения аргументов. Арифметические операции вычисления коэффициентов интерполирующего полинома по значениям выборки функции и аргумента выполняются в операционном блоке 15. Формирование выборки осуществляется блоками 7, 8 памяти, содержащими численные значения констант вычислительного процесса, узлами 2 - 4 и блоком 11 формирования адресов. Управление ходом вычислений производится с помощью узла 1, элемента И 5, блока 6 памяти, триггеров 14, 15, ключа 12. Указанные элементы позволяют проводить полиномиальную интерполяцию функции N - переменных. 5 ил.

О

23

t

Фиг.З

Фиг. 2.

П

ik

гг

.JLlФиг. Ц

фиг 5