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

14

писи пятого счетчика, первый выход третьего триггера соединен с вторым входом пятого элемента И, а второй выход - с входами запрета счета первого и второго счетчиков импульсов, выход первого элемента ИЛИ соединен со счетным входом пятого счетчика импульсов, первые выходы пятого счетчика импульсов соединены с входами третьего дешифратора, первый выход которого соединен с первым входом седьмого элемента И, второй выход соединен с третьим входом первого .регистра, третий выход соединен С третьим входом второго регистра, а четвертый выход третьего дешифратор ра соединен с первьм входом двенадцатого элемента И, выход Шестого эле мента И соединен с вторыми входами седьмого и с первым входом восьмого элементов И, выход седьмого элемента И соединен с первым входом третье гр элемента ИЛИ,, выход второго элемента ИЛИ соединен с первым входом третьего триггера и через первый элемент задержки - с вторым входом третьего.элемента ИЛИ и с вторым входом пятого элемента И, выход которого соединен с четвертыми входами первого, второго регистров и с вторым входом двенадцатого элемента И, выход третьего элемента ИЛИ соединен с входом управления записью третьего счетчика импульсов, выход конца счета третьего счетчика .импульсов соединен с первым входом девятого элемента И и с третьим входом третьего регистра, первые выходы первого и второго дешифраторов соединены со- ответст венно с вторыми входами девятого и десятого элементов И, вторые выходы первого и второго дешифраторов соединены соответственна с вторым и третьим входами восьмого 3j;e- мента И, выход которого соединен с входами установки-в О первого и второго триггеров, выход девятого элемента И соединен с первыми входами первого и второго элементов 2И-ИЛИ и с входом управления счетом третьего счетчика импульсов, выход десятого элемента И соединен с вторыми входами первого и второго элементов 2И-ШШ и с ВХОДОМ управления счетом четвёртого счетчика импульсов

600 .

первый выход блока сравнения соединен с управляющими входами первого блока мультиплексоров и с третьими входами первого и второго элементов 2И-ИЛИ, второй выход блока сравнения соединен - с-управляюпщми входами вто рого блока мультиплексоров и с четвертыми входами первого и второго элементов 2И-ИЛИ, вторые выходы первого и второго регистров соединены с первым и вторым входами одиннад- . цатого элемента И соответственно, выходы одиннадцатого и двенадцатого элементов И соединены с входами четвертого элемента ИЛИ, .выход которого через третий элемент задержки соединен с пятыми входами третьего и четвертого счетчиков импульсов и с входами установки в О третьего,чет- . вертого и пятого триггеров, первого и второго счетчиков, выход четвертого триггера соединен с первым входом третьего элемента И и первым входом пятого триггера, выход пятого триггера соединен с первым входом четвертого элемента И и с первым входом четвертого триггера, вход интерполятора Вх.1 соединён со счетными входами первого и третьего счетчиков, вторыми входами четвертого триггера и четвертого элемента И, а также с вторым входом первого элемента ИЛИ,вход интерполятора Bx.j соединен со счетными входами второго и четверто- ,го счетчиков, с вторыми входами пято- I го триггера, третьего элемента И, а также с третьим входом первого элемента ИЛИ, вход интерполятора подключен к входу установки в 1 . первого триггера, к входам управления режимом параллельной записи третьего и четвертого счетчиков и к входу установки в исходное состояние пятого счетчика, входы знаковых разрядов ЗнД и 3H,J соединены с третьими входами четвертого элемента ИЛИ, выход второго элемента И подключен к второму входу десятого элемента И, причем выходами интерполятора в режиме интерполяции являются выходы элементов 2И-ИЛИ, в режиме ап- проксимации - выходы третьего и четвертого счетчиков и выход четвертого элемента ИЛИ.

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

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

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

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

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

Интерполятор (смофиг,) содержит первый 1 и второй 2 счетчики импуль- с;ов, блок 3 сравнения, первый 4 и второй 5 блоки мультиплексоров,.третий 6 и чет-вертый 7 счетчики импуль- сов, первый 8 и второй 9 дешифраторы.

