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

 

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

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

РЕСПУБЛИК

41Рц G 06 F 15/353

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

r1G ДЕЛАМ ЙЗОЬРЕТЕНИЙ И ОТКР} и ИЙ

У (21) 3557788/24-24 (22) 23.02.83 (46) 23.05 ° 85. Вюл. Р 19 (72) В.И.Ткачев (71) Ленинграпское научно-производственное объелинение "Буревестник" (53) 681. 32 (088. 8) (56) Авторское свидетельство СССР

Р 257150, кл. F 06 F.15/353, 1969.

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

Р 696498, кл. С Об F 15/353, 1979. (54)(57) ЛИНЕЙНЬЙ АЛПРОКСИИАТОР, соДержащий входной регистр и блок унравлеиия, причем информационные входы анпроксиматора подключены к входам входного регистра, о т л и— ч а ю шийся тем, что, с целью повышения быстродействия, в него введены блок памяти, буферный регистр

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

„„SU„„È 57548 реверсивного счетчика коэффициента наклона, выходы которого подключены к информационным входам. регистра коэффициента наклона, инверсный выход первого триггера соединен с вторым информационным входом первого ключа, второй выход которого соединен с управляющим входом второго ключа, первый и второй выходы которых соединены соответст енно с входом суммирования и входом вычитания реверсивного счетчика коэффициента наклона, управляющий вход Ro торого подключен к выходу элемента

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

ИЛИ блока управления и с выходом сигнала окончания работы аппроксиматора, блок сравнения линий содержит регистр начального смещения и матрицу из H N (где И=2 +1, 6- предельное отклонение линий, И вЂ” число разрядов) трехканальных демультиплексоров, причем информационные входы регистра начального смещения соединены с входом начального смещения аппроксиматора, первый вход опроса регистра начапьного смещения соединен с выходом второго такта генератора тактовых импульсов, выход третьего такта которого соеди1157548 нен с управляющим входом первого ключа, выход четвертого такта генератора тактовых импульсов. соединен с вторым входом элемента И и вторым входом опроса регистра начального смещения, < -й (» =1,И) выкод которого соединен с информационным входом (1, 1).-го трехканального демультиплексора, первый выход (»,j)-го трехканального демультиплексора (»=2,N-1,1 1,1)} объединен с вторым выходом (i-1, j )-го и третьим выходом (»-2,j)-ro трехканальных демультиплексоров и подключен к информационному входу (f-1, j+1) rо трехканального демультиплексора, блок сравнения длины содержит сумматор-вычитатель длины отрезка аппроксимации, группу элементов ИЛИ и элемент ИЛИ, причем первый выход (1, 1 )"го (j =Ã,7) трехканального демультиплексора соединен с первым входом » -го элемента ИЛИ группы, выход которого соединен с информационным входом (hl» »j)-ro разряда сумматора-вычитателя длины отрезка аппроксимации, информационные выходы которого соединены с выходами

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

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

На фнг.1 представлена- блок-схема аппроксиматора, на фиг.2 — функциональная схема блока сравнения линиИ; на фиг.3 — функциональная схема блока сравнения длины, на фиг.4 — функциональная схема блока управления, на фиг.5 — карта состояния ячеек накопителя; на фиг.6 — графики, поясняющие работу аппроксиматора, на фиг. 7— блок-схема работы аппроксиматора.

Аппроксиматор состоит из блока.1 памяти, блока 2 сравнения линий, блока 3 сравнения длины, входного регистра 4, буферного регистра 5 и блока 6 управления. Вход 7 служит для начального значения коэффициента наклона аппроксимирующей прямой, вход

