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

 

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

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

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

РЕСПУБЛИК (>)4 G 06 F 7/02

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61) 1049899 (21) 3708 119/24-24 (22) 29.02.84 (46) 23.07.85. Бюл. Р 27 (72) А.Н. 21урашко (53) 681.325.3(088.8) (56) Авторское свидетельство СССР

В 1049899, кл. G 06 F 7/02, 1982. (54)(57) УСТРОЙСТВО РАНЖИРОВАНИЯ

ЭКСТРЕЙИЛЬНЫХ ЗНАЧЕНИЙ по авт.св.

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

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

1168924

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

Цель изобретения — повышение быстродействия устройства.

На фиг. 1 представлена функцио-. 10 нальная схема устройства ранжирования экстремальных значений; на фиг.2— функциональная схема блока управления; на фиг.3 — временные диаграммы работы блока управления (на фиг,3а — 1S тактовые иипульсы с генератора, на фиг.3 Б - на выходе переполнения счетчика рангов, на фиг.3 6 — на выходе блока сравнения; на фиг.3 a— на выходе блока управления, на фиг.3д2О

f .на другом выходе блока управления, на фиг,3 e — на очередном выходе блока управления).

Устройство ранжирования экстре" иальных значений (фиг.1) содержит входную шину 1 данных, основной регистр 2, буферный регистр 3, первый блок 4 сравнения, переключатель 5, блок 6 управления, генератор 7 тактовых импульсов, счетчик 8 рангов, 30 первый элемент И 9, выходные шины

10, выход 11 конца цикла сравнения устройства, шину 12 начала работы устройства, второй элемент И 13, третий элемент И 14, формирователь

15 импульсов, элемент ИЛИ t6, дешифратор 17, четвертый элемент И 18 регистр 19 порога, второй блок 20 сравнения.

Блок 6 управления содержит первый gg н второй элементы И 21, 22, первый

RS-триггер 23, счетный триггер 24, второй RS-триггер 25, первый и второй элементы ИЛИ 26, 27,входы 28-31, выходы 32-35. 45

Назначение элементов устройства следующее. . Основной регистр 2 служит для хранения набора из N чисел B,.(i

1,2,...,И), расположенных по порядку их величины, а также для сдвига, например, слева направо всех хранимых там чисел. Буферный регистр

3 служит для временного запоминания

I сдвигаемых с крайней правой (старшей) ячейки основного регистра 2 хранимых чисел, первый блок 4 сравнения — для сравнения чисел В. с выхода буферного регистра 3 с числами

А., поступающими на входную шину данных. Переключатель 5 служит для мультиплексирования на информационный вход основного регистра 2 чисел либо с входной шины 1, либо с выхода буферного регистра 3, либо с выхода крайней правой ячейки регистра 3. Блок 6 управления служит для выработки управляющих сигналов для элементов устройства, генератор 7 тактовых импульсов — для формирования импульсов синхронизации.

Счетчик 8 рангов служит для формирования ранга R. соответствую1 щего каждому числу Б, сдвигаеиоиу

7 в основном регистре 2 на выходные шины 10. Первый элемент И 9 служит для клапанирования тактовых импульсов с выхода генератора 7 на тактовые входы основного регистра 2, регистр 19 — для хранения числа, соответствующего низшему рангу Г, из всех чисел, хранимых в основном ре» гистре 2. Дешифратор 17 служит для дешифрации низшего ранга — кода максимального числа N в счетчике 8 рангов, четвертый элемент И 18— для выработки сигнала записи информации в регистр 19.порога с зы хода переключателя 5 при условии, что в основном регистр 2 в такте будет записываться наименьшее число (низшего ранга).. Блок 20 сравнения служит для выработки сигнала о результате сравнения для второго и третьего элементов И 13, 14 чисел, поступающих с входной шины 1 А., и наименьшего числа А, хранимого в н регистре 2 и записанного в регистр