блок 10 постоянной памяти, первый 11, второй 12 и третий 13 регистры, третий блок 14 мультиплексоров, пятый счетчик 15, третий дешифратор 16 генератор J7 тактовых импульсов, первый 18 и второй 19 триггеры, первый 20 и второй 21 элементы И, первый элемент ИЛИ 22, третий 23, четвертый 24 и пятый 25 триггеры, третий 26, четвертый 27 и пятый 28 элементы И, второй элемент ИЛИ 29, первый 30 и второй 31 элементы задержки, третий элемент ИЛИ 32, с шестого по десятый элементы И 3-3-37, первый 38 и второй 39 элементы 2И-ИЛИ (2-2И-2ИЛИ), одиннадцатый 40 и двенадцатый 41 элементы И, четвертый элемент ИЛИ 42 и третий элемент 43 задержки.

Счетчики 1 и 2 импульсов служат для хранения в режиме интерполяции значений координат и Л У (входы Вх ЛХ, Вх лУ) и для подсчета в режиме аппроксимации (обратной интерполяции) базового приращения координат (входы Bx.i, Bx.). Блок 3 сравнения служит для сравнения значений счетчиков 1 и 2 и управления блоками 4 и 5 мультиплексоров, которые в зависимости от управляющих входов коммутируют на входы счетчиков 6 и 7 содержимое счетчиков 1 и 2 импульсов. Счетчики 6 и 7 импульсов служат для хранения меньшей и большей координат дХ и й интерполируемой прямой, а также для подсчета количества элементарных приращений по осям X и Y в режиме линейной аппроксимации. Дешифраторы 8 и 9 служат для дешифрации состояния счетчиков 6 и 7 импульсов. Первые выходы дешифраторов показывают, что содержимое счетчиков импульсов не равно нулю, вторые - что равно нулю.

Блок 10 постоянной памяти служит для определения в режиме интерполяции базиса полного изображения прямой. Адресные входы блока 10 соединены с вькодами счетчиков 1 и 2 импульсов. Выходы блока 10 постоянной памяти соединены с регистрами 11, 12 и 13, В регистре 1) хранится первое число характеристики фасада, в регистре 1-2 - второе число, а в сдвиговом регистре 13 - порядок следования чисел в фасаде. Блок 14 му аьти,плексоров служит для коммутаций на вход счетчика 15 содержимого регист10

15

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

Генератор 17 служит для вьфаботки тактовых импульсов. Первый 18, второй 19 три ггеры и первый 20, второй 21 элементы И служат для выработки управляющих сигналов в режиме интерполяции. Первый элемент ИЛИ 22,третий 23, четвертый 24 и пятый 25 триггеры, третий 26, четвертый 27 и пя- 20 тый 28 элементы И, второй элемент ИЛИ 29 служат для выработки управляющих сигналов в режиме аппроксимациио Первый 30 и второй 31 элементы задержки, третий элемент ИЛИ 32, шестой25 33 и седьмой 34 элементы И служат для формирования управляющего сигнала записи в счетчик -15 о Восьмой элемент И 35 служит для выработки сигнала сброса первого 18 и второго 19 триг- ЗО герово Элементы И 36,37 служат для вьтолнения режима вычисления счетчиков 6 и 7 при линейной интерполяции Первый 38 и второй 39 элементы 2И-ИЛИ служат для формирования выходных сиг-, налов ВыХо ,. j в режиме интерполяции. Одиннадцатый 40, двенадцатый 41 элементы И и четвертый элемент ИЛИ 42 служат для формирования сигнала кода линейной аппроксимации. Тре- о тий элемент 43 задержки формирует сигнал сброса третьего и четвертого счетчиков по окончании аппроксимации линии,

1413600

указывающий на то, что линейная аппроксимация окончена.

Устройство в режиме интерполяции работает следующим образомо

В исходном состоянии в счетчиках 1 и 2 импульсов записаны значения ЛхХ и uY прямой, которую нужно.про- интерполировать, остальные элементы схемы сброшены Выходы счетчиков 1 и 2 импульсов соединены с адресными входами блока 10 постоянной памяти. В зависимости от значений У и д Y на выходах блока постоянной памяти устанавливаются значения двух чисел, составляющих характеристику фасада прямой, и последовательность следования этих чисел при образовании ба- зиса полного изображения прямойо

По сигналу Пуск через блоки 4 и 5 мультиплексоров значения Л X и ЛУ записываются в счетчики 6 и 7 импульсов о При этом в счетчик 7 импульсов записьшается большая координата (длинная ось), а в счетчик 6 - меньшая (короткая ось) Управление мультиплексорами осуществляет блок 3 сравнения Сигналом Пуск счетчик 15 импульсов устанавливается в исходное состояние и синхронно с работой генератора тактовых импульсов первый триггер- 18 - в Г.

