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

i (Л

Изобретение относится к автоматике и вычислительной технике, может быть использовано для обработки изображений и является усовершенствованием устройства по а.с. СССР N 1401451. ЦЕЛЬ ИЗОБРЕТЕНИЯ - ПОВЫШЕНИЕ ТОЧНОСТИ ОПРЕДЕЛЕНИЯ КОЛИЧЕСТВА ЛОКАЛЬНЫХ ЭКСТРЕМУМОВ. УСТРОЙСТВО СОДЕРЖИТ БЛОК 1 БУФЕРНЫХ РЕГИСТРОВ, СОСТОЯЩИЙ ИЗ П РЕГИСТРОВ 2, (П-1) СХЕМ 3 СРАВНЕНИЯ, (К-1) ГРУПП ПО ДВА ЭЛЕМЕНТА ИЛИ 4, К ШИФРАТОРОВ 5 И БЛОК 6 СУММАТОРОВ. ШИФРАТОРЫ 5 РЕАЛИЗОВАНЫ НА СХЕМАХ ПЗУ, в которых определенной кодовой комбинации, поступающей на вход ПЗУ, соответствует определенная кодовая комбинация на выходе, определяющая количество экстремумов на отдельных отрезках выборки, при этом на дополнительных выходах шифратора появляются кодовые комбинации знаков, характеризующие наличие или отсутствие в анализируемых кодах знаков ограничения справа знаками "больше" или "меньше" значений ординат в пределах отрезка. Поступление знаков "больше" или "меньше" об ограничении справа на следующий шифратор позволяет выявить все нестрогие экстремумы в выборке. Уточненные кодовые комбинации о количестве экстремумов с выходов шифраторов поступают на блок 6 сумматора, где производится общее суммирование количества локальных экстремумов в выборке. 2 ил. 1 табл.

О

со

00

ГЧ)

3150

но содержит блок 1 Gyiticpubix регистров, состоящий из п регистров 2.. () схем 3 сравнения, (К-1) групп по два элемента HJDI 4, К шифраторов 5 и блок 6 сумматоров. Шифраторы 5 реализованы на схемах ПЗУ, в которых определенной кодовой ком -инации, поступающей на вход ПЗУ, соответствует определенная кодовая комбинация на выходе, определяющая количество экстремумов на отдельных отрезках выборки, при этом на дополнительных выходах шифратора появляются кодовые комбинации знаков, характеризуюнще

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

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

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

В таблице приведена зашивка выходных кодов шифратора от входных на примере восьмивходового игифрато- ра, выполненного на микросхеме К 556 РТ 4.

Функциональная схема устройства (фиг. 1) включает блок 1 буферных регистров, состоящий из п регистров 2, (п-1) схем 3 сравнения, (k-1) групп по два элемента HJUi 4, k шифраторов 5, блок 6 сумматоров.

Устройство реализовано на следую щих микросхемах: регистры 2 - К555ТМ9, схемы 3 сравнения К555СП1, .элементы И1Й 4 К5551Ш1, шифраторы 5 К556РТ4, сумматоры 6 К555Ш6.

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

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

i

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

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

происходит сравнение соседних значений ординат выборки. Если (i-l)-e значение ординаты меньше i-ro значения ординаты, то уровень 1 появ- ляется на первом выходе схемы 3

сравнения, если больше - то на втором. В случае равенства двух соседних значений на обоих выходах схемы 3 сравнения будет присутствовать

0. уровень О. Результаты сравнения с выходов всех (п-1) схем 3 сравнения поступают на соответствующие входы k шифраторов 5. В результате подключения очередной группы, сос -

- тоящеи из (.-Г) схем 3 сравнения, к

очередному шифратору вся выборка значений ординат разбивается на отдельные отрезки. В каждом из отрез0 ков количество анализируемых значений ординат определяется количеством входов шифратора 5, равное числу га, гДе m . 4 - число четное, а количество таких отрезков - количеством

5 шифраторов, равное k. Причем так как вькоды первых схем 3 сравнения каждой р-й группы подключены через .. вторые входы соответствующих групп элементов ИЛИ 4 к первым входам р-го шифратора 5, то обеспечивается сравнение значений ординат в окрестностях гран иц отрезков выборки. А для слу.чаев, когда два или несколько значений ординат, следующих одна

