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

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

Иллюстрации

Показать все

Реферат

 

Союз Советскин

Социалистическик

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6! ) Дополнительное к авт. свнд-ву— (22) Заявлено 19.09.77 (21) 2527270/18-24 (5})м. Кл.

G 06 F 15/34 с присоединением заявки ¹â€”

Государственный комитет (23) Приоритет—

Опубликовано 25.05.80. Бюллетень №19

Дата опубликования описания 28.05.80

Il0 делам изобретений и открытий (53 ) Уд К 681. 325, (088.8) (72) Авторы изобретения

С. К. Островский, В, A. Фильштинский, B. Н. Чинков, 10. А. Стеценко и В. Д. Яковец (7l) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ЭКСТРЕ N УМОВ

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

Известно устройство для определения экстремумов, содержащее генератор так товых импульсов, преобразователь, коммутатор, ключи, триггер, блок сравнения, 10 регистр, триггер экстремума, элементы

И, счетчик, элементы ИЛИ (1).

Это устройство не обеспечивает опти мального по быстродействию поиска экст ремума, так как с его помощью осущест

15 вляется прямой перебор всех возможных значений сигнала.

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

2 выкоду сумматора и к первому входу схемы сравнения, регистр экстремального значенчя функции, выход которого соединен со вторым входом схемы сравнения и входом регистра экстремального значения функции, выход которого соединен с первым входом коммутатора, второй вход которого подключен к выходу регистра текущего значения функции, второй вход устройства подключен к третьему входу схемы сравнения, выход которой подключен к третьему входу коммутатора (2).

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

736111

Педостаток этого устройства состоит в отсутствии возможности наискорейшего поиска экстремума и необходимости иметь непрерывные все без исключения выборки, а также в ограниченном динами5 ческом диапазоне, который задается установкой начальных пороговых значений.

Цель изобретения - повышение эффективности за счет сокращения числа выборок и увеличения динамического диапазо- i0 на.

Поставленная цель достигается reM, что в устройство, содержащее коммутатор, схему сравнения, выходы которой соединены соответственно со входами 15 регистра экстремумов, выход которого подключен к первому выходу устройства, введены блок формирования чисел Фибоначчи, блок памяти, блок управления и преобразователь аналог-код, вход кото- 20 рого соединен с первым выходом блока памяти, второй выход блока памяти и выход преобразователя аналог-код через коммутатор соединены со входом схемы сравнения управляющей, выход которой подключен ко входу блока управления, первый выход блока формирования чисел

Фибопаччи подключен ко второму выходу устройства, второй выход соединен с управляющими входами блока памяти и преобразователя аналог-код, вход блока формирования чисел Фибоначчи подключен ко входу устройства, управляющий вход регистра экстремумов, первый и второй управляющие входы схемы сравнения, 35 первый и второй управляющие входы блока формирования чисел Фибоначчи соединены с соответствующими выходами блока управлепия.

На фиг. 1 приведена схема устройства; на фиг. 2 и фиг. 3 - примеры сигналов и методика оптимального по быстродейст« вию разбиения интервала поиска.

Устройство содержит блок 1 памяти, преобразователь 2 аналог-код, схему 3 сравнения, состоящую из реверсивного сумматора 4 и буферного регистра 5, регистр 6 экстремумов, блок 7 формирования чисел Фибоначчи, состоящий из регистров 8 и 9 сдвига, реверсивного счетчика 1 О и счетчика 1 1 интервалов, блок

12 управления, коммутатор 13, вход 14 и выходы 15, 16 устройства.

Известен метод дихотомического поиска (метод Фибоначчи), использующий стратегию поиска экстремума по числам

Фибоначчи, задаваемых рекурентным уравенением ф(и+1) =4(и) (-М),y(<)=g,q(), (1) Числа Фибоначчи до номера 62 приведены в табл. 1; диаграмма формирования прямой и обратной последовательности . чисел Фибоначчи - в табл. 2.

