Устройство для вычисления значений многомерного полинома Советский патент 1992 года по МПК G06F15/31 

Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах контроля, работающих в реальном масштабе времени.

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

Известно устройство для вычисления

значений многомерного (обобщенного) пол- N

инома, содержащее генератор импульсов,

счетчик количества аргументов, счетчик ко-Ю

личества членов полинома, узел памяти ар-00

гументов, узел памяти показателей степени,|

узел памяти коэффициентов полинома,

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

Ја,А,Й

(D

при работе с действительными аргументами и коэффициентами, где

X - {xi, X2xk} - множество независимых параметров (аргументов) числом К;

N+1 - число членов обобщенного полинома;

- к i

fn (X) - П Х|| IJ - функция, задающая вид

J 1 1-го члена обобщенного полинома;

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

Недостатком данного устройства является относительно низкое быстродействие, так как время, требуемое для вычисления обобщенного показателя Y, пропорционально числу К параметров X.

Цель изобретения - повышение быстродействия устройства за счет распараллеливания процесса вычисления полинома вида. Поставленная цель достигается тем, что в устройство, содержащее генератор импульсов, первый блок вычисления двумерного полинома, который содержит счет- чик количества аргументов, счетчик количества членов полинома, узел памяти аргументов, узел памяти показателей степени, узел памяти коэффициентов полинома, умножитель, первый элемент задержки, накапливающий сумматор и узел возведения в степень дополнительно введены с второго по М-й блоки вычисления двумерных полиномов, где М - количество сочетаний из количества аргументов исходного многомерного полинома по два, блок вычисления среднего и элемент И, выход которого соединен с входом останова генератора импульсов, вход запуска которого соединен с входом пуска устройства, выход результата которого соединен с выходом блока вычисления среднего, причем каждый блок вычисления двумерного полинома дополнительно содержит ключ, с второго по четвертый элементы задержки, коммутатор И, группу элементов ИЛИ, четыре регистра, узел сравнения с нулем, узел сравнения с числом 2 и узел сравнения с числом Км+1, где Км - количество членов m-ro двумерного полинома, причем выход ключа соединен с счетным входом счетчика количества аргументов, выходы первого и второго разрядов которого соединены соответственно с первым и вторым адресными входами узла памяти показателей степени и соответственно с первым и вторым входами узла сравнения с числом два, выход которого соединен с входом первого элемента задержки, выход которого со- единен с входом установки счетчика количества аргументов и счетным входом счетчика количества членов полинома, выход которого соединен с входом узла сравнения с числом Км+1 и адресным входом узла памяти коэффициентов полинома и третьим адресным входом узла памяти показателей степени, выход которого соединен с входом узла сравнения с нулем и входом показателя узла возведения в степень, вход аргумента которого поразрядно соединен с выходами соответствующих элементов ИЛИ группы, первые и вторые входы

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

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

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

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

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

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

5 блоков вычисления двумерного полинома, выходы узлов сравнения с числом Км+1 которых соединены с соответствующими входами элементов И,

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

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

На фиг.1 представлена общая структурная схема устройства; на фиг.2 - функцио- нальная схема одного из блоков вычисления двумерных полиномов; на фиг.З - график зависимости Q от Y.

Устройство содержит генератор 1 импульсов, группу элементов И 2, блок вычис- ления среднего и М блоков вычисления двумерных полиномов, каждый из которых содержит счетчик 4 количества аргументов, счетчик 5 количества членов полинома, узел б памяти показателей степени, узел 5 памяти коэффициентов полинома, узел 8 возведения в степень, умножитель 9, накапливающий сумматор 10, первый регистр 11, второй регистр 12, третий регистр 13, четвертый регистр 14, коммутатор 15, блок 16 сравнения с числом 2, блок 17 сравнения с нулем, блок 18 сравнения с числом «м+1, первый элемент 19 задержки, второй элемент 20 задержки, третий элемент 21 задержки, четвертый элемент 22 задержки, узел 23 па- мяти аргументов, ключ 24, группу элементов ИЛИ 25.

В устройстве обобщенный многомерный полином (1) представляется в виде системы из М двумерных полиномов

Km

Ym X b m Vlm(xi. Xj), I о

j Гк,Ч j, т

где

К1

- число сочета

21() ний из К по 2;

Dim - весовой коэффициент;

$m (xi, j) xf e m xf -функция, задающая вид 1-го члена т-ro двумерного полинома;

aijm- показатель степени i-ro аргумента в 1-ом члене m-ro двумерного полинома;

Кт+1 - количество членов m-ro двумерного полинома.

Следовательно, при представлении полинома (1) в виде системы (2) предлагав- мое устройство может быть использовано для вычисления значений полиномов с числом аргументов К 3. Значение обобщенного многомерного полинома (1) определяется из

(2) в блоке вычисления среднего, реализующего вычисления по формуле

1

м

-W

(3)

Уравнения системы (2) определяются из полинома (1) путем следующего математического преобразования. Для преобразования (1) в заданное уравнение системы (2), соответствующее паре (xi, Xj), необходимо в исходную функцию (1) вместо аргументов х, кроме рассматриваемых (xi, xj), подставить их значения, соответствующие точке математического преобразования

X {Х1П, Х2ПXk }

Погрешность Q представления (1) в виде (2) и (3) для заданных значений аргументов определяется в виде

Q I

(4)

1520 2530

35

40

45

50

55

где Y - значение обобщенного многомерного полинома, определяемое по формулам (2)и(3);

Y - значение обобщенного многомерного полинома, определяемое по формуле (1).

Величина Q зависит от текущих значений X и Y. Значение Yn (фиг.З) соответствует точке математического преобразования Хп, использованной для получения системы уравнений (2). В системах контроля при организации процесса контроля по обобщенному показателю по измеренным значениям аргументов X определяется величина показателя Y для сравнения с заданной нормой (требуемым значением) YTp. По результатам сравнения делается вывод о готовности изделия, описываемого полиномом (1), в соответствии решающим правилом вида

Y УтрилиУ YTp.

Следовательно, в данном случае не требуется обеспечивать высокую точность выл числения значений полинома (1) на всем интервале возможных значений Y. Требуется с высокой точностью вычислять лишь граничные значения YTp. Следовательно, если точка Yn (фиг.З) соответствует требуемому граничному значению Yrp, то система (2) обеспечивает высокую достоверность разделения изделий на классы годных и не годных в соответствии с указанным решающим правилом.

Таким образом, узел 7 памяти представляет собой память на (Км+1) регистре, узел 23 памяти аргументов - память на двух регистрах, узел 6 памяти - двухадресную память, содержащую (Км+1) строку по два регистра в каждый. Разрядность счетчика 5 определяется величиной (Км+1); счетчик 4 - двух разрядный.

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

В исходном состоянии счетчик 4 и накапливающий сумматор 10 обнулены, в счетчик 5 занесена-единица. В узел 7 памяти занесены коэффициенты двумерных полиномов (2) bim, которые вычисляются для заданного полинома (1) путем описанного математического преобразования по значениям Хп, соответствующим заданной величине YT, в узел 23 памяти - значения аргументов xi, xj. В каждый i-й регистр 1-й строки узла б памяти занесены показатели степени а i;m 0 ®Мм, i 1.2). На управляющем входе ключа 24 - нуль.

