Линейный интерполятор Советский патент 1987 года по МПК G05B19/18 G05B19/4103 

129

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

1

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

Цель изобретения - повышение быстродействия интерполятора.

На фиг. 1 показан отрезок аппроксимируемой прямой в первой четверти квадранта и полученный на основе инверсии перемещений данного отрезка - соответствующий отрезок во второй четверти квадранта; на фиг. 2 - структурная схема предлагаемого линейного интерполятора; на фиг, 3 - отрезок аппроксимируемой прямой; на фиг, 4 - функциональная схема реализации блока управления; на фиг, 5 - граф-схема алгоритма функционировани блока управления; на фиг, 6 - функциональная схема реализации сумматора,

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

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

Для получения отрезка прямой с

а

углом наклона - необходимо проинвертировать последовательность приращений, соответствующих отрезку -г На14.

для первой четверти квадранта и в дальнейшем обеспечивается преобразование полученных перемещений для других областей посредством простых операций инверсии и коммутации, реализуемых в блоке управления в зависимости от сортношения приращений. Погрешность аппроксимации не превышает шага дискретизации, I з,п, ф-лы 6 ил,, 1 табл.

5

0

5

0

5

0

фиг, 2 показан пример получения от11

резка прямой с наклоном -- на основе

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

последних. Отрезку прямой с углом

4 наклона -- по ведомой координате

соответствует последовательность приращений 010001000100010, где 1 соответствует диагональному шагу. Инверсия приведенной последовательности (101110111011101) соответствует отрезку прямой с углом наклона

-, причем погрешности аппроксимации

указанных прямых совпадают.

Указанное свойство позволяет путем инверсии получать отрезки прямых во второй четверти квадранта по известным последовательностям приращений соответствующих прямых с первой четверти.

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

