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

 

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

„„ЯЦ„„1748158 А1

СО103 СОВЕТСКИХ

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

РЕСГ1УБЛИК (я)5 G 06 F 15/353 >7093

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

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

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ с, . :

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 2 (21}4827057/24 иномов nî значениям двух различных выбо(22) 21.05.90 рок. Значения интерполируемой функции, (46) 15.07.92. Бюл, N 26 . промежуточные и окончательные результа(71) Одесский политехнический институт. ты хранятся в блоке 10 памяти, в блоке 9 (72) В.А.Парасочкин, Ю.И.Костелов и памяти хранятся значения аргументов, В, Г,Ткаченко Арифметические операций, связанные с вы(53) 681.325(088.8) . численйем коэффициентов интерполирую(56) Авторское свидетельство СССР щего. полинома по. значенйям выборки.

¹ 1667104, кл. G 06 F 15/353, 1989, функции и аргумента, вййолняются в операАвторское свидетельство СССР: циойных блоках 13, 14; Формирование выМ - 1317452, кл. G 06 F 15/353, 1985, борки осуществляется блоками 7, 8 памяти, содержащими чйсленные значения кон(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КО- стант вычйслительного процесса, счетными

ЭФФИЦИЕНТОВ ИНТЕРПОЛИРУЮЩЕГО узлами 2 — 4 и блоком 11 формирования адПОЛИНОМА .. ": :: . "ресов. Управление ходом вйчислений про(57) Изобретение относится к автоматике, изводится с помощью счетното узла 1,. вычислительноЪ технике и средствам обра- элемента И 5, блока 6 памяти, узла управлеботки экспериментальной информации. ния 12.Укаэанные элементы позволяют расЦелью изобретения является увеличение параллелить процесс вычисления быстродействия устройства за счет одно- . коэффициентов одйомерных полиномов на. временного вычисления коэффицйентов двух неэависимйх операционных блоках 13, двух одномерных интерполирующих пол 14 8 ил

1748158

20

30

50

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

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

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

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

Указанная цель достигается тем, что s устройство, содержащее четыре счетных узла, элемент И, блок управления, три блока памяти, блок памяти аргументов, блок памяти функций и первый операционный блок, причем вход пуска устройства соединен с первыми входами всех счетных узлов, блока формирования адреса и блока управления, второй вход которого соединен с выходом элемента И, первый, второй и третий входы которого соединены соответственно с пер- . вым выходом блока управления, синхровходом устройства и первым выходом первого счетного узла, второй вход которого соединен с входом количества аргументов устройства, а третий вход — с вторым входом блока формирования адреса и с первым выходом второго счетного узла, второй выход которого соединен с третьим входом блока формирования адреса, четвертый и пятый, шестой и седьмой входы которого соединены соответственно с первыми выходами третьего и четвертого счетных узлов, и выходами первого и второго блоков памяти, адресные входы которых соединены с адресным входом третьего блока памяти и вторым выходом первого счетного узла, первый выход которого соединен с выходом окончания работы устройства, вторые входы второго, третьего и четвертого счетных узлов соединены соответственно с выходами третьего, первого и второго блоков памяти, третий вход второго счетного узла соединен с вторым выходом третьего счетного узла, первый и второй вы1748158 ском порядке. Вычисление коэффициентов интерполирующего полинома такой функции выполняется по известному алгоритму, Устройство (фиг, 1) содержит первый 1, ходы блока формирования адреса подключены соответственно к адресным входам блоков памяти аргументов и функций, выходы которых подключены соответственно к второй 2, третий 3 и четвертый 4 счетные первому и второму входам первого опера- 5 ционного блока, третий и четвертый входы и первый выход которого подключены соответственно к выходу второго блока памяти, к первому выходу четвертого счетного узла и к третьему входу блока управления, чет- 1 узлы. элемент И 5, первый 7, второй 8, третий 6 блоки памяти, блок памяти 9 аргументов, блок памяти 10 функций, блок 11 формирования адреса, блок 12 управления, первый 13 и второй 14 операционные блоки, вертый вход, второй и третий выходы которого соединены соответственно с вторым выходом четвертого счетного узла и с пятым, шестым входами первого операционпричем вход 15 пуска устройства соединен с первыми входами счетных узлов 1-4, блока 11 формирования адреса и блока 12 управления, второй вход которого соединен с ного блока, седьмой вход котоporo 15 выходом элемента И 5, первый, второй и соединен с синхровходом устройства. введен второй операционный блок, причем третретий входы которого соединены соответственно с первым выходом блока 12 управвторого счетного узла соединены соответст- 20 BropoA вход которого соединен с входом 16 венно с четвертым и пятым выходами блока управления, пятый и шестой входы и пятый количества аргументов устройства, а третий вход — с вторым входом блока .11 формирои шестой выходы которого подключены сования адреса и с первым выходом второго 2 счетногоузла, второй выход которого соедиответственно к третьему выходу второго счетного узла, к первому выходу второго 25 нен с третьим входом блока 11 формироваоперационного блока, к входу задания ре- ния адреса, четвертной и пятый, шестой и жима блока памяти функцийипервомувхо- .. седьмой входы которого соединены соот ду второго операционного блока, второй; третий, четвертый, пятый; шестой и седьмой ветственно с первыми выходами третьего 3 и четвертого 4 счетных узлов и выходами входы erорого операционного блока соеди- ЗО первого 7 и второго 8 блоков памяти, адреснены соответственно с синхровходом уст-- ные входы которых соединены с адресным ройства, входами блоков памяти функций и @ходом третьего блока 9 памяти и вторым аргументов, выходом второго блока памяти, выходом nepeoro счетного узла 1, первый выходомчетвертогосчетногоузлаитретьим выход которого соединен с выходом 18 выходом блока управления, вторые выходы 35 окончания работы устройства. вторые входы первого и второго операционных блоков. второго 2, третьего 3 и четвертого 4 счетных объединены и подключены к информацион-. узлов соединены соответственно с выходаному входу блока памяти функций„третий ми третьего 6, первого 7 и второго 8 блоков выход четвертого счетного узла подключен памяти, третий вход второго 2 счетного узла к пятому входу третьего счетного узла, ." 40 соединен с вторым выходом третьего счетПредлагаемое устройство позволяет од- ного узла 3, первый и второй выходы блока новременно вычислять коэффициенты даух. - 11 формирования адреса подключейы соотодномерных интерполирующих полиномов ветственно к адресным входам блоков памяпо значениям двух различных выборок и за ти аргументов 9 и функцйй 10. выходы счет этого увеличить быстродействие уст- 45 которых подключены соответственно к перройства. . ." вому и второму входам первого операционУстройство вычисляет коэффициенты ного блока 13, третий и четвертый входы и обобщенного полинома А . первый выход которого подключены соот ветственно к выходу второго блока 8 памя50 ти, к первому выходу четвертого счетного

Р =(А *х1 *х 2 ° .- х о ) Р (1) .. узла4 и к третьему входу блока 12 управле. i-1 ния, четвертый вход, второй и третий выходы которого соедийены соответственно с вторым выходом четвертого счетного узла 4

55 и с пятым, шестым входами первого операИсходными данными для определения значений коэффициентов А является поСлецгонного блока 13;.седьмой вход которого довательность значений аргументов Х1, соединен с синхровходом 18 устройства, третий и четвертый входы третьего 3 и четвертого 4 счетных узлов и четвертый, пятый тийичетвертыйвходытретьегоичетвертого - ления, синхровходом 17 устройства и счетных узлов и четверть1й. пятый входы: первым выходом"первогд 1 счетного узла;

1748158

4 соответственно с четвертым и пятым выходами блока 12 управления, пятый и шестой входы и пятый и шестой выходы которого подключены соответственно к третьему выходу второго счетного узла 2, к первому выходу второго ойерационного блока 14, к входу задания режима блока 10 памяти функций и первому входу второго oneрационноro блока 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, 10 Коммутатор 29 подключает к первому и . второму выходу первый и третий входи при уровне лог, 1 на входе 36, и второй и четвертый — при уровне лог. 0

Блок 11 формирования адреса (фиг. 5) состоит из сумматоров 41 — 46, умножителей

47 и.48, регистра 49, причем выход суммато15 ра 42 соединен с информационным входом регистра 49, выход которого соединен с первыми входами сумматоров 42 и 45, вход

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

43 и умножителя 47, выход которого соединен с вторым входом сумматора 43, выход которого соединен с первым входом сумматора 46, выход которого является. вторым

30 выходом блока 11, третий вход которого явумножителя 47, пятый вход блока 11 соединен с вторыми входами сумматоров 44 и 45, четвертый вход блока 11 является входом сумматора 46, выход сумматора 45 является йервым выходом блока 11, на второй вход сумматора 41 подается единичное значение.

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

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

J- и К-входами триггера 52, одноименные входы триггера 51 соединены с пятым и шеляется вторым входом умножителя 48, шес35 той вход блока 11 является вторым входом

1748158

10 стым выходами преобразователя 50, седьмой выход которого является первым выхо- дом блока 12, второй вход которого является входом строба триггеров 51-54 и соединен с первым входом логического ключа 56, вы- 5 ход которого является пятым выходом блока 01=

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

-1+П (К +1)

1)+1

