Обработка по a и b для

Нет Да Нет Да

Fi£0 Fi£0

Fi+1=Fi+2 Fi+1=Fi+ Fi+1=Fi+ Fi+1=Fi-

2(ai+bi)+2 +2(ai-bi)+2 -2bi+1

Шаг по b bi+1=bi-1 ai+1=ai+1 Шаг по a

fi+1=fi-Vk/R fi+1=fi+Vk/R

ai+1=ai+1 Шаг по a bi+1=bi-1 Шаг по b

окончательного раннего кадра

движения УП

Конец

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

Достоинства: Простота реализации.

Недостаток: Vk (скорость) мала. Контурная скорость ограничена из-за необходимости отработки приводами элементарных приращений с частотой fi.

В современных ЧПУ – такие алгоритмы применяются редко (NC типа) – с жёсткой реализацией алгоритма и дискретными приводами с шаговыми двигателями.

Более широкое применение в СNC – типах систем находят методы интерполяции в кодовых приращениях (определяются Dхт и Dут, а в абстрактных Daт и Dbт) за время Tk – период квантования управляющих воздействий. Процедура их расчёта базируется на моделировании движений изображающей точки с оценочной функцией в ускоренном масштабе времени начиная с большего шага:

H0>>dz (по a и b) и заканчивается шагом.

Hm = dz, где k=0,1,2,...,m – номер шага.

1 этап: вычисление Daт, Dbт

2 этап: их выдача ai=ai+Daт

bi=bi+Dbт

Методы интерполяции «цифра за цифрой».

Здесь числа рассматриваются как композиции цифр с основанием q, зависящим от использования системы счисления. Для двоичных систем q=2.

В общем, виде x = å(liq-i)

i=1

число

где AiÎ{0,1,2,...,q-1}

Алгоритмы этих методов мы используют итерационную процедуру: U[k+1] = f{u[k]}, однократное применение которой даёт одну достоверную цифру результата, а n – кратное – n – верных результатов (цифр).

Такие методы появились в начале ХVII века.

а) Работы 2-х авторов Вагдер и Меджер.

Ими были разработаны алгоритмы для вычисления:

- элементов f(x) (показательных, прямых и обратных тригонометрических, логарифмических, гиперболических).

- множительн о – дели тель ные (х/y×z).

- корневые Ö хi× у, 3Öх/у...

- векторных преобразований.

Основные положения метода.

Если U(x) – заданная функция, X – аргумент.

U0(x) – известные начальные значения.

Иерархическая формула:

U[k+1] = U[k] + mix[k]

mi – скаляр (величина шага итерации).

x[k] = -1 направления движения

mix[k]=DU[k] – приращение.

При этом ½mi½ изменится в q – раз (например q=2) при получении очередной верной функции искомой функции.

Алгоритмы этих методов 2-х этапные.

а) На первом этапе формируются последовательные значения x[к]

x[1]®x[2]®...x[kmax]

Kmax зависит от разрядности представленных используемых чисел (x, u(x))

б) Строится итерационный процесс и определяется последовательность

x[1] x[1] n

U[0]= ¾¾ U[1]= ¾¾ ® u[kmax]

m[1] m[2] n

0 для разных

u0(x) = 1 U(x) свои случаи

C0 – некоторая константа

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

Примеры рекуррентных выражений для вычисленных функций sin j и cos j.

1 этап:

Qk+1=Qk - xkarctg (q -i)

табличное значение

xk = sign (Qk)

k=0,1,...kmax

Начальное условие: Q0=j0

Определяем знаки К-ые, Кmax – зависит от требуемой точности вычислений.

2 этап: yk+1=yk-xkxkq-i - для sin j

xk+1=xk+xkykq-i - для cos j

Начальное условие у0=0, х0=1/m

где m=1,646 – масштабный коэффициент.

При к=m ym = -sin j

Хm = cos j

Алгоритм круговой интерполяции по методу «цифра за цифрой» Меджита.

(q=2, замена переменной qi yi=zi)

x = R cos j; y = R sin j

Для 1 – го этапа:

Qi+1 = 2 × (Qi - xi × 2-i × arctg 2-i)

xi = sign Qi

1) *.

2) вычисление тригонометрических функций cos j, sin j.

___

где Q0=j0; i=0,n – где n – число достоверных разрядов.

Для 2-го этапа

Zi-1=2-1(Zi+xXi)

Xi-1=Xi - xi-12-2(i-1)×Zi

где i=n, n-1,... 0

Начало

Хn=R/M; j0, Dj j0=arctg(Iнач/Xнач)

i=0; Q0 Dj=VkTk/R

приращение угла

xi = sign Qi

И запоми - Да Нет

наем xi 4 xi<0 5

Qi+1=Qi+ Qi+1=Qi-

+2iarctg2-i -2iarctg2-i

Qi+1=Qi+1/2

.... Блок 1-7 результирует

i=i+1 1 этап алгоритма

Нет 7

i=n

Да

Да 8 Нет

xi<0

9 10

Zi-1=(Zi-Xi)/2 Zi-1=(Zi+Xi)/2

Да 11

I<n/2

Zc=Zi2-2(i-1)

Да 13 Нет

14 xi<0 15

Xi-1=Xi+Zc Xi-1=Xi-Zc

i = i-1 Блоки 8-17

реализуют

2 этап

17 алгоритма.

