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

1 Изобретение относится к вычислительной технике и может быть исполь зовано в устройствах обработки спек ров сигналов, в устройствах распознавания образцов и др. и является усовершенствованием изобретения по авт.св. № 1049899. Цель изобретения - повьшение быс родействия устройства. На фиг. 1 представлена функционапьная схема устройства ранжирован экстремальных значеш-Ш; на фиг.2 функциональная схема, блока управления j на фиг.З - временные диаграммы работы блока управления (на фиг.За тактовые импульсы с генератора, на фиг.35 - на выходе переполнения счетчика рангов,на фиг.Зб- на выходе бло1йа сравнения; на фиг.З-ьна выходе блока управления, на фиг. .на другом вь1ходе блока управления, на- фиг,,3е - на очередном выходе бло управления). Устройство, ранжирования экстремальных значений (фиг.1) содержит. входную шину 1 данных, основной ре гистр 2, буферный регистр 3, первьш блок 4 сравнения, переключатель 5, блок б управления, генератор 7 тактовых импульсов, счетчик 8 рангов, первый элемент И 9, выходные шины 10, выход 11 конца цикла сравнения устройства, шину 12 начала работы устройства, второй элемент И 13, третий элемент И 14, формирователь 15 импульсов, элемент ИЛИ 16, дешиф ратор 17, четвертьд элемент И 18, регистр 19 порога, второй блок 20 сравнения. Блок 6 управления содержит первь . H:второй элементы И 21, 22, первый RS-триггер 23, счетный триггер 24, второй RS-триггер 25, первый и второй йЛемеиты: ИЛИ 26, 27,входы 28-31 выходы 32-35. Назначение элементов устройства следующее... . . Основной регистр 2 служит для хранения набора из N чисел В (i 1,2,...,N), расположенных по порядку их величины, а также для сдви га, например, слева направо всех хранимых там чисел. Буферный регист 3 служит для временного запоминания сдвигаемых с крайней правой (старшей) ячейки основного регистра 2 хранимых чисел, первьш блок 4 сравнения - для сравнения чисел В с вы 4 хода буферного регистра 3 с числами А., поступающими на входную шину 1 данных. Переключатель 5 служит для мультиплексирования на информационньй вход основного регистра 2 чисел либо с входной шины 1, либо с выхода буферного регистра 3, либо с выхода крайней правой ячейки регистра 3. Блок 6 управления служит .для выработки управляющих сигналов для элементов устройства, генератор 7 тактовых импульсов - для формирования импульсов синхронизации. Счетчик 8 рангов служит для формирования ранга R- соответствующего каждому числу В-, сдвигаемому в основном регистре 2 на выходные шины 10, Первый элемент И 9 служит для клапанирования тактовых импульсов с выхода генератора 7 на тактовые входы основного регистра 2, регистр 19 - для хранения числа, соответствующего низшему рангу R.,, из всех чисел, хранимых в основном ре- гистре 2. Дешифратор 17 служит для дешифрации низшего ранга - кода максимального числа N в счетчике 8 рангов, четвертый элемент И 18 для выработки сигнала записи информации в регистр 19 порога с выхода переключателя 5 при условии, что в основном регистр 2 в такте будет записываться наименьшее число (низшего ранга). Блок 20 сравнения служит для выработки сигнала о результате сравнения для второго и третьего элементов И 13, 14 чисел, поступающих с входной шины 1 А:, и наименьшего числа А , хранш юго в регистре 2 и записанного в регистр 19 порога. Причем при превышении числом A.J с входной шины 1 числа, хранимого в регистре 19 порога, на выходе второго блока 20 сравнения появляется разрешающий потенциал по второму входу второго элемента И 13 и запрещающий для третьего элемента И 14, поскольку по второму входу последнего производится инверсия этого сигнала. Элементы И 13, 14, формирователь 15, элемент ИЛИ 16 служат для выработки сигнала запуска блока 6 управления, спгнал,ч обнуления счетчика 8 рангов, л также для формирования сигнала конца цикла сравнения по шине 11, Исполнение элементен устроГютва может быть, например, следукччео.