0 приJ= I, и — 1; при) = и

Каждое из чисел К1, В1, 0) хранится по

10 адресу и — + 1. В блоке 9, начиная с адреса

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

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

По сигналу пуска 15, который совпадает с нйэким уровнем сийхроимпульса на синхровходе 17, в счетный узел 1 с входа количества аргументов .. устройства 16

25 записывается число этапов вычислений,равное 4; триггеры 25 и 26 (фиг. 4) счетных узлов

2 — 4 сбрасываются; блок 11 формирования адреса и блок 12 управления устанавливаются в исходное cocT(NHN8. При этом триг30 геры 51 — 54 блока 12 устанавливаются в состояние лог.1, Первый выход блока 12 также устанавливается в состояние лог. 1. разрешая прохождение синхроимпульсов через элемент И 5. . 35 Уровень лог, 1. на четвертом выходе блока 12 подключает к выходам 39 и 40 узлов 2 — 4 счетчики 27 и разрешает для них запись данных. Поэтому по сигналу пуска устройства 15 в счетчики 27 узлов 2-4 с

40 выхода блоков 6-8 записываются значения

01, В1. К1, равные 11, О, 3 соответственно.

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

45 от состояния выходов счетных узлов 2-4 и блоков 7 и 8 памяти.

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

О при J 1:

)-1

