Устройство для определения медианы

 

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

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

СОЯМЛИСТИЧЕСНИХ

РЕСПУБЛИК (19} (И} (5}} 4 С Об F 15/36

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

К ASTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЬЙ КОМИТЕТ СССР пО делАм изОБРетений и ОтнРытий (21 ) 3936699/24-24 (22) 26.07 ° 85 (46) 23.12.86. Бюп. В 47 (71) Научно-производственное обьединение космических исследований при

АН АЗССР (72) В.Ф.Кашин, И.И.Кузьмин

;и P.À,Øåé îâ

l(53) 681.3 (088.8) (56) Авторское свидетельство СССР

У 492882, кл. G 06 F 15/36, 1974, Авторское свидетельство СССР

1l 607226, кл. G 06 F 15/36, 1975. (54) УСТРОЙСТВО ДЛЯ ОИРЕДЕЛЕНИЯ ИЕДИАНЫ (57) Изобретение относится к специа-. лизированным средствам вычислительной техники, с помощью которых решается задача нахождения медианы.

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

t 278889 2

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

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

На фиг, l приведена структурная схема устройства дпя определения медианы; на фиг. 2 — структурная схема источника чисел, на фиг,3 — структурная схема блока управления.

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

Источник чисел (фиг,2) содержит и регистров 11 -l l „выборки, регистр

12 числа и группы элементов И 13 3по числу разрядов регистров 1 l и 12.

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

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

В исходном состоянии на прямых выходах триггеров 15-17 блока 2 управления высокий уровень сигнала.

Регистр 6 блока 3 анализа чисел, выходной регистр 10 и счетчики 8 и

9 обнулены. В каждом из и регистров

I1 выборки находятся числа выборки, I а в регистре 12 числа находится число (п+1) /2.

При подаче импульса "Пуск" на установочный вход триггера 15 на его инверсном выходе появляется высокий уровень сигнала, поступающий на вход элемента 18 задержки, второй вход элемента И 22 и на вторые входы элементов И 13 источника 1 чисел.

С приходом высокого уровня сигнала на вторые входы элементов И 13 разрешается параллельное прохождение чисел, установленных в и регистрах

11 выборки и регистре 12 числа, на выход источника 1 числа. Эти числа поступают соответственно на первые входы компараторов 4 и информационный вход счетчика 8. Кодовая комбинация числа (и+1)/2 с регистра 12 числа заносится к счетчик 8 по приходу импульса разрешения записи блока 2

fQ

t5

ЗО

55 управления. Этот импульс формируется элементом 18 задержки из фронта сиг,нала с инверсного выхода триггера

15 с задержкой его появления на время, необходимое для установки кода числа (n+I)/2 на информационных входах счетчика 8. Высокий уровень сигнала, поступающий с выхода триггера

15 на первый вход элемента И 22, раэрешает прохождение тактовых импульсов с генератора 14 на счетный вход счетчика 9 через элемент И 22, так как на его третьем и четвертом входах присутствуют высокие уровни сигналов. На разрядном выходе счетчика

9 формируется возрастающий разрядный код числа, поступающий на вторые входы п компараторов 4 и на входы выходного регистра 10, на входе запрета записи которого присутствует низкий уровень сигнала, поступающий с инверсного выхода триггера 16 блока 2 управления, который запрещает запись в этот регистр 10. При равенстве одной или нескольких кодовых комбинаций чисел выборки с кодовой комбинацией числа, сформированной на выходе счетчика 9, на одном или нескольких выходах койпараторон.

4 появляются высокие уровни сигналов, которые поступают на информационный вход регистра 6. Запись этой информации в регистр 6 производится сигналом с блока 2 управления в момент прихода на вход разрешения sa писи тактового импульса с генератора

14, так как íà его входе разрешения сдвига находится высокий уровень сигнала с прямого выхода триггера 17, прошедшего через элемент 20 задержки. Высокие уровни сигналов с выходов компараторов поступают также на элемент ИЛИ 5, на инверсном выходе которого в этот момент появляется сигнал низкого уровня, который поступает на установочный вход триггера 17, По этому сигналу триггер 17 устанавливается в нулевое состояние, Перепад с его инверсного выхода поступает на вход элемента 21 задержки с задержкой его появления на выходе на (n+1) периодов тактовых импульсов. С прямого выхода триггера

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

2 управления, и через элемент 20

3 1278889 4

f0