19 порога. Причем при превышении числом А с входной шины 1 числа, хранимого в регистре 19 порога, на выходе второго блока 20 сравнения появляется разрешающий потенциал по второму входу второго элемента

И 13 и запрещающий для третьего элемента И 14, поскольку по второму входу последнего производится инверсия этого сигнала. Элементы И 13, t4 формирователь 15, элемент ИЛИ 16 служат для выработки сигнала запуска блока 6 управления, сигнала обнуления счетчика 8 рангов, а также для формирования сигнала конца цикла сравнения по шине 11.

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

3 1168

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

Блоки 4 и 20 сравнения выполнены на базе 4-разрядной схемы сравнения

К561ИП2. Формирователь 15 представляет собой одновибратор выполненный на базе микросхем К155АГЗ. Генератор

7 тактовых импульсов выполнен на базе !О

155АГЗ по схеме мультивибратора по типовой схеме. Дешифратор 17 может быть выполнен на многовходовом элементе И для дешифрации единичного состояния всех разрядов счетчика 8 !5 рангов, соответствующего младшему рангу. Остальные элементы устройства: элемент ИЛИ, элемент И являются типовыми в цифровых интегральных сериях

К155, К561 и т.д. 20

Первая входная шина 1 слуттг для ввода в устройство анализируемых чисел А . Выходные шины 10 служат для вывода чисел В. и соответствующего ! им ранга P. (порядкового номера) при 25 работе устройства. Выход 11 конца цикла сравнения служит для выдачи сигнала об окончании анализа одного числа A . Шина 12 начала работы слуj жит для ввода пускового импульса при З0 анализе последующего числа А + .

Устройство работает следующим об-. разом. .В исходном состоянии все регистры и счетчик 8 рангов устройства обну35 лены (цепи сброса не показаны). На шину 1 входных данных поступает анализируемое число А . Далее пусковой импульс поступает на шину !2, а

1 именно на первые входы второго и третьего элементов И 13, 14. Поскольку регистр 19 порога обнулен, а поступившее число A„ > О, то на выходе второго блока 20 сравнения находится единичный потенциал. Срабо- 45 тает второй элемент И 13 и по выходному импульсу последнего блок 6 управления по своему первому выходу

35 включает элемент И 9, который .разрешает прохождение тактовых им- 50 пульсов от генератора 7 на тактовые входы основного регистра 2, буферного регистра 3 и на второй вход четвертого элемента И 18. При каждом тактовом импульсе число В. с выхода 55 ! регистра 2 записывается в регистр 3 и с выхода регистра 3 поступает в блок 4 сравнения, где производится

924 операция сравнения двух чисел: поступившего с входа 1 числа А. и чис-! ла В; с выхода регистра 3. Если

А, ) В (в нашем случае В, = О), то на выходе блока 4 сравнения появляется потенциал логической "!".

Потенциал "1" на третьем входе 28 блока 6 управления вызывает появление на его третьем выходе 33 потенциала "1", по которому переключатель 5 разрешает прохождение информации с входной шины 1, а именно числа А, на вход основного регист11 ра 2 вместо числа В = О.

На втором такте за числом А пе1 репишется число с регистра 3, а по сигналу логической "1" на четвертом выходе 34 блока 6 управления происходит кольцевой сдвиг информации в регистре 2 (разрешение на третьем выходе 33 снимается). После (N-1) тактовых импульсов число А

1 окажется в предпоследней справа на фиг. 1 ячейке регистра 2. Перед последним тактом сдвига и перезаписи информации в регистр 2 на выходе счетчика 8 рангов выставится число (!! 1), Счетчик 8 рангов при этом подсчитывает импульсы и после N-го им-. пульса «а его выходе переполнения появляется импульс переполнения, поступающий на первый вход элемента

ИЛИ 16 и на четвертый вход 31 блока

6 управления. При поступлении этого импульса блок 6 управления прекращает выдачу разрешения на элемент

И 9 иа своем нервом выходе 35, сдвиг информации в регистре 2 прекращается.

