Устройство для определения экстремумов Советский патент 1980 года по МПК G06F17/17 

Изобретение относится к вычислительной технике и может быть использовано в автоматизированных, системах контроля различных процессов, например при построении анализаторов сигналов интегрирующих машин. Известно устройство для определения экстремумов, содержащее генератор тактовых импульсов, преобразователь, коммутатор, КЛЮЧИ, триггер, блок сравнения, регистр, триггер экстремума, элементы И, счетчик, элементы ИЛИ l. Это устройство не обеспечивает оптимального по быстродействию поиска экст ремума, так как с его помощью осуществляется прямой перебор всех возможных значений сигнала. Наиболее близким к изобретению по технической сущности является устройство, содержащее сумматор, первый вход которого соединен с первым входом устройства, второй вход сумматора соединен с выходом регистра текущего значения функции, вход которого подключен к выходу сумматора и к первому входу схемы сравнения, регистр экстремального значения функции, выход которого соединен со вторым входом схемы сравнения и входом регистра экстремального значения функции, выход которого соединен с первым входом коммутатора, второй вход которого подключен к выходу регистра текущего значения функции, второй вход устройства подключен к третьему входу схемы сравнения, выход которой подключен к третьему входу коммутатора 2. В исходном состоянии его регистры содержат начальное значение функции, а на входе схемы сравнения установлен заданный потенциал, по отношению к которому осуществляется оценка наибольших (наименьших) значений функции. Далее приращения функции последовательно и непрерывно сравниваются по итерациям и результаты сравнения записываются в регистре экстремального значения функции и сохраняются искомые значения. Недостаток этого устройства состоит в отсутствии возможности наискорейшего поиска экстремума и необходимости и}иеть -непрерывные все без исключения выборки, а также в ограниченном динамическом диапазоне, который задается установкой начальных пороговых значений. Цель Изобретения - повышение эффективности за счет сокращения числа выборок и увеличения динамического диапазона. Поставленная цель достигается тем, что в устройство, содержащее коммутатор, схему сравнения, выходы которой соединены соответственно со входами регистра экстремумов, выход которого подключен к первому выходу устройства, Введены блок формирования чисел Фибоначчи, блок памяти, блок управления и преобразователь аналог-код, вход которого соединен с первым выходом блока памяти, второй выход блока памяти и выход преобразователя аналог- год через KOMfvfyTaTop соединены со входом схемы срав}1ения управляющей, выход которой подключен ко входу блока управления, первый выход блока формирования чисел Фибоначчи подключен ко второму выходу устройства, второй выход соединен с управляющими входами блока памяти и преобразователя аналог-код, вход блока формирования чисел Фибоначчи подключен ко входу устройства, управляющий вход регистра экстремумов, первый и второй управляющие входы схемы сравнения, первый и второй управляющие входы блок формирования чисел Фибоначчи соединены с соответствующими выходами блока управления. Кроме того, блок формирования чисел Фибоначчи в устройстве содержит два регистра сдвига, реверсивный счетчик и счетчик интервалов, входы которого соединены соответственно с входом блока и со вторым управляющим входом блока, первый и второй выходы счетчика интервалов соединены соответственно с первы выходом блока и с первым входом ревер сивного счетчика, другие входы которого подключены соответственно к выходам первого регистра сдвига, выход реверсив лого счетчика соединен со вторым выходом блока и черезвторой регистр сдвига - со входом первого регистра сдвига управляющие входы реверсивного счетчик и регистров сдвига подключены к первом управляющему входу блока. На фиг. 1 приведена схема устройства; а фиг. 2 и фиг. 3 - примеры сигналов методика оптимального по быстродейстию разбиения интервала поиска. Устройство содержит блок 1 памяти, реобразователь 2 аналог-«од, схему 3 равнения, состоящую из реверсивного умматора 4 и буферного регистра 5, егистр 6 экстремумов, блок 7 формироания чисел Фибоначчи, состоящий из реистров 8 и 9 сдвига, реверсивного счетика 10 и счетчика 11 интервалов, блок 2 управления, коммутатор 13, вход 14 выходы 15, 16 устройства. Известен метод дихотомического поска (метод Фибоначчи), использующий тратегию поиска экстремума по числам ибоначчи, задаваемыхрекурентным уравениемФCn-))tи-1),(,q)(lЬ2.(l) Числа Фибоначчи до номера 62 приведены в табл. 1; диаграмма формирования прямой и обратной последовательности Чисел Фибоначчи - в табл. 2. Процедура поиска включает следующие этапы (табл. 1). Проводится пара измерения в точках ф (и) и ф ( n-l). Согласно условию унимодальности перед вторым этапом происходит сокращение интервала неопределенности по информации о численных значениях функции X (-t) в указанных точках. Если )J X lti-1 3, (2) то экстремум слева, в противном случае 01,)1, (3) а экстремум справа. Особенностью данного поиска является то, что из двух точек в каждом цикле, одна всегда совпадает с точкой предыдущего шага, в которой уже проведено испытание , т. е. необходимо находить только координату, одного из двух измерений. Так как последовательность чисел Фибоначчи весьма быстро растет и разрыв между соседними числами составляет сотни миллионов уже с сороковых номеров (см. табл. 1), то эффективность применяемого метода существенна при больших объемах обрабатываемой информации. Следует отметить, действительность задачи, которая решается с помощью данного метода, С одной стороны, это мини(мизация числа измерений при равной точ5 нести и с другой - минимизация погреш ности при значительном числе точек изм рения. В дальнейщем будем рассматривать только задачу быстродействия. Принцип построения устройства для всех случаев, когда исследуемый сигнал записан на каком 1ибо носителе .в блоке 1 памяти в непрерывной или дискретной форме,, заключается в еле- дующем. Предлагаются известными распределения максимумов и минимумов на кривой. Последнее условие необходимо для выбора интервалов унимодальности и предварительного ввода его в счетчик 11 интервалов (здесь и далее исследуются временные сигналы или процессы). Верхние пределы унимодальности с помощью блока 12 управления последовательно вводятся в счетчик 11 и в этих заданных интервалах производится поиск экстремума. Исходное состояние характеризуется наличием нулей во всех счетчиках и уз- .лах за исключением регистров 8 и 9, где записаны единицы и счетчика 11 интервалов, куда введен верхний предел интервала унимодальности. Коммутатор 13 устанавливают в положение, указанное на фиг. 1. В противном случае вход ное напряжение подключают к преобразо вателю 2 аналог-код для замены непрерывных значений сигнала дискретными. Команда на вь1борку последовательности значений сигнала из блока 1 памяти или на запуск преобразователя 2 поступает из блока 7 формирования чисел Фибоначчи. Первое числовое значение записывается по отрицательному вхо ду в реверсивный сумматор 4 и перен о- сится в параллельном коде без изменения в буферный регистр 5. По приходу второго значения сигнала на положитель ный вход сумматора 4 вычисленная разность оценивается по критериям (2) и (3). Если она положительная, т. е. выпол няется условие (2), можно сделать вывод, что максимум слева по оси времен Для сохранения максимального из перво поступившей пары чисел необходимо полу ченную разность прибавить к содержимо му буферного регистра 5 и результаТ| равный второму (большему) из чисел переписать в сумматор 4. Этим самым схема 3 сравнения подготволена для при ема следующего (третьего) числа. Одновременно это промежуточное максималь- i6 ное значение фиксируется в регистре 6 SKcrpeN-iyMoB, но на выход оно не поступает. Если первая разность окажется отрицательной и выполнится другое услбвие (3), свидетельствующее о наличии максимума справа от исходной точки по оси времени, то прохождение импульсных последовательностей изменится по сравнению с первым случаем. Сумматор 4 обнуляется с помощью блока 12 управления, а из буферного регистра число, поступившее первым (большее из двух), переносится снова в сумматор 4 и схема 3 сравнения подготовлена к приему третьего числа. Аналогично с первым случаем, максимальное число также перезаписывается в регистр 6 экстремумовДо сих пор не рассматривался вопрос формирования последовательности чисел Фибоначчи, которые по существу и определяют существенное сокращение выборок сигнала и оптимизацию, в смысле быстродействия процесса поиска экстре- мумов. Для ее осуществления необходимо формировать как прямую, так и обратную последовательность чисел Фибоначчи. Регистры 8 и 9 содержат в исходном состоянии единицы, а счетчик 11 - верхний интервал унимодальности. Наличие их необходимо для формирования прямой последовательности чисел Фибоначчи в соответствии с выражением (1), начиная с Ф(1) -(1). Проследим процесс формирования прямой и обратной последовательности чисел Фибоначчи с помощью табл. 1 и 2. Первое прямое число образуется после сложения в реверсивном счетчике 10 нуля и единицы. На втором щаге единица из регистра 8 сдвигается в регистр 9-, а на третьем из счетчика 10 переписывается в регистр 8 (без стирания в самом счетчике). Четвертым шагом сложением 1 + 1 в счетчике заканчивается формирование второго числа Ф(2)2, Далее процесс формирования продолжается последовательно по своей таблице чисел Фибоначчи однообразно и на 40 шаге . фиксируется число 61О. Верхний предел при этом задается счетчиком 11 интервалов, в который предварительно вводят необходимый интервал унимодальности. Обратная последовательность чисел Фибоначчи Ф(П) начинается с предустановки числа (ф(и+1) и Ф(11-1) , которые ранее, находились, соответственно, в реверсивном счетчике 10 и peinicrpe 9, меняются местами, а Ф(И) остааг1яет ся в регистре 8. Кроме того, счетчик 10 устанавливается в режим вычитания. Здесь следует отметить особеннсють формирования Ф (,И) - обратной последе вательности. Чтобы обратные числа начи нались с ф(13) 377, необходимо в прямых числах закончить на номере 15, т. е. на два номера далее требуемого Ф{15) - 987, Предустановка происходит таким образом, что число 987 переносится в регистр 9 из счетчика 10, последний сбрасывается в нуль н в него записывается 610, На первом шаге оно вычитается из предыдущего Ф (1) Ф (13) 377 и начинается обратная последовательность. Второе обратное число формируется после сдвига 610 из регистра 8 в регистр 9, а 377 - из счетчика 1О в регистр 8, После вычитания 610-377 появляется второе число 233, Дальнейшее получение обратных чисел происходит аналогично. На фиг, 2 приведены два крайних: случая, которые могут представиться в в практике поиска экстремума сигнала на интервале унимодальности , Кривая 1 иллюстирует нахождение максимума на левом конце интервала, а 2 - на правом. Оба сигнала изменяются по указанны законам в течение 34 с. Записанные в непрерывном виде на магнитном {либо Ином носителе) или в виде кода в блоке 1 памяти, эти сигналы хранятся до момента поиска их максимумов. Требуется в кратчайшее время отыскать и измерит максимум, Пример 1, Поиск ведется от правого конца интервала к левому. При этом для простоты изложения соблюдают тот же временной масштаб. На практике нет смысла 34 с искать точку и время можно сжать в 1ОО - 100О раз, Поиск начинаем с числа (7) - 21 (Для этого требуется вводить в блок 7 числа 34 и 55), В точке -Ь 21 кодируется значени сигнала , v ( 2 1 ) н записывается по о рицательному входу в реверсивном сумм торе 4 и переносится без изменения в б (})ерный регистр 5, По приходу второго .значения сигнал j X (1 3j ) на сумматор вычисляется разность и оценивается по критериям (2) и (3), Соблюдается усло вие (2), значит экстремум слева. Следу нумерацип точек по кривой 1, видим, чт в игнал возрастает, и ра.иность X(lU) (21) для сохранения максималглш о из той пары чисел должна добавиться в буерный регистр 5 и переписаться в суматор 4, а затем в регистр 6 экстремуа. Здесь будет фиксироваться текущее значение максимума до получения итоговой величины. Далее сигнал пробегает последовательно значения х( 8), х(5), х(З), ;с(2) и x(l-j). Процесс сохранения максимальных значений такой же как и ранее и позволяет сделать одно из двух основных аключений по поиску экстремумов. Если экстремум ожидается слева, то никаких изменений в порядке измерений мгновеных значений сигнала, равно как и формировании обратной последовательности чисел Фибоначчи не наблюдается. Регистр 6 зафиксирует максимум х( 2) - (заштрихованная точка 2 на фиг, 2), который будет считан по приходу импульса с блока 12 управления. Вместо обычного прохождения 34 измеряемых точек сигнала искомый результат получен на седьмом такте. Пример 2, Процесс, протекающий по кривой 2 (см. фиг. 2), позволяет выявить вторую особенность поиска экстремумов. Первое измерение сигнала при интервале 34 с осуществляем лищь для точки -Ь 21, а второе - для -t -13. Теперь полученные значения удовлетворяют неравенству (3), т, е, х(21, ) х( 13 ).-Схема 3 сравнения по другому реагирует на эту ситуацию. Сумматор 4 обнуляется, а из буферного регистра чис- :ло, поступившее первым, т, е. х(21) переносится снова в сумматор 4 для под- готовки к сравнению с новым поступающим значением, В отличие от первого примера, здесь с той точки аргумента, где обнаружен факт, что максимум находится справа (работает условие унимодальности), необходимо формировать новую прямую последовательность чисел Фибоначчи Ф (tl) до того же номера Ф(6) - 132 , на котором имеет место неравенство х( 1 3.) х( 21 ), Это обстоятельство является второй особенностью поиска экстремума. В этот момент с выхода реверсивного сумматора 4 импульс перехода через нуль является управляющим импульсом для начала формирования новой прямой последовательности чисел. Формирование идет с запасом до числа Ф2( 8) - 34, чтобы стало возможным получение обратной последовлтольиостн ф. Определяется амплитуда сигнала X (i3, сравнивается с х(21) и оста ляется большее как и в конце предыдущего такта, т. е. х( ISj) 7 х{21 ), или что то же самое х( 13,,) х( S), гак как точки новой последовательности иногда совпадают со старыми точками. Такой вид неравенства приводит к необходимости формировать новую Ф,, последовательность, как прямую, так и обратную, а именно, с точки Ф„( О) Фл( 5) 8. Следующей измеренной точкой 4 (кривая 2) является х(8). Так как н это значение больще чем х{5) (т. е. максимум находится еще правее), возникает необходимость в дальнейшем сужении интервала нахождения максиму- ма. Для этого крайнего случая, наиболее трудоемкого по обработке кривой, только на 6 цикле поиска удается отыскать максимум в точке x(lg). (защтрихованная первая точка на фиг. 3). Однако по числу измерения и этот прдмер показывает пятикратное сокраще1110ние временных затрат на определение текущих значений сигнала. Пример 3. Приведенная на фиг. 3 форма изменения сигнала, харакгеризуется срединным положением максимума и является промежуточным случаем в сравнении с двумя предыдущими. Интервал унимодальности Т - 13 с. Поэтому первыми измеренными значениями явл$иотся х{ 8) х( 5 ). Здесь имеет место равенство амплитуд, однако в соответствии с формулой (2), поиск продолжается так же, как если бы соблюдалось х(8)х(5). В точке Ф(3) 3 сигнал становится меньшим и поэтому генерируется последовательность чисел Ф. Далее иллюстрируется возможность повышения точности определения момента . экстремума за счет изменения масштаба по оси времени. На любом из циклов поиска этот масштаб можно уменьшить произвольно и добиваться необходимого снижения погрешности. Процедура поиска для минимумов ничем не отличается от рассмотренной для максимумов.

11

73611112

Продолжение табл. 1

Диаграмма формирования прямой и обратной последовательности чисел Фибоначчи

Таблица 2

13

3 -

3f34- 5 8

736111

14 Продолжение табл. 2

-89 89

55

- 15 Формула изобретения 1. Устройство для определения экстремумов, содержащее коммутатор, схему сравнения, выходы которой соединены соответственно со входами регистра экстремумов, выход которого подключен к первому выходу устройства, отличаю щееся тем,что,с целью повышения эффективности за счет сокращения числа выборок и увеличения динамического диапазона, в него введены блок формирования чисел Фибоначчи, блок памяти, блок управления, и преобразователь аналог-код, вход которого соединен с первым выходом блока памяти, второй выход блока памяти и выход преобразователя аналог-«од через коммутатор соединены со входом схемы сравнения управляющей, выход которой подключен ко входу блока управления, первый выход блока формирования чисел Фибоначчи подключен хо второму выходу устройства, второй выход соединен с управляющими входами блока памяти и преобразователя аналог-жод, вход блока фор- мирования чисел Фибоначчи подключен ко входу устройства, управляющий вход регистра экстремумов, первый и второй управляющие входы схемы сравнения, первый и второй управляющие входы бло- 7 1116 ка формирования чисел Фибоначчи соединены с соответствующими выходами блока управления. 2. Устройство по п. 1, отличающееся тем, что блок формирования чисел Фибоначчи содержит два регистpd сдвига, реверсивный счетчик и счетчик интервалов, входы которого соединены соответственно с входом блока и со вторым управляющим входом блока, первый в второй выходы счетчика интервалов соединены соответственно с первым выходом блока и с первым входом реверсивного счетчика, другие входы которого подключены соответственно к выходам первого регистра сдвига, выход реверсивного счетчика соединен со вторым выходом блока и через второй регистр сдвига - со входом первого регистра сдвига, управляющие входы реверсивного счетчика и регистров сдвига подключены к первому управляющему входу блока. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 506868, кл. G 06 F 15/36, 1974. 2.Авторское свидетельство СССР № 40 2001; кл, Q Об F 15/36, кл. G 06 F 1/02, 1971 (прототип).

iS

Фай. t