Интерполятор

 

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

А "1 (19) (11) (5D4 G 05 В 1 18 19 415

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К A BTOPCH0MY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21 ) 3965534/24-24 (22) 17,10,85 (46) 30.07.88. Бюл. Р 28 (71) Институт технической кибернетики АН БССР (72) В.С.Давейнис (53) 621.503.55 (088.8) (56) Авторское свидетельство СССР

11 117590, кл. G 05 В 19/18, 1984.

Авторское свидетельство СССР

1 108395, кл. G 05 В 19/415, 1983, (54).(57) ИНТЕРПОЛЯТОР, содержащий генератор импульсов, соединенный выходом с первыми входами первого и второго элементов И, первый, второй и третий элементы задержки, первый и второй счетчики импульсов, выходы кото" рых соединены с входами блока сравнения, а входы являются соответственно первым и вторым входами интерполятора, первый триггер, выход которого соединен с вторым входом пер" вого элемента И, а выход второго элемента И " с первым входом-первого элемента ИЛИ, третий, четвертый и пятый элементы И, выходы третьего и четвертого элементов И соединены с первым и вторым входами второго элемента ИЛИ, выход которого подключен к входу первого элемента задержки, а также третий и четвертый элементы

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

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

2И-ИЛИ и с входом управления счетом третьего счетчика импульсов, выход десятого элемента И соединен с вторыми входами первого и второго эле" ментов 2И-ИЛИ и с входом управления счетом четвертого счетчика импульсов, первый выход блока сравнения соединен с управляющими входами первого блока мультиплексоров и с третьими входами nepaoro и второго элементов

2И-ИЛИ, второй выход блока сравнения соединен: с управляющими входами вто. рого блока мультиплексоров и с четвертыми входами первого и второго элементов 2И-ИЛИ, вторые выходы пер" вого и второго регистров соединены с первым и вторым входами одиннад" цатого элемента И соответственно, вы" ходы одиннадцатого и двенадцатого элементов И соединены с входами чет- вертого элемента ИЛИ,,выход которого через третий элемент задержки соединен с пятыми входами третьего и четвертого счетчиков импульсов и с входами установки в "0" третьего,четвертого и пятого триггеров, первого и второго счетчиков, выход четвертоro триггера соединен с первым входом третьего элемента И и первым входом пятого триггера, выход пятого триггера соединен с первым входом четвертого элемента И и с первым входом четвертого триггера, вход интерполятора Вх.i соединен со счетными входа11 ° 1) ми первого и третьего счетчиков, вторыми входами четвертого триггера и четвертого элемента И, а также с вторым входом первого элемента ИЛИ,вход интерполятора "Bz,g соединен со счетными входами второго и четвертого счетчиков, с вторыми входами пято" го триггера, третьего элемента И, а также с третьим входом первого элемента ИЛИ, вход интерполятора "Пуск" подключен к входу установки в "1" . первого триггера, к входам управления режимом параллельной записи третьего и четвертого счетчиков и к входу установки в исходное состояние пятого счетчика, входы знаковых раз" рядов "Зн.i" и "Зн,g" "соединены с третьими входами четвертого элемента ИЛИ, выход второго элемента И под" ключен к второму входу десятого зле" мента И, причем выходами интерполятора в режиме интерполяции являются выходы элементов 2И-ИЛИ, в режиме аппроксимации — выходы третьего и четвертого счетчиков и выход четвертого элемента ИЛИ.

1413600

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

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

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

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

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

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

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

