Линейный аппроксиматор Советский патент 1985 года по МПК G06F17/17 

нен с управляющим входом первого ключа, выход четвертого такта генератора тактовых импульсов, соединен с вторьм входом элемента И и вторым входом опроса perHC- f начш1ьно1 о смещения, Г-й ( ) выход которого соединен с информационным входом (1, 1)-го трехканального демультиплексора, первый выход («,j)-го трехканального демульти плексора (2,М-1,)Г) объединен с вторым выходом («-1,j )-го и третьим выходом (f-2,j)-ro трехканальных демультиплексоров и подключен к информационному входу (f-1, j + 1)-ro трехканального демультиплексора, блок сравнения длины содерядит сумматор-вычитатель длины отрезка аппроксимации, группу элементов ИЛИ и элемент ИЛИ, причем первый выход (1, j)-ro () трехканального демультиплексора соединен с первым входом У -го элемента ИЛИ группы, выход которого соединен с информационным входом (JJ-J)TO разряда сумматора-вычитателя длины отрезка аппроксимадаи, инФормащюнные выходы которого соединены с выходами

длины отрезка аппроксиматора, а знаковый выход подключен к входу установки в ноль первого триггера, третий выход (M,J )-го (,15 трехканального демультиплексора соеда1нен с вторым входом jl-го элемента ИЛИ группы и У -м входом элемента ИЛИ блока сравнения длины, выход которого подключен к входу установки в ноль второго, триггера, выходы второго, третьего и четвертого тактов генератора тактовых импульсов соединены соответственно с входом установки режима вычитания, входом сброса и входом установки режима сложения сумматора-вычитателя длины отрезка аппроксимации, выходы реверсивного счетчика коэффициента наклона соединены с входами блока памяти, выходы которого соединены с вхог дами .буферного регистра, j-й выход входногорегистра соединен с первм и адресными входами ( «, р-х (1 - ,Й) трехканальных демультиплексоров,/-и выход буферного регистра соединен с вторьм адресными входами (,/)-х (Т7М) трехканальиых демультиплексоров.

Изобретение относится к вычислительной технике, к устройствам обработки информации. Цель изобретения - повышение быстродействия. На фиг.1 представлена- блок-схема аппроксиматора; на фиг.2 - функционапьная схема блока сравнения линий; на фиг.3 -функциональная схема блок сравнения длины; на фиг.4 - функциональная схема блока управления; на фиг.5 - карта состояния ячеек накопи теля; на фиг.6 - графики, поясняющие работу аппроксиматора; на фиг.7 блок-схема работы аппроксиматора. Аппроксиматор состоит из блока.1 памяти, блока 2 сравнения линий, блока 3 сравнения дпины, входного ре гистра 4, буферного регистра 5 и бло ка 6 управления. Вход 7 служит для начапьного значения коэффициента наклона аппроксимирующей прямой, вход 8 - для смещения ее начальной точки. вход 9 - для аппроксимируемой кривой в виде последовательности единичных приращений (фиг.6). Вход 10 является входом запуска аппроксиматора, выход 11 - выходом синхроимпульса выдачи коэффициента наклона, выходы 12 - D -выходами дпины отрезка аппроксимации. Сигнап Конец работы выдается на выходе t3. Информационными входами блока 2 сравнения линий являются входы t4 и 15, вход 16 опроса блока 2, выходы 18 и 19 блока 2, входы 20-22 блока 3 сравнения дпины и его выходы 23 и 24, а также входы 25 и 26 блока б управления и его выходы 17 и 27. Блок 2 сравнения линий содержит (фиг.2) регистр 28 начального смещения и матрицу M)(N трехканальных демультиплексоров 29, где N - число разрядов, а + 1, Д- предельное отклонение линий. 3 Блок 3 сравнения длины Сфиг.З) с держит сумматор-вычитатель 30 длины отрезка аппроксимации, группу 31 элементов ИЛИ, элемент 1ШИ 32. Блок 6 управления (фиг.4) содержит управляемый генератор 33 тактовых импульсов (ГТИ), триггер 34 включения, триггер 35 знака погреш ности, ключи 36 и 37, элемент ИЛИ 38,элемент И 39, формирователь 40, регистр 41 коэффициента наклона, реверсивный счетчик 42 коэффициента наклона. В блоке 6 управления (фиг.4) вход установки в единицу триггера 34 включения соедияен с вх дом 10 запуска аппрокеиматора. Прямой выход триггера 34 соединен с входом запуска ГТИ 33 и первы информационным входом ключа 36, упр|авляю1дий вход которого соединен с вькодом третьего такта ГТИ 33. Первый выход ключа 36 соединен с вы ходом И синхроимпульса выдачи коэф фициента наклона аппрокеиматора и входом опроса регистра 41 коэффици ента наклона, выходы которого соеди нены с входами 7 коэффициента накло на аппрокеиматора и информационными входами реверсивного счетчика 42 коэффициента наклона. Выходы послед )сего подключены к информационным входам регистра 41 коэффициента наклона. Инверсный выход триггера 34 включения соединен с вторым информационным входом первого ключа 36, второй выход его соединен с управляющим входом второго ключа 37, первый и второй выходы которого соединены соответственно с входами суммирова,ния и входом вычитания реверсивного счетчика 42 коэффициента наклона. Управляющий вход счетчика 42 подключен к выходу элемента ИЛИ 38. Вькод четвертого такта ГТИ 33 соединен с вторым входом элемента И 39, а выход первого такта ГТИ 33 подключен к первому входу элемента ИЛИ 38 и к входу установки в единицу триггера 35. Прямой и инверсный выходы триггера 35 соединены соответственно с nepBbw и вторым ийформационными входами ключа 37. Йнверсньсй выход триггера 34 подключен к первому входу элемента И 39,выход которого соединен с Ьторьви входом элемента ИЛИ 38 блока Ь управ 484 ления и с выходом 13 сигнала окончания работы аппрокеиматора. . В блоке 2 сравнения линий (фиг.2) информационные входы регистра 28 начального смещения соединены с входом 8 начального смещения аппроксиматора. Первый и второй входы опроса регистра 28 через группу входов 16 блока 2 и группу выходов 17 блока 6 управления соединены соответственно с выходами второго и четвертого тактов Гта 33. Ч-й (-(«(Тм) выход регистра 28 соединён с информационными входом (, 1)го трехканального демультиплексора 29. Первый выход (l,j )-го трехкан ального демультиплексора 29 ( 2,M-1, j 1 ,/) объединен с вторьм выходом (-1,})-го и третьим выходом (-2,j)-ro трехканапьных демультиплексоров 29 и подключен к информационному входу (-1, i+1)-ro трехка- , напьного демультиплексора 29. Первьй выход (l,j)-ro (j 1,N) трехканального демультиплексора 29 через выход 19 блока 2 сравнения линий и вход 21 блока 3 сравнения длины соединен с, первым входом j -го элемента ИЛИ группы 31. Третий выход (M,j )-го (j 1,N) трехканального демультиплексора 29 через выход 18 блока 2 сравнения линий и вход 20 блока 3 сравнения длины соединен с вторым входом J -го элемента ИЛИ группы 31 и j -м входом элемента ИЛИ 32 блока 3 сравнения длины. Кроме того, в блоке 3 выход J -го элемента ИЛИ группы 31 соединен с информационным входом (N-j)-ro разряда сумматора-вычитателя 30 длины отрезка аппроксимации, информационные выхода которого соединены с выходами 12 длины отрезка аппроксимации аппрокеиматора, а знаковый выход через выход 23 блока 3 сравнения и вход 25 блока 6 управления подключен к входу установки в ноль триггера 34. Выход элемента ИЛИ 32 через %ыход 4 блока 3 и вход 26 блока 6 управения соединен с входом установки ноль триггера 35. Выходы второго, ретьего и четвертого тактов ГТИ 33 ерез группу выходов 17 блока 6 правления и группу входов 22 блока сравнения длины соединены соответтвенно с входом установки режима ычитания, входом сброса и входом

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

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

Информадион{Пз1е входы входного регистра 4 соединены с входом 9 аппроксимируемой кривой.1-й выход входного регистра 4 (J, 1,N) через вход 14 блока 2 сравнения линий соединен., с первыми адресными входами (5J) (-1 jM) трехканальных демультиплексоров 29, а J-и выход буферного регистра 5 через вход 15 блока 2 сравнения линий соединен с вторыми адресными входами (f ,j)x (l i jМ) трехканальных демультиплексоров 29.

Блок I памяти представляет собой накопитель запоминающего устройства, в котором в единичном состоянии находятся . TljL(.2K 1) -е р азрядные ячейки (, ) 5 где ( номер адреса накопителя,, а Р - разрядност счетчика 42, Таким образом, данные коды зависят только от количества разрядов коэф4)ициентов наклона интерполирующей прямой, но не зависят от его вида и ддтины Прямой,, т.е. данные коды являются универсальными, и может быть использован накопитель постоянного запоминающего устройства

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

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

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

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

Пусть , тогда блок 1 памяти, буферньй регистр 5, входной регистр 4 и блок 2 сравнения линий имеют23 разряда, а сумматор-вычитатель 30-24 разряда, счетчик 42 и регистр 41 коэффициента наклона - по 5 разрядов. Пусть максимальная погрешность равна двум, тогда количество разрядов регистра 28 начального смещения, равное количеству адресов блока 2 сравнения линий, равно пяти

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

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

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

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

второй выход демультиплексора 29 ервого разряда первого адреса блока 2 и оттуда на вход демультиплексора 29 второго разряда первого ад реса (кривая & , фиг.6). Во втором § азряде имеется единица в последовательности f , поэтому импульс переходит на второй адрес блока 2. В третьем разряде имеется единица в последовательности , следовательно tQ импульс переходит на первый адрес блока 2, и так до пятого разряда, после которого импульс поступает на выход 18 блока 2 сра внения линий (фиг,6). Таким образом в этом бло- is ке путь прохождения импульсов опроса повторяет кривую погрешности и заканивается там, где погрешность по аболютному значению больше Л с В даном, случае погрешность отрицательна, 2@ мпульс,формируется на пятом выходе 18-й группы, поступает на группу вхоов 20 блока 3 ср,авнения длины (фиг.З) и через функциональную группу 3.1 элемента ИЛИ на вход соответ- 25 ствующего разряда сумматора-вычктателя 30,а через элемент ИЛИ 32 на выход 24.

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

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

Место,,в котором погрешнюсть превышает Л , запоминается в виде еди- S , записанной в соответствующий азряд счетчйка-вычитателя 3,0-. При следующем варианте нппроксиьшрующе- , го отрезка сумматор-вьгчитатель 30 переводится в режим вычитания. Если 5 длина отрезка, в котором погрешность находится в пределах норм,ы, увеличивается, то из имеющихся чисел вычитается число,, содержащее единицу в более младшем разряде (более ниж- S5 нем) ,, и в, результате получается положительное число, т.е. ноль в знаковом разряде сумматора-вычитателя 30

обнуляется и повторяется опрос блока 2 сравнения линий (фиг.7), Носумматор-вычитатель 30 в это время переведен в режим сложения, поэтому импульс с блока 2 записывается в сумматор-вычитатель 30 и, тем самым запоминается новая длина отрезка аппроксимации. Таким образом блок 3 сравнения осуще.ствляет сравнение дли текущего и предыдущего отрезков аппроксимации и запоминает текущий, если он больше пред 1дущего, т.е. выбирается лучший вариант аппроксимирующей прямой, О том, что текущий вариант хуже предыдущего Чдлина, погрешность которой не выходит за дрпустимые пределы, стала меньше) сигнализирует появление единицы в знаковом разряде сумматора-вычитателя 30.

Возвращаясь к лримеру, запомним, чтю в качестве начальной установки сумматора-вычитателя 30 бьша записана единица в его старший разряд. С блока 2 сравнения линий поступает импульс на пятый от старшего разряд. Это происходит во время действия второго Такта, которьй из ГТИ 33 поступает на вход установки режима вычитания cy p aтopa-вычитaтeля 30.

Так как при вычитании получилось положительное число, триггер 34 остается S единичном состоянии. Триггер 35 знака первьи тактом установлен в единичное состояние. При сравнении линий погрешность выходит за нижнюю границу, импульс формируе,тся на пятом- разряде группы выходов 18 и по,ступает на вход 20 блока 3. В этом случае появляется импульс на выходе элемента I-UIH 32, поступает на вход 26 блока 6 и устанавливает в ноль триггер 35,

Таким образом, триггер 35 является триггером знака погрешности. При данном состоянии триггеров 34 и 35 импульс третьего такта с выхода ключа 36 поступает на вход ключа 37, а с его вьгхода на вход вычитания едиНИ15 реверсивного счетчика 42, что изменяет коэффициент наклона прямой, которьй равен 0,01001. Кроме того, такт всегда обнуляет сумматор-вычитатель 30. Все это соответствует алгоритму (фиг.7).

Четвертым тактом (фиг.7) проведен второй опрос блока 2 сравнения линий по входз 16 (фиг.2), но при этом 9 сумматор-вьгчитатель 30 блока 3 нахо дится в режга е сложения, так как на его вход установки режима сложения поступает четвертьй такт ГТИ 33 А так как в третьем такте сумматорг вычитатель 30 обнулен, в нем записы вается единица в пятом от старшего разряде. Далее снова следует опрос блока 1 памяти (фиг.7) и в буферном регис ре 5 записывается последовательност единичнь1х приращений, сооТветсвую щая прямой В на графике ((Х) (фиг,6). При опросе блока 2 импульс проходит по пути, соответствующему варианту кривой fi (фиг.6). Погрешность выходит за пределы отрицатель допуска, поэтому по сигналу с выхода 2А блока 3 триггер 35 устано лен в ноль, и число в счетчике 42 коэффициента наклона опять уменьшается на единицу и равно 0,01000. Это соответствует варианту (фиг.6). Здесь погрешность выходит за пределы положительного допуска, поэтому импульс с блока 2 поступает на один из входов 21 группы и не формирует импульс на выходе 24 бло,ка 3 сравнения длины. Триггер 35 остается в единичном состоянии и по импульсу с выхода ключа 37 со цержимое счетчика 42 коэффициента наклона увеличивается и рав«р 0,01001 В этом случае при опросе блока 2 flo втором такте из числа записанного в сумматоре-выЧитателе 30, вычитается большее, что приводит к изменению знакового разряда сумматоравычитателя 30 и, следовательноj к 48 появлению импульса на входе 25 блока 6 и к установке в ноль триггера 3. В результате этого третий такт с выхода ключа 36 поступает на выход 11 синхроимпульса выдачи коэффициента блока 6 и на вход опроса регистра 41 коэффициента наклона. При этом содержимое регистра 41, предыдущее значение коэффициента наклона, переписывается в счетчик 42 .и формируется на входе 7 аппроксиматора для записи его во внешние устройства. Переключение триггера 34 приводит к тому, что четвертый такт с выхода элемента И 39 поступает на выход 13 сигнала окончания работы аппроксиматора и через элемент ИЛИ Э8 на опрос счетчика 42. Кроме того, этот же такт, как и раньше, опрашивает блок 2 сравнения линий с переводом сумматора-вычитателя 30 в режим сложения. По сигналу с выхода 11 аппроксиматора выведено найденное наилучшее значение коэффициента наклона аппроксимирующего отрезка, содержащееся в регистре 41 и счетчике 42 коэффициента наклона, а длина отрезка, представленная в позиционном коде в сумматоре-вычитателе 30, может быть считана в любой момент после формирования сигнала Конец на выходе 13 аппроксиматора. Таким образом, за четыре цикла работы аппроксиматора (1б-ть тактов) определена максимально возможная лина аппроксимации исходной кривой заданной погрешностью и найдены араметры аппроксимирующего отрезка.

К

кГ CS

Ч

:

5

26

f I gjgl /1 gtgf t g g| / o o t Ш 0

/ Wflfl/fniiflrbbHi(tf bl0tfflff

Фиг 6