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

 

Изобретение относится к автоматике, вычислительной технике и средствам обработки экспериментальной информации. Целью изобретения является расширение области применения устройства за счет вычисления коэффициентов интерполирующего полинома от 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 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) (51)5 G 06 F 15/353

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4685462/24 (22) 03.05.89 (46) 30,07.91. Бюл. (Ф 28 (71) Одесский политехнический институт (72) B.À.Ïàðàcî÷êèí, Ю,.И.Костелов и

В.Г.Ткаченко (53) 681.32 (088.8) (56) Авторское свидетельство СССР йг 1317452; кл. G 06 F 15/353, 1985.

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

N 1290354, кл. G 06 F 15/353, 1985. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ ИНТЕРПОЛИРУЮЩЕГО

ПОЛИНОМА (57) Изобретение относится к автоматике, вычислительной технике и средствам обработки экспериментальной информации.

Целью изобретения является расширение области применения устройства за счет вычисления коэффициентов интерполирующего полинома от и-переменных. Устройство содержит четыре счетных узла 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. Указанные элементы позволяют проводить полиномиальную интерполяцию функции и-переменных. 5 ил.

1667104

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

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

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

S1 i S2i S ni

Р = (< А х Х1 х Х2, ..., хХп), (1) где Sii, 521, Sni — показатели степени при коэффициенте А.

B устройстве применяется следующая стандартная форма обобщенного полинома. Предполагается, что,.если 51макс, З2макс, ..., SnMavc — МаКСИМаЛЬНЫЕ ПОКааатЕЛИ СтЕпени в полиноме (1) при аргументах Х1, Х2, ..., Xn, то для любых S1, S2, ..., Sn таких что 0 <= S1<= Я1макс, 0 <== S2 <= 52макс, ..., 0 <= Sn <= SnMaKc всегда найдется только один коэффициент Al (быть может равный нулю), S1I S2l Sni такой, что Ai х Х1 х Х2, „x Хп является слагаемым в выражении (1). Отсюда следует, что в полиноме (1) имеетсЯ N == (S1Mavc+

+1) х (S2MaKc+ 1) x ... x (SnMGKC+ 1) слагаемых.

Исходными данными для определения значений коэффициентов А является последовательность значений аргументов Х1, Х2,,.„Хп и функции F(X1, Х2, ..., Xn), значения которой упорядочены в лексикографическом порядке, т.е., если аргумент Х1 принимает значения из множества (Х11, Х12, ..., Х1Щ Х2 — (Х21, Х22, ..., X2k2), ..., Xn — (Xn1, Хп2, ..., Xnkn), то каждому значению функции F(X111, X212, ..., Xn1n) однозначно соответствует число 1п ... 12 11, составленное из индексов значений аргументов, причем

1 <= 1! <= ki, 1 <=! <= n. Лексикографический порядок означает, что если значению функции F1 соответствует число in „, 1211, а значению функции F2 соответствует число

Ьп ... Ь2Ь1, то f 1< f2 тогда и только тогда, когда 1n ... 1211 < bn ... Ь2Ь1. Например, значения функции (X1, Х2, XÇ, Х4), причем

Х1 принимает значения из множества (Х11, Х12, Х13, Х14), Х2 — (Х21, Х22), XÇ вЂ” (X31, Х32), Х4 -(X41, Х42, Х43)лексикографически упорядочены следующим образом. f(X11„

Х21, Х31, Х41), f(X12, Х21, Х31, Y41), f(X13, Х21, Х31, Х41), f(X14, Х21, Х31, X41), f(X11, Х22, Х31, Х41), f(X12, Х22, Х31, X41), f(X13, Х22, Х31, Х41), f(X14, Х22, Х31, X41). f(X11, Х21, ХЗ2, Х41), f(X12, Х21, Х32, X41), „., f(X11, Х22, Х32, X43), 1(Х.12, Х22, Х32, X43), 1(Х13, Х22, Х32, X43), 1(Х14, Х22, Х32, X43), Общее число значений функции f равно 4x2x2x3 =

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

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

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

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

25 Устройство (фиг.1) содержит четыре счетных узла 1-4, элемент И 5, пять блоков

6 — 10 памяти, блок 11 формирования адресов, ключ 12, триггеры 13 и 14, операционный блок 15, вход 16 запуска устройства, 30 вход 17 количества аргументов устройства, синхровход 18 устройства, выход 19 окончания работы устройства.

Счетный узел 1 (фиг.2) содержит счетчик

20 и элемент И 21. Счетные узлы 2 — 4 (фиг.3)

35 содержат счетчик 22, элемент И 23 и элемент ИЛИ 24, Блок 11 формирования адресов (фиг.4) содержит. сумматоры 25 — 30, умножители 31 и 32, регистр ЗЗ.

40 Операционный блок 15 (фиг,5) содержит вычислитель 34, блоки 35 — 37 памяти, регистр 38, элемент И 39, дешифраторы 40-44, коммутаторы 45 и 46, 45 Работу устройства рассмотрим на примере вычисления коэффициентов интерполирующего полинома функции f(X1, Х2, XÇ, Х4), причем Xi. = (Xi i, Х12, Х13, Х14), Х2 = (Х21, Х22), XÇ = (Х31, X32),.Х4 = (Х41, Х42, 50 Х43). Значения функции f упорядочены в лексикографическом порядке в блоке 10 памяти.

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

55 1 количество значений j аргумента функции

f К1=3, К2=1, К3=1, К4=2. В блоке7 хранятся числа В, равные О, 3, 7, 15 где В((j

-1, 4) — уменьшенное на 1 количество выборок íà j этапе вычисления коэффициентов интерполирующего полинома. В общем слу1667104. чае, когда функция F зависит от и аргументов, используется выражение:, при j = 1

j — 1 — 1+П(K1+1), при j =2 и

i-=1

Bl=

В блоке 8 хранятся значения Qi, равные

11, 5, 1, О, где С!1(j = 1, 4) — уменьшенное на

1 число областей на j-м этапе вычислений. 8 общем случае используется выражение — 1 + П (Ki + 1), при j = 1, и — 1 ! =)+1 15

О, приj=n

Qi=

Каждое из чисел Kj, BJ, Oj хранится по адресу и -j+ 1. В блоке 9, начиная с адреса

О, хранится массив значений аргументов, упорядоченный в виде Х11, Х12, Х13, Х14, Х21, Х22, Х31, Х32, Х41, Х42, Х43.

llo сигналу запуска 18 в узел 1 с входа

17 количества аргументов устройства записывается число этапов вычислений, равное

4, в узлы 2 — 4 с выхода блоков 6-8 записываются значения 01, 81, К1, равные 11, О, 3 соответственно, триггеры 13 и 14 устанавли-. ваются в лог. "1", блок 11 формирования адресов устанавливается в исходное состо- 30 яние, За счет подачи на второй вход блока

15 сигнала лог."1" с выхода триггера 14 блок

15 настраивается на прием значений функции и аргументов.

С синхровхода 18 устройства через эле- 35 мент И 5 на блоки устройства поступают синхроимпульсы. Блок 11 формирования адресов вычисляет функции адреса Ау и Ах значений функции и аргумента в блоках 10, 9 В заВисимости От состОЯниЯ ВыхОДОВ узлов 40

2-4 и блоков 7, 8 памяти.

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

Ay= q1x(Bj+ 1)(KJ+ 1)+Ы+kl(8+ 1)=

=(Bj + 1) x (qi х (К) +1) + ki) + Ы

45. l— - 1

Ax = X (K1+ 1)+ ki, ! =-1 где j — номер этапа j = 1, 4; с!! — текущая область интерполяции (вы- 50 ход узла 2) q! = О, Qi, Bl — уменьшенное на 1 число выборок в области на ) этапе вычислений (выход блока

7 памяти);

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

