Устройство для вычисления значений многомерного полинома

 

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

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

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

РЕСПУБЛИК (sl)s G 06 F 15/31

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

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

ПРИ ГКНТ СССР

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

Y» g апЫХ) n=o

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

1 (21) 4819895/24 (22) 28.04.90 (46) 23.06.92. Бюл. М 23 (72) С.В.Кизима, В.И.Мороз и Н.Н.Шиенок (53) 681.325 (088.8) (56) Авторское свидетельство СССР

N- 744559, кл. G 06 F 15/31, 1978.

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

% 962973, кл, G 06 F 15/31, 1981. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

ЗНАЧЕНИЙ МНОГОМЕРНОГО ПОЛИНОМА (57) Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах контроля, работающих в реальном масштабе времени, С целью повышения быстродействия за счет распараллеливания процесса вычислений в

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

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

ЭВМ для вычисления значений обобщенных полиномов в системах, работающих в реальном масштабе времени, 5U 1742829 А1 него введены генератор импульсов, М блоков вычисления двумерных полиномов, блок вычисления среднего, элемент И, причем значение М определяется числом сочетаний из количества аргументов исходного многомерного полинома по два. Устройство обеспечивает возможность вычисления значений многомерных полиномов. Распараллеливание процесса вычислений, за счет которого и достигается повышение быстродействие, обеспечивается тем, что в данном устройстве обобщенный многомерный полином представляется в виде системы из M двумерных полиномов, вычисление которых производится независимо друг от друга.

Полученные в результате этого М значений двумерных полиномов суммируются и осредняются. 3 ил.

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

1742829

Х - (х1, хг, ..., х ) — множество независимых параметров (аргументов) числом К;

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

К .1 (Х)- П Х1 -функция, задающая вид !

=1

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

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

"обобщенного показателя Y", .пропорционально числу К параметров Х.

Цель изобретения — повышение быстродействия устройства за счет распараллеливания процесса вычисления полинома вида.

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

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

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

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

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

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

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

55 блоков вычисления двумерного полинома, выходы узлов сравнения с числом KM+1 которых соединены с соответствующими Входами элементов И, Положительный эффект в использовании предложенного технического решения

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

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

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

6 памяти показателей степени, узел 5 памяти 20 коэффициентов полинома, узел 8 возведения в степень, умножитель 9, накапливающий сумматор 10, первый регистр 11, второй регистр 12, третий регистр 13, четвертый регистр 14, коммутатор 15, блок 1б сравнения с 25 числом 2, блок 17 сравнения с нулем, блок.

18 сравнения с числом /M+1, первый элемент 19 задержки, второй элемент 20 задержки, третий элемент 21 задержки, четвертый элемент 22 задержки, узел 23 па- 30 мяти аргументов, ключ 24, группу элементов

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

Ф 1

Y = Ymm. (3) Xn (и п и) Q=! Y-Y*l, (4) Km

Ym =, blm.Jim(xl, х ), J=1,k;i WJ,m=1,М, (2) 45

Y Yzp или У Утр.

Следовательно, в данном случае не требуется обеспечивать высокую точность вы

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

Kl где M = С < — — @ — -2, — число сочегений из К по 2;

bum — весовой коэффициент; е. ф (хь xi) =.x i хЯ -функция, задающая вид 1-ro члена m-ro двумерного полинома; а ;„— показатель степени i-го аргумента в I-ом члене m-го двумерного полинома;

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

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

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

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

Гопределяется в виде где Y* — значение обобщенного многомерного полинома, определяемое по формулам (2) и (3);

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

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

По результатам сравнения делается вывод о готовности изделия, описываемого полиномом (1), в соответствии с решающим правилом вида

1742829.

Таким образом, узел 7 памяти представляет собой память на (Ку+1) регистре, узел

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