8 — для смещения ее начальной точки, длины отрезка аппроксиматора, а знаковый выход подключен к входу установки в ноль первого триггера, третий выход (M 5 ) го (1=1,@ трехканального демультиплексора соединен с вторым входом $ --го элемента ИЛИ группы и 1 -м входом элемента ИЛИ блока сравнения длины, выход которого подключен к входу установки в ноль второго, триггера, выходы второго, третьего и четвертого тактов генератора тактовых импульсов соединены соответственно с входом установки режима вычитания, входом сброса и входом установки режима сложения сумматора-вычитателя,длины отрезка аппроксимации, выходы реверсивного счетчика коэффициента наклона соединены с входами блока памяти, выходы которого соединены с вхо» . дами буферного регистра, »-й выход входного регистра соединен с первьыи адресными входами (»,j)-x (»=Т,Й) трехканальных демультиплексоров,1-й выход буферного регистра соединен с вторым адресными входами {»,1)-х (< =Т,И) трехканальных демультиплексоров.

2 . вход 9 - для аппроксимируемой кривой в виде последовательности единичных приращений (фиг.б).

Вход 10 является входом запуска . аппроксиматора, выход 11 — выходом синхроимпульса выдачи коэффициента наклона, выходы 12 — 3 -выходами длины отрезка аппроксимации. Сигнал

"Конец работы" выдается на выходе 13.

Информационными входами блока 2 сравнения линий являются входы 14 й

15, вход 16 опроса блока 2, выходы

18 и 19 блока 2, входы 20-22 блока 3

1 сравнения длины и его выходы 23 и 24, а также входы 25 и 26 блока 6 управления и его выходы 17 и 27.

Блок 2 сравнения линий содержит (фиг.2) регистр 28 начааьного смеще20 ния и матрицу NqN трехканальных демультиплексоров 29, где Й - число разрядов, а И=2ь+1, b - предельное отклонение линий. з 1157

Блок 3 сравнения длины (фиг.3} содержит сумматор-вычитатель 30 длины отрезка аппроксимации, группу 31 элементов ИЛИ, элемент ИЛИ 32, 5

Блок 6 управления (фиг.4) содержит управляемый генератор 33 тактовых импульсов (ГТИ), триггер 34 включения, триггер 35. знака погрешности, ключи 36 и 37, элемент ИЛИ 10

38, элемент И 39, формирователь 40, регистр 41 коэффициента наклона, реверсивный счетчик 42 коэффициента наклона. В блоке 6 управления (фиг.4) вход установки в единицу 15 триггера 34 включения соединен с входом 10 запуска аппрокеиматора..

Прямой выход триггера 34 соединен с входом запуска ГТИ 33 и первым информационным входом ключа 36, 20 управляющий вход которого соединен с выходом третьего такта ГТИ 33.

Первый выход ключа 36 соединен с выходом 11 синхроимпульса выдачи коэффициента наклона аппроксиматора и И входом опроса регистра 41 коэффициента наклона, выходы которого соединены с входами 7 коэффициента наклона аппроксиматора и информационными входами реверсивного счетчика 42 30 коэффициента наклона. Выходы последнего подключены к информационныи входам регистра 41 коэффициента наклона.

Инверсный выход триггера 34 вклю- 35 чения соединен с вторым информационным входом первого ключа 36, второй выход его соединен с управлявшим входои второго ключа 37, первый и второй выходы которого соединены 40 соответственно с входами суммирова.ния и входом вычитания реверсивного счетчика 42 коэффициента наклона.

Управляющий вход счетчика 42 подключен к выходу элемента ИЛИ 38. Выход 45 четвертого такта ГТИ 33 соединен с вторым входом элемента И 39, а выход первого такта ГТИ 33 подключен к первому входу элемента ИЛИ 38 и к входу установки в единицу тригге- 50 ра 35. Прямой и инверсный выходы триггера 35 соединены соответственно с первым и вторым информационными входами ключа 37 °

Инверсный выход триггера 34 под- 55 ключен к первому входу элеиекта И39, выход которого соединен с вторым входом элемента ИЛИ 38 блока 6 управ548 4 ления и с выходом 13 сигнала оконч ани я р аботы аппроксиматор а. I

В блоке 2 сравнения линий (фиг.2) информационные входы регистра 28 начального смещения соединены с входом 8 начального смещения аппроксиматора. Первый и второй входы опроса регистра 28 через группу входов 16 блока 2 и группу выходов 17 блока 6 управления соединены соответственно с выходами второго и четвертого тактоэ ГТИ 33, i-й (1 =1,M) выход регистра 28 соединен с информационными входом (i,t)го трехканального демультиплексора

29. Первый выход (I, 1 )-го трехканальното лентльтнллексора 29 (=

;=2,Ì-1, 1 =1ф/) обьенннек с вторьн выходом (а -1,1)-го и третьим выходом (<-2,5) "го трехканальных демультиплексоров 29 и подключен к йнформационному входу (t -1, 1+1)-ro трехканального демультиплексора 29.

Первьй выход (1,$ )-го (1 1,N) трехканального демультиплексора 29 через эыход 19 блока 2 сравнения линий и вход 21 блока 3 сравнения дли,Hbl соединен с,первым входом 1 -го .элемента ИЛИ группы 31. Третий вьгкод (Мрg )-ro ($ =1рНГ) трехканального демультиплексора 29 через выход 18 блока 2 сравнения линий и вход 20 блока 3 сравнения длины соединен с вторым входом f -ro элемента ИЛИ группы 31 и 1 -м входом элемента ИЛИ

32 блока 3 сравнения длины.

Кроме того, в блоке 3 выход f -го элемента ИЛИ группы 3t соединен с информационным входом (8 †)-го разряда сумматора-эычитателя 30 длины отрезка аппроксимации, информационные выходы которого соединены с выходами 12 длины отрезка аппроксимации аппроксиматора, а знаковый выход через выход 23 блока 3 сравнения и вход 25 блока 6 управления подключен к входу устаноэки в ноль триггера 34.

Выход элемента ИЛИ 32 через выход

24 блока 3 и вход 26 блока 6 управления соединен с входом установки в ноль триггера 35. Выходы второго, третьего и четвертого тактов ГТИ 33 через группу выходов 17 блока 6 управления и группу входоэ 22 блока

3 сравнения длины соединены соответственно с входом установки релжма эычитания, входом сброса и входом

1157548 установки режима сложения сумматоравычитателя 30 длины отрезка аппроксимации. Выход формирователя 40 че-. рез группу выходов 17 блока 6 управления и группу входов 22 блока 3 3 сравнения длины соединен с входом установки в единицу Й-го разряда сумматора-вычитателя 30 длины отрезка аппроксимации.

Выходы реверсивного счетчика 42 1© коэффициента наклона через выходы 27 блока 6 управления соединены с входами блока 1:памяти, выходы которого соединены с входами буферного регистра 5. 15

Информационные входы входного регистра 4 соединены с входом 9 аппроксимируемой кривой. -й выход входного регистра 4 (=1,И) через вход 14 блока 2 сравнения линий со- 20 едикен с первыми адресными входами (<,<)-х (<=-1,И) трехканальных демультиплексоров 29, а ) -й выход буферного регистра 5 через вход 15 блока 2 сравнения линий соединен с 2$ вторыми адресными входами (I, g)-х (l =Г,И) трехканальных демультиплексоров 29.