Следующий тактовый импульс устанавливает в 1 второй триггер 19, проходит через первый э лемент И 20 и записывает в первый 1 1,. второй 12 и третий 13 регистры информацию с выходов постоянного запоминающего устройства. В первый 11 и второй 12 регистры записываются числа, определяющие характеристику фасада прямой, а в сдвиговый регистр 13 запи- сьшается порядок следования чисел, фасада для образования базиса полного изображения прямой При этом указанный вьш1е порядок следования чисел фасада повторяется до окончания интерполяции прямой.с данным фасадом. На выходе третьего блока 14 мульти плексоров (входы параллельной записи счетчика 15 импульсов) устанавливается одно из чисел характеристики фасада прямой, которое определяется одним из рдзрядов сдвигового регистра 13, например старшим Если в старшем разряде регистра 13 - I,- то на выходе.блока мультиплексоров - первое число характеристики фасада пряВ режиме интерполяции входами устройства являются входы йХ и первого 1 и второго 2 счетчиков импульсов , а выходами - выходы апементов 2И-ИЛИ 38,39. В режиме аппроксимации входами устройства являются вхо- ды Bx.i, Bxoj (элементарные приращения по осям координат) и входы Зн,1, 3Hoj, указывающие на то, что изменился знак элементарных: приращений, а выходами устройства - выходы третьего 6 (Вых. ДХ) и четвертого 7 (ВыХо ДУ) счетчиков, а так- же выход элемента ИЛИ 42 (Вых„А),

Следующий тактовый импульс устанавливает в 1 второй триггер 19, проходит через первый э лемент И 20 и записывает в первый 1 1,. второй 12 и третий 13 регистры информацию с выходов постоянного запоминающего устройства. В первый 11 и второй 12 регистры записываются числа, определяющие характеристику фасада прямой, а в сдвиговый регистр 13 запи- сьшается порядок следования чисел, фасада для образования базиса полного изображения прямой При этом указанный вьш1е порядок следования чисел фасада повторяется до окончания интерполяции прямой.с данным фасадом. На выходе третьего блока 14 мульти плексоров (входы параллельной записи счетчика 15 импульсов) устанавливается одно из чисел характеристики фасада прямой, которое определяется одним из рдзрядов сдвигового регистра 13, например старшим Если в старшем разряде регистра 13 - I,- то на выходе.блока мультиплексоров - первое число характеристики фасада прямой, О - .то второе о Задержанный на .половину периода следования на элементе 31 тактовый импульс проходит через шестой 33, седьмой 34 элементы И и третий элемент ИЛИ 32 на вход управления параллельной записью в пятый счетчик 15, в который записывается выбранное число характеристики фасада прямой,

Рабочие импульсы (первая серия) с выхода второго элемента И 21 проходят на счетный вход счетчика 15 и десятый элемент И 37 о С выхода десятого элемента И (разрешение от дешифратора 9) импульсы поступают на счетный вход счетчика 7 (большая координата), вычитая каждый раз из его содержимого единицу Количество рабочих импульсов, поступающих на входы счетчиков 15 и 7, равно содержимому счетчика 15, т.е. значению одного из чисел характеристики фасада. По окончании счета счетчик 15 выдает импульс конца счета (например,

сформированный сигнал переноса), ко«