Нет

i = 0

Да

Конец

Назначение блока № 11: при i>n/2 Zc выходит за разрядную сетку, что позволяет сократить время счёта.

Межтактовые приращения вычисляются по значениям х0 и у0 для соответствующих шагов интерполяции.

Dхт[к]=х0[k-1]±x0[k]

Dyт[k]=y0[k-1]±y0[k]

где х0[k], x0[k-1], y0[k], y0[k-1] – вычисленные по приведённому выше алгоритму (на соседних шагах) верхние знаки («-» и «+») соответствуют движениям против часовой стрелки, нижним – по часовой.

Алгоритм линейной интерполяции по методу «цифра за цифрой» Меджита – аналогичен предыдущему, но:

а) в блоке № 1 хn = DL/M где DL=VkTk – приращение пути за Tk.

б) в блоках 4 и 5 таблицы констант заменяются на единичное значение arctg (yкон/xкон)

в) Вычисляем значения x0 и у0 являются приращениями констант за Tk.

Dx[k]=x0[k]; Dy[k]=y0[k]

Оценка требуемой разрядности n.

1) При линейной интерполяции.

а) DLmax=Vk max, max[inf Tk] = 10 м/c*0,01 c =0,1 м

inf – максимальное значение из минимального, т. е. inf Tk –нижняя граница Тk.

DLmax 0,1

Следовательно: ¾¾¾¾ = ¾¾ = 105, то есть 1666 бит < 211-1

min dz 10-6

или n=11.

2) При круговой интерполяции.

а) Rmax = 10 m

б) min dz = 10-6 m Þ Dj min = (min dz)/(Rмах)=10-6/10=10-7»2-24 или n=24

т. о. Rmax=224dz

Вывод: методы «цифра за цифрой» позволяют минимизировать временные затраты на реализацию алгоритмов с учётом типа интерполяции.

Время вычисления sin j (или cos j).

а) на К580» 6 мс

К1810» 1,5 мс.

Таблично – аналитические методы интерполяции (4-я группа).

Чисто табличные методы не применяются.

f(x)

2n – для указанных операций, n – разрядных операндов.

22n – для бинарных операций.

Объём ПЗУ в словах.

X ПЗУ f(x) – значение(двоичный код)

f(x)

адрес

(двоичный код)

Пример: R=10 м, dz=1 мкм

22n»1,7*106 – 24 разрядных слов Þ

требуется ПЗУ объёмом» 5,1*104 Кбайт = 51 МБ для хранения значений sin j c точностью dz.

Достоинства: Отсутствует накапливающееся погрешность. Упрощаются итерационные процедуры.

В качестве аппроксимирующей функции используют итерационные полиномы Лагранжа, Ньютона, а в зависимости от числа учитывающего табличные значения применяют линейную, параболическую, кубическую аппроксимацию.

Кусочно-линейная аппроксимация (интерполяция) по формуле Ньютона:

f(x) = f(xi)+(f(xi+1) - f(xi))/(xi+1-xi)×(x-xi) = f(xi+kix)

где f(xi); f(xi+1) – табличные значения.

xi+1-xi=Dxi – итог таблицы.

Шаг таблицы, конечно, оценивается требуемой погрешностью аппроксимации:

Dхi £ [d×½d2f(x)/dx2½при х=хi -1×dxа]1/2

где ½d2f(x)/dx2½-1- обратная величина модуля второй производной.

dxа – максимальное значение ошибки аппроксимации хÎ[хi, xi+1]

Для ф-й sin j и cos j при ½sin j½=½cos j½=1

___

Dj=Öd×dx - постоянный шаг в таблице (на апроксимации для табличных значений sin j и cos j).

.....

Так как½sin j½ = ½sin j½ ½sin j½max = 1

... Þ..

½ cos j½ = ½cos j½ ½cos j½max = 1

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

D хi+1 = xi+1 – хi = q-(n-r) =2-(n-r)

шаг по аргументу

где (n-r) – разрядность, кода старшей части аргумента xi (являющейся адресом, «грубые» значения функций в таблице ПЗУ).

Для таблицы sin j и cos j шаг:

Dj £ 2–(n-r)

Оценка объёма ПЗУ (пример). Если таблица содержит 25 – разрядные значения функции, то есть n = 25, a(n-r) = 12 разрядов адреса, тогда при R = 10 м и dz = 1 мкм для хранения опорных точек на дуге окружности первого квадранта требуется N = 3835 опорных точек, так как N = pR/4×R×arcsin(22dz/2/R) = pR/(2N+1×dz) – это отношение длины дуги (pR/2) к длине дуги, стягиваемой аппроксимированной хордой Þ объём ПЗУ Q = 2(N-1)*225 бит =

= 23963 байт = 24 кБ

Другой способ представления таблиц:

- не в абсолютных значениях sin j и cos j, а в приращениях их смежных значений:

Dхi = xi – xi-1= R(cos ji – cos ji-1) = R × Dcos j i

Dyi = yi – yi-1= R(sin ji – sin ji-1) = R × Dsin ji

Это позволяет вдвое уменьшить объём таблиц.

Вычисление поправок (к табличным значениям функции) – это типичная интерполяционная задача, которая может решаться любым

рассматриваемым ранее методом.

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

Обобщённая схема алгоритма линейно – круговой интерполяции таблица алгоритмического типа.