Устройство для определения медианы Советский патент 1986 года по МПК G06F17/18 

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

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

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

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

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

Блок управления (cjiHr.B} содержит генератор 14 тактовых импульсов, триггеры 15-17, четыре элемента 18- 21 задержки и элемент И 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. С

894

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

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

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

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

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

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

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

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

to

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

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

2. Устройство по П.1, отличающееся тем, что источник ,

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

/У2. /

o

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

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

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

2. Устройство по П.1, отличающееся тем, что источник ,

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

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