По сигналу Пуск запускается генератор 1 импульсов, первый импульс которого поступает через ключ 24 на вход счетчика 4 количества аргументов, начиная тем самым этап вычисления первого члена двумерного полинома. При записи в счетчик 4 единицы, единица появляется на его первом входе и поступает на первый вход узла 6 памяти показателей степени и на первый вход узла 23 памяти аргументов. При этом из узла 6 памяти показателей степени извлекается значение показателя степени первого аргумента двумерного полинома и поступает на первый вход блока 8 возведения в степень, а также на вход схемы 17 сравнения, где осуществляется сравнение a ijtn с нулем. Если значение поступившего числа не равно нулю, то на выходе схемы 17 сравнения появляется нуль, не влияющий на прохождение первого аргумента xi из блока 23 памяти аргументов через группу 25 элементов ИЛИ на второй вход блока 8 возведения в степень при любом, пусть даже нулевом значении аргумента xi. Тем самым устраняется возможность появления в блоке 8 возведения в степень неопределенности вида 0° в случае одновременного равенства нулю и основания и показателя степени.

Результат возведения в степень поступает на коммутатор 15, который после прихода на его первый управляющий вход единицы с выхода счетчика 4 разрешает прохождение этого результата на вход второго регистра 12, и в момент прихода задержанного импульса с выхода второго элемента 20 задержки ре- зу%тат записывается в данный регистр. В