Оснопной регистр 2, наприме р, выполнен на базе микросхем 505ИР6, а Gyфернг.пЧ регистр 3 и регистр 19 порога - на базе микросхемы 155 ИР 13.

Блоки 4 и 20 сравнения выполнены на базе 4-разрядной схемы сравнения К561ИП2. Формирователь 15 представляет собой одновнбратор выполненный на базе микросхем К155АГЗ. Генератор 7 тактовых импульсов выполнен на баз 155АГЗ по схеме мультивибратора по типовой схеме. Дешифратор 17 может быть выполнен на многовходовом элементе И для дешифрации единичного состояния всех разрядов счетчика 8 рангов, соответствующего младшему рангу. Остальные элементы устройства элемент 1ШН, элемент И являются типо выми в цифровых интегральных сериях К155, К561 и т.д. Первая входная шина 1 служит для ввода в устройство анализируемых чисел А;. Выходные шины 10 служат для вывода чисел В. и соответствующего им ранга R (порядкового номера) при работе устройства. Выход 11 конца цикла сравнения служит для выдачи сигнала об окончании анализа одного числа А;. Шина 12 начала работы служит для ввода пускового импульса при анализе последующего числа А;. . Устройство работает следующим образом. ;В исходном состоянии все регистры и счетчик 8 рангов устройства обнулены (цепи сброса не показаны). На шину 1 входных данных поступает анализируемое число AI. Далее пусковой .импульс поступает на шину 12, а именно на первые входы второго и третьего элементов И 13, 14. Посколь ку регистр 19 порога обнулен, а поступившее число А О, то на выходе второго блока 20 сравнения находится единичный потенциал. Сработает второй элемент И 13 и по выход ному импульсу последнего блок 6 уп,равления по своему первому выходу 35 включает элемент И 9, который .разрешает прохождение тактовых импульсов от генератора 7 на тактовые входы основного регистра 2, буферного регистра 3 и на второй вход четвертого элемента И 18. При каждо тактовом импульсе число В. с выхода регистра 2 записывается в регистр 3 и с выхода регистра 3 поступает в блок 4 сравнения, где производится

операция сравнения двух чисел; поступиБшего с входа 1 числа Л- и числа В; с выхода регистра 3. Ксли А,|7 1 (внешен случае В О), то на выходе блока 4 сравнения появляется потенциал логической 1. Потенциал 1 на третьем входе 28 блока 6 управления вызывает появление на его третьем выходе 33 по тенциапа 1, по которому переключатель 5 разрешает прохождение информащш с входной шины 1, а именно числа А, на вход основного регистра- 2 вместо числа В 0. Па втором такте за числом А перепишется число с регистра 3, а по сигналу логической 1 на четвертом выходе 34 блока 6 управления происходит кольцевой сдвиг информации в регистре 2 (разрешение на третьем выходе 33 снимается). После (N-1) тактовых импульсов число А окажется в предпоследней справа на фиг. 1 ячейке регистра 2. Перед последним тактом сдвига и перезаписи информации в регистр 2 на выходе счетчика 8 рангов выставится число (1Ы). Счетчик 8 рангов при этом под|Считывает импульсы и после N-ro имт пульса на его выходе переполнения появляется импульс переполнения, поступающий на первьш вход элемента ИЛИ 16 и на четвертый вход 31 блока 6 управления. При поступлении этого импульса блок 6 управления прекращает выдачу разрешения на элемент И 9 на своем первом выходе 35, сдвиг информации в регистре 2 прекрасдается, TaKiiM образом, при поступлении последнего импульса на вход счетчика 8, на тактовый вход регистра 2 и второй вход четвертого элемента И 18 срабатывает дешифратор 17, выставив 1 на своем выходе, и происходит сдвиг вправо информации в регистре 2 и перезапись поступающего числа с переключателя 5 в регистр 19 порога по сигналу с выхода четвертого элемента И 18 и этого же числа в левую ячейку основного регистра 2. В результате в регистре 19 порога окажется число, соответствующее наинизшему рангу , хранящемуся в регистре 2. Поскольку в нашем слу чае все регистры вначале бьши обнулены, то после N тактовых импульсов число А, окажется в самой последней