ki — номер элемента в выборке (выход узла 4) ki = О, ki;

Ы вЂ” текущая выборка (выход узла 3) bl =

=0, В!.

На тактах 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, Х22, Х32, Х43), Х12; f(X11, Х22, Х32, Х43), Х11. Ключ 12 в зависимости от состояния триггера 13 пропускает синхроимпульсы на один из двух разрядов выхода. На.тактах 1-4 синхроимпульсы поступают на первый разряд выхода ключа 12 и разрешают чтение значений из блока 10 и запись в блок 15.

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

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

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

3 2

А47,1хХ1 + А46.1хХ1 +А 45.1 Х1 + А44.1

После окончания вычислений блок 15

Вырабатывает синхронизированный Сигнал окончания работы, который устанавливает триггер 14. В результате этого через элемент И 5 вновь поступают синхроимпульсы.

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

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

На тактах 9-12 в блоке 11 формируются адреса 43, 42. 41, 40(на диаграмме показан только адрес 43). 8 блок 15 записываются пары значений функции и аргумента: f(X14„ . Х21, Х32, Х43), Х14; f(X13, Х21, Х32, Х43), Х13; f(X12, Х21, Х32, Х43), Х12; f(X11, Х21, Х32, Х43), Х11. После вычислений блоком 15 коэффициентов А43.1, А42,1, А41.1, А40.1 интерполирующего полинома

