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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХ ЛИК ц 4 Г 06 Г 15 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ СА ЗОБРЕТЕН К АВТОРСКОМУ СВИДЕТЕЛЬСТ 254/24-247 84 л,У 4 Р.Г.Т.8)свидетельст06 Р 7/04,Челпанов Ина основе уМ,: Советс 1973.Б, Обраорядоое радио ВЫОПРЕ област ехники относитсяслительной(54) УСТРОЙСТВО ДЛЯБОРОЧНОЙ МЕДИАНЫ(57) Изобретениеавтоматики и вычи 801270764 и может быть использовано для определения выборочной медианы случайных временных интервалов, Цель изобретения - повышение быстродействия.Цель изобретения достигается за счетвведения в устройство блоков формирования ранга медианы и сравнениярангов временных интервалов, которыеимеют сложную структуру, Устройстводля определения выборочной медианыпозволяетопределять медиану принеполном переборе всех сравниваемыхвременных интервалов, что позволяетсократить время определения медианыв среднем. в 2 раза. 3 з,п, А-лы,71270764 Серед орр О. Лугов Тираж 67 одп е ВНИИПИ Государственного комитета СССР по делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4 оизводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная Редактор Ю,Заказ 6244/ Составител Техред Л,С Ефимоваова, 1270764Изобретение относится к автоматике и вычислительной технике и можетбыть использовано для определениявыборочной медианы случайных временных интервалов.Цель изобретения - повышениебыстродействия,На фиг, 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 импульсов. Блок измерения временных интервалов (Фиг. 3) содержит первую группу элементов И 44, элемент И 45, вторую группу элементов И 46, ре 5 10 15 20 25 30 35 40 Я 50 55 гистр 47, группу ключей 48, группусчетчиков 49,Блок попарного сравнения временных интервалов (фиг 4) содержитпервую группу ключей 50, вторую груп.пу ключей 51, первую и вторую группы элементов ИЛИ 52 и 53 и блок 54сравнения,Блок формирования рангов временных интервалов (фиг, 5) содержитпервую группу элементов ИЛИ 55, груп.пу элементов И 56, вторую группуэлементов ИЛИ 57, группу счетчиков 58.Блок сравнения рангов временныхинтервалов (фиг. 6) содержит группуключей 59, группу элементов ИЛИ 60,блок 61 сравнения,Блок Формирования ранга медианы(Фиг. 7) содержит счетчик 62, ключ63, делитель 64, элемент 65 задержки, регистр 66 памяти,Устройство работает следующимобразом.Общий алгоритм работы устройстваследующий, После включения питанияимпульс подается от отдельного генератора на вход "Стоп" блока 1 управления для установки всех регистрови счетчиков в нулевое состояние,Затем на вход задания числа временных интервалов блока устройстваподается число в двоичном коде равное объему выборки, которое запоминается в блоке 1 управления и изнего подается в блок 6 Формированияранга медианы (сигнал П ) для опре 8деления ранга медианы.1На вход задания временного интервала устройства подаются сигналы,соответствующие началу и концу временных интервалов исследуемого процесса, Начало определения выборочной медианы соответствует подачеимпульса на вход "Пуск" блока 1управления. По этому сигналу блок 1управления формирует управляющиесигналы П подаваемые на вход блока 6 Формирования ранга медианы, покоторому заканчивается формированиеранга медианы и осуществляется подача его в виде кода Н на вход блока 5 сравнения рангов временных интервалов. Кроме того, по сигналу"Пуск" в блоке 1 управления формируются сигналы Н и Н , в соответствии с которыми в блоке 2 измерения интервалов времени произво 1270764.дится измерение интервалов временимежду поступающими входными импульсами путем подсчета тактовых импульсов П в течение соответствующих временных интерваловПосле измерения каждого временного интервала блок 2 формирует игналы У , соответствующие измеренным временным интервалам,Блок 1 управления сравнивает но О меркаждого измеренного временного интервала с числом объема выборки Ь и в случае совпадения этих значений осуществляет следующие операции.Формирует сигнал Ц"Конец изме рения", который подается в блок 2 измерения интервалов времени и закрывает его на время определения медианы. Формирует синхроимпульс Нз для одновременного сравнения времен ных интервалов в блоке 3 попарного сравнения временных интервалов: Формирует импульсы 0 и Ь определяющие следующую последовательность сравнения временных интервалов; срав нивается временной интервал 1 с временными интерваламисравнивается Ф си т,д. до сравнениясВ случае еслиблок 3 по- парного сравнения временных интервалов вьщает положительный импульс 0 на выход, в противном случае, когда- на выход П , которые подаются в блок 4 формирования ран гов временных интервалов. В этом блоке в соответствии с сигналами д 5 и П формируется ранг г в ходеИсравнения , сьи одновременно осуществляется начало формирования рангов других временных интервалов. После формирования ранга г осуществляется его сравнение с рангом медианы, Для этого блок 1 управления после сравнения " сл и формирует сигнал П который считывает код 05 , соответствующий г из блока 4 формирования рангов временных интервалов и подает его в блок 5 сравнения рангов временных интервалов, Одновременно сигнал П 6.л готовит блок 4 пля считыванияв случае если=, Блок 5 сравнения рангов осуществляет сравнение кода П , соответствующего рангу г с кодом П, который соответствует рангу медианы, поступающей из блока 6 формирования ранга медианы, Момент сравнения синхронизируется импульсом Н , поступающим из блоКа 1 управления.В случае, когда г = г , блок 5сравнения рангов формирует сигнал П 6 который подается на вход блока 2 и считывает с него временной интервалВ случае, когда гг работа устройства продолжается и формируется ранг следующего временного интервала, Процесс продолжается пока не будет обнаружен ранг медианы среди измеренных временных интервалов.Рассмотрим работу устройства более детально.Формирователь 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 сравнения,Ъобеспечивая одновременное сравнениекодов, соответствующих временным инЛ/ Ътервалам , илВ случае если) ь , то на выходе 55 блока 54 сравнения формирует;ся импульс, поступающий на входыгруппы ключей 55 из которых будетоткрыт только ключ 55-1. Через открьггый ключ 55-1 импульс записывается в счетчик 58-1 из группы счетчиков 58 блока 4 Формирования рангов,обеспечивая формирование ранга временного интервала. В случае еслиФ (, то блок 54 сравнения формирует импульс на выходе, который поступает на вход ключа 56-2 из группыключей 56, который был открыт потен-циалом с выходом блока 41,Через открытый ключ 56-2 импульспоступает через элемент ИЛИ 57-2 20из группы элементов ИЛИ 57 на входсчетчика 58-2 обеспечивая тем самымФормирование ранга. временного интервала25Одновременно импульсы с выхсдаблока 32 поступают на вход открытогоэлемента И 31 и через него на входэлемента 30 задержки, С выхода элементов 30 задержки импульсы с запазМ Зцдыванием на время , поступают навход 1 триггера 37, который перебрасывается в состояние "1" и положительным потенциалом Пс выхода 1открывается элемент И 38,Через открытый элемент И 38 импульсы с генератора 34 поступает навходы счетчика 40, в котором ужебыло записано число 2. На выходахсчетчика 40 последовательно Формируются двоичные коды соответствующиечислам 4,3, , и, которыеподаютна на входы дешифратора 41, На выходах дешифратора 41 последовательнопоявляются потенциалы, которые после"довательно открывают ключи группы 51,45обеспечивая тем самым подачу двоичных кодов, соответствующих измеренным интервалам ь . . . , , навходы элемента ИЛИ 53 и через негона входы блока 54 сравнения. В результате временные интервалыпоследовательно сравниваются сивременным интервалом . Считываниерезультатов сравнения осуществляетсяимпульсами, подаваемыми с Формирователя 43 импульсов, которые Формируются после появления потенциаловна выходах дешифратора 41. Зт исключает появление паразитных сигналов на выходах блока 54 сравненияпри смене сравниваемых кодов,Таким образом, в случае если)ь (3. = 3 4, .., п) импульсы,сформированные на выходе 55 блока 54сравнения, поступают через открытыйключ 55-1 на вход счетчика 58-1,формируя тем самым ранг временногоинтервала ,В том случ;.е, если;, импульсы, сформированные на выходе бло-.ка 54 сравнения, поступают черезсоответствующий ключ 56- (на схемене обозначены) и элемент ИЛИ 57-на вход счетчика 58-х, обеспечиваятем самым Формирование ранга временного интервалаПроцесс сравненияспродолжается до тех пор гока на счетчике 40не будет записано число п,Результаты сравнения считываютсяподачей импульса с выхода формирователя 7, в котором формированиепроизводится по переднему фронтуимпульса, поцаваемого с выхода дешифратора 16 через элемент ИЛИ 12. Еслиранг т совпадает с рангом медианы2то блок 61 сравнения вырабатываетимпульс, которьгй подается на входыгруппы ключей 48 блока 2 измерениявременных интервалов, из которыхбудет открыт только ключ 48-1, таккак на другой его вход будет поданположительный потенциал, В результате двоичный код, соответствующийвременному интервалу, будет подаваться с выходов счетчика 49-1через открытый ключ 48-1, элементИЛИ 46 в регистр 47, где будут храниться медианы временных интерваловг , , г и при необходимостисчитываться с выхода устройства.Для определения медианы следующей серии временных интервалов или когда гг работа устройства продолжается.формирование рангов временных интервалов,продолжается до тех пор пока. не произойдет совпадение г с г , При совпадении (г;= г ) блок 61 сравнения формирует импульс, который обеспечивает считываниер, лмедианы ;= соответствующего счетчика 48-, группы счетчиков 48 ана,Ълогично изложенному, когдаПри этом необходимо учесть, что при г; = г все элементы схемы сбрасы7 12ваются в нулевое состояние и всепоследующие действия по формированиюрангов последующих временных интервалов прекращаются,Таким образом, в соответствии сизложенным медиана может быть определена при неполном переборе всехсравниваемых временных интервалов вотличие от полного перебора, как этоделается в известном устройстве, чтопозволяет сократить время определениямедианы в среднем в два раза,Формула изобретения 1. Устройство для определения выборочной медианы, содержащее блок измерения интервалов времени, блок попарного сравнения временных интер-. валов, блок формирования рангов временных интервалов и блок управления, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены блок формирования ранга медианы и блок сравнения рангов временных интервалов, причем блок управления содержит три формирователя импульсов, четыре дешифратора, пять счетчиков, два коммутатора, группу ключей, генератор тактовых импульсов, шесть элементов ИЛИ, четыре элемента И, пять элементов задержки, блок сравнения, регистр памяти, элемент НГ, три триггера, первый вход первого элемента ИЛИ блока управления является входом "Стоп" устройства, второй вход первого элемента ИЛИ соединен с выходом первого элемента задержки, авыход - с выходом установки нуля первого триггера блока управления, вход установки в "1" которого является входом "Пуск" устройства, информационный вход регистра памяти блока управления является входом задания числа временных интервалов устройства, прямой выход первого триггера соединен с первым входом первого элемента И, второй вход которого является входом задания временного интервала устройства, а выход первого элемента И соединен с информационным входом первого счетчика, группа информационных выходов которого соединена с группой входов первого дешифратора, группа выходов которого соединена с группой управляющих входов первого коммута,тора, группа информационных входов которого подключена к одноименной 707648 группе выходов регистра памяти, а выход - соединен с входами первого формирователя импульсов и элемента НЕ, выход которого соединен с третьим 5 входом первого элемента И, выход первого формирователя импульсов соединен с первым входом второго элемента ИЛИ, входом установки в "1" второго триггера, с первым входом тре О тьего элемента ИЛИ, и через второйэлемент задержки - с вторым входом третьего элемента ИЛИ, третий вход 1которого соединен с выходом второго элемента И и подключен к второму входу второго элемента ИЛИ, выход которого соединен с информационным входом второго счетчика, группа информационных выходов которого соединена с группой входов второго деши- ратора, группа входов которого сое,динена с группой управляющих входов второго коммутатора, группа информационных входов которого соединена с одноименной группой выходов регистра, 25памяти, а выход - соединен с входом установки в "О" второго триггера, а через третий элемент задержки - с первым входом четвертого элемента ИЛИ, выход которого соединен с ьп 1" формационным входом четвертого счетчика, группа информационных выходов которого соединена с группой входов.третьего дешифратора, группа выходов которого соединена с соответствующи ми входами пятого элемента ИЛИ, вьгход которого соединен с входом второго формирователя импульсов, выход второго триггера соединен с первыми входами второго и третьего элементов 40И, выход третьего элемента ИЛИ соединен с информационным входом третьего счетчика и через четвертый элемент задержки - с вторым входом третьего элемента И и управляющими 45 входами ключей группы, выход третьегоэлемента И через пятый элемент задержки соединен с входом установки в "1" третьего триггера, выход которого соединен с первым входом четвер" 5 О того элемента И, второй вход которогосоединен с выходом генератора тактовых импульсов, а выход - соединен с управляющим входом пятого счетчика, группа информационных входов которогс соединена с группой выходов ключей группы, группа информационных входов которых соединена с группой информа.ционных выходов третьего счетчика, 9 1270группа информационных выходов пятогосчетчика соединена с группой входовчетвертого дешифратора, группа выходов которого соединена с соответствующими входами шестого элемента ИЛИ,выход которого соединен с входомтретьего формирователя импульсов.группа выходов числа временных интервалов пятого счетчика соединена с первой группой входов блока сравнения, 10вторая группа входов которого соединенас группой информационных выходоврегистра памяти, выход блока сравнения соединен с выходом установки вО третьего триггера, с вторым входом второго элемента И, с вторымвходом четвертого элемента ИЛИ ивходом разрешения перезаписи пятогосчетчика, блок сравнения рангов временных интервалов содержит группуключей, группу элементов ИЛИ и блок сравнения, вьгходы ключей группы соединены с соответствующими входами элементов ИЛИ группы, выходы которых соединены с первой группой 25 информационньгх входов блока сра:внения, выход которого является вьгходом блока сравнения рангов временных интервалов, блок формирования ранга медианы содержит счетчик, ключ, ЗО делитель, регистр памяти и элемент задержки, группа информационных выходов счетчика соединена с информационными входами ключа, информационные выходы которого соединены с группой входов делимого делителя, группа выходов частного которого соединена с группой информационных входов регистра памяти, выход элемента задержки соединен с управляющим входом ключа и входом делителя, вход элемента задержки соединен с счетным входом счетчика и подключен к выходу первого формирователя импульсов блока управления, группа информационньгх выходов регистра памяти которого соединена с одноименной группой входов счетчика блока формирования ранга медианы, информационные выходы регистра памяти которого соединены с второй группой одноименных вхоцов блока сравнения рангов временных интервалов, тактовый вход которого соединен с выходом второго формирователя импульсов блока управления, группа выходов третьего дешифратора которого соединена с управляющими входами выходов соответствующих 764Оключей группы блока сравнения рангов временных интервалов и является первым выходом блока управления, вторым выходом которого является выход генератора тактовых импульсов, группа выходов четвертого дешифратора является третьим выходом блока управления, четвертым выходом которого является группа выходов второго дешифратора блока управления, пятым выходом которого является выход третьего формирователя импульсов, шестым выходом блока управления является группа выходов первого дешифратора блока управления, выход элемента НЕ которого является седьмым выходом блока управления, первый выход блока управления соединен с первым входом блока изменения интервалов времени, второй вход которого соединен с вторым выходом блока управления, третий выход которого соединен и с первым входом блока попарного сравне. ния временных интервалов, второй вход которого соединен с вторым входом блока попарного сравнения временных интервалов и подключен к четвертому выходу управления, пятый выход которого соединен с третьим входом блока попарного сравнения временных интервалов, шестой выход блока управления соединен с третьим входом блока измерения интервалов времени, четвертый вход которого соединен с седьмым .выходом блока управления, первый выход блока измерения интервалов времени является выходом устройства, выход блока сравнения рангов временных интервалов соединен с пятым входом блока измерения интервалов времени, второй выход которого соединен с четвертым входом блока попарного сравнения временных интервалов, первый и второй выходы которого соединены соответственно с третьим и четвертым выходами блока формирования рангов временных интервалов, группа выходов которого соединена с входами соответствующих ключей группы блока сравнения рангов временных интервалов.2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок измерения интервалов времени содержит первую и вторую группы элементов И, элемент И, группу ключей, регистр и группу счетчиков, выход элемента И соединен с первым входом каждого11 1 элемента И первой группы, выходы которых соединены с управляющими входами соответствующих счетчиков групп, первая группа информационных выходов которых соединена с одноименными входами соответствующих ключей группы, выходы которых соединены с соответствующими входами элементов И второй группы, выходы которых соединены с группой информационных входов регистра, выход которого является первым выходом блока, вторые входы элементов И первой группы являются третьим входом блока, первый и второй входы элемента И являются соответственно вторым и четвертым входами блока, управляющие входы ключей группы являются первым входом блока, информационные входы ключей группы являются пятым входом блока, вторая группа информационных выходов счетчиков группы является вторым выходом блока.3, Устройство по п, 1, о т л ич а ю щ е е с я тем, что блок по- парного сравнения временных интервалов содержит первую и вторую группы ключей, первую и вторую группы элементов ИЛИ и блок сравнения, первая и вторая группы информационных входов которого соединены соответственно с одноименной группой выходов элементов ИЛИ первой и второй групп, группа информационных входов ключей первой группы соединена с соответствующими входами элементов ИЛИ первой группы, группа информационных270764 12 выходов ключей второй группы соединена с соответствующими входамиэлементов ИЛИ второй группы, управляющие входы ключей первой и второйгрупп являются соответственно вторыми первым входами блока, группы информационных входов ключей пе 1 вой ивторой групп является,соответственно четвертым входом блока, тактовый 10 вход блока сравнения является третьимвходом блока, выходы "Больше" и"Меньше" блока сравнения являютсяпервым и вторым выходами блока соответственно154. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок формирования рангов временных интерваловсодержит первую и вторую группы эле ментов ИЛИ, группу. элементов И игруппу счетчиков, информационныевыходы которых являются группой выходов блока, первые входы элементовИЛИ первой группы являются третьим 25 входом блока, вторые входы элементовИЛИ первой группы являются вторымвходом блока, первые входы элементовИ группы являются четвертым входомблока, вторые входы элементов И группы являются первым входом блока, выходы элементов ИЛИ первой группы иэлементов И группы соединены соответственно с первыми и вторыми входами элементов ИЛИ второй группы, выходы которых соединены с счетнымивходами соответствующих счетчиковгруппы.