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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик оч 1 003070 (61) Дополнительное к ввт. свид-ву (22) Заявлено 22.09.81 (21) 3340296/18.-24 (51) М. Кл.з с присоединением заявки ¹ (23) Приоритет

G 06 F 7/02

Государственный комитет

1 СССР ио делам изобретений н открытий ($3) УДК 681 ° 325 3 (088. 8) Опубликовано 07.03 83.Бюллетень ¹ 9

Дата опубликования описания 07.03 ° 83 (72) Авторы .изобретения

;Г.A Поляков и В.Е. Козлов

»л (71) Заявитель

;!

1 ««юане »-, ч-,щ1 (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ

ЧИСЕЛ

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

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

Выделение экстремального числа в устройстве производится поразрядным сравнением, осуществляемым по управляющим тактовым сигналам за а шагов 1).

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

Наиболее близким к предлагаемому является устройство для выделения экстремального из n m-разрядных двоичных чисел, содержащее n m-разрядных регистров на триггерах, выходы триггера каждого 1-го разряда

j-ro регистра (где i=1, 2,..., m, j=.1,2,..., n) соединены с информационнйми входами (j)-узла анализа.

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

j-м входом i-го элемента ИЛИ первой группы, второй вь1ход каждого (ixj) -го. узла анализа подключен к j-му вхоДу 1-Го элемента ИЛИ второй группы

В устройство также входят и дополнительных триггеров, группы элементов И-НЕ, И, группа элементов ИЛИ„ причем выход каждого i-го элемента

ИЛИ первой группы соединен с первым входом i-го элемента И-НЕ группы, с i-M информационным выходом устройства и с первым управляющим входом 1-х узлов анали:а. Выход каждого i-го элемента ИЛИ второй группы 0,ïîäêëþ÷åH к второму входу i-го эле1003070 мента И-НЕ группы, третий выход каждого (18 j)-го узла анализа соединен c i-м входом j-ro элемента

ИЛИ третьей группы, выход каждого

j-го элемента ИЛИ третьей группы подключен к входу установки в нулевое состояние -го дополнительного триггера, прямой выход каждого j-го дополнительного триггера соединен с, j-м выходом управления устройства и с вторым управляющим входом j-х уз- 10 лов анализа, выход каждого i-го элемента И-ЙЕ группы подключен к первому входу i-го элемента И группы, выход каждого из которых соединен с третьим управляющим входом,. 15 (i+1)-х узлов анализа и с вторым входом (itl)-ro элемента И группы, вход управления устройства подключен к второму входу первого элемента И группы и третьему управляющему в оду узла . анализов первых разрядов всех регистров g2).

Недо"татком укаэанного устройст-! ва являются узкие функциональные возможности.

Цель изобретения — расширение ,функциональных возможностей устройства путем обеспечения выделенищ локально-максимальных значений чисел. поставленная цель достигается тем, что в устройство для выделения экстремальных чисел, содержащее и узлов сравнения, каждый из которых состоит из регистра, элемента И, узла связи, состоящего из двух элемен- З тов ИЛИ, причем выход. блокировки каждого i rî узла сравнения, где i = 1, 2,..., n, соединен с управляющим входом (i+1)-ro узла сравнения, первый и второй выходы переносов, каж- 40 дого i-ro узла сравнения подключены к первому и второму входам переносов (i-1)-ro узла сравнения, вход опроса устройства соединен Е .первым входом элемента И каждого узла-сравнения@ выход элемента И каждого i-го узла сравнения подключен к i-му адресному выходу устройства, введены m узлов коммутации, каждый из которых состоит из элемента ИЛИ и двух эле-, 50 ментов И, и схема сравнения, состоя щая нз двух триггеров и трех элемен тов И, причем прямой и инверсный выходы каждого j-ro разряда, где

1, 2,..., m, m-количество разрядов в сравниваемых числах, соединены с первыми входами первого и второго элементов И соответственно

j-ro узла коммутации, выход элемента

И каждого i-го узла сравнения подключен к первому входу элемента ИЛИ каждого узла коммутации i-го узла сравнения, каждый j-ый вход тактовых сигналов устройства соединен с вторым входом элемента ИЛИ j-ro узла коммутации всех узлов сравнения, вы- 45 ход элемента ИЛИ каждого у-го узла коммутации Подключен к вторым входам элементов И j-го узла коммутации, выход первого и второго элементов И каждого j-го узла коммутации каждого i-ro узла сравнения соединен с

j-м входом первого и второго элементов ИЛИ узла связи соответственно

i-го узла сравнения, выходы первого и второго элементов ИЛИ узла связи каждого i-го узла сравнения подключены к первым входам первого и второго элементов И схемы сравнения

i-го узла сравнения, выходы первого и второго .элементов ИЛИ узла связи

i-го узла сравнения соединены с вторым и первым выходами переносов соответственно i-го узла сравнения, первый и второй входы переносов каждого

i-ro узла сравнения подключены к вторым входам первого и второго элементов И схемы сравнения i-ro узла сравнения, выходы первого и второго элементов И схемы сравнения каждого

