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

(51)4 С Об Г 7/02 ПИСАНИЕ ИЗОБРЕТЕ етьего элеменоды которых работы уст ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССРВ 1049899, кл. С 06 Р 7/02, 1982.(54)(57) УСТРОЙСТВО РАНЖИРОВАНИЯ .ЭЕ(СТРЕЕЕАЛЬЕЕЕЕХ ЗНАЧЕЕЕИЙ по авт. св.В 1049899, о т л и ч а ю щ е е с ятем, что, с целью повьпвения быстродействия, в него введены второй,третий и четвертый элементы И, формирователь импульсов, элемент ИЛИ, деюифратор, регистр порога и второйблок сравнения, первая группа входовкоторого соединена с ниной входныхданных устройства, вторая группа входов - с выходами разрядов регистрапорога, а выход подключен к управляю-. ЯО 1168924 щим входам второго и ов И, информационные оединены с щиной нач роиства, выход второго элемента Иподключен к первому входу блока управления, выход третьего элемента И через формирователь импульсов соединенс первым входом элемента ИЛИ, второйвход которого подключен к выходупереполнения счетчика рангов, выходэлемента ИЛИ является выходом конца цикла сравнения устройства, выходы счетчика рангов соединены с входами дешифратора, выход которогосоединен с первым входом четвертогоэлемента И, второй вход которого подключен к выходу первого элемента И,а выход соединен с входом разрешения записи регистра порога, информационный вход которого соединен свыходом переключателя.Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки спектров сигналов, в устройствах распознавания образцов и др, и является 5усовершенствованием изобретения поавт.св. У 1049899,Цель изобретения - повышение быстродействия устройства.На фиг, 1 представлена функцио-. 10нальная схема устройства ранжированияэкстремальных значений; на фиг,2 -функциональная схема блока управления; на фиг,З " временные диаграммыработы блока управления (на фиг,За - 15тактовые импульсы с генератора,на фиг.З б - на выходе переполнениясчетчика рангов,на фиг.З б - на выходе блока сравнения; на фиг.З-на выходе блока управления, на фиг.Зд 20.на другом выходе блока управления,на фиг,3 е - на очередном выходе блокауправления),Устройство ранжирования экстре"мальных значений (Фиг.1) содержит 25входную шину 1 данных, основной регистр 2, буферный регистр 3, первыйблок 4 сравнения, переключатель 5,блок 6 управления, генератор 7 тактовых импульсов, счетчик 8 рангов, ЗОпервый элемент И 9, выходные шины10, выход 11 конца цикла сравненияустройства, шину 12 начала работыустройства, второй элемент И 13,третий элемент И 14, формирователь15 импульсов, элемент ИЛИ 16, дешифратор 1, четвертый элемент И 18,регистр 19 порога, второй блок 20сравнения,Блок 6 управления содержит первый дон второй элементы И 21, 22, первый1 Б-триггер 23, счетный триггер 24,второй 28-триггер 25, первый и второй элементы ИЛИ 26, 27,входы 28-31,выходы 32-35. 453Назначение элементов устройстваследующее.. Основной регистр 2 служит дляхранения набора из И чисел Б,.(11,2И), расположенных по по орядку их величины, а также для сдвига, например, слева направо всеххранимых там чисел. Буферный регистр3 служит для временного запоминаниясдвигаемых с крайней правой (старшей) ячейки основного регистра 2хранимых чисел, первый блок 4 сравнения - для сравнения чисел В с вы" хода буферного регистра 3 с числамиА., поступающими на входную шинуданных, Переключатель 5 служит длямультиплексирования на информационный вход основного регистра 2 чиселлибо с входной шины 1, либо с выхода буферного регистра 3, либо свыхода крайней правой ячейки регистра 3. Блок 6 управления служит длявыработки управляющих сигналов дляэлементов устройства, генератор 7тактовых импульсов - для формирования импульсов синхронизации,Счетчик 8 рангов служит дляформирования ранга к соответствующего каждому числу Б , сдвигаемому7в основном регистре 2 на выходныешины 10, Первый элемент И 9 служитдля клапанирования тактовых импульсов с выхода генератора 7 на тактовые входы основного регистра 2, регистр 19 - для хранения числа, соответствующего низшему рангу Й , извсех чисел, хранимых в основном регистре 2. Дешифратор 17 служит длядешифрации низшего ранга - кодамаксимального числа И в счетчике 8рангов, четвертый элемент И 18 -для выработки сигнала записи инФормации в регистр 19.порога с зыхода переключателя 5 при условии,что в основном регистр 2 в тактебудет записываться наименьшее число(низшего ранга). Блок 20 сравненияслужит для выработки сигнала о результате сравнения для второго итретьего элементов И 13, 14 чисел,поступающих с входной шины 1 А , инаименьшего числа А , хранимого внфрегистре 2 и записанного в регистр19 порога. Причем при превышениичислом А с входной шины 1 числа,хранимого в регистре 19 порога, навыходе второго блока 20 сравненияпоявляется разрешающий потенциалпо второму входу второго элементаИ 13 и запрещающий для третьего элемента И 14, поскольку по второмувходу последнего производится инверсия этого сигнала. Элементы И 13,14, формирователь 15, элемент ИЛИ 16служат для выработки сигнала запуска блока 6 управления, сигнала обнуления счетчика 8 рангов, а такжедля формирования сигнала конца цикласравнения по шине 11,Исполнение элементов устройстваможет быть, например, следунчн.е.3 1168 Основной регистр 2, например, выпол- нен на базе микросхем 505 ИР 6, а буферьип регистр 3 и регистр 19 порога - на базе микросхемы 155 ИР 13.Блоки 4 и 20 сравнения выполнены на базе 4-разрядной схемы сравнения К 561 ИП 2. Формирователь 15 представляет собой одновибратор выполненный на базе микросхем К 155 АГЗ. Генератор 7 тактовых импульсов выполнен на базе О 155 АГЗ по схеме мультивибратора по типовой схеме. Дешифратор 17 может быть выполнен на многовходовом элементе И для дешифрации единичного состояния всех разрядов счетчика 8 5 рангов, соответствующего младшему рангу. Остальные элементы устройства: элемент ИЛИ, элемент И являются типовыми в цифровых интегральных сериях К 155, К 561 и т.д. 20Первая входная шина 1 служит для ввода в устройство анализируемых чисел А . Выходные шины 10 служат для вывода чисел В. и соответствующегоим ранга Р (порядкового номера) при 25 работе устройства. Выход 11 конца цикла сравнения служит для выдачи сигнала об окончании анализа одного числа А . Шина 12 начала работы служит для ввода пускового импульса при З 0 анализе последующего числа АУстройство работает следующим об-. разом..В исходном состоянии все регистры и счетчик 8 рангов устройства обну 35 лены (цепи сброса не показаны). На шину 1 входных данных поступает анализируемое число А . Далее пусковой импульс поступает на шину 12, а 1именно на первые входы второго и третьего элементов И 13, 14, Поскольку регистр 19 порога обнулен, а поступившее число АО, то на выходе второго блока 20 сравнения находится единичный потенциал. Срабо тает второй элемент И 13 и по выходному импульсу последнего блок 6 управления по своему первому выходу 35 включает элемент И 9, который .разрешает прохождение тактовых им пульсов от генератора 7 на тактовые входы основного регистра 2, буферного регистра 3 и на второй вход четвертого элемента И 18. При каждом тактовом импульсе число В. с выхода 55 регистра 2 записывается в регистр 3 и с выхода регистра 3 поступает в блок 4 сравнения, где производится 924операция сравнения двух чисел: поступившего с входа 1 числа А и числа В; с выхода регистра 3. Если А,) В (в нашем случае В, = О), то на выходе блока 4 сравнения появляется потенциал логической . Потенциал "1" на третьем входе 28 блока 6 управления вызывает появление на его третьем выходе 33 потенциала "1", по которому переключатель 5 разрешает прохождение информации с входной шины 1, а именно числа А , на вход основного регистр фра 2 вместо числа В = О.На втором такте за числом А пе 1 репишется число с регистра 3, а по сигналу логической "1" на четвертом выходе 34 блока 6 управления происходит кольцевой сдвиг информации в регистре 2 (разрешение на третьем выходе 33 снимается), После (1-1) тактовых импульсов число А окажется в предпоследней справа на фиг. 1 ячейке регистра 2, Перед последним тактом сдвига и перезаписи информации в регистр 2 на выходе счетчика 8 рангов выставится число (1-1) .Счетчик 8 рангов при этом подсчитывает импульсы и после М-го им-, пульса на его выходе переполнения появляется импульс переполнения, поступающий на первьп вход элемента ИЛИ 16 и на четвертый вход 31 блока 6 управления. При поступлении этого импульса блок 6 управления прекращает выдачу разрешения на элемент И 9 иа своем нервом выходе 35, сдвиг информации в регистре 2 прекращается. Таким образом, при поступлении последнего импульса на вход счетчика 8, на тактовый вход регистра 2 и второй вход четвертого элемента И 18 срабатывает дешиФратор 17, выставив " 1" на своем выходе, и происходит сдвиг вправо информации в регистре 2 и перезапись поступаощего числа .с переключателя 5 в ре,гистр 9 порога по сигналу с выхода четвертого элемента И 18 и этого же числа в левую ячейку основного регистра 2, В результате в регистре 9 порога окажется число, соответствующее наинизшему рангу 1 хранящемуся в регистре 2. Поскольку в нашем слу.чае все регистры вначале были обнулены, то после 1 тактовых импульсов число А окажется в самой последней(правой) ячейке регистра 2, а в остальных ячейках регистра 2 и в регистре 19 порога будет нулевая информация. С выхода элемента ИЛИ 16 импульс о переполнении счетчика 8 подается на выход 11 конца цикла, свидетельствуя о готовности устройства к:анализу следующего чиСла А 2.На следующем цикле анализа,. если 1 О новое анализируемое число А 3 А1 ф то на время первого тактового интервала на третьем выходе 33 блока 6 управления появляется потенциал логической "1, который разрешает про хождение через переключатель 5 с входной шины 1 числа А, Таким образом, на первом такте число А запишется в регистр 2. После этого на втором тактовом интервале разрешает ся прохождение информации А с буферного регистра 3 через переключатель 5. В основной регистр 2 вслед за числом А записывается число А и1 далее после И тактовых импульсов в 25 регистре окажется сначала число АФ затем Аи далее нули. Если второе анализируемое число А( А , то на1 ф выходе блока 4 сравнения будет потенциал логического "0". При этом блок 30 6 управления выдает потенциал логической п 1 п по второму выходу 32, по которому переключатель 5 в этом случае пропускает на свойвыход информацию с тРетьего входа (верхнего 35 на Фиг.1). Таким образом, основной регистр 2 получается замкнутым в кольцо, и число А с выхода регистра 2 перезаписывается на его вход, а следом за ним с входной шины 1 40 число А . В результате такого процесса за И циклов анализа (кащый по И тактовых импульсов) произойдет сортировка по величине чисел А 1,А 2 ф ф Аи, и в регистре 2 Они окажутся 45 расположенными по порядку величины и будут иметь обозначения В, При работе устройства на выходных шинах 10 каждому числу В, будет соответствовать его порядковый номер (ранг) Кс выходов 50 счетчика рангов, Перед записью в регистр 2 последнего по рангу Е чис-М ла с выхода переключателя 5 срабатывает дешифратор 17 по коду послед-него ранга, и с выхода дешифратора 55 17 на первый. вход четвертого элемен,та И 18 поступает единичный потея" циал. При поступлении последнего тактового импульса в регистр 19 порога в крайнюю левую ячейку регистра 2 записывается сортируемоечисло А , соответствующее наинизшему райгу Е.При дальнейшеи работе устройства при поступлении на вход 1 устройства последующего числа Ач,на втором входе второго блока 20 сравнениябудет число А, которое и сравнивает.ся с вновь поступившим числом АЕсли число А А , то на выходей 1 пфблока 20 сравнения находится единичный потенциал, а при поступлении пошине 12 пускового импульса последний стробирует второй элемент И 13,и по его сигналу сбрасывается в"Оп счетчик 8, а блок 6 управленияпо первому выходу 35 включает элемент И 9, который разрешает прохождение тактовых импульсов от генератора 7 на тактовые входы основногои буферного регистров 2 и 3. Приэтом сортировка будет происходитькак и в предыдущих случаях. Еслипоступающее число А А, т,е.Именьше самого малого числа, хранимого в основном регистре 2, то второй блок 20 сравнения на своем выходе выставит нулевой потенциал.Второй элемент И 13 блокируется,а третий элемент И 14 разблокируется.При подаче пускового импульса пошине 12 срабатывает элемент И 14,а по концу этого импульса срабатывает формирователь 15, сигнал скоторого через элемент ИЛИ 16 поступает на вход 11 конца цикла.Импульс на выходе 11 устройствапри этом свидетельствует о готовнос"ти устройства к анализу следующегочисла А 1 , хотя запуска блока 6управления не произошло, а сам цикланализа поступившего числа сократился во времени с И тактовых импульсов до длительности входногопускового импульса,В дальнейшем все поступающие навходную шину 1 числа А сравниваются с меньшим числом А, хранимым врегистре 2, а также.в регистре 19порога, и в случае превышения кодачисла А кода числа в регистре 19порога (АА ) по сигналу с выхо 1да элемента И 13 производится запуск устройства на цикл анализа, длящегося И тактовых импульсов.7 1168В результате работы устройствана первых циклах анализа происходитсортировка по величине чисел А,ААм, и в регистре 2 они окажутся по порядку величины. При5последующем ранжировании чисел вновьпоступающее число "вклинивается"согласно своему. рангу в последовательность М чисел В,В В 1,1 ф афхранимых в основном регистре 2,и . 1 Юпоследнее (И+1)-е число В оказывается в буферном регистре 3, а таккак это число оказалось меньшим повеличине, то Она отбрасывается, ибопосле И-го тактового импульса буферный регистр 3 исключается из кольца.При дальнейшей работе устройствав регистре 2 б"дут накапливаться толь.ко самые большие по величине (экстре мальные) числа, расположенные по порядку величины.Работа блока 6 (фиг.З) происходитследующим образом.Пусковой импульс с шины 12 посту 25пает на вход 30, устанавливает 8 триггер 25 в состояние "1" по прямому выходу, а ЕБ-триггер 15 и счетныйтриггер 24 через элементы ИЛИ 26 и27 - в состояние "О" по входам В.,30Прямой выход КЯ-триггера 25 являетсявыходом 35 блока 6 и поступает затемна элемент И 9. На инверсных выходахКБ-триггера 23 и счетного триггера24 устанавливается потенциал логической "1". Таким образом, на всех вхо45дах элемента И 22 имеются логические"1", а на выходе 32 блока 6 такжепоявится логическая "1" (фиг.Зе). Этосоответствует режиму работы устрой Оства ранжирования с замкнутым в коль.цо регистром 2,9248Если блок 4 сравнения выдает на к-м тактовом импульсе потнциал логической "1" (А 1 В , Фиг.30), то этот потенциал через вход 28 блока 6 поступает на первый вход элемента И 21, на втором входе которого к этому времени находился потенциал логи" ческой "1" с инверсного выхода счетного триггера 24, поэтому на выходе элемента И 21 появляется потенциал логической "1" и устанавливает КБ- триггер 23 в состояние "1" по прямому выходу. Эта "1" поступает на выход 33 блока 6 (фиг. 31). На вход 29, блока 6 поступают тактовые импульсы с генератора 7 (фигЗц). Первый же импульс после срабатывания триггера 23 (т.е. (к+1)-й по счету) через элемент ИЛИ 26 по К-входу возвращает триггер 23 снова в состояние "О" по прямому выходу. Положительный перепад напряжения с инверсного выхода триггера 23 при этом запускает по счетному входу триггер 24 и перево" дит его в состояние логической "1" по прямому выходу, который является выходом 34 блока 6 управления (фиг,ЗИ . В этом состоянии триггер 24 находится до поступления импульса переполнения счетчика 8 рангов по входу 31 блока 6, которым устанавливается внулевое состояние как триггер 24 (через элемент КПИ 27), , так и триггер 25.Выход 1", конца цикла сравнения и ,шина 12 начала работы могут быть перемкнуты между собой. В этом случае устройство ранжирования переходит в непрерывный автономный режим и его темп работы определяется только частотой импульсов генератора 7 (фиг.2).1168924 Составитель Е, ИваноТехред С.йовжий. Редак нк Подписноеного комитета СССРений и открытий5, Раушская наб., л аказ 4613/4 Ужгород, ул, Проектная, 4 Тираж 710 ПИИПИ Государствепо делам изобре 13035, Иосква, Ж филиал ППП "Патент орректор И, Самборск