Блок 1 памяти представляет собой накопитель запоминающего устройства, в котором в единичном состоянии находятся 7я .". т2к-1) -е р аяряяяые ячейки (Коя1,? < ), где ф — номер адреса накопителя, а. Р— разрядность счетчика 42. Таким образом, данные 3g коды зависят только от количества разрядов коэффициентов наклона интерполирующей прямой, но не зависят от его нида и длины прямой, . т.е. данные коды являтотся универсальными, 41т и может быть использован накопитель постоянного запоминающего устройства.

Если каждому разряду поставить в соответствие шаг по Х, а шаги по У делать в том случае, когда в 43 данном разряде содержится единица, то для «j,-го адреса получаем ступекчат ло, которая интерполирует прямую, имеющую коэффициент наклона, равный двоичной дроби вида 0,00...01 ® где единица находится на тт -м месте после запятой.

Последовательность импульсов интерполирующая прямую, коэффициент наклона которой не является простой 55

ДРОбьюp можнО полУчитьp сУммиРУЯ описанные последовательности. Например, для прямой с наклоном

0 10110 надо логитески сложить по= следовательности, записанные в первом, третьем и четвертом адресах, т.е. одновременно считать эти адреса. Таким образом, блок 1 памяти

Формирует сразу всю последовательность интерполирующих импульсов.

