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

фиг i

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

Известно устройство, содержащее блок управления, блок памяти, первый, второй, третий и четвертый счетчики, регистры с первого по двенадцатый, первый и второй операционные блоки.

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

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

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

Недостатком известного устройства яв0 ляется невысокая скорость вычислений.

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

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

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

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

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

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

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

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

Xi:

11 X .

х

Snl

ЬО)

где 5л S2i....,Sni - показатели степени при коэффициенте AI.

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

Х2Хп и функции F (Xi, X2Xn). значения

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

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

5 выходом элемента И 5, первый, второй и третий входы которого соединены соответственно с первым выходом блока 12 управления, синхровходом 17 устройства и первым выходом первого 1 счетного узла,

0 второй вход которого соединен с входом 16 количества аргументов устройства, а третий вход - с вторым входом блока 11 формирования адреса и с первым выходом второго 2 счетного узла, второй выход которогосоеди5 нен с третьим входом блока 11 формирования адреса, четвертый и пятый, шестой и седьмой входы которого соединены соответственно с первыми выходами третьего 3 и четвертого 4 счетных узлов и выходами

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

5 окончания работы устройства, вторые входы второго 2, третьего 3 и четвертого 4 счетных узлов соединены соответственно с выходами третьего б, первого 7 и второго 8 блоков памяти, третий вход второго 2 счетного узла

0 соединен с вторым выходом третьего счетного узла 3, первый и второй выходы блока 11 формирования адреса подключены соответственно к адресным входам блоков памяти аргументов 9 и функций 10, выходы

5 которых подключены соответственно к первому и второму входам первого операционного блока 13, третий и четвертый входы и первый выход которого подключены соответственно к выходу второго блока 8 памя0 ти, к первому выходу четвертого счетного узла 4 и к третьему входу блока 12 управления, четвертый вход, второй и третий выходы которого соединены соответственно с вторым выходом четвертого счетного узла 4

5 и с пятым, шестым входами первого опера- цгонного блока 13. седьмой вход которого соединен с синхровходом 18 устройства, третий и четвертый входы третьего 3 и четвертого 4 счетных узлов и четвертый, пятый входы второго счетного узла 2 соединены

соответственно с четвертым и пятым выходами блока 12 управления, пятый и шестой входы и пятый и шестой выходы которого подключены соответственно к третьему выходу второго счетного узла 2, к первому выходу второго операционного блока 14, к входу задания режима блока 10 памяти функций и первому входу второго операционного блока 14, второй, третий, четвертый, пятый, шестой и седьмой входы второго операционного блока 14 соединены соответственно с синхровходом 18 устройства, входами блоков памяти функций 10 и аргументов 9, выходом второго блока 8 памяти, выходом четвертого счетного узла 4 и третьим выходом блока 12 управления, вторые выходы первого 13 и второго 14 операционных блоков объединены и подключены к информационному входу блока 10 памяти функций, третий выход четвертого счетного узла 4 подключен к пятому входу третьего счетного узла 3.

Счетный узел 1 (фиг, 3) содержит последовательно включенные счетчик 19 и элемент ИЛИ 20, причем выход счетчика 19 является первым выходом узла 1, а выход элемента ИЛИ 20 - вторым выходом узла 1,

Счетные узлы 2-4 (фиг 4) содержат элементы ИЛИ 21-24, триггеры 25 и 26, счетчики 27 и 28 и коммутатор 29, причем выходы элементов ИЛИ 21 и 22 соединены соответственно с инверсными асинхронными S- входами триггеров 25 и 26, выходы которых соединены соответственно с первыми входами элементов ИЛИ 23 и 24, выходы которых соединены соответственно с первыми входами элементов ИЛИ 21 и 22 и входами разрешения записи счетчиков 27 и 28, информационные выходы которых соединены соответственно с первым и вторым входом коммутатора 29, третий и четвертый входы которого соединены соответственно с выходами заема счетчиков 27 и 28 и инверсными К-входами триггеров 25 и 26, инверсные асинхронные R-входы которых являются первыми входами 35 узлов 2-4, вторые входы 32 которых являются информационными входами счетчиков 27 и 28, первыми выходами узлов 2-4 являются соответственно выход 38 счетчика 28 и выходы 39 коммутаторов 29, вторыми выходами узлов 2-4 являются соответственно выход 39, выходы 37, 38 и выход 40 коммутатора 29, третьими выходами узлов 2 и 4 являются соответственно выход 40 и выходы 37 и 38; третьими входами узлов 2-4 являются соответственно входы 30 и 31 вычитания единицы счетчиков 27 и 28 и входы 36, которые соединены с вторыми инверсными входами элементов ИЛИ 23, вторыми входами элементов ИЛИ

