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

Изобретение относится к автоматике и вычислительной технике и MQжет быть использовано при реализации технических средств для выделения локальных мaкc мyмoв из множества сравниваемых чисел.

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

Недостатком указанного устройства является малое быстродействие.

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

10 и третий входы третьего элемента И подключены к второму и третьему управляющим входам узла, а выход третьего элемента И соединен с третьим выходом узла, первый выход каждого (iAj)-ro узла анализа соединен с J-M входом i-ro элемента ИЛИ первой :группы,второй выход каждого (ixj)-гоузла анализа подключен к j-му вхо- ду 1-го элемента ИЛИ второй группы.

20 В устройство также входят п дополнительных триггеров, группы элементов И-НЕ, И, группа элементов ИЛИ причем выход каждого i-ro элемента ИЛИ первой группы соединен с пер25вым входом i-ro элемента И-НЕ группы, с i-M информационным выходом устройства и с первым управляющим входом i-x узлов анали: а. Выход каждого i-ro элемента ИЛИ второй группы

30

.подключен к второму входу 1-го элемента И-НЕ группы, третий выход каждого ()-ro узла анализа соединен с i-M входом j-ro элемента ИЛИ третьей группы, выход каждого j-ro элемента ИЛИ третьей группы по ключен к входу установки в нулевое состояние j-ro дополнительного триггера, прямой выход каждого j-ro дополнительно о триггера соединен с J-M выходом управления устройства и с вторым управляющим входом j-x узлов анализа, выход каждого i-ro элемента И-НЕ группы подключен к первому входу i-ro элемента И группы, выход каждого из которых соединен с третьим управляющим входом... (1+1)-х узлов анализа и с вторым входом (i+1)-ro элемента И группы, вход управления устройства подключе к второму входу первого элемента И группы и третьему управляющему входу узла . анализов первых разрядов всех регистров t2, Недостатком указанного устройст|ва являются узкие функциональные возможности. Цель изобретения - расширение ,функциональных возможностей устройства путем обеспечения выделения локально-максимальных значений чиПоставленная цель достигается тем, что в устройство для выделения экстремальных чисел, содержащее п узлов сравнения, каждый из которых состоит из регистра, элемента И, уз ла связи, состоящего из двух элемен тов ИЛИ, причем выход блокировки ка дого i-ro узла сравнения, где 1 1 2,..., п, соединен с управляющим входом (i+1)-ro узла сравнения, пер вый и второй выходы переносов, каждого i-ro узла сравнения подключены к первому и второму входам переносо (i-l)-ro узла сравнения, вход опроса устройства соединен с .первым вхо дом элемента И каждого Узла -сравнен выход элемента И каждого i-ro узла сравнения подключен к i-му адресному выходу устройства, введены .т узлов коммутации, каждый и.з .которых состоит из элемента ИЛИ и двух элементов И, и схема сравнения, состоя щая из двух триггеров и трех элемеН тов И, причем прямой и инверсный . выходы каждого j-ro разряда, j 1,2,.,., m, га-количестврраэрядов в сравниваемых числах, соединены с первыми взводами первого и второго элементов И соответственно j-ro узла коммутации, выход элемент И каждого i-roузла сравнения подкй чен к первому входу элемента ИЛИ каждого узла коммутации i-ro узла сравнения, каждый j-ый вход тактовы сигналов устройства соединен с вторим входом элемента ИЛИ j-ro узла коммутации всех узлов сравнения, вы ход элемента ИЛИ каждого j-ro узла коммутации Подключен к вторым входам элементов И j-ro узла коммутации, выход первого и второго элементов И каждого j-ro узлакоммутации каждого i-ro узла сравнения соединен с J-M входом первого и второго элементов ИЛИ узла связи соответственно i-ro узла сравнения, выходы первого и второго элементов ИЛИ узла связи каждого i-rp узла сравнения подключены k первым входам первого и второго элементов И схемы сравнения i-ro узла сравнения, выходы первого и второго .элементов ИЛИ узла связи i-ro узла сравнения соединены с вторьм и первым выходами переносов соответственно i-ro узла сравнения, первый и второй входы переносов каждого i-ro узла сравнения подключены к вторым входам первого и второго элементов И схемы сравнения i-ro узла сравнения, выходы первого и второго элементов И схемы сравнения каждого i-ro узла сравнения соединены с входами установки в единичное сос. тояние первого и второго триггеров схемы сравнения i-ro узла сравнения, инверсные выходы первого и второго триггеров схемы сравнения в каждом из узлов сравнения подключены к входам третьего элемента И схемы сравнения, выход которого соединен с третьими входами первого и второго элементов И схемы сравнения, прямой выход первого триггера схемы сравнения i-ro узла сравнения подключен к второму входу элемента И i-ro узла сравнения, прямой выход второго триггера схемы сравнения соединен с выходом блокировки i-ro узла сравнения, управляющий вход каждого i-ro узла сравнения подключен к третьему входу элемента И i-ro узла сравнения, выход первого элемента И каждого j-ro узла коммутации каждого i-ro узла сравнения соединен с j-ым информационным выходом i-ro узла сравнения. На чертеже приведена функциональная схема устройства. Устройство содержит п узлов сравнения 1, каждый из которых состоит из регистра 2, элемента ИЗ, узла связи 4, состоящего из первого 5 и второго б элементов ИЛИ, m узлов коммутации 7, содержащих элемент ИЛИ 8, первый 9 и второй 10 элементы И, схемы сравнения 11, состоящей из первого 12 и второго 13 триггеров/ первого 14, второго 15 и третьего 16 элементов И, и m информационных вы ходов 17, m входов 18 тАктовых сигналов, п адресных выходов 19, вход 20 опроса. Считают, что узлы сравнения 1 и входящие в их состав схемы сравнения 11 имеют текущий индекс i и пронуме-;

