SU1278889A1 - Устройство дл определени медианы - Google Patents

Abstract

Изобретение относитс  к специализированным средствам вычислительной техники, с помощью которых решаетс  задача нахождени  медианы. Цель изобретени  - повьшение быстродействи  устройства. С этой целью в устройство введены суммирующий и вычитающий счетчики, выходной регистр . Устройство позвол ет обрабатывать все числа выборки параллельно . 1 3.п. ф-лы,3 ил.

Description

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

Цель изобретени  - повьппение быстродействи  устройства за счет параллельного анализа чисел выборки.

На фиг,1 приведена структурна  схема устройства дл  определени  медианы; на фиг.2 - структурна  схема источника чисел; на фиг.З - структурна  схема блока управлени .

Устройство дл  определени  медианы (фиг.О содержит источник 1 чисел, блок 2 управлени , блок 3 анализа чисел, п компараторов А, злемент ИЛИ 5, регистр 6 и элемент И 7 первый счетчик 8, второй счетчик 9 и выходной регистр 10.

Источник чисел (фиг,2) содержит п регистров выборки, регистр 12 числа и группы элементов И 13 по числу разр дов регистров П и 12,

Блок управлени  (cjiHr.B} содержит генератор 14 тактовых импульсов, триггеры 15-17, четыре элемента 1821 задержки и элемент И 22,

Устройство работает следующим образом ,

В исходном состо нии на пр мых выходах триггеров 15-17 блока 2 управлени  высокий уровень сигнала. Регистр 6 блока 3 анализа чисел, выходной регистр 10 и счетчики 8 и 9 обнулены, В каждом из п регистров 11 выборки наход тс  числа выборки, а в регистре 12 числа находитс  число (п+1)/2.

При подаче импульса Пуск на установочный вход триггера 15 на его инверсном выходе по вл етс  высокий уровень сигнала, поступающий на вход элемента 18 задержки, второй вход элемента И 22 и на вторые входы элементов И 13 источника 1 чисел, С приходом высокого уровн  сигнала на вторые входы элементов И 13 разрешаетс  параллельное прохождение чисел, установленных в ti регистрах 11 выборки и регистре 12 числа, на выход источника 1 числа. Эти числа поступают соответственно на первые входы компараторов 4 и информационный вход счетчика 8, Кодова  комбинаци  числа (п-«-1)/2 с регистра 12 числа заноситс  к счетчик 8 по приходу импульса разрешени  записи блока 2

управлени . Этот импульс формируетс  элементом 18 задержки из фронта сиг .нала с инверсного выхода триггера 15 с задержкой его по влени  на врем , необходимое дл  установки кода числа ()/2 на информационных входах счетчика 8, Высокий уровень сигнала , поступающий с выхода триггера 15 на первый вход элемента И 22, разрешает прохождение тактовых импульсов с генератора 14 на счетный вход счетчика (9 через элемент И 22, так как на его третьем и четвертом входах присутствуют высокие уровни сигналов . На разр дном выходе счетчика 9 формируетс  возрастающий разр дный код числа, поступающий на вторые входы п компараторов 4 и на входы выходного регистра 10, на входе запрета записи которого присутствует низкий уровень сигнала, поступающий с инверсного выхода триггера 16 блока 2 управлени , который запрещает запись в этот регистр 10, При равенстве одной или нескольких кодовых комбинаций чисел выборки с кодовой комбинацией числа, сформированной на выходе счетчика 9, на одном или нескольких выходах коМпараторов.

4 по вл ютс  высокие уровни сигналов , которые поступают на информационный вход регистра 6, Запись этой информации в регистр 6производитс  сигналом с е5лока 2 управлени  в момент прихода на вход разрешени  записи тактового импульса с генератора 14, так как на его входе разрешени  сдвига находитс  высокий уровень сигнал-а с пр мого выхода триггера 17,

прошедшего через элемент 20 задержки . Высокие уровни сигналов с выходов компараторов поступают также на .элемент ИЛИ 5, на инверсном выходе которого в этот момент по вл етс 

сигнал низкого уровн , который поступает на установочный вход триггера 17, По этому сигналу триггер 17 устанавливаетс  в нулевое состо ние. Перепад с его инверсного выхода поступает на вход элемента 21 задержки с задержкой его по влени  на выходе на (п+1) периодов тактовых импульсов С пр мого выхода триггера 17 низкий уровень сигнала поступает

на четвертый вход элемента И 22, запреща  прохождение тактовых импульсов с генератора 14 на выход блока 2 управлени , и через элемент 20

31

задержки с задержкой его по влени  на врем , равное 1,5 периодам тактовых импульсов и длительностью отрицательного импульса, сформированного элементом 20 задержки, равной ((п+1)-1,5) периода тактовых импульсов , необходимой на сдвиг записанной в регистре 6 информации, поступает на вход разрешени  сдвига регистра 6, разреша  сдвиг записанной в нем информации. С выхода элемента И 7 информаци  поступает на вычитаюпщй вход счетчика 8, уменьша  записанное в нем число ()/2, каждым тактовым импульсом на число совпадений на выходах компараторов 4. После вычитани  выдвинутой информации за п периодов тактовой частоты, записанной в регистре 6 из числа записанного в счетчике 8, на выходе элемента 21 задержки, в котором осуществл етс  задержка на (п+1) периодов тактовых импульсов, формируетс  импульс сброса, поступающий на вход сброса триггера I7, устанавлива  его в исходное состо ние. Высокий уровень сигнала с пр мого выхода триггера 17 через элемент 20 задержки поступает на вход разрешени  сдвига регистра 6, запреща  режим сдвига и устанавлива  режим записи в регистр 6, и на четвертый вход элемент И 22, разреша  прохождение тактовых импульсов на счетный вход счетчика 9, который продолжает увеличивать разр дный код числа до его очередного совпадени  с кодовой комбинацией одного или нескольких чисел выборки. Таким образом , продсшжает функционирование устройство аналогично описанному и такой режим работы устройства продолжаетс  до тех пор, пока на выходе счетчика 8 не по витс  импульс обнулени  его содержимого. По вление на выходе счетчика 8 импульса обнулени  свидетельствует о прохождении операции сравнени  (п+1)/2 чисел из выборки и окончании функции анализа чисел, следовательно, на выходе счетчика 9 сформировалс  разр дный код числа медианы.

Импульс обнулени  с выхода счетчика 8 поступает на первый вход триггера 16, устанавлива  его в нулевое состо ние . С пр мого выхода триггера 16 иизкий уровень сигнала поступает на третий вход элемента И 22, запреща  прохождение тактовых импульсов через элемент И 22 на счетчик 9. С

88894

инверсного выхода триггера 16 йысокий уровень сигнала поступает,на вход запрета записи выходного регистра 10, разреша  запись кода числа г медианы с разр дных выходов счелчика 9 в выходной регистр 10 по фронту тактового импульса, поступающего на вход разрешени  записи с генератора 14. С выходов регистра 10 считывает0 с  медианное значение числа. С инверсного выхода триггера 16 высокий уровень сигнала поступает на элемент 19 задержки, где задерживаетс  на 2 периода тактовых импульсов. Эле5 мент 19 задержки формирует сигнал сброса триггеров 15 и 16 счетчиков 8 и 9 и регистров 6 и 10. После чего устройство готово к очередной обработке выборки чисел.

Claims (2)

1. Формула изобретени 

   Устройство дл  определени  медианы , содержащее источник чисел, блок

   5 управлени , блок анализа чисел, состо щий из первого компаратора, регистра и элемента И, первый выход блока управлени  соединен с входом разрешени  выдачи чисел источника

   0 чисел, выход кода первого числа группы которого соединен с первым входом первого компаратора, второй выход блока управлени  соединен с первым входом элемента И блока анализа чи5 сел, отличающеес  тем, что, с целью повьш1ени  быстродействи , в него введены первый и второй счетчики и выходной регистр, а в блок анализа чисел введеньт элементы

   0 ИЛИ и (п-1) (п - нечетное число чисел в выборке) компараторов, блок управлени  содержит генератор тактовых импульсов , три триггера, четыре элемента задержки и элемент И, вход

   5 установки первого триггера блока управлени   вл етс  входом запуска устройства, инверсный выход первого триггера соединен с первым входом элемента И блока управлени  через

   0 первый элемент задержки - с входом разрешени  записи первого счетчика и  вл етс  первым выходом блока управлени , выход элемента И которого соединен со счетным входом второ5 го счетчика, инверсный выход второго триггера соединен с входом запрета записи выходного регистра и через второй элемент задержки - с входами сброса перв.ого и второго триггеров. первого и второго счетчиков, выходного регистра и регистра, выход генератора тактовых импульсов соединен с вторым входом элемента И блока управлени j с входами разрешени  записи выходного регистра и регистра и  вл етс  вторым выходом блока управ лени , пр мой выход третьего триггера соединен с третьим входом элемента И блока упра;влени  и через третий элемент задержки - с входом разрешени  сдвига регистра, выход элемента ИЛИ соединен с входом установки в единицу третьего триггера, инверсный выход которого через четвертый элемент задержки соединен со своим входом сброса второго триггера, пр мой выход которого соединен с четвертым входом элемента И блока управлени , выходы кодов с 2-го по п-е чисел группы источника чисел соединены с первыми входами соответствующих компараторов , выход кода регистра числа источника чисел соединен с информационным входом первого счетчика, раз р дные выходы второго .счетчика ; соединены соответственно с вторыми вхо дами всех компараторов и с информационным входом выходного регистра, выход которого  вл етс  выходом устройства , выходы компараторов соединены с соответствующими входами элемента ИЛИ и с информационными входами регистра соответственно, выход регистра соединен с вторым входом элемента И блока анализа чисел, выход которого соединен со счетным входом первого счетчика.
2. 2. Устройство по П.1, отличающеес  тем, что источник , чисел содержит п регистров выборки, регистр числа и (n+l) групп элвмен тов И, причем первые входы элементов И каждой из п групп соединены с выxoдa fi : разр дов одноименного регистрз выборки, первые входы элементов И (п+1)-й группы соединены с выходами соответствующих разр дов регистра числа, вторые входы элементов И всех групп  вл ютс  входом разрешени  выдачи чисел источника, выходы элементов И всех групп  вл ютс  группой выходов кодов (п+1) чисел источника.

   /У2. /