20 задержки с задержкой его появления на время, равное 1,5 периодам тактовых импульсов и длительностью отрицательного импульса, сформированного элементом 20 задержки, равной ((и+1)-1,5) периода тактовых импульсов, необходимой на сдвиг записанной в регистре 6 информации, поступает на вход разрешения сдвига регистра

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

21 задержки, в котором осуществляет— ся задержка íà (и+1) периодов тактовых импульсов, формируется импульс сброса, поступающий на вход сброса триггера 17, устанавливая его в исходное состояние. Высокий уровень сигнала с прямого выхода триггера 17 через элемент 20 задержки поступает на вход разрешения сдвига регистра

6, запрещая режим сдвига и устанавливая режим записи в регистр 6, и на четвертый вход элемент И 22, разрешая прохождение тактовых импульсов на счетный вход счетчика 9, который продолжает увеличивать разрядный код числа до его очередного совпадения с кодовой комбинацией одного нли нескольких чисел выборки. Таким образом, продолжает функционирование устройство аналогично описанному и такой режим работы устройства продолжается до тех пор, пока на выходе счетчика 8 не появится импульс обнуления его содержимого. Появление на выходе счетчика 8 импульса обнуления свидетельствует о прохождении опера" ции сравнения (и+1)/2 чисел из выборки и окончании функции анализа чисел, следовательно, на выходе счетчика 9 сформировался разрядный код числа медианы.

Импульс обнуления с выхода счетчика

8 поступает на первый вход триггера

16, устанавливая его в нулевое состояние. С прямого выхода триггера

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

55 инверсного выхода триггера 16 высокий уровень сигнала поступает, на вход запрета записи выходного регкстра 10, разрешая запись кода числа медианы с разрядных выходов счезчнка

9 в выходной регистр 10 по франту тактового импульса, посту-пающего на вход разрешения записи с генератора

14. С выходов регистра 10 считывается медианное значение числа. С инверсного выхода триггера 16 высокий уровень сигнала поступает на элемент

19 задержки, где задерживается на

2 периода тактовых импульсов. Элемент 19 задержки формирует сигнал сброса триггеров 15 и 16 счетчиков

8 и 9 и регистров 6 и 10. После чего устройство готово к очередной обработке выборки чисел.

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

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

ИЛИ и (и-1) (n — нечетное число чисел в выборке) компараторов, блок управления содержит генератор тактовых импульсов, три триггера, четыре элемента задержки н элемент И, вход установки первого триггера блока управления является входом запуска устройства, инверсный выход первого триггера соединен с первым входом элемента И блока управления через первый элемент задержки — с входом разрешения записи первого счетчика и является первым выходом блока управления, выход элемента И которого соединен со счетным входом второго счетчика, инверсный выход второго триггера соединен с входом запрета записи выходного регистра и через второй элемент задержки — с входами сброса первого и второго триггербв, 5 12788 первого и второго счетчиков, выходного регистра и регистра, выход генератора тактовых импульсов соединен с вторым входом элемента И блока управления, с входами разрешения записи выходного регистра и регистра и является вторым выходом блока управления, прямой выход третьего триrrера соединен с третьим входом элемента И блока управления и через третий Я элемент задержки - с входом разрешения сдвига регистра, выход элемента

ИЛИ соединен с входом установки в единицу третьего триггера, инверсный выход которого через четвертый эле- 15 мент задержки соединен со своим входом сброса второго триггера, прямой выход которого соединен с четвертым входом элемента И блока управления, выходы кодов с 2-го по п-е чисел Д1 группы источника чисел соединены с первыми входами соответствующих компараторов, выход кода регистра числа источника чисел соединен с информационным входом первого счетчика, раз- 25 рядные выходы второго .счетчика; соединены соответственно с вторыми вхо89 6 дами всех компараторов и с информационным входом выходного регистра, выход которого является выходом устройства, выходы компараторов соединены с соответствующими входами элемента ИЛИ и с информационными входами регистра соответственно, выход регистра соединен с вторым входом элемента И блока анализа чисел, выход которого соединен со счетным входом первого счетчика.

2. Устройство по и. I о т л ич а ю щ е е с я тем, что источник чисел содержит и регистров выборки, регистр числа и (и+1) групп элементов И, причем первые входы элементов

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

И (и+1)-й группы соединены с выходами соответствующих разрядов регистра числа, вторые входы элементов И всех групп являются входом разрешения выдачи чисел источника, выходы элементов И всех групп являются группой выходов кодов (и+1) чисел источника.

1278889

Составитель В.Орлов

Редактор В.Иванова Техред A.Кравчук Корректор Л.Пилипенко

Заказ 6841/49 Тираж 671 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4