24 и управляющими входами коммутаторов 29,четвертыми входами узлов 2-4 являются входы 33 и 34, которые соединены с вторыми входами элементов ИЛИ 21 и 22 и входами строба триггеров 25 и 26, входы 33 и 34 узла 4 соединены и объединены соответственно с входами 30 и 31, пятыми входами узлов 2 и 3 являются соответствен но вход 36 и входы 30 и 31.

0 Коммутатор 29 подключает к первому и второму выходу первый и третий входы при уровне лог, 1 на входе 36, и второй и четвертый - при уровне лог. 0.

Блок 11 формирования адреса (фиг. 5)

5 состоит из сумматоров 41-46, умножителей 47 и 48, регистра 49, причем выход сумматора 42 соединен с информационным входом регистра 49, выход которого соединен с первыми входами сумматоров 42 и 45, вход

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

5 входом сумматора 42 и первым входом умножителя 48, выход которого соединен с первым входом сумматора 44, выход которого соединен с первыми входами сумматора 43 и умножителя 47, выход которого соеди0 нен с вторым входом сумматора 43, выход которого соединен с первым входом сумматора 46, выход которого является вторым выходом блока 11, третий вход которого является вторым входом умножителя 48, шес5 той вход блока 11 является вторым входов умножителя 47, пятый вход блока 11 соединен с Вторыми входами сумматоров 44 и 45, четвертый вход блока 11 является входом сумматора 46, выход сумматора 45 является

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

Блок 12 управления (фиг, 6) состоит из логического преобразователя 50, триггеров

5 51-54 и логических ключей 55 и 56, причем первый вход бпрка 12 соединен с первыми инверсными асинхронными S-входами триггеров 51-54, выходы которых соединены с одноименными входами логического преоб0 разователя 50, пятый и шестой входы которого являются соответственно четвертым и пятым входами блока 12. третий и шестой входы которого являются соответственно вторыми инверсными асинхронными 5-вхо5 дами триггеров 53 и 54, К-входы которых соединены соответственно с первым и вторым выходами преобразователя 50, третий и четвертый выходы которого соединены с J- и К-входами триггера 52, односменные входы триггера 51 соединены с пятым и шестым выходами преобразователя 50, седьмой выход которого является первым выхолом блока 12, второй вход которого является входом строба триггеров 51-54 и соединен с первым входом логического ключа 56, вы- ход которого является пятым выходом блока 12 и соединен с первым входом логического ключа 55, выход которого является третьим выходом блока 12, четвертым выходом которого является выход триггера 52, который соединен с вторым входом ключа 56, выход триггера 51 соединен с вторым входом ключа 55, выходы триггеров 53 и 54 являются соответственно вторым и шестым выходами блока 12.

Логический преобразователь 50 вырабатывает по каждому из своих выходов следующие логические функции:

KBtL52 I5lL

КВ К Т52 Т51+КВ Т51 Т52;

К|3 КЭ Т515Г52+К В Т52 Т51 ;

(Т53+Т52+Т51 )(Т54+Т51+Т52),

где Т51, Т52, Т53, Т54 - состояние прямых выходов триггеров 51-54 соответственно;

KB (конец выборки) - состояние четвертого входа блока 12;

КЭ (конец этапа) - состояние пятого вхо- да блока 12.

