Целочисленные алгоритмы цифровой интерполяции криволинейных траекторий

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

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Вороновский Г.К. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Харьков: Основа, 1997.

2. Медведев В.С., Потемкин В.Г. Нейронные сети. MATLAB 6. -М: Д-М, 2002.

3. Сегерлинд Л. Применение метода конечных элементов. -М.: Мир, 1979.

4. Терехов В.А. Нейросетевые системы управления. -М.: Высш. школа, 2002.

Н.С. Анишин, И.Н. Булатникова

ЦЕЛОЧИСЛЕННЫЕ АЛГОРИТМЫ ЦИФРОВОЙ ИНТЕРПОЛЯЦИИ КРИВОЛИНЕЙНЫХ ТРАЕКТОРИЙ

В системах числового позиционного управления, использующих исполнительные устройства шагового типа (шаговые двигатели, счётчики импульсов с выходом на ЦАП, интеграторы электрических импульсов и т. п.) часто возникает задача формирования траектории рабочего органа по заданным параметрам.

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

Область применения цифровых интерполяций - станки с программным управлением, манипуляторы, координатные столы, графопостроители, дисплеи и т. п. Ранее они выполнялись аппаратными средствами [1,2].

Эволюция их развития привела к появлению оптимальных (в смысле точности и быстродействия) алгоритмов линейной и круговой цифровой интерполяции [3,4].

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

А ориентация на быстродействие и точность привела к необходимости, чтобы алгоритмы были ещё и целочисленными (т. е. без операций умножения и деления) и ориентированными на RISK - архитектуру используемых микропроцессоров.

Для этой цели нами был обобщён оптимальный алгоритм линейной цифровой интерполяции на случай интерполяции произвольной плоской кривой.

Идея такого обобщения состоит в применении алгоритма цифровой линейной интерполяции к касательной, проведённой к кривой в данном

F(x,y) = у ДХ — X •ДY корректируется не только в зависимости от типа сделанного шага (координатного или диагонального), но и из-за изменения крутизны касательной в новом узле интерполяции.

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

В качестве входных параметров этого алгоритма ДХ и ДY (таких, что ДX/ДY равно угловому коэффициенту касательной к кривой в текущем узле) используем следующие величины:

а) для случая явного задания функции

Д Y = т[к • f'

б) для случая неявного задания функции Г(х,у)=0

ДY = ±т[к • /ЭР /Эх/ + 0,5]1п ,

ДХ = +т[к • / ЭР/ Эу/ + 0,5];п1, ;

в) для случая параметрического задания функции х=

ДУ = т[к • dф(t)/dt + 0,5];п1,

ДХ = т[к • dф

где т - коэффициент {1, -1}, учитывающий направление обхода кривой, к - масштаби-

рующий коэффициент 2П (п £ N), выбираемый из соображений удобства умножения путём сдвига и допустимой ошибки округления величин до целого.

Как и в случае линейной интерполяции, для каждого 1-го узла интерполяции вводится оценочная функция Е; = Р(Х;,У;) в форме

где ДХ1 и ДY1 - значения ДХ и ДY в 1 - м (текущем) узле с координатами х1, у1; 1=0, 1, 2, 3 ... - номер узла.

В предлагаемом алгоритме направление и тип (координатный или диагональный) перемещения определяются также по знаку оценочной функции Е1 в виде

|Э; (х)| = |Э ;(у) = 1 в остальных случаях.

Однако, как уже сообщалось выше, в обобщённом алгоритме Е1 корректируется не только из-за возможного отхода (или приближения) от кривой при Э ¡(х) = 1 в виде

Е; =

¡=1

Е; — 2ДУ; |, если Э; (у ) = 0,

Е; + 2

но и из-за возможного изменения крутизны кривой вблизи 1-го узла интерполяции в виде

Тогда правила выбора направления и типа шага таковы:

Xj+1 = Xj + signAXj,yj+1 = Yj, если 13j >0,

иначе xi+1 = xi + sign AXi,yi+1 = yi + sign AYi

б) для случая |AX^ < |AYi | имеем

xi+1 = xi + signAXi,yi+1 = yi + signAYi; если Ei >0,

иначе xi+i = xi,yi+i = yi + sign AYi