первый регистр 11 записывается значение первого коэффициента двумерного полинома bim, которое извлекается из узла 7 памяти коэффициентов полинома в момент установления счетчика 5 количества членов полинома в исходное состояние (запись единицы).

Второй тактовый импульс с выхода генератора 1 импульсов через ключ 25 посту0 пает на вход счетчика количества аргументов, в результате чего уже описанным выше образом происходит формирование сомножителя , который с второго выхода коммутатора 15 поступает на вход

5 третьего регистра 13 и записывается в данный регистр в момент прихода импульса с первого выхода четвертого элемента 22 задержки. В момент прихода импульса с второго выхода четвертого элемента 22

0 задержки происходит перемножение на умножителе 9 содержимого регистров 11-13 и запись результата в регистр 14, с выхода которого данный результат поступает на вход накапливающего сумматора 10 и зано5 сится в него с приходом импульса с третьего выхода элемента 22 задержки, поступающего на его управляющий вход.

Как только содержимое счетчика 4 количества аргументов превысит значение 2,

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

поступает на вход обнуления счетчика 4 и на вход счетчика 5 количества членов полинома, добавляя к его содержимому, единицу.

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

Как только содержимое счетчика 5 превысит значение (Км+1), на выходе схемы 18 сравнения появляется единица, которая поступает на управляющий вход ключа 24, за5 прещая тем самым прохождение тактовых импульсов с генератора 1 на вход счетчика 4 и прекращая процесс вычислений в данном пл-м блоке вычисления двумерных полиномов. Кроме того, единица с выхода

0 схемы 18 сравнения поступает на один из входов группы 2 элементов И. Как только все М-блоков вычисления двумерных полиномов завершат вычисления, на всех входах группы 2 элементов И будет единица и еди5 ничным сигналом с выхода группы 2 элементов И обеспечивается останов генератора 1 импульсов, установка в исходное состояние счетчика 5 количества членов полинома, обнуление ч ерез третий элемент 21 задержки накапливающего сумматора в каждом т-м

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

Результаты теоретических расчетов и математического моделирования подтвердили работоспособность предлагаемого устройства и показали, что создано устройство для вычисления значений многомерных обобщенных полиномов (1) по формулам (2) и (3) при работе с действительными числами. Устройство предназначено для вычисления значений многомерных полиномов (с числом аргументов К 3).

Результаты математического моделирования показали, что предлагаемое устройство позволяет решать задачу вычисления значений многомерных полиномов (с числом аргументов К 3) с более высоким быстродействием, чем известное устройство. Причем разница в быстродействии тем выше, чем больше число К аргументов полинома. Время вычислений с помощью предлагаемого устройства практически не зависит от числа аргументов полинома и приблизительно равно времени вычисления двумерного полинома. Вместе с тем, как показали результаты моделирования, минимальное значение погрешности Q, определяемое согласно (4) и соответствующее точке, использованной для преобразования (1) в (2), настолько мало, что в случае совпадения Yn YTp контроль обеспечивается с достоверностью, практически равной 1.

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

0 членов m-ro двумерного полинома), причем выход ключа соединен со счетным входом счетчика количества аргументов, выходы первого и второго разрядов которого соединены соответственно с первым и вторым

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

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

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

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

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

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

с числом Кщ+1 соединен с управляющим входом ключа, информационный вход которого соединен с выходом генератора импульсов, вход останова которого соединен с

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

Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах контроля, работающих в реальном масштабе времени. С целью повышения быстродействия за счет распараллеливания процесса вычислений в него введены генератор импульсов, М блоков вычисления двумерных полиномов, блок вычисления среднего, элемент И, причем значение М определяется числом сочетаний из количества аргументов исходного многомерного полинома по два. Устройство обес- печивзет возможность вычисления значений многомерных полиномов. Распараллеливание процесса вычислений, за счет которого и достигается повышение быстродействие, обеспечивается тем, что в данном устройстве обобщенный многомерный полином представляется в виде системы из М двумерных полиномов, вычисление которых производится независимо друг от друга. Полученные в результате этого М значений двумерных полиномов суммируются и ос- редняются. 3 ил. 5 Ё

Фиг.1

Ymln. Yrnp Фиг 3

Y

Y