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

 

УСТРОЙСТВО РАНЖИРОВАНИЯ . ЭКСТРЕ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