Устройство для определения локальных экстремумов функции

 

Изобретение относится к автоматике и вычислительной технике и предназначено для поиска экстремумов функций, представленных в виде дискретных выборок. Цель изобретения - повышение точности определения экстремума функции. Устройство содержит буферные регистры 1<SB POS="POST">1</SB> - 1<SB POS="POST">4</SB>, элементы 2<SB POS="POST">1</SB> - 2<SB POS="POST">4</SB> задержки, счетчик управления 3, коммутаторы 4<SB POS="POST">1</SB>, 4<SB POS="POST">2</SB>, регистр глобального экстремума 5, сумматор по модулю два 6, счетчик адреса экстремума 8, блок определения координаты экстремума 9, элементы И/И - НЕ 10<SB POS="POST">1</SB> - 10<SB POS="POST">4</SB>, элементы ИЛИ-НЕ 11<SB POS="POST">1</SB> - 11<SB POS="POST">4</SB>, триггеры 12<SB POS="POST">1</SB> -12<SB POS="POST">4</SB>, 13, 14<SB POS="POST">1</SB>, 14<SB POS="POST">2</SB>, элементы И 15<SB POS="POST">1</SB> - 15<SB POS="POST">10</SB>, формирователь импульсов 16, элементы ИЛИ 17<SB POS="POST">1</SB>, 17<SB POS="POST">2</SB>. ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫБОРОК ФУНКЦИИ ПОСТУПАЕТ НА ИНФОРМАЦИОННЫЙ ВХОД УСТРОЙСТВА В ПОСЛЕДОВАТЕЛЬНОМ КОДЕ. УСТРОЙСТВО ИМЕЕТ ДВА РЕЖИМА РАБОТЫ: РЕЖИМ ВЫДЕЛЕНИЯ ЛОКАЛЬНОГО ЭКСТРЕМУМА И РЕЖИМ ВЫДЕЛЕНИЯ ГЛОБАЛЬНОГО ЭКСТРЕМУМА. УСТРОЙСТВО ВЫДЕЛЯЕТ ЛОКАЛЬНЫЙ ЭКСТРЕМУМ ФУНКЦИИ ПО ТРЕМ СМЕЖНЫМ ДИСКРЕТНЫМ ВЫБОРКАМ, ОТЛИЧАЯ ЕГО ОТ ТОЧКИ ПЕРЕГИБА. ОПРЕДЕЛЕНИЕ КООРДИНАТЫ ЭКСТРЕМУМА ФУНКЦИИ ПРОИЗВОДИТСЯ ПО ДВУМ СОСЕДНИМ ВЫБОРКАМ В БЛОКЕ ОПРЕДЕЛЕНИЯ КООРДИНАТЫ ЭКСТРЕМУМА. 1 З.П. Ф-ЛЫ, 2 ИЛ.

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

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

РЕСПУБЛИК

ggy G 06 F 7/06,;;< 1, „a-г.:;-, :1<: а< .<

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTQPCHGMY СВИДЕТЕЛЬСТВУ фалья

ГОСУДАРСТВЕННЫЙ КОМИТЕТ пО изОБРетениям и ОтнРытиям

ПРИ ГКНТ СССР (61) 1290297 (21) 4380270/24-24 (22) 06, 01,88 (46) 15. 09,89, Бюл. N - 34 (71) Опытно-конструкторское бюро специальных радиотехнических систем

Новгородского политехнического института и Новгородский политехнический институт (72) Л,В.Мельник, M.Ë.Ïîäoëüñêàÿ и В,A.ßðìàêîâè÷ (53) 681,325(088.8) (56) Авторское свидетельство СССР

Р 1241227, кл. G 06 F 7/04, 1986.

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

Ф 1290297, кл, G 06 F 7/06, 1987. .1

„SU„, 1508205

