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

ОЮЗ СОВЕТСКИХОЦИАЛИСТИЧЕСНИХЕСПУБЛИН 59563 19) (111 11 06 г 7 ГОСУДАРСТВЕННЫЙ НОМИТЕТ С ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТН ОПИСАНИЕ ИЗОБРЕТЕНИЯ МУ СВИДЕТЕЛЬСТ Н АВТО вым входом элемента ИЛИ 1 -го узлакоммутации каждого блока сравнения,выход элемента ИЛИ 1 -го узла коммутации каждого .блока сравненияподключен к вторым входам элементовИ 1 -го узла коммутацги, выходя первого и второго элементов И-го узла коммутации 1 -го блока сравнениясоединен с 1 -ми входами первого ивторого элементов ИЛИ узла связисоответственно 1 -го блока соавнения, выходя пеового и второгоэлеглентон ИЛИ узла связи 1 -го блокасоавнения подключены к первым входам первого и второго элементовИ соответственно схемы сравнения-го блока сравнения и первым ивторым выходам переносов соответственно-го блока сранненич, первый и второй входы переносов- гоблока сравнения подключены к вторяглвходам первого и второго элементовИ схемы сравнения 1 -го блока сравнения, выходы первого и второгоэлементов И схемы сравнения-гоблока сравнения соединены с входамиустановки в единичное состояниепервого и второго триггеров схемысравнения-го блока сравнения, инверсные выходя первого и второготриггеров схемы сравнения-го блока сравнения,подключены к входамтретьего элемента И схемы сравнения,выход третьего элемента И схемы сравнения соединен с третьими входамипервого и второго элементов И схемысравнения 1 -го блока сравнения,прямой выход перного триггера схемысравнения 1 -го блока сравнения подключен к второму входу первого элемента И -го блока сравнения, прямой выход второго триггера схемысравнения соединен с первым няходомблокировки-го блока сравнения,первый управляющий вход-го блокасравнения подключен к третьему входупервого элеглента И-го блока сраввидетельств С) 06 Г 7/021059563 иения, выход первого элемента И"го узла коммутации-го блокасравнения соединен с-м информационным .выходом-го блока сравнения, о т л и ч а ю щ е е с я тем,что с целью расширения его функциональных возможностей путем обеспечения выделения локально-минимальных значений чисел, в каждый блоксравнения введены элемент ИЛИ и второй элемент И, причем второй выход блокировки-го блока сравнениясоединен с вторым управляющим входом+ 1 -го блока сравнения, второйвход опроса устройства соединен спервым входом второго элемента И-го блока сравнения, выход второгоэлемента И-го блока сравненияподключен к второму адресному выходуИзобретение относится к автоматике и вычислительной технике и может быть использовано при реализации технических средств для выделения локальных экстремумов из множества сравниваемых чисел,Известно устройство для выделения экстремального из пш-разрядных двоичных чисел, содержащее пш-разрядных регистров пса узлов анализа, 1 О состоящих из трех элементов И, П дополнительных триггеров, группы элементов И-НЕ,.И, группу элементов ИЛИ. Выделение экстремального числа в устройстве производится поразрядным 5 сравнением по сигналам, Формируеыым по Окончании сравнения в данном разряде или если во всех триггерах данного разряда содержится одинаковая инФормация все нули или все единицы) ИНедрстатком такого устройства являются узкие Функциональные возможности.Наиболее близким техническим реше- р 5 нием к изобретению является устройство для выделения экстремальных чисел, содержащее п узлов сравнения, причем выход блокировки каждого-го узла сравнения, где= 1,2,п, ЗО соединен с управляющим входом+ + 1) -го узла сравнения, первый и второй Выходы переносов каждого-го узла сравнения подключены к первому и Второму Входам:переносОВ- 1)-го узла сравнения, вход опроса устройства соединен с первым входом элемента И каждого узла сравнения, выход элемента И каждого 1 -го узла сравнения подключен к 1 -му адрес -го блока сравнеыия, инверсныйвыход первого триггера схемч сравнения-го блока сравнения соединенс вторым входом, второго элемента И-го блока сравнения, инверсный выход второго триггера схемы сравнения1-го блока сравнения соединен с вто рым выходом блокировки-го блокасравнения;, второй управляющий вход-го блока сравнения подключен ктретьему входу второго элемента Иэтого блока сравнения, выходы первогои второго элементов И-го блокасравнения подключены к входам элемента ИЛИ того же блока сравнения,Выход элемента ИЛИ .-го блока сравнения соединен с вторыми входамиэлементов ИЛИ всех узлов коммутации-го блока сравнения,аному выходу устройства, каждый узел сравнения содержит регистр, элемент И.и узел связи, состоящий из двух элементов ИЛИ, п узлов коммутации, состоящих из элемента ИЛИ и двух элементов И, и схему сравнения, которая состоит из двух триггеров и трех элементов И, причем прямой и инверсный выходы каждого-го разряда регистра, где= 1,2в (Ь - количество разрядов в сравниваемых числах), соединены с первыми входами первого и второго элементов И соответственно-го узла коммутации, выход элемента И каждого-го узла сравнения подключен к первому входу элемента ИЛИ каждого узла коммутации-го узла сравнения, каждый -й вход тактовых сигналов устройства соединен с вторым входом элемента ИЛИ-го узла коммутации всех узлов сравнения, выход элеМента ИЛИ каждого-го узла коммутации подключен к вторым входам элементов И -го узла коммутации, выход первого и второго элементов И каждого-го узла коммутации каждого-го узла сравнения соединен с 1 -м входом первого и второго элемента ИЛИ узла связи .соответственно-го узла сравнения, выходы первого и второго элементов ИЛИ узла связи каждого 1 -го узла сравнения подключены к первым входам первого и второго элементов И соответственно схемы, сравнения -го узла сравнения, выходы первогои второго элементов ИЛИ узла связи -го узла сравнения соединены с вторым и первым выходами переносов соответственно-го узла сравнения,40 первый и второй входы переносов каждого-го узла сравнения подключены к вторым входам первого и второго элементов И схемы сравнений ( -го узла сравнения, выходы первого и второго элементов И схемы сравнения 5 каждого 1 -го узла сравнения соединены с входами установки в единичное состояние первого и второго триггеров схемы сравнения 1 -го. узла сравнения, инверсные выходы первого и вто 10 рого триггеров схемы сравнения в каждом из узлов сравнения подключены к входам третьего элемента И схемы сравнения, выход которого соединен с третьими входами первого.и второго элементов И схемы сфавнения, прямой выход первого триггера схемы сравнения-го узла сравнения под" ключен к второму входу элемента И-го узла сравнения, прямой выход второго триггера схем сравнения соединен с выходом блокировки с -го узла сравнения, управляющий вход каждого-го узла сравнения подключен к третьему входу элемента И -го узла сравнения, выход первого элемента И каждого-го узла коммутации каждого-го узла сравнения соединен с 1 -м информационным выходом -го узла сравнения (2 .Недостаток известного устройства также обусловлен узкимо.Функциональными возможностями.Цель изобретения - расширение Функциональных воэможностей устройства путем обеспечения выделения 35 локально-минимальным значений чисел.Поставленная цель достигается тем, что в устройство для выделения экстремальных чисел, содержащее и блоков сравнения ( и - количество сравниваемых чисел ),каждый из которых содержит регистр, первый элемент И, узел связи, состоящий из первого и второго элементов ИЛИ, и узлОВ коммутации ( я - число Раз рядов сравниваемых чисел), каждый из которых состоит из первого и второго элементов И и элемента ИЛИ, и схему сравнения, состоящую из первого и второго триггеров, первого, второго и третьего элементов И, причем первый выход блокировки каждого 1 -го блока сравнения (1 = 1,2, ,п соединен с первым управляющим входом (ф + Ц -го блока сравнения, первый и второй выходы переносов каждого 1 -го блока сравнения подключены к первому и второму входам переносов ( -1)-го блока сравнения, первый вход опроса устройства соединен с,первыми входами пер вых элементов И каждого блока сравнения, выход элемента И- го блока сравнения подключен к первому адресному выходу-го блока сравнения, прямой и инверсный выходы 3 -го раз ряда регистра 1 = 1,2. в) каж дого блока сравнения соединены с первыми входами первого и второго элементов И соответственно-го узла коммутации,-й вход тактовых сигналов устройства соединен с первым входом элемента ИЛИ -го узла коммутации каждого блока сравнения, выход элемента ИЛИ-го узла коммутации каждого блока сравнения. .подключен к вторьж входам элементов И-го узла коммутации, выходы первого и второго элементов И-го узла коммутации-го блока сравнения соединены с-ми входами первого и второго элементов .ИЛИ узла связи соответственно ( -го блока сравнения, выходы первого и второго элементов ИЛИ узла связи 1 -го блока сравнения подключены к первым входам первого и второго элементов И соответственно схемы сравнения 1 -го блока сравнения и к первым и вторым выходам переносов соответственно-го блока сравнения, первый и второй ъход переносов-го блока сравнения подключены к вторым входам первого и второго элементов И схемы сравнения -го блока сравнения, выходы первого и второго элементов И схемою сравнения 1-го блока сравнения соединены с входами установки в единичное состояние первого и. второго триггеров схеьы сравнения 1 -го блока сравнения, инверсные выходы первого и второго триггеров схемы сравнения-го блока сравнения подключены к входам третьего элемента И схемы сравнения, выход третьего элемента И схемы сравнения соединен с третьими входами первого и второго элементов И схемы сравнения-го блока сравнения, прямой выход первого триггера схеьн сравнения-го блока сравнения подключен к второму входу первого элемента И, -го блока сравнения, прямой выход второго триггера схемы сравнения соединен с первым выходом блокировки-го блока сравнения, первый управляющий вход-го блока сравнения подключен к третьему входу первого элемента И-го блока сравнения, выход первого элемента И, -го узла коммутации-го блока сравне-ния соединен с-м инФормационным выходом-го блока сравнения, в каждый блок сравнения введены элемент ИЛИ и второй элемент И, причем второй выход блокировки-го блока сравнения соединен с вторым управ,ляющим входом ( + Ц -го блока сравнения, второй вход опроса устройства соединен с первым входом второ,го элемента И. 1 -го блока сравнения, выход второго элемента И-го блока сравнения подключен к второму адресному выходу-го блока сравнения, инверсный выход первого триггерасхемы сравнения-го блока сравнения соединен с вторым входом второго элемента И-го блока сравнения,инверсный выход второго триггерасхемы сравнения -го блока сравнениясоединен с, вторым выходом блокировки-го блока сравнения, второй управляющий вход-го блока сравнения подключен,к третьему входу второго элемента И этого блока сравнения, выходы первого и второго элементов И-го. блока сравнения подключены к входам элемента ИЛИ тогоже блока сравнения, выход элементаИЛИ-го блока сравнения соединенс вторыми входами элементов ИЛИ всехузлов коммутации-го блока сравнения.Такое выполнение позволяет выделять наряду,с локально-максимальными значениями локально-минимальныезначения чисел,На чертеже приведена функциональная .схема устройства.Устройство содержит и блоков 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 до п, разояды чиселимеют текущий индекси пронумерованы слева направо от 1 до т (первый - старший, щ-й - младший).Устройство работает следующимобразом.В исходном состоянии все регистры 502 содержат нулевую информацию,первый 12 и второй 13 триггеры блока1 сравнения находятся в нулевомсостоянии.55Единичные .Уровни с инверсных выходов триггеров 12 и 13 поступают на входы третьего элемента И 16 блока сравнения, а единичный уровень с выхода этого элемента подается на третьи входы элементов И 14 и 15 60 и открывает цепи прохождения сигналов сравнения. В силу перекрестного соединения выходов элементов ИЛИ 5 и б с выходами переносов в пределах каждого блока 1 сравнения на элемен те И 14 сравниваюТся сигналы с прямого выхрда-го разряда регистра 2-го блока 1 сравнения и с инверсного выхода 1 -го разряда регистра 2 (+ 1) -го блока 1 сравнения, а на элементе И 15 - с инверсного выхода-го разряда регистра 2-го блока 1 сравнения и прямого выходатого же разряда регистра 2 ( + 1) -го блока сравнения.Сравнение всех разрядов происходит одинаково по тактовым сигналам единичного уровня.В регистры 2 блоков 1 сравнения принимаются двоичные числа. Первый тактовый сигнал с входа 18 подается через элемент ИЛИ 8 на вторье входи элементов И 9 и 10 первого узла 7 коммутации всех блоков 1 сравнения и открывает цепи прохождения сигналов с прямого и инверсного выходов первого разряда всех регистров соответственно через элементы ИЛИ 5 и б на первые входы элементов И 14 и 15 схемы 11 сравнения.Если в первом разряде регистров -го и ( + 1)-го блоков сравнения содержатся соответственно "1" и фОф, то на обоих входах первого элемента И 14-й схемы 11 сравнения будут сигналы единичного уровня, а на обоих входах второго элемента И 15 этой схемы - сигналу нулевого уровня. В единичное состояние установится первый 12 триггер-й схемы сравнения. Нулевой уровень с инверсного выхода этого триггера подается на вход третьего элемента И 16, и нулевой уровень с его выхода, поданный на третьи входы элементов . И 14 и 15, разрывает цепь прохождения сигналов через первый 14 и второй 15 элементы И-й схемы сравнения. Сравнение-го и ( 1 + 1)-го значений чисел на этом заканчивается.Если в первом разряде регистров 1-го и ( + 1) -го блоков сравнения содержатся соответственно 1 й" и 11", то в единичное состояние установится второй триггер 13-й схемы сравнения, Сравнение-го и (+ 1) -го чисел на этом тоже заканчивается.Если в первом разряде регистров -го и (. + 1)-го блоков сравнения содержится одинаковая информация, то на первом и втором входах элементов И 14 и 15 будут сигналы разного уровня. Следовательно, на входах этих элементов будет нулевой уровень и триггеры 12 и . 13-й схемы 11 сравнения останутся в исходном состоянии. Сравнение чисел будет продолжено в следующих разрядах.После окончания сравнения последнего щ-го разряда чисел на вход1059563 1 У 74 ИИПИ Заказ 9841/52 Тираж 706 сн л ППП "Патентф, г.ужгород,ул.Проектна 20 опроса подается сигнал единичного уровня, который поступает на первый вход элементов И 3 всех блоков сравнения. На выходе элемента И 3-го блока сравнения сигнал единичного уровня будет в случае, когда на втором и третьем его входах будет единичный уровень, Этосоответствует состоянию первого 12 и второго 13 триггеров ( - 1)-го блока сравнения "Оф и ф 1 ф и состоянию триггеров 12 и 13-го блока сравнения ф 1" и фОф, т.е. наличию .локального максимума в регистре-го блока сравнения. Единичный уровень с выхода элемента И 3, поданный через элемен ИЛИ 23 и первый вход элемента ИЛИ 8 всех узлов 7 коммутации-го блока 1 сравнения, разрешает считывание значения локально-максимального числа с информационных выходов 17 Единичный уровень на адресном выходе 21 устройства указывает положение локального максимума.Сигнал единичного уровня, поданный на второй вход 22 опроса, поступает на первый вход вторых элеменстов И 24 всех блоков 1 сравнения.На выходе элемента И 24-го блока 1сравнения сигнал единичного уровнябудет, когда состояние первого 12 ивторого 13 триггеров ( -1.-го и .-го 5 блока 1 сравнения будут соответственно ф 1", фО" и фОф, ф 1", что указывает на наличие локального минимума в регистре 2 -го блока сравнения, Единичный уровень с выхода 10 второго элементаИ 24, поданныйчерез элементы ИЛИ 23 и 8 на всеузлы 7 коммутацииго блока сравнения, разрешает считывание локально-минимального числа с информа ционных выходов 17. Единичный уровень на втором адресном выходе 19устройства указывает положение локального минимума.Таким образом, устройство обеспечивает выделение из множествасравниваемых чисел наряду с локаль"но-максимальными локально-минимальных: значений чисел и определениеих положений. Это позволяет использовать устройство для выделенияэкстремальных чисел при цифровойобработке информации.