рованы сверху вниз от 1 до п, разряды чисел имеют текущий индекс j и пронумерованы слева направо от 1 до m (первый - старший, т-й - младший) .

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

В исходном состоянии все регистры 2 содержат нулевую информацию первый 12 и второй 13 триггеры схели сравнения 11 - в нулевом состояНИИ.

Единичные уровни с инверсных выходов триггеров 12. и 13 поступают н входы третьего 16 элемента И схемы сравнения, а единичный уровень с вы хода элемента И 16 подается на третьи входы элементов И 14 и 15. В силу перекрестного соединения выходов элементов ИЛИ 5 и б с выходами переносов в пределах каждого узла сравнения на элементе И 14 сравниваются сигналы с прямого выхода j-ro разряда регистра i-ro узла сравнения и с инверсного выхода j-ro разряда регистра (i+1) -го узла сравнения, а н элементе И 15 - с инверсного выхода j-ro разряда регистра i-ro узла сравнения и прямого выхода того же разряда регистра (i+1)-ro узла сравнения.

В регистры 2 узлов сравнения принимаются двоичные числа. Сравнение всех разрядов происходит одинаково по тактовым сигналам единичного уровня.

Первый тактовый сигнал подается через элемент ИЛИ 8 на вторые входы элементов И 9 и 10 -первого узла коммутации 7 всех узлов сравнения и , открывает цепи прохождения сигналов с прямого и инверсного выходов первого разряда всех регистров соответственно через элементы ИЛИ 5 и ИЛИ на первые входы элементов И 14 и 15 схемя сравнения 11.

Если в первом разряде регистров i-ro и (i+1)-ro узлов сравнения содержатся соответственно 1 и О, то на обоих входах первого 14 элемен та И схемы сравнения 11 будут сигналы единичного уровня, а на обоих входах второго 15 элемента И этой схема - сигналы нулевого уровня. В единичное состояние установится первый 12 триггер i-й схемы сравнения. Нулевой уровень с инверсного выхода этого триггера подается на вход третьего 16 элемента И и нулевой уровень с его выхода, поданный на третьи входы элементов И 14 и 15, разрывает цепь прохождения сигналов через первый 14 и второй 15 элементы

И i-й схемы сравнения. Сравнение i-ro и (i+1)-ro значений чисел на этом заканчивается.

Если в первом разряде регистров i-ro и (1+1)-го узлов сравнения содержатся соответственно О и 1, то в единичное состояние установится второй 13 триггер i-й схемы сравнения. Сравнение i-ro и (i4-1)-ro чисел на этом тоже заканчивается.

Если в первом разряде регистров i-ro и (i+1)-ro узлов сравнения содержится одинаковая информация, то на первом и втором входах элементов И 14 и 15 будут сигналы разного уровня. Следовательно на выходах этих элементов будет нулевой уровен и триггеры 12 и 13 i-й схемы сравнения 11 останутся в исходном состоя йии. Сравнение чисел будет продолжено в следующих разрядах.

После окончания сравнения последнего т-го разряда чисел на вход 20 опроса подается сигнал единичного уровня, который поступает на первый вход элементов И 3 всех узлов сравнения, На выходе элемента И 3 i-ro узла сравнения сигнал единичного уровня будет в случае, когда на втором и третьем его входах будет единичный уровень. Это соответствует состоянию первого 12 и второго 13 триггеров (i-l)-ro узла сравнения О и 1 и состоянию триггеров 12 и 13 i-ro узла сравнения 1 и О, т.е. наличию локального максимума в регистре i-ro узла сравнения. Единичный уровень с выхода элемента И 3 поданный через первый вход элемента ИЛИ 8-всех узлов коммутации 7 i-ro узла сравнения 1, разрешает считывание значения локально-максимального числа с информационных выходов 17. Единичный уровень на адреном выходе устройства указывает положение локального максимума.

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

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

Устройство для выделения экстремальных чисел, содержащее п узлов сравнения, каждый из которых состоит из регистра, элемента И, узла связи, состоящего из двух элементов ИЛИ, причем выход блокировки каждо го i-ro узла сравнения, где i 1, 2,..., п, соединен с управляющим входом (i+.1)-ro узла сравнения, первый и второй выходы переносов каждого i-ro узла сравнения подключены к первому и второму входам перено