2 (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЛОКАЛЪНЫХ ЭКСТРЕМУМОВ ФУНКЦИИ (57) Изобретение относится к автоматике и вычислительной технике и предназначено для поиска экстремумов функций, представленных в виде дискретных выборок. Цель изобретения повышение точности определения экстремума функции. Устройство содержит буферные регистра 1< -1<, элементы

2<-2< задержки, счетчик управления

3, коммутаторы 4< 4, регистр глобаль ного экстремума 5, сумматор по модулю два 6, счетчик адреса экстремума

8, блок определения координаты экстремума 9 элементы И/И вЂ” НЕ 10<-10, 3 1508205 элементы ИЛИ-НЕ 111-1!,, триггеры

121-12,|,, 13, 14 -14, элементы И

15„-15<, формирователь импульсов 16, элементы ИЗ И 171, 17 . Последователь- 5 ность выборок функции поступает на информационный вход устройства в последовательном коде. Устройство имеет два режима работы: режим вьделения локального экстремума и режим 10

1 вьделения глобального экстремума.

Устройство выделяет локальный экст» ремум функции по трем смежным дискретным выборкам, отличая его от точки перегиба. Определение координаты экстремума функции производится по двум соседним выборкам в блоке определения координаты экстремума, 1 з.п. ф-лы, 2 ил.

Изобретение относится к автоматике и вычислительной технике и предназначено для поиска экстремумов функции, представленных в виде дискретных выборок, .может быть использовано при разработке специализированной аппаратуры и различных автоматизированных систем управления и является усовершенствованием изобретения по авт,св. N- 1290297, 25

Цель изобретения — повьппение точности определения экстремума функции, На фиг.1 представлена блок-схема устройства для определения локальных экстремумов функции; на фиг,2 - блок. 30 схема блока определения координаты экстремума.

Устройство для определения локальных экстремумов функции (фиг.1) содержит буферные регистры 1,-14, элементы 2 -2+ задержки, счетчик 3 управления, коммутаторы 4,1 и 4, регистр

5 глобального экстремума, сумматор

6 по модулю два, счетчик 7 адреса экстремума, регистр 8 адреса экстрему- 40 ма, блок 9 определения координаты экстремума, элементы И/И-HE 101-10, элементь| ИЛИ-HE 111-114 9 триггеры 12112,, 13, 14 1 и 14, элементы И 15115 ., формирователь 16.импульсов, |О элементы ИЛИ 17 и 17, вход 18 за.пуска, тактовый вход 19, информационный вход 20, вход 21 выбора режима, информационный выход 22 и выход 23 фиксации экстремума.

Блок 9 определения координаты экст50 ! ремума (фиг.2) образуют буферные регистры 21 и 24, блоки 251 и

25 деления, сумматор 26, блок 27 сум" мирования и вычитания, двухразрядный регистр 28, вход 29 разрешения записи, первый 30, второй 31 и третий

32 информационные входы, а также функциональные входы 33 и 34, Устройство работает следующим образом, Последовательность выборок функции поступает на информационный вход 20 устройства в последовательном коде старшими разрядами вперед и записывается в первый буферный регистр 11 . Одновременно старший .разряд хранящегося в первом буферном регистре 1 чис1 ла переписывается во второй буферный регистр 1, старший разряд числа, хранящегося во втором буферном регистре 1, — в третий буферный регистр

1, а старший разряд числа, хранящегося в третьем буферном регистре

1 » — в четвертый буферный регистр 1, Каждый поступающий разряд сопровождается сигналом на тактовом входе 19 (при этом на входе 18 запуска устройства установлен сигнал "1"), Тот же тактовый сигнал увеличивает содержимое счетчика 3 управления, емкость кокоторого равна количеству разрядов поступающих чисел.

Устройство имеет два режима работы, В режиме выделения локальных экстремумов на входе 21 выбора режима установлен сигнал "0", в режиме вьделения глобального экстремума на входе 21 выбора режима установлен сигнал

"1". ачало работы устройства определяется поступлением сигнала на вход

18 запуска. При этом тактовые сигналы по тактовому входу 19 поступают через элемент И 15 и элемент 21 задержки на входы управления сдвигом буферных регистров 1,-1 и регистра 5 глобального экстремума.

Рассмотрим процессы выделения ло" кального экстремума. В буферных регистрах 11-1< хранятся четыре смежные по номеру выборки функции. Предположим, что в данный момент времени в первом буферном регистре 11 нахо5

1О

30

5

150 дится N „, выборки функции, во втором буферном регистре 1 — N выборка функции, в третьем буферном регистре 1> — N, выборка функции, в четвертом буферном регистре 14 — N выборка функции, Сравнение производится И +,, N> Nx, выборок функции поразрядно каждый такт, начиная со старшего .разряда. Если все очеред.ные разряды выборок функций на выходах буферных регистров 1„ -1 равны единице, то на прямых выходах всех элементов И/И-НЕ 10< †> устанавливается потенциал "1", а на выходах элементов ИЛИ-НЕ 11 -11 — потенциал

"О" и триггеры 12,-12з не изменяют своего состояния, Если очередные разряды выборок функции все равны нулю, то на объединенных инверсных выходах элементов И/И-НЕ 10,-10 (соединенных в виде МОНТАЖНОГО И) устанавливается потенциал "1", на выходах элементов ИЛИ-НЕ 11 -11 — потенциал "0", а триггеры 12, — 12 также не изменяют своего состояния, Если часть разрядов выборок функции на выходах буферных регистров 1, -1З нулевые, а часть — единичные, то в единичное состояние устанавливаются те из триггеров 12, разряды в соответствующих буферных регистрах 1 кото3 рых равны "0". В дальнейшем сигнал

"0" с инверсного выхода данного триггера !2 поступает на вход соответ,! ствующего элемента И/И-НЕ 10, имитируя поступление минимального числа.

Таким образом, в нулевом состоянии находится триггер (или триггеры) )2 соответствующий максимальной (или в случае равенства выборок функции максимальным) из выборок функции в буферных регистрах 1 -1 . При этом в данном режиме работы триггер 12 на4 ходится в единичном состоянии, так как на выходе регистра 5 глобального экстремума присутствует "0" вследствие обнуления всех регистров перед запуском устройства, Одновременно на входы сумматора 6 по модулю два поступают поразрядно выборки функции N +, и N, ° Они же подаются на вход установки в единич1 ное состояние триггера 14, а разряды выборки функции Б, — на вход .; установки в единичное состояние триггера 14<, Если все разряды выборок функции N „ „ и 1! „, равны, т,е, выбор ки функции равны между собой, то оба

