Цифровой линейный интерполятор

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в выходных графических устройствах с линейными матричными органами регистрации, а также в станках с программным управлением, в которых применяются линейные и матричные органы. Цель изобретения - повышение точности Изобретение относится к автоматике и вычислительной технике и может быть использовано в выводных графических устройствах с линейными матричными органами регистрации, а также в станках с программным управлением, в которых использованы линейные и матричные Органы. Цель изобретения - повышение точности интерполяции. интерполяции. Цифровой интерполятор содержит блок выделения нуля, регистр остатка , три коммутатора, накапливающий сумматор, регистр меньшего приращения, б/ток инверторов, два двоичных сумматора, блок управления, регистр многоразрядных приращений, выходной коммутатор. В интерполяторе в каждый тактовый промежуток времени на выходах формируются многоразрядные шаговые приращения. В первом такте формируется многоразрядное приращение (К+1)/2. В последующие тактовые промежутки на информационном выходе интерполятора формируются многозарядные приращения Кили К-И, порядок следования которых определяется по знаковому разряду накапливающего суммагора. Последнее многоразрядное приращение определяется по первому, причем в нем запрещается формирование элементарного шага по ведомой координате. В интерполяторе за счет симметрирования многораарядных приращений и отслеживания отклонения их от идеальной прямой достигнута максимальная точность аппроксимации , 1 з. п. ф-лы, 11 ил., 2 табл. На фиг. 1 изображена структурная схема интерполятора; на фиг. 2 - функциональная схема блока управления; на фиг. 3 - граф-схема алгоритма работы интерполятора; на фиг. 4 - временная диаграмма работы блока управления при М 16, N 5; на фиг, 5 - аппроксимация отрезка прямой при М 16, N 5; на фиг. 6-график распределения погрешностей аппроксимации отрезка прямой многоразрядными приращениями при ч (Л о ю ы СП ю ю

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

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

РЕСПУБЛИК

У (1)5 G 05 В 19/415

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

:а;а ал ---. - -й г

t !

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

:..:. ь

1;.-::.: 1

И (21) 4721756/24 (22) 24.07.89 (46) 23.11.91. Бюл, М 43 (71) Специальное конструкторско-технологическое бюро "Модуль" Винницкого политехнического института (72}A.Ï. Стахов, A.Н. Романюк, В.С. Сенчик, В.А. Шебуков, Н.И. Сорока и Н.Ф, Гейвандова (53) 621.503.55 (088.8) (56) Авторское свидетельство СССР

М 1413603, кл, G 05 В 19/415, 6 06 F 15/353, 1988.

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

N1310779,,кл. G 05 В 19/18, 1987, (54) ЦИФРОВОЙ ЛИНЕЙНЫЙ ИНТЕРПОЛЯТОР (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в выходных графических устройствах с линейными матричными органами регистрации, а также в станках с программным управлением, в которых применяются линейные и матричные органы.

Цель изобретения — повышение точности

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

Цель изобретения — повышение точности Интерполяции.

ЯЛ,, 1693592 Al интерполяции. Цифровой интерполятор содержит блок выделения нуля, регистр остатка, три коммутатора, накапливающий сумматор, регистр меньшего приращения, блок инверторов, два двоичных сумматора, блок управления, регистр многоразрядных приращений, выходной коммутатор. В интерполяторе в каждый тактовый промежуток времени на -выходах формируются многоразрядные шаговые приращения. В первом такте формируется многоразрядное прираи;ение (К+1)/2. В последующие тактовые промежутки на информационном выходе интерполятора формируются многозарядные прира цения К или К+1, порядок следования которых определяется по знаковому разряду накапливающего суммагора. Последнее многоразрядное приращение определяется по первому, причем в нем запрещается формирование злементарного шага по ведомой координате. В интерполяторе за счет симметрирования многоразрядных приращений и отслеживания отклонения их от идеальной прямой достигнута максимальная точность аппроксимации, 1 з. и. ф-лы, 11 ил., 2 табл.

На фиг. 1 изображена структурная схема интерполятора; на фиг. 2 — функциональная схема блока управления; на фиг. 3— граф-схема алгоритма работы интерполятора; на фиг. 4- временная диаграмма работы блока управления при M - 16, N -5; на фиг, 5- аппроксимация отрезка прямой при М =

=16, N = 5; на фиг. 6 — график распределения погрешностей аппроксимации отрезка прямой многоразрядными приращениями при

1693592 условии !пх центрироеания; на фиг. 7 — схемы расположения едини IIoIo элемента при левом и правом цеатрир )вании; на фиг. 810 — схемы коммутаторов; ня фиг, 11 — сегменты.

Цифровой линейный интерполятор (фиг. 1) содержит блок 1 выделения нуля, регистр 2 остатка, первый коммутатор 3., накапливающий сумматор 4, регистр 5 меньшего приращения, второй коммутатор

6, блок 7 инверторов, первый двоичный сумматор 8, блок 9 управления, регистр l0 мноГOP83PRP HbIX ПРИ ()Я ЩЕН Ий, ВТОРОЙ двоичный сумматор 11, третий коммутатор

12, выходной коммутатор 13, Интерполятор имеет вход l4 остатка, вход 15 записи, вход 16 меньшего приращения, вход 17 "Пуск", вхо,. ., 18 начальной устаковки, вход 19 признака, Вход 22 цифрового сегмента, выход 2О конца интерполяции, Стробирующий ВыхОД 21, перВый информа-цион ный ВыхОД 23 многоразрядных и ри()Ящений, второй информационный выход 24 многоразрядных приращений, Позициями

25-34 обозначены входы и выходы блока 9, Блок 9 управления (фиг. 2) содержит элемент M JlM 35, О-триггеры 36 и 37, формирователь 38 импульсов, зле 4енты И 39-43, О-.григгер 44 и 45, с етчик 46 импульсов, 0-триггер 47, элемент ИЛИ 48, элементы И

49 и 50, элемент ИЛИ 51, элемент ИСКЛ1ГЧАК3Щ1=Е ИЛИ 52 и D-триггер 53. КоммутаТор 6 ".Одерж!лт группу мул»типлексоров

54 — 54п. Комму втор i2 содесжит группу мультиплексоров 55л-55в. Коммутатор 3 ооДержит группу мультиглексоров 56.I — 56в.

Рег1лстр 2 ocTBTI:3;fl )I