(правой) ячейке регистра 2, а в остальных ячейках регистра 2 и в регисре 19 порога будет нулевая информаци С выхода элемента ИЛИ 16 импульс о переполнении счетчика 8 подается на выход 11 конца цикла, свидетельствуя о готовности устройства к.-анализу следующего А2.

На следующем цикле анализа,.если новое анализируемое число А А, то на время первого тактового интервала на третьем выходе 33 блока 6 управления появляется потенциал логической 1, которьш разрешает прохоисдение через переключатель 5 с входной шины 1 числа А2. Таким образом, на первом такте число А запишется в регистр 2. После этого на втором тактовом интервале разрешается прохождение информации А с буферного регистра 3 через переключатель 5. В основной регистр 2 вслед за числом Aj записывается число Аи далее после N тактовых импульсов в регистре окажется сначала число А , затем А и далее нули. Если второе анализируемое число ., то на выходе блока 4 сравнения будет потенциал логического О. При этом блок 6 управления выдает потенциал логической 1 по второму выходу 32, по которому переключатель 5 в этом случае пропускает на свойвыход информацию с третьего входа (в.ерхнего на фиг,1). Таким образом, основной регистр 2 получается замкнутым в кольцо, и число А с выхода регистра 2 перезаписывается на его вход, а следом за ним с входной шины 1 числр А2. В результате такого процесса за N циклов анализа (каждый по N тактовых импульсов) произойдет сортировка по величине чисел А,А ,..., , и в регистре 2 они окажутся расположенными по порядку величины и будут иметь обозначения В. . При работе устройства на выходных шинах 10 ка;кдому числу В будет соответствовать его порядко.вый номер (ранг) с выходо счетчика рангов. Перед записью в регистр 2 последнего по рангу К|у числа с выхода переключателя 5 срабатывает дешифратор 17 по коду последнего ранга, и с выхода дешифратора 17 на первый.вход четвертого элемен,та И 18 поступает единичньш потенциал. При поступлении последнего

тактового импульса в регистр 19 порога в крайнюю левую ячейку регистра 2 записывается сортируемое число A.j, соответствующее наинизшему рангу R.

Придальнейшей работе устройства при поступлении на вход 1 устройства последующего числа , на втором входе второго блока 20 сравнен и будет число А , которое и сравниваеся с вновь поступившим числом А. Если число А 7-А, то на выходе блока 20 сравнения находится единичный потенциал, а при поступлении по шине 12 пускового импульса последний стробйрует второй элемент И 13, и по его сигналу сбрасывается в О счетчик 8, а блок 6 управления по первому выходу 35 включает элемент И 9, который разрешает прохождение тактовых импульсов от генератора 7 на тактовые входы основного и буферного регистров 2 и 3. При этом сортировка будет происходить как и в предьщущих случаях. Если поступающее число , т.е. меньше самого малого числа, хранимого в основном регистре 2, то второй блок 20 сравнения на своем выходе выставит нулевой потенциал. Второй элемент И 13 блокируется, а третий элемент И 14 разблокируетс При подаче пускового импульса по шине 12 срабатьшает элемент И 14, а по концу этого импульса срабатывает формирователь 15, сигнал с которого через элемент ИЛИ 16 поступает на вход 11 конца цикла.

Импульс на выходе 11 устройствапри этом свидетельствует о готовности устройства к анализу следующего числа хотя запуска блока 6 управления не произошло, а сам цикл анализа поступившего числа сократился во времени с N тактовых импульсов до длительности входного пускового импульса.