6 триггера 14, и 14 2 не изменяют своего состояния, на прямых выходах триг14 H 14 прису ли.выборки функции N,,и N, не равны, то первые же различные старшие разряды вызывают появление на выходе сумматора 6 по модулю два "!". Формирователь 16 импульса по этому сигналу формирует импульс, который через элемент И 158 подается на счетные входы триггеров 14 и 14, По этому импульсу в единичное состояние по выходу переходит тот триггер 14, на входе установки в,единичное состояние которого присутствует "1". Таким образом, фиксируется большее из значений выборок функции N, и Ы „,. Чтобы избежать повторного срабатывания триггеров 14 < и 14 за данный цикл сравнения, на элемент И 15 подаются сигналы с инверсных входов триггеров 14„ и 14

Через и тактов (n — количество разрядов в выборке) после того, как следующая выборка функции будет полностью записана в первый буферный регистр 1, счетчик 3 управления выдает сигнал переполнения, который увеличивает на единицу содержимое счетчика 7 адреса экстремума и поступает на входы элементов И 15„ -15<, 15 и !5(о .

В дальнейшем возможны следующие варианты, Если триггеры 2 †12 > уста" новлены соответственно в состояние

l0 т.е, выборки функции находятся в соотношении NÄ+, (N > N„,, то на выходе элемента И 15 появляется сиг40 нал, который через элементы ИЛИ

17 и И 15! поступает на выход 23 фиксации экстремума, а также на вход разрешения записи регистра 8 адреса экстремума, в который переписывается значение адреса локального экстремума из счетчика 7 адреса экстремума. Таким образом будет зафиксирован локальный максимум, При этом в первом буферном регистре 1 уже находится N « выборка функции, во втором буферном регистре 1 — И„, выборка функции, в третьем буферном регистре 1 - N „ выборка функции, в четвертом буферном регистре 1 < — N „, выборка функции.

Одновременно сигнал с выхода элемента И 15 подается на вход 29 разрешения записи блока 9 определения координаты экстремума. По сигналу переполнения со счетчика 3 управления через элементы И 15> и 151р передаются сигналы с прямых выходов триггеров 14 и 14 на адресные входы коммутатора 4< и на функциональный вход 33 блока 9 определения координаты экстремума. Если триггеры 14 и 14 установлены соответственно в состояние 10 (т,е. выборки функции находятся в соотношении N „, ) N„,), то коммутатор 4 подключает выходы разрядов второго буферного регистра

1 (где находится выборка функции N )

K+i к соответствующим разрядам первого информационного входа 30 блока 9 опредеютения координаты экстремума.

Если триггеры 14 и 14 установлены соответственно в состояние 01 (т,е. выборки функции находятся в соотношении N к,(И ), то коммутатор 4 подключает выходы разрядов четвертого буферного регистра 11 (где находится выборка функции N«) к соответ. ствующим разрядам первого информаци- 25 онного входа 30 блока 9 определения координаты экстремума, На второй информационный вход 31 блока 9 определения координаты экстремума по сигналу с выхода элемента И 15 ком- 30

7 мутатор 4 подключает выходы разрядов третьего буферного регистра . Код на адресных входах коммутатора 4 я

10 (в режиме определения локального экстр™ума) . На третий информационный вход 32 блока 9 определения координаты экстремума подается номер выборки N локального экстремума функК ции с вьгкода регистра 8 адреса зкст" ремума. Координата локального экст- 40 ремума появляется на выходе 22 устройства через время Т „ после появления сигнала на выходе 23 фиксации экстремума, причем определение координаты локального экстремума осущест- 45 вляется,по времени параллельно со . следующим циклом сравнения выборок функции !! г, N „, NK 1 так как блок

К+1

9 определения координаты экстремума работает автономно.

Блок 9 определения координаты экст50 ремума работает следующим образом.

По сигналу разрешения записи, поступившему на вход 29 производится sa) пись NK, выборки функции из второго буферного регистра 1 (при коде

10 на адресных входах коммутатора 4,) по информационному входу 30 в буферный регистр 24), Если на адресных вхо.