Управляющий вхсд регистра 2 соединен с управля ющим Входом регистра 5, первым входом блока управления, К-входом (входом сброса) накапливаюьцего сумматора 4 и управляк)щит входом регMcTpB 1Î многop33- рядных приращений, Информационный вход регистра 2 остатка подклк)чен к информационному входу блока 1. первому информационному Входу flBpBQI o суммяторя 8, первому входу первого коммутатора 3, ня первый вход которого ггоступает удвоен <ое

-значение содержимого, регистра 2 остатка.

Удвоенное значение достигаегся монтажной коммутацией перво-о входа коммутатора 3. Для этого каждый l-й разряд выхода регистра 2 подключен к (i+1)-му разряду первого входа коммутатора 3, (! =-- 1, m)„ где m — разрядность регистра 2, млядшии разряд первого информационного входа коммутатора 3 заземлен.

Блок 1 выделения нуля служит для выделения нулевого значения остатка h. Выход блока 1 соединен с вторым входом 26 блока

9 управления, Первый коммутатор 3 обеспечивает передачу на свой вход содержимого одного из трех входов В зависимости от значения адресного входа (табл, 1). Выход первого коммутатора 3 подключен к информационному входу накапливающего сумматора 4. Старший разряд адресного входа (А1) первого коммутатора 3 подключен к второму выходу 27 блока 9 управления.

Младший разряд адресного входа (АО) первого коммутатора 3 соединен с выходом переноса накапливающего сумматора 4 и с третьим входом 29 блока 9 управления.

Таблица 1

Накапливаю. ИЙ сумматор 4 представляет собой накапливающий сумматор и осуществляет суммирование значения с его информационного входа со значением, хранящимся в его внутреннем регистре. Сигнал с выхода знакового разряда сумматора поступает на третий 29 вход блока 9 управления и на старший разряд адреса первого 3 коммутатора. Сигнал записи суммы во внутренний рег.пстр уммятора 3 осуществляется передним фронтам сигнала, поступающего с третьего выхода блока 9 управления. Сброс внутреннего регистра сумматора 3 производится активным сигналом логической единицы, поступающей на

R-вход сумматора 3. Перенос младшего разряда сумматора 3 заземлен.

Регистр 5 меньшего приращения служит для хранения меньшего приращения N задающего отрезка аппроксимируемой прямой, Запись в регистр 5 осуществляется передним фронтом сигнала записи, поступающего на вход 15 записи интерпо ляторя. Информационный вход регистра!; соединен с вторым входом 16 интерполято ря и с информационным .входом блока Ь управления. Выход регистра 5 соединен с

"693592 первым и вторым входами второго коммутатора, причем на первый вход коммутатора 6 поступает удвоенное значение регистра 5.

Удвоенное значение достигается монта:-,:.ной комутацией входа коммутаторов, Для этого каждый 1-й разряд выхода регистра 5 подключен к (i+1)-му разряду первого входа коммутатора 6, причем i = 1, и, где и — разрядность выходной информационной шины регистра 5, младший разряд первого входа коммутатора 6 заземлен. При значении логического нуля на управляющем входе коммутатора 6 последний осуществляет передачу операнда со своего первого входа на выход. При значении логического нуля на управляющем входе коммутатора 6 последний осуществляет передачу операнда со своего первого входа на выход. При значении логической единицы на управляющем входе коммутатора 6 осуществляется передача операнда со своего второго входа на выход, Выход коммутатора 6 подключен к блоку 7 инверторов. Управляющий вход второго коммутатора 6 соединен с блоком 9 управления.

Сумматор 8 представляет собой комбинационный сумматор и осуществляет сложение операндов, поступающиx на первый

20 и второй суммирующие входы. Вхсд с лматора 8 переноса подключен к выходу лаги- 30 ческой единицы.

Выход сумматора 8 соединен с вторым и третьим входами первого комму. егора ", причем на его второй вход поступает удвоенное значение содержимого первого сум- 35 матора 8. Удвоенное значение достигается монтажной коммутацией входа коммутатора 3. Для этого каждый I-й разряд выхода сумматора 8 подключают к {3+1}-му разряду второго входа коммутатора 3, причем! = 1, 40 и - 1, где и — разрядность информационной шины сумматора 8, Младший разряд второго информацианнога входа коммутатора 3 заземлен.

Блок 9 управления осуществляет управ- 45 ление операционными узлами интерполятора в соответствии с алгоритмом работы, По входу 17 интерполятора происходит запуск интерполятора передним фронтам сигнала.

Вход интерполятора соединен с входом 50 блока 9 управления. По входу 18 интерполятора уровнем логического нуля происходит начальная установка интерпалятора. Единичное значение сигнала на четвертом входе 19 интерполятора указывает, что 55 интерполирование будет происходить во втором полуоктанте. Значение логического нуля на входе 19 указывает, что интерполирование производится в первом полуоктанте. Вход 19 соединен с входом блока 9 упаавления. Единичное значение младшего, разряда регистра 10, поступающее на вход

30 блока управления, указывает о нечетном значении К. На выходе 20 блока 9 управления формируется сигнал "Конец интерполяш.и". Сигнал логического нуля на укаэанном выходе сигнализирует об интерполяции отрезка в заданный момент времени, т, е. о занятости интерполятора. При значении логической единицы на выходе 20 блока 9 управления интерполятор готов к приему исходного задания отрезка прямой. Выход .

20 блока 9 управления соединен с выходом

20 конец интерполирования интерполятора.

Под воздействием сигнала, формируемого на страбирующем выходе 21 интерполятара, осуществляется стробирование выходных многоразрядных приращений.