i-ro узла сравнения соединены с входами установки в единичное сос" тояние первого и второго триггеров схемы сравнения i-го узла сравнения, инверсные выходы первого и второго триггеров схемы сравнения в каждом из узлов сравнения подключены к входам третьего элемента И схемы сравнения, выход которого соединен с третьими входами первого и второго элементов И схемы -сравнения, прямой выход первого триггера схемы сравнения i-ro узла сравнения подключен к второму входу элемента И

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

i-го узла сравнения.

На чертеже приведена функциональная схема устройства.

Устройство содержит и узлов сравнения 1, каждый из которых состоит из регистра 2, элемента И 3, узла связи 4, состоящего из первого 5 . и второго б элементов ИЛИ, m узлов коммутации 7, содержащих элемент

ИЛИ 8, первый 9 и второй 10 элементы .

И, схемы сравнения 11, состоящей иэ первого 12 и второго 13 триггеров, первого 14, второго 15 и третьего 16 элементов Й, и m информационных вы.ходов 17, m входов 18 тактовых сигналов, и адресных выходов 19, вход

20 опроса.

Считают, что узлы сравнения 1 и входящие в их состав схемы сравнения

11 имеют текущий индекс i и пронуме-, 1003070

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

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

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

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

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

Если в первом разряде регистров

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

И i-й схемы сравнения. Сравнение

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

Если в первом разряде регистров

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

Если в первом разряде регистров

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

После окончания сравнения последнего m-го разряда чисел на вход 20 опроса подается сигнал единичного уровня, который поступает на первый вход элементов И 3 всех узлов сравнения, На выходе элемента И 3 i-ro узла сравнения сигнал единичного уровня будет в случае, когда на втором и третьем его входах будет единичный уровень. Это соответствует состоянию первого 12 и второго 13 триггеров (i-1)-го узла сравнения

"0" и "1" и состоянию триггеров 12 и 13 i-го узла сравнения "1" и "0", т.е. наличию локального максимума в регистре i-ro узла сравнения. Единичный уровень с выхода элемента И 3, поданный через первый вход элемента ИЛИ 8-всех узлов коммутации 7

i-ro узла сравнения 1, разрешает считывание значения локально-максимального числа с информационных выходов 17. Единичный уровень на адресном выходе устройства указывает положение локального максимума.

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

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

Устройство для выделения экстремальных чисел, содержащее и узлов сравнения, каждый из которых состоит из регистра, элемента И, узла связи, состоящего из двух элементов

ИЛИ, причем выход блокировки каждо.

iго i-ro узла сравнения, где i = 1, 2,..., n соединен с управляющим входом (i+1)-го узла сравнения, первый и второй выходы переносов каждого i-го узла сравнения подключены .к первому и второму входам перено1003070

35ф

ВГИИПИ Заказ 1554/32 Тираж 704 . Подписное

Филиал ППП "Патент", r.ужгород,ул,Проектная,4 сов (i-1)-ro узла сравнения, вход опроса устройства соединей с первым входом элемента И каждого узла сравнения, выход элемента И каждого i-го узла сравнения подключен к i-му адресному выходу устройства, о т л и

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

m узлов коммутации, каждый из которых состоит из элемента ИЛИ и двух элементов И, и схема сравнения, состоящая из двух триггеров и трех эле- ментов И, причем прямой и инверсный выходы каждого j-ro разряда регистра, где 1 = 1, 2,...,в, ю-количество разрядов в сравниваемых числах, соединены с первыми входами первого и второго элементов И соответст- Щ

BBHIIo j го узла коммутации, выход элемента И каждого i-ro узла сравнения подключен к первому входу элемента ИЛИ каждого узла коммутации

1-го узла сравнения, каждый -й 25 вход тактовых сигналов устройства соединен с вторым входом элемента

ИЛИ i-ro узла коммутации всех узлов сравнения, выход элемента ИЛИ каждого j-ro узла коммутации подключен к вторым входам элементов И j-ro узла коммутации, выход первого и второго элементов И каждого j-ro узла коммутации каждого i-ro узла сравнения соединен с 1-м входом первого и второго элементов. ИЛИ узла связи соответственно i-го узла сравнения, выходы первого и второго элементов ИЛИ узла связи каждого

i-го узла сравнения подключены со1 ответственно к первым входам первого и второго элементов И схемы сравнения i-ro узла сравнения, выхо-.. ды первого и второго элементов ИЛИ узла связи i-ro узла сравнения сое;цинены соответственно со вторым и первым выходами переносов i-го узла сравнения, первый и второй входы

1 ереносов каждого i-ro узла сравне ния подключены к вторым входам пер. вого и второго элементов И схемы" сравнения i-го узла сравнения, выходы первого и второго элементов И схемы сравнения каждого i-ro узла сравнения соединены с входами установки в единичное состояние первого и второго триггеров схемы сравне. ния i-ro узла сравнения, инверсные выходы первого и второго триггеров схемы сравнения в каждом из узчов сравнения подключены к входам третьего элемента И схемы сравнения, выход которого соединен с третьими входами первого и второго элементов

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

j-го узла коммутации каждого i-ro узла сравнения соединен с j-ым инфор мационным выходом i-ro узла сравнения.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

Р 514291, кл. G 06 F 7/02, 1973.

2. Авторское свидетельство СССР

Р 752326, кл. G 06 F 7/02, 1978 (прототип).