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

ЮЗ СОВЕТСКИХОЦИАЛИСТИЧЕСКИХ СПУБЛИК 1742829 А(9) 5)5 6 06 Р 15 ОСУДАРСТВЕННЫИ КОМИТЕТО ИЭОБРЕТЕНИЯМ И ОТКРЫТИЯМРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИ ной т авто рабо их батия чиво ие ых вЬ (Х) ВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССРМ 744559, кл. 0 06 Е 15/31, 1978,Авторское свидетельство СССРВ 962973, кл, 6 06 Е 15/31, 1981.(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯЗНАЧЕНИЙ МНОГОМЕРНОГО ПОЛИНОМА(57) Изобретение относится к вычислительной технике и может быть использовано вавтоматизированных системах контроля,работающих в реальном масштабе времени,С целью повышения быстродействия за счетраспараллеливания процесса вычислений в бретение относится к вычислитель- нике и может быть использовано в тизированных системах контроля, ющих в реальном масштабе времени. Известно решение подобных задач универсальных ЭВМ, При этом для каждо вида обобщенного полинома разрабаты ется своя программа вычислений, Кроме го, при использовании аппроксимирующ полиномов в системах контроля по "обо щенному показателю" требуется многокр ное обращение к подпрограмме вычислен значений полинома, Это приводит к зна тельному запаздыванию информации времени, что затрудняет использован ЭВМ для вычисления значений обобщенн полиномов в системах, работающих в реа иом масштабе времени,2него введены генератор импульсов, М блоков вычисления двумерных полиномов, блок вычисления среднего, элемент И, причем значение М определяется числом сочетаний из количества аргументов исходного многомерного полинома по два, Устройство обеспечивает возможность вычисления значений многомерных полиномов. Распараллеливание процесса вычислений, за счет которого и достигается повышение быстродействие, обеспечивается тем, что в данном устройстве обобщенный многомерный полином представляется в виде системы из М двумерных полиномов, вычисление которых производится независимо друг от друга. Полученные в результате этого М значений двумерных полиномов суммируются и осредняются. 3 ил. Известно устройство для вычисления значений многомерного (обобщенного) полинома, содержащее генератор импульсов, счетчик количества аргументов, счетчик ко- Я личества членов полинома, узел памяти ар- ф 3 гументов, узел памяти показателей степени, я узел памяти коэффициентов полинома, ум- р ножитель, элемент задержки, накапливающий сумматор, узел возведения в степень и соответствующие связи. Указанное устрой- й ство обеспечивает возможность вычисления значений обобщенных полиномов вида при работе с действительными аргументами коэффициентами, гдеХ - (х, хг, , хк) - множество независимых параметров (аргументов) числом К;И+1 - число членов обобщенного полинома;КЬ(Х)- П Х -функция, задающая вид1=11-го члена обобщенного полинома;а - показатель степени, с которой )-й аргумент входит в 1-й член обобщенного полинома.Недостатком данного устройства является относительно низкое быстродействие, так как время, требуемое для вычисления "обобщенного показателя У", .пропорционально числу К параметров Х.Цель изобретения - повышение быстродействия устройства за счет распараллеливания процесса вычисления полинома вида.Поставленная цель достигается тем, что в устройство, содержащее генератор импульсов, первый блок вычисления двумерного полинома, который содержит счетчик количества аргументов, счетчик количества членов полинома, узел памяти аргументов, узел памяти показателей степени, узел памяти коэффициентов полинома, умножитель, первый элемент задержки, накапливающий сумматор и узел возведения в степень дополнительно введены с второго по М-й блоки вычисления двумерных полиномов, где М - количество сочетаний иэ количества аргументов исходного многомерного полинома по два, блок вычисления среднего и элемент И, выход которого соединен с входом останова генератора импульсов,.вход запуска которого соединен с входом пуска устройства, выход результата которого соединен с выходом блока вычисления среднего, причем каждый блок вычис. ления двумерного полинома дополнительно содержит ключ, с второго по четвертый элементы задержки, коммутатор И, группу элементов ИЛИ, четыре регистра, узел сравнения с нулем, узел сравнения с числом 2 и узел сравнения с числом Км+1, где Км - количество членов в-го двумерного полинома, причем выход ключа соединен с счетным входом счетчика количества аргументов, выходы первого и второго разрядов которого соединены соответственно с первым и вторым адресными входами узла памяти показателей степени и соответственно с первым и вторым входами узла сравнения с числом два, выход которого соединен с входом первого элемента задержки, выход которого соединен с входом установки счетчика количества аргументов и счетным входом счетчика количества членов полинома, выход которого соединен с входом узла сравнения с числом Км+1 и адресным входомузла памяти коэффициентов полинома итретьим адресным входом узла памяти показателей степени, выход которого соеди 5 нен с входом узла сравнения с нулем ивходом показателя узла возведения в степень, вход аргумента которого поразрядносоединен с выходами соответствующих элементов ИЛИ группы, первые и вторые входы10 которых соединены соответственно с выходом узла сравнения с нулем и выходамисоответствующих разрядов узла памяти аргументов, первый адресный вход которогосоединен с первым управляющим входом15 коммутатора, вторым адресным входом узлапамяти показателей степени, выходом второго разряда счетчика количества аргументов, входом второго элемента задержки ивходом записи первого регистра, информа 20 ционный вход которого соединен с выходомузла памяти коэффициентов полинома, информационные входы второго и третьего регистров соединены соответственно спервым и вторым выходами коммутатора,25 информационный вход которого соединен свыходом узла возведения в степень, выходтретьего элемента задержки соединен с входом установки накапливающего сумматора,информационный вход которого соединен с30 выходом четвертого регистра, информационный вход которого соединен с выходом умножителя, входы сомножителей с первогопо третий которого соединены с выходамисоответствующих регистров, входы записи35 второго, третьего и четвертого регистров ивход синхронизации накапливающего сумматора соединены соответственно с выходомвторого элемента задержки и выходами с первого по третий четвертого элемента эадерж 40 ки, вход которого соединен с вторымуправляющим входом коммутатора, вторымадресным входом узла памяти аргументов ивыходом первого разряда счетчика количества аргументов, выход накапливающего45 сумматора каждого блока вычисления двумерного полинома соединен с соответствующим входом блока вычисления среднего,выход узла сравнения с числом Км+1 соединен с управляющим входом ключа, инфор 50 мационный вход которого соединен свыходом генератора импульсов, вход останова которого соединен с входами установки счетчиков количества членов полинома ивходами третьих элементов задержки всех55 блоков вычисления двумерного полинома,выходы узлов сравнения с числом Км+1 которых соединены с соответствующими входами элементов И,Положительный эффект в использовании предложенного технического решениязаключается в возможности распараллелить процесс вычисления многомерныхобобщенных .полиномов и достижения темсамым большего быстродействия, Существенными отличиями являются наличиедополнительно введенных указанных элементов исвязей между ними для достижения указанной совокупности признаков.На фиг.1 представлена общая структурная схема устройства; на фиг.2 - функциональная схема одного из блоков вычислениядвумерных полиномов; на фиг,З - графикзависимости 0 от У.Устройство содержит генератор 1 импульсов, группу элементов И 2, блок вычисления среднего и М блоков вычислениядвумерных полиномов, каждый из которыхсодержит счетчик 4 количества аргументов,счетчик 5 количества членов полинома, узел6 памяти показателей степени, узел 5 памяти 20коэффициентов полинома, узел 8 возведенияв степень, умножитель 9, накапливающийсумматор 10, первый регистр 11, второй регистр 12, третий регистр 13, четвертый регистр 14, коммутатор 15, блок 1 б сравнения с 25числом 2, блок 17 сравнения с нулем, блок.18 сравнения с числом Км+1, первый элемент 19 задержки, второй элемент 20 задержки, третий элемент 21 задержки,четвертый элемент 22 задержки, узел 23 памяти аргументов, ключ 24, группу элементовИЛИ 25,В устройстве обобщенный многомерный полином (1) представляется в виде системы из М двумерных полиномов .35 У =У .(3) Х" = (х 1", х 2"хк") 0=У-У.1,(4) кгпУ,=, Ьп 1 фь(хь х),) =13; Ф, а=1,М,(2) 45 УУтр илИ У Утр,Следовательно, в данном случае не требуется обеспечивать высокую точность выд 50 числения значений полинома (1) на всеминтервале возможных значений У, Требуется с высокой точностью вычислять лишь граничные значения Утр. Следовательно, если точка Уп (фиг,З) соответствует требуемому 55 граничному значению Утр, то система (2)обеспечивает высокую достоверность разделения изделий на классы годных и не годных в соответствии с указанным решающим правилом. К 1где М = С - 2- -2, - число сочегений из К по 2;Ьп - весовой коэффициент;е 4 гф (хь х) = х е 1 хЯв-функция, задающая вид 1-го члена а-го двумерного полинома;а 1; - показатель степени 1-го аргумента в 1-ом члене а-го двумерного полинома;Кп+1 - количество членов а-го двумерного полинома.Следовательно, при представлении полинома (1) в виде системы (2) предлагаемое устройство может быть использовано для вычисления значений полиномов с числом аргументов К3. Значение обобщенного многомерного полинома(1) определяется из(2) в блоке вычисления среднего, реализующего вычисления по формуле Уравнения системы (2) определяются иэ полинома (1) путем следующего математического преобразования. Для преобразования (1) в заданное уравнение системы (2), соответствующее паре (хь х), необходимо в исходную функцию (1) вместо аргументов (, кроме рассматриваемых (хь х), подставить их значения, соответствующие точке математического преобразования Погрешность 0 представления(1) в виде(2) и (3) для заданных значений аргументовГопределяется в виде где У - значение обобщенного многомерного полинома, определяемое по формулам (2) и (3);У - значение обобщенного многомерного полинома, определяемое по формуле (1),Величина 0 зависит от текущих значений Х и У. Значение У(фиг.З) соответствует точке математического преобразования Хп, использованной для получения системы уравнений (2). В системах контроля при организации процесса контроля по обобщенному показателю по измеренным значениям аргументов Х определяется величина показателя У для сравнения с заданной нормой (требуемым значением) Утр. По результатам сравнения делается вывод о готовности изделия, описываемого полиномом (1), в соответствии с решающим правилом видаТаким образом, узел 7 памяти представляет собой память на (Км+1) регистре, узел 23 памяти аргументов - память на двух регистрах, узел 6 памяти - двухадресную память, содержащую (Км+1) строку по два регистра в каждый. Разрядность счетчика 5 определяется величиной (Км+1); счетчик 4 - двухразрядный.устройство работает следующим образом.В исходном состоянии счетчик 4 и накапливающий сумматор 10 обнулены, в счетчик 5 занесенаединица: В узел 7 памяти занесены коэффициенты двумерных полиномов (2) Ьп, которые вычисляются для заданного полинома (1) путем описанного математического преобразования по значениям Хп, соответствующим заданной величине Уть в узел 23 памяти - значения аргументов х 1, х. В каждый 1-й регистр 1-й строки узла б памяти занесены показатели степени а 1; (1 = 0,5 Ъ, 1 = 1,2). На управляющем входе. ключа 24 - нуль,По сигналу "Пуск" запускается генератор 1 импульсов, первый импульс которого поступает через ключ 24 на вход счетчика 4 количества аргументов, начиная тем самым этап вычисления первого члена двумерного полинома. При записи в счетчик 4 единицы, единица появляется на его первом входе и поступает на первый вход узла б памяти показателей степени и на первый вход узла 23 памяти аргументов. При этом из узла б памяти показателей степени извлекается значение показателя степени первого аргумента двумерного полинома и поступает на первый вход блока 8 возведения в степень, а также на вход схемы 17 сравнения, где осуществляется сравнение а ;в с нулем. Если значение поступившего числа не равно нулю, то на выходе схемы 17 сравнения появляется нуль, не влияющий на прохожде,ние первого аргумента х из блока 23 памяти аргументов через группу 25 элементов ИЛИ на второй вход блока 8 возведения в степень при любом, пусть даже нулевом значении аргумента хь Тем самым устраняется возможность появления в блоке 8 возведения в степень неопределенности вида 0 в случае одновременного равенства нулю и основания и показателя степени.Результат возведения в степень поступает на коммутатор 15, который после прихода на его первый управляющий вход единицы с выхода счетчика 4 разрешает прохождение этого результата на вход второго регистра 12, и в момент прихода задержанного импульса с выхода второго элемента 20 задержки результат записывается в данный регистр, В первый регистр 11 записывается значение первого коэффициента двумерного полинома Ь 1 п, которое извлекается иэ узла.7 памяти коэффициентов полинома в момент уста новления счетчика 5 количества членов полинома в исходное состояние (запись единицы).Второй тактовый импульс с выхода генератора 1 импульсов через ключ 25 посту пает на вход счетчика количества.аргументов, в результате чего уже описанным выше образом происходит формирование сомножителя х"9 щ, который с второго выхода коммутатора 15 поступает на вход 15 третьего регистра 13 и записывается в данный регистр в момент прихода импульса с первого выхода четвертого элемента 22 задержки. В момент прихода импульса с второго выхода четвертого элемента 22 20 задержки происходит перемножение на умножителе 9 содержимого регистров 11-13 и запись результата в регистр 14, с выхода которого данный результат поступает на вход накапливающего сумматора 10 и зано сится в него с приходом импульса с третьеговыхода элемента 22 задержки, поступающего на его управляющий вход.Как только содержимое счетчика 4 количества аргументов превысит значение 2, 30 схема 17 сравнения вырабатывает импульс,который через первый элемент 19 задержки поступает на вход обнуления счетчика 4 и на вход счетчика 5 количества членов полинома, добавляя к его содержимому, единицу.35 После этого начинается вычисление второгочлена двумерного полинома. Значения всех членов двумерных полиномов последовательно накапливаются в сумматоре 10, производящем суммирование своего содер жимого с вновь поступившим членом.Как только содержимое счетчика 5 превысит значение (Км+1), на выходе схемы 18 сравнения появляется единица, которая поступает на управляющий вход ключа 24, за прещая тем самым прохождение тактовыхимпульсов с генератора 1 на вход счетчика 4 и прекращая процесс вычислений в данном гп-м блоке вычисления двумерных полиномов. Кроме того, единица с выхода 50 схемы 18 сравнения поступает на один извходов группы 2 элементов И. Как только все М-блоков вычисления двумерных полиномов завершат вычисления, на всех входах группы 2 элементов И будет единица и еди ничным сигналом с выхода группы 2 элементов И обеспечивается останов генератора 1 импульсов, установка в исходное состояние счетчика 5 количества членов полинома, обнуление через третий элемент 21 задержки накапливающего сумматора в каждом в-мФормула изобретенияУстройство для вычисления значений многомерного полинома, содержащее гене ратор импульсов, первый блок вычисления двумерного полинома, который содержит счетчик количества членов полинома, узел памяти аргументов, узел памяти показателей степени, узел памяти коэффициентов 45 полинома, умножитель, первый элемент задержки, накапливающий сумматор и узел возведения в степень, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия за счет распараллеливания процесса 50 вычисления, в него введены со второго по М-й блоки вычисления двумерных полиномов, где М - количество сочет аний из количества аргументов исходного многомерного полинома по два), блок вычисления средне го и элемент И, выход которого соединен с входом останова генератора импульсов, вход запуска которого соединен с входом . пуска устройства, выход результата котороблоке вычисления двумерных полиномов и включение в работу блока 3 вычисления среднего, в котором реализуется вычисление по формуле (3) среднего значения из значений двумерных полиномов. На этом заканчивается работа устройства.Результаты теоретических расчетов и математического моделирования подтвердили работоспособность предлагаемого устройства и показали, что создано устройство для вычисления значений многомерных обобщенных полиномов (1) по формулам (2) и (3) при работе с действительными числами, Устройство предназначено для вычисления значений многомерных полиномов (с числом аргументов К3),Результаты математического моделирования показали, что предлагаемое устройство позволяет решать задачу вычислениязначений многомерных полиномов (с числом аргументов К ) 3) с более высоким быстродействием, чем известное устройство. Причем разница в быстродействии тем выше, чем больше число К аргументов полинома, Время вычислений с помощью предлагаемого устройства практически не зависит от числа аргументов полинома и приблизительно равно времени вычисления двумерного полинома. Вместе с тем, какпоказали результаты моделирования, минимальное значение погрешности О, определяемое согласно (4) и соответствующееточке, использованной для преобразования (1) в (2), настолько мало, что в случае совпадения Уп = Ур контроль обеспечивается сдостоверностью, практически равной 1. 5101520 253035 го соединен с выходом блока вычисления среднего, причем каждый блок вычисления двумерного полинома дополнительно содержит ключ, с второго по четвертый элементы задержки, коммутатор, группу элементов ИЛИ, четыре регистра, счетчик количества аргументов, узел сравнения с нулем, узел сравнения с числом 2 и узел сравнения с числом К+1, (где Кп 1+1 - количество членов а-го двумерного полинома), причем выход ключа соединен со счетным входом счетчика количества аргументов, выходы первого и второго разрядов которого соединены соответственно с первым и вторым адресными входами узла показателей степени и соответственно с первым и вторым входами узла сравнения с числом два, выход которого соединен с входом первого элемента задержки, выход которого соединен с входом установки счетчика количества аргументов и счетным входом счетчика количества членов полинома, выход которого соединен с входом узла сравнения с числом К+1 и адресным входом узла памяти коэффициентов полинома и третьим адресным входом узла памяти показателей степени, выход которого соединен с входом узла сравнения с нулем и входом показателя узла возведения в степень, вход аргумента которого поразрядно соединен с выходами соответствующих элементов ИЛИ группы, первые и вторые входы которых соединены соответственно с выходом узла сравнения с нулем и выходами соответствующих разрядов узла памяти аргументов, первый адресный вход которого соединен с первым управляющим входом коммутатора, вторым адресным входом узла памяти показателей степени, выходом второго разряда счетчика количества аргументов, входом второго элемента задержки и входом записи первого регистра, информационный вход которого соединен с выходом узла памяти коэффициентов полинома, информационные входы второго и третьего регистров соединены соответственно с первым и вторым выходами коммутатора, информационный вход которого соединен с выходом узла возведения в степень, выход третьего элемента задержки соединен с входом установки накапливающего сумматора, информационный вход которого соединен с выходом четвертого регистра, информационный вход которого соединен с выходом умножителя, входы сомножителей и первого по третий которого соединены с выходами соответствующих регистров, входы записи второго, третьего, четвертого регистров и вход синхронизации накапливающего сумматора соединены соответственно с выходом второго элементазадержки, выходами с первого по третий четвертого элемента задержки, вход которого соединен с вторым управляющим входом коммутатора, вторым адресным входом узла памяти аргументов и выходом первого разряда счетчика количества аргументов, выход накапливающего сумматора каждого блока вычисления двумерного полинома соединены с соответствующим входом блока вычитания среднего, выход узла сравнения с числом Кв+1 соединен с управляющим входом ключа, информационный вход которого соединен с выходом генератора импульсов, вход останова которого соединен с 5 входами установки счетчиков количествачленов полинома и входами третьих элементов задержки всех блоков вычисления двумерного полинома, выходы узлов сравнения с числом К+1 которых соединены с соответ ствующими входами элемента И.льский комбинат "Патент", г. Ужгород, ул.Гагари изводственно-из Заказ 2286 Тираж Подписное . ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб 4/5