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

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

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

УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ ЧИСЕЛ, содер)-атее И блоков сравнения(п - количество срав-. 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 -го блока срав

Л ,.; , Изобретение относится к автомати ке и вычислительной технике и может быть использовано при реализации те нических средсгв для выделения локальных экстремумов из множества сравниваемых чисел. Известно устройство для выделения экстремального из пт-разрядных двоичных чисел, содержащее пт-разря ных регистров узлов анализа. состоящих из трех элементов И, ц до полнительных триггеров, группы элементов И-НЁ,. iPl, группу элементов ИЛИ Выделение экстремального числа в уст ройстве производится поразрядным сравнением по сигналам, Формируемым по окончании сравнения в данном разряде или если во всех триггерах да;нного разряда содержится одинаковая информация (все нули или все единицы) 1 . Недостатком такого устройства являются узкие функциональные возможности . Наиболее близким техническим реше нием к изобретению является устройство для выделения экстремальных чисел, содер жа1пее и узлов сравнения причем выход блокировки каждогоi-ro узла сравнение, где 1,2,...,п, соединен с управляющим входом (j + + узла сравнения, первый и второй выходыпереносов каждого и-го узла сравнения подключены к первому и второму входам/переносов (i- 1)-г узла сравнения, вход опроса устройства соединен с первым входом элемента И каждого узла сравнения, выход элемента И каждого i -го узла сравнения подключен к i -му адресному выходу устройства, каждый узел сравнения содержит регистр, элемент И и узел связи, состоящий из двух элементов ИЛИ, П) узлов коммутации, состоящих из элемента И1Ш и двух элементов И, и схему сравнения, которая состоит из двух триггеров и трех элементов И, причем прямой и инверсный выходы каждого « -го разряда регистра, где i 1, 2,.. . , m ( hi - количество разрядов в сравниваемых числах), соединены с первыми входами первого и второго элементов И соответственно j-го узла коммутации, выход элемента И каждого i-ro узла сравнения подключен к первому входу элемента ИЛИ каждого узла комл тации i -го узла сравнения, каждыйj-и вход тактовых сигналов устройства соединен с вторым входом элемента ИЛИ j-го узла коммутации всех узлов сравнения, выход элемента ИЛИ каждого j -го узла коммутации подключен к вторым входам элементов И J-го узла коммутации, выход первого И второго элементов И каждого j -го узла коммутации каждого -го узла сравнения соединен с j-м входом первого и второго элемента ИЛИ узла связи соответственно i -го узла сравнения, выходы первого и второго элементов ИЛИ узла связи каждого If -го узла сравнения подключены к первым входам первого и второго элементов И соответственно схемы-сравнения 1-го узла сравнения, выходы первого и второго элементов ИЛИ узла связи -го узла сравнения соединены с вторым и первым выходами переносов соответственно i-го узла сравнения. первый и второй входы переносов каж дого J -го узла сравнения подключены к вторым входам первого и второго элементов И схемы сравнения ( -го узла сравнения, выходы первого и второго элементов И схемы сравнения каждого i-го узла срарнения соединены с входами установки в единично состояние первого и второго триггеров cxevN сравнения -го узла cpiaBнения, инверсные выходы первого и в рого триггеров схемы сравнения в ка дом из узлов сравнения подключены к входам третьего элемента It схемы сравнения, выход которого соединен с третьими входами первого и второго элементов И схемы с{ авнеНия, прямой выход первЫ О триггера схемы сравнения i-го узла сравнения подключен к второму входу элемента И 4-го узласравнения, прямой выход второго триггера схемы сравнения соединен с выходом блокировки t-го узла сравнения, управляющий вход каждого 4 -го узла сравнения подключен к третьему входу элемента И i-ro узла сравнения, выход первого элемента И каждого j -го узла коммутации каждого -го узла сравнения соединен с j -м информационным выходом (-ГО узла сравнения 2J . Недостаток известного устройства также обусловлен узкими, функциональными возможностями. Цель изобретения - расширение функциональных возможностей устройства путем обеспечения выделения локально-минимальных значений чисел Поставленная цель достигается тем, что в устройство для выделения экстремальных чисел, содержащее ц блоков сравнения ( п - количество сравниваемых чисел ),каждый из которых содержит регистр, первый элемент И, узел связи, состоящий из первого и второго элементовИЛИ, m узлов коммутации (т - число разрядов сравниваемых чисел, каждый из которыхсостоит из первого и вто рого элементов И и элемента ИЛИ, и схему сравнения, состоящую из первого и второго триггеров, перво го, второго и третьего элементов И, приче; первый выход блокировки каждого 1 -го блока сравнения ( 1,2, ... , п) соедин ен с первым управляющим входом 14 + 1)-го блока сравнения, первый и второй выходы переносов каждого «i -го блока сравнения подключены к первому и второму входам переносов {ч-1)-го блока сравнения , первый вход опроса устройства соединен с .первыми входами первых элементов И каждого блока сравнения, выход элемента И i -го блока сравнения подключен к первому адресному выходу 4-го блока сравнения прямой и инверсный выходы j-го раэряда регистра (j 1,2, ..., m) каждого блока сравнения соединены с первыми входами первого и второго элементов И соответственно j -го узла коммутации,j -и вход тактовых сигналов устройства соединен с первым входом элемента ИЛИ j-го узла коммутации каждого блока сравнения, выход элемента ИЛИ j -го узла коммутации каждого блока сравнения подключен к вторым входам элементов И j-го узла коммутации, выходы первого и второго элементов И j -го узла коммутации -го блока сравнения соединены с j-ми входами первого и второго элементов ИЛИ узла связи соответственно -гр блока сравнения, выходы первого и второго элементов ИЛИ узла связи i -го блока сравнения подключены к первым входам первого и второго элементов И соответственно схемы сравнения i -го блока сравнения, и к первым и вторым выходам переносов соответственно ч -го блока сравнения,Первый и второй тйход;-л переносов i -го блока сравнения подключены к вторым входам первого и второгчэ элементов И схемы сравнения . -го блока сравнения, выходы первого и второго элементов К схе сравнения i-го блока сравнения соединены с входами установки в единичное состояние первого И- второго триггеров схемы сравнения i -го блока сравнения, инверсные выkoды первого и второго триггеров схемы сравнения t -го блока сравнения подключены к входам третьего элемента И схемы сравнения, выход третьего элемента И схемы сравнения соединен с третьиьот входами первого и второго элементов И схемы сравнения 1-го блока сравнения, прямой выход первого триггера cxevw сравнения i -го блока сравнения подключен к второму входу первого элемента И, 1-го блока сравнения, прямой -выход второго триггера сравнения соединен с первым выходом блокировки 4-го блока сравнения, первмй управляющий вход « -го блока сравнения подключен к третьему входу первого элемента Н 4-го блока сравнения, выход первого элемента И, -го узла коммута11ии i-го блока сравнения соединен crj -м информационным выходом i-го блока сравнения, в каждый блок сравнения введены элемент ИЛИ и второй элемент И, причем второй выход блокировки -го блока сравнения соединен с вторым управляющим входом (4+ 1)-го блока сравнения, второй вход опроса устройства соединен с первым входом второго элемента И i -го блока сравнения, выход второго элемента И -го .блока сравнения подключен к второму ад- . ресному выходу i-ro блока сравнения, инверсный выход первого триггера

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

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

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

Устройство содержит п блоков 1 сравнения, состоящих из регистра 2, Элемента И 3, узла 4 связи, который состоит из первого 5 и второго 6 элементов ИЛИ, m узлов 7 коммутации содержащих элемент ИЛИ 8, первый 9 и второй 10 элементы И, схемы 11 сравнения, в состав которой входят первый 12 и второй 13 триггеры, первый 14, второй 15 и третий 16 элементы И, а также tti информационных выходов 17, m входов 18 тактовых сигналов, п адресных выходов 19, вход 20 опроса, п вторых адресных выходов 21 и второй вход 22 опроса. В состав блока сравнения входят также элемент ИЛИ 23 и второй элемент И 24.

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

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

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

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

а на элементе И 15 - с инверсного

выхода j-го разряда регистра 2 -го

блока 1 сравнения и прямого выхода . того же разряда регистра 2 + 1/ -го блока сравнения.

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

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

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

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

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

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