Работу устройства рассмотрим на примере вычисления коэффициентов интерполирующего полинома функции f(X1, X2. ХЗ, Х4), причем Х1 Х11, Х12. Х13, Х21, ХЗ Х31. Х4 {Х41. Х42, Х43 Значения функции f упорядочены в лексикографическом порядке в блоке 10 памяти. Схема выполнения этапов вычисления коэффициентов интерполирующего полино- мз приведена на фиг. 7.

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

О

J-1

-1 + П (Кн-0 1-1

при 1; npnje2,n - 55

В блоке 6 хранятся значения QJ, равные 11, 5, 1, 0, где Qj(j 1,4)- уменьшенное на 1

число областей на j-м этапе вычислений В общем случае используется выражение

при J 1, п-1; при J п.

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

Счетный узел 1 обнулен. При этом его первый выход принимает значение лог. О и блокирует прохождение синхроимпульсов через элемент И 5, в результате этого устройство находится в состоянии останова и возможна предварительная запись значений в блоки 6-10 памяти.

По сигналу пуска 15, который совпадает с низким уровнем синхроимпульса на синх ровходе 17, в счетный узел 1 с входа количества аргументоЁ устройства 16 записывается число этапов вычислений,рав- ное 4, триггеры 25 и 26 (фиг. 4) счетных узлов 2-4 сбрасываются, блок 11 формирования адреса и блок 12 управления устанавливаются в, исходное состояние. При этом триггеры 51-54 блока 12 устанавливаются в состояние лог.1. Первый выход блока 12 также устанавливается в состояние лог. 1. разрешая прохождение синхроимпульсов через элемент И 5.

Уровень лог. 1. на четвертом выходе блока 12 подключает к выходам 39 и 40 узлов 2-4 счетчики 27 и разрешает для них запись данных. Поэтому по сигналу пуска устройства 15 в счетчики 27 узлов 2-4 с выхода блоков 6-8 записываются значения Qi, Bi. Ki, равные 11, О, 3 соответственно.

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

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

(Bj-nXKH-i)+bi+k,(Bj+i) (Bj+i)(qi(Kj+i)+ki)+bi,

J-1 Ax.i(K +1)+klгде j - номер этапа J m 1.4;

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

qi 0,Qj;

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

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

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

bi - текущая выборка (первый выход узла 3) bi - О, BJ

Уровень лог. 1 на выходе триггера 52 бл ока 12 разрешает прохождение синхроимпульсов на первый разряд выхода ключа 56. Инвертированные синхроимпульсы с первого разряда выхода ключа 56 блока 12 поступают на синхроеходы триггеров 25 узлов 2-4. На тактах 1-4 устройство записывает данные в первый операционный блок 13 При этом блок 11 формирует адреса 47, 46, 45 и 44 для блока 10 и адреса 3, 2, 1,0 для блока 9. По этим адресам на первых полутактах тактов 1-4 в блок 13 записываются пары значений функции и аргумента: f(X14, Х22, Х32, Х43), Х14, f(X13, X22, Х32, Х43), Х13, f(X12, Х22, Х32, Х43), Х12; f(X11, X22, X32, X43), X11.

Ключ 55 блока 12 подключает выход ключа 56 к первому 13 (второму операционному блоку при уровне лог. 1. (лог. 0.) на выходе триггера 51.

На тактах 1-4 инвертированные синхроимпульсы поступают на первые разряды выходов ключей 56 и 55 и разрешаютчтение значений из блока 10 и их запись в блок 13,

На вторых полутактах тактов 1-3 по заднему фронту синхроимпульса из счетчика 27 узла 4 вычитается 1 По достижению этим счетчиком нулевого значения на первом полутакте четвертого такта его выход заема устанавливается в лог. О, откуда уровень лог. О поступает на четвертый вход блока 12 и инверсный К-вход триггера 25 Пре,образо- ватель 50 блока 12 вырабатывает уровень лог. 1 по своим первому и шестому выходам. На втором полутакте такта 4 по заднему фронту синхроимпульса триггер 25 узла 4 и триггеры 51 и 53 блока 12 сбрасываются. При этом через элемент ИЛИ 23 на вход разрешения записи счетчика 27 подается уровень лог. О, разрешая запись значения К1 в счетчик, выход ключа 56 подключается к блоку 14, а блок 13 запускается для вычисления коэффициентов одномерного интерполирующего полинома.

Счетчики 27 узлов 2-4 соединены через входы 30 и выходы 37 по каскадной схеме. Поэтому передний фронт инвертированного синхроимпульса, поступающего на втором полутакте такта 4 на вход вычитания

единицы счетчика 27 узла 4, передается на вход вычитания единицы счетчика 27 узла 2, из которого вычитается 1 лак как счетчик 27 узла 3 равен нулю.

По переднему фронту синхроимпульса

на пятом такте элемент ИЛИ 21 узла 4 выра- батываетуровень лог 0, который устанавливает триггер 25 и этим запрещает запись данных в счетчик 27.

0 На тактах 5-8 устройство выполняет запись данных во второй операционный блок 14. Блок 11 формирует адреса 43, 42,41 и 40 для блока 10 и адреса 3, 2, 1,0 для блока 9. По этим адресам на тактах 5-8 в блок 14

5 записываются пары значений функции и аргумента: f(X14, Х21, Х32, Х43), Х14, f(X13, Х21, Х32, Х43); Х13; f(X12, X21, Х32, Х43), Х12; f(X11, X21, X32, X43),X11. При этом синхроимпульсы поступают на первый и

0 третий разряды выходов ключей 56 и 55, разрешая чтение значений из блока 10 и их запись в б ток 14. Счетчик 27 узла 1 на тактах 5-7 работает аналогично тактам 1-3 На первом полутакте такта 8 уровень лог. О с

5 выхода заема счетчика 27 поступает на К- вход триггера 25 узла 4 и четвертый вход блока 12. Проебразователь 50 блока 12 выдает лог. 1. по своему второму, четвертому и пятому выходам.

0На втором полутакте такта 8 по заднему

фронту синхроимпульса триггер 25 узла 4 и триггеры 25 и 54 блока 12 сбрасываются, а триггер 51 устанавливается, из счетчика 27 узла 2 вычитается единица

5 Уровень лог, 0 с выхода триггера 52 блокирует прохождение сигналов разрешения записи через элементы ИЛИ 23 на входы счетчиков 27, разрешает прохождение аналогичных сигналов с выходов триггеров

0 26 на входы счетчика 28, подключает их выходы к выходам 39 и 40 узлов 2-4 и разрешает прохождение синхроимпульсов на второй выход ключа 56 блока 12, который соединен с синхровходами триггеров 26.

5 Так как триггеры 26 узлов 2-4 сброшены сигналом пускз 15, то на втором полутакте гакта 8 в счетчики 26 записываются значения Qi.Bi.Ki соответственно. Уровнем лог. О с выхода триггера 54

0 блох 14 запускается для вычисления коэффициентов одномерного интерполирующего полинома. Уровнем лог. 1 с выхода триггера 51 выход ключа 55 подключается к блоку 13.

5 После переключения триггеров 51 и 52 преобразователь 50 выдает по седьмому выходу уровень лог. 0. который поступает на первый вход элемен га И 5 и блокирует прохождение через него синхроимпульсов. Операционные блоки 13, 14 выполняют одповременное вычисление коэффициентов интерполирующих полиномов (1) и (2).

А47.1 Х13+А46.1 Х12+А45.1 Х1+А44.1; (1)

А43.1 Х13+А42.1 ХГ+А41.1 Х1+А40.1. (2)

После окончания вычислений блок 13 вырабатывает синхронизированный с низким уровнем синхроимпульса сигнал окон- чания работы, который поступает на третий вход блока 12 и устанавливает триггер 53 в состояние лог.1, В результате этого преобразователь 50 выдает на первый выход блока 12 лог. 1 и разрешает прохождение синхроимпульсов через элемент 5.

Начинается чтение данных из первого операционного блока 13. В начале первого полутакта такта 9 элементы ИЛИ 22 вырабатывают уровень лог. 0., которым устанавли- ваются в состояние лог. 1 триггеры 26 узлов 2-4, прекращая этим запись в счетчики 28. На тактах 9-12 синхроимпульсы поступают на вторые выходы ключей 56 и 55 блока 12, разрешая чтение коэффициентов из блока 13 и их запись в блок 10. Значения А47.1, А461, А45.1, А44.1 записываются в блок 10.На вторых полутактах тактов 9-11 счетчик 28 узла 4 работает аналогично счетчику 27 на тактах 1-3. На первом полутакте такта 12 счетчик 28 узла 4 равен нулю и выдает лог.О на четвертый вход узла 12 и К-вход триггера 26. Преобразователь 50 выдает лог. 1 на свой шестой выход. На втором полутакте такта 12 по заднему фронту си.нх- роимпульса триггер 26 узла 4 и триггер 51 блока 12 сбрасываются.

Если блок 14 еще не завершил вычисления и триггер 54 сброшен, то после сброса триггера 51 преобразователь 50 выдает лог. О на первый выход блока 12 и блокирует прохождение синхроимпульсов через элемент 5 до окончания вычислений блоком 14. Лог 0 с выхода триггера 51 подключает выход ключа 56 к блоку 14.

Счетчики 28 узлов 2-4 соединены через выходы 38 и входы 31 по каскадной схеме, поэтому по переднему фронту инвертированного синхроимпульса, поступающего на вход вычитания единицы счетчика 28 узла 4 на втором полутакте такта 12, вычитание единицы происходит из счетчика 28 узла 2. Одновременно разрешается запись значения К в счетчик 28 узла 4. После окончания вычислений блок 14 аналогично блоку 13 вырабатывает сигнал окончания работы, который поступает на шестои вход блока 12 и устанавливает триггер 54.

На тактах 13-16 устройство производит чтение данных из второго 14 операционного

блока. Синхроимпульсы поступают на второй и четвертый выходы ключей 56 и 55, разрешая чтение коэффициентов из блока 14 и их запись в блок 10. В начале первого полутакта 13 устанавливается триггер 26 узла ч, прекращая запись в счетчик 28. На тактах 13-16 значения А43.1, А42. 1 , А41.1, А40.1 записываются в блок 10. На первом полутакте такта 16 счетчик 28 узла 4 равен нулю и выдает лог. О на входы преобразователи 50 и триггера 26. В результате этого преобразователь 50 выдает лог. 1 по своему третьему и пятому выходу. На втором полутакте такта 16 по заднему фронту синхроимпульса триггеры 52 и 51 устанавливаются, из счетчика 28 узла 2 вычитается единица.

Уровень лог. 1 с выхода триггера 52 блокирует прохождение сигналов разрешения записи через элементы ИЛИ 24 на входы счетчиков 28, разрешает прохождение аналогичных сигналов с выходов триггеров 25 на входы счетчиков 27. подключает их выходы к выходам 39 и 40 узлов 2-4 и разрешает прохождение синхроимпульсов на первый выход ключа 56, который соединен с синх- ровходйми триггеров 25. Так как триггер 25 узла 4 был ранее сброшен (на такте 8), то в счетчик 27 разрешается запись значения К1. Уровень лог. 1 с выхода триггера 51 подключает выходы ключа 56 к блоку 13. В начале такта 17 триггер 25 сбрасывается, прекращая запись в счетчик 27. Начинается запись данных в первый операционный блок 13.

Таким образом, устройство выполняет на тактах 1-4, 17-20. 33-36, 49-52, 65-68, 81-84 запись данных в блок 13; на тактах 5-8. 21-24, 37-40, 53-56. 69-72, 85-88 - запись данных в блок 14; на тактах 9-12, 25-28, 41-44. 57-60, 73-76, 89-92 - чтение данных из блока 13; на тактах 13-16, 28-32, 45-48, 61-64, 77-80. 93-96 - чтение данных из блока 14.

На первом полутакте такта 96 четвертый выход блока 12 установлен в состояние лог. 1 , к выходам узлов 2-4 подключены счетчики 28, равные нулю. На втором полутакте такта 96 передний фронт инвертированного синхроимпульса, поступающий на вход вычитания единицы счетчика 28 узла 4, транслируется счетчиками 28 узлов 3 и 2 на первый выход узла 2 и вычитание единицы происходит из счетного узла 1. Содержимое узла 1 становится равным 2 и начинается второй этап интерполяции.

В счетчики 27 узлов 2-4 с выходов блоков 6-8 памяти записываются числа Q2. В. равные 5,3,1 соответственно. На первых полутактах тактов 97-100 блок 11 формирует адреса 47, 43, 39. 35 для блока 10 и 5, 4, 5, 4 для блока 9. В операционный блок 13

записываются коэффициенты А47.1, А43.1, а в операционный блок 14 - А39.1, А35.1. Операционные блоки 13 и 14 выполняют одновременное вычисление коэффициентов интерполирующих полиномов

А47. + А43.. А39. + А35.2.

(3) (4)

которые на тактах 101-104 записываются в блок 10,

Аналогично выполняются и другие циклы второго этапа, пока не будут обработаны выборки из всех областей, а затем циклы третьего и четвертого этапов. Считывая последнюю выборку четвертого этапа, на тактах 382, 383, 384 блок 11 формирует адреса 32, 16, 0, в блок 10 записываются вычисленные коэффициенты А32.4, А16.4, АО.4. На первом полутакте такта 384 в счетчиках 28 узлов 2-4 находятся 0, передний фронт импульса с второго выхода ключа 56 транслируется счетчиками 28 узлов 2-4 и вычитание единицы происходит из счетного узла 1, Содержимое счетчика 1 становится равным 0. Первый выход узла 1 и подключенный к нему выход окончания работы устройства 18 становится равным лог. 0. При этом через элемент 5 блокируется прохождение синхроимпульсов, устройство переходит в состояние останова и возможно считывание коэффициентов полинома из блока 10 памяти

В качестве счетчиков 19, 27 и 28 можно использовать микросхемы К555ИЕ7, в качестве триггеров 25 и 26 - микросхемы К155ТВ15, в качестве коммутаторов 29 - микросхемы К555КП11. В качестве блоков 6-9 памяти можно использовать микросхемы К155РУ2, в качестве блока 10.- микросхемы К537РУ10, На третий вход блока 11 подается gi, на шестой вход - Bjt на пятый вход - ki, на четвертый вход - bi, на седьмой вход - Kj. Регистр 49 обнуляется сигналом пуска 15 и в конце каждого этапа добавляет к накопленной сумме значение Kj-n no сигналу с второго входа блока 11, который является входом записи регистра 51.

В качестве сумматоров 41-46 можно использовать микросхемы К155ИМЗ. Умножители 47 и 48 можно построить на микросхемах К155ИМЗ и К555ЛИ1.

Преобразователь 50 блока 12 можно выполнить на ПЗУ типа К155РЕЗ и элементах логики, В качестве триггеров 51 и 52 можно использовать микросхемы К531ТВ9, Триггеры 53 и 54 отличаются от стандартных К531ТВ9 тем, что имеют на инверсном асинхронном S-входе двухвходовой элемент И,

Ключ 56 представляет собой два элемента И-НЕ, первые входы которых соединены с прямым и инверсным выходами триггера 52, а вторые входы - с выходом

элемента 5. Ключ 55 представляет собой четыре элемента И , первые входы первого и третьего элементов И соединены с Первым выходом ключа 56, а второго и четвертого элементов И - с вторым выходом

0 ключа 56, вторые входы первого и второго элементов И соединены с прямым выходом триггера 51, а третьего и четвертого - с инверсным выходом триггера 51.

Операционные блоки 13 и 14 (фиг. 8)

5 состоят из вычислителя 57, блоков 58-60 памяти, регистра 61, элемента ИЛИ 62, дешифраторов 63-67, коммутаторов 68-70 Операционные блоки 13 и 14 выполняют полиномиальную интерполяцию с целью

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

Вычислитель 57 можно реализовать на микросхемах К1810ВМ86-процессор; КР580ИР82, КР580ВА86 - формирователи

5 магистрали.

Выходы вычислителя 57 подразделяются на адресные, информационные, управляющие. Информационные выходы вычислителя двунаправленные. Адресный

0 выход является выходом формирователя магистрали адреса (микросхемы КР580ИР82), информационный - выходом формирователя магистрали данных (микросхе.м.ы КР580ВА86), управляющий (сигналы RD,

5 WR) являются соответствующими выходами процессора. Седьмой вход блока 13 и второй вход блока 14 соединены с входами синхронизации CLC процессоров. Второй вход блока 13 и третий вход блока 14 являются

0 первыми входами информационных сигналов коммутаторов 68. Первый вход блока 13 и четвертый вход блока 14 являются первыми входами информационных сигналов коммутаторов 69. Третий вход блока 13 и пятый

5 вход блока 14 являются информационными входами регистров 61. Четвертый вход блока 13 и шестой вход блока 14 соединены с первыми входами адресных сигналов коммутаторов 68 и 69. Шестой вход блока 13 и

0 седьмой вход блока 14 - двухразрядные и соединены с первыми входами управляющих сигналов коммутаторов 68, причем вторые разряды этих входов соединены с входами управления коммутаторов 70, Шес5 той вход блока 13 соединен с первым и вто- , рым выходами ключа 55 блока 12, а седьмой вход блока 14 - с третьим и четвертым выходами ключа 55. Пятый вход блока 13 и первый вход блока 14 являются парафазными и соединены соответственно с прямыми и инверсными выходами триггеров 53 и 54 блока 12 С прямым выходом триггера 53 соединены входы сброса CLR) процессора блока 13, входы разрешения вывода (ОЕ) формирователей магистрали, Прямой и инверсный вы- ходы триггера 53 соединены с входами управления коммутаторов 68 и 69. Аналогично соединены узлы блока 14 с выходами тртгера 54. Выходы элемента ИЛИ 62 и коммутатора 70 являются соответственно первыми и вторыми выходами блоков 13 и 14.

Коммутаторы 68 и 69 подключают к блокам 58 и 59 памяти адресные, информационные и управляющие сигналы, поступающие как со стороны внутреннего вычислителя 57 операционного блока, так и внешнего по отношению к операционному блоку устройства. В связи с этим первые входы коммутаторов 68 и 69 могут быть раз- делены на первые входы адресных, информационных и управляющих сигналов Аналогичное деление можно провести для вторых входов и выходов коммутаторов 68 и 69 Одноименные выходы коммутируются с первыми входами при лог.О на инверсном выходе триггера 53(54), а с вторыми входами - при лог. О на прямом выходе триггера 53(54).

Адресный выход вычислителя 57 соеди- нен с вторыми входами адресных сигналов коммутаторов 68 и 69, адресными входами дешифраторов 63-67. Информационный выход вычислителя 57 соединен с вторыми входами информационных сигналов комму- таторов 68 и 69, выходами блоков 58-60 памяти, регистра 61. Управляющий выход вычислителя 57 соединен с вторыми входами управляющих сигналов коммутаторов 68 и 69, входами управления блока 60 памяти, дешифратора 67, элемента ИЛИ 62.

Дешифраторы 63-67 служат для формирования сигнала разрешения ввода/вывода в блоки 58-62, если их собственный адрес совпадает с адресом, передаваемым вычис- лителем 57 на свой адресный выход. Собственный адрес устройства формируется за счет подключения сигнала разрешения ввода/вывода на один из выходов дешифратора. Дешифратор 67 помимо адресного входа имеет управляющий вход, который разрешает работу дешифратора, если есть управляющий сигнал Чтение. Это позволяет сделать регистр 61 доступным для процессора только по чтению.

Операционный блок работает следующим образом. В начальном состоянии на вход CLR процессора и формирователя магистрали операционного блока подается сигнал лог. 1, за счет этого формирователи

магистрали находятся в третьем состоянии. Сигнал лог. 1. поступает на управляющие входы коммутаторе 68 и 69, которые подключают адресные входы и входы управления блоков 58 и 59 памяти через первые входы коммутаторов 68 и 69 к первому выходу узла 4 и третьему выходу блока 12 соответственно, а информационные входы блоков 58 и 59 - к выходам блоков 10 и 9 памяти соответственно. По адресам, поступающим с выхода узла 4, импульсами лог. О с третьего выхода блока 12 в блоки 58 и 59 записываются значения функции и аргумента. После того, как записаны все значения, триггер 53 или 54 сбрасывается, при этом входы блоков 58 и 59 через вторые входы коммутаторов 68 и 69 подключаются к магистрали процессора. Процессор начинает выполнять записанную в блоке 60 памяти программу. Вначале считывается уменьшенное на единицу число значений аргумента из регистра 61. При чтении процессором регистра 61 дешифратор 66 формирует сигнал разрешения ввода/вывода, который поступает на вход разрешения вывода регистра 61 (вывод ОЕ микросхемы КР580ИР82, вывод строба STB микросхемы подключен к лог. 1). В результате на выход регистра 61 передается состояние его информационного входа, который соединен с выходом блока 8 памяти, в котором записано уменьшенное на 1 количество значений j аргумента функции F. Содержимое регистра 61 позволяет отделить значащие ячейки блоков 58 и 59 от других, в которые данные не записывались. Затем производится полиномиальная интерполяция методом Лаг- ранжа по приведенному алгоритму. Алгоритм LAGR

1.Начало алгоритма.

2.Начало цикла по i(i 1,Re).

3.Присваивание Si: О.

4.Присваивание А: 1.

5.Начало цикла по j 0 1-Re).

6.Если I о j. то (Xi-Xj).

7.Конец цикла по j.

8.Вычисление Yc Yi/A.

9.Конец цикла по I.

10.Начало цикла по i(l 1,RB).

11.Начало цикла по j(j 2,RB).

12.Присваивание Vj: 0.

13.Конец цикла no j.

14.Присваивание Vi: 1.

15.Присваивание Wi: 0.

16.Присваивание В:. 1.

17.Начало цикла по j(j 1,RB).

18.Если I-j, T0j:-j + 1.

19.Начало цикла по k(k 1,8).

20.Вычисление - Vk+1-Vk Xj.

21.Конец цикла по к.

22.Вычисление В: - В-И.

23.Начало цикла по k(k 2,8).

24.Присваивание Wk.

25.Конец цикла по k.

26.Конец цикла по J.

27.Начало цикла по JQ 1,В).