-1+ П (К+1) при) 2,п . 55

1-1

J 1

Ax g (K + 1)+" 1.

1=-1 где j —. номер этапа j 1.4:

q1 — текущая область интерполяции (второй выход узла 2) ключа 55, выход которого является третьим выходом блока 12, четвертым выходом которого является выход триггера 52, который соединен с вторым входом ключа 56, выход триггера 51 соединен с вторым входом ключа 55, выходы триггеров 53 и 54 являются соответственно вторым и шестым выходами блока 12.

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

КВ*Т51*Т52;; КВ Т52" Т51;

К В * К Э*Т52*Т51+ К В *Т51*Т52;

КЪ+КЭ*Т51*Т52+КВ+Т52*Т51;

КВ*Т51; КВ*КЭ+Т51; (Т53+Т52+Т51)*(Т54+Т51+Т52), . где Т51, Т52, Т53, Т54 — состояние прямых выходов триггеров 51-54 соответствейно;

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

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

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

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

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

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

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

11, 5, 1, О, где 0Д = 1,4)- уменьшенное на 1

АуЦ1*(В)+1)(К)+1)+Ь|+Ь(В 1+ 1)=

=(В)+1)*(Ц1*(К)+1)+1с )+ Ь|;

qI - О,Q, 81 — уменьшенное на 1 число выборок в области на)-м этапе вычислений (выход блока 7), Kf — уменьшенное на 1 число значений аргумента на )-м этапе вычислений (выход блока 8); К вЂ” 1 =-1;

Ь вЂ” номер элемента в выборке (первый выход узла 4) kI = О, К1, bI — текущая выборка (первый выход узла 3) bI = 0, 81.