Процедура поиска включает следующие этапы (табл. 1). Проводится пара измерения в точках ф (И) и ф (il -1). Согласно условию унимодальности перед вторым этапом проискодит сокращение интервала неопределенности по информации о численных значениях функции Х (Ь) в указанных точках.

Если Х Г ф(и))Х(ф(0-1Ч, (2) то экстремум слева, в противном случае

X,tô(i )» X,(ô Ü-S) $, (3) 40

I(pone того, блок формирования чисел

Фибоначчи в устройстве содержит два регистра сдвига, реверсивный счетчик и счетчик интервалов, входы которого соединены соответственно с входом блока 45 и со вторым управляющим входом блока, первый и второй выходы счетчика интервалов соединены соответственно с первым выходом блока и с первым входом реверсивного счетчика, другие входы которого 50 подключены соответственно к выходам т первого регистра сдвига, выход реверсив-. ного счетчика соединен со вторым выходом блока и через второй регистр сдви» га - со входом первого регистра сдвига, управляющие входы реверсивного счетчика и регистров сдвига подключены к первому управляющему входу блока. а экстремум справа, Особенностью данного поиска является то, что из двух точек в каждом цикле, одна всегда совпадает с точкой предыдущего шага, в которой уже проведено испытание, т. е. необходимо находить только координату одного из двух измерений.

Так как последовательность чисел

Фибоначчи весьма быстро растет и разрыв между соседними числами составляет сотни миллионов уже с сороковых номеров (см. табл. 1), то эффективность применяемого метода существенна при больших объемак обрабатываемой информации.

Следует отметить, действительность задачи, которая решается с помощью данного метода. С одной -стороны, это мини(мизация числа измерений при равной точ736 11.1

5 ности и с другой » минимизация погрешности при значительном числе точек измерения. В дальнейшем будем рассматривать только задачу быстродействия. нуляется с помощью блока 12 управления, а из буферного регистра число, поступившее первым (большее из двух), переносится снова в cyMMarop 4 и схема 3 сравнения подготовлена к приему третьего числа. A нелогично с пе рвым случаем, максимальное число также перезаписывается в регистр 6 экстремумов

20 Qo сих пор не рассматривался вопрос формирования последовательности чисел

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

Регистры 8 и 9 содержат в исходном

З состоянии единицы, а счетчик 1 1 - верхний интервал унимодальности. Наличие их необходимо для формирования прямой последовательности чисел Фибоначчи в соответствии с выражением (1), начиная

35 с Ф(1) =(1).

Проследим процесс формирования прямой и обратной последовательности чисел

Фибоначчи с помощью табл. 1 и 2.

Первое прямое число образуется после сложения в реверсивном счетчике 10 ну ля и единицы. На втором шаге единица из регистра 8 сдвигается в регистр 9-, а на третьем из счетчика 1 0 переписывается в регистр 8 (без стирания в

4 самом счетчике). Четвертым шагом сложением 1 + 1 в счетчике заканчива ется формирование второго числа Ф(2)=2.

Лалее процесс формирования продолжается последовательно по своей таблице чисел

Фибоначчи однообразно и на 40 шаге фиксируется число 610. Верхний предел при этом задается счетчиком 11 интервалов, в который предварительно вводят необходимый интервал унимодальности.

Обратная последовательность чисел

Фибоначчи Ф(И) начинается с предустановки числа (Ф(0+1) и Ф(И-1), котопые ранее, находились, соответственно, в

Принцип построения устройства для всех случаев, когда исследуемый сигнал записан на каком либо носителе .в блоке 1 памяти в непрерывной или дискретной форме,, заключается в сле дующем. Предлагаются известными распределения максимумов и минимумов на кривой. Последнее условие необходимо для выбора интервалов унимодальности и предварительного ввода его в счетчик 1 1 интервалов (здесь и далее исследуются временные сигналы или процессы). Верхние пределы унимодальности с помощью блока 12 управления последовательно вводятся в счетчик 11 и в этих заданных интервалах производится поиск экстремума.

Исходное состояние характеризуется наличием нулей во всех счетчиках и уз.лах за исключением регистров 8 и 9, где записаны единицы и счетчика 11 интервалов, куда введен верхний предел интервала унимодальности. Коммутатор

13 устанавливают в положение, указанное на фиг. 1. В противном случае входное напряжение подключают к преобразователю 2 аналог-код для замены непрерывных значений сигнала дискретными.

Команда на выборку последовательности значений сигнала из блока 1 памяти или на запуск преобразователя 2 поступает из блока 7 формирования чисел Фибоначчи. Первое числовое значение записывается по отрицательному входу в реверсивный сумматор 4 и переносится в параллельном коде без изменения в буферный регистр 5. По приходу второго значения сигнала на попожительный вход сумматора 4 вычисленная разность оценивается по критериям (2) и (3).

Если она положительная, т. е. выпол» няется условие (2), можно сделать вы вод, что максимум слева по оси времени.

Йля сохранения максимального из первой поступившей пары чисел необходимо полученную разность прибавить к содержимому буферного регистра 5 и результат, равный второму (большему) из чисел„ переписать в сумматор 4. Этим самым схема 3 сравнения подготволена для приема следуюшего (третьего) числа. Одновременно это промежуточное максималь ное значение фиксируется в регистре 6 экстремумов, но на выход оно не поступает.

Если первая разность окажется отрицательной и выполнится другое услЬвие (3), свидетельствующее о наличии максимума справа от исходной точки по оси времени, то прохождение импульсных последовательностей изменится по сравне10. нию с первым случаем. Сумматор 4 об25

7, 611

penepcNBH0M счетчике 1 0 и pet истре 9, меняются местами, а Ф(Р) оставляется в регистре Н, Кроме того, счетчик

10 устанавливается в режим вычитания.

Здесь следует отметить особенность формирования Ф (.й) — обратной последоI вательности. Чтобы обратные числа начинались с Ф (13) = 377, необходимо в

I прямых числах закончить на номере 15, т. е. на два номера далее требуемого 10

Ф(15) = 987. Предустановка происходит таким образом, что число 987 переносится в регистр 9 из счетчика 1 О, последний сбрасывается в нуль и в него записывается 610. На первом шаге оно 15 вычитается из предыдущего Ф (1) !

Ф (13) = 377 и начинается обратная последовательность. Второе обратное число формируется после сдвига 610 из регистра 8 в регистр 9, а 377 - 20 из счетчика 10 в регистр 8. После вычитания 610-377 появляется второе число 233. Дальнейшее получение обратных чисел происходит аналогично.

На фиг. 2 приведены два крайних случая, которые могут представиться в в практике поиска экстремума сигнала на интервале унимодальности Т-"34с. ,Кривая 1 иллюстирует нахождение максимума на левом конце интервала, а

2 — на правом.

Оба сигнала изменяются по указанным законам в течение 34 с. Записанные в непрерывном виде на магнитном (либо ином носителе) или в виде кода в бпоке

1 памяти, эти сигналы хранятся до момента поиска их максимумов. Требуется .в кратчайшее время отыскать и измерить максимум.

Г! р и м е р 1. Поиск ведется от правого конца интервала к левому. При этом для простоты изложения соблюдают тот же временной масштаб. На практике нет смысла 34 с искать точку и время можно сжать в 100 - 1000 раз.

Поиск начинаем с числа 4„(7) - 21!. (Для этого требуется вводить в блок 7 числа 34 H 55 ) .

Б точке .Ь= 21 кодируется значение сигнала 1 (21 ) и записывается по or- 50 рицательному входу в реверсивном сумматоре 4 и переносится без изменения в буферный регистр 5. По приходу второго значения сигнал. Х (13 ) на сумматор 4 вычисляется разность и оценивается по критериям (2) и (3). Соблюдается условие (2), зна ит экстремум слева. Следуя нумерации точек по кривой 1, видим, что

1 сигнал возрастает, и рг зность у (! ) (21! ) для сохранения максима гьно Q из этойпары чисел должна добавиться в буферный регистр 5 и переписаться в сумматор 4, а затем в регистр 6 экстремума. Здесь будет фикс иров атьс я текущее значение максимума до получения итоговой величины.

Лалее сигнал пробегает последовательно значения х(8.!), х(5, ), x(3g), x(2 ) х(1 ), Процесс сохранения максимальных значений такой же как и ранее и позволяет сделать одно из двух основных заключений по поиску экстремумов. Если экстремум ожидается слева, то никаких изменений в порядке измерений мгновенных значений сигнала, равно как и формировании обратной последовательности чисел Ф иб она ччи не наблюдается.

Регистр 6 зафиксирует максимум х(2,() - (заштрихованная точка 2 4 на фиг. 2), который будет считан по приходу импульса с блока 12 управления.

Вместо обычного прохождения 34 измеряемых точек сигнала искомый результат получен на седьмом такте.

Пример 2. Процесс, протекающий по кривой 2 (см. фиг. 2), позволяåò выявить вторую особенность поиска экстремумов. Первое измерение сигнала при интервале 34 с осуществляем лищь для точки = 21, а второе — для

$-.-13. Теперь полученные значения удовлетворяют неравенству (3), т. е. х(21 )) х(13„). Схема 3 сравнения по другому реагирует на эту ситуацию. Сумматор 4 .обнуляется„ а из буферного регистра число, поступившее первым, т. е. x(21< ) переносится снова в сумматор 4 для подготовки к сравнению с новым поступающим значением. В отличие от первого примера, здесь с той точки аргумента, где обнаружен факт, что максимум находится справа (работает условие унимодальности), необходимо формировать новую прямую последовательность чисел

Фибоначчи Ф (И) до того же номера

Ф (6) = 13, на котором имеет место неравенство x(1 3) (х(21 ) . Зто обстоятельство является второй особенностью поиска экстремума. В этот момент с выхода реверсивного сумматора 4 импульс перехода через нуль является управляющим импульсом для начала формирования новой прямой последовательности чисел.

Формирование идет с запасом до числа

Ф 1(8) = 342, чтобы стало возможным получение обратной последовательности

10 ние временных затрат на определение текущих значений сигнала.

Пример 3. Приведенная на фиг.

3 форма изменения сигнала, характеризуется срединным положением максимума и является промежуточным случаем в сравнении с двумя предыдущими. Интервал унимодальности Т = 13 с. Поэ« тому первыми измеренными значениями являются х(8 ) = х(5 ). Здесь имеет место равенство амплитуд, однако в соответствии с формулой (2), поиск продолжается так же, как если бы соблюдалось х(8 ) < х(5 ). В точке Ф (3) = 3 сиг3 1 нал становится меньшим и поэтому генерируется последовательность чисел Ф .

Далее иллюстрируется возможность повышения точности определения момента экстремума за счет изменения масштаба по оси времени. На любом из циклов поиска этот масштаб можно уменьшить произвольно и добиваться необходимого снижения погрешности.

Процедура поиска для минимумов ничем не отличается от рассмотренной для макс имумов.

1о

l5 го

Таблица 1

Числа Фибоначчи

1 32

2 33

3 34

5 35

8 36

13 37

21 38

34 39

55 40

89 41

144 42

233 43

377 44

610 45

987 46

1597 47

2584 48

12

j5

9 7361

Ф . Определяется амплитуда сигнала г. х (13 ), сравнивается с х(21„) и остав ляется большее как и в конце предыдущего. такта, т. е. х(13 ) 7 х(21 ), или, что то же самое х(13 ) ) х(8 ), так как точки новой Ф - последовательности иногда совпадают со старыми точками.

Такой вид неравенства приводит к необходимости формировать новую Ф—

3 последовательность, как прямую, так и обратную, а именно, с точки Ф (0) ф (5) = 8. Следуюшей измерейной точкой 4 (кривая 2) является х(8 ). Так как и это значение больше чем х(5) (r. е. максимум находится еще правее), возникает необходимость в дальнейшем сужении интервала нахождения максиму ма. Для этого крайнего случая, наиболее трудоемкого по обработке кривой, только на 6 цикле поиска удается отыскать максимум в точке х(1 g ) . (заштрихованная первая точка на фиг. 3).

s.

Однако по числу измерения и этот г5 пример показывает пятикратное сокраще3524578

5 702887

14930352

24157817

39088169

63245986

1 655 80141

267914296

433494437

701408733

1 83631 1 903

2971215073

4807526976

7778742049

736111

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

4181 49

6765

20

10946

17711 52

28657

46368 54 1 39583862445

75025

55 225851433717

26

28

832040

60 2504730781961

1 346269 61 4052739537881

2178309 62 6557470319842

Таблица 2

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

0 610

1 0

987 — 610 = 377

1 + 0 = 1

610 ъ- 610

377

377 †.610 — 377 = 233

1 - 1 = 2

1 — 1

377 377

233

233

1 + 2 = 3

377 — 233 = 144

2 2

233 233

1 44

144

121393 56

196418 57

317811 58

5 L4229 59

20365011074

32951280099

53316291173

86267571272

365435296162

591286729879

956722026041

1548008755920

233 — 1 44 = 89

736111

1 44 1 44

3 3

12

3 + 5 = 8

5 — «5

89 «ъ 89

55

5 + 8 = 13

55 55

1 3.

18

8 + 13 = 21

13 1%.

21

21

13 + 21 = 34

21 В 21

13! 34

21 .+ - 34 = 55

13 — » 13

8 8

29 55 — ч 35

30 89

55 - .89 "- 144

144

5 — 3

89 + 144 = 233

3 — 2 3

35 144 144

36 233

233

37 144 + 233 =. 377

38 233-Ъ-233

2 «2

377

233 + 377 .= 610

39 377

1 1

2 1 — - 21

26 5 34

27 55

32 89 89

ЗЗ 144 55

55 89

14

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

144 — 89 = 55

89 — 55 = 34

55 — 34 = 21

34 — Ф34

34 — 21 = 13

21 — 13 = 8

13 8 - .б

3 — 2

736111

Формула изобретения

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

Фибоначчи, блок памяти, блок управления, и преобразователь аналог-код, вход которого соединен с первым выходом блока памяти, второй выход блока памяти и выход преобразователя аналог-код через коммутатор соединены со входом схемы сравнения управляющей, выход которой подключен ко входу блока управления, 20 первый выход блока формирования чисел

Фибоначчи подключен zo второму выходу устройства, второй выход соединен с управляющими входами блока памяти и преобразователя аналог-код, вход блока фор- 25 мирования чисел Фибоначчи подключен ко входу устройства, управляющий вход регистра экстремумов, первый и второй управляющие входы схемы сравнения, первый и второй управляющие входы бло- 30 ка формирования чисел Фибоначчи соединены с соответствующими выходами блока управления.

2. Устройство по и. 1, î т л и ч ею щ е е с я тем, что блок формирования чисел Фибоначчи содержит два регистра сдвига, реверсивный счетчик и счетчик интервалов, входы которого соединены соответственно с входом блока и со вторым управляющим входом блока, первый и второй выходы счетчика интервалов соединены соответственно с первым выходом блока и с первым входом реверсивного счетчика, другие входы которого подключены соответственно к выходам первого регистра сдвига, выход реверсивного счетчика соединен со вторым выходом блока и через второй регистр сдвига — со входом первого регистра сдвига, управляющие входы реверсивного счетчика и регистров сдвига подключены к первому управляющему входу блока.

Источники информации, принятые во внимание при экспертизе

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

¹ 506868, кл. 5 06 F 15/36, 1974.

2. Авторское свидетельство СССР № 402001; кл. Q 06 F 15/36, кл 5 06 F 1/02 1971 (прототип)