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

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМУМОВ

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

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

Недостатком этого .устройства является то, что оно позволяет отыскивать из множества значений выборок функций I только локальные экстремукяа, не ;отыск ивая абсолютные экстремумьг - Недостатком этого устройства является гАкже его сложность и невоз.мржиость .работы с оперативными запоминающими устройствами (ОЗУ), где обычно хранятся во многих вычислительных устройствах дискретные выброски исследуемых функций.

Наиболее близким к предлагаемому потехнической сущности является устройство для определения экстремумов, содержащее регистры приема, элементы И, ИЛИ, триггер, элементы задержки, счетчик, элемент сравнения, фор- мирователь одиночных импульсов, дешифратор, причем первая входная шина устройства соединена с первыми входами первого и второго элементов И, выходы которых соединены с входами первого и второго регистров соответственно, выходи которых соединены с входами первого элемента ИЛИ, выходы первого, второгои третьего регистров соединены с информационными входами элемента сравнения, вход управления которого соединен с выходомвторого элемента ИЛИ, первый вход которого соединен с вторым входом устройства, а второй вход второго элемента ИЛИ соединен с выходом формирователя одиночных импульсов, вход которого соединен с выходом дешифратора, информационные входы которого соединены с выходами разрядов счетчика, а вход управления соединен с третьим входом устройства, выходы разрядов счетчика соединены с установочными входами четвертого регистра, первый выход элемента сравнения соединен с первым входом третьего рлемента И, управляющим входом первого регистра и через первый элемент задержки - с вторым входом первого элемента И, с первым входом третьего элемента ИЛИ и с входом установки триггера в нулевое состояние, второй выход элемента сравнения соединен с первьам входом четвертого элемента И и с управляющим входом второго регистра, и через второй элемент задер ки - с вторым входом второго элемента И, с вторым входом третьего элеме та , ИЛИ и с входом уста-новки триггера в единичное состояние, прямой и инверсный выходы которого соединены с вторыми входами четвертого и третьего элементов И соответственно, выход которых соединены с входами четверто го элемента ИЛИ, выход которого соединен с управляющим входом четвертого регистра, выход третьего элемента ИЛИ соединен со счетным входом счет. чика, . . Это. устройство позволяет при рабо те с ОЗУ в различных вычислительных системах определять абсолютные экстр мальные значения чисел и их адрес в ОЗУ 2. Однако это устройство не позволяет находить при однократном прочтении ОЗУ локальные экстремумы и их адреса в ОЗУ. Кроме того, в STOM устройстве при менена однотактная система синхронизации по тактовым импульсам на входной шине, причем для-обеспечения раз несения во времени срабатывания элементов устройства введены лишь два элемента задержки при записи информа ции в один из приемных регистров по тактовым импульсам. Работа остальных элементов устройства не разнесена последовательно во времени, что приводит к тому, что, например, при изменении своего состояния счетчик, вследствие переходных процессов, и подключенный к его выходу дешифратор не исключают выработку ложного сигна ла запуска формирователя одиночных уимпульсов. Этот недостаток влияет на .достоверность поисда экстремумов Целью изобретения является расши рение Функциональных возможностей ус ройства за счет определения локальных экстремумов и их адресов наряду с поиском абсолютных зкстремуйов, а также повышение достоверности их по иска. Поставленная цель достигается тем что в устройстве, содержащем первый, второй, третий и четвертый регистры, элемент И, первую вторую, третью rpy пы элементов И, элемент сравнения, счетчик, дешифратор, причем группа информационных .входов устройства соединена с первыми входами элементов И первой группы, -выходы которых соединены с входами, установки первого регистpa, выходы разрядов которого соединены с первыми информационными входами первого элемента сравнения, .вторая группа входов которого соединена с выходом разрядов второго регистра, выход первого элемента сравнения соединен с первым входом элемента И, а группа выходов счетчика соединена с входами дещифратора, введены второй и третий элементы сравнения, четвертая-седьмая группы элементов И, второй элемент И, пятый и шестой регистры, генератор импульсов, причем выходы разрядов пер.вого регистра соединены с первыми входами элементов И второй группы, выходы которых соединены с входом установки второго регистра, выходы. разрядов которого соединены с вторыми группами информационных входов второго и.третьего элементов сравнения, с первыми входами элементов. И третьей и четвертой групп и с первой группой выходов устройства, первая группа информационных входов второго элемента сравнения соединена с выходами разрядов третьего регистра, входы установки которого соединены с выходами элементов И третьей группы, выход второго элемента сравнения соединен с вторым входом первого элемента И, выход которого соединен с первыми входами элементов И четвертой и седьмой групп и с первым выходом устройства, выходы элементов И четвертой группы соединены с входами установки четвертого регистра, выходы разрядов которого соединены с второй группой выходов устройства и с первыми входами элементтов И пятой группы, выходы Которых соединены с входами установки пятого регистра, выходы разрядов которого соединены с первой группой информационных входов треть.его -элемента сравнения, выход которого соединен с вторыми входами элементов И седьмой группы и с третьими входами элементов счетчика, выходы разрядов которого соединены с третьей группой выходов устройства и с третьими входами элементов И седьмой группы, выходы которых соединены с входами установки шестого регистра, выходы разрядов которого являщся четвертой группой выходов уст™йства, выход дешифратора соединен с первым входом второго элемента И, вцход которого является вторым выходом устройства, управляющий вход устройства соединен с управляющими, входами первого, второго и третьего элементов сравнения, вход генератора импульсов соединен с входом синхронизации устройства, первый выход генератора импульсов соединен i с вторыми входами второго элемента И и элементов И первой группы, второй выход генератора импульсов соединен с третьим входом первого элемента И, третий выход генератора импульсов соединен с вторыми, входами элементов И третьей и пятой групп, четвертый выход генератора импульсов соединен с вторыми входами элементов И второй группы и со счетным входом счетчика.

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