Счетчики 1 и 2 импульсов служат для хранения в режиме интерполяции значений координат а.Х и b,Y (входы

"Bx Х", "Bx hY") и для подсчета в режиме аппроксимации (обратной интерполяции) базового приращения координат (входы "Вх.i" "Вх.J ). Блок 3 сравнения служит для сравнения значений счетчиков 1 и 2 и управления блоками 4 и 5 мультиплексоров, которые в зависимости от управляющих входов коммутируют на входы счетчи" ков 6 и 7 содержимое счетчиков 1 и

2 импульсов, Счетчики 6 и 7 импульсов служат для хранения меньшей и большей координат g X и ДХ интерполируемой прямой, а также для подсчета количества элементарных приращений по осям Х и Y в режиме линейной аппроксимации. Дешифраторы 8 и 9 служат для дешифрации состояния счет. чиков 6 и 7 импульсов. Первые выходы дешифраторов показывают, что содержимое счетчиков импульсов не равно нулю, вторые — что равно нулю.

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

3 1413 ров 11 и 12 в режиме интерполяции и значения базового приращения (через блок 5 мультиплексоров) в режиме аппроксимации. Дешифратор 16 служит для дешифрации состояния счетчика 15.

Выходы дешифратора указывают, что текущее значение счетчика равно, мень" ше на единицу, больше на единицу, меньше или больше, чем на единицу, числа, занесенного ранее в счет" чик 15, Генератор 17 служит для выработки тактовых импульсов. Первый 18, второй 19 триггеры и первый 20, второй

2l элементы И служат для выработки управляющих сигналов в режиме интерполяции. Первый элемент ИЛИ 22,третий 23, четвертый 24 и пятый 25 триггеры, третий 26, четвертый 2? и пя- 20 тый 28 элементы И, второй элемент

ИЛИ 29 служат для выработки управляющих сигналов в режиме аппроксимации.

Первый 30 и второй 31 элементы за" держки, третий элемент ИЛИ 32, шестой25

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

И 35 служит для выработки сигнала сброса первого 18 и второго 19 триг- 30 геров. Злементы И 36,37 служат для выполнения режима вычисления счетчиков 6 и 7 при линейной интерполяции.

Первый 38 и второй 39 элементы 2И-ИЛИ служат для формирования выходных сиг- З5 налов "Вых.i" "Âûõ.)" в режиме интерполяции. Одиннадцатый 40, двенадцатый 41 элементы И и четвертый элемент

ИЛИ 42 служат для формирования сигнала кода линейной аппроксимации. Тре- ао тий элемент 43 задержки формирует сигнал сброса третьего и четвертого счетчиков по окончании аппроксимации линии»

В режиме интерполяции входами уст- ройства являются входы 6Х и Х первого 1 и второго 2 счетчиков импульсов, а выходами — выходы элементов

2И-ИЛИ 38,39. В режиме аппроксима50 ции входами устройства являются входы "Вх.i", "Вх.g" (элементарные приращения по осям координат) и входы

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

В исходном состоянии в счетчиках

1 и 2 импульсов записаны значения

hX и ЬХ прямой, которую нужно проинтерполировать, остальные элементы схемы сброшены. Выходы счетчиков 1 и 2 импульсов соединены с адресными входами блока 10 постоянной памяти.

В зависимости от значений g Х и 6 Y на выходах блока постоянной памяти устанавливаются значения двух чисел, составляющих характеристику фасада прямой, и последовательность следования этих чисел при образовании ба" зиса полного изображения прямой, По сигналу "Пуск" через блоки 4 и 5 мультиплексоров значения Д Х и дХ записываются в счетчики 6 и 7 импульсов. При этом в счетчик 7 импульсов записывается большая координата (длинная ось), а в счетчик б — меньшая (короткая ось). Управление мультиплексорами осуществляет блок 3 сравнения. Сигналом "Пуск" счетчик

15 импульсов устанавливается в исходное состояние и синхронно с работой генератора тактовых импульсов первый триггер 18 - в "1".

Следующий тактовый импульс устанавливает в "1" второй триггер 19, проходит через первый элемент И 20 и записывает в первый 11, второй 12 и третий 13 регистры информацию с выходов постоянного запоминающего устройства, В первый 11 и второй 12 регистры записываются числа, определяющие характеристику фасада прямой, а в сдвиговый регистр 13 записывается порядок следования чисел фасада для образования базиса полного изображения прямой. При этом указанный вьппе порядок следования чисел фасада повторяется до окончания интерполяции прямой с данныи фасадом.

На выходе третьего блока 14 мульти» плексоров (входы параллельной записи счетчика 15 импульсов) устанавливается одно из чисел характеристики фасада прямой, которое определяется одним из разрядов сдвигового регист" ра 13, например старшим, Если в старшем разряде регистра 13 " "1", то на выходе .блока мультиплексоров — первое число характеристики фасада пря1413600 мой, если "0" — .то второе. Задержанный на .половину периода следования на элементе 31 тактовый импульс проходит через шестой 33, седьмой 34 элементы И и третий элемент ИЛИ 32 на вход управления параллельной записью в пятый счетчик 15, в который записывается выбранное число характеристики фасада прямой. 10

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

По окончании счета счетчик 15 выдает импульс конца счета (например, сформированный сигнал переноса), который поступает на вход элемента (И 36. С выхода элемента И 36 (разрешение от дешифратора 8, определяющего, что содержимое счетчика 6 не 30 равно нулю) импульс поступает на вход счетчика 6, вычитая из его содержимого единицу. С выхода элементов

И 36 и 37 импульсы проходят на выход устройства через элементы 2И-ИЛИ 38 и 39 под управлением блока 3 сравнения, который "восстанавливает" первоначальное исходное направление осей, И нарушенное ранее определением больи шей оси. 40 !

Сигнал "Конец счета" поступает также на сдвиговый регистр 13, осуществляя его сдвиг. На выходе блока

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

ИЛИ 22 на счетный вход счетчика 15.

Цикл работы, описанный выше, повторяется до тех пор, пока содержимое счетчиков 6 и 7 не станет равно нулю. В этом случае сигнал с выхода элемента И 33 проходит через восьмой элемент И 35 и устанавливает первый

18 и второй 19 триггеры в "0". Процесс интерполирования окончен. На выход устройства через элементы

2И-ИЛИ 38 и 39 проходит число импульсов, равное содержимому счетчиков

6 и 7, т,е, значениям b X u hY.

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

На входы устройства "Вх,i" и

"Вх.)" поступают единичные приращения по координатам Х и Y. Пусть,например, единичные приращения поступа" ют по шине "Вх.i". Четвертый триггер

24 устанавливается в единичное состояние, а в счетчике 1 накапливаются единичные приращения, пришедшие по оси i. Единичное приращение по оси проходит через элементы И 26, ИЛИ 29, устанавливая третий триггер

23 в "1" и запрещая тем самым поступление единичных приращений в счетчики 1 и 2 импульсов, В счетчиках 1 и 2 фиксируются значения базового приращения. Сигнал с выхода элемен" та ИЛИ 29 проходит через первый элемент 30 задержки и элемент ИЛИ 32, разрешая запись в счетчик 15 значе" ния базового приращения. Значение базового приращения устанавливается на входах счетчика 15 с выхода счетчика 1 через блоки 5 и 14 мультиплексоров. Управление блоком 5 мультиплексоров осуществляется от блока 3 сравнения, а блоком 14 мультиплексоров - от триггера 23.

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

Если текущее. значение элементарного приращения меньше базового на единицу, то оно записывается в первый регистр 11. Если текущее элементарное приращение больше базового на единицу, то оно записывается во второй регистр 12. Если текущее значение

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

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

F = (н„лв )ч(я,)v(i,„) (g,„), где R < Б — содержимое регистров

11,12;

R " значение дешифратора з

16, указывающее на то, что значение текущего элементарного приращения значительно больше или .меньше базового .

Это выражение говорит о том, что сигнал формируется тогда, когда име" ются отклонения на единицу от базового приращения как в ту, так и в другую сторону (2,< Н ), значение текущего элементарного приращения значительно больше или меньше базового (R ), а также когда есть изменение знака единичных приращений по оси i

> (i i,„).

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

/ Сигнал с выхода элемента ИЛИ 42 очищает. счетчики 1 и 2, сбрасывает триггеры 23, 24 и 25 и, проходя через элемент 43 задержки, очищает счетчики 6 и 7. Если на выходе элемента ИЛИ 42 сигнал не сформирован, то в счетчик 15 заносится базовое приращение и устройство готово к приему очередных единичных приращений по оси i и т,д. Если вначале поступают единичные приращения по оси, то устройство работает аналогично описанному выше с той лишь разницей, что вначале устанавливаетсн пятый триггер 25 и сигнал с шины проходит через четвертый элемент И 27.

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

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

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

1413600!

413600

7 б б ф

2

1 2 3 9 5 67 8 9101112131475%1718

Фуз. 2

13

12

10

6, 7

6.5

1

О 1 2 3 4 5 Е 7 В 9 Ю 11 12 13 14 15 517 18 19202122232425И2728293д (Рие. 3

Составитель И.Швец

Техред Л.Сердюкова

Редактор И,Рыбченко

Корректор Л.Пилипенко

Заказ 3784/50 Тираж 866 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4