Объединяя корректировки по (5) и (6), имеем корректировку после выполнения очередного шага:

E i+1 = Ei + |AXi+1 - 2| AYi+1 - |AXi | • signEi;

E i+1 = Ei + 2| AXi+1 - |AYi+1 - |AYi | • signEi •

И, напоследок, изредка делается ещё одна корректировка из-за смены аналитического выражения целевой функции (4), которая такова:

Ei +1 + (|AXi +1| + |AYi +11); случай (а),

Ei +1 - (|AXi +1| + |AYi +11); случай (б) ,

Ei+1;случай

Случай (а): при переходе от |AX^ > |AYi | к |AXi+1 < |AYi+1.

Случай (б): при переходе от |AX^ < |AYi | к |AXi +11 > |AYi +1

Случай (в): в остальных случаях.

Заметим, что начальное значение Е0 по формулам (4) при i=0 (координаты начальной точки интерполяции), а х0 и у0 - равны координатам начального узла интерполяции.

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

Другой путь для повышения точности интерполяции использовать уточнённые формулы (1 - 3) для определения AX и AY, учитывая среднее значение производных на интервале, равном шагу интерполяции.

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

E

i +1

Последнее рекомендуется при интерполяции отрезков кривых синусоиды - косинусоиды, эллипса, циклоиды и др.

Однако более важно применение данного целочисленного алгоритма цифровой интерполяции при графоаналитическом моделировании сложных кинематических систем (например, манипуляционных роботов со многими степенями свободы).

Это даёт большие перспективы применения при автоматизации пространственных устройств со многими силовыми приводами по каждой координате, так называемой «электронной кинематики» [5].

Конкретные примеры применения обобщённого алгоритма цифровой интерполяции разработаны в Академии маркетинга и социально-информационных технологий (г.Краснодар) и приведены в [6, 7].

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Агурский М. С. и др. Числовое программное управления станками. -М.: Машгиз, 1966. С. 144149.

2. Способы подготовки программ и интерполяторы для контурных систем программного управления станками. -М.: Машгиз. 1970. С. 52 - 57

3. Анишин Н. С., Тивков А. М. Оптимальный алгоритм цифровой линейной интерполяции. Изв. вузов. Приборостроение. 1983. №8. С. 56 - 59.

4. Анишин Н. С. и др. Оптимальный алгоритм цифровой круговой интерполяции. Изв. вузов. Приборостроение. 1983. №6. С. 44- 50.

5. Платонов А. К. Проблемы разработки микропроцессорных средств для управления роботами. Микропроцессорные средства и системы. 1984. №1. С. 22 - 27.

6. Анишин Н. С. Цифровые интерполяторы криволинейных траекторий. Автоматика и телемеханика. 1986. №12. С.95 - 101

7. Анишин Н. С. и др. Целочисленные алгоритмы вычисления интеграла вероятностей//Сборник докладов на международной научной конференции «СуперЭВМ и многопроцессорные вычислительные системы (МВС - 2002)». Таганрог, 2002. С. 148 - 152.

М.И.Ледовской

ОБРАБОТКА ВЕЩЕСТВЕННЫХ ДАННЫХ В МИКРОКОНТРОЛЛЕРАХ С АРИФМЕТИКОЙ ФИКСИРОВАННОЙ ТОЧКИ

Современные микропроцессоры и микроконтроллеры позволяют производить математические вычисления над вещественными переменными в двух режимах: с фиксированной и плавающей точкой. Данные режимы отличаются, прежде всего, формой представления двоичных чисел. В первом случае точка (запятая), разделяющая целую и дробную части числа, фиксируется в строго определенном месте. Например, в микроконтроллерах фирмы Motorola она фиксируется справа от числа (формат целых чисел), а у сигнальных процессоров - слева от числа (формат правильных дробей) [1]. Во втором случае двоичные числа представляются в экспоненциальной форме, поэтому положение точки в числе зависит от значения порядка.

Обработка вещественных данных в режиме фиксированной точки сопряжена с проблемой масштабирования всех величин, участвующих в вычислениях, и с получением масштабированных математических зависимостей. Эта проблема известна из исторического прошлого вычислительной техники [2].

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