Таким образом, при поступлении последнего импульса на вход счетчика

8, на тактовый вход регистра 2 и второй вход четвертого элемента

И 18 срабатывает дешифратор 17 выставив " 1" на своем выходе, и происходит сдвиг вправо информации в регистре 2 и перезапись поступающего числа с переключателя 5 в ре,гистр !9 порога по сигналу с выхода четвертого элемента И 18 и этого же числа в левую ячейку основного регистра 2. В результате в регистре 19 порога окажется число, соответствующее наинизшему рангу I, хранящемуся в регистре 2. Поскольку в нашем слу.чае все регистры вначале были обнуле ны, то после N тактовых импульсов число А окажется в самой последней

1168924 (правой) ячейке регистра 2, а в остальных ячейках регистра 2 и в регистре 19 порога будет нулевая информация.

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

На следующем цикле анализа,. если 10 новое анализируемое число Az А т то на время первого тактового интервала на третьем выходе 33 блока 6 управления появляется .потенциал логической "1, который разрешает про- f5 хождение через переключатель 5 с входной шины 1 числа А, Таким образом, на первом такте число А запишется в регистр 2. После этого на втором тактовом интервале разрешает- 20 ся прохождение информации А„ с буферного регистра 3 через переключатель

5. В основной регистр 2 вслед за числом А записывается число А и

f далее после N тактовых импульсов в регистре окажется сначала число А

2 затем А „ и далее нули. Если второе анализируемое число А < А, то на выходе блока 4 сравнения будет потенциал логического "0". При этом блок 30

6 управления выдает потенциал логической и1и по второму выходу 32, по которому переключатель 5 в этом случае пропускает на свой выход информацию с тРетьего входа (верхнего 35 на фиг.1). Таким образом, основной регистр 2 получается замкнутым в кольцо, и число A„ с выхода регистра

2 перезаписывается íà его вход, а следом за ним с входной шины I 40 число А . В результате такого процесса за И циклов анализа (ка>щый по И тактовых импульсов) произойдет сортировка по величине чисел А,A,..., 4У 2У У

АИ, и в регистре 2 они окажу я 45 расположенными по порядку величины и будут иметь обозначения В, При работе устройства на выходных шинах 10 каждому числу В, будет соответствовать

его порядковый номер (ранг) R„c выходов 50 счетчика рангов. Перед записью в регистр 2 последнего по рангу R чисМ ла с выхода переключателя 5 срабатывает дешифратор 17 по коду послед- него ранга, и с выхода дешифратора 55

17 на первый. вход четвертого элемен,та И 18 поступает единичный потенциал. При поступлении последнего тактового импульса в регистр 19 порога в крайнюю левую ячейку регистра 2 записывается сортируемое число А, соответствующее наинизшему райгу R >, При дальнейшеи работе устройства при поступлении на вход 1 устройства последующего числа А,на втором входе второго блока 20 сравнения

1 будет число А„, которое и сравнивается с вновь поступившим числом А +„.

Если число А А, то на выходе

Я» и блока 20 сравнения находится единичный потенциал, а при поступлении по шине 12 пускового импульса последний стробирует второй элемент И 13, и по его сигналу сбрасывается в

"Ои счетчик 8, а блок 6 управления по первому выходу 35 включает элемент И 9, который разрешает прохождение тактовых импульсов от генератора 7 на тактовые входы основного и буферного регистров 2 и 3. При этом сортировка будет происходить как и в предыдущих случаях. Если поступающее число А„ А„, т.е. N»f меньше самого малого числа, хранимого в основном регистре 2, то второй блок 20 сравнения на своем выходе выставит нулевой потенциал.

Второй элемент И 13 блокируется, а третий элемент И 14 разблокируется.

При подаче пускового импульса по шине 12 срабатывает элемент И 14, а по концу этого импульса срабатывает формирователь 15 сигнал с которого через элемент ИЛИ 16 поступает на вход 11 конца цикла.

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