В дальнейшем все поступающие на входную шину 1 числа А; сравниваются с меньшим числом А, хранимым в регистре 2, а также.в регистре 19 порога, и в случае превьш1ения кода числа AJ кода числа в регистре 19 порога (А-7/ А„) по сигналу с выхода элемента И 13 производится запуск устройства на цикл анализа, длщегося N тактовых импульсов. В результате работы устройства на первых циклах анализа происходит сортировка по величине чисел А A2,...,Aj, и в регистре 2 они жутся по порядку величины. При последующем ранжировании чисел вновь поступающее число вклинивается согласно своему рангу в последовательность N чисел В ,В ,.. . ,Bjij, (хранимых в основном регистре 2,и последнее (N+1)-e число Б оказывается в буферном регистре 3, а так как это число оказалось меньшим по величине, то она отбрасывается, ибо после N-ro тактового импульса буферный регистр 3 исключается из коль ца. При дальнейшей работе устройства в регистре 2 будут накапливаться тол ко самые большие по величине (экстре мальные) числа, расположенные по порядку величины. Работа блока 6 (фиг.З) происходит следующим образом. Пусковой импульс с шины 12 посту пает на вход 30, устанавливает RSтриггер 25 в состояние 1 по прямому выходу, а RS-триггер 15 и счетньй триггер 24 через элементы ИЛИ 26 и 27 - в состояние О по входам R, Прямой выход RS-триггера 25 является выходом 35 блока 6 и поступает затем на элемент И 9. На инверсных выходах RS-триггера 23 и счетного триггера 24 устанавливается потенциал логичес кой 1. Таким образом, на всех вхо- дах элемента И 22 имеются логические 1, а на выходе 32 блока 6 также появится логическая 1 (фиг.Зе). Эт соответствует режиму работы устройства ранжирования с замкнутым в коль до регистром 2. . 24S Если блок 4 сравнения выдает на к-м тактовом импульсе потенциал логической 1 (Aj В, фиг.Зг), то этот потенциал через вход 28 -блока 6 поступает на первый вход элемента ; И 21, на втором входе которого к этому времени находился потенциал логической 1 с инверсного выхода счетного тригге ра 24, поэтому на выходе элемента И 21 появляется потенциал логической 1 и устанавливает RSтриггер 23 в состояние 1 по прямому выходу. Эта 1 поступает на выход 33 блока 6 (фиг.Зг). На вход 29 блока 6 поступают тактовые импульсы с генератора 7 (фиг.Зч). Первый же импульс после срабатывания триггера 23(т.е. (к+1)-й по счету) через элемент ИЛИ 26 по R-входу возвращает триггер 23 снова в состояние О по прямому выходу. Положительный перепад напряжения с инверсного выхода триггера 23 при этом запускает по счетному входу триггер 24 и переводит его в состояние логической 1 по прямому выходу, который является выходом 34 блока 6 управления (фиг.3d). В этом состоянии триггер 24находится до поступления импульса переполнения счетчика 8 рангов по входу 31 блока 6, которым устанавливается в нулевое состояние как триггер 24 (через элемент ИЛИ 27), так и триггер 25. Выход 11 конца цикла сравнения и шина 12 начала работы могут быть перемкнуты между собой. В этом случае устройство ранжирования переходит в непрерывный автономный режим и его темп работы определяется только частотой импульсов генератора 7 (фиг.2).

J Л 5

J5

УСТРОЙСТВО РАНЖИРОВАНИЯ . ЭКСТРЕ11АЛЫ1ЫХ ЗНАЧЕНИЙ по авт.с18. № 1049899, отличающееся тем, что, с целью повьшения быстродействия, в него введены второй, третий и четвертый элементы И, формирователь импульсов, элемент ИЛИ, деишфратор, регистр порога и второй блок сравнения, первая группа входов которого соединена с шиной входных данных устройства, вторая группа входов - с выходами разрядов регистра порога, а выход подключен к управляющим входам второго и третьего элементов И информационные входы которых соединены с шиной начала работы устройства, выход второго элемента И подключен к первому входу блока управления, выход третьего элемента И через формирователь импульсов соединен с первым входом элемента ИЛИ, второй вход которого подключен к выходу переполнения счетчика рангов, выход элемента ИЛИ является выходом конца цикла сравнения устройства, выходы счетчика рангов соединены с входами дешифратора, выход которого с соединен с первым входом четвертого & элемента И, второй вход которого под(Л ключен к выходу первого элемента И, с а выход соединен с входом разрешения записи регистра порога, информационньй вход которого соединен с выходом переключателя. о 00 ю 4

.2

.3