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

 

Изобретение относится к области автоматики и вычислительной техники и может быть использовано для определения выборочной медианы случайных временных интервалов. Цель изобретения - повьшение быстродействия. Цель изобретения достигается за счет введения в устройство блоков формирования ранга медианы и сравнения рангов временных интервалов, которые имеют сложную структуру. Устройство для определения выборочной медианы позволяетопределять медиану при неполном переборе всех сравниваемых временных интервалов, что позволяет сократить время определения медианы в среднем, в 2 раза. 3 з.п. ф-лы, 7 ил. (Л

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

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

РЕСПУБЛИК (дц 4 Г 06 F 15/36

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3775254/24-24 (22) 25.07.84 (46) 15.11.86. Бюл, У 42 (72) Э.В.Борисов, P Ã.Толпарев и Е,Н.Хохлачев (53) 681.32(088.8) (56) Авторское свидетельство СССР

У 489104, кл. G 06 F 7/04, 1973.

Гильбо Е.П., Челпанов И.Б. Обработка сигналов на основе упорядоченного выбора, М,: Советское радио, 1975, с. 15 ° (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ВЫ-

БОРОЧНОЙ МЕДИАНЫ (57) Изобретение относится к области автоматики и вычислительной техники.80, 1270764 А 1 и может быть использовано для определения выборочной медианы случайных временных интервалов. Цель изобретения — повышение быстродействия.

Цель изобретения достигается за счет введения в устройство блоков формирования ранга медианы и сравнения рангов временных интервалов, которые имеют сложную структуру, Устройство для определения выборочной медианы позволяет определять медиану при неполном переборе всех сравниваемых временных интервалов, что позволяет сократить время определения медианы в среднем. в 2 раза. 3 s.ï. ф-лы, 7 ил.

1270764

l5

Я

Блок измерения временных интервалов (фиг. 3) содержит первую группу элементов И 44, элемент И 45, вторую группу элементов И 46, реИзобретение относится к автоматике и вычислительной технике и может быть использовано для определения выборочной медианы случайных временных интервалов.

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

На фиг. 1 представлена структурная схема предлагаемого устройства для определения выборочной медианы; на фиг. 2 — схема блока управления; на фиг. 3 — схема блока измерения интервалов времени; на фиг. 4 — схема блока попарного сравнения временных интервалов; на фиг. 5 — схема блока формирования рангов временных интервалов; на фиг. 6 — схема блока сравнения рангов временных интервалов; на фиг. 7 — схема блока формирования ранга медианы.

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

4 формирования рангов временных интервалов, блок 5 сравнения рангов временных интервалов. блок 6 формирдвания рангов медианы.

Блок управления (фиг. 2) содержит второй формирователь 7 импульсов, регистр 8 памяти, первый элемент

ИЛИ 9, первый триггер 10, первый . элемент И 11, пятый элемент ИЛИ 12. первый счетчик 13, первый дешифратор 14, первый коммутатор 15, третий. дешифратор 16, второй счетчик 17, второй дешифратор 18, второй коммутатор 19, второй элемент 20 задержки, первый формирователь 21 импульсов, элемент НЕ 22, четвертый счетчик 23, второй элемент ИЛИ 24, третий элемент 25 задержки, второй триггер 26, третий и четвертый элементы ИЛИ .27 и 28, второй элемент И 29, пятый элемент 30 задержки, третий элемент

И 31, четвертый и пятый элементы

32 и 33 задержки, генератор 34 тактовых импульсов, группу ключей Зэ, третий счетчик Зб, третий триггер 37, четвертый элемент И 38, блок 39 сравнения, пятый счетчик 40, четвертый дешифратор 41, шестой ИЛИ 42, третий формирователь 43 импульсов. гистр 47, группу ключей 48, группу счетчиков 49.

Блок попарного сравнения временных интервалов (фиг„ 4) содержит первую группу ключей 50, вторую группу ключей 51, первую и вторую группы элементов ИЛИ 52 и 53 и блок 54 сравнения.

Блок формирования рангов временных интервалов (фиг, 5) содержит первую группу элементов ИЛИ 5, группу элементов И 56, вторую группу элементов ИЛИ 57, группу счетчиков 58.

Блок сравнения рангов временных интервалов (фиг. 6) содержит группу ключей 59, группу элементов ИЛИ 60, блок 61 сравнения.

Блок формирования ранга медианы (фиг. 7) содержит счетчик 62, ключ

63, делитель 64, элемент 65 задержки, регистр 66 памяти.

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

Общий алгоритм работы устройства следующий. После включения питания импульс подается от отдельного генератора на вход "Стоп" блока 1 управления для установки всех регистров и счетчиков в нулевое состояние.

Затем на вход задания числа временных интервалов блока устройства подается число в двоичном коде равное объему выборки, которое запоминается в блоке 1 управления и из него подается в блок 6 формирования ранга медианы (сигнал U ) для опре8 деления ранга медианы.

На вход задания временного интервала устройства подаются сигналы, соответствующие началу и концу временных интервалов исследуемого процесса. Начало определения выборочной медианы соответствует подаче импульса на вход "Пуск" блока 1 управления. По этому сигналу блок 1 управления формирует управляющие сигналы U,, подаваемые на вход блока 6 формирования ранга медианы, по которому заканчивается формирование ранга медианы и осуществляется подача его в виде кода U на вход блока 5 сравнения рангов временных интервалов. Кроме того, по сигналу

"Пуск" в блоке 1 управления формируются сигналы П и U, в соответствии с которыми в блоке 2 измерения интервалов времени произво1270764.дится измерение интервалов времени между поступающими входными импульсами путем подсчета тактовых импульсов П в течение соответствующих временных интервалов °

После измерения каждого временного интервала блок 2 формирует .игналы U, соответствующие измеренным временным интервалам.

Блок 1 управления сравнивает но- 10 мер i каждого измеренного временного интервала с числом объема выборки h u в случае совпадения этих значений осуществляет следующие операции.

Формирует сигнал Ц "Конец изме- 15 рения", который подается в блок 2 измерения интервалов времени и закрывает его на время определения медианы. Формирует синхроимпульс U<> для одновременного сравнения времен- 20 ных интервалов в блоке 3 попарного сравнения временных интервалов:

Формирует импульсы U и Ьд„ определяющие следующую последовательность сравнения временных интервалов: срав- 25 нивается временной интервал 1„ с времени и интервалами 11 " .ьи сравнивается Ф с ь ... и т.д.

l1 до сравнения „„с

В случае если „. блок 3 попарного сравнения временных интервалов выдает положительный импульс U < на выход, в противном случае, когда

«» < 1 — на выход U < которые подаются в блок 4 формирования ран- 35 гов временных интервалов. В этом блоке в соответствии с сигналами U< и U< формируется ранг г В ходе

И сравнения с ... ь и одновре1 2 менно осуществляется начало формирования рангов других временных интервалов. После формирования ранга г„ осуществляется его сравнение с рангом медианы. Для этого блок 1 управления после сравнения " с л и формирует сигнал U„который считывает код U>» соответствующий г„ из блока 4 формирования рангов временных интервалов и подает его в блок 5 сравнения рангов временных интервалов. Одновременно сигнал U 6 .л готовит блок 4 пля считывания в случае если „ = . Блок 5 сравнения рангов осуществляет сравнение кода U r с кодом П, который соответствует рангу медианы, поступающей из блока

6 формирования ранга медианы. Момент сравнения синхронизируется импульсом

Н, поступающим из блоКа i управления.

В случае, когда r„ = г, блок 5 сравнения рангов формирует сигнал

U который подается на вход блока 2 и считывает с него временной интервал

i„ = с . В случае, когда г„ r работа устройства продолжается и формируется ранг следующего временного интервала . Процесс продолжается пока не будет обнаружен ранг медианы среди измеренных временных интервалов.

Рассмотрим работу устройства более детально.

Формирователь 21 формирует импульс, который поступает на вход счетчика 62, увеличивая его потенци- ал и на 1, т.е. образуя число и+1, а также на вход элемента 65 задержки блока формирования ранга медианы.

Пройдя элемент 65 импульс открывает ключи 63, считывая содержимое счетчика 62 в делитель 64, который делит и+1 на 2, Результат деления записывается в регистр 66, сигнал с выхода которого подается на входы блока 61 сравнения, блока 5 сравнения рангов временных интервалов, На выходе дешифратора 18 появляется положительный потенциал, который открывает ключ 50-1 группы ключей 50. Через открытый ключ 50-1 содержимое счетчика 49-1, соответствующее измеренному интервалу „, поступает на входы элемента ИЛИ 52 и через него на входы блока 54 сравнения. Кроме того. положительный потенциал открывает ключ 55-1 группы ключей 55 блока формирования рангов временных интервалов.

На выходе дешифратора 41 появляется положительный потенциал, который открывает ключ 51-2 из группы 51 блока 3 попарного сравнения временных интервалов.

Содержимое счетчика 49-2, соответствующее измеренному интервалу поступает на входы элемента Э

ИЛИ 53 и через него на входы блока 54 сравнения.

Одновременно потенциал с выхода блока 41 поступает через элемент

ИЛИ 42 на вход формирователя 43 испульсов. Формирователь 43 импульсов формирует импульс, который поступает в тактовый вход блока 54 сравнения, ° >

1270764 обеспечивая одновременное сравнение кодов, соответствующих временным ин,» бЪ тервалам, и

Л

В случае если 1„) ь, то на выходе 55 блока 54 сравнения формирует; ся импульс, поступающий на входы группы ключей 55 из которых будет открыт только ключ 55-1. Через открытый ключ 55-1 импульс записывается в счетчик 58-1 из группы счетчиков 58 блока 4 формирования рангов, обеспечивая формирование ранга временного интервала. В случае если Ф„ (, то блок 54 сравнения формирует импульс на выходе, который пос- 15 тупает на вход ключа 56-2 из группы ключей 56, который был открыт потен- циалом с выходом блока 41.

Через открытый ключ 56-2 импульс поступает через элемент ИЛИ 57-2 20 из группы элементов ИЛИ 57 на вход счетчика 58-2 обеспечивая тем самым формирование ранга. временного интервала„

Одновременно импульсы с выхсда блока 32 поступают на вход открытого элемента И 31 и через него на вход элемента 30 задержки. С выхода элементов 30 задержки импульсы с запаз \ 30 дыванием на время, поступают на вход 1 триггера 37, который перебрасывается в состояние "1" и положительным потенциалом П „ с выхода 1 открывается элемент И 38.

Через открытый элемент И 38 импульсы с генератора 34 поступает на входы счетчика 40, в котором уже было записано число 2. На выходах счетчика 40 последовательно формируются двоичные коды соответствующие числам 4 р 3 у в е ll y KQTopbte подают на на входы дешифратора 41. На выходах дешифратора 41 последовательно появляются потенциалы, которые последовательно открывают ключи группы 51, 45 обеспечивая тем самым подачу двоичных кодов, соответствующих измеренным интервалам ь, ...,,„, на входы элемента ИЛИ 53 и через него на входы блока 54 сравнения. В результате временные интервалы последовательно сравниваются с и временным интервалом „. Считывание результатов сравнения осуществляется импульсами, подаваемыми с формирователя 43 импульсов, которые формируются после появления потенциалов на выходах дешифратора 41. Зт » исключает появление паразитных сигналов на выходах блока 54 сравнения при смене сравниваемых кодов.

Таким образом, в случае если

,3 ь; (i = 3„4, . ° ., п) импульсы, сформированные на выходе 55 блока 54 сравнения, поступают через открытый ключ 55-1 на вход счетчика 58-1, формируя тем самым ранг временного интервала,, В том случ; е, если „ ;, импульсы, сформированные на выходе бло-, ка 54 сравнения, поступают через соответствующий ключ 56-i (на схеме не обозначены) и элемент ИЛИ 57-i на вход счетчика 58-i, обеспечивая тем самым формирование ранга временного интервала

Процесс сравнения t с продол1 1 жается до тех пор гока на счетчике 40 не будет записано число п.

Результаты сравнения считываются подачей импульса с выхода формирователя 7, в котором формирование производится по переднему фронту импульса, поцаваемого с выхода дешифратора 16 через элемент ИЛИ 12. Если ранг r совпадает с рангом медианы

2 то блок 61 сравнения вырабатывает 1 импульс, которьгй подается на входы группы ключей 48 блока 2 измерения временных интервалов, из которых будет открыт только ключ 48-1, так как на другой его вход будет подан положительный потенциал. В результате двоичный код, соответствующий временному интервалу „, будет подаваться с выходов счетчика 49-1 через открытый ключ 48-1, элемент

ИЛИ 46 в регистр 47, где будут храниться медианы временных интервалов г, ..., г и при необходимости считываться с выхода устройства.

Для определения медианы следующей серии временных интервалов или когда г r работа устройства продол4 жается.

Формирование рангов временных интервалов „ ..., в продолжа1 ется до тех пор пока не произойдет совпадение г с r . При совпадении (г;= г ) блок 61 сравнения формирует импульс, который обеспечивает считывание р, л медианы ь;= 1„ соответствующего счетчика 48-,i группы счетчиков 48 ана,Ъ логично изложенному, когда

При этом необходимо учесть, что при г; = г„„ все элементы схемы сбрасы7 12 ваются в нулевое состояние и все последующие действия по формированию рангов последующих временных интервалов прекращаются.

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

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

НГ, три триггера, первый вход первого элемента ИЛИ блока управления является входом "Стоп" устройства, второй вход первого элемента ИЛИ соединен с выходом первого элемента задержки, а выход — с выходом установки нуля первого триггера блока управления, вход установки в "1" которого является входом

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

70764

8 группе выходов регистра памяти, а выход - соединен с входами первого формирователя импульсов и элемента

НЕ, выход которого соединен с третьим

5 входом первого элемента И, выход первого формирователя импульсов соединен с первым входом второго элемента ИЛИ, входом установки в "1" второго триггера, с первым входом треl0 тьего элемента ИЛИ, rr wepea второй элемент задержки — с вторым входом третьего элемента ИЛИ, третий вход

В которого соединен с выходом второго элемента И и подключен к второму входу второго элемента ИЛИ, выход которого соединен с информационным входом второго счетчика, группа информационных выходов которого соединена с группой входов второго дешифратора, группа входов которого сое.динена с группой управляющих входов второго коммутатора, группа информационных входов которого соединена с одноименной группой выходов регистра, 25 памяти, а выход — соединен с входом установки в "О" второго триггера, а через третий элемент задержки — с первым входом четвертого элемента

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

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

45 входами ключей группы, выход третьего элемента И через пятый элемент задержки соединен с входом установки в "1" третьего триггера, выход которого соединен с первым входом четвер50 того элемента И, второй вход которого соединен с выходом генератора тактовых импульсов, а выход — соединен с управляющим входом пятого счетчика, группа информационных входов которогс соединена с группой выходов ключей группы, группа информационных входов которых соединена с группой информационных выходов третьего счетчика, 9 1270 группа информационных выходов пятого счетчика соединена с группой входов четвертого дешифратора, группа выходов которого соединена с соответствующими входами шестого элемента ИЛИ, выход которого соединен с входом третьего формирователя импульсов. группа выходов числа временных интервалов пятого счетчика соединена с первой группой входов блока сравнения, IO вторая группа входов которого соединена с группой информационных выходов регистра памяти, выход блока сравнения соединен с выходом установки в

"О" третьего триггера, с вторым вхо- I$ дом второго элемента И, с вторым входом четвертого элемента ИЛИ и входом разрешения перезаписи пятого счетчика, блок сравнения рангов вре-. менных интервалов содержит группу ключей, группу элементов ИЛИ и блок сравнения, вьгходы ключей группы соединены с соответствующими входами элементов ИЛИ группы, выходы которых соединены с первой группой 25 информационньгх входов блока сра:внения, выход которого является вьгходом блока сравнения рангов временных интервалов, блок формирования ранга медианы содержит счетчик, ключ, ЗО делитель, регистр памяти и элемент задержки, группа информационных выходов счетчика соединена с информационными входами ключа, информационные выходы которого соединены с группой входов делимого делителя, группа выходов частного которого соединена с группой информационных входов регистра памяти, выход элемента задержки соединен с управляющим 4О входом ключа и входом делителя, вход элемента задержки соединен с счетным входом счетчика и подключен к выходу первого формирователя импульсов блока управления, группа информационньгх выходов регистра памяти которого соединена с одноименной группой входов счетчика блока формирования ранга медианы, информационные выходы регистра памяти которого соединены с второй группой одноименных вхоцов блока сравнения рангов временных интервалов, тактовый вход которого соединен с выходом второго формирователя импульсов блока управления, группа выходов третьего дешифратора которого соединена с управляющими входами выходов соответствующих

764 !

О ключеи группы блока сравнения ран гов временных интервалов и является первым вьгходом блока управления, вторым выходом которого является выход генератора тактовых импульсов, группа выходов четвертого дешифратора является третьим выходом блока управления, четвертым выходом которого является группа выходов второго дешифратора блока управления, пятым выходом которого является выход третьего формирователя импульсов, шестым выходом блока управления является группа выходов первого дешифратора блока управления, выход элемента НЕ которого является седьмым выходом блока управления, первый выход блока управления соединен с первым входом блока изменения интервалов времени, второй вход которого соединен с вторым выходом блока управления, третий выход которого соединен и с первым входом блока попарного сравнения временных интервалов, второй вход которого соединен с вторым входом блока попарного сравнения временных интервалов и подключен к четвертому выходу управления, пятый выход которого соединен с третьим входом блока попарного сравнения временных интервалов, шестой выход блока управления соединен с третьим входом блока измерения интервалов времени, четвертый вход которого соединен с седьмым .выходом блока управления, первый выход блока измерения интервалов времени является выходом устройства, выход блока сравнения рангов временных интервалов соединен с пятым входом блока измерения интервалов времени, второй выход которого соединен с четвертым входом блока попарного сравнения временных интервалов, первый и второй выходы которого соединены соответственно с третьим и четвертым выходами блока формирования рангов временных интервалов, группа выходов которого соединена с входами соответствующих ключей группы блока сравнения рангов временных интервалов.

2. Устройство IIG п. 1, о T JI H» ч а ю щ е е с я тем, что., блок измерения интервалов времени содержит первую и вторую группы элементов И, элемент И, группу ключей, регистр и группу счетчиков, вьгход элемента И соединен с первым входом каждого

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

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

270764

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

10 вход блока сравнения является третьим входом блока, выходы "Больше" и . "Меньше" блока сравнения являются первым и вторым выходами блока соответственно.

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

ИЛИ первой группы являются третьим

25 входом блока, вторые входы элементов

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

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

1270764

1270764

1270764

Составитель Е. Ефимова

Редактор Ю. Середа Техред Л.Сердюкова, Корректор О. Луговая

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

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

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

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