Дифференцирующее устройство Советский патент 1991 года по МПК G06F7/64 

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

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

На фиг. 1 представлена структурная схема устройства; на фиг. 2 - структурная схема первого блока синхронизации; на фиг. 3 - структурная схема второго блока синхронизации.

Устройство (фиг. 1) содержит информационные входы 1, группу вычитателей 2, входы 3 задания шага, первую группу умножителей 4, входы 5 первого коэффициента, вторую группу умножителей 6. группу сум- маторов 7, группу регистров 8, первый мультиплексор 9, первый и второй сумматоры 10 и 11, первый и второй вычитатели 12 и 13, дешифратор 14, первый и второй умножители 15 и 16, входы 17 второго коэффициента, третий вычитатель 18, третий сумматор 19, входы 20 третьего коэффициента, четвертый - седьмой сумматоры 21-24, второй и третий мультиплексоры 25 и 26, первый счетчик 27, элемент ИЛИ 28, второй и третий счет- чики 29 и 30, первый и второй блоки синхронизации 31 и 32.

Первый блок синхронизации (фиг. 2) содержит вход 33, триггер 34, генератор 35, элемент И 36, счетчик 37 и дешифратор 38. Второй блок синхронизации содержит триггер 39, генератор 40, элемент И 41, счетчик 42, дешифратор 43.

При решении ряда технических задач (например, построении программных движений станков с ЧПУ и роботов при обработке лопаток авиационных двигателей) требуется решать задачу интерполяции, которая заключается в определении функции у f(x), принимающей в заданных узловых точках xi X2... xn+i заданные узловые значения fi, hfn+1.

Хорошее качество интерполяции обеспечивает выбор функции у f(x) в виде эр- митового сплайна третьей степени.

При таком выборе функция у f(x) будет иметь непрерывную производную.

Эрмитовый сплайн f(x) с узловыми точками xi, X2Хп-м и узловыми значениями fi,

f2fn-n можно на отрезке xi, xi+i задать в

виде

f(x) p (t)fi + (pi (t)f,-n (t )f i hi +

+ 974 (t)hifVi

pi W (1 t)2 (1 н 2t)

pl (t) t (3 - 7t) y (t) t(1 - i}2 p4(T) -t2(1- t)

(1)

hi XI-H - xi, t

x - xi hi

Величины fi , f 2 . .,f n+i выбираются произвольно и совпадают с производными

f (Xi), f(X2)f(xn+l).

При построении эрмитово о сплайна f(x)

по формуле (1) производные f 1 , f 2f n+i

являются параметрами, выбор которых позволяет удовлетворить дополнительным требованиям, касающимся формы кривой у f(x). Одним из таких требований является выпуклость (например, при обработке поверхности лопатки).

Предположим, что величины xi, ..,хп+1 и fifn+1 образуют выпуклую систему исходных данных. Пусть

дг fl+1-fl.

Af|-йг

где I 1n, hi XI-H -- xi. Предполагается,

что Afi+i Af, где i 1n-1. Геометрически выполнение этих неравенств означает, что кусочно-линейная функция, принимающая значение yi в точке xi, является выпуклой функцией. Опишем алгоритм выбора скоростей f i f n+i. обеспечивающих выпуклость интерполяционного сплайна f(x). Этот алгоритм сводится к решению системы из 2 n-линейных неравенств.

Функция f(x) является выпуклой, если f(x) 0 при всех xi х Х2. Однако на отрезке xi, XI-M эрмитовый сплайн является многочленом третьей степени. Поэтому на этом отрезке его вторая производная f (х) является линейной функцией. Отсюда следует, что для выпуклости эрмитового сплайна f(x) необходимо и достаточно, чтобы

f(xi + 0) 0

Г(хн.1-0)0(2)

где I 1n.

Используя предст вление (1), систему неравенств (2) можно переписать D зиде

2f i + fi+i ai )

fi + 2fVi ai Г(3)

где ai 3Afi, I 1, .,n

Будем систему линейных неравенств (3) называть невырожденной, если в области ее решений существует шар достаточно малого радиуса г

Пусть система (3) не вырождена а 0 I

-т. Тогда ее решение f 1 ,.. ,fn+i может

быть определено с помощью следующего алгоритма. Пусть

fi - A fi

Afi-i Ч-Af, - I - 2n(4)

f n-H A fn

начальное приближение к решению Днлее производные f 1 , ,f пи циклически по I 1,2, . ,п - 1 перевычисляются согласно следующим привалам

1°. Вычисляем С - Т - fVi Если С :Ј ai, то переходим к пункту 2° Если С п то f i уменьшаем на (а. С) 0.4 - 21 a f с . уменьшаем на (а С) 0 2 4 I и переходим к пункту 2°.