торый поступает на вход элемента (И 36. С выхода элемента И 36 (разрешение от дешифратора 8, определяющего, что содержимое счетчика 6 не равно нулю) импульс поступает на вхо счетчика 6, вычитая из его содержимого единицу С выхода элементов И 36 и 37 импульсы проходят на выход устройства через элементы 2И-ИЛИ 38 и 39 -под управлением блока 3 сравнения, который восстанавливает первоначальное исходное направление осей, нарушенное ранее определением большей оси о

i .

Сигнал Конец счета поступает

также на сдвиговый регистр 13, осуществляя его сдвиг На выхор е блока 14 мультиплексоров устанавливается следующее число характеристики фасада прямой. Задержанный на половину периода относительно последнего рабочего импульса первой серии сигнал с выхода шестого элемента И 33 проходит через элементы И 34 (разрешение от дешифратора 16), ИЛИ 32 на вход управления параллельной записью в счетчик 15, записывая в него очередное число характеристики фасада.

С выхода второго элемента И 21 рабочие импульсы (очередная серия) вновь поступает через первый элемент ИЛИ 22 на счетный вход счетчика 15

с 0

5 20 25

30 5

40

45

50

5

Цикл работы, описанный выше, повторяется до тех пор, пока содержимое счетчиков 6 и 7 не станет равно нулю В этом случае сигнал с выхода элемента И 33 проходит через восьмой элемент И 35 и устанавливает первый 18 и второй 19 триггеры в О. Процесс интерполирования окончен На выход устройства через элементы 2И-ИЛИ 38 и 39 проходит число импульсов, равное содержимому счетчиков 6 и 7, значениям и, X и .

Устройство в режиме аппроксимации (обратной интерполяции) работает следующим образом.

На входы устройства Bx.i и BXoj поступают единичные приращения по координатам X и Y. Пусть,например, единичные приращения поступают по шине BXoi Четвертый триггер 24 устанавливается в единичное состояние, а в счетчике 1 накапливаются единичные приращения, пришедшие по оси i Единичное приращение по оси J проходит через элементы И 26, ИЛИ 29, устанавливая третий триггер 23 в 1 и запрещая тем самым поступление единичньк приращений в счетчики 1 и 2 импульсов, В счетчиках 1 и 2 фиксируются значения базового приращения. Сигнал с выхода элемента ИЛИ 29 проходит .через первый элемент 30 задержки и элемент ИЛИ 32, разрешая запись в счетчик 15 значения базового приращения. Значение базового приращения устанавливается на входах счетчика 15 с выхода счетчика 1 через блоки 5 и 14 мультиплексоров . Управление блоком 5 мультиплексоров осуществляется.от блока 3 сравнения, а блоком 14 мультиплексоров - от триггера 23 о L

Очередные единичные приращения

проходят через элемент ИЛИ 22 на счетный вход счетчика 15, где вычита- ются (или суммируются при работе в обратном коде) из содержимого счетчика 15. С приходом единичного приращения сигнал с выхода элемента ИЛИ 29 анализирует состояние дешифратора 16 Если текущее, значение элементарного приращения меньше базового на единицу, то оно записьшается в первый регистр 11 Если текущее элементарное приращение больше базового на единицу, то оно записьшается во второй регистр 12, Если текущее значение

714

элементарного приращения больше или меньше базового на единицу, то сиг- нал с вьпсода дешифратора поступает через элементы И 41, ИЛИ 42 на выход устройства (ВыХоА), Сигнал на выходе элемента ИЛИ 42 указывает на то, что очередное текущее элементарное приращение выходит за пределы допус- тимсгй ошибки о

Для нашего примера функция рассогласования имеет вид:

F (R,AR,)v(R,)v(i,Jv(j, )

где R,, R- - содержимое регистров

11,12; RJ значение дешифратора

16, указывающее на то, что значение текущего элементарного приращения значительно больше или .меньше базовог о Это выражение говорит о том, что сигнал формируется тогда, когда имеются отклонения на единицу от базового приращения как в ту, так и в другую сторону (R, лН;), значение текущего элементарного приращения значительно больше или меньше базового (RJ), а также когда есть изменение знака единичных приращений по оси i или j (1зц или JjH ).

Вькод элемента ИЛИ 42 (ВыХсА), а также выходы счетчиков 6 и 7 (Вых. ЛХ, Выходу) являются выходами устройства в режиме аппроксимаций В счетчиках 6 и 7 содержатся значенияUX и йУ, полученные путем подсчета единичных приращений, приходящих соответственно по осям i и J.

0 -8

Сигнал с выхода элемента ИЛИ 42 очищает счетчики 1 и 2, сбрасьюает триггеры 23, 24 и 25 и, проходя

через элемент 43 задержки, очищает счетчики 6 и 7о Если на выходе элемента ИЛИ 42 сигнал не сформирован, то в счетчик 15 заносится базовое приращение и устройство готово к

приему очередных единичных приращений по оси i и ТоДо Если вначале поступают.единичные приращения по оси j, то устройство работает аналогично описанному выше с той лишь

разницей, что вначале устанавливается пятый триггер 25 и сигнал с шины проходит через четвертый элемент И 27 о Связь выхода одного триггера с входом, другого (триггеры 24 и 25) необходима для запоминания информации, о том, по какой из осей i или j пришел первый сигнал Другой триггер в этом случае заблокирован до окончания цикла измерения

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

обработку информации

В6//С

Хф«2,3...

1 2 3 5 6 7 S 3 10 1112131 1516 17 18 Фиг. 2

О 1 2 3 If 5 В 7 В 9 1011 12 13 Hi 15 IS 17 18 192021,2223 2(25 2627 62330

Фиг.З