В дальнейшем все поступающие на входную шину 1 числа А сравнивают1 ся с меньшим числом А„, хранимым в регистре 2, а также.в регистре 19 порога, и в случае превышения кода числа А кода числа в регистре 19 порога (А 7 А ) по сигналу с выхо1 да элемента И 13 производится запуск устройства на цикл анализа, длящегося N тактовых импульсов.

7 1168

В результате работы устройства на первых циклах анализа происходит сортировка по .величине чисел А„, А,...,А, и в регистре 2 они окажутся по порядку величины. При

5 последующем ранжировании чисел вновь поступающее число "вклинивается" согласно своему. рангу в последовательность N чисел В„,В,...,В 1, z хранимых в основном регистре 2,и . 1p последнее (N+1)-е число В оказывается в буферном регистре 3, а так как это число оказалось меньшим по величине, то она отбрасывается, ибо после N-го тактового импульса буферный регистр 3 исключается из кольца.

При дальнейшей работе устройства в регистре 2 б"дут накапливаться только самые большие по величине (экстре-20 мальные) числа, расположенные по порядку величины.

Работа блока 6 (фиг.3) происходит следующим образом.

Пусковой импульс с шины 12 посту-25 пает на вход 30, устанавливает RSтриггер 25 в состояние "1" по прямому выходу, а RS-триггер 15 и счетный триггер 24 через элементы ИЛИ 26 и

27 — в состояние "0" по входам R.

Прямой выход RS-триггера 25 является выходом 35 блока 6 и поступает затем на элемент И 9. На инверсных выходах

RS-триггера 23 и счетного триггера

24 устанавливается потенциал логической "1". Таким образом, на всех вхо»

45 дах элемента И 22 имеются логические

"1", а на выходе 32 блока 6 также появится логическая ™1" (фиг.Зе). Это соответствует режиму работы устрой- 40 ства ранжирования с замкнутым в кольцо регистром 2.

924

Если блок 4 сравнения выдает на к-м тактовом импульсе потенциал логической "1" (А 2 В, фиг.38), то этот потенциал через вход 28 блока

6 поступает на первый вход элемента

И 21 на втором входе которого к этому времени находился потенциал логической "1" с инверсного выхода счетного триггера 24, поэтому на выходе элемента И 21 появляется потенциал логической "1" и устанавливает RSтриггер 23 в состояние "1" по прямому выходу. Эта "1" поступает на выход 33 блока 6 (фиг. 3 ) . На вход 29. блока 6 поступают тактовые импульсы с генератора 7 (фиг-.Зц). Первый же импульс после срабатывания триггера

23 (т.е. (к+1)-й по счету) через элемент ИЛИ 26 по R-входу возвращает триггер 23 снова в состояние "0" по прямому выходу. Положительный перепад напряжения с инверсного выхода триггера 23 при этом запускает по счетному входу триггер 24 и переводит его в состояние логической "1" по прямому выходу, который является выходом 34 блока 6 управления ° (фиг,33). В этом состоянии триггер

24 находится до поступления импульса переполнения счетчика 8 рангов по входу 31 блока 6, которым устанавливается в нулевое состояние как триггер 24 (через элемент KTH 27), . так и триггер 25.

Выход 1", конца цикла сравнения и ,шина 12 начала работы могут быть перемкнуты между собой. В этом случае устройство ранжирования переходит в непрерывный автономный режим и его темп работы определяется только частотой импульсов генератора 7 (фиг.2).

1168924

1!689?4

1168924

Составитель Е. Иванова

Редактор В. Данко Техред С.Иовжий. Корректор N, Самборская

Заказ 4613/41 Тираж 710 Подписное

ВПИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Иосква, Ж"35, Раушская наб., д. 4/5

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4

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

 

Похожие патенты:

Изобретение относится к способам обработки листового материала с сортировкой листов

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

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

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

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

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

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

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

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

 

Наверх