Устройство содержит первую группу элементов И 1, первый регистр 2, первый элемент 3 сравнения, первый элемент И 4, второй элемент 5 сравнения вторую группу элементов И б, второй регистр 7, третью группу элементов И 8, третий регистр 9, четвертую группу элементов И 10, четвертый регистр 11, пятую группу 12 элементов И, пятый регистр 13, третий элемент 14 сравнения, счетчик.15, дешифратор 16, второй элемент И .17, генератор 18 импульсов, седьмую группу элементов И 19, шестой регистр 20, группы информационных входов 21 устройства, группу управляющих входов 22 устройства, управляющий вход 23 устройства, вход 24 синхронизации устройства, первую группу выходов 25 устройства, первый выход 26 устройства, вторую группу выходов 27 устройства, третью группу выходов 28 устройства, второй выход 29 устройства, четвертую группу выходов 30 устройства.

Группа информационных входов устройства 21 Соединена с первыми входами элементов И 1 первбй группы, выходы которых соединены с группой установочных входов первого регистра 2. Выходы разрядов первого регистра 2 соединены с первыми входами элемента 3 сравнения и элементов И 6 второй группы, вторые входы элемента- 3 сравнения соединены с выходами разрядов второго регистра 7. Выход первого элемента 3 сравнения соединен с первым входом первого элемента И 4. Выходы второй группы элементов И 6 соединены с,установочными входами второго регистра 7/ выходы, разрядов которого соединены с вторыми информационными входами второго и третьего элементов 5, 14 сравнения и к первым входам элементов И третьей группы 8, к вторым входам элементов И четвертой группы 10, к первой группе выходов 25 устройства. Первая группа входов второго элемента 5 сравнения соединена С: выходами разрядов третьего регистра 9, а его установочные входы - с

