Устройство для определения локальных экстремумов функции Советский патент 1989 года по МПК G06F7/06 

(/

СП

о

00 N9 О СП

N)

31508205

элементы ИЛИ-НЕ П,11, триггеры ., 13, 14,-14, элементы И 15д-15,р, формирователь импульсов 16, элементы ИЛИ 17,17. Последователь- ность выборок функции поступает на информационньш вход устройства в последовательном коде. Устройство имеет два режима работы: режим вьзд еле- ния локального экстремума и режим Ю

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

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

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

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

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

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

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

6по модулю два, счетчик 7 адреса экстремума, регистр 8 адреса экстрему- ма, блок 9 определения координаты экстремума, элементы. И/И-НЕ , элементы ИЛИ-НЕ 1 Ц-11 , триггеры 1.2- 12, 13, 14 и 14,j, элементы И 15,- 15 ., формирователь 16 импульсов, элементы ИЛИ 17 и 17, вход 18 запуска, тактовьй вход 19, информационный вход 20, вход 21 выбора режима, информационный выход 22 и выход 23 фиксации экстремума.

Блок 9 определения координаты экст ремума (фиг,2) образуют буферные регистры 21 и 24, блоки 25 и 25„ деления, сумматор 26, блок 27 сум мирования и вычитания, двухразряд- ный регистр 2В, вход 29 разрешения записи, первый 30, второй 31 и третий 32 информационные входы, а также функциональные входы 33 и 34.

п25

ЗО

,с

Q .,

0

Устройство работает следующим образом.

Последовательность выборок функции поступает на информационный вход 20 устройства в последовательном коде старшими разрядами вперед и записывается в первый буферный регистр 1 . Одновременно старший -разряд хранящегося в первом буфернъм регистре 1. числа переписывается во второй буферньй регистр Ig, старший разряд числа, хранящегося во втором буферном регистре 1, - в третий буферный регистр Ц, а старший раз$)яд числа, хранящегося в третьем буферном регистре Ij, - в четвертьй буферный регистр 1, Каждый поступающий разряд сопровождается сигналом на тактовом входе 19 (при этом на входе 18 запуска устройства установлен сигнал 1). Тот же тактовый сигнал увеличивает содержимое счетчика 3 управления, емкость ко- которого равна количеству разрядов поступающих чисел.

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