При интерполяции отрезка прямой единичными приращениями при (4Х|7 |ЛУ| используется оценочная функция: при и I j i/ О, перемещение по оси X и

.,j , Р Ц 0« еРе- мещение по X и U;,- + /|ilX( -fAYIj , т.е, выполняется диагональный шаг по ведомой координате. В ис3 12

ходном состоянии значение оценочной функции равно БП (большое приращение) ,

Во время интерполяции прямой в первой четверти квадранта вслед за перемещением по направлению, характеризуемому меньшей проекцией, т.е. выполнении диагонального щага, обязательно следует перемещение по направлению, характеризуемому больщей проекцией. Это объясняется тем, что после выполнения диагонального шага к значению оценочной функции прибавляется значение |1лХ1 - IdYII . Поскольку для рассматриваемого случая (первая четверть первого квадранта) 1/5X17/2 I4YI, очередное значение оценочной функции после выполнения диагонального шага всегда будет больше О, т.е. следуюш,им выполняется шаг по ведущей координате при отсутствии перемещения по ведомой координате. Таким образом, по ведомой координате возможны следующие сочетания шагов: 01, 10, 00, где 1 соответствует на- личию перемещения, а О отсутствию перемещения. Если очередное, значение оценочной функции положительное и выполняется условие U-. - 70, .то очередные два перемещения произ- водятся только по оси X. Если же имеет место условие U;. - 2- ЛУ О, то по ведомой координате возможно сочетание перемещений 10 или 01, причем при (Uj--2jdY|j / 4Y выполняет- ся перемещение 10, а при (Ujj -2|dYI| uY - перемещение 01.

Линейный интерполятор (фиг. 2) содержит первый 1 и второй 2 регистры координатных перемещений, коммута тор 3, первый 4 и второй 5 блоки совпадения, накопительный сумматор 6, блок 7 сравнения, вход 8 линейного интерполятора, блок 9 управления с выходами 10-20, вход 21 Пуск линей ного интерполятора, входы 22-26 блока управления.

Блок управления (фиг. 4) содержит триггер 27, узел 28 постоянной памяти, первый регистр 29, триггер 30, второй регистр 31, генератор 32 импульсов. Сумматор (фиг. 6) содержит первый 33 и второй 34 комбинационные сумматоры, регистр 35, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 36. Регистры координатных приращений 1 и 2 служат соответственно для хранения большего и меньшего приращения

144

координат, определяющего отрабатываемый отрезок прямой.

Большее приращение (БП) записывается в регистр 1 по входам, явля ющимся первыми входами устройства. Выход регистра 1 соединен со входами первого блока 4 сравнения, выход которого соединен с первыми входами накопительного сумматора 6, а управляющий вход - с первым выходом блока 9 управления. Меньшее приращение . (МП записывается в регистр 2 по входам, являющимся вторыми входами устройства. Вторые входы регистра 2 прира щения соединены с информационными выходами сумматора 6 приращения. Вход записи регистра 2 координатного приращения соединен с вторым выходом блока 9 управления. Вход регистра 2 соединен с первыми и вторыми входам коммутатора 3, управляющий вход которого соединен с первым выходом блока управления.

На первые входы коммутатора 3 подается значение, равное содержимому регистра 2 координатных приращений, а на вторые - удвоенное значение содержимого регистра 2. Последнее достигается монтажным соединением, для чего i-й выход регистра 2 координатных приращений соединяется с (i+1) входом коммутатора 3, а младший разряд коммутатора 3 заземляется.

Блок 7 сравнения обеспечивает сравнение модуля суммы, полученной в накопительном сумматоре 6, с содержимым второго регистра 2 координатных приращений, поступающих на входы блока 7 сравнения. При единичном значении знакового разряда, сумматора 6 и содержимом регистра 2 координатных приращений, большем модуля суммы, формируемой сумматором 6, на выходе блока 7 сравнения появляется уровень логической единицы. В противном случае - на выходе блока 7 сравнения формируется уровень логического нуля.

Триггер 27 устанавливается в состояние лог. единицы при БП /lY, и в состояние лог. нуля при .

Выходы 10-13 блока 9 управления являются выходами X интерполято-ра, и выходы 14-17 - выходами Y,

Отсутствие перемещения по соответствующей координате за время интерполяционного тока обозначено через О, а наличие - через 1, Уровень логической единицы на выходах

5 12

IО-17 блока 9 управления обозначает, двойные комбинированные перемещения По координате X По координате Y 10-0014-00

II-0115-01

12- 016-10

13- 117-11,

Блок 9 управления, анализируя значение знакового разряда сумматора 6 и выхода блока 7 сравнения, задает направление генерируемого двойного перемещения и характер следующей за ним арифметической операции по расчету очередного значения оценочной функции в соответствии с формулами: при U-- 7 О - перемешивание 00 по оси Y и

,Г bi - 2-dY;

при о И iU,-,j f I ,3 Y I - переме- щение О 1 по оси Y и

и,-,2, ,-./ и,- - 4Y + (aX-4Y);

Mj

при и,-5 О к iUi,,-l 7f //)Y/ - перемещение 10 по оси Y и

,ifi Uf,j -dY -b(dX - Л).

Перемещение по оси X производится в каждом интерполяционном такте.

Интерполятор работает следующем образом.

Модули проекций5 задающих отрезок прямой, записываются в регистр 1 (большее приращение БД) и регистр 2 (меньшее приращение МП). При этом в триггер 27 записывается логическая единица при БП и ноль при и Y БП.

По сигналу Пуск начинается процесс воспроизведения отрезка прямой. Модули проекций через коммутаторы 3 и блоки совпадения 5 и 4 подаются в сумматор 6 для проведения операции БП-МП, Б блоке 7 сравнения полученное значение БП-МП, хранящееся в на- копительном сумматоре 6, сравниваетс со значениями МП, При БП - МП /МП, что соответствует появлению логического нуля на выходе блока 7 сравнения, блок 9 управления на своем выхо де 18 формирует сигнал логического нуля, которьш не является активным сигналом записи в регистр 2. При БМ - WI МП значение разности пере- записываетёя в регистр 2. Этому слу- чаю соответствует формирование логических единиц на выходе блока 7 сравнения и выходе 18 блока 9 управления Условие БП - МП МП при йХ БП оп146

ределяет прршадлежность генерируе-- мого отрезка прямой к второй четверти первого квадранта,, Для обеспечени воспроизведения указанного вектора путем инверсии последовательности приращений по ведомой координате соответствующего вектора в первой четверти квадранта необходимо, чтобы последний имел следующие значения модулей проекций; лХ БП, dY БП- МП, что и обеспечено на первом подготовительном такте работы интерполятора. При этом блок 9 управления должен обеспечить в дальнейшем инвертирование последовательности приращений по ведомой координате. На этом заканчивается подготовительный зтап, предшествующий собственно процессу интерполяции. Причем сумматор 6 принимает значение содержимого регистра 1 после выполнения подготовительных операций, . UQ БП. I

Поскольку эквивалентными трансформациями с учетом соответствующих признаков интерполяция сводится к генерации отрезков прямых в первой четверти первого квадранта, то процесс получения выходных последовательностей интерполятора по значениям входных приращений рассматривается только для указанной области, для которой ЛХ БП, Y МП, 2AY ЛХ.

В цикле интерполяции в первом такте в сумматоре 6 производится вычисление разности UQ - 2 Y, что обеспечивается формированием логических единиц на выходах 19 и 20 блока 9 управления, а также подачей логической единицы на вход сумматора 6. Блоком 7 сравнения проводится сопоставление полученного модуля оценочной, функции, хранящегося в сумматоре 6, с модулем МП, храняшлмся в регистре 2 координатных приращений. Блок 9 управления в зависимости от значения знакового разряда сумматора 6, формируемого на его выходе, уровней сигналовр поступаюших с выхода блока 7 сравнения, и значения сигнала, поступающего с выхода триггера 27, формирует выходные сигналы, соответствующие двойным перемещениям по обоим направлениям. В зависимости от значения знакового разряда сумматора 6 формируется новое значение оценочной функции, определяющей очередные двойные перемещения. При положительном значении модуля оценочной функции ее новое значение оп7 1

ределяется согласно выражению U;. U; - 2aY, а при отрицательном - Согласно выражению Uj-dY+UX- -4Y).

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

Up 7 - перемещение отсутствует, 2/jY 6, БП

и 7-6 10- перемещение 00 по ведомой координате (вых. 14, вых. 13);

и 1-6. -5, |U;|7 4Y - перемещение 10 по ведомой координате (вых. 16, вых. 13);

Vj -5-3 + (7-3) -4, IU3l74Y - перемещение 10 по ведомой координа- те (вых. 16, вых. 13);

U4 -4-3 + (7-3) -3, |U4l 4Y - перемещение 10 по ведомой координате (вых. 16, вых. 13).

Блок 9 управления может быть син- тезирован различными известйыми методами.

В исходном состоянии регистры 29 и 30, а также триггер 30 обнулены. По сигналу Пуск начинает работу генератор 32 импульсов. Дпя обеспечения принципа единой временной организации синхронизация регистров 23 и 31 осуществляется от различных фронтов. С каждым тактовым импульсом из узла 28 постоянной памяти обеспечивается выборка управляющего сигнала по адресу, хранящемуся в регистре 31 и определяемому входными сигналами 22,23,27 блока и состоянием триг- гера 30. Управляющее слово записыва А

ется в регистр 29. Нулевой уровень сигнала Пуск определяет окончание процесса интерполяции и устанавливает в ноль триггер 30 и регистр 31

Схема алгоритма функционирования блока 9 управления приведена на фиг. 4. Содержимое узла 28 постоянной памяти блока 9 управления, сое- тавленное в соответствии с алгоритмом функционирования, приведено в таблице. Таблица приведена только для случая dX Л Y, где 5 X, AY - проекции приращений аппроксимируемого отрезка соответственно на оси X и Y Случаю ДХ 4Y соответствует значение О в колонке, определяющей старший разряд адреса адресного прост4 8

ранства ПЗУ, поскольку значение сигнала на входе 23 - нулевое. Случаю dY dX соответствует 1 в указанной колонке. Таблица, определяющая содержимое узла постоянной памяти для данного случая, соверщенно аналогична приведенной, за исключением разрядов, определяющих выходные сигналы. Значение указанных разрядов получают путем взаимной перестановки колонок Q1 - Q4 и колонок Q5-Q8 в таблице, т.е. обеспечивается взаимная перекоммутация выходных сигналов с координат X на Y,

Накопительный сумматор 6 работает следующим образом.

В каждый момент времени на информационный вход регистра 35 подается значение, равное сумме операндов, поступающих от блоков 4 и 5, а также с выхода регистра 35. При появлении переднего фронта на входе 24 сумматора значение суммы подается на выход регистра и при нулевом значении знакового разряда - на выход блока. При единичном значении знакового разряда блок 36 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ обеспечивает инвертирование значения суммы, поступающей с выхода регистра 35, т.е.обеспечивается выдача модуля суммы.

Погрещность аппроксимации не пре- выщает щага дискретизации.

Быстродействие приведенного линейного интерполятора превьппает быстродействие известного устройства в 2 раза.

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

Кроме того, в Нем достигается воспроизведение прямых с углом накло- .на 45° с максимальной точностью (погрешность аппроксимации равна 0), в то время как в известном устройстве этого достичь нельзя.

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

1. Линейный интерполятор, содержащий первый и .второй регистры, первый и второй блоки совпадения, выходы которых подключены к первому и второму входам сумматора соответственно.

912

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

10

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

1 8 д 10 11 12 /3 -7 5 X Фиг. 1

Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах программного управления станками и графических устройствах ввода - вывода цифровых вычислительных машин. Цель изобретения - повьш1ение быстродействия интерполятора. Линейный интерполятор содержит регистры 1)2, коммутатор 3, блоки совпадения 4,5, сумматор 6, блок сравнения 7, блок управления 9. В данном линейном интерполяторе существенным отличием является определение по диску и модулю оценочной функции очередного Mf7 а Ё (Л Ю)П2и Пуск П15№П Фиг.2

Фиг.З

Z8

29

Ф1лг.Ц