Уровень лог. 1 на выходе триггера 52 блока 12 разрешает прохождение синхроимпульсов на первый разряд выхода ключа

56. Инвертированные синхроимпульсы с первого разряда вь хода ключа 56 блока 12 поступают на синхровходы триггеров 25 узлов 2 — 4, На тактах 1 — 4 устройство записывает данные в первый операционный блок

13, При этом блок 11 формирует адреса 47, 46, 45 и 44 для блока 10 и адреса 3. 2, 1, О для блока 9. По этим адресам на первых полутактах.тактов 1-4 в блок 13 записываются пары значений функции и аргумента:

f(X14, Х22, Х32, Х43), Х14; f(X13, Х22, Х32, X43), Х13; f(X12, Х22, Х32, X43), Х12; f(X11, Х22, Х32, Х43), Х11.

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

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

27.узла 4 вь|читается 1. По достижениЮ этим счетчиком нулевого значения на первом полутакте четвертого такта его выход заема устанавливается в лог, О, откуда уровень лог .

О поступает на четвертый вход блока 12 и инверсный К-вход триггера 25, Преобразователь 50 блока 12 вырабатывает уровень

nor. 1 посвоим первому, и шестоМу выходам, На втором полутакте такта 4 по заднему фронту синхроимпульса триггер 25 узла 4 и триггеры 51 и 53 блока 12 сбрасываются, При этом через элемент ИЛИ 23 на вход разрешения записи счетчика 27 подается уровень лог, О, разрешая запись значения

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

Счетчики 27 узлов 2 — 4 соединены через входы 30 и выходы 37 по каскадной схеме.

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

20 5

ЗО

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

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

На тактах 5-8 устройство выполняет запись данных во второй операционный блок

14. Блок 11 формирует адреса 43, 42, 41 и 40 для блока 10 и адреса 3, 2, 1, О для блока 9, По этим адресам на тактах,5 — 8 в блок 14 записываются пэры значений функции и аргумента: f(X14, Х21, Х32, Х43), Х14; f(X13, Х21, Х32, Х43); Х13; f(X12, Х21, ХЗ2, X43), Х12; f(X11, Х21, Х32, Х43) Х11. При этом синхроимпульсы поступают на первый и третий разряды выходов ключей 56 и 55, разрешая чтение значений из блока 10 и их запись в блок 14, Счетчик 27 узла 4 на тактах

5 — 7 работает аналогично тактам 1-3. На первом полутакте такта 8 уровень лог. О с выхода заема счетчика 27 поступает на Квход триггера 25 узла 4 и четвертый вход блока 12, Проебразователь 50 блока 12 выдает лог, 1. по своему второму, четвертому и пятому выходам, На втором полутакте такта 8 по заднему фронту синхроимпульса триггер 25 узла 4 и триггеры 25 и 54 блока 12 сбрасываются, а триггер 51 устанавливается, из счетчика 27 узла 2 вычитается единица

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

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

Так как триггеры 26 узлов 2 — 4 сброшены сигналом пуска 15, то на втором полутакте такта 8 в счетчики 26 записываются значения 01,81,К1 соответственно.

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

После переключения триггеров 51 и 52 преобразователь 50 выдает по седьмому выходу уровень лог. О, который rIocT) naeò на первый вход элемента И 5 и блокирует прахождение через него синхроимпульсов.

Операционные блоки 13, 14 выполняют одФ

1748158

20

27 на тактах 1-3. На первом полутакте такта 30

12 счетчик 28 узла 4 равен нулю и выдает. триггера 26. Преобразователь 50 выдает лог, 1 на свой шестой выход. На втором полутакте такта 12 по заднему фронту синх- 35 ния и триггер 54 сброшен, то после сброса триггера 51 преобразователь 50 выдает лог. 40

О на первый выход блока 12 и блокирует ход ключа 56 к блоку 14

50 новременное вычисление коэффициентов интерполирующих полиномов (1) и (2), А47.1*X1 +А46,1*Х1 + А45,1*Х1+ А44.1; (1)