Рассмотрим процессы выделения локального экстремума. В буферных регистрах lj(-l(). хранятся четыре смеж.- ные по номеру выборки функции. Предположим, что в данный момент времени в первом буферном регистре Ц находится N 1 выборки функции, во втором буферном регистре 1 - N, выборка функции, в третьем буферном регистре 1,, - N., выборка функции, в четвертом буферном регистре l (. выборка функции. Сравнение производится N,, N(, N, выборок функции поразрядно каждьй такт, начиная

со старшего .разряда. Если все очеред- IQ формирует импульс, который через элемент И 15g подается на счетные входы триггеров 14 и 14. По этому импульсу в единичное состояние по выходу переходит тот триггер 14:, на входе 15 установки в«единичное состояние которого присутствует 1. Таким образом, фиксируется большее из значений выборок функции N и N ., . Чтобы избежать повторного срабатьшания тригге. ные разряды выборок функций на выходах буферных регистров з единице, то на прямых выходах всех элементов И/И-НЕ устанавливается потенциал 1, а на выходах элементов ЙЛИ-НЕ 11,-1Ц - потенциал О и триггеры 12,-125 не изменяют своего состояния. Если очередные разряды выборок функции все равны нулю, то на объединенных инверсных выходах элементов И/И-НЕ 10,-10 (соединенных в виде МОНТАЖНОГО И) устанавливается потенциал 1, на выходах элементов ИПИ-НЕ ll,-ll:j - потенциал О, а триггеры 12,-12j также не изменяют своего состояния. Если. часть разрядов выборок функции на выходах буферных регистров .1. вые, а часть - единичные, то в единичное состояние устанавливаются те из триггеров 12;, разряды в соответствующих буферных регистрах которых равны о. В дальнейшем сигнал О с инверсного выхода данного триггера 12: поступает на вход соответствующего элемента И/И-НЕ 10;, имитируя поступление минимального числа. Таким образом, в нулевом состоянии находится триггер (или триггеры) 2;, соответствующий максимальной (или в случае равенства выборок функции максимальным) из выборок функции в буферных регистрах 1,-Ц« При этом в данном режиме работы триггер 12. находится в единичном состоянии, так-f как на выходе регистра 5 глобального экстремума присутствует О вследствие обнуления всех регистров перед запуском устройства.

Одновременно на входы сумматора 6 по модулю два поступают поразрядно выбррки функции N,| , Они же подаются на вход установки, в единич- кое состояние триггера 14, а разряды выборки функции N j, - на вход ; установки в единичное состояние триггера Hj. Если все разряды выборок функции N и N равны, Теб, выбор20 ров 14, и 14 2 за данный цикл сравнена элемент И 15 подаются сигна- инверсных входов триггеров 14

2

ния, лы с и 14

Через п тактов (п - количество

25 разрядов в выборке) после того, как следующая выборка функции будет полностью записана в первый буферный регистр 1 , счетчик 3 управления выдает сигнал переполнения, который

30 увеличивает на единицу содержимое

счетчика 7 адреса экстремума и поступает на входы элементов И ,

15, и 15,0

Б дальнейшем возможны следующие

25 варианты. Если триггеры установлены соответственно в состояние 10, т.е. выборки функции находятся в соотношении N., 1N N , то на выходе элемента И 15.- появляется сиг40 нал, который через элементы ИЛИ 17 и И 15-3 поступает на выход 23 фиксации экстремума, а также на вход разрешения записи регистра 8 адреса экстремума, в

45 который переписывается значение адреса локального экстремума из счетчика 7 адреса экстремума. Таким образом будет зафиксирован локальный максимум. При этом в первом буферном

50 регистре 1, уже находится N jj,. выборка функции, во втором буферном регистре 1 2. выборка функции, в третьем буферном регистре 1 , N j, выборка функции, в четвертом буферном регистK-t-1

ни функции равны между собой, то оба

55 ре 1 4- к. выборка функции.

Одновременно сигнал с выхода элемента И 15-7 подается на вход 29 разрешения записи блока 9 определения координаты экстремума. По сигналу пётриггера 14, и 14- не иэменягот своего состояния, на прямых выходах триггеров 14 и 14 присутствует. О. Если выборки функции N и N,.., не равны, то первые же различные старшие ., разряды вызывают появление на выходе сумматора 6 по модулю два 1. Формирователь 16 импульса по этому сигналу

20 ров 14, и 14 2 за данный цикл сравнена элемент И 15 подаются сигна- инверсных входов триггеров 14

2

ния, лы с и 14

Через п тактов (п - количество

5 разрядов в выборке) после того, как следующая выборка функции будет полностью записана в первый буферный регистр 1 , счетчик 3 управления выдает сигнал переполнения, который

0 увеличивает на единицу содержимое

счетчика 7 адреса экстремума и поступает на входы элементов И ,

15, и 15,0

Б дальнейшем возможны следующие

5 варианты. Если триггеры установлены соответственно в состояние 10, т.е. выборки функции находятся в соотношении N., 1N N , то на выходе элемента И 15.- появляется сиг0 нал, который через элементы ИЛИ 17 и И 15-3 поступает на выход 23 фиксации экстремума, а также на вход разрешения записи регистра 8 адреса экстремума, в

5 который переписывается значение адреса локального экстремума из счетчика 7 адреса экстремума. Таким образом будет зафиксирован локальный максимум. При этом в первом буферном

0 регистре 1, уже находится N jj,. выборка функции, во втором буферном регистре 1 2. выборка функции, в третьем буферном регистре 1 , N j, выборка функции, в четвертом буферном регист55 ре 1 4- к. выборка функции.

Одновременно сигнал с выхода элемента И 15-7 подается на вход 29 разрешения записи блока 9 определения координаты экстремума. По сигналу пё 1508205

-реполнения со счетчика 3 управления через элементы И 15, и 15

передаются сигналы с прямых выходов триггеров 4, и 14 на адресные входы коммутатора 4, и на функциональный вход 33 блока 9 определения координаты экстремума. Если триггеры 4 и 14, установлены соответственно в

дах коммутатора 4.,- код 01 то в буферный 24. хранения перепи- сьгаается значение N ,, выборки функции из четвертого буферного регистра Ц, Тем же сигналом разрешения записи по входу 23 производится запись Nf/выборки функции из третьего буферного регистра 1, в буферньй ресостояние 10 (т.е. выборки функции ю гистр 24 (код на адресных входах ком- находятся в соотношении N,N ),

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

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

к соответствующим разрядам первого 5

информационного входа 30 блока 9 оп- редел ения координаты -экстремума. Если триггеры 14 и Hg установлены соответственно в состояние 01 (т.е. выборки функции находятся в соотно- 20 шении ), то коммутатор 4 подключает выходы разрядов четвертого буферного регистра Ц (где находится выборка функции ) к соответствующим разрядам первого информаци- 25 онного входа 30 блока 9 определения координаты экстремума. На второй информационный вход 31 блока 9 - определения координаты экстремума по сигналу с выхода элемента И 15- ком- ЗО мутатор 42 подключает выходы разрядов третьего буферного регистра 1-. Код на адресных входах коммутатора 4 - 10 (в режиме определения локального экстремума). На третий информацион- ньм вход 32 блока 9 определения коор динаты экстремума подается номер выборки Nj локального экстремума функции с выхода регистра 8 -адреса экстремума. Координата локального экстремума появляется на выходе 22 устройства через время Тд„р после появления сигнала на выходе 23 фиксации экстремума, причем определение координаты локального экстремума осущест- .с вляется по времени параллельно со v следзтощим циклом сравнения выборок

функции . NK-H к) блок 9 определения координаты экстремума работает автономно.

Блок 9 определения координаты экстремума работает следующим образом. По сигналу разрешения записи, поступившему на вход 29. производится за- ,

35

40

Г.50

мутатора 10)р Одновременно по с сигналу с входа 29 разрешения записи происходит запись кода с выходов триг-. геров 14 и J4 через открытые элементы И 15 и 15 ,р в двухразрядный регистр 28. После окончания сигнала по входу 29 буферные регистры 24 и 24- и .двухразрядный регистр 28 переходят в режим Хранение - считьшание. Выборки функции поступают из соответствующих регистров на соответствующие входы первого блока 25, деления. На выходе этого блока 25 деления появляется результат: отношение числа из регистра 24 к числу из регистра 24 , Этот результат d передается на первый информационный вход сумматора 26, на второй информационный вход которого подается код 1, на выходе сумматора имеем результат сложения (l+cf). На первый информационный вход блока 25 деления подается с , на второй информационный вход - результат сложения (1 + оС). На выходе этого блока получаем результат от деления П

об

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

на второй информационный вход блока . 27 суммирования и вычитания, на первый информационный вход которого подан номер выборки N локального максимума, В блоке 27 происходит вычисление координаты X,

путем сложения К+р, если , , или вычитания К-р, если N, ;N, , и результат появляется на выходе 22, Процедура сложения или вычитания определяется кодом, подаваемым на функциональный вход блока 27 суммирования и вычитания с выхода двухразрядного регистра 28 хранения. Код 10 соответствует сложению, код 01 - вычитанию. Возможна ситуация N,N.,, тогдэ код

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

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

8

S-дах коммутатора 4.,- код 01 то в буферный 24. хранения перепи- сьгаается значение N ,, выборки функции из четвертого буферного регистра Ц, Тем же сигналом разрешения записи по входу 23 производится запись Nf/выборки функции из третьего буферного регистра 1, в буферньй регистр 24 (код на адресных входах ко

ю гистр 24 (код на адресных входах ком-

5

20 25 ЗО .с

,

35

40

50

55

мутатора 10)р Одновременно по с сигналу с входа 29 разрешения записи происходит запись кода с выходов триг-. геров 14 и J4 через открытые элементы И 15 и 15 ,р в двухразрядный регистр 28. После окончания сигнала по входу 29 буферные регистры 24 и 24- и .двухразрядный регистр 28 переходят в режим Хранение - считьшание. Выборки функции поступают из соответствующих регистров на соответствующие входы первого блока 25, деления. На выходе этого блока 25 деления появляется результат: отношение числа из регистра 24 к числу из регистра 24 , Этот результат d передается на первый информационный вход сумматора 26, на второй информационный вход которого подается код 1, на выходе сумматора имеем результат сложения (l+cf). На первый информационный вход блока 25 деления подается с , на второй информационный вход - результат сложения (1 + оС). На выходе этого блока получаем результат от деления П

об

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

на второй информационный вход блока . 27 суммирования и вычитания, на первый информационный вход которого подан номер выборки N локального максимума, В блоке 27 происходит вычисление координаты X,

путем сложения К+р, если , , или вычитания К-р, если N, ;N, , и результат появляется на выходе 22, Процедура сложения или вычитания определяется кодом, подаваемым на функциональный вход блока 27 суммирования и вычитания с выхода двухразрядного регистра 28 хранения. Код 10 соответствует сложению, код 01 - вычитанию. Возможна ситуация N,N.,, тогдэ код

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

и вычитания помещается номер выборки N локального максимума, который совпадает с координатой этого максимума , Эта координата передается на информационный выход 22.

Если триггеры 12,-12 установлены в состояние 001 (т.е. N, ) то значение выборки может быть локальным максимумом либо точ- кой- перегиба в зависимости от дальнейшего поведения функции. Эта ситуация фиксируется элементом И 15, импульс на выходе которого переводит триггер 13 в единичное состоянй е. Ее- ли в дальнейшем значение функции убывает (т.е. ,N), то триггеры 2,-12з устанавливаются в состояние 100, Это состояние фиксируется -- элементом И 15, при этом триггер 13 переводится в нулевое состояние, а на выходе 23 формируется сигнал локального максимума. Определение координаты локального максимума происходит в блоке 9 определения координаты экст- ремума аналогично описанному. Если при N, ic K-i дальнейшем значение функции возрастает (т.е. N, ), то триггеры 12,-12з устанавливаются в состояние 011. Это со- ответствует ситуации перегиба функции, при этом сигнал формируется на t выходе элемента И 15, что приводит к установке триггера 13 в нулевое состояние. Сигнал на выходе 23 устройства при этом не формируется.

Устройство может также работать в режиме вьщеления глобального экстремума. При этом на входе 21 выбора режима устанавливается потенциал 1. Вьщеление глобального экстремума осуществляется аналогично вьщеле- нию локального экстремума, но каждый вьщеленный при этом локальный экстремум сравнивается элементами И/И-НЕ 10, ШТИ-НЕ 11 и триггером 12 с текущим глобальным экстремумом, хранящемся в регистре 5 глобального экстремума. Сигнал на выходе 23 фиксации экстремума формируется при этом толь- ко Е случае, когда К,Нрд,где значение вйборки функции текущего глобального экстремума. Этим сигналом в регистр 5 глобального экстремума через элемент 2 задержки и от- крытый элемент И 15g после окончания цикла сравнения переписывается значение N. выборки функции из третьего бу буферного регистра Ij, Затем с за

-

5 0 5 0

0

5

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

экстремума, 1 , -( В дальнейшем определение координаты,, глобального экстремума производится аналогично определению координаты локального экстремума в блоке 9 определения координаты экстремума. По окончании цикла сравнения с задержкой на время, в течение которого в блок 9 определения координаты экстремума будут записаны значения выборок функции и код с выходов элементов И 15о и . , осуществляется обнуление триггеров ., 14 и 14 сигналом через элемент 2 задержки. Начинается новый цикл сравнения.

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

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

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

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

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

дзигг