Работу аппроксиматора рассмотрим на конкретном примере.

Пусть N =23 тогда блок 1 памяти, буферный регистр 5, входной регистр

4 и блок 2 сравнения линий имеют.

23 разряда, а сумматор-вычитатель

30-24 разряда, счетчик 42 и регистр

41 коэффициента наклона - по 5 разрядов, Пусть максимальная погрешность равна двум, тогда количество разрядов регистра 28 начального смещения, равное количеству адресов блока 2 сравнения линий, равно пяти.

Пусть начальное смещение равно 2, т.е. записана единица в первом разря". де регистра 28. Аппроксимируемая х кривая т . записывается в регистр 4 в виде последовательности единичных приращений (Фиг.б). Так как ее суммарное приращение равно девяти, в счетчик 42 в качестве начального значения записывается число 0,01010.

Далее поступает сигнал на вход 10 запуска аппроксиматора, который устанавливает в единицу триггер 34 включения. Сигнал с его выхода разрешает работу ГТИ 33, который формирует тактовые сигналы, начиная с первого. Кроме того, ка выходе формирователя 40 формируется сигнал начальной установки, который записывает единицу в старший разряд сумматора-вьтчитателя 30.

Импульс первого такта, пройдя через элемент 38, поступает на опрос счетчика 42 (фиг.7), вследствие чего число 0,01010 переписывается в регистр 4 1 и считываются второй и четвертый адреса блока 1 памяти. В регистр 5 записывается 23-разрядная последовательность единичных приращений, соответствующая прямой с наклоном 0,01010 (последовательность а, фиг.б).

Вторым тактом опрошен регистр 28.

Импульс с его первого разряда поступает на соответствующий трехканальный демультиплексор 29 блока 2 сравнения линий. Так как в нервом разряде последовательностей а и т; находятся нули, имттульс проходит на

1157548 второй выход демультиплексора 29 первого разряда первого адреса блока 2 и оттуда на вход дем льтиплексора 29 второ."о разряда первого адреса (кривая 1, фиг.б). Во втором разряде имеется единица в последовательности Г, поэтому импульс переходит на второй адрес блока 2, В третьем разряде имеется единица в последовательности, следовательно 36 импульс переходит на первый адрес блока 2, и так до пятого разряда, после которого импульс поступае на выход 18 блока 2 сравнения линий (фиг.б) . Таким образом, в этом бло- д ке .путь прохождения импульсов опроса повторяет кривую погрешности и заканГ чивается там, где погрешность по абсолютному значению больше й, В данном случае погрешность отрицательна, р@ импульс формируется на пятом выходе

18-й группы, поступает на группу входов 20 блока 3 сравнения длины (фиг.Ç) и через функциональную группу 31 элемента ИЛИ í- вход соответствующего разряда сумматора-вычитателя 30, а через элемент ИЛИ 32 на выход 24.

