Линейный интерполятор

/4 ОСУДАРСТ 8 ЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСА ОБРЕТЕНИЯ ЕЛЬСТ МУ 0(54) ЛИНЕЙНЫЙ ИНТЕРПОЛЯТОР (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах программного управления станками и графических устройствах ввода - вывода цифровых вычислительных машин. Цель изобретения - повышение быстродействия интерполятора, Линейный интерполятор содержит регистры 1,2, коммутатор 3, блоки совпадения 4,5, сумматор 6, блок сравнения 7, блок управления 9В данном линейном интерполяторе существенным отличием является определение по диску и модулю оценочной функции очередного мп129874 и Швец Составитель И Техред: А.Крав Егор Редак Пилипенко ре зводственно"полиграфическое предприятие, г, Ужгород, ул Проектная,аказ 224 б Тираж В 11 ИИПИ Государственн по делам изобрете 113035, Москва, Ж, 63 Подписноего комитета СССРий и открытийаушская наб., д, 4/512987 двойного комбинированного перемещения эа два такта работы, Это достигается введением коммутатора, формирующего как одиночное (в цикле подготовки), так и удвоенное (в цикле интерполя" ции) значение меньшего приращения, и блока сравнения, обеспечивающего сравнение модуля оценочной функции с меньшим приращением, Значение оценочной функции определяют только 14.для первой четверти квадранта и вдальнейшем обеспечивается. преобразование полученных перемещений. длядругих областей посредством простых операций инверсии и коммутации,реализуемых в блоке управления в зависимости от сортношения приращений.Погрешность аппроксимации не превышает шага дискретизации. 1 з.п. Ф-лы,6 ил., 1 табл.Изобретение относится к автоматике и вычислительной технике и можетбыть использовано в устройствах программного управления стенками и графических устройствах ввода-вывода 5цифровых вычислительных машин,Цель изобретения - повышение быстродействия интерполятора,На фиг, 1 показан отрезок аппроксимируемой прямой в первой четвертиквадранта и полученный на основе инверсии перемещений данного отрезка -соответствующий отрезок во второйчетверти квадранта; на фиг. 2структурная схема предлагаемого ли 15нейного интерполятора; на фиг3 -отрезок аппроксимируемой прямой; наФиг, 4 - функциональная схема реализации блока управления; на фиг. 5 "граф-схема алгоритма функционирования20блока управления; на фиг, 6 - функциональная схема реализации сумматора,В основе изобретения лежит возможность однозначного определения перемещений за два такта работы интерполятора по знаку и модулю оценочнойфункции,Вывод функций для определенияперемещений производится только для30значений первой четверти первогоквадранта. Трансформация полученныхрезультатов на остальные четвертипроизводится согласно следующим правилам., 35Для получения отрезка прямой сауглом наклона - необходимо проинверЪтировать последовательность приращеЬ-а 40 ний, соответствующих отрезку . На 2фиг, 2 показан пример получения от 11резка прямой с наклоном - на основе15известных приращений для прямой с уг 4лом наклона - путем инвертирования15последних, Отрезку прямой с углом4наклона - по ведомой координате15соответствует последовательность приращений 0 1000 1000 1000 10, где 1 соответствует диагональному шагу, Инверсия приведенной последовательности(101110111011101) соответствует отрезку прямой с углом наклона11причем погрешности аппроксимации15 фуказанных прямых совпадают,Укаэанное свойство позволяет путеминверсии получать отрезки прямых вовторой четверти квадранта по известным последовательностям приращенийсоответствующих прямых с первой четверти.Взаимная перекоммутация последовательностей приращений, формируемыхв первой половине квадранта с координаты Х на 1 и с У на Х, обеспечи-.вает симметричное воспроизведениеотрезка прямой во второй половинеквадранта относительно биссектрисыугла по заданному отрезку в первойполовине квадранта,При интерполяции отрезка прямойединичными приращениями при 1 4 Х 1)1д У 1 используется оце ночная функция:при П; 7 О, перемещение по оси Х ипри 111( 0 перемещение по Х и Б;+ +, =Б;1 + ( Й Х-147, т.е, выполняется диагональный шаг по ведомой координате. В ис 3 12987 ходном состоянии значение оценочной функции равно БП (большое приращение).Во время интерполяции прямой в первой четверти квадранта вслед за перемещением по направлению, характеризуемому меньшей проекцией, т.е.выполнении диагонального шага, обязательно следует перемещение по направлению, характеризуемому большей проекцией, Это объясняется тем, что после выполнения диагонального шага к значению оценочной функции прибавляется значение ЬХ-д 11, Поскольку для рассматриваемого случая(первая четверть первого квадранта)Ь ХЪ 2ЬУ 1, очередное значениеоценочной функции после выполнениядиагонального шага всегда будет больше О, т,е. следующим выполняется шаг 20по ведущей координате при отсутствииперемещения по ведомой координате,Таким образом, по ведомой координатевозможны следующие сочетания шагов;01, 10, 00, где 1 соответствует наличию перемещения, а 0 отсутствиюперемещения. Если очередное значениеоценочной функции положительное ивыполняется условие );. - 2 ЬУ 7 О,то очередные два перемещения производятся только по оси Х. Если жеимеет место условие У; - 2 ЬУО,то по ведомой координате возможносочетание перемещений 1 О или 01, причем при О; -2 Ь"11 ), ЬУ выполняется перемещение 10, а при 1) -2 Ь 1( ЬУ - перемещение 01.Линейный интерполятор (фиг2)содержит первый 1 и второй 2 регистры координатных перемещений, коммута тор 3, первый 4 и второй 5 блоки совпадения, накопительный сумматор 6,блок 7 сравнения, вход 8 линейногоинтерполятора, блок 9 управления свыходами 10-20, вход 2 "Пуск" линей ного интерполятора, входы 22-26 блока управления,Блок управления (фиг, 4) содержиттриггер 27, узел 28 постоянной памяти, первый регистр 29, триггер 30, 5 рвторой регистр 31, генератор 32 импульсов. Сумматор (фиг, 6) содержитпервый 33 и второй 34 комбинационныесумматоры, регистр 35, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 36, 55 Регистры координатных приращений1 и 2 служат соответственно для хранения большего и меньшего приращения 4 4координат, определяющего отрабатываемый отрезок прямой,Большее приращение (БП) записывается в регистр 1 по входам, явля.ющимся первыми входами устройства.Выход регистра 1 соединен со входамипервого блока 4 сравнения, выход которого соединен с первыми входаминакопительного сумматора 6, а управляющий вход - с первым выходом блока9 управления, Меньшее приращение (МП)записывается в регистр 2 по входам,являющимся вторыми входами устройства, Вторые входы регистра 2 приращения соединены с информационнымивыходами сумматора 6 приращения,Вход записи регистра 2 координатногоприращения соединен с вторым выходомблока 9 управления, Вход регистра 2соединен с первыми и вторыми входамикоммутатора 3, управляющий вход ко-торого соединен с первым выходомблока управления,На первые входы коммутатора 3 подается значение, равное содержимомурегистра 2 координатных приращений,а на вторые - удвоенное значение содержимого регистра 2, Последнее достигается монтажным соединением, длячего 1-й выход регистра 2 координатных приращений соединяется с (+1)входом коммутатора 3, а младший разряд коммутатора 3 заземляется,Блок 7 сравнения обеспечиваетсравнение модуля суммы, полученной внакопительном сумматоре 6, с содержимым второго регистра 2 координатных приращений, поступающих на входыблока 7 сравнения, При единичном значении знакового разряда, сумматора 6и содержимом регистра 2 координатныхприращений, большем модуля суммы,формируемой сумматором 6, на выходеблока 7 сравнения появляется уровеньлогической единицы, В противном случае - на выходе блока 7 сравненияформируется уровень логического нуля.Триггер 27 устанавливается в состояние лог. единицы при БП = ЬУ,и в состояние лог, нуля при БП=ЬХ,Выходы 10-13 блока 9 управленияявляются выходами Х интерполятора,и выходы 14-17 - выходами У.Отсутствие перемещения по соответствующей координате эа времяинтерполяционного тока обозначеночерез О, а наличие - через 1, Уровень логической единицы на выходах5 12987 10-17 блока 9 управления обозначает двойные комбинированные перемещения:По координате Х По координате У10-00 14-0011-01 15-0112-10 16-1013-11 17-11Блок 9 управления, анализируя значение знакового разряда сумматора б и выхода блока 7 сравнения, задает 10 направление генерируемого двойного перемещения и характер следующей за ним арифметической операции по расчету очередного значения оценочной функции в соответствии с формулами: 15 при П;0 - перемешивание 00 по оси У и11 .=П - 2 ЛУ1при П; 0 и 101,1дУ - перемещение О 1 по оси У. и(меньшее приращение МП), При этом втриггер 27 записывается логическаяединица при Д Х = БП и ноль при д У==БППо сигналу "Пуск" начинается процесс воспроизведения отрезка прямой, 40Модули проекций через коммутаторы 3и блоки совпадения 5 и 4 подаются всумматор б для проведения операцииБП-МП, В блокесравнения полученное значение БП-МП, хранящееся в накопительном сумматоре 6, сравниваетсясо значениями МП, При БП - МП 3 МП,что соответствует появлению логического нуля на выходе блока 7 сравнения, блок 9 управления на своем выходе 18 формирует сигнал логическогонуля, который не является активнымсигналом записи в регистр 2, ПриБМ - ЬП 1 ( МП значение разности переэаписывается в регистр 2 Этому случаю соответствует формирование логических единиц на выходе блока 7 сравнения и выходе 18 блока 9 управления,условие БП - МП (МП при аХ = БП оп 14 6ределяет принадлежность генерируемого отрезка прямой к второй четверти первого квадранта Для обеспечения воспроизведения указанного вектора путем инверсии последовательности приращений по ведомой координате соответствующего Вектора в первой четверти квадранта необходимо, чтобы последний имел следующие значениямодулей проекций: а Х = БП, дУ = БПМП, что и обеспечено на первом подготовительном такте работы интерполятора, При этом блок 9 управления должен обеспечить в дальнейшем инвертирование последовательности приращений по ведомой координате. На этом заканчивается подготовительный этап, предшествующий собственно процессу интерполяции, Причем сумматор 6 принимает значение содержимого регистра 1 после выполнения подготовительных операций, т,е. По = БП,Поскольку эквивалентными трансформациями с учетом соответствующих признаков интерполяция сводится к генерации отрезков прямых в первой четверти первого квадранта, то процесс получения выходных последовательностей интерполятора по значениям входных приращений рассматривается только для указанной области, для которой йХ = БП, дУ = МП, 2 йУ (аХ,В цикле интерполяции в первом такте в сумматоре 6 производится вычисление разности Пр - 2 аУ, что обеспечивается формированием логических единиц на выходах 19 и 20 блока 9 управления, а также подачей логической единицы на вход сумматора б, Блоком 7 сравнения проводится сопоставление полученного модуля оценочной функции, хранящегося в сумматоре 6, с модулем МП, хранящимся в регистре 2 координатных приращений, Блок 9 управления в зависимости от значения знакового разряда сумматора 6, формируемого на его выходе, уровней сигналов поступающих с выхода блока 7 сравнения, и значения сигнала, поступающего с выхода триггера 27, формирует выходные сигналы, соответствующие двойным перемещениям по обоим направлениям, Б зависимости от значения знакового разряда сумматора 6 формируется новое значение оценочной функции, определяющей очередные двойные перемещения, При положительном значении модуля оценочной функции ее новое значение оп 129ределяется согласно выражению 111, ==П - 2 дУ, а при отрицательном -согласно выражению 0 = Ц -аУ+(ьХ-М)На фиг, 3 изображен отрезок аппроксимируемой прямой с дХ=7, ЛУ=З.Вычисление оценочной функции и формирование комбинированных двойных .перемещений производится следующимобразом:Оо = 7 - перемещение отсутствует, 2 дУ = 6, БП = Л Х=7;П, = 7-6 =0 - перемещение 00по ведомой координате (вых. 14,вых, 13)0 = 1-6, = -5, 1 1 уВУ - перемещение 1 О по ведомой координате(вых. 16, вых, 13);П = -5-3 + (7-3) = -4, 11 дУ -перемещение 10 по ведомой координате (вых, 16, вых, 13);Ц = -4-3 + (7-3) = -3, П 4= ДУ - перемещение 10 по ведомойкоординате (вых16, вых. 13).Блок 9 управления может быть синтезирован различными известйыми методами,В исходном состоянии регистры 29и 30, а также триггер 30 обнулены.По сигналу "Пуск" начинает работугенератор 32 импульсов. Для обеспечения принципа единой временной организации синхронизация регистров 23и 31 осуществляется от различныхфронтов, С каждым тактовым импульсомиз узла 28 постоянной памяти обеспечивается выборка управляющего сигнала по адресу, хранящемуся в регистре31 и определяемому входными сигналами 22,23,27 блока и состоянием триггера 30. Управляющее слово записывается в регистр 29. Нулевой уровеньсигнала "Пуск" определяет окончаниепроцесса интерполяции и устанавливает в ноль триггер 30 и регистр 31,Схема алгоритма функционирования блока 9 управления приведена на фиг, 4. Содержимое узла 28 постоянной памяти блока 9 управления, составленное в соответствии с алгоритмом функционирования, приведено в таблице. Таблица приведена только для случая ДХ 7 д У, где В Х, ЛУ - проекции приращений аппроксимируемого отрезка соответственно на оси Х и У. Случаю йХ ) ЛУ соответствует значение 0 в колонке, определяющей старший разряд адреса адресного прост 8714 8 на 45 с максимальной точностью (погрешность аппроксимации равна 0), в 50 то время как н известном устройствеэтого достичь нельзя,Формула и з о б р е т е н и я 55 5 О 5 20 25 30 35 40 45 ранства ПЗУ, поскольку значение сигнала на входе 23 - нулевое, СлучаюДУ; аХ соответствует 1 н указаннойколонке. Таблица, определяющая содержимое узла постоянной памяти дляданного случая, совершенно аналогична приведенной, эа исключением разрядов, определяющих выходные сигналы, Значение указанных разрядов получают путем взаимной перестановкиколонок Я 1 - С 4 и колонок С 5-Я 8 втаблице, те, обеспечивается взаимная перекоммутация выходных сигналов с координат Х на У,Накопительный сумматор 6 работаетследующим образом,В каждый момент времени на информационный вход регистра 35 подаетсязначение, равное сумме операндов,поступающих от блоков 4 и 5, а также с выхода регистра 35, При появлении переднего фронта на входе 24 сумматора значение суммы подается навыход регистра и при нулевом значении знакового разряда - на выход блока. При единичном значении знаковогоразряда блок 36 элементов ИСКЛЮЧАЮЩЕЕ.ИЛИ обеспечивает инвертирование значения суммы, поступающей с выходарегистра 35, т,е, обеспечивается выдача модуля суммы,Погрешность аппроксимации не превышает шага дискретизации,Быстродействие приведенного линейного интерполятора превышает быстродействие известного устройства в 2раза,Это объясняется тем, что в последнем значение оценочной функции вычисляется только для одного единичного перемещения по обеим координатам, В предлагаемом линейном интерполяторе значение оценочной функциивычисляется сразу же для двойногоперемещения по обеим координатам,Кроме того в нем достигается воспроизведение прямых с углом накло 1, Линейный интерполятор, содержащий первый и второй регистры, первый и второй блоки совладения, выходы которых подключены к первому и второму входам сумматора соответственно,1298714 выход первого регистра соединен спервым входом первого блока совпадения, вход первого регистра соединен с первым входом линейного интерполятора, второч вход которогоподключен к первому входу второго регистра, отличающийсятем, что, с целью повышения быстро"действия интерполятора, в него вве"дены блок управления, коммутатор и 1 Облок сравнения, выход которого подключен к первому входу блока управления, второй вход которого соединенс первым выходом сумматора и с первым Входом блока сравнения, второйвход которого подключен к второмувыходу сумматбра и к второму входувторого регистра, третий вход - квыходу второго регистра и к информационным входам коммутатора, управ- щоляющий вход которого соединен с первым выходом блока управления, второйвыход которого подключен к третьемувходу второго регистра, третий выход - к первому входу второго блокасравнения, подключенного вторым входом к выходу коммутатора, четвертыевыходы блока управления соединены стретьими входами сумматора, пятыивыход - с вторым входом первого бло- Зрка совпадения, третий вход блока управления подключен к третьему входулинейного интерполятора, вход Пуск"которого соединен с входом "Пускблока управления, пятые и шестые выходы которого являются выходами линейного интерполятора,1 О2.Интерпопятор по п, 1, о т л и -ч а ю щ и й с я тем, что блок управления содержит генератор импульсов, первый и второй регистры, дватриггера и узел постоянной памяти,первые выходы которого подключены кпервым входам первого регистра, выходы которого являются пятыми и шестыми выходами блока управления, вторые выходы узла постоянной памятисоединены с информационными входамивторого регистра, управляющий входкоторого соединен с инверсным выходом генератора импульсов, прямой выход которого подключен к управляющему входу первого регистра, а вход -к входу "Пуск" линейного интерполятора и к установочным входам первоготриггера и второго регистра, первый,второй, третий и четвертый выходыкоторого подключены к соответствующим первым входам узла постояннойпамяти, второй вход которого соединен с выходом первого триггера, третий и четвертый входы - соответственно с первым и вторым входами блокауправления, пятый вход узла постоянной памяти соединен с выходом второго триггера, вход которого является третьим входом блока управления,вторые выходы первого регистра подключены к соответствующим выходамблока управления, второй выход узлапостоянной памяти соединен с управляющим входом первого триггера, 0-входкоторого соединен с третьим входомузла постоянной памяти,