выходами элементов И третьей группы Выход второго элемента 5 сравнения соединен-с входом первого элемента И 4, выход которого соединен с первыми входами элементов И четвертой и седьмой групп и с первым выходом 26 устройства. Выходы злёментов И четвертой группы 10. соединены с входами четвертого регистра. 11, разрядов которого соединены с первыми входами элементов И пятой груп}пы 12 и второй группой выходов 27 ;устройства, а выхода элементов И пятой группы 12 соединены с установочными входами пятого регистра 13, выходы разрядов которого соединены с первой группой входов третьего элемента 14 сравнения, выход которой соединен с третьими входами элементов И четвертой группы 10 и вторыми входами элементов И седьмой группы 1 Группа управляющих входов 22 устройства соединена с установочными входами счетчика 15, выхода разрядов ко- торого соединены-с входами дешифратора 16, с третьими входами элементов И седьмой группы 19 и к третьей группе выходов 28 устройства. Выход дешифратора 16 соединен с первым входом второго элемента И 17, выход которого является вторым выходом устройства. Выходы элементов И седьмой группы 19 соединены с установочньпли входами шестого регистра 20, выходы разрядов которого являются четвертой группой выходов 30 устройства.

Упр;авляющий вход 23 устройства соединен с управлякяцими входами первого, второго и третьего элементов 3, 5 и 14 сравнения.

Вход генератора 18 импульсов соединен с входом 24 синхронизации устройства, а первый выход генератора 18 импульсов соединен с вторыми входами второго элемента И 17 и элементов И первой группы 1. Второй выход генератора 18 импульсов соединен с третьим входом первого элемента И 4, третий выход генератора 18 импульсов - с вторыми входами элементов И третьей 8 и пятой 12 групп. Четвертый выход генератора 18 импульсов соединен с вторыми входами элементов И второй группы 6 и счетным входом счетчика 15..

Назначение элементов устройства следующее.

Для обеспечения поиска значения локальных экстремумов служат группы элементов И 1, 4, 6 и 8, элементы 3 и 5 сравнения, а также регистры 2, 7 и 9, причем, выборка значения локального экстремума с выхода регистра 7 на внешнее устройство производится по синхроимпульсам с выхода элмента И 4 (по выходу 26 устройства).