В исходном состоянии счетчик 4 и накапливающий сумматор 10 обнулены, в счетчик 5 занесенаединица: В узел 7 памяти занесены коэффициенты двумерных полиномов (2) blm, которые вычисляются для заданного полинома (1) путем описанного математического преобразования по значениям Хп, соответствующим заданной величине Y I, в узел 23 памяти — значения аргументов xI, х1. В каждый i-й регистр 1-й строки узла б памяти занесены показатели степени а ; (II = 0,5ц, 1 = 1,2). На управляющем входе. ключа 24 — нуль, По сигналу "Пуск" запускается генератор 1 импульсов, первый импульс которого поступает через ключ 24 на вход счетчика 4 количества аргументов, начиная тем самым этап вычисления первого члена двумерного полинома. При записи в счетчик 4 единицы, единица появляется íà его первом входе и поступает на первый вход узла б памяти показателей степени и на первый вход узла

23 памяти аргументов. При этом из узла 6 памяти показателей степени извлекается значение показателя степени первого аргумента двумерного полинома и поступает на первый вход блока 8 возведения в степень, а также на вход схемы 17 сравнения. где осуществляется сравнение а ; с нулем. Если значение поступившего числа не равно нулю, то на выходе схемы 17 сравнения появляется нуль, не влияющий на прохожде.ние первого аргумента х из блока 23 памяти аргументов через группу 25 элементов ИЛИ на второй вход блока 8 возведения в степень при любом, пусть даже нулевом значении аргумента х, Тем самым устраняется возможность появления в блоке 8 возведения в степень неопределенности вида О в случае одновременного равенства нулю и основания и показателя степени.

Результат возведения в степень поступает на коммутатор 15, который после прихода на его первый управляющий вход единицы с выхода счетчика 4 разрешает прохождение этого результата на вход второго регистра 12, и в момент прихода задержанного импульса с выхода второго элемента 20 задержки ðåзультат записывается в данный регистр, В первый регистр 11 записывается значение первого коэффициента двумерного полинома blm которое извлекается иэ узла.7 памяти коэффициентов полинома в момент уста5 новления счетчика 5 количества членов полинома в исходное состояние (запись единицы).

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

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

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

Как только содержимое счетчика 4 количества аргументов превысит значение 2, 30 схема 17 сравнения вырабатывает импульс, который через первый элемент 19 задержки поступает на вход обнуления счетчика 4 и на вход счетчика 5 количества членов полинома, добавляя к его содержимому, единицу.

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

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

4 и прекращая процесс вычислений в данном m-м блоке вычисления двумерных полиномов. Кроме того, единица с выхода

50 схемы 18 сравнения поступает на один из входов группы 2 элементов И. Как только все

M-блоков вычисления двумерных полиномов завершат вычисления, на всех входах группы 2 элементов И будет единица и еди55 ничным сигналом с выхода группы 2 элементов И обеспечивается останов генератора 1 импульсов, установка в исходное состояние счетчика 5 количества членов полинома, обнуление через третий элемент 21 задержки накапливающего сумматора в каждом m-м.9 1742829 10 блоке вычисления двумерных полиномов и включение в работу блока 3 вычисления среднего, в котором реализуется вычисление по формуле (3) среднего значения из значений двумерных полиномов. На этом заканчивается работа устройства.

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

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

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

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

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

М-й блоки вычисления двумерных nonwoмов, (где М вЂ” количество соче аний из количества аргументов исходного многомерного полинома по два), блок вычисления средне- 55

ro и элемент И, выход которого соединен с входом останова генератора импульсов, вход запуска которого соединен с входом . пуска устройства, выход результата котороro соединен с выходом блока вычисления среднего, причем каждый блок вычисления двумерного полинома дополнительно содержит ключ, с второго по четвертый элементы задержки, коммутатор, группу элементов ИЛИ, четыре регистра, счетчик . количества аргументов, узел сравнения с нулем, узел сравнения с числом 2 и узел сравнения с числом К +1, (где К +1 — количество членов m-ro двумерного полинома), причем выход ключа соединен со счетным входом счетчика количества аргументов, выходы первого и второго разрядов которого соединены соответственно с первым и вторым адресными входами узла показателей степени и соответственно с первым и вторым входами узла сравнения с числом два, выход которого соединен с входом первого элемента задержки, выход которого соединен с входом установки счетчика количества аргументов и счетным входом счетчика количества членов полинома, выход которого соединен с входом узла сравнения с числом

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

1742829

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

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

1742829

I

I

Составитель А.Зорин

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

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

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

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