Линейный аппроксиматор

СОЮЭ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 11 606 Г ЕТЕН ГОСУДАРСТВЕНЯЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОУНРЬЩ 4 Й(56) Авторское свидетельство СССР Р 257150, кл. Р 06 Г 15/353, 1969,Авторское свидетельство СССР 9 696498, кл, С Об Г 15/353, 1979. (54)(57) ЛИНЕЙНЬЙ АЛПРОКСИИАТОР, соДержащий входной регистр и блок унравлеиия, причем информационные входы анпроксиматора подключены к входам входного регистра, о т л и - ч а ю щ и й с я тем, что, с целью повышения быстродействия, в него введены блок памяти, буферный регистрР блок сравнения длины и блок сравнения линий, причем блок управления содержит регистр коэффициента наклона, реверсивный счетчик коэффициента наклона, два триггера, два ключа генератор тактовых импульсов, элемент И и элемент ИЛИ, причем вход запуска аппроксиматора соединен с входом установки в "1" первого триггера, прямой выход которого соединен с входом запуска генератора тактовых импульсов и первым информационным входом первого ключа, а первый выход первого ключа соединен с выходом синхроимпульса выдачи коэффициента наклона аппрокснматора и входом опроса регистра коэффициента накло- . на, выходы которого соединены с выходами коэффициента наклона апнроксиматора и информационными входами реверсивного счетчика коэффициента наклона, выходы которого подключены к информационным входам. регистра коэффициента наклона, инверсный выход первого триггера соединен с вторым информационным входом первого ключа, второй выход которогосоединен с управляющим входом второго ключа, первый и второй выходы которых соединены соответст енно с входом суммирования и входом вычитания реверсивного счетчика коэффициента наклона, управляющий вход которого подключен к выходу элемента ИЛИ блока управления, выход первого такта генератора тактовых импульсов соединен с первым входом элемента ИЛИ блока управления и.входом установки в единицу второго триггера, прямой и инверсный выходы которого соединены соответственно с первым и вторым информационными входами второго ключа, инверсный выход, первого триггера подключен к первому входу элемента И, выход которого соединен с вторым входом элемента ИЛИ блока управления и с выходом сигнала окончания работы аппроксиматора блок сравнения линий содержит регистр начального смещения и матрицу из И 111 (где И=2 д+1, й - предельное отклонение линий, И - число разрядов) трехканальных демультиплексоров, причем информационные входы регистра начального смещения соединены с входом начального смещения аппроксиматора, первый вход опроса регистра начапьного смещения соединен с выходом второго такта генератора тактовых импульсов, выход третьего такта которого соеди1157548 Составитель А,ЧекановБобкова Техред Ж.Кастелевич едак Подпистета СССРкрытийнаб., д. 47 710 е Т каз Госуда енного ко ений и Раушск елам изоб осква, ЖФилиал ППП нПатент", г. Ужгород роектная 73/48ВНИИПИпо3035,орректор С.Черни ее т1 157548 нен с управляющим входом первогоключа, выход четвертого такта генератора тактовых импульсов. соединенс вторым входом элемента И и вторымвходом опроса регистра начальногосмещения, 1 -й (=1,М) выход которого соединен с информационнымвходом (1, 1).-го трехканальногодемультиплексора, первый выход(,)-го трехканального демультиплексора (=2,М=1,Ж) объединенс вторым выходом (-1,)-го итретьим выходом (-2,)-го трехканальных демультиплексоров и подключен к информационному входу (-1,5+1) го трехканального демультиплексора, блок сравнения длины содержитсумматор-вычитатель длины отрезкааппроксимации, группу элементов ИЛИи элемент ИЛИ, причем первый выход(1, 1 )-го (у=Г,У) трехканального демультиплексора соединен с первымвходом-го элемента ИЛИ группывыход которого соединен с информационным входом (Ю- )-го разрядасумматора-вычитателя длины отрезкааппроксимации, информационные выходы которого соединены с выходами Изобретение относится к вычисли- . тельной технике, к устройствам обработки информации.Цель изобретения - повышение быстродействия.На фнг.1 представлена блок-схема аппроксиматора; на фиг.2 - функциональная схема блока сравнения линий; на фиг.З - функциональная схема блока сравнения длины; на Фиг.4 - функциональная схема блока управлениями на фиг.5 - карта состояния ячеек накопителя, на Фиг,б - графики, поясняющие работу аппроксиматора, на фиг.7 - блок-схема работы аппроксиматора.Аппроксиматор состоит из блока.1 памяти, блока 2 сравнения линий, блока 3 сравнения длины, входного регистра 4, буферного регистра 5 и блока б управления. Вход 7 служит для начального значения коэффициента наклона аппроксимирующей прямой, вход 8 - для смещения ее начальной точки,длины отрезка аппроксиматора, а знаковый выход подключен к входу установки в ноль первого триггера, третий выход (М, )-го (1=1,В трехканального демультиплексора соединенс вторым входом 7 -го элемента ИЛИгруппы и 1 -м входом элемента ИЛИблока сравнения длины, выход которого подключен к входу установки вноль второго, триггера, выходы второго, третьего и четвертого тактов генератора тактовых импульсов соединены соответственно с входом установки режима вычитания, входом сброса и входом установки режима сложения сумматора-вычитателя,длины отрезка аппроксимации, выходы реверсивного счетчика коэффициента наклона соединены с входами блока памяти, выходы которого соединены с входами буферного регистра, -й выходвходногорегистра соединен с первымиадресными входами (,1)-х (1=Г,Й)трехканальных демультиплексоров,-йвыход буферного регистра соединен свторым адресными входами (,)-х( =Т,М) трехканальных демультиплексоров. 2вход 9 - для аппроксимируемой кривойв виде последовательности единичных приращений (фиг.б).Вход 1 О является входом запуска э. аппроксиматора, выход 11 - выходомсинхроимпульса выдачи коэффициентанаклона, выходы 12 - 3 -выходамидлины отрезка аппроксимации. Сигнал"Конец работы" выдается на выходе 13.10 Информационными входами блока 2сравнения линий являются входы 14 й 15, вход 16 опроса блока 2, выходы18 и 19 блока 2, входы 20-22 блока 3 1 сравнения длины и его выходы 23 и 24,а также входы 25 и 26 блока 6 управления и его выходы 17 и 27,Блок 2 сравнения линий содержит(фиг.2) регистр 28 начааьного смеще 20 ния и матрицу МЧ трехканальныхдемультиплексоров 29, где Й - числоразрядов, а М=2 ь+1, Ь - предельноеотклонение линий.%Блок 6 управления (фиг.4) содержит управляемый генератор 33 тактовых импульсов (ГТИ), триггер 34включения, триггер 35. знака погрешности, ключи 36 и 37, элемент ИЛИ 1038, элемент И 39, формирователь 40,регистр 41 коэффициента наклона,реверсивный счетчик 42 коэффициентанаклона. В блоке 6 управления(Фиг.4) вход установки в единицу 15триггера 34 включения соединен с входом 10 запуска аппрокеиматора,Прямой выход триггера 34 соединен с входом запуска ГТИ 33 и первыминформационным входом ключа 36, 20управляющий вход которого соединенс выходом третьего такта ГТИ 33.Первый выход ключа 36 соединен с выходом 11 синхроимпульса выдачи коэффициента наклона аппроксиматора и Ивходом опроса регистра 41 коэффици"ента наклона, выходы которого соединены с входами 7 коэффициента наклона аппроксиматора и информационнымивходами реверсивного счетчика 42 З 0коэффициента наклона. Выходы последнего подключены к информационныивходам регистра 41 коэффициента наклона.Инверсный выход триггера 34 включения соединен с вторым информационным входом перэбго ключа 36, второй выход его соединен с управляющим входои второго ключа 31, первыйи второй выходы которого соединены 40соответственно с входами суммирова,ния и входом вычитания реверсивногосчетчика 42 коэффициента наклона.Управляющий вход счетчика 42 подключен к выходу элемента ИЛИ 38. Выход 45четвертого такта ГТИ 33 соединен свторым входом элемента И 39, а выход первого такта ГТИ 33 подключенк первому входу элемента ИЛИ 38 и квходу установки в единицу триггера 35, Прямой и инверсный выходытриггера 35 соединены соответственно с первым и вторым информационнымивходами ключа 37Инверсный выход триггера 34 под- Зэключен к первому входу элеиекта И.39, выход которого соединен с вторымвходом элемента ИЛИ 38 блока 6 управ 548 4ления и с выходом 13 сигнала оконч ани я р аботы аппроксиматор а.В блоке 2 сравнения линий (фиг,2) информационные входы регистра 28 начального смещения соединены с входом 8 начального смещения аппроксиматора, Первый и второй входы опроса регистра 28 через группу входов 16 блока 2 и группу выходов 11 блока 6 управления соединены соответственно с выходами второго и четвертого тактоэ ГТИ 33,.-й (1 =1,М) выход регистра 28 соединен с информационными входом (,1)- го трехканального демультиплексора 29. Первый выход (,)-го трехканельното лентльтнллексора 29 ( =2,М-), ) =ф/) обьелннек с вторьн выходом (-1 р 1)-го и тРетьим выходом (-2,)"го трехканальных демультиплексоров 29 и подключен к йнформационному входу ( -1, 1+1)-го трехканального демультиплексора 29.Пер вью выход (1 р 1 ) -го (1 = 1, й ) трехканального демультиплексора 29 через выход 19 блока 2 сравнения линий и вход 21 блока 3 сравнения длины соединен с,первым входом 1 -го .элемента ИЛИ группы 31. Третий вьгкод (Мр 1 )-го О =1,ЬГ) трехканального демультиплексора 29 через выход 18 блока 2 сравнения линий и вход 20 блока 3 сравнения длины соединен с вторым входом-го элемента ИЛИ группы 31 и-м входом элемента ИЛИ 32 блока 3 сравнения длины.Кроме того, в блоке 3 выход 1 -го элемента ИЛИ группы 31 соединен с информационным входом (й-,1)-го разряда сумматора-эычитателя 30 длины отрезка аппроксимации, информационные выходы которого соединены с выходами 12 длины отрезка аппрокси" мацин аппроксиматора, а знаковый выход через выход 23 блока 3 сравнения и вход 25 блока 6 управления подключен к входу установки в ноль триггера 34Выход элемента ИЛИ 32 через аэыход 24 блока 3 и вход 26 блока 6 управления соединен с входом установки в воль триггера 35. Выходы второго, третьего и четвертого тактов ГТИ 33 через группу выходов 17 блока 6 управления и группу входоэ 22 блока 3 сравнения длинь 1 соединены соответственно с входом установки режима эычитания, входом сброса и входомустановки режима сложения сумматоравычитателя 30 длины отрезка аппроксимации. Выход Формирователя 40 че-. рез группу выходов 17 блока б управления и группу входов 22 блока 3сравнения длины соединен с входом установки в единицу Й-го разряда сумматора-вычитателя 30 длины отрезка аппроксимации.Выходы реверсивного счетчика.42 Я коэффициента наклона через выходы 27 блока б управления соединены с входами блока 1:памяти, выходы которого соединены с входами буферного регистра 5. 15Информационные входы входного регистра 4 соединены с входом 9 аппроксимируемой кривой,-й выход входного регистра 4=1,И) через вход 14 блока 2 сравнения линий со О единен с первыми адресными входами (1,)-х (=-1,И) трехканальных демультиплексоров 29, а 1 -й выход буферного регистра 5 через вход 15 блока 2 сравнения линий соединен с Й 5 вторыми адресными входами О 1)-х (а =Г,И) трехканальных демультиплексоров 29.Блок 1 памяти представляет собой накопитель запоминающего устройства, ЗО в котором в единичном состоянии находятся 2 т; ". хК)-е р аарадяые ячейки (К=-1,2 ф ), где- номер адреса накопителя, а 0 - разрядность счетчика 42, Таким образом, данные ЗЗ коды зависят только от количества разрядов коэффициентов наклона интерполирующей прямой, но не зависят от его нида и длины прямой,.т.е. данные коды являются универсальными, 49 и может быть использован накопитель постоянного запоминающего устройства.Если каждому разряду поставить в соответствие шаг по Х, а шаги по У делать в том случае, когда в 43 данном разряде содержится единица, то для -го адреса получаем ступенчатую, которая интерполирует прямую, имеющую коэффициент наклона, равный двоичной дроби вида 0,0001,М где единица находится на О.-м месте после запятой.Последовательность импульсов интерполирующая прямую, коэффициент наклона которой не является простой 55 дробью, можно получить, суммируя описанные последовательности. па- пРимеР р Для ПРЯмой с наклоном О, 10110 надо логически сложить по= следовательности, записанные в пер. вом, третьем и четвертом адресах, т.е, одновременно считать эти адреса, Таким образом, блок 1 памяти Формирует сразу всю последовательность интерполирующих импульсов.Работу аппроксиматора рассмотрим на конкретном примере,Пусть Н =23, тогда блок 1 памяти,буферный регистр 5, входной регистр4 и блок 2 сравнения линий имеют23 разряда, а сумматор-вычитатель30-24 разряда, счетчик 42 и регистр41 коэффициента наклона " по 5 разрядов, Пусть максимальная погрешность равна двум, тогда количество разрядов регистра 28 начального смещения, равное количеству адресов блока 2 сравнения линий, равно пяти.Пусть начальное смещение равно 2, т,е. записана единица в первом разря". де регистра 28. Аппроксимируемая кривая 1 записывается в регистр 4 в виде последовательности единичных приращений (фиг.б). Так как ее суммарное приращение равно девяти, всчетчик 42 в качестве начального значения записывается число 0,01010.Далее поступает сигнал на вход 10 запуска аппроксиматора, который устанавливает в единицу триггер 34 включения. Сигнал с его выхода разрешает работу ГТИ 33, который формирует тактовые сигналы, начиная с первого. Кроме того, на выходе формирователя 40 Формируется сигналначальной установки, который записывает единицу в старший разряд сумматора-вычитателя 30,Импульс первого такта, пройдя через элемент 38, поступает на опрос счетчика 42 (фиг.7), вследствие чего число 0,01010 переписывается в регистр 4 1 и считываются второй и четвертый адреса блока 1 памяти. В регистр 5 записывается 23-раэрядная последовательность единичных прира" щений, соответствующая прямой с наклоном 0,01010 (последовательность а, фиг.б) .Вторым тактом Опрошен регистр 28.Импульс с его первого разряда поступает на соответствующий трехканальный демультиплексор 29 блока 2 сравнения линий. Так как в первом разряде последовательностей а и 1 находятся нули, импульс проходит навторой выход демультиплексора 29первого разряда первого адреса блока 2 и оттуда на вход демльтиплексора 29 нторо."о разряда первого адреса (кривая 1 , Фиг.б), Во второмразряде имеется единица н последовательности Г, поэтому импульс переходит на второй адрес блока 2, Втретьем разряде имеется единица в последовательности , следовательно 6импульс переходит на первый адресблока 2, и так до пятого разряда,после которого импульс поступае навыход 18 блока 2 сравнения линий(фиг,б). Таким образом, в этом бло- дке путь прохождения импульсов опросаповторяет кривую погрешности и заканчивается там, где погрешность по абсолютному значению больше й, В данном случае погрешность отрицательна,импульс Формируется на пятом выходе18-й группы, поступает на группу входов 20 блока 3 сравнения длины(Фиг.З) и через Функциональную группу 31 элемента ИЛИ на вход соответ- уствующего разряда сумматора-вычитателя 30, а через элемент ИЛИ 32 навыход 24,Заметим, что разряды сумматортвычитателя 30 расположены н обратном 30порядке (сверху старший разряд), е,е.выход последнего разряда блока 2подключен к входу младшего разрядасумматора-вычитателя 30, выходпредпоследнего разряда блока. 2 "к входу второго разряда сумматоравычитателя 30, и т.д. до ньжодапервого разряда блока 2 (слева,Фиг.2), которь 1 й подключен хвходу старшего разряда сумматора- рвычитателя 30.Блок 3 сравнения длины работаетследующим образом.Место, н котором погрешность превышает ь, запоминается н виде еди ницы, записанной н соответствующий разряд счетчика-. вычитателя 30. При следующем варианте аппроксимирующего отрезка сумматор-вычитатель ЗО переводится в режим вычитания. Если И длина отрезка, н котором погрешность находится в пределах нормы, увеличивается, то из имеющихся чисел вычитается число, содержащее единицу в более младшем разряде (более ниж нем), и в результате получается положительное число, т.е. ноль н знаковом разряде сумматора-нычитателя 30 обнуляется и повторяется опрос блока 2 сравнения линий (Фиг.7), Но- сумматор-вычитатель 30 в это время переведен н режим сложения, поэтому импульс с блоха 2 записывается в сумматор-вычитатель 30 и, тем самым, запоминается новая дтина отрезка аппроксимации. Таким образом блок 3 сравнения осуществляет сравнение длин текущего и предыдущего отрезков аппроксимации и запоминает текущий, . если он больше предыдущего, т.е. выбирается лучший вариант аппроксимирующей прямой. 0 том, что текущий вариант хуже предыдущего (длина, погрешность которой не выходит за дрпустимые пределы стала меньше) сигнализирует появление единицы в знаковом разряде сумматора-вычитателя 30Возвращаясь к уримеру, запомним, что в качестве начальной установки сумматора-нычитателя 30 была записана единица в его старший разряд. С блока 2 сравнения линий поступает импульс на пятый от старшего разряд, Это происходит но время действия второго такта, который из ГТИ 33 поступает на нход установки режима вычитания суьратора"вычитателя 30.Так как при вычитании получилось положительное число, триггер 34 остается н единичном состоянии, Триггер 35 знака первым тактом уст:нонлен в единичное состояние. При сравнении линий гогрешность выходит за нижнюю границу, импульс Формируется на пятом разряде группы выходов 18 и поступает на вход 20 блока 3. В этом случае появляется импульс на выходе элемента ИЛИ 32, поступает на вход 26 блока 6 и устанавливает в ноль триггер 35.Таким образом, триггер 35 является триггером знака погрешности. При данном состоянии триггеров 34 и 35 импульс третьего такта с выхода ключа 36 поступает на вход ключа 37, а с его выхода на вход вычитания единицы реверсивного счетчика 42 что изменяет коэФФициент наклона прямой, который ранен 001001, Кроме того, такт, всегда обнуляет сумматор-нычитатель 30. Все это соответствует алгоритму (Фиг.7).Четвертым тактом (Фиг,) проведен второй опрос блока 2 сравнения линий по входу 16 (Фиг,2), но при этом9. 11575сумматор-вычитатель 30 блока 3 нахо.дится в режиме сложения, так какна его вход установки режима сложения поступает четвертыи такт ГТИ 33,А так как в третьем такте сумматор-вычитатель 30 обнулен, в нем записывается единица в пятом от старшегоразряде,Далее снова следует опрос блокапамяти (фиг,7) и в буферном регист ре 5 записывается последовательностьединичных приращений, соответсвующая прямой В на графике У=0(Х)(фиг,6) . При опросе блока 2 импульспроходит по пути, соответствующемуварианту кривой 3 (фиг.6). Погрешность выходит за пределы отрицательно о допуска, поэтому по сигналу свыхода 24 блока 3 триггер 35 установлен в ноль, и число в счетчике 42 рркоэффициента наклона опять уменьшается на единицу и равно 0,01000. юЗто соответствует варианту(фиг.6). Здесь погрешность выходитза пределы положительного допуска, д .поэтому импульс с блока 2 поступаетна один из входов 21 группы и неФормирует импульс на выходе 24 бло,ка 3 сравнения длины. Триггер 35остается в единичном состоянии ипо импульсу с выхода ключа 37 со о,ержимое счетчика 42 коэффициентанаклона увеличивается и равно 0,01001. В этом случае при опросе блока 2 во втором такте из числа записанногоЮЭ в сумматоре-вычитателе 30, вычитается большее, что приводит к изменению знакового разряда сумматора" вычитателя 30 и, следовательно, к48 10 появлению импульса на входе 25 блока 6 и к установке н ноль триггера 34.В результате этого третий такт с выхода ключа 36 поступает на выход 11 синхроимпульса выдачи коэффициента блока 6 и на вход опроса регистра 41 коэффициента наклона. При этом содержимое регистра 41, предыдущее значение коэффициента наклона, переписывается в счетчик 42 и Формируется на входе 7 аппроксиматора для записи его во внешние устройства. Переключение триггера 34 приводит к тому, что четвертый такт с выхода элемента И 39 поступает на выход 13 сигнала окончания работы аппроксиматора и через элемент ИЛИ 38 на опрос счетчика 42. Кроме того, этот же такт, как и раньше, опрашивает блок 2 сравнения линий с переводом сумматора-вычитателя ЗО в режим сложения.По сигналу с выхода 11 аппроксиматора выведено найденное наилучшее значение коэффициента наклона аппроксимирующего отрезка, содержащееся в регистре 41 и счетчике 42 коэффициента наклона, а длина отрезка, представленная в позиционном коде в сумматоре-вычитателе 30, может быть считана в любой момент после формирования сигнала "Конец" на выходе 13 аппроксиматора.Таким образом, за четыре цикла работы аппроксиматора (16-ть тактов) определена максимально возможная длина аппроксимации исходной кривой с заданной погрешностью и найдены параметры аппроксимирующего отрезка,