А43,1*X1 +А42.1*X1 + А41,1*X1+ А40,1. (2) После окончания вычислений блок 13 вырабатывает синхронизированный с низким уровнем синхроимпульса сигнал окончания pc360Tbl, KOTOpblA поступает нэ третий вход блока 12 и устанавливает триггер 53 в состояние лог.1, В результате этого преобразователь 50 выдает на первый выход блока 12 лог, 1 и разрешает прохождение синхроимпульсов через элемент 5.

Начинается чтение данных из первого операционного блока 13, B начале первого полутакта такта 9 элементы ИЛИ 22 вырабатывают уровень лог. О., которым устанавливаются в состояние лог. 1 триггеры 26 узлов

2-4, прекращая этим запись в счетчики 28.

На тактах 9-12 синхроимпульсы поступают на вторые выходы ключей 56 и 55 блока 12, разрешая чтение коэффициентов из блока

13 и их запись в блок 10. Значения А47Л, А46.1, А45.1, А44.1 записываются в блок

10.На вторых полутактах тактов 9 — 11 счетчик 28 узла 4 работает аналогично счетчику лог.О на четвертый вход узла 12 и К-вход роимпульса триггер 26 узла 4 и триггер 51 блока 12 сбрасываются., Если блок 14 еще не завершил вычислепрохождение синхроимпульсов через:элемент 5 до окончания вычислений блоком 14.

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

Одновременно разрешается запись значения Кг в счетчик 28 узла 4, После окончания вычислений блок 14 аналогично блоку 13 вырабатывает сигнал окончания работы, который поступает на шестой вход блока 12 и устанавливает триггер 54, На тактах 13-16 устройство производит чтение данных из второго 14 операционного

15 блока. Синхроимпульсы поступают на второй и четвертый выходы ключей 56 и 55. разрешая чтение коэффициентов из блока

14 и их запись в блок 10. В начале первого полутакта 13 устанавливается триггер

26 узла ч, прекращая запись в счетчик 28. На тактах 13-16 значения А43,1, А42. 1, А41,1, А40.1 записываются в блок 10. На первом полутакте такта 16 счетчик 28 узла 4 равен нулю и выдает лог, 0 на входы преобразователя 50 и tp rrepa 28. В результате этого преобразователь 50 выдает лог; 1 по своему третьему и пятому вйходу. На втором полутакте такта 16 по заднему фронту синхроимпульса триггеры 52 и 51 устанавливаются, иэ счетчика 28 узла 2- вычитается единица.

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

Уровень лог. t с выхода трйггера 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, В2, К,равные 5, 3, 1 соответственно. На первых полутактах тактов 97-100 блок 11 формирует адреса 47, 43, 39, 35 для блока 10 и 5, 4, 5, 4 для блока 9. В операционный блок 13

1748158

15 записываются коэффициенты А47,1, А43.1, а в операционный блок 14 —. A39,1, А35.1.

Операционные блоки 13 и 14 выполняют одновременное вычисление коэффициентов интерполирующих полиномов

16

Р

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

5 элемента 5. Ключ 55 представляет собой четыре элемента И, первые входы пер. А47.2*Х2+ А43.2*Х1;

А39.2*Х2 + A35;2, (3) (4) которые на тактах 101 — 104 записываются в блок 10.

Аналогично выполняются и другие циклы второго этапа, пока не будут обработаны выборки иэ всех областей, а затем циклы третьего и четвертого этапов, Считывая последнюю выборку четвертого этапа, на тактах 382, 383, 384 блок 11 формирует адреса

32, 16, О, в блок 10 записываются вычисленные коэффициенты АЗ2.4, А16,4, А0.4, На первом полутакте такта 384 в счетчиках 28 узлов 2 — 4 находятся О, передний фронт импульса с второго выхода ключа 56 транслируется счетчиками 28 узлов 2 — 4 и вычитание единицы происходит из счетнога узла 1, Со держимое счетчика 1 становится равным О.

Первый выход узла 1 и подключенный к нему выход окончания работы устройства 18 становится равным лаг, О, При этом через элемент 5 блокируется прохождение синхраимпул ьсов, устройство переходит в состо:яние астанава и возможно считывание коэффициентов палинама из блока 10 памяти;