2° Вычисляем С - f i f 2f i-м Если С ai. то переходим к пункту 3° Если С ai, то f, увеличиваем на (a, C)-02 + 2I. a fVi увеличиваем на (а. С) 0,4 + 21 и переходим к пункту 3°

3°. Увеличиваем i на единицу Если i n + 1. то цикл пересчета производных

f i f n+i заканчивается Если i n то пе-

реходим к пункту 1°.

Описанный цикл пересчета производных f i f n+1 повторяем до тех пор, пока

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

Дифференцирующее устройство работает следующим образом. Перед началом работы производится установка в О всех триггеров и счетчиков устройства (цепи ус- тановки в О всех триггеров и счетчиков устройства не показаны). На входы 1 подаются значения функции fifn на входы 3 значения ,...,hn 1. на входы 5 - число 3, а на входы 17 - число 0,2, на входы 20 - число

I При подаче сигнала Пуск на вход 33 осуществляется запуск первого блока синхронизации 31 и установка в единичное состояние триггера 34 По первому синхроимпульсу БС 31 в вычитателях 2 вычисляются значения fin fi По второму синхроимпульсу в умножителях 4 вычисляются значения Afi(A fi i Д f()hi 1. no третьему - в умножителях 6 значения ai - 3 (Af| i -i- A fijhi а по четвертому - в сумматорах 7 суммирования значения f i (A fi -+ fi+i) После этого первый блок синхронизации блокируется сигналом с четвертого выхода дешифратора 38 и на его выходах сигналов не появляется

По этому же сигналу с четвертого выхода первого блока синхронизации запускается второй блок синхронизации. По первому синхросигналу с его выхода в регистры 8 записываются значения f i, а содержимое счетчика 27 увеличивается на 1 По второму синхроимпульсу на выходы мультиплексора 9 проходят значения f i fVi и а, где I - содержимое счетчика 27 По третьему синхроимпульсу в блоках 10 и 11 вычисляются ci1 2f i + f i-и и С21 fi 4 2f 1+1 . а по четвертому в блоках 12 и 13 значения а, - с/ и ai - С2 . При значениях знаковых р.-зрядов этих блоков 10 и 11 сигнал 1 на первом выходе дешифратора, при значениях 00 - на третьем Эти коды соответствуют следующим ситуациям при проверке неравенств (3) коды 10, 11 не выполняется первое неравенство системы (3) код 00 не выполняется второе неравенство 01 - оба неравенства выполняются

По пятому синхроимпульсу на одном из выходов дешифратора И появляется сигнал 1 Если сигнал 1 на первом выходе (не выполняется первое неравенство) то содержимое счетчика 27 уменьшается на 1. В блоке 15 умножения вычисляется значение 0,2 (а, - ci ) по шестому синхроимпульсу в блоке 13 - значение 0,2 (а( ci1) - I, а по седьмому в сумматорах 2 1 и 22 новые значения f, Г, + 0,4(а, - ci ) - 21 и fVi f i + i + 0,2(ai - ci1) - I. По девятому синхроимпульсу новые значения f i и f ,t 1 с выходов второго мультиплексора 25 пооходят на входы третьего мультиплексора 26 и переписываются в регистры 8 по первому синхроимпульсу блока 32, после чего цикл повторяется. Если сигнал 1 на втором выходе дешифратора 14, то в блоках 16, 29. 23, 24 по соответствующим синхроимпульсам вычисляются значения 0,2 (а, - С21) , затем 0,2 (ai - С21) + I и новые значения производных f i f i-м + + 0,2 (а, - С21) + I и f ,+i fVi + 0,4 (ai - С21) + 21, При появлении сигнала 1 на третьем выходе дешифратора 14 сбрасывается счетчик 42 второго блока синхронизации, что приводит к выдаче следующего импульса на первом выходе блока 33.

Таким образом, при невыполнении первого неравенства системы (3) в соответствующих регистрах 8 будут записаны новые значения f i и fVi после первого прохода. При этом происходит переполнение счетчи ка 42 и второй блок синхронизации следующий импульс сформирует на первом выходе, содержимое счетчика 27 станет равным прежнему I. При втором проходе первое не равенство системы (3) будет выполняться гарантированно, содержимое счетчика 27 вновь увеличивается на 1 Если не выполняется второе неравенство системы (3), то г блоках 16, 19, 23 и 24 перевычисляются новые значения f i и fVi, которые проходят на входы соответствующих регистров 8 При этом сигнал 1 на втором выходе дешифратора 14 и содержимое счетчика 27 вновь становится равным i При появлении 1 на третьем выходе дешифратора (выполнение обоих неравенств) системы (3) происходит сброс счетчика 43 и происходит переход к новому циклу вычислений.

Реверсивный счетчик 27 имеет коэффи циент счета п. После попарной проверки всех 2п неравенств (3) на выходе переполнения счетчика 27 появляется сигнал, по которому на единицу увеличивается содержимое счетчика 29, Коэффициент счета счетчика 29 устанавливается равным предельно допустимому числу прохода (как правило. при п 50число проходов не превышает 100). Если за это число проходов че удается обес печить выполнение условий (3), то на выходе переполнения счетчика 29 появляется сиг нал Останов, который свидетельствует о невозможности решения задачи. По этому сигналу сбрасывается триггер 39

Считывание результатов, удовлетворяющих условиям (3), с регистров 8 осуществляется по сигналу счетчика 29 с выхода переполнения счетчика 30, имеющею коэф фициент счета п. Содержимое счетчика 30 увеличивается на 1 при каждом появлении сигнала на третьем выходе дешифратора 14 и обнуляется при каждом появлении сигна ла на первом либо втором выходах дешиф ратора 14.

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

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

0 вычитателя группы и входом вычитателя (i - 1)-ro вычитателя группы, первый и (п + 1)-й информационные входы устройства соединены соответственно с входом вычитаемого первого вычитателя группы и

5 входом вычигател я л-ro р.ычитателя группы, выходы i-го (п - .п) вычитателя группы соединены с входами первого сомножителя 1-го умножителя первой группы, выходы которого соединены с входами первого сомножи0 теля 1-го умножителя второй группы, выходы которого соединены с информационными входами i-й группы первого мультиплексора, выходы первой группы которого соединены с входами первых слагаемых первого

S и второго сумматоров выходы которых соединены с входами уменьшаемого первого и второго вычитателей соответственно, входы вычитаемого которых подключены к выходам второй группы первого мультиплексо0 ра. а выходы соединены с входами первых сомножителей первого и второ( о умножителей соответственно, выходы которых соединены с входами вычитаемого третьего вычитателя и входами первого слагаемого

5 третьего сумматора входы i-й группы задания устройства (i 1 п) соединены с входами второго сомножителя i-ro умножителя первой группы, выходы i-го (i - 2,п-1) умножителя первой группы соединены с входами

0 первого слагаемого (i 1)-го сумматора группы и входами второго слагаемого i-го сумматора группы, выходы которого соединены с информационными входами i-ro регистра группы, выходы первого и n-го умножителей

5 первой группы соединены с информационными входами первого и (n -t 1)-го регистров группы, выходы 1-го регистра группы соединены с информационными выходами 1-й группы устройства (I - 1, п 1) и информаци0 онными входами (п ()й группы первого мультиплексора, выходы третьей группы которого соединены с входами второго слагаемого второго сумматора, входы первого коэффициента устройства подключены к

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

третьего вычитателя и второго слагаемого третьего сумматора, с первого по четвертый выходы первого блока синхронизации соединены с входами синхронизации вычитате- лей группы, умножителей первой группы, умножителей второй группы и сумматоров группы соответственно, кроме того, четвертый выход соединен с первым входом второго блока синхронизации, выходы знака первого и второго вычитателя соединены с первым и вторым входами соответственно дешифратора, первый вход которого соединен с вторым входом второго блока синхронизации, а второй и третий выходы соединены с входами запуска первого и второго умножителей соответственно, первым и вторым управляющими вводами ти. ого мультиплексооа соответственно и первь,м и вторым входами соответстпенно эл мента- ми ИЛИ, выход которого соединен с РХОДОМ блокировки первого счегчика, информационные выходы которого соединен;: с управляющими входами первого и трет его мультиплексоров, а выход переполнет ч .;о единен со счетным входом второго сче чи ка, выход переполнения которого соеди с выходом признака невозможности реи.з- ния устройства и третьим входом второю блока синхронизации, с первого по девятый выходы которого соединены с входами синхронизации регистров группы и счетным входом первого счетчика, входом синхронизации первого мультиплексора, входами синхронизации первого и второго суммато-

10

15

20

25

30

35

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

Изобретение относится к вычислительной технике и предназначено для вычисления производных по таблично заданным исходным данным при наложении дополнительных требований на вид функции, аппроксимирующей исходные данные. Цель изобретения - расширение функциональных возможностей за счет учета в вычислениях ограничений на вид восстанавливаемой функции. Устройство содержит входы 1, группу вычитателей 2, входы 3, группу умножителей 4, входы 5, группу умножителей 6, группу сумматоров 7, группу регистров 8, мультиплексор 9, сумматоры 10, 11, вычитатели 12, 13, дешифратор 14, умножители 15, 16, входы 17, вычитатель 18, сумматор 19, входы 20, сумматоры 21 - 24, мультиплексоры 25, 26, счетчик 27, элемент ИЛИ 28, счетчики 29, 30, блоки 31 и 32 синхронизации. 3 ил.

JJ

L/

I

Фиг. 2.

Фиг. 5