3 2

А43;1хХ1+ А42.1х Х+ А41.1х Х1+ А40,1, они записываются на тактах 13 — 16 на места переданных значений функции, После ряда аналогичных циклов на тактах 89, 90, 91, 92 в блок 15 записываются пары значений: f(X14, Х21, X31, X41), Х14;

1667104

f(X13, Х21, Х31, Х41), Х13; f(X12, Х21, Х31, Х41), Х12; f(X12, Х21, Х31, X41), Х11„по которым вычисляются коэффициенты А3,1, А2.1, А1.1, А0.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.

Аналогично выполняются другие циклы второго этапа, пока не будут обработаны выборки из всех областей, а затем циклы ! третьего и четвертого этапов, Обрабатывая

1 последнюю выборку четвертого этапа, на тактах 379, 380, 381 блок 11 формирует адреса 32, 16.0. B блок 15 записываются пары значений . коэффициентов, полученных на третьем этапе, и аргумента Х4; А32.3, Х43;

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

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

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

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

15 окончания работы устройства и соединен с первым входом элемента И, выход которого соединен с третьими входами второго, третьего и четвертого счетных узлов и первым входом ключа, выход которого соеди20 нен с входом задания режима первого блока памяти и с первым входом операционного блока, первый выход которого соединен со стробирующим входом первого триггера, инверсный выход которого соединен с вто25 рым входом элемента И, а прямой и инверсный выходы — с вторым входом операционного блока, второй выход которого соединен с информационным входом первого блока памяти, выход которого сое30 динен с третьим входом операционного блока, четвертый вход которого соединен с выходом пятого блока памяти, адресный вход которого соединен с вторым выходом блока формирования адресов, первый и вто35 рой входы которого соединены соответственно с входом запуска устройства и первым выходом второго счетного узла, второй выход которого соединен с вторым входом первого счетного узла и третьим входом

40 блока формирования адресов, четвертый, пятый, шестой и седьмой входы которого соединены соответственно с первыми выходами третьего и четвертого счетных узлов и выходами третьего и четвертого блоков па45 мяти, первый выход четвертого счетного узла соединен с пятым входом операционного блока, шестой вход которого соединен с третьим входом элемента И и с синхровходом устройства, седьмой вход операционно50 го блока соединен с выходом четвертого блока памяти, второй выход третьего счетного узла соединен с четвертым входом ВТорого счетного узла, вход запуска устройства соединен с установочным входом второго

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

1667104

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

1667104

Составитель Л,Логачева

Техред М, Моргентал Корректор Л.Бескид

Редактор С.Лисина

Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101

Заказ 2526 Тираж 412 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Мо<-.ква, Ж-35, Раушская наб., 4/5