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

, 15082 9) 6 Р 7/06 пгг.:;С йфС,Е.ТЕН ИЯ ЛОюл. У 34трукторскоехнических си о сп ин литехническ й политехнич и Л льска/06, 1 ОСУДАРСТВЕННЫЙ КОМИТЕТизоБРетениям и ОтнРытиямРИ ГКНТ СССР ОПИСАНИЕ ИЗ ВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕН КАЛЪНЫХ ЭКСТРЕМУМОВ ФУНКЦИИ(57) Изобретение относится к автоматике и вычислительной технике и пред назначено для поиска экстремумов функций, представленных в виде дискретных выборок. Цель изобретения повышение точности определения экстремума функции, Устройство содержит буферные регистра 1 -1, элементы 2-2 задержки, счетчик управления 3, коммутаторы 4, 4, регистр глобал ного экстремума 5, сумматор по модулю два 6, счетчик адреса экстремума 8, блок определения координаты экстремума 9 элементы И/И - НЕ 10-10,3 1508205 элементы ИЛИ-НЕ 111-1 триггеры 12 -12, 13, 14 -14 , элементы И 15-151 , формирователь импульсов 16, элементы ИЛИ 17, 17. Последователь ность выборок функции поступает на информационный вход устройства в последовательном коде. Устройство имеет два режима работы: режим выделения локального экстремума и режим 10 выделения глобального экстремума.Устройство выделяет локальный экстремум функции по трем смежным дискретным выборкам, отличая его от точкиперегиба, Опйделение координатыэкстремума функции производится подвум соседним выборкам в блоке определения координаты экстремума, 1 з,п,ф-лы, 2 ил.Изобретение относится к автоматике и вычислительной технике и предназначено для поиска экстремумов функ.ции, представленных в виде дискретных выборок, .может быть использованопри разработке специализированной аппаратуры и различных автоматизированных систем управления и является усовершенствованием изобретения поавт,св. У 1290297, 25Цель изобретения - повышение точности определения экстремума функции,На фиг,1 представлена блок-схемаустройства для определения локальныхэкстремумов функции; на фиг,2 - блок 30схема блока определения координатыэкстремума.Устройство для определения локальных экстремумов функции (фиг.1) содержит буферные регистры 1,-14, эле"менты 2 -2 задержки, счетчик 3 управления, коммутаторы 4,1 и 4, регистр5 глобального экстремума, сумматор6 по модулю два, счетчик 7 адреса экстремума, регистр 8 адреса экстрему" 40ма, блок 9 определения координатыэкстремума, элементы И/И-НЕ 10-104,элементы ИЛИ-НЕ 111-114триггеры 12(.12 13, 14 и 14 , элементы И 15115 , формирователь 16.импульсов,Офэлементы ИЛИ 17 и 17, вход 18 запуска, тактовый вход 19, информационный вход 20, вход 21 выбора режима,информационный выход 22 и выход 23фиксации экстремума.Блок 9 определения координаты экст.50ремума (фиг.2) образуют буферныерегистры 21 и 24 , блоки 25 и25 деления, сумматор 26, блок 27 сум"мирования и вычитания, двухразрядный регистр 28, вход 29 разрешениязаписи, первый 30, второй 31 и третий32 информационные входы, а также функциональные входы 33 и 34,Устройство работает следующим образом,Последовательность выборок функциипоступает на информационный вход 20устройства в последовательном кодестаршими разрядами вперед и записывается в первый буферный регистр 1 . Одновременно старший разряд хранящегося в первом буферном регистре 1 числа переписывается во второй буферныйрегистр 1, старший разряд числа,хранящегося во втором буферном регистре 1, - в третий буферный регистр1 , а старший разряд числа, хранящегося в третьем буферном регистре1 З, - в четвертый буферный регистр 14,Каждый поступающий разряд сопровождается сигналом на тактовом входе 19(при этом на входе 18 запуска устрой"ства установлен сигнал "1"), Тот жетактовыйсигнал увеличивает содержимое счетчика 3 управления, емкость кокоторого равна количеству разрядовпоступающих чисел,Устройство имеет два режима работы, В режиме выделения локальных экст"ремумов на входе 21 выбора режимаустановлен сигнал "0", в режиме выделения глобального экстремума на входе 21 выбора режима установлен сигнал"1". Рачало работы устройства определяется поступлением сигнала на вход18 запуска. При этом тактовые сигналы по тактовому входу 19 поступаютчерез элемент И 15 и элемент 2 задержки на входы управления сдвигомбуферных регистров 1,-1 и регистра 5 глобального экстремума.Рассмотрим процессы выделения ло"кального экстремума. В буферных регистрах 1 -1 хранятся четыре смежные по номеру выборки функции. Предположим, что в данный момент временив первом буферном регистре 1 нахо5 10 15 20 25 30 35 45 50 55 5150дится В , выборки функции, во втором буферном регистре 1- Ик выборка функции, в третьем буферном регистре 1 - Б , выборка функции, вчетвертом буферном регистре 14 - Бвыборка функции, Сравнение производится Б+ И, И выборок функции поразрядно каждый такт, начинаясо старшего .разряда. Если все очеред.ные разряды выборок функций на выходах буферных регистров 1 -1 равныединице, то на прямых выходах всехэлементов И/И-НЕ 10-10 устанавливается потенциал "1", а на выходахэлементов ИЛИ-НЕ 11 - 11 з - потенциал"0" и триггеры 12,-12 з не изменяютсвоего состояния, Если очередныеразряды выборок функции все равны нулю, то на объединенных инверсных выходах элементов И/И-НЕ 0,-10 (соединенных в виде МОНТАЖНОГО И) устанавливается потенциал "1", на выходах элементов ИЛИ-НЕ 11-11- потенциал "0", а триггеры 12, - 12 также не изменяют своего состояния, Есличасть разрядов выборок функции на выходах буферных регистров 1, -1 З нулевые, а часть - единичные, то в единичное состояние устанавливаются теиз триггеров 12, разряды в соответствующих буферных регистрах 1 которых равны "0. В дальнейшем сигнал0 с инверсного выхода данного триггера 2 поступает на вход соответ,ствующего элемента И/И-НЕ 10, имитируя поступление минимального числа,Таким образом, в нулевом состояниинаходится триггер (или триггеры) 12соответствующий максимальной (илив случае равенства выборок функциимаксимальным) из выборок функции вбуферных регистрах 1-1 в, При этом вданном режиме работы триггер 12 на 4ходится в единичном состоянии, так )как на выходе регистра 5 глобальногоэкстремума присутствует 0 вследствие обнуления всех регистров передзапуском устройства,Одновременно на входы сумматора 6по модулю два поступают поразрядновыборки функции Б , и Б, . Они жеподаются на вход установки.в единичное состояние триггера 14, а разряды выборки функции Ю , - на вход .,установки в единичное состояние триггера 14, Если все разряды выборокфункции Би Я , равны, т,е, выборки функции равны между собой, то оба 82056 триггера 14, и 14 не изменяют своего состояния, на прямых выходах тригв 4, и 14 присули.выборки функции И , и Нк, не равны, то первые же различные старшие разряды вызывают появление на выходе сумматора 6 по модулю два . Формирователь 16 импульса по этому сигналу формирует импульс, которьвй через элемент И 158 подается на счетные входы триггеров 14и 14, По этому импульсу в единичное состояние по выходу переходит тот триггер 14 , на входе установки в,единичное состояние которого присутствует "1", Таким образом, фиксируется большее из значений выборок функции Ь , и Ы ,. Чтобы избежать повторного срабатывания триггеров 14и 14 за данный цикл сравнения, на элемент И 15 а подаются сигналы с инверсных входов триггеров 14 и 14Через и тактов (и - количество разрядов в выборке) после того, как следующая выборка функции будет полностью записана в первый буферный регистр 1, счетчик 3 управления выдает сигнал переполнения, который увеличивает на единицу содержимое счетчика 7 адреса экстремума и поступает на входы элементов И 15 -154, 15 и 15(о .В дальнейшем возможны следующие варианты, Если триггеры 2 в 12 уста" новлены соответственно в состояние 1 О, т.е, выборки Функции находятся в соотношении И+, (БИ то на выходе элемента И 15 появляется сиг 40 нал, который через элементы ИЛИ 17 и И 151 поступает на выход 23 фиксации экстремума, а также на вход разрешения записи регистра 8 адреса экстремума, в который переписывается значение адреса локального экстремума из счетчика 7 адреса экстремума, Таким образом будет зафиксирован локальный максимум, При этом в первом буферном регистре 1 уже находится Ивыборка функции, во втором буферном регистре 1- Б, выборка Функции, в третьем буферном регистре 1- Мвыборка функции, в четвертом буферном регистре 14 - Б, выборка функции.Одновременно сигнал с выхода элемента И 15 т подается на вход 29 разрешения записи блока 9 определения координаты экстремума, По сигналу переполнения со счетчика 3 управления через элементы И 15и 15 передаются сигналы с прямых выходовтриггеров 14и 14 на адресные входы коммутатора 4 и на функциональный вход 33 блока 9 определения координаты экстремума. Если триггеры 14и 14 установлены соответственно всостояние 10 (т,е. выборки функциинаходятся в соотношении И,Н,),то коммутатор 4 подключает выходыразрядов второго буферного регистра1 (где находится выборка функции Н )с+к соответствующим разрядам первогоинформационного входа 3 блока 9 опреде)тения координаты экстремума,Если триггеры 14 и 14 установленысоответственно в состояние 01 (т,е,выборки функции находятся в соотношении И к ,(И ), то коммутатор 4подключает выходы разрядов четвертого буферного регистра(где находится выборка функции И,) к соответствующим разрядам первого информационного входа 30 блока 9 определения координаты экстремума, На второй информационный вход 31 блока 9определения координаты экстремума посигналу с выхода элемента И 15 ком7мутатор 4 подключает выходы разрядовтретьего буферного регистра 1, Кодна адресных входах коммутатора 4я10 (в режиме определения локальногоэкстремума) . На третий информационный вход 32 блока 9 определения координаты экстремума подается номер выборки И локального экстремума функКции с выхода регистра 8 адреса зкст"ремума. Координата локального экстремума появляется на выходе 22 устройства через время Тпосле появления сигнала на выходе 23 фиксацииэкстремума, причем определение координаты локального экстремума осуществляется,по времени параллельно со .следующим циклом сравнения выборокФУнкции к+, И, Бк 1 так как блокК+1 ф9 определения координаты экстремумаработает автономно.Блок 9 определения координаты экст 50ремума работает следующим образом,По сигналу разрешения записи, поступившему на вход 29 производится за)пись Ик, выборки функции из второго буферного регистра 1 (при коде10 на адресных входах коммутатора 4,)по информационному входу 30 в буферный регистр 24, Если на адресных вхо 508205 8дах коммутатора 41. - код 01 то в бу)ферный регистр 24 хранения переписывается значение И выборки функМ ции иэ четвертого буферного регистра 1 . Тем же сигналом разрешениязаписи по входу 23 производится запись Нвыборки функции из третьегобуферного регистра 1 в буферный регистр 24 (код на адресных входах коммутатора 4- 10), Одновременно по ссигналу с входа 29 разрешения записипроисходит запись кода с выходов триг-,геров 14и )4 через открытые элементы И 15 и 15, в двухразрядный регистр 28, После окончания сигнала повходу 29 буферные регистры 24и 24и .двухразрядный регистр 28 переходят в режим "Хранение - считывание",Выборки функции поступают из соответствующих регистров на соответствующиевходы первого блока 25 1 деления, Навыходе этого блока 25 деления появляется результат: отношение числа изрегистра 24 к числу из регистра 242Этот результат с передается на первыйинформационный вход сумматора 26, навторой информационный вход которогоподается код "1", на выходе сумматораимеем результат сложения (1+ Ы ), Напервый информационный вход блока 25деления подается Ы, на второй информационный вход - результат сложения(1 + К), На выходе этого блока получаем результат от деления- Этот результат 0 подается1+ сГна второй информационный вход блока27 суммирования и вычитания, на первый информационный вход которого подан номер выборки Ж локального мак. -ксимума, В блоке 27 происходит вычисление координаты Х, путем сложенияК+), если М,) Я или вычитанияК-), если Х+,И и результат появляется на выходе 22Процедурасложения или вычитания определяетсякодом, подаваемым на Функциональныйвход блока 27 суммирования и вычитания с выхода двухразрядного регистра28 хранения. Код 1 О соответствуетсложению, код 01 - вычитанию. Возможна ситуация М, =Итогда кодна выходах триггеров 141 и 14 бу"дет 00, Этот код по сигналу с входа29 записывается в двухразрядныйрегистр 28 блока 9 определения координаты экстремума, В соответствиис этим кодом в блок 27 суммированияи вычитания помещается номер выборкиИлокального максимума, который совпадает "с координатой этого максимумаХ =К, Эта координата передается на,ийформационный выход 22Если триггеры 1 2-12 э установлены в состояние 00 (т.е. Я=И)Н )ф + 1 кто значение выборки И , =М к можетбыть локальным максимумом либо точ Окой перегиба в зависимости от дальнейшего поведения функции. Эта ситуация фиксируется элементом И 15 , импульс на выходе которого переводиттриггер 13 в единичное состояние, Если в дальнейшем значение функции убывает (т.е. Б сМ=И), то триггеры 121-12 э устанавливаются в состояние 100, Это состояние фиксируетсяэлементом И 15, при этом триггер 13 20переводится в нулевое состояние, а навыходе 23 формируется сигнал локального максимума, Определение координатылокального максимума происходит вблоке 9 определения координаты экстремума аналогично описанному. Еслипри И, =МЮ , в дальнейшем значение функции возрастает (т,е, ИИ, =Б), то триггеры 1,-12 э устанавливаются в состояние 011, Это соответствует ситуации перегиба функции, при этом сигнал формируется навыходе элемента И 151, что приводитк установке триггера 13 в нулевоесостояние. Сигнал на выходе 23 устройства при этом не формируется,Устройство может также работать врежиме выделения глобального экстремума. При этом на входе 21 выборарежима устанавливается потенциал 40"1", Выделение глобального экстремума осуществляется аналогично выделению локального экстремума, но каждыйвыделенный при этом локальный экстремум сравнивается элементами И/И-НЕ 45104, ИЛИ-НЕ 11 и триггером 124 с те"кущим глобальным экстремумом, хранящемся в регистре 5 глобального экстремума, Сигнал на выходе 23 фиксации .экстремума формируется при этом только г случае, когда И ) Н,где М,значение выборки функции текущегоглобального экстремума, Этим сигналом в регистр 5 глобального экстре"мума через элемент 2 э задержкии открытый элемент И 156 после окончанияцикла сравнения переписывается значеийе Н выборки функции из третьего бубуферного регистра 1 з, Затем с задержкой на время, равное времени перезаписи из третьего буферного регистра 1 в регистр 5 глобального экэстремума, на адресных входах второго коммутатора 42 сформируется код 11. По этому коду коммутатор 4 подключает выходы разрядов регистра 5 глобального экстремума к соответствующим разрядам второго информационного вхо-, да 31 блока 9 определения координаты экстремума.(В дальнейшем определение координаты глобального экстремума произво" дится аналогично определению координаты локального экстремума в блоке 9 определения координаты экстремума, По окончании цикла сравнения с задержкой на время, в течение которого в блок 9 определения координаты экстремума будут записаны значения выборок функции и код с выходов элементов И 159 и 5, , осуществляется обнуление триггеров 12-12, 141 и 14 сигналом через элемент 2 задержки. Йачинается новыйцикл сравнения.Формула из обретения. Устройство для определения локальных экстремумов йункции по авт,св, У 1290297, о т л и ч а ю щ е е с я тем, что, с целью повьппения точности определения экстремума функции, в него введены четвертый буферный регистр, первый и второй коммутаторы, блок определения координаты экстремума, сумматор по модулю два, формирователь импульсов, восьмой, девятый и десятый элементы И, шестой и седьмой триггеры, четвертый элемент задержки, причем выход третьего буферного . регистра соединен с информационным входом четвертого буферного регистра, с входом установки в "1" шестого триггера, с первым входом сумматора по модулю два, выход которого через формирователь импульсов соеди - нен с первым входом восьмого элемен" та И, второй и третий входы которогосоединены соответственно с инверсными выходами шестого и седьмого .триг" геров, счетные входы которых соеди-, нены с выходом восьмого элемента И, а входы установки в "0" - с выходом второго элемента задержки, вход которого соединен с первыми входами девятого и десятого элементов И, вторые входы которых соединены с прямы 1508205 12ми выходами соответственно шестого иседьмого триггеров, вход установкив "1" седьмого триггера соединен свторым входом сумматора по модулюдва и выходом первого буферного регистра, выходы разрядов второго ичетвертого буферных регистров соединены соответственно с первой и второй информационными. группами входовпервого коммутатора, выходы которогоявляются первой информационной группой входов блока определения координаты экстремума, вторая группа информационных входов которого соединена с выходами разрядов регистраадреса экстремума, а третья группаинформационных входов подключена квыходам второго коммутатора, перваяи вторая группы информационных входовкоторого соединены соответственнос выходами разрядов третьего буферного регистра и регистра глобального экстремума, выход первого элемента задержки соединен с входом управления сдвигом четвертого буферного регистра, выход седьмого элемента И соединен с первыми управляющимивходами блока определения координа-.ты экстремума и второго коммутатора,второй управляющий вход которого соединен через четвертый элемент задержки с выходом шестого элемента И, выходы девятого и десятого элементовИ соединены соответственно с вторыми третьим управляющими входами блокаопределения координаты экстремума и,соответственно с первым и вторым управляющими входами первого коммутатора, выход блока определения коорди-. наты экстремума является информационным выходом устройства,2, Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок опреде"ления координаты экстремума содержитпервый и второй буферные регистры,двухразрядный регистр, первый и второй блоки деления, сумматор, блок10 суммирования и вычитания, причемпервая и вторая группы информационных входов блока подключены к информационным входам первого и второгорегистров, входы разрешения записи15 которых соединены с входом разрешения записи двухразрядного регистраи соединены с первым управляющим входом блока, второй и третий управляющие.входы которого соединены с соот 20 ветствующими входами двухразрядного регистра, выходы разрядов которого являются управляющими входами блока суммирования и вычитания, перваяи вторая группы информационных вхо 25 дов которого соединены соответственно с третьей группой информационныхвходов блока и с выходами первогоблока деления, первая и вторая группыинформационных взводов которого соеЗ 0 динены соответственно с выходамисумматора и с выходами первого блокаделения, и с информационными входамипервой группы сумматора, второй информационный вход которого подключенк потенциалу логической единицы, вы"ходы разрядов первого и второго регистров соединены с первой и второйгруппами входов второго блока деления, выходы блока суммирования и вы 40 читания соединены с информационнымивыходами блока,1508205 7 Козл Корр Борисов Редак нык но-издательский комбинат "Патент", г. Узгород, ул. Гагарина,1 роизвод Составитель А,Огар ТехредЛ,ОЛЗаказ 5541/50 Тираа 668 Подписное ВНИИПИ Государственнбго комитета по изобретениям113035, Иосква, Ж, Раушская н ткрытиям при ГКНТ СССР д. 4/5