1508205 8 дах коммутатора 41. — код 01 то в буР ферный регистр 24 хранения перепи( сывается значение N выборки функМ-i ции иэ четвертого буферного регистра 1 . Тем же сигналом разрешения записи по входу 23 производится запись N g выборки функции из третьего буферного регистра 1 в буферный регистр 24< (код на адресных входах коммутатора 4 — 10), Одновременно по с сигналу с входа 29 разрешения записи происходит запись кода с выходов триг-, геров 14 < и )4 через открытые элементы И 15 и 15, в двухразрядный регистр 28. После окончания сигнала по входу 29 буферные регистры 24 и 24 и двухразрядный регистр 28 переходят в режим "Хранение — считывание", Выборки функции поступают из соответствующих регистров на соответствующие входы первого блока 25 деления. На выходе этого блока 25 деления появ( ляется результат: отношение числа из регистра 24< к числу из регистра 24 и

Этот результат передается на первый информационный вход сумматора 26, на второй информационный вход которого подается код "1", на выходе сумматора имеем результат сложения (1+ Ы ), На первый информационный вход блока 25 деления подается Ы, на второй информационный вход — результат сложения (1 + ). На выходе этого блока получаем результат от деления р

0( — Этот результат р подается

1+ oE на второй информационный вход блока

27 суммирования и вычитания, на первый информационный вход которого подан номер выборки N no nbHo o MaK.— к симума. В блоке 27 происходит вычисление координаты Х, путем сложения

К+, если NK,) N„,, или вычитания

К-, если N„+,(И„,, и результат появляется на выходе 22 ° Процедура сложения или вычитания определяется кодом, подаваемым на функциональный вход блока 27 суммирования и вычитания с выхода двухразрядного регистра

28 хранения. Код 10 соответствует сложению, код 01 — вычитанию. Возможна ситуация М„, =И „ „ тогда код на выходах триггеров 141 и 14 будет 00, Этот код по сигналу с входа

29 записывается в двухразрядный регистр 28 блока 9 определения координаты экстремума В соответствии с этим кодом в блок 27 суммирования

1508205

1О и вычитания помещается номер выборки

И „ локального максимума, который совпадает "с координатой этого максимума

Х =К, Эта координата передается на .ийформационный выход 22 °

Если триггеры 1 2 -12 > установлены в состояние 001 (т.е ° N =N )N )

"+1 к KI ) то значение выборки N „, =N к может быть локальным максимумом либо точ- 10 кой перегиба в зависимости от дальнейшего поведения функции. Эта ситуация фиксируется элементом И 15, импульс на выходе которого переводит триггер 13 в единичное состояние, Ес- I5 ли в дальнейшем значение функции убывает (т,е. N„zN„„=N„), то триггеры 121-12 устанавливаются в состояние 100, Это состояние фиксируется элементом И 15, при этом триггер 13 20 переводится в нулевое состояние, а на выходе 23 формируется сигнал локального максимума. Определение координаты локального максимума происходит в блоке 9 определения координаты экст- 25 ремума аналогично описанному. Если при Nlcti =М > NK- в дальнейшем значение функции возрастает (т,е, N >

>NÄ, =Н„), то триггеры I?,-12 устанавливаются в состояние 011. Это со- 30 ответствует ситуации перегиба функции, при этом сигнал формируется на выходе элемента И 15, что приводит к установке триггера 13 в нулевое состояние. Сигнал на выходе 23 устройства при этом не формируется, Устройство может также работать в режиме вьщеления глобального экстремума. При этом на входе 21 выбора режима устанавливается потенциал 40

