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

 

УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ ЧИСЕЛ, содер)-атее И блоков сравнения(п - количество срав-. HHBaeNf-ix чисел), каждый из которых содержит регистр, первый элемент И, узел связи, состоящи; из первого и второго элементов ИЛИ,m узлов коммутации (п - число разрядов сравниваем 1х чисел), каждый из которчх состоит из первого и второго элементов И и элемента ИЛИ, и схему сравнения, состоглпую из первого и второго триггеров, первого, второго и третьего элементов И, причем первый вь-хвд блокировки каждого -го блока сравнения (i 1,2, ..., t) соединен с nepBbiM управляющим входом ( + 1) -го блока сравнения, первый и второй выходы переносов каждого ( -го блока сравнения подключены к первому и второму входам переносов ( - 1J-го блока сравнения , первчй вход опроса устройства соединен с первыми входами первых элементов И каждого блока сравнения , выход элемента И -го блока сравнение подключен к первомуадресному выходу ; -го блока сравнения, прямой и инверсный выходы j -го разряда регистра (i 1,2, ...,) каж дого блока сравнения соединены с первыми входами первого и второго элементов И соответственно j -го узла коммутации, j -и вход тактовых сигналов устройства соединен с первым входом элемента ИЛИ j -го узла коммутации каждого блока сравнения, выход элемента ИЛИ j -го узла коммутации казддого .блока сравнения подключен к вторым нходам элементов И i -го узла коммутацп:, Быxoд - первого и второго элементов И j -го узла коммутации i -го блока сравнения соединен с j-ми входами первого и .второго элементов ИЛИ узла связи соответственно i-го Олока соавнения , выходы пеового и второго элементов ИЛИ узла связи i -го блока сравнения подключены к первым входам первого и второго элементов И соответственно схемы сравнения 4-го блока сравнения и первым и вторым выходам переносов соответ (Л ственно i -го блока сравнения, первый и второй входы переносов ( -го блока сравнения подключенч к вторым входам первого и второго элементов И схемы сравнения i -го блока сравнения , выходы первого и второго элементов И схемы сравнения -го блока сравнения соединены с входами установки в единичное состояние первого и второго триггеров схемы ел сравнения 1-го блок-а сравнения, инверсные выход-- первого и второго со сд триггеров схем;.- сравнения i -го блока срав.нения .подключены к входам 05 третьего элемента И схемы сравнения, выход третьего элемента И схемы сравW нения соединен с третьими входами первого и второго элементов И схемы сравнения i -го блока сравнения, прямой выход первого триггера схемы сравнения i-го блока сравнения подключен к второму входу первого элемента И -го блока сравнения, прямой выход второго триггепа cxeMi-j сравнения соединен с первым выходом блокировки -го блока сравнения, первый управляющий вход i -го блока сравнения подключен к третьему входу первого элемента И j -го блока срав

.СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН

M5D 06 Р 7 12

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ, (21) 3466924/18-24 (,22) 08.07.82 (46) 07.12.83. Вюл. М 45 (72) Г.А. Поляков и В.Е. Козлов (53) 681. 325. 5 (088. 8) (56) 1. Авторское свидетельство

СССР Р 752326, кл. С 06 г 7/02, 1978.

2. Авторское свидетельство СССР по зачвке .) 3340296/18-24, кл. 06 F 7/02, 1981 (прототип) . (54) (57) УСТРОЙСТВО ДЛЙ В??ДЕЛЕНИЯ

ЭКСТРЕМАЛЬНЫХ ЧИСЕЛ, содержащее г? блоков сравнения (n — количество срав-. ниваем-|х чисел), каждый из которых содержит регистр, первый элемент

И, узел связи, состоящий из первого и второго элементов ?IJIH,гП узлов коммутации (и? — число разрядов сравниваемых чисел 1, каждый из которых состоит из nepaoro и второго элементов И и элемента ИЛИ, и схему сравнения, состочщую из первого и второго триггеров, первого, второго и третьего элементов И, причем первый в сбд блокировки каждого

j --ro блока сравнения (л = 1,2, tl) соединен с первым управляющим входом (< + 1) -го блока сравнения, первый и второй выходы переносов каждого j -го блока сравнения подключены к первому и второму входам переносов (1 в 1) -го блока сравнения, перв.-|й вход опроса устройства соединен с первыми входагли первых элементов И каждого блока сравнения, выход элемента И q -го блока сравнения подключен к первому адресному 1выходу s -го блока сравнения, прямой и инверсный выходы -го разряда регистра (i 1,2, ..., гг)каж— дого блока сравнения соединены с первыми входами первого и второго элементов И соответственно 1 -го узла коммутации, j -й нход тактовых сигналов устройства соединен с пер„„SU„„1059563 А вым входогл элемента ИЛИ 1 -го узла коммутации каждого блока сравнения, выход элемента ИЛИ j -го узла коммутации каждого .блока сравнения подключен к вторым Exодам элементов

И ) -го узла коммутацг?г, выходя первого и второго элементов И -го узла коммутации 1 --ro блока сравнения соединен с ) -ми входами первого и второго элементов ИЛИ узла связи соответственно q -ro блока сравнения, выходя пеового и второго элеглентон ИЛИ узла связи 1 -го блока сравнения подключены к первым входам первого и второго элементов

И соответственно схемы сравнения -го блока сравнения и первым и вторым выходам переносов соответственно < -го блока сранненич, первый и второй входы переносов < — го блока сравнения подключены к вторягл входам первого и второго элементов

И схемы сравнения I --го блока сравнения, выходы первого и второго элементов И схемы сравнения j --го блока сравнения соединены с входами установки в единичное состояние первого и второго триггеров схемы сравнения < -го блока сравнения, инверсные выходя первого и второго триггеров схемы сравнения (-го блока сравнения .подключены к входам третьего элемента И схемы сравнения, выход третьего элемента И схемы сравнения соединен с третьими входами первого и второго элементов И схемы сравнения j -го блока сравнения, прямой выход перного триггера схемы сравнения j --го блока сравнения подключен к второму входу первого элемента И q-ro блока сравнения, прямой выход второго триггера схемы сравнения соединен с первым няходом блокировки < -го блока сравнения, первый управляющий вход i -ro блока сравнения подключен к третьему входу первого элеглента И j -ro блока срав1059563 кения, выход первого элемента И «го узла коммутации i --ro блока сравнения соединен с j --м информационным .выходом a --ro блока сравнения, о т л и ч а ю щ е е с я тем, что с целью расширения его функциональных возможностей путем обеспечения выделения локально- минимальных значений чисел, в каждый блок сравнения введены элемент ИЛИ и второй элемент И, причем второй выход блокировки i --ro блока сравнения соединен с вторым управляющим входом (j + 1j -го блока сравнения, второй вход опроса устройства соединен с первым входом второго элемента И

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

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

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

Выделение экстремального числа в устройстве производится поразрядным 15 сравнением по сигналам, Формируеыым по окончании сравнения в данном разряде или если во всех триггерах данного разряда содержится одинаковая информация (все нули или все единицы) N

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

Наиболее близким техническим реше- р5 нием к изобретению является устройство для выделения экстремальных чисел, содержащее п узлов сравнения, причем выход блокировки каждого 4 -го узла сравнения, где < = 1,2,...,п, соединен с управляющим входом (+

+ 1j -го узла сравнения, первый и второй Выходы переносов каждого -zo узла сравнения подключены к первому и ВтОрОму ВхОдам: переносОВ { — 1) — ГО З узла сравнения, вход опроса устройства соединен с первым входом элемента И каждого узла сравнения, выход элемента И каждого -го узла сравнения подключен к -му адрес 1-го блока сравнеыия, инверсный выход первого триггера схемч сравнения 1 -го блока сравнения соединен с вторым входом, второго элемента И

<-го блока сравнения, инверсный выход второго триггера схемы сравнения

<-го блока сравнения соединен с вто рым выходом блокировки -го блока ° сравнения;, второй управляющий вход

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

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

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

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

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

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

И соответственно схемы .сравнения

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

40 первый и второй входы переносов каждого -го узла сравнения подключены к вторым входам первого и второго элементов И схемы сравнения (-го узла сравнения, выходы первого и второго элементов И схемы сравнения 5 каждого j -го узла сравнения соединены с входами установки в единичное состояние первого и второго тригге-. ров схемы сравнения j -го. узла сравнения, инверсные выходы первого и вто-30 рого триггеров схемы сравнения в каждом из узлов сравнения подключены к входам третьего элемента И схемы сравнения, выход которого соединен с третьими входами первого,и второго элементов И схемы сравнения, прямой выход первого триггера схемы сравнения s --ro узла сравнения подключен к второму входу элемента

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

i-ro узла сравнения, выход первого элемента И каждого I --го узла коммутации каждого ) -го узла сравнения соединен с 1 -м информационным выходом <-го узла сравнения (2) .

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

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

Поставленная цель достигается тем, что в устройство для выделения экстремальных чисел, содержащее д блоков сравнения (и — количество сравниваемых чисел), каждый из которых содержит регистр, первый элемент И, узел связи, состоящий из первого и второго элементов ИЛИ, в узлов коммутации (m - число раз- 45 рядов сравниваемых чисел), каждый из которых состоит из первого и второго элементов И и элемента ИЛИ, и схему сравнения, состоящую из первого и второго триггеров, первого, второго и третьего элементов И, причем первый выход блокировки каждого 1 -го блока сравнения (j = 1,2, ...,nI соединен с первым управляющим входом (i + 1) -го блока cpasнения, первый и второй выходы переносов каждого q -го блока сравнения подключены к первому и второму входам переносов (-1)-ro блока сравнения, первый вход опроса устройства соединен с,первыми входами пер- 60

I вых элементов И каждого блока сравнения, выход элемента И < - го блока сравнения подключен к первому адресному выходу -го блока сравнения, прямой и инверсный выходы $ -""го раз- 65 ряда регистра tj = 1,2, ...,rn) каж» дого блока сравнения соединены с первыми входами первого и второго элементов И соответственно -го узла коммутации, j -й вход тактовых сигналов устройства соединен с первым входом элемента ИЛИ j --го узла коммутации каждого блока сравнения, выход элемента ИЛИ j -ro узла коммутации каждого блока сравнения. .подключен к вторыь входам элементов

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

ИЛИ узла связи 1 -го блока сравнения подключены к первым входам первого и второго элементов И соответственно схемы сравнения j --го блока сравнения и к первым и вторым выходам переносов соответственно s -го блока сравнения, первый и второй ахорун пе. реносов (-го блока сравнения подключены к вторым входам первого и второго элементов И схемы сравнения

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

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

1059563 схемы сравнения I --ro блока сравнения соединен с вторым входом второго элемента И I -го блока сравнения, инверсный выход второго триггера схемы сравнения j-ro блока сравнения соединен с. вторым выходом блокиров- 5 ки < --го блока сравнения, второй управляющий вход -го блока сравнения подключен,к третьему входу второго элемента И этого блока сравнения, выходы первого и второго эле- 10 ментов И -ro. блока сравнения подключены к входам элемента ИЛИ того же блока сравнения, выход элемента

ИЛИ j -ro блока сравнения соединен с вторыми входами элементов ИЛИ всех узлов коммутации е -го блока сравнения.

Такое выполнение позволяет выделять наряду,с локально-максимальными значениями локально-минимальные значения чисел.

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

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

9 и второй 10 элементы И, схемы 11 сравнения, в состав которой входят первый 12 и второй 13 триггеры, первый 14, второй 15 и третий 16 элементы И, а также Ф информационных выходов 17, ы входов 18 тактовых сигналов, и адресных выходов 19, вход 20 опроса, и вторых адресных выходов 21 и второй вход 22.опроса.

В состав блока сравнения входят также элемент ИЛИ 23 и второй элемент

И 24. 40

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

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

В исходном состоянии все регистры 50

2 содержат нулевую информацию, первый 12 и второй 13 триггеры блока

1 сравнения находятся в нулевом состоянии.

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

2 j -го блока 1 сравнения и с инверсного выхода 1 -го разряда регистра 2 (< + 1) -го блока 1 сравнения, а на элементе И 15 — с инверсного выхода I --ro разряда регистра 2 i --го блока 1 сравнения и прямого выхода ° того же разряда регистра 2 (» + 1) -ro блока. сравнения.

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

В регистры 2 блоков 1 сравнения принимаются двоичные числа. Первый тактовый сигнал с входа 18 подается через элемент ИЛИ 8 .на вторь|е входи элементов И 9 и 10 первого узла 7 коммутации всех блоков 1 сравнения и открывает цепи прохождения сигналов с прямого и инверсного выходов первого разряда всех регистров соответственно через элементы ИЛИ 5 и б на первые входы элементов И

14 и 15 схемы 11 сравнения.

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

i-ro и (i + 1)-го блоков сравнения содержатся соответственно "1" и

"0", то на обоих входах первого элемента И 14 i -й схемы 11 сравнения будут сигналы единичного уровня, а на обоих входах второго элемента И 15 этой схемы — сигналу нулевого уровня. В единичное состояние установится первый 12 триггер i --й схемы сравнения. Нулевой уровень с инверсного выхода этого триггера подается на вход третьего элемента

И 16, и нулевой уровень с его выхода, поданный на третьи входы элементов .

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

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

I-ro и (+ 1) -ro блоков сравнения содержатся соответственно "й" и

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

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

После окончания сравнения по леднего rn-го разряда чисел на вход

1059563

ВНИИПИ 3 акаэ 9841/52 Тираж 706 Подписное

Филиал ППП "Патент", r.Óêãîðoä,óë.Ïðoåêòíàÿ,4

20 опроса подается сигнал единичного уровня, который поступает на первый вход элементов И 3 всех блоков сравнения. На выходе элемента

И 3 t --ro блока сравнения сигнал единичного уровня будет в случае, когда на втором и третьем его входах будет единичный уровень. Это соответствует состоянию первого 12 и второго 13 триггеров (j — 1)-ro блока сравнения "0" и "1" и состоянию триггеров 12 и 13 i -го блока сравнения "1" и "0", т.е. наличию .локального максимума s регистре j -го блока сравнения. Единичный уровень с выхода элемента И 3, поданный через элемен ИЛИ 23 и первый вход элемента ИЛИ 8 всех узлов 7 коммутации » --го блока 1 сравнения, разрешает считывание значения локально-максимального числа с информационных выходов 17.. Единичный уровень на адресном выходе 21 устройства указывает положение локального максимума.

Сигнал единичного уровня, поданный на второй вход 22 опроса, поступает на первый вход вторых элемен-тов И 24 всех блоков 1 сравнения.

На выходе элемента И 24 i --го блока 1 сравнения сигнал единичного уровня будет, когда состояние первого 12 и второго 13 триггеров (» -1).-го и j.-го

5 блока 1 сравнения будут соответственно "1", "0" и "0", "1", что указывает на наличие локального минимума в регистре 2 i -го блока сравнения. Единичный уровень с выхода

1О второго элемента И 24, поданный через элементы ИЛИ 23 и 8 на все узлы 7 коммутации j го блока сравнения, разрешает считывание локально-минимального числа с информа 5 ционных выходов 17. Единичный уровень на втором адресном выходе 19 устройства указывает положение локального минимума.

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