Заметим, что разряды сумматор твычитателя 30 расположены в обратном З( порядке (сверху старший разряд), .е. выход последнего разряда блока 2 подключен к входу младшего разряда сумматора-вычитателя 30, выход предпоследнего разряда блока. 2 "

5 к входу второго разряда сумматоравычитателя 30, и т.д. до вьжода первого разряда блока 2 (слева, фиг.2), который подключен х входу старшего разряда сумматора- gy вычитателя 30.

Блок 3 сравнения длины работает следующим образом.

Место, н котором погрешность превышает Ь, запоминается в виде еди- 45 ницы, записанной в соответствующий разряд счетчика-. вычитателя 30. При следующем варианте аппроксимирующего отрезка сумматор-вычитатель 30 переводится в режим вычитания. Если И длина отрезка, в котором погрешность находится в пределах нормы, увеличивается, то из имеющихся чисел вычитается число, содержащее единицу в более младшем разряде (более ниж- 55 нем), и в результате получается положительное число, т.е. ноль в знаковом разряде сумматора-вычитателя 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, что изменяет коэффициент наклона прямой, который равен 0„01001. Кроме того, такт, всегда обнуляет сумматор-вычитатель 30. Все это соответствует алгоритму (фиг.7).

Четвертым тактом (фиг.?) проведен второй опрос блока 2 сравнения линий по входу 16 (фиг.2), но при этом 9 11575 сумматор-вычитатель 30 блока 3 находится в режиме сложения, так как на его вход установки режима сложения поступает четвертыи такт ГТИ 33, А так как в третьем такте сумматор-.. вычитатель 30 обнулен, в нем записывается единица в пятом от старшего разряде, Далее снова следует опрос блока памяти {фиг.7) и в буферном регист-16 ре 5 записывается последовательность единичных приращений, соответсвующая прямой В на графике У=1(Х) (фиг.6) . При опросе блока 2 импульс проходит по пути, соответствующему варианту кривой 3 (фиг.6}. Погрешность выходит за пределы отрицательно о допуска, поэтому по сигналу с выхода 24 блока 3 триггер 35 установлен в ноль, и число в счетчике 42 gg коэффициента наклона опять уменьшается на единицу и равно 0,01000.

Зто соответствует варианту (фиг.6). Здесь погрешность выходит за пределы положительного допуска, д поэтому импульс с блока 2 поступает на один из входов 21 группы и не формирует импульс на выходе 24 бло,ка 3 сравнения длины. Триггер 35 остается в единичном состоянии и по импульсу с выхода ключа 37 со о,ержимое счетчика 42 коэффициента наклона увеличивается и равно 0,Q10Q1„

В этом случае при опросе блока 2 но втором такте из числа записанного

83 в сумматоре-вычитателе 30, вычитается большее, что приводит к изменению знакового разряда сумматора" нычитателя 30 и, следовательно, к

10 появлению импульса на входе 25 блока 6 и к установке н ноль триггера

34.

В результате этого третий такт с выхода ключа 36 поступает на выход 11 синхроимпульса выдачи коэффициента блока 6 и на вход опроса регистра 41 коэффициента наклона. При этом содержимое регистра 41, предыдущее значение коэффициента наклона, переписывается в счетчик 42 и формируется на входе 7 аппроксиматора для записи его во внешние устройства. Переключение триггера 34 приводит к тому, что четвертый такт с выхода элемента И 39 поступает на выход 13 сигнала окончания работы аппроксиматора и через элемент ИЛИ 38 на опрос счетчика 42. Кроме того, этот же такт, как и раньше, опрашивает блок 2 сравнения линий с переводом сумматора-вычитателя 30 в режим сложения.

По сигналу с выхода t1 аппроксиматора выведено найденное наилучшее значение коэффициента наклона аппроксимирующего отрезка, содержащееся в регистре 41 и счетчике 42 коэффициента наклона, а длина отрезка, предо ставленная в позиционном коде в сумматоре-вычитателе 30, может быть считана в любой момент после формирования сигнала "Конец" на выходе 13 аппроксиматора.

Таким образом, за четыре цикла работы аппроксиматора (16-ть тактов) определена максимально возможная длина аппроксимации исходной кривой с заданной погрешностью и найдены параметры аппроксимирующего отрезка.

1 I>7548

1157548

1 3 57548

0

Az. 5

2 0 д д Ю Q fO Ю f8 30 22 Z4

Ю

+f д

-1

1157548

Составитель А.Чеканов

Техред Ж.Кастелевич Корректор C.ЧеРни

Редактор Н.Бобкова

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4

Заказ 3373/48 Тираж 710 Подписное

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

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