Устройство для определения экстремумов

(6 ) Дополнительное к авт. свнд-ву -51)м, К 22) Заявл 9,77(21) 2527270/18-2 06 Р 15/34 присоелнненнем заявки-Государственный комитет 23) Пр тет -ковано 25.05,80. Бюллетень 1 до делам нзобретеии и открытийДата опублнкованкя описания 28,05 2) Авторы изобретен К, Островский, В, А. Фильштинск Ю. А. Стеценко и В. Д. Яковец(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИ ЭКСТРЕ М УМОВИзобретение относится к вычислительной технике и может быть использовано в автоматизированных системах контроля различнык процессов, например при построении анализаторов сигналов интегрирующих машин.Известно устройство для определенияэкстремумов, содержащее генератор тактовых импульсов, преобразователь коммутатор, ключи, триггер, блок сравнения, регистр, триггер экстремума, элементы И, счетчик, элементы ИЛИ 11.Это устройство не обеспечивает оптимального по быстродействию поиска экст ремума, так как с его помощью осущест вляется прямой перебор всех возможных значений сигнала.Наиболее близким к изобретению потехнической сущности является устройство, содержащее сумматор, первый вход которого соединен с первым входом устройства, второй вход сумматора соединен с выходом регистра текущего значе ния функции, вход которого подключен к выкоду сумматора и к первому входусхемы сравнения, регистр экстремальногозначенчя функции, выход которого соединен со вторым входом схемы сравненияи входом регистра экстремального значения функции, выход которого соединенс первым входом коммутатора, второйвход которого подключен к выходу регистра текущего значения функции второй вход устройства подключен к третьему входу схемы сравнения, выход которой подключен к третьему входу коммутатора 2,В исходном состоянии его регистрысодержат начальное значение функции, а 5на входе схемы сравнения установлен заданный потенциал, по отношению к которому осуществляется оценка наибольших(наименьших) значений функции. Далее оприращения функции последовательно инепрерывно сравниваются по итерациями результаты сравнения записываютсяв регистре экстремального значенияфункции и сохраняются искомые значения.736111 едостаток этого устройства состоит в отсутствии возможности наискорейшего поиска экстремума и необходимости иметь непрерывные все без исключения выборки, а также в ограниченном динами 5 ческом диапазоне, который задается установкой начальных пороговых значений.Цель изобретения - повышение эффективности за счет сокращения числа выборок и увеличения динамического диапазо на.Поставленная цель достигается тем, что в устройство, содержащее коммутатор, схему сравнения, выходы которой соединены соответственно со входами 15 регистра экстремумов, выход которого подключен к первому выходу устройства, введены блок формирования чисел Фибоначчи, блок памяти, блок управления и преобразователь аналог-код, вход кото рого соединен с первым выходом блока памяти, второй выход блока памяти и выход преобразователя аналог-код через коммутатор соединены со входом схемы сравнения управляющей, выход которой подключен ко входу блока управления, первый выход блока формирования чисел фибопаччи подключен ко второму выходу устройства, второй выход соединен с управляющими входами блока памяти и преобразователя аналог-код, вход блока формирования чисел фибоначчи подключен ко входу устройства, управляющий вход регистра экстремумов, первый и второй управляющие входы схемы сравнения,35 первый и второй управляющие входы блока формирования чисел Фибоначчи соединены с соответствующими выходами блока управлепия. 4На фиг. 1 приведена схема устройства; на фиг. 2 и фиг. 3 - примеры сигналов и методика оптимального по быстродейст вию разбиения интервала поиска.Устройство содержит блок 1 памяти, преобразователь 2 аналог-код, схему 3 сравнения, состоящую из реверсивного сумматора 4 и буферного регистра 5, регистр 6 экстремумов, блок 7 формирования чисел фибоначчи, состоящий из регистров 8 и 9 сдвига, реверсивного счетчика 1 О и счетчика 1 1 интервалов, блок 12 управления, коммутатор 13, вход 14 и выходы 15, 16 устройства.Известен метод дихотомического поиска (метод фибоначчи), использующий стратегию поиска экстремума по числам Фибоначчи, задаваемых рекурентным уравф"нением Числа фибоначчи до номера 62 приведены в табл. 1; диаграмма формирования прямой и обратной последовательности чисел Фибоначчи - в табл. 2.Процедура поиска включает следующие этапы (табл. 1). Проводится пара измерения в точках ф (И) и ч) ( г( -1). Согласно условию унимодальности перед вторым этапом проискодит сокращение интервала неопределенности по информации о численных значениях функции Х (1) в указанных точках,Если Х ( Ч) Ж 3-ХЕФЬ-ЯЗ ) (2) то экстремум слева, в противном случае(Сроме того, блок формирования чисел Фибоначчи в устройстве содержит два регистра сдвига, реверсивный счетчик и счетчик интервалов, входы которого соединены соответственно с входом блока 45 и со вторым управляющим входом блока, первый и второй выходы счетчика интервалов соединены соответственно с первым выходом блока и с первым входом реверсивного счетчика, другие входы которого 50 подключены соответственно к выходам первого регистра сдвига, выход реверсив-. ного счетчика соединен со вторым выходом блока и через второй регистр сдви га - со входом первого регистра сдвига, управляющие входы реверсивного счетчика н регистров сдвига подключены к первому управляющему входу блока. а экстремум справа,Особенностью данного поиска является то, что из двух точек в каждом цикле,одна всегда совпадает с точкой предыдущего шага, в которой уже проведено испытание, т. е. необходимо находить только координату одного из двух измерений,Так как последовательность чиселФибоначчи весьма быстро растет и разрыв между соседними числами составляет сотни миллионов уже с сороковых номеров (см. табл. 1), то эффективностьприменяемого метода существенна прибольших объемак обрабатываемой информации.Следует отметить, действительностьзадачи, которая решается с помощью данного метода, С одной стороны, это мини(мизация числа измерений при равной точ5 736 ности и с другойминимизация погрешности при значительном числе точек измерения. В дальнейшем будем рассматривать только задачу быстродействия. нуляется с помощью бпока 12 управления, а из буферного регистра число, поступившее первым (большее из двух),переносится снова в сумматор 4 и схе 15 ма 3 сравнения подготовлена к приемутретьего числа, Аналогично с первымслучаем, максимальное число такжеперезаписывается в регистр 6 экстремумов,20 До сих пор не рассматривался вопросформирования последовательности чиселФибоначчи, которые по существу и определяют существенное сокращение выборок сигнала и оптимизацию, в смыслебыстродействия процесса поиска экстре-мумов, Для ее осушествления необходимо формировать как прямую, так и обратную последовательность чисел Фибоначчи.Регистры 8 и 9 содержат в исходномЗ 0 состоянии единицы, а счетчик 1 1 - верхний интервал унимодальности, Наличиеих необходимо для формирования прямойпоследовательности чисел фибоначчи всоответствии с выражением ( 1), начиная35 с Ф(1) (1)Проследим процесс формирования прямой и обратной последовательности чиселФибоначчи с помощью табл. 1 и 2.Первое прямое число образуется после40 сложения в реверсивном счетчике 10 нуля и единицы, На втором шаге единицаиз регистра 8 сдвигается в регистр 9;а на третьем из счетчика 1 0 переписывается в регистр 8 (без стирания в4 самом счетчике), Четвертым шагомсложением 1 + 1 в счетчике заканчивается формирование второго числа Ф(2)=2,Далее процесс формирования продолжаетсяпоследовательно по своей таблице чиселФибоначчи однообразно и на 40 шагефиксируется число 610. Верхний пределпри этом задается счетчиком 11 интервалов, в который предварительно вводятнеобходимый интервал унимодальности.Обратная последовательность чиселФибоначчи ф(11) начинается с предустановки числа (Ф(11+1) и Ф(И), которые ранее, находились, соответственно, в Принцип построения устройства для всех случаев, когда исследуемый сигнал записан на каком либо носителе .в блоке 1 памяти в непрерывной или дискретной форме заключается в следующем, Предлагаются известными распределения максимумов и минимумов на кривой, Последнее условие необходимо для выбора интервалов унимодальности и предварительного ввода его в счетчик 1 1 интервалов (здесь и далее исследуются временные сигналы или процессы). Верхние пределы унимодальности с помощью блока 12 управления последовательно вводятся в счетчик 11 и в этих заданных интервалах производится поиск экстремума.Исходное состояние характеризуется наличием нулей во всех счетчиках и уз.лах за исключением регистров 8 и 9, где записаны единицы и счетчика 1 1 интервалов, куда введен верхний предел интервала унимодальности. Коммутатор 1 3 устанавливают в положение, указанное на фиг. 1. В противном случае входное напряжение подключают к преобразователю 2 аналог-код для замены непрерывных значений сигнала дискретными,Команда на выборку последовательности значений сигнала из блока 1 памяти или на запуск преобразователя 2 поступает из блока 7 формирования чисел фибоначчи, Первое числовое значение записывается по отрицательному входу в реверсивный сумматор 4 и переносится в параллельном коде без изменения в буферный регистр 5, По приходу второго значения сигнала на положительный вход сумматора 4 вычисленная разность оценивается по критериям (2) и (3).Если она положительная, т, е. выпол" няется условие (2), можно сделать вы-. вод, что максимум слева по оси времени. Для сохранения максимального из первой поступившей пары чисел необходимо полученную разность прибавить к содержимому буферного регистра 5 и результат, равный второму (большему) из чисел переписать в сумматор 4. Этим самым схема 3 сравнения подготволена для приема следующего (третьего) числа, Одновременно это промежуточное максималь ное значение фиксируется в регистре 6 экстремумов, но на выход оно не поступает.Если первая разность окажется отрицательной и выполнится другое услЬвие (3), свидетельствующее о наличии максимума справа от исходной точки по оси времени, то прохождение импульсных последовательностей изменится по сравне. нию с первым случаем. Сумматор 4 об25 40 7 М 11реверсивном счетчике 10 и ре истре 9,меняются местами, а Ф(О) оставляется в регистре 8, Кроме того, счетчик10 устанавливается в режим вычитания.Здесь следует отметить особенностьформирования Ф (,И) - обратной последовательности. Чтобы обратные числа начинались с Ф (13) = 377, необходимо впрямых числах закончить на номере 15,т. е, на два номера далее требуемого 1 Оф( 1 5 ) = 9 87, Предустановка проис кодит таким образом, что число 987 переносится в регистр 9 из счетчика 1 О,последний сбрасывается в нуль и в негозаписывается 610, На первом шаге оно 15вычитается из предыдущего Ф (1)Ф (13) = 377 и начинается обратнаяпоследовательность. Второе обратноечисло формируется после сдвига 610из регистра 8 в регистр 9, а 377 - 20из счетчика 10 в регистр 8, Послевычитания 610-377 появляется второечисло 233. Дальнейшее получение обратных чисел происходит аналогично,На фиг. 2 приведены два крайнихслучая, которые могут представиться вв практике поиска экстремума сигнала на интервале унимодальности Тд 34 с.,Кривая 1 иллюстирует нахождение максимума на левом конце интервала, и302 - на правом,Оба сигнала изменяются по указаннымзаконам в течение 34 с, Записанные внепрерывном виде на магнитном (либоином носителе) или в виде кода в бпоке1 памяти, эти сигналы хранятся до момента поиска ик максимумов, Требуется,в кратчайшее время отыскать и измеритьмаксимум.Г 1 р и м е р 1, Г 1 оиск ведется отправого конца интервала к левому, Приэтом для простоты изложения соблюдаюттот же временной масштаб, На практикенет смысла 34 с искать точку и времяможно сжать в 100 - 1000 раз,45Поиск начинаем с числа 4(7) - 21(Для этого требуется вводить в блок 7ила 34 и 55).Б точке Ь= 21 кодируется значениесигнала Х (21 ) ц записывается по отрицательному входу в реверсивном сумматоре 4 и переносится без изменения в буферный регистр 5. 1 о приходу второгозначения сигнал. Х (13 ) на сумматор 4вычисляется разцость и оценивается покритериям (2) и (3). Соблюдается условие (2), зна ит экстремум слева. Следуянумерации точек по кривой 1, видим, что 1сигнал возрастает, и разность Х () (21 ) для сокрацения максимальцо о изэтойпары чисел должна добавиться в буферный регистр 5 и переписаться в сумматор 4, а затем в регистр 6 экстремума. Здесь будет фиксироваться текущее значение максимума до получения итоговой величины.Далее сигнал пробегает последовательно значения х( 8,1), х( 5,), х( 3), х( 2 ) и х ( 1 5 ), Процесс сохранения максимальных значений такой же как и ранее и позволяет сделать одно из двух основных заключений по поиску экстремумов. Если экстремум ожидается слева, то никаких изменений в порядке измерений мгновенных значений сигнала, равно как и формировании обратной последовательности чисел фибоначчи не наблюдается,Регистр 6 зафиксирует максимум х(2 - (заштрихованная точка 24 на фиг, 2), который будет считан по приходу импульса с блока 12 управления, Вместо обычного прохождения 34 измеряемых точек сигнала искомый результат получен на седьмом такте.П р и м е р 2, Процесс, протекающий по кривой 2 (см. фиг. 2), позволяет выявить вторую особенность поиска экстремумов, Первое измерение сигнала при интервале 34 с осуществляем лищь для точки = 21, а второе - для 13. Теперь полученные значения удовлетворяют неравенству (3), т. е, х(21к(13), Скема 3 сравнения по другому реагирует на эту ситуацию. Сумматор 4 обнуляется а из буферного регистра число, поступившее первым, т, е. к(214) переносится снова в сумматор 4 для подготовки к сравнению с новым поступающим значением. В отличие от первого примера, здесь с той точки аргумента, где обнаружен факт, что максимум находится справа (работает условие уцимодальности), необходимо формировать новую прямую последовательность чисел Фибоначчи ф 2 (И) до того же номера Ф (6) = 13, на котором имеет место неравенство к(13) ( к(21 ). Это обстоятельство является второй особенностью поиска экстремума, В этот момент с выхода реверсивного сумматора 4 импульс перехода через нуль является управляющим импульсом для начала формирования новой прямой последовательности чисел, Формирование идет с запасом до числа ф,(8) = 342, чтобы стало возможным получение обратной последовател ностиние временных затрат на определение текущих значений сигнала.П р и м е р 3. Приведенная на фиг.3 форма изменения сигнала, характеризуется срединным положением максимума и является промежуточным случаем в сравнении с двумя предыдущими, Интервал унимодальности Т = 13 с, Поэ тому первыми измеренными значениями являются х(8) = х(5 ). Здесь имеет место равенство амплитуд, однако в соответствии с формулой (2), поиск продолжается так же, как если бы соблюдалось х(8 )х(5 ). В точке Ф (3) = 3 сиг 3нал становится меньшим и поэтому генерируется последовательность чисел ф. Далее иллюстрируется возможность повышения точности определения момента экстремума за счет изменения масштаба по оси времени. На любом из циклов поиска этот масштаб можно уменьшить произвольно и добиваться необходимого снижения погрешности,Процедура поиска для минимумов ничем не отличается от рассмотренной для максимумов. 1 о го Таблица 1 Числа Фибоначчи 1 32 2 33 3 34 535 8 36 13 37 2138 34 39 55 40 89 41 144 42 233 43 377 44 610 45 987 46 1597 47 2584 48 10 12 14 9 7361 Ф . Определяется амплитуда сигналагх (132), сравнивается с х(21) и остав ляется большее как и в конце предыдушего. такта, т. е, х(13) 1 х(21 ), или, что то же самое х(13х(8), таккак точки новой ф- последовательности иногда совпадают со старыми точками. Такой вид неравенства приводит к необходимости формировать новую Ф 3 последовательность, как прямую, так и обратную, а именно, с точки Ф(0) ф(5) = 8. Следуюшей измерейной точкой 4 (кривая 2) является х(8). Так как и это значение больше чем х(5) (т, е. максимум находится еще правее), возникает необходимость в дальнейшем сужении интервала нахождения максимума. Для этого крайнего случая, наиболее трудоемкого по обработке кривой, только на 6 цикле поиска удается отыскать максимум в точке х( 1). (заштрихованная первая точка на фиг. 3). с.Однако по числу измерения и этот 25 пример показывает пятикратное сокраще 35245785702887 922746514930352 24157817 39088169 63245986102334155 165580141 267914296 433494437 701408733 1134903170 1 836311 903 2971215073 4807526976 7778742049736111 12 Продолжение табл. 1 4181 49 19 6765 50 51 20 10946 17711 52 21 28657 22 46368 54 139583862445 23 75025 24 55 225851433717 26 27 28 832040 60 2504730781961 30 1346269 61 4052739537881 2178309 62 6557470319842 31 Таблица 2 Диаграмма формирования прямой и обратнойпоследовательности чисел фибоначчи 10 0 610 1 0 987 - 610 : 377 1 + 0: 1 610 ъ. 610 377 377 1 + 1: 2 377 ф 377 233 233 1 + 2 = 3 377 - 233 = 144 2 - ь 2 233- 233 14формула изобретения 1. Устройство для определения экстремумов, содержащее коммутатор, схему сравнения, выходы которой соединены соответственно со входами регистра экстремумов, выход которого подключен к первому выходу устройства, о т л и ч а ющ е е с я тем,что,с целью повыщенияэффективности за счет сокращения числа выборок и 10 увеличения динамического диапазона, в него введены блок формирования чисел фибоначчи, блок памяти, блок управления, и преобразователь аналог-код, вход которого соединен с первым выходом блока памяти, второй выход блока памяти и выход преобразователя аналог-код через коммутатор соединены со входом схемы сравнения управляющей, выход которой подключен ко входу блока управления, 20 первый выход блока формирования чисел фибоначчи подключен ко второму выходу устройства, второй выкод соединен с управляющими входами блока памяти и преобразователя аналог-код, вход блока фор мирования чисел фибоначчи подключен ко вкоду устройства, управляющий вход регистра экстремумов, первый и второй управляющие входы схемы сравнения, первый и второй управляющие входы бло ка формирования чисел Фибоначчи соединены с соответствующими выходами блока управления,2. Устройство по и. 1, о т л и ч ею щ е е с я тем, что блок формирования чисел фибоначчи содержит два регистра сдвига, реверсивный счетчик и счетчикинтервалов, входы которого соединенысоответственно с входом блока и со вторым управляющим входом блока, первыйи второй выходы счетчика интерваловсоединены соответственно с первым выходом блока и с первым входом реверсивного счетчика, другие входы которогоподключены соответственно к выходампервого регистра сдвига, выход реверсивного счетчика соединен со вторым выходом блока и через второй регистр сдвига - со входом первого регистра сдвига,управляющие входы реверсивного счетчика и регистров сдвига подключены к первому управляющему входу блока.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРМ 506868, кл. 6 06 Р 15/36, 1974.2, Авторское свидетельство СССРМ 402001; кл. О 06 Р 15/36,кл. б 06 Г 1/02, 1971 (прототип), 736111