В качестве счетчйков 19, 27 и 28 можно. использовать микросхемы К555ИЕ7, в качестве триггеров 25 и 26 — микросхемы, К155ТВ15, в качестве коммутаторов 29— микросхемы К555КП11, В качестве блоков

6-9 памяти можно использовать микросхемы К155РУ2, в качестве блока 10.— микросхемы К537РУ10, На третий вход блока 11 .подается gi, на шестой вход — В1, на пятый вход — Ь,. на четвертый вход — bl, на Седьмой вход — К . Регистр 49 обнуляется сигналом пуска 15 и в конце каждого этапа добавляет к накопленной сумме значение К +1 по сигналу с второго входа блока 11, который является входом записи регистра 51.

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

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

К531ТВ9 тем, чта имеют на инверсном асинхронном $-входе двухвходовой элемент И, вого и третьего элементов И соединены С первым выходом ключа 56, а второго и четвертого элементов И вЂ” с вторым выходам ключа 56, вторые входы первого и второго элементов И соединены с прямым выходом триггера 51, а третьего и четвертого — с инверсным выходом триггера 51.

Операционные блоки 13 и 14 (фиг, 8) состоят из вычислителя 57, блоков 58 — 60

15 памяти, регистра 61, элемента ИЛИ 62, дешифраторов 63-67, коммутаторов 68 — 70.

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

Вычислитель 57 можно реализовать на

20 микросхемах К1810ВМ86 — процессор;

КР580И Р82, KP580BA86 — формирователи магистрали.

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

50 вход блока 14 являются информационными входами регистров 61. Четвертый вход блока 13 и шестой вход блока 14 соединены с первыми входами адресных сигналов коммутаторов 68 и 69. Шестой вход блока 13 и седьмой вход блока 14 — двухразрядные и соединены с первыми входами управляющих сигналов коммутаторов 68, причем вторые разряды этих входов соединены с входами управления коммутаторов 70, LUecтай вход блока 13 соединен с первым и вторым выходами ключа 55 блока 12, а седьмой вход блока 14 — с третьим и четвертым выхо55

1 дами ключа 55. Пятый вход блока 13 и первый вход блока 14 являются парафазными и соединены соответственно с прямыми и инющие, Информационные выходы вычислителя двунаправленные.. Адресный

30 выход является выходом формирователя магистрали адреса {микросхемы КР580ИР82), информацион ный — выходом формирователя магистрали данных (микрасхемы

KP580BA86), управляющий (сигналы RD, 35 ЮР) являются соответствующими выходами процессора, Седьмой вход блока 13 и второй вход блока 14 соединены с входами синхронизации CLC процессоров. Второй вход блока 13 и третий вход блока 14 являются

40 первыми входами информационных сигна1748158

18 версными выходами триггеров 53 и 54 блока магистрали находятся в третьем состоянии.

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

14. с третьего вйхода блока 12 в блокй 58 и 59

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

Аналогичное деление можно провести для процессором регистра 61 дешифратор 66 вторых входов и выходов коммутаторов 68 и формирует сигнал разрешения ввода/выво69. Одноименные выходы коммутируются с 25 да, который поступает на вход разрешения первыми входами при лог,О на инверсйом вывода регистра 61 (вывод ОЕ микросхемы выходе триггера 53(54); а с вторыми входа- КР580ИР82, вывод строба STB микросхемы ми — при лог. 0 на прямом выходе триггера подключен к лог. 1). В результате на выход

53(54). регистра 61 передается состояние его инАдресный выход вычислителя 57 соеди- 30 формационного входа, который соедийен с нен с вторыми входами адресных сигналов выходом блока 8 памяти, в котором записакоммутаторов 68 и 69. адресными входами ноуменьшенное на 1 количествозначенийj дешифраторов 63-67. Информационный . аргументафункцииР.Содержимоерегистра выход вычислителя 57 соединен с вторыми 61 позволяет отделить значащие ячейки входами информационных сигйалов комму- 35 блоков 58 и 59 от других, в которые данные таторов 68 и 69, выходами блоков 58-60 не записывались. Затем производится полпамяти, регистра 61, Управляющий выход иномиальная интерполяция методом Лагвычислителя 57 соединен с вторыми входа- ранжа bio приведенному алгоритму. ми управляющих сигналов коммутаторов 68 Алгоритм LAGR и 69, входами управления блока 60 памяти, 40 1. Начало алгоритма. дешифратора 67, элемента ИЛИ 62.: — " - . 2. Начало цикла по i(i = 1,й ).