Страбирование происходит передним фронтом сигнала. Выход 21 (стробирующий) интерпопятора соединен с выходом 21 блока 9 управления.

Регистр 10 многоразрядных приращень и служит для хранения К, определяющего

:.исло элементарных шаговых приращений па ведущей координате, приходящееся на единичное перемещение по ведомой координате, Информационный вход регистра 10 соединен с входам 22 интерполятора, а выход соединен с входам сумматора 11, с третьим и четвертым входами коммутатора

10, причем на четвертый вход коммутатора

12 поступает половина значения садержи-гого регистра 10. равного (К/2). Половина значен«я содержимого регистра 10 достигается монтажной коммутацией четвертого входа коммутатора 12. Для этага каждый

i-й разряд входа третьего коммутатора 12 подключают к {i+1}-му разряду регистра 10, причем i = 1, п-1, где и — разрядность информационной шины регистра 10.

Двоичный сумматор 11 представляет собой комбинационный сумматор и осуществляет суммирование операнда, поступающего на ега второй информационный вход со значением логической единицы, поступающей на его вход переноса, Информационный вход сумматора 11 заземлен. Половина значения содержимого сумматора 11 достигается монтажной коммутацией второго входа коммутатора 12, Для этого каждый 1-й разряд входа коммутатора 12 подключают к (n+ 1-му разряду сумматора 11, причем

i=1,ï-1, где п — разрядность информационной шины, Коммутатор 12 обеспечивает передачу на свой выход значения содержимого из четырех ега входов в зависимости от значения адресного входа (табл. 2). Выход коммутатара 12 подключен к входу выходного коммутатора. Старший разряд адресного

1693592

Таблица 2

Значение операнда на выходе коммутатора 12 од адреса коммутатс

10

34 (А1) 31 (АО) (К+1)/2

К+1

К/2

1

0 входа (А1) коммутатора 3 подключен к выходу 34 блока 9 управления, Младший разряд адресного входа (АО) кб- мутатора 3 подключен к входу 31 блока 9 управления.

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

При r = 0 (признак принадлежности отрезка прямой первому полуоктанту) на выход 23 выдается значение многоразрядного приращения от коммутатора 12, а на выход 24 - значение логической единицы от входа коммутатора 13. Следовательно,, внешним устройством будет воспринят цифровой сегмент, показанный на фиг. 11а.

При г = l (признак принадлежности отрезка прямой второму полуоктанту) на выход 24 выдается значение многоразрядного приращения от коммутатора 13, Внешним устройством будет восп ринят цифровой сегмент, показанный на фи:. 11б.

Таким образом, информация на выходе

24 определяет число диагональных шагов, а на выходе 23 — горизонтальных шагов.

Адресный вход коммутатора 13 соединен с выходом 33 блока 9 управления. Все разряды первого информационного входа заземлены за исключением младшего разряда, который подключен к выходу блока 9 управления.

Счетчик 46 предназначен для определения окончания процесса интерполяции. При задании отрезка прямой в него записывается значение меньшего приращения, Запись в счетчик 46 обеспечивается активным уровнем сигнала, поступающего с входа 15 записи интерполятора, соединенного с входом блока 9 управления.

Триггеры 36 и 37 предназначены для присинхрониэированного каналеработы к импульсной последовательности, вырабатываемой формирователем 38 импульсов после поступления сигнала "Запуск интерполятора". Вход 17 блока 9 управления соединен с входом первого элемента ИЛИ 35, выход

55 которого подключен к управляющему С-входу D-триггера, выход которого — к выходу 32 блока 9 управления.

Сигнал "Начальная установка" служит для обнуления первого 36, второго 37, третьего 44, четвертого 45, шестого 53 О-триггеров, Сигнал "Начальная установка" поступает на вход 18 блока 9 управления, на

R-входы первого 36 и второго 37 0-триггеров и на первь",е входы третьего 41 и четвертого 42 элементов И.

Формирователь 38 импульсов служит для выработки импульсов, тактирующих работу блока 9 управления. Элемент И 39 совместно с инверсным выходом триггера 37 служит для выработки сигнала "Конец интерполяции". Элемент И 40 служит для формирования требуемой импульсной последовательности для накапливающего сумматора, Элемент И 43 служит для формирования требуемой импульсной последовательности стробирования значения на информационных выходах 23 и 24 интерполятора.

Триггеры 44, 45 и 53, элементы И 49 и

50, элемент ИЛИ 51 и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 52 служат для формирования адреса для коммутаторов 3 и 12. Сигнал на прямом выходе триггера 45 соответствует старшему разряду адреса коммутатора 12.

Сигнал на выходе элемента ИЛИ 51 соответствует младшему разряду адреса коммутатора 12. Сигнал на прямом выходе триггера 53 соответствует старшему разряду адреса коммутатора 3. Элемент ИЛИ 48 служит для управления второго коммутатора 6, Триггер 47 служит для хранения признака о принадлежности интерполируемого отрезка прямой й. конкретному полуоктанту.

Запись в триггеры 36, 47 и 53 осуществляется передним фронтом сигнала, поступающего на их управляющие С-входы. Запись в триггеры 3/, 44 и 45 осуществляется передним фронтом сигнала„поступающего на их управляющие С-входы.

В предлагаемом интерполяторе разрядность и регистров 5 и 10 совпадают. Максимальное значение К на единицу меньше значения максимального большего приращения (при БПмакс = 2" - 1, МПмакс - 1, М вЂ” и и

Кмакс =

М

2 -2), а разрядность большего приращения равняется разрядности меньшего приращения (БПмакс = 2 - 1;

МПмакс= БП 1 =2" 2 = Кмакс).

Максимальное значение остатка не превышает половины большего приращения, а следовательно, разрядность m регистра 2 равна n - 1, т. е. m = n — 1.

1693592

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

Пусть исходный отрезок прямой, заданный приращениями M и N, расположен в первом полуоктанте (М > О, N > О, М = 2N) с началом в точке с координатами (0,0), Отрезки прямых с приращениями М, N, принадлежащие второму полуоктанту (M > 0, N > О, M <2N), получают путем инвертирования значений интерполяционных шагов по ведомой координате при интерполировании дтрезка с приращениями N, (М - N), принадлежащего первому полуоктанту. Изменение знаков приращений и замена координатных направлений позволяют получить отрезки с любым расположением и ориентацией по отношению к координатным осям.

Указанные эквивалентные преобразования позволяют существенно упростить алгоритм интерполяции, сводя его только к аппроксимирующим действиям в первом полуокта нте.

Многоразрядное приращение (цифровой сегмент) длиной S определяет п = S - 1 единичных шагов перемещений по ведущей координате и следующее за ними диагональное перемещение. Последнее соответствует одновременной выдаче единичных шаговых приращений по ведущей и ведомой координатам, Исходный отрезок прямой может быть аппроксимирован цифровыми сегментами двух длин, отличающихся на единицу, значение которых находят вычисляя неравномерностные характеристики первого. порядка, которые для первого полуоктанта принимают вид: г1 = О,К = ((М - N)/N)q.4.

Параметр К определяет число элементарных шаговых приращений по ведущей координате, приходящихся на единичное перемещение по ведомой координате, а параметр г1=4 . — преобладание количества интерполяционных тактов, для которых шаговые приращения по ведомой координате не формируются, Для второго полуоктанта — r> -1.

N 1 N — h

2М 2 2М (3)

При нечетком К возможны два варианта центрирования многоразрядного приращения. При левом центрировании диагональ45 ный шаг формируется после (К + 1)/2 - 1 горизонтальных, а при правом — после (К+

+3)/2 - 1 горизонтальных шагов (фиг. 7).

Отклонение 4i от идеальной прямой при левом центрировании (фиг. 7а) опреде 50 ляется согласно выражению

N 1+ h

40 2М 2 2М (4) 55 1

2 М

При соответствующем выборе алгоритма следования цифровых сегментов только длиной (К+1) и (К+2) можно достичь погрешности аппроксимации, не превышающей шага дискретизации. Дальнейшее уменьшение модуля погрешности невозможно, поскольку параметр К находят путем выделения целой части отношения (M - N)/N при М Мй или N/(Ì - N) при М< 2N и дробная часть указанных отношений может приближаться к единице, Известно, что уменьшения погрешности аппроксимации можно достичь при цен5 трировании (симметричном размещении единицы среди нулей) в многоразрядном приращении (фиг. 61.

Отклонение д2 от идеальной прямой в точке (К + 1) при отработке первого много10 разрядного приращения (К+ 1) равно и N М вЂ” Й д2 =1 — — (К+1) =1- — (() „+

M М N

15 М М вЂ” N h

+1) =1 — — (— — +1) = —, (1)

M N N М где h — остаток от деления (М - N) íà N.

При отработке многоразрядного прира20 щения (К + 2) отклонение дз от идеальной

/. прямой в точке (К + 2) составляет д3 =1 — — (К+2)=1 — — (К+1) — =

N N N

М М М

h N h — N

M М M (2) Поскольку — < .,знаки

1 N 1

30 отклонений Bz и дз от идеальной прямой противоположные.

Значение погрешности аппроксимации д1зависит от четности или нечетности К. При четном K

35 д 1 N. К+2 1+(1 N. К+1 )

М 2 2 2 М 2 д1 =1 — — °

N К+1 1 — h/M

M 2 2

Из последнего вь.ражения следует, что при левом центрировании и нечетном эна-!

1693592

12 чении К модуль погрешности аппроксимации превышает половину шага дискретизации.

В случае правого центр!лрования откг онение д1 от идеальной прямой (фиг. 7б) равно

K+3 1 1 2 N — h (5)

2 M ". 2M

Поскольку 2N > h, то I дт ) - 1/2, Поэтому при нечетном K используют правое центрирование.

В общем случае для первого многоразрядного приращения длиной (K + 1) диагональный шаг формируют после ((К+ 1)/Яц.4 горизонтальных.

Обобщая выражения (3) !л (5), можно записать д 1 2 И вЂ” h (6)

2 2М где 7 --- 1 при нечетном К.

При четном К Z =- О.

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

К или (K !- 1). Зто позволяет интерполироьать воспроизведение отрезка прямой циф1! . выми сегментами с диагональными шагами. формируемыми в конце группы.

При этом аппроксимирующие преобразопания сводятся к следующему. Формируют первое многоразрядное приращение

Равным ((К + 1)/2)ц 4+ 1. Все послеДУюЩие приращения, за исключением последнего, принимают равным (К + 1) или (К + 2) в зависимости от результатов отслеживания отклонения аппроксим!лрующей точки от идеальной прямой. Последнее приращение принимают равным первому без генерации диагонального шага. Зто следует из свойства симметрии последовательности значений шаговых приращений по ведомой координате относительно своего центрального элемента при отклонении от идеальной прямой, не превышающем половины шага дискретизации, Исключение составляет случай для вектора с N =- 1 и четном M u h ==О, В этом случае, в сипу правого центрирования, последнее многоразрядное. приращение по ведущей координате на один элементарный шаг меньше по сравнению с первым многоразрядным приращением.

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

Обозначим через д1 отклонение от идеальной прямой после выполнения j-ro диагонального шага. Поскольку ордината точки

Х = К + 1 идеальной прямой смещена вниз относительно аппроксимирующего отрезка ! на величину 6z, то значение погрешности д) при замене j-го участка идеальной прямой

10 цифровым сегментом длиной (К+ 1) равно ! значению д;-< + ä, При аппроксимации цифровым гегментом длиной (К + 2) значение погрешности д1 находят путем вычита-! ния из погрешности д1-1 величины l дз I, 15 Учитывая указанный характер накопления погрешности д1, можно предложить следующий алгоритм линейной интерполяции, Первое многоразрядное приращение

2О формируют равным целой части отношения ((К+ 1)/2)ц 4+ 1. При этом погрешность аппроксимации после выполнения первого диагонального шага достигает значения д, Последовательно прибавляют значение д2 к д до момента выхода указанной, суммы за пределы допустимой погрешности, формируя в каждом интерполяционном такте многоразрядное приращение (К,+ 1), т. е. для . каждого j последоватепьно проверяется условие д1 + ) Ж:- 1/2, где j — число интерполяционных тактов после выдачи первого многоразрядного приращения.

С учетом выражений (1) и (6) последнее неравенство можно записать в виде

2 И вЂ” И Ь

2 2М М 2

После эквивалентных преобразований окончательно получают

h - -2 N + 2jh < О.

Таким образом, к значению h - 2 N последовательно прибавляют величину 2h до момента выхода суммы из отрицательной области, формируя в каждом интерполяционном такте многоразрядное приращение (K+ 1). В такте, соответствующем выполнению условия (7), формируют многоразрядное приращение (К + 2), что согласно выражению (2) обеспечивает уменьшение модуля погрешности на величину (N — h)/M.

Последнее эквивалентно вычислению из левой части неравенства (7) величины, (2N - h). Однако, поскольку прогнозирующее вычисление проводилось для многоразрядного приращения (К т 1), а формируется приращение (К + 2), то с целью коррекции результата из левой части неравенства (7) вычитают значение 2h+ 2(N — h) = 2N, Проце13

1693592

14 дуру коррекции можно совместить с вычислением значения следующего многоразрядного приращения, для чего к левой части неравенства (7) дополнительно прибавляют значение 2h. При положительном значении 5 результата формируют многоразрядное приращение (К + 1), в противном случае— (К+ 2), повторяя описанные вычисления.

Группы (К + 1) или (К + 2) формируют N раз, Последнее многоразрядное прираще- 10 ние принимают равным первому беэ генерации диагонального шага, за исключением случая, оговоренного ранее. Процесс интерполяции отрезка прямой на этом заканчивается. Граф-схема рассмотренного 15 алгоритма линейной интерполяции приведена на фиг. 3, где F — значение дополнительной функции, знак которой определяет длину цифрового сегмента на данном интерполяционном такте;с- признак,опреде- 20 ляющий Наличие или отсутствие в цифровом сегменте диагонального шага, причем при

С =Одиагональный шаг формируется; П (J>)— участок цифрового сегмента S(J<) до диагонального шага на J- интерполяционном 25 такте.

В соответствии с полученным алгорит мом предлагается структурная схема интерполятора (фиг, 1), Интерполятор работает следующим об- 30 разом, На второй информационный вход 16 устройства поступает значение меньшего приращения N, которое записывается в регистр.5 и блок 9 управления, активный уро- 35 вень сигнала записи — на входе 15. При этом в регистре 10 запоминается значение К,, где К = (.(М вЂ” N)/N J при М 2N;

К= (N/(M N) J приМ <2N, а также остаток h, получаемый внешним ус- 40 тройством при определении К, где h= M- KN npu M 2N;

h = N — K(N — M) и ри М < 2 N ..

Единичным уровнем сигнала на входе

15 осуществляется обнуление накапливаю- 45 щего сумматора 4, Передним фронтом сигнала на входе 15 в блоке 9 управления записывается признак, принимающий нулевое значение при М > 2N (первый полуоктакт), и значение логической единицы при 50

М< 2N (второй полуоктант). Единичным уровнем сигнала на входе 15 в счетчик 46 блока 9 управления записывается значение меньшего приращения N.

На выходе коммутатора 13 формируется 55 значение (К + 1)/2, получаемое на втором входе коммутатора 12. Для этого в сумматоре 11 к значению К прибавляется единица, т, е. формируется операнд (К + 1). Монтажным путем из операнда (К + 1) на в1ором. входе коммутатора 12 получают значение (К + 1)/2, которое является первым многоразрядным приращением исходного отрезка прямой. Значение операнда на выходе сумматора 8 определяет начальное значение оценочной функции F, которое передается в накапливающий сумматор 4 в зависимости от четности К:

F< = h — N при четном К;

F0 = h - 2N при нечетном К.

Это достигается следующим образом.

Младший разряд К, по значению которого судят очетности К,,поступает с информационного выхода регистра 10 на вход 30 блока

9 управления. При четном К на выходе 25 блока 9 управления формируется значение логической единицы, поступающей на управляющий вход коммутатора 6, что приведет к передаче значения N на вход 7 блока инверторов. С выхода блока 7 инверторов на вход сумматора 8 поступает обратный код N. Поскольку на вход сумматора 8 от регистра 2 поступает значение h, а на вход переноса — значение логической единицы, то на выходе сумматора 8 получают значение h — N. При нечетном К на выходе 25 блока управления формируется значение логического нуля, что приводит к передаче на выход коммутатора 6 значения 2N, Следовательно, на выходе сумматора 8 получают значение h — 2N, После указанных действий на выходе коммутатора 13 формируется многоразрядное приращение (К + 1)/2. От внешнего уст-. ройства на вход 17 интерполятора поступает сигнал "Пуск"., после чего в первом такте на третьем выходе 28 блока 9 управления формируется передний фронт импульса, позволяющий записать содержимое накапливающего сумматора 4 в его внутренний регистр (табл. 1). На выходе 21 интерполятора формируется передний фронт сопроводительного импульса, подтверждающий действительное значение многоразрядного приращения.

Начиная с второго интерполяционного такта, на выходе 25 блока 9 управления формируется значение логической единицы, которое обеспечивает значение на выходе блока 6 значения N. Следовательно, на выходе сумматора 9, начиная с второго такта, формируется значение (h — N). которое поступает на третий вход коммутатора 3. На второй вход коммутатора 3 со сдвигом влево на один разряд поступает значение (h — N), т. е. формируется знач..ние 2(h — N). К содержимому Накапливаюгцеro сумматора 4 прибавляется значение 2h, получаемое монтажным

1693592

16 путем на первом входе первого коммутатора 3, т. е, формируется значение

F1 = Fo+ 2h.

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

По знаку оценочной функции Р на выход коммутатора 12 передается одно из значений П(2) = К; П(2) = К+ I, Отрицательному значению оценочной функции F< соответствует приращение П(2) = К, а положительному — П(2) = К+ 1.

В дальнейшем оценочная функция вычисляется в соответствии со следующими соотношениями;

Fl+1 = F + 2h при FI <0;

Fi+1= Ft-2(N- h) при Fl =*О.

При F < О на выходе коммутатора 12. формируется операнд П = К, а при Fi О - П:=-K+ 1. -=" Операнды 2h, 2(N - h) суммируются соответственно на первом и втором входах коммутатора 3, а операнды П == К и П = К+" — на третьем и первом входах коммутатора

12. Значения оценочной функции определяются в накопительном сумматоре 4, С каждым интерполяционным тактам содержимое счетчика 46 блока управления уменьшается на единицу. При достижении им нулевого состояния на его выходе пер-,.носа формируется сигнал единичногс урсвня, указывающий о необходимости, выдачи последнего многоразрядногo прлращения, Согласно алгоритму работы последнее многоразрядное приращение может принимат ь одно из двух значений:

П(й + 1) =- П(1) - 1 и рл h = О, К - нечетное;

П(М + 1) = П(1) — в остальных случаях.

При h = О на выходе элемента ИЛИ i формируется сигнал нулевогс уровня, котсрый поступает на вход 26 блока 9 управления. При единичном уровне сигнала на входе 30 блока 9 управления на входах 34,л

31 формируются сигналы соответственна

1 нулевого и единичного уровней, что, в свою . очередь, приводит к передаче на выход коммутатора 12 значения j К/2)„т. е, П(1) - 1.

Во всех остальных случаях в последнем интерполяционном такте на входах 34 и 31 блока 9 управления формируются нулевые значения, что обеспечивает передачу на выход коммутатора 12 значения (Ki1)/2, т, е, П(1).

В последнем интерпсляционном так1е на выходе 32 формируется сигнал нулевсгс уровня, запрещающий формирование диа5

55 гонального шага при M 2 2N или горизонтального шага при М < N, Выдача шагов, приращений на выход коммутатора осуществляется в соответствии со значением признака, определяющего соответствие генерируемого отрезка первому или второму полуоктанту.

При г = О (признак принадлежности отрезка прямой первому полусктанту) на выход 23 выдается значение многоразрядногс приращения от коммутатора 12, а на выход

24 — значение логической единицы от первого входа коммутатора 13.

Следовательно, внешним устройством воспринимается цифровой сегмент, показанный на фиг. 11в.

При r = 1 (признак принадлежности отрезка прямой второму пслуоктанту) на выход 24 выставляется значение многоразрядного приращения от коммутатора 12, е на выход 23 — значение логической единицы с первого входа коммутатора i3. Внешним устройством воспринимается цифровой сегмент,. показанный на фиг. 11г.

Таким образом, информация на выходе

24,определяет число диагональных шагов, а на выходе 23 — горизонтальных шагов, Графсхема алгоритма работы интерполятора приведена на фиг, 3.

Рассмотрим работу блока 9 управления.

Для избежания гонок и состязаний npv. синтезе блока использован принцип единой врг, ленной организации.

В цикле подготовки в триггер 47 передним фронтом сигнала на входе 15 записи интерполятсра запоминается признак, определяющий принадле>кность интерполируемсго отрезка первому или второму полусктанту, r =. 0 — соответствует принадле>кности отрезка прямой первому пслуоктанту, а r = 1 -- второму, Единичное значение сигнала на входе

15 интерполятора производит запись меньшего приращения N в счетчик 46, а также устанавливает в нулевое состояние триггеры 44, 45 и 53.

Передним фронтом сигнала "Пуск" на входе 17 интерполятора разрешается работа интерполятора. В этом случае устанавливается в единичное состояние триггер 36.

При появлении после этого заднего фронта сигнала на выходе формирователя 38 импульсов григгер 37 устанавливается в единичное состояние, что разрешает прохождение импульсной последовательности от формирователя 38 на выход элемента 40, Укаэанные действия по запуску интерполятора обеспечивают присинхронизированную его работу к импульснсй последовательности от формирователя 38 после

55 поступления сигнала "Пуск" (передний фронт сигнала на третьем входе 17 интерполятора). Нулевое состояние сигнала на инверсном выходе триггера 37, поступающее через элемент 39 на выход 20 "Конец интерполяции", указывает о занятости интерполятора.

Рассмотрим формирование начального значения оценочной функции и засылку ее в накапливающий сумматор 4. Функция формируется нэ выход сумматора 8 в зависимости от четности К. Если К нечетное (его младший разряд равен единице), значение которого поступает на второй вход элемента ИЛИ 48, на его выходе 25 формируется логический нуль, значение которого на адресном входе коммутатора б обеспечивает передачу на его выход значения 2N, Если К вЂ” четное (его младший разряд равен нулю), в свою очередь, на выходе 25 формируется логическая единица, значение которой на адресном входе коммутатора 6 обеспечивает передачу на его выход значения N.

Таким образом, на выходе сумматора 8 формируется значение

Fo = h - N при четном К;

F0 = h - 2N при нечетном К.

На адресном входе первого коммутатора выставлен логический нуль, так как.григге р переноса сумматора 4 и триггер 53 блока управления обнулены. Единичное состояние триггера 37 обеспечивает прохождение импульсной последовательности нэ выход

28. В дальнейшем каждым передним фронтом указанной последовательности производится засылка суммы во внутренний регистр сумматора 4, В первом такте после сигнала "Пуск" (табл. 1) происходит засылка во внутренний регистр сумматора содержимого третьего входа первого 3 коммутатора (регистр сумматора обнулен в подготовительном цикле).

Последующил задний фронт импульса, поступающего с формирователя 38 импулосов, устанавливает триггер 44 в единичное состояние. В дальнейшем на третьем входе коммутатора 3 формируется значение h - N, а следовательно, на втором входе коммутатора 3 — значение 2(h — N). Значение логической единицы с выхода триггера 44 поступает на первый входэлемента ИЛИ 48, что приводит к появлению на выходе 25 блока 9 управления значения логической единицьг, которое будет неизменным втечение всего цикла интерполяции. Поскольку блоки 6 — 8 комбинационные, то указанные действия обеспечат формирование на втором входе блока 3 значение 2(h — N), которое необходимо дпя формирования последую5

50 цих после F< значений оценочной функции.

Fl {см. алгоритм).

Сформированная единица нэ прямом выходе триггера 44 приводит к появлению на выходе элемента 52 переднего фронта сигнала и устанавливает триггер 53 в единичное состояние, при этом старший разряд коммутатора 3 устанавливается в единичное состояние. В дальнейшем изменение адреса коммутатора 3 определяется сигналом переноса, поступающего с накапливающего сумматора 4, в соответствии с алгоритмом работы (табл, 1, фиг. 3).

Единичное состояние триггера 44 обеспечивает передачу импульсной последовательности от прямого выхода формирователя 38 импульсов через элемент 43 на выход 21, Передним фронтом сигнала на выходе 21 осуществляется стробирование многоразрядных выходных приращений на выходах 23 и 24 интерполятара.

Рассмотрим работу блока 9 управления при формировании цифровых сегментов, В первом интерполяционном такте триггер 45 обнулен сигналом "Пуск", а перенос накапливающего сумматора 29 равен нулю (так как происходит только первая засылка), поэтому на адресном входе коммутатора 12 выставлены нули. На выходе коммутатора

12 выставлен цифровой сегмент (К + 1)/2

{табл. 2).

Первым задним фронтом импульсной последовательности, поступающим с элемента И 43 триггер 45 устанавливается в единичное состояние, тэк как прямой выход. триггера 44 установлен в единичное состояние ранее. Единичное состояние триггера

45 изменяет старший адрес коммутатора 12 (устанавливает его B единичное состояние) и готовит элемент 52 для формирования переднего фронта импульса.

Все последующие значения цифровых сегментов, выставленных на выходе коммутатора 12, зависят от значения сигнала переноса сумматора 4. При нулевом значении сигнала переноса и отсутствии перекоса счетчика 46 (логический нуль) на выходе элемента 50 формируется уровень логического нуля, а следовательно, и на выходе 31 блока

9 управления. На выходе коммутатора 12 формируется цифровой сегмент К (табл. 2).

При единичном значении сигнала переноса сумматора 4 на выходе 31 формлруется уровень логическога нуля. На выходе коммутатора l2 формируется цифровой сегмент (К+1) (табл. 2).

С каждым при„одом заднего фронта импульса импульсной последовательности с выхода элемента И 43 содержимое счетчика

46 уменьшается на единицу. После поступ19

1693592

35 ления N тактов на вычитас щий вход счетчика 46 íà его выходе формируется сигнал переноса (логическая единица), передний фронт которого поступает на вход элемента

ИЛИ 35. Следовательно, ка выходе элемента ИЛИ 35 формируется передний фронт импульса, который устанавливает триггер

36 в нулевое состояние, (так как на Э-входе выставлен логический нуль). На прямом выходе триггера 36 устанавливается логический нуль. Сигнал логического нуля с выхода 32 поступает на младший разряд первого входа коммутатора 13. Следовательно, в последнем интерполяционном такте отсутствует диагональный шаг. Импульс переноса счетчика 46 поступает через элемент И 42 и устанавливает В нулевое состояние триггер 45, à -акже выставляет на выходе элемента И 50 значение логического нуля.

В последнем интерполяционном такте при нечетном К, остатке h = О и единичном состоянии переноса счетчика на выходе элемента 31 формируется сигнал единичного уровня, следовательно, на адресном входе коммутатора 12 формируется адрес АО, равный значению логической единицы, Старший разряд А1 равен значению логического нуля, так как триггер 45 oÁíóëeí р "íåå. Указанное приводит к выдаче»=-" выходе коммутатора 12 эначекия П® = (К+1)12 - i, В

I .ротивном случае на входе младшего разряда адреса коммутатора 12 сигнял равен ну лю, Указанное приводит к выдаче ка выходе ,коммутатора 12 зкачения "lg) (К+ I)/2, Каждое значение цифровых сегментов, выставленное на выходах 23 и 24, сопровождается передним фронтом стробирующего импульса, формируемого на выходе элемента 43.

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

1. Цифровой линейный интерполятар, содержащий регистр остатка, регистр меньшего приращения, первый и выходной коммутаторы, блок управления, первый двоичный и накапливающий сумматоры, информационные входи регистра остатка и регистра меньшего приращекия являются соответственно первым и вторым информационными входами иктерполятсра, вход записи интерполятора соедикен с входом записи регистра остатка и регистра меньшеГо приращения, пуск интерполятора соединен с первым входом блока управления, первый выход блока управления подключен к управляющему входу накапливающего сумматора, второй выход блока управления подключен к выходу конца интерполяции интерполятора, третий выход блока управления подключен к стробирующему выходу интерполятора, группа икформационных выхбдов выходного коммутатора под«лючена к выходам цифрового сегмента интерполятора, отличающийся тем, что, с целью повышения точности, введены второй и третий коммутаторы, регистр многоразрядного приращения, второй двоичный сумматор, блок инверторав, блок выделения нуля, выход которого подключен к второму входу блока управления, вход блока выделения нуля соединен с, выходом регистра остатка и с первым входом первого двоичного сумматора, второй вход которого соединен с выходом блока инверторов, а вход переноса — с выходом логической единицы интерПОлятоаа, выход перВОГО дВОичнОГО сумматора подключен к первой и второй группам информационных входов neoeoro коммутатора, причем во второй группе информационных входов коммутатора каждый (1+1)-й разряд подключен к 1-разрядному выходу перваго двоичного сумматора, i = 1, и, где и — разрядность информационной шины первого сумматора, младший разряд второй группы информационных входов первого коммутатора подключен к общей шине, Группа информационных входОВ кОтОрОГО

;юдключека к выходу реп стра, остатка, паичем каждый!-й разряд выхода регистра остат. а подключен к (i+1)-му разряду третьей гру .пы входов первого коммутатора, i =

=,, m. 1-де m — разрядность информационной шины регистра остатка, младший разрял третьей группы информационных входов первого ксммутатора подключен к общей шине, группа вы" îäîâ первого коммутатора подключена к группе входов накапливающего сумматора, вход переноса которого подключен к общей шине., à R-вход сброса подключен к входу записи интерполятора, к третьему входу блока управления и к управляющему входу регистра многоразрядныхх приращений, вход KoTopofо соединен с входом цифровога сегмента интерполятора, а выход — с группой информационных входов второго двоичного сумматора и с первой и второй группами информационных входов третьего коммутатора, причем каждый i-й разряд четвертой группы информационных входов третьего коммутатора подключен к (1 + 1)-му разряду регистра многоразрядных приращений, i = 1, n - 1, где и — разрядность информационной шины регистра многоразрядных приращений, третья и четвертая группы информационных входов третьего коммутатора подключены к выходу второго сумматора, причем каждый 1-й.разряд чет21

1693592

10

55 вертай группы информационных входов третьего коммутатора подклачен к (!+1)-му разряду второго сумматора, i = 1, и - 1, где и — разрядность информационной шины второго сумматора, младший разряд четвертой группы информационных входов первого коммутатора подключен к общей шине, а вход переноса подключен к выходу логической единицы: старший и младший разряды адресного входа третьего коммутатора г.одключены соответственно к четвертому и пятому выходам блока управления, четвертый вход которого подключен к младшему разряду регистра многоразрядных приращений, шестой выход блока управления подключен к младшему разряду первой группы информационных входов выходного коммутатора, старшие разряды которой подключены к общей шине, вторая группа информационных входов выходного коммутатора подключена к группе выходов третьего коммутатора, адресный вход выходного коммутатора соединен с седьмым выходом блока управления, восьмой выход которого подключен к адресному входу второго коммутатора, группа выходов которого подключена к группе входов блока инверторов, а первая и вторая группы информационных входов — к разрядным выходам регистра, меньшего приращения, причем каждый 1-й разряд регистра меньшего приращения соединен с (i+1)-м разрядом первой группы информационных входов второго коммутатора, i = 1, и, где и — разрядность первой группы информационных входов второго коммутатора, младший разряд которой соединен с общей шиной. девятый выход блока управления подключен к старшему разряду адресного входа первого коммутатора, младший разряд адресного входа которого соединен с выходом знакового разряда накапливающего сумматора и с пятым входом блока управления, шестой и седьмой входы которого подключены соответственно к входу начальной установки и входу признака интерполятора, информационный вход блока управления соединен с.входом меньшего приращения интерполятора.

2, Интерполятор по и. 1, о т л и ч а юшийся тем, что блок управления содержит с первого по шестой О-триггеры, семь элементов И, первый, второй и третий элементы ИЛИ, счетчик, формирователь импульсов, элемент ИСКЛЮЧАЮ.ЩЕЕ ИЛИ, выход которого подключен к управляющему С-входу первого D-триггера,инверсный выход которого подключен к информационному 0-входу первого 0-триггера, прямой выход которого подключен к девятому выходу блока управления, седь15

45 мой выход которого соединен с прямым вы-,,ходом второго D-триггера, информационный 0-вход которого подключен к седьмому входу блока управления, восьмой вход которого подключен к управляющему С-входу второго О-триггера, к управляющему $-входу счетчика и к вторым инверсным входам первого и второго элементов И, шестой вход блока управления соединен с инверсными

R-входами третьего и четвертого О-триггеров и с первыми входами первого и второго элементов И, выход первого элемента И подключен к инверсным R-входам пятого и первого О-триггеров; первый вход блока управления подключен к первому входу первого элемента ИЛИ, выход которого соединен с управляющим С-входом третьего D-триггера, инверсный выход которого подключен к информационному D-входу третьего триггера, прямой выход которого соединен с информационным 0-входом четвертого триггера и с шестым выходом блока управления, восьмой выход которого подключен к выходу второго элемента ИЛИ, первый вход которого соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, прямым выходом пятого триггера. с информационным

0-входом шестого триггера и с.вторым входом третьего элемента И, первый вход которого подключен к прямому выходу формирователя импульсов, инверсный выход которого соединен с втооым входом четвертого элемента Yi, управляющим

С-входом четвертого D-триггера и с управляющим С-входом пятого D-триггера, управ-. ляющий D-вход которого подключен к первому входу четвертого элемента И и к прямому выходу четвертого триггера, инверсный выход которого соединен с первйм входом пятого элемента И, инверсный вход которого соединен с выходом третьего элемента И, третьим выходом блока управления, управляющим С-входом счетчика и с управляющим С-входом шестого триггера, прямой выход которого подключен к второму входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и к четвертому выходу блока управления, четвертый вход которого соединен с инверсным вторым входом второго элемента ИЛИ и с первым входом шестого элемента И, выход которого соединен с первым входом третьего элемента ИЛИ, выход которого подключен к пятому выходу блока управления, второй вход которого соединен с инверсным вторым входом шестого элемента

И, третий вход которого соединен с вторым инверсным входом седьмого элемента И, третьим инверсным входом второго элемента И, вторым входом первого элемента ИЛИ и выходом счетчика, информационный вход

1693592

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

5 ИЛИ.

1693592

Т5 I7

I !

ПрямоР вмхох элемента 38

Инверскь Р выход элемента 36

Прямой выход элемента Зб

Прямой выход элемента _#_

Выход элемента 4О

Прямой выход элемента 44

Выход элемента 52

Выход элемента 46

1693592

1693592

ПриА=7 О=С прц,4=0 8=8

1693592

1693592

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

Техред М. Моргентал

Корректор В. Гирняк

Редактор А. Козориз

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 4078 Тираж Подписное

ВНИМАЙ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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