е за другой, равны и попадают на границы отрезков или все значения ординат какого-либо отрезка или ряда отрезков выборки равны, то на двух дополнительных выходах шифратора 5,

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

Шифраторы 5 реализованы на схема ПЗУ, на каждые два очередных входа которых с выхрдов схем 3 сравнения приходят двухразрядные кодовые комбинации, характеризующие один из знаков больше, меньше, равно и соответствующие: 01 - знаку больше, 10 - знаку меньше, 00 - знаку равно.

Таким образом, на га входов шифра m

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

Для общего случая количество размещений с повторениями двоичяых кодовых комбинаций знаков бо,, меньше, равно на m входах шифратора 5 определяется по формуле N

где число знаков

С 3, J количество размещений знаков.

В качестве примера показана таблица зашивки для восьмивходового шифратора, в котором число всевозможных размещений с повторениями ко( довых комбинаций знакоё N 3 i

3 81. Каждой 81 комбинации знаков соответствует определенная информация о количестве локальных экстремумов в отрезках выборки и. информация о знаке больше или меньше в случаях наличия неограниченного в пределах отрезка выборки нестрогого локального экстремума.

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

Для выборок, представленных на фиг. 2, количество отрезков, на которые разбивается вся выборка, определяется количеством шифраторов. Для выборки, представленной 14-ю значениями ординат и при восьмивходовых шифраторах, количество шифраторов равно:

k

2(14 - 2) 8-2

О

0

5

0

Для первого отрезка (О - 4) выборки (фиг. 2 ) количество локальных экст- реьгумов, определяемое в соответст-. ВИИ порядковым номером таблицы равно 2 - код суммы 10. Для второго отрезка (3-7) в соответствии с 54 порядковым номером таблицы количество экстр мумов равно 1 - код суммы 01. Для третьего отрезка (6- 10) в соответствии с 41 порядковым номером таблицы количество экстре гу мов равно 2 - код суммы 10. Для вертого отрезка (9-13) в соответст-, ВИИ с 66 порядковым номером таблиидл количество экстремумов равно 2 - коД суммы 10. Ввиду того, что значение е ординаты а равно а не ограничено справа от значения ординаты а зна-. ками больше юти меньше в пределах первого отрезка (0-4), то неизвестно, является ли значение орди-.

наты aj экстремумом, поэтому код знака между значениями ординат меньше - 10 об ограничении слева с дополнительных выходов шифратора, анализирующего знаки между значениями ординат первого отрезка (0-4), поступает на первые входы следую- щего шифратора, анализирующего знаки между значениями ординат второго Q отрезка (3-7). Код знака меньше 10 заменяет код знака равно - 00 между значениями а, а4 во втором шифраторе, а так как в анализируемом ртором отрезке (3 - 7) имеется огра- jj ничение справа значения ординаты а, т.е. а а., знаком больше в преелах этого отрезка, то на входах торого шифрато ра устанавливается кодовая комбинация, соответствующая 20 41 порядковому номеру таблицы, котоая означает наличие количества локальных экстремумов, равное 2 - код суммы 10.. Так как неопределенностей об ограничениях в пределах всех от- 25 резков выборки больше нет, то, сумируя коды сумм . о количестве экстремумов из отрезков выборки, полуаем, что для выборки, показанной на фиг. 2с1, количество локальных Q экстремумов равно 8, что соответствует истинному количеству экстремумов .

Для первого отрезка (О - 4) выборки (фиг. 2 ) количество локальных экстремумов, определяемое в соответ- с твии с 9 порядковым номером таблицы, равно О - код суммы 00. Для второго отрезка (3 - 7) и четвертого отрезка (9- 13) количество локальных .. экстремумов в соответствии с 54 и 43 порядковыми номерами таблицы равно 1 - код суммы 01, а количество локальных экстремумов для третьего отрезка (6-10) в соответствии с 79 ,, порядковым номером таблицы равно 2 - код суммы 10. Ввиду того , что значения ординат а, а, aj равны а в пределах первого отрезка (О - 4) и значение ординаты а равное а;,„ в пределах третьего отрезка (6 - 10) не ограничено справа соот- . вётственно от значения ординат а и знаками больше или меньше, то коды знака между значениями ординат меньше - 10 об ограничении слева с дополнитель- ньЬс выходов первого и третьего шифраторов поступают соответственно на

первые входы второго и четвертого шифратора. Код знака меньше - 10 заменяет код знака равно - 00 между значениями а, а. и а, а на втором и четвертом шифраторах, а так как в анализируемых вторых (3-7) и четвертых (9 - 13) отрезках имеется ограничение справа значения ординаты а, т.е. а, а знаком больше в пределах второго отрезка (3 - 7) и значение ординаты ар , т.е. а знаком меньше в пределах четвертого отрезка (9-13), то на входах второго и четвертого шифраторов устанавливаются кодовые комбинации, соответствующие 41 и 64 порядковым номерам таблицы, которые означают, что ВО втором отрезке количество локальных экстремумов равно 2, а в четвертом отрезке количество локальных экстремумов сохраняется, т.е. равно 1. Так как неопределенностей об ограничениях в пределах всех отрезков выборки больше нет, то, суммируя коды сумм о количестве экстремумов из отрезков выборки, получаем что для выборки,показанной на фиг.2 количество локальных экстремумов равно 5. что соответствует истинному количеству экстремумов.

Для первого отрезка (О - 4) и четвертого отрезка (9 - 13) выборки (фиг. 2 ) количество локальных экстремумов в соответствии с 18 и 64 порядковыми номерами таблицы равно 1, а количество локальных экстремумов для второго отрезка (3 - 7) и третьего (6 - 10) в соответствии с 1 и 11 порядковыми номерами таблицы равно 0. Ввиду того, что значения ординат aj, aj равное а. не ограничено справа от значения ординаты а знаками больше или меньше в пределах первого отрезка (О - 4), то код знака между значениями ординат а. а больше - 01 об ограничении слева с дополнительных выходов первого шифратора поступает на первые входы второго шифратора. Код знака больше - 01 заменяет код знака равно 00 между значениями а,, а, и на входах второго шифратора устанавливается кодовая комбинация, соответствующая 5 порядковому номеру таблицы, которая означает, что во втором отрезке количество локальных экстремумов равно 0. и так как во втором отрезке меязду значениями ора , а стоит знак

равно,

динат , т. е. в справа

ками больше или меньше н пределах второго отрезка (3 - 7) то, код знака, установившийся между значениями ординат а а ограничении слева, выходов второго шифратора, поступает на первые входы третьего шифратора. Код больше - 01 заменяет код знака

этом отрезке нет ограничения от значения ординаты а зна больше - 0.1 об с дополнительных

равно - 00 между значениями

8 ю -

и на входах третьего шифратора устанавливается кодовая комбинация, соответствующая 27 порядковому номеру таблицы, которая означа- ет, что в третьем отрезке (6 - 10) количество локальных экстремумов равно 1„ Так как неопределенностей об ограничениях в пределах всех отрезков выборки больше нет, то, суммируя коды сумм о количестве экстремумов из отрезков выборки, получаем, что для выборки, показанной на фиг. 2 Ь, количество локальных экстремумов равно 3, что соответствует истинному количеству экстремумов.

Для первого (О - 4), второго (3 - 7) и третьего отрезков (6 - 10) выборки (фиг. 2 ) количество локальных экстремумов в соответствии с 5, 1 и 11 порядковыми номерами таблицы равно О, а количество локальных экстремумов для четвертого отрезка (9 - 13) в соответствии с 69 порядковым номером таблицы равно 3 - код суммы 11. Ввиду отсутствия ограничения между значениями ординат справа в первом отрезке (О - 4) знак между

значениями ординат а

01 об ограничении слева поступает на первые входы второго шифра,та и

больше 0

5

0

5

0

5

0

на его входах устанавливается кодовая комбинация, соответствующая

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

втором отрезке (3 - 7). А так как значения ординат второго отрезка (3 - 7) не имеют ограничения справа, то установившийся код между значе-. ниями ординат а т больше - 01

06ограничении слева поступает на первый входы третьего ши|)ратора и на его входах устанавливается кодовая комбинация, соответствующая 27 порядковому номеру таблицы, которая означает, что в третьем отрезке (6 - 10) количество локальных экстремумов равно 1. Так как неопределенностей- об ограничениях в пределах всех отрезков выборки больше нет, то, суммируя коды сумм о количестве экстре- мумов из отрезков выборки, получаем, что дли выборки, показанной на фиг. 2 , количество локальных экстремумов равно 4. Это соответствует истинному количеству экстремумов.

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

щ. / iztzkiiz

F

Ш

Zi.dliliiMiZlZSI