Дешифраторы 63 — 67 служат для форми- 3. Присваивание Sl: - О. рования сигнала разрешения ввода/вывода 4. Присваивайие А: = 1. в блоки 58-62, если их собственный адрес 5. Начало цикла rio j (j = 1ЯВ). совпадает с адресом, передаваемым вычис- 45 " 6. Если i < > j, то АяА (Xi-Õi). лителем 57 на свой адресный выход. Собст-: 7. Конец цикла по j. венный адрес устройства формируется за 8. Вычисление Yi . - %/А. счет подключения сигнала разрешения вво- 9. Конец цикла по 1. да/вывода на один из выходов дешифрато- 10, Начало цикла no i(l - 1,RS). ра.Дешифратор67помимоадресноговхода .50 11. Начало цикла поj(j -2.R>). имеет управляющий вход, который раэре- 12. Присваивание Vi .- О. шает работу дешифратора, если есть управ- 13. Конец цикла по j. ляющий сигнал "Чтение", Это позволяет 14. Присваивание V>. - t. сделать регистр 61 доступным для процес- 15. Присваивание W<: = О.. сора только по чтению.. 55 16. Присваивание В: . 1.

Операционный блок работает следую- 17. Начало цикла по Я = 1Яв). щим образом, В.начальном состоянии на 18. Еслибы),то):-j+1. вход CLR процессора и формирователя ма- 19, Начало цикла по k(k = 1,B), гистрали операционного блока подается 20. Вычисление We+1: " Чк+1-Чк*Х . сигнал лог. 1, за счет этого формирователи 21. Конец цикла по k.

1748158

22; Вычисление В: - В+1.

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

24. Присваиаание Vy; = В4.

25. Конец цикла по k, 26. Конец цикла по j. 5

27. Начало цикла по Щ = 1,В), 28, Вычисление 1: = В-j+1.

29, Вычисление Я : = Si+Vj*Y<.

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

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

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

Здесь RB — размер выборки, т.е, количество пар значений аргумента и функции; Х— массив, в котором хранятся значения аргу- мента; Y — массив,в котором хранятся зна- 15 чения функции; S — массив, в котором ., хранятся коэффициенты полученного в результате интерполяции одномерного полинома; V u W — вспомогательные массивы;

А, В и — вспомогательные переменные;1 j 20 и k — счетчики итераций циклов.

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

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

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

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

22 онный блок, причем третьи и четвертые третий, четвертый, йятйй,шестой иседьмой

:входы третьего и четвертото счетйых входы второго операцэйзнйого блока соеди узлов и четвертый и пятый входы второ- I нены соответственно с синхровходом устго счетного узла соединены соответст-" ройства, выходами блоков памятйфункций венно с четвертым и пятым выходами 5 и аргументов, выходом второго блока памяблока управления, пятый и шестой вхо- ти, выходом четвертого счетного узла и ды и пятый и шестой выходы которого третьимвыходомблокауправмния; вторые .подкл ючен ы соответственно к: выходы первого и второго операционных

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

174Р I 58

1748158

1748158

1748158

0 udnpcm

Aidu ug

Р adverb

0 odium

1х/4 3 7 6

Ею О

РуЮ7 Рэ Юб тЬ инвераомции кассиа F )p а рр ö

Выборщ О ВвдоркаО

Я зтаа интерлоляиии

ХоГлюл 6 дыЮЮ 6ьй2 был Выб.О

Рзпуай унжерполяцуи

3 ямРсюБ

УасЫА 47 46 М Jf J8 Л

Ъ|Ю1 Вь 61 Вы61 Ю lЫ °

1748158

Составитель ЮУастелов

Техред М.Моргентал Корректор А.Осауленко

Редактор Е.Коп«а

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

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

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

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