"1", Вьщеление глобального экстремума осуществляется аналогично вьщелению локального экстремума, но каждый выделенный при этом локальный экстремум сравнивается элементами И/И-НЕ 45

10, ИЛИ-НЕ 11 и триггером 124 с те" кущим глобальным экстремумом, хранящемся в регистре 5 глобального экстремума. Сигнал на выходе 23 фиксации . экстремума формируется при этОм тОль- 50 ко в случае когда Як ) N Вiгде МГэ значение выборки функции текущего глобального экстремума. Этим сигналом в регистр 5 глобального экстремума через элемент 2> задержки и открытый элемент И 156 после окончания цикла сравнения переписывается значеийе Н выборки функции из третьего буА буферного регистра 1>, Затем с задержкой на время, равное времени перезаписи из третьего буферного регистра 1 в регистр 5 глобального экъ стремума, на адресных входах второго коммутатора 42 сформируется код 11.

По этому коду коммутатор 4 подключает выходы разрядов регистра 5 глобального экстремума к соответствующим разрядам второго информационного вхо-. да 31 блока 9 определения координаты экстремума.

j (В дальнейшем определение координаты глобального экстремума производится аналогично определению координаты локального экстремума в блоке 9 определения координаты экстремума, По окончании цикла сравнения с задержкой на время, в течение которого в блок

9 определения координаты экстремума будут записаны значения выборок функ-. ции и код с выходов элементов И 15 и

15,, осуществляется обнуление триггеров 12 -12, 141 и 14z сигналом через элемент 2z задержки. Йачинается новый цикл сравнения.

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

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

I соединены соответственно с инверсными выходами шестого и седьмого .триггеров, счетные входы которых соеди-. нены с выходом восьмого элемента И, а входы установки в "0" — с выходом второго элемента задержки, вход которого соединен с первыми входами девятого и десятого элементов И, вторые входы которых соединены с прямы1508205

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

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

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

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

40 читания соединены с информационными выходами блока, 1508205

72

Составитель В.Козлов

Редактор . А,Orap ТехредЛ.Олийнык Корректор Н.Борисова

Заказ 5541/50 Тирам 668 Подлнсное

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

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

Производственно-издательский комбинат "Патент", г. Умгород, ул. Гагарина, 103