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

о

ct ;i

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

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

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

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

Блок управления (фиг. 2) содер кит второй формирователь 7 импульсов регистр 8 памяти, первый элемент ИЛИ 9, первый триггер 10, первый . элемент И 11, пятый элемент ИЛИ 12, первый счетчик.13, первый дешифратор 14, первый коммутатор 15, третий дешифратор 1 6, второй счетчик 17 , второй дешифратор 18, второй ком1 1утатор 19, второй элемент 20 задержки, первый формирователь 21.импульсов, элемент НЕ 22, четвертый счетчик 23, второй элемент ИЛИ 24, третий элемент 25 задержки, второй триггер 26, третий и четвертый элементы ШТИ 27 и 28, второй элемент И 29, пятый элемент 30 задержки, третий элемент И 31, четвертый и пятый элементы 32 и 33 задержки, генератор 34 тактовых импульсов, группу ключей 35, третий счетчик 36, третий триггер 37 четвертый элемент И 38, блок 39 сравнения, пятый счетчик 40, четвертый дешифратор 41, шестой ИЛИ 42, третий формирователь 43 импульсов.

Блок измерения временных интервалов (фиг. 3) содержит первую группу элементов И 44, -элемент И 45, вторую группу элементов И 46, ре-гистр 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 формирования ранга медианы (сигнал Пд) Для определения ранга медианы.

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

импульса на вход Пуск блока 1

управления. По этому сигналу блок 1 управления формирует управляющие сигналы IJg, , подаваемые на вход блока 6 формирования ранга медианы, по

которому заканчивается формирование ранга медианы и осуществляется подача его в виде кода Ug на вход блока 5 сравнения рангов временных интервалов. Кроме того, по сигналу