28.Вычисление I: B-J+1.

29.Вычисление Si: Si+Vj Y|.

30.Конец цикла по .

31.Конец цикла по I.

32.Конец алгоритма.

Здесь RB - размер выборки , т.е. количество пар значений аргумента и функции; X - массив, в котором хранятся значения аргумента; Y - массив, в котором хранятся значения функции; S - массив, в котором хранятся коэффициенты полученного в результате интерполяции одномерного полинома; V и W - вспомогательные массивы; А, В и I - вспомогательные переменные; j и k - счетчики итераций циклов.

Затем процессор переписывает массив коэффициентов в блок 58 на место значений функции и выполняет цикл записи по фикси- рованноу адресу. При обращении по этому адресу выход дешифратора 67 принимает значение лог. О, по приходу импульса записи WR срабатывает элемент ИЛИ 62, сигнал с выхода которого поступает на первый выход операционного блока. 1 риггер 55 или 56 устанавливается. В результате на вход начальной установки CLR процессора подается сигнал лог. 1, адресные входы и входы управления блоков 58 и 59 памяти через первые входы коммутаторов 68 и 69 подклю- чаются к первому выходу узла 4 и третьему выходу блока 12,

Если на управляющий вход коммутатора 70 подается уровень лог. 1, то его выходы и выходы блока 58 памяти находятся в треть- ем состоянии. Считывание коэффициентов производится импульсами лог. 0. При этом на выход блока 58 выдаются данные, которые передаются через коммутатор 70 на второй выход операционного блока. Импульсы чтения не поступают в блок 59 и поэтому его информационный выход находится в третьем состоянии.