Для обеспечения поиска значения абсолютного экстремума служат группы элементов И 10 и 12, регистры 11 и 1 а также элемент 14сравнения, причем выборка значения-абсолютного экстремума с выхода регистра 11 (выход 27 устройства) на внешнее устройство происходит по сигналу Конец поиска с выхода элемента И 17 (по выходу 29 устройства). . Счетчик 15, дешифратор 16, элемен И 17 служат для определения адресов локальных экстремумов .и конца поиска локальных и абсолютного экстремумов. Регистр 20 служит для хранения значения адреса абсолютного экстремума, |выборка значения которого внешним устройством происходит по сигналу Конец поиска с выхода элемент та И 17. Дешифратор 16 вырабатывает сигнал разрешения по первому входу. элемента И 17 лишь при наличии нулевого состояния счетчика 15. Вход 24 синхронизации устройства служит для ввода синхронизирующих импульсов с внешнего устройства, по которым генератор 18 импульсов вырабатывает последовательность непере,крывающихся тактирующих импульсов (ТИ): ТИ 1 - на первом выходе, ТИ 2 на втором, ТИ 3 - на третьем, ТИ 4 на четвертом. Группа информационных входов 21 служит для ввода чисел из ОЗУ, группа входов 22 устройства предназначена для занесения в счетчик 15 из вне него устройства числа- (п+1) где п количество чисел в массиве. Управляющий вход 23 устройства сл жит для задания вида экстремумов максимумов или минимумов. Выход- 25 устройства служит для вы вода значения локальных экстремумов, сопровождаемых синхроимпульсами по выходу 26 устройства. На выходе 29 устройства по окончании работы формируется синхронизирующий импульс для выборки значения адреса абсолютного экстремума на выходе 30 устройства и его значения на выходе 27 устройства. Устройство работает следующим об разом. Перед началом работы регистры 2, j7,9, 11, 13, 20 и счетчик 15 находят ся в нулевом состоянии. По входу 22 устройства в счетчик 15 заносится число (п+1), с входа 23 устройства на управляющие входы элементов 3, 5 и 14 сравнения поступает сигнал управления их работой, причем при наличии на входе 23 единичного сигнала элементы 3, 5 и 14 сравнения формируют на своих выходах единичные сигналы при поступлении на вторые инфор мационные входы элементов чисел боль ших, чем на их первых информационных входах, что обуславливает режим поиска локальных и абсолютного максимумов, и наоборот, если на входе 23 устройства присутствует нулевой сигнал, то элементы 3, 5 и 14 сравнение формируют на своих выходах единичные сигналы при наличии на их вторых информационных входах чисел меньших, чем на их первых информационных входах,- что обуславливает режим локальных и абсолютного минимумов. При определении локальных и абсолютного максимумов устройство работает следующим образом. Перед началом работы в регистры 7 и 13 заносится нулевой код, В счетчике 15 записано число (п+1). По вхо|ДУ 21 устройства на первый вход группы элементов И 1 из ОЗУ поступает код ctyj первого из массива сравниваемых чисел, причем выборка значений сравниваемых чисел из ОЗУ происходит со старших номеров (адресов) массива и далее к его началу. С внешнего устройства на вход 24 синхронизации устройства поступает , первый синхроимпульс, по которому запускается работа внутреннего генератора 18 импульсов. Y. . Поступление по входу 24 устройства синхроимпульса означает, что внешнее устройство выставило код d очередного из анализируемых чисел и до прихода очередного синхроимпульса устройство должно произвести анализ кода числа, поступившего из ОЗУ по первой входной шине 21 устройства. В первом такте ТИ 1 через группу элементов И 1 код числа (3 записывается в регистр 2, при этом на первом . входе элемента 3 сравнения появляется в этом же такте код первого из сравниваемых чисел. На выходе элементов 3 и 5 сравнения - сигналы логического нуля, число в регистре 7 не превышает чисел, записанных в регист- . pax 2 и 9 соответственно, поскольку в начале работы эти регистры обнулены, поэтому на первом и-.втором входах и на выходе элемента И 4 нулевые сигналы. Во втором.такте ТИ 2 происходит стробирование элемента И 4 по третьему входу. На выходе элемента И 4 нулевой выходной сигнал. В третьем такте ТИ 3 происходит перезапись кода числа, находящегося в регистре 7, в регистр 9 путем стробирования группы элементов И 8 по его второму входу. Так как регистр 7 был ранее обнулен, то в регистр 9 записывается нулевой код. В этом же такте происходит перезапись кода числа, записанного в регистре 11, в регистр 13 через группу элементов И 12. Так как регистр 11 в начале работы был обнулен, то в регистре 13 записывается нулевой код. В четвертом такте ТИ 4 происходит перезапись кода первого числа ,, за писанного.-в регистре 2, в регистр 7 -через группу элементов И б. В том 5ке такте из содержимого счетчика 15 вычитается единица и на его выходе устанавливается код п - адрес относительно начала массива знака, находящегося в регистре 7 Далее на первую входную шину 21 устройства поступает код числа d. / второго из массива сравниваемых чисел, а на вход. 24 устройства поступает второй синхроимпульс, запускающий повторно генератор 18 импульсов. В первом такте ТИ 1 код второго числа (Зу1 записывается в регистр 2, Если код второго числа не превышает код первого числа: dyi dy, , то на первом и втором входах элемента И 4 присутствует единичные сигналы, т.е. с.облюдено условие, локального максиму ..-d, . ма: Во втором такте происходит строби рование состояния выходов элементов 3 и 5 сравнения. Тактовый импульс ТИ 2 поступает на третий вход элемен та, И 4 и с его выхода поступает на .первые- входы группы элементов И 10. По сигналу с выхода элемента И 4 .про исходит перезапись кода первого числа из регистра 7 в регистр 11 через группу элементов И 10. По этому же сигналу с выхода элеМента И 4 через группу элементов И 19 происходит перезапись состояния счетчика 15 в регистр 20, так как на вторых входах группы элементов И 19 единичный сигнсШ, а на их первые вхо ды поступает тактовый импульс ТИ 2. Сигнал о том, что в регистре 7 находится значение локального максимума, с выхода элемента И 4 поступает на выход 26 устройства. В третьем такте по импульсу ТИ 3 происходит перезапись первого числа из регистра 7 через группу элементов И 8 в регистр 9 а также перезапись содержимого регист ра 11 в регистр 13 чарез группу элементов И 12. В четвертом такте по им пульсу ТИ 4 происходит перезапись ко да второго числа dyi.1 из регистра 2 через группу элементов И б регистр 7 а также содержимое счетчика 15 умень шается на единицу и на его выходе устанавливается код (п-1) - адрес относительно начала массива числа, на ходящегося в регистре 7. Далее на вход 21 устройства поступает код третьего числа б ц-1 из массива сравниваемых чис.ел, а на вход 24 синхронизации поступает синхроимпульс. Если третье число не превышает второго числа 6у(--2.(3ц.;, , то после его записи в первом такте через группу элементов И 1,в регистр 2 на выходе элемента 3 сравнения присутствует единичный сигнал, однако на выходе элемента 5 сравнения нулевой сигнал, так как код первого числа .превышает код второго числа tdn,,3y. При стррбировании состояния выходов элементов 3 и 5 сравнения во. втором такте на выходе элемента И 4 нулевой сигнал, что означает, что не выполнилось условие локального максимума: .a,a.,,, где - коды сравниваемых чисел. Второе число на является локальным экстремумом и поэтому регистр 11 йе изменяет своего содержимогово втором такте, поскольку на первых входах группы элементов И 10 - сигнал логического нуля. В четвертом такте происходит перезапись третьего числа Ий--2. регистр 7 и уменьшение содержимого счетчика 15 на единицу. Таким образом, в регистре 11 запоминаютсЯ числа, представляющие локаль|ные максимумы при превышении их значений предадущих локальных максимумов, записанных в регистре 13. В конце поиска в регистре 11 записывается максимальный из всех локальных максимумов, т.е. абсолютное максимальное значение. 1 -. Аналогично происходит дальнейшая работа устройства. Таким образом, при поступлениииз ОЗУ на вход 21 устройства числа (3 в регистре 7 находится Число , число d(2 - в регистре 9. После поступления-п-го синхроимпульса в первом такте число записывается в регистр 2. ЕСЛИ код числа удовлетворяет условию: dv, то на выходах элементов 3 и 5 сравнения появляются единичные сигналы. Во втором такте ТИ 2 происходит стробирование элемента И 4 по третьему входу, и с его выхода сигнал поступает на входы групп элементов И 10 и 19 и на выход 26 устройства. Если da больше максимального иЗ предыдущих локальных максимумов, хранимого в регистре 13, То на выходе-элемента 14 сравнения появляется единичный сигнал, и число dl перезаписывается в регистр 11. В третьем такте происходит перезапись числа do. в регистр 9 из регистра 7, а содержимого регистра 11 - в регистр 13. В четвертом такте происходит перезапись числа из регистра 2 в регистр 7. Перед поступлением на вход 24 синхронизации уетройства {п+1)-го синхроимпульса в счетчике 15 записана единица, а на входе 21 устройства устанавливается нулевой код. Таким образом, условие локального максиму-, ма не соблюдено: 0 и на выходе элемента И 4 отсутствует единичный сигнал и регистры 11, 13 и 20 не изменяют своего состояния. В четвертом такте ТИ 4 происходит перезапись содержимого регистра 2 (в котором находятся нули) в регистр 7 и уменьшение содержимого счетчика 15, т.е. на выходе счетчика 15 нулевой код. При этом на выходе дешифратора 16 появляется единичный сигнал. По приходу следующего синхроимпульса по входу 24 устройства генератор 18 импульсов в такте ТИ 1 стробирует элемент И 17, в результате чего на выходе 29 устройства появляется сигнал об окончании поиска. Аналогичным образом осуществляется поиск локальных и абсолютного минимумов. В этом случае на вход 23 устройства поступает нулевой сигнал, В начале поиска в этом случае во все регистры устройства заносится максимальное число, а затем происходит поиск минимумов по ранее описанному алгоритму. Таким образом, при однократном прочтении значений кодов исследуемых чисел из ОЗУ устройство эа время -4(.Т+лТ, . ргде ДТ - длительность тактового импульса, производит поиск локальных и абсолютного экстремумов. По сравнению с известным,предлага емое устройство при однократном прочтении значений выборок исследуемых функций позволяет определить локальные и абсолютные экстремумы одновременно, что сокращает время поиска. Указанное качество устройства рас ширяет его функциональные возможности и расширяет область его применения. . . Введение жесткой синхронизации ра боты всех элементов устройства по сравнению с известным исключает ложное срабатывание его элементов при переходных процессах, что приводит к повышению достоверности поиска экстремумов. Формула изобретения Устройство для определения экстре йумов, содержащее первый, второй, третий и четвертый .регистры, элемент И, первую, вторую, третью группы эле ментов И, элемент сравнения, счетчик дешифратор, причем группа информационных входов устройства соединена с первыми входами элементов И первой группы, выходы которых соединены с входами установки первого регистра, выходы разрядов которого соединены с первыми информационными входами пе вого элемента сравнения, вторая груп па входов которого соединена с выходом разрядов второго регистра, выход первого элемента сравнения соединен с первым входом элемента И, а группа выходов счетчика соединена с входами дешифратора, отличающееся тем, что, с целью расширения функциональных возможностей за счет определения значений локальных экстремумов, в него введены второй и третий элементы сравнения, четвертая - седьмая группы элементов И, второй элемент И, пятый и шестой регистры, генератор импульсов, причем выходы разрядов первого регистра соединены с первыми входами элементов И второй группы, выходы которых соединены с входом установки второго регистра, выходы разрядов которого соединены с вторыми группами информационных входов второго и третьего элементов сравнения, с первыми входами элементов И третьей и четвертой групп и с первой группой выходов устройства, первая группа информационных входов второго элемента сравнения соединена-с выходгми разрядов третьего регистра, входы устано вки которого соединены с выходами элементов И третьей группы, выход второго элемента сра:внения соединен с вторым входом первого элемента И, выход, которого соединен с первыми входами (элементов И четвертой и седьмой групп и с первым выходом устройства, выходы элементов И четвертой группы соединены с входами установки четвертого регистра, выходы разрядов которого соединены с второй группой -выходов устройства и с первыми входами элементов И группы, выходы которых соединены с входами установки пятого регистра, выходы разрядов которого соединены с первой группой информационных входов третьего элемента сравнения, выход- которого соединен с вторыми входами элементов И седьмой группы и с третьими входами элементов И четвертой группы, группа управляющих входов устройства соединена с группой установочных входов счетчика, вызсбды разрядов которого соединены с третьей группой выходов устройства и с третьими входами элементов И седьмой группы,выходы которых соединены с входами установки шестого регистра, ВЫХО.ДЫ разрядов которого являются четвертой группой выходов устройства,выход дешифратора соединен с первым входом второго элемента И,выход которого является вторым выходом устройства, управляющий вход устройства соединен с управляющими входами первого, второго и третьего элементов сравнен ния,вход генератора импульсов соединен с входом синхронизации устройства, первый выход генератора импульсов соединен с-вторыми входами- второго элемента И и элементов И первой группы, второй выходГенератора импульсов соединен/с третьим входом первого элемента И,третий выход генератора импульсов соединен- с вторыми входами элементов И третьей и иятой групп,четвертый йыход генератора импульсов соединен с вторыми входами элементов И вто- 5 рой группы и со счетным, входом счетчика. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР 696442, кл. .G Об Р 7/06, 1977. 2. Авторское свидетельство СССР 746504, кл. G 06 Р 7/04, 1978 (прототип).