Пуск g блоке 1 управления формируются сигналы и и Ujj , в соответствии с которыми )з блоке 2 измерения интервалов времени произво3 .дится измерение интервалов времени t, между поступающими входными импульсами путем подсчета тактовых импульсов llj в течение соответствующих временных интервалов. После измерения каждого временно го интервала блок 2 формирует сигна лы , соответствующие измеренным временным интервалам. Блок 1 управления сравнивает номер i каждого измеренного временного /интервала с числом объема выборки h и в случае совпадения этих значений осуществляет следующие операции. Формирует сигнал Конец изме рения, который подается в блок 2 измерения интервалов времени и закрывает его на время определения мед аны. Формирует синхроимпульс U для одновременного сравнения времен ных интервалов в блоке 3 попарного сравнения временных интервалов; Формирует импульсы U и Ъ, определяющие следующую последовательность сравнения временных интервалов: сра нивается временной интервал с временными интервалами t сравнивается t с t - и т.д до сравнения i. с f . В случае если t- / V блок 3 по парного сравнения временных интерва лов выдает положительный импульс Ugj на выход, в противном случае, когда tf - на выход и 5 , которые подаются в блок 4 формирования ран гов временных интервалов. В этом блоке в соответствии с сигналами и Ujg формируется ранг г в ходе сравнения t с t одновременно осуществляется начало формирования рангов других временных интервалов. После формирования ранга г осуществляется его сравнение с рангом медианы. Для этого блок 1 управления после сравнения с t формирует сигнал U , который считы вает код Ujg , соответствующий г из блока 4 формирования рангов временных интервалов и подает его в блок 5 сравнения рангов временных интервалов. Одновременно сигнал Ugg готовит блок 4 пля считывания t в случае если . Блок 5 сравне ния рангов осуществляет сравнение кода Ujg , соответствующего рангу г с кодом , который соответствует рангу медианы, поступающей из блока 6 формирования ранга медианы. Момен 644 сравнения синхронизируется импульсом и, поступающим из 6noka 1 управления. В случае, когда г г, блок 5 сравнения рангов формирует сигнал и, , который подается на вход блока 2 и считывает с него временной интервал t Сд . В случае, когда г г работа устройства продолжается и формируется ранг следующего временного интервала t . Процесс продолжается пока не будет обнаружен ранг медианы среди измеренных временных интервалов. Рассмотрим работу устройства более детально. Формирователь 21 формирует импульс, который поступает на вход счетчика 62, увеличивая его потенциал п на 1, т.е. образуя число п+1, а также на вход элемента 65 задержки блока формирования ранга медианы. Пройдя элемент 65 импульс открывает ключи 63, считывая содержимое счетчнка 62 в делитель 64, которьй делит п+1 на 2. Результат деления записывается в регистр 66, сигнал с выхода которого подается на входы блока 61 сравнения, блока 5 сравнения рангов временных интервалов, На выходе дешифратора 18 появляется положительный потенциал, который открывает ключ 50-1 группы ключей 50. Через открытый ключ 50-1 содержимое счетчика 49-1, соответствующее измеренному интервалу i , поступает на входы элемента ИЛИ 52 и через него на входы блока 54 сравнения. Кроме того, положительный потенциал открывает ключ 55-1 группы ключей 55 блока формирования рангов временных интервалов . На выходе дешифратора 41 появляется положительный потенциал, кото- рый открывает ключ 51-2 из группы 51 блока 3 попарного сравнения временных интервалов. Содержимое счетчика 49-2, соответствующее измеренному интервалу tj, поступает на входы элемента ИЖ 53 и через него на входы блока 54 сравнения. Одновременно потенциал с выхода блока 41 поступает через элемент ИЛИ 42 на вход формирователя 43 испульсов. Формирователь 43 импульсов формирует импульс, который поступает в тактовый вход блока 54 сравнения. 51 обеспечивая одновременное сравнение кодов5 соответствующих временным интервалам L и Г 4 i В случае если 1 t то на вы1ходе 55 блока 54 сравнения формирует ся импульс, поступающий на входы группы ключей 55 из которыхбудет открыт- только ключ 55-1. Через открытый ключ 55-1 импульс записывается в счетчик 58-1 из группы счетчиков 58 блока 4 формирования рангов, обеспечивая формирование ранга временного интервала. В если то блок 54 сравнения форми г рует импульс на выходе, который поступает на вход ключа 56-2 из группы ключей 56 который был открыт потенциалом с выходом блока 41. Через открытьй ключ 56-2 импульс поступает через элемент ИЛИ 57-2 из группы элементов PfflH 57 на вход счетчика 58-2 обеспечивая тем самым формирование ранга временного интервала. Одновременно импульсы с выхода блока 32 поступают на вход открытог элемента И 31 и через него на вход элемента 30 задержки. С выхода элементов 30 задержки импульсы с запаз дыванием на время L.Q поступают на вход 1 триггера 37, который перебра сывается в состояние 1 и положительным потенциалом , с выхода 1 открывается элемент И 38. Через открытый элемент И 38 :импульсы с генератора 34 поступает на входы счетчика 40, в котором уже было записано число 2. На выходах счетчика 40 последовательно формируются двоичные коды соответствувогцие числам 4,,3, ., ., п, которыеподаютна на входы дешифратора 41, На выходах дешифратора 41 последовательно появляются потенциалы, которые после довательно открывают ключи группы 5 обеспечивая тем самым подачу двоичных кодов, соответствующих измеренкым интервалам входы элемента ИЛИ 53 и через него на входы блока 54 сравнения. В результате временные интервалы , , ° Г последовательно сравниваготся с временным интервалом t . Считывание результатов сравнения осуществляется импульсами, подаваемыми с формирователя 43 импульсов, которые формируются после появления потенциалов на выходах дешифратора 41, Это 4 исключает появление паразитных сигналов на выходах блока 54 сравнения при смене сравниваемых кодов. Таким образом, в случае если (1 - 3., 4, ..., п) импульсы. сформироваиные на выходе 55 блока 54 сравнения, поступают через открытый ключ 55-1 на вход счетчика 58-1, формируя тем самым ранг временного интервала 1 , В том , если i импульсы, сформированные на выходе бло-. ка 54 сравнения, поступают через соответствзтощий ключ 56-i (на схеме не обозначены) и элемент ИЖ 57-i на вход счетчика 58-i, обеспечивая тем самым формирование ранга временного интервала Т Процесс сравнения с f- продолжается до тех пор пока на счетчике 40 не будет записано число п. Результаты сравнения считываются подачей импульса с выхода формирователя 7, в котором формирование производится по переднему фронту импульса, подаваемого с выхода дешифратора 16 через элемент ИЛИ 12. Если ранг г совпадает с рангом медианы г„, то блок 61 сравнения вырабатывает импульс, который подается на входы группы ключей 48 блока 2 измерения временных интервалов, из которых будет открыт только ключ 48-1, так как на другой его вход будет подан положительный потенциал. В результате двоичный код, соответствующий будет повременному интервалу t даваться с выхЪдов счетчика 49-1 через открытый ключ 48-1, элемент ИЛИ 46 в регистр 47, где будут храниться медианы временных интервалов :: , ..., г и при необходимости считываться с выхода устройства. Для определения медианы следующей серии временных интервалов или когда i: ji г работа устройства продолжается. Формирование рангов временных , Iff продолжаинтерваловется до тех пор пока не произойдет совпадение с Г|,. При совпадении (г,- г) блок 61 сравнения формирует импульс, который обеспечивает считывание медианыi)y соответствующего счетчика 48-,i группы счетчиков 48 аналогично изложенному, когда tj, . При этом необходимо учесть, что при г.,- - г все элементы схемы сбрасываются в нулевое состояние и все последующие действия по формированию рангов последующих временных интервалов прекращаются. Таким образом, в соответствии с изложенным медиана может быть определена при неполном переборе всех сравниваемых временных интервалов в отличие от полного перебора, как это делается в известном устройстве, что позвоЛяет сократить время определени медианы в среднем в два раза. Формула изобр. етения 1. Устройство для определения выборочной медианы, содержащее блок измерения интервалов времени, блок попарного сравнения временных интерг валов, блок формирования рангов временных интервалов и блок управления, отличающееся тем, что, с целью повышения быстродействия, в него введены блок формирования ранга медианы и блок сравнения рангов временных интервалов, причем блок управ ления содержит три формирователя импульсов, четыре дешифратора, пять счетчиков, два коммутатора, группу ключей, генератор тактовых импульсов шесть элементов ИЛИ, четьфе элемента И, пять элементов задержки, блок сравнения, регистр памяти, элемент НЕ, три триггера, первый вход первог элемента ИЛИ блока управления является входом Стоп устройства, второй вход первого элемента ИЛИ соединен с выходом первого элемента задержки, а выход - с выходом установки нуля первого триггера блока управления, вход уста- новки в 1 которого является входом Пуск устройства, информационный вход регистра памяти блока управления является входом задания числа временных интервалов устройства, прямой выход первого триггера соединен с первым входом первого элемента И, второй вход которого является входом задания временного интервала устройства, а выход первого элемента И соединен с информационным входом первого счетчика, группа информационных выходов которого соединена с группой входов первого дешифратора, группа выходов которого соединена с группой управляющих входов первого коммута,тора, группа информационных входов которого подключена к одноименной 1 64 группе выходов регистра памяти, а выход - соединен с входами первого формирователя импульсов и элемента НЕ, выход которого соединен с третьим входом первого элемента И, выход первого формирователя импульсов соединен с первым входом второго элемента ИЛИ, входом установки в 1 второго триггера, с первым входом третьего элемента Hnti, и через второй элемент задержки - с вторьм входом третьего элемента ИЛИ, третий вход которого соединен с выходом второго элемента И и подключен к второму входу второго элемента ИЖ, выход которого соединен с информационным входом второго счетчика, группа информационных выходов которого соединена с группой входов второго дешифратора, группа входов которого сое.динена с группой управляющих входов второго коммутатора, группа информационных входов которого соединена с одноименной группой выходов регистра , памяти, а выход - соединен с входом установки в О второго триггера, а через трет1гй элемент задержки - с первым входом четвертого элемента ИЛИ, выход которого соединен с raiформационным входом четвертого счетчгаса, группа информационных выходов которого соединена с группой входов, третьего дешифратора, группа выходов которого соединена с соответствующими входами пятого элемента ИЛИ, выход которого соединен с входом второго формирователя импульсов, выход второго триггера соединен с первыми входами второго и третьего элементов И, выход третьего элемента ИЛИсоединен с информационным входом третьего счетчика и через четвертый элемент задержки - с вторым входом третьего элемента И и управляющими входами ключей группы, выход третьего элемента И через пятый элемент задержки соединен с входом установки в 1 третьего триггера, выход которого соединен с первым входом четвертого элемента И, второй вход которого соединен с выходом генератора тактовых импульсов, а выход - соед1шен с управляющим входом пятого счетчика, группа информационных входов KOToporf соединена с группой выходов ключей группы, группа информационных входов которых соединена с группой информационных выходов третьего счетчика. группа информационных выходов пятог счетчика соединена с группой входов четвертого дешифратора, группа выходов которого соединена с соответств ющими входами шестого элемента ИЛИ, выход которого соединен с входом третьего формирователя импульсов, группа выходов числа временнык инте валов пятого счетчика соединена с первой группой входов блока сравнения, вторая группа входов которого соединен с группой информационных выходов регистра памяти, выход блока сравне ния соединен с выходом установки в О третьего триггера, с вторым вхо дом второго элемента И, с вторым входом четвертого элемента ИЛИ и входом разрешения перезаписи пятого счетчика, блок сравнения рангов вре менных интервалов содержит группу кл10чей, группу элементов PUfli и блок сравнения, выходы ключей группы соединены с соответствующими входами элементов ИЛИ группы, выходы которых соединены с первой группой информационных входов блока сравнения, выход которого является вьпкодом блока сравнения рангов временных интервалов, блок формирования ранга медианы содержит счетчик, ключ делитель, регистр памяти и элемент задержки, группа информационных выходов счетчика соединена с информационными входами ключа, информационные выходы которого соединены с группой входов делимого делителя, группа выходов частного которого соединена с группой информационных входов регистра памяти, выход элемен та задержки соединен с управляющим входом ключа и входом делителя, вход элемента задержки соединен с счетным входом счетчика и подключен к вкгходу первого формирователя импульсов блока управления группа информадион™ ных выходов регистра памяти которого соединена с одноименной группой входов счетчика блока формирования ранга медианы, информационные вьгходы }зегистра памяти которого соединены с второй группой одноименных входов блока сравнения рангов временных интервалов, тактовый вход которого соединен с выходом второго форми:ронателя импульсов блока управления, группа выходов третьего дешифратора которого соединена с управляюш даи нходами вьпссдов соответствующих ключей группы блока сравнения рангов временных интервалов и является первым выходом блока управления, вторым выходом которого является выход генератора тактовых импульсов, группа вьпходоБ четвертого дешифратора является третьим выходом блока управления, четвертым выходом которого является группа выходов второго дешифратора блока управления, пятым выходом которого выход третьего формирователя импульсов, шестым выходом блока управления яйляется группа выходов первого дешифратора блока управления, выход элемента НЕ которого является седьмым выходом блока управления, первый выход блока управления соединен с первым входом блока изменения интервалов времени, второй вход которого соединен с вторым выходом блока управления, третий выход которого соединен и с первым входом блока попарного сравнения временных интервалов, второй вход которого соединен с вторым входом блока попарного сравнения временных интервалор и подключен к четвертому выходу управления, пятый выход которого соединен с третьим входом блока попарного сравнения временных интервалов, шестой выход блока управления соединен с третьим входом блока измерения интервалов времени, четвертьй вход которого соединен с седьмым.выходом блока управления, первый выход блока измерения интервалов времени является выходом устройства, выход блока сравнения рангов временных интервалов соединен с пятым входом блока измерения интервалов времени, второй выход которого соединен с четвертым входом блока попарного сравнения временных интервалов,-первый и второй выходы которого соединены соответственно с третьим и четвертым выходами блока формирования рангов временных интервалов, группа выходов которого соединена с входами соответствующих ключей группы блока сравнения рангов временных интервалов, 2. Устройство по п, 1, отличающееся тем, что., блок измерения интервалов времени содержит первую и BTopjno группы элементов И, элемент И, грзшпу ключей, регистр и группу счетчиков, выход элемента И соединен с первым входом каждого

П

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

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

7076412

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

t5

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

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

&

,п

r/f

Pui.i

%