Блоки 58 и 59 памяти аналогичны блоку 10 памяти. В качестве блока 60 можно ис- пользовать микросхемы К573РФ5. в качестве регистра 61 и коммутатора 70 - микросхемы КР580ИР82, в качестве дешифраторов 63-67 - микросхемы К155ИДЗ, в качестве коммутаторов 68 и 69 - микросхе- мы КР580ИР82, управляемые парафззкым сигналом с седьмого входа операционного блока.

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

5

0

5

0 5

0 5

0 5

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

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

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

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

i акт

Сьнхр L/CfTJff /7 Второй St/к зл 1

Второй дых зл I Лерёый SbiX зл J Пердыи Вы зл 4 ЛерВый дых зл 11

йторой Зык зл Л Пятый 8ых зл 12 перВый разряд Пятый оьк зм 12 Второй разряд Четвертый 8ых зли ПерВый Sb/х эл 12

Второй вых. зл П Шестой Вых зл. /J Пврбый дых. зл 13 Первый дш эл 14 &ь/х эл 5 Пуск устр 15 Окончание рад 18

ФиеЗ

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

Фие4

и

«

и

и

8918Ш

Массид F

1 этЬп ин/перлолрцсш

ЛобластьЮо&ляслъ

47 46 43 44 43 42 V 40

Выборка О &/ЯоркаО

2 ЗЛ70/7 t/H/77Ј P/ 0J1f ULfU

5 область Массив А 47 ft 4J М $ у w 40

8ы$.3 Вы5.2 Выб.1 Выб.О

3 зтап интерполяции

2 область Массив А 47 46 ЬО 3938 32

Выд.7 Выё.б8ыд.ОAtf 7 fa&6Выд.О

Ц этап интерполяции

О область МассидА 47 4632 31 30fi & W ,

Вы б. 15 Вы д. Я

О область 3 2

ВыдорхяО

О одлас/пь

Выд.З Вы5.2 6ы5.1 Выд.О

О область /S # 376 О

Ъь/б.О

Фиг.7