Устройство для определения характеристик случайного процесса Советский патент 1982 года по МПК G06F17/18 

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК СЛУЧАЙНОГО.ПРОЦЕССА

Изобретение .относится к специали зированным средствам вычислительной техники и может найти применение при определении статистических характе ж.стик случайных величин. Устройство предназначено для определения квантилей при произвольном неизвестном распределении случайных величин. Известно устройство для вычисления статистических моментов случайных процессов, содержащее центрующий фильтр, два умножителя, два квадратрра, интегратор и два усреднителя II . Это устройство позволяет определить третий и четвертый центральные моменты случайного процесса, но не позволяет определить квантили распределения. Наиболее близким ни нс значению и технической сущности к предлагаем му является устройство определения квантиля, которое определяет выборо ную медиану, содержащее два счетчика, блок элементов И, два триггера, дифференцирующий элемент,. два генератора импульсовf три элемента И, элемент НЕ 2j. Недостатком прототипа является ограниченность решаемых им задач. Он может определить только один квантиль - выборочную медиану, что снижает эффективность устройств, в которых он используется. Цель изобретения - расширение функциональных возможностей путем определения заранее заданного числа требуемых квантилей. Поставленная цель достигается тем, что в устройство, содержащее счетчик импульсов, счетчик числа инверсий, генератор импульсов,: группу элементов И, п1ервые входы которых объединены.дополнительно введены регистр буферной памяти, группа переключателей, регистр, схема сравнения, два коммутатора, группы сумматоров , масштабных усилителей и блоков вычитания, причем вход регистра буферной памдти является входом устройства, выход разряда регистра буферной памяти соединен с входом запуска генератора импульсов, а информационный выход регистра буферной памяти соединен с информационным входом регистра, тактовый вход которого соединен с первым выходом генератора импульсов, второй выход которого соединен с входом счетчика импульсов,управляющими входами первог и второго коммутаторов, информационные выход -л каждого регистра соединены с соответствующими им входами первого коммутатора и ключей первыми входами элементов И группы, выход первого разряда регистра соеди нен с первым входом первого переклю чателя группы, информационный выход i-ro разряда (i 2, N--1) соединен с вторьв входом ()ro переключателя и первым-входом i-ro переключа ,теля группы, выход последнего N-ro разряда регистра соединен с вторым входом (N-l)-ro переключателя группы, первый и второй выходы i-ro переключателя (i 1 , N-1) соединены соответственно с входа.ми i-ro и fi+l)-ro разрядов регистра, оба выхода первого KOMiviyTaTopa соединены с с соответствующими входами схемы сравнения, выход которой соединен с информационным входом второго коммутатора и с информационным входом счетчика числа инверсий, установочный вход которого соедин.ен с выходом счетчика импульсов, а выход счетчика числа инверсий соединен с входом останова генератора импульсов и с вторыми входами элементов ,И группы, i-й выход (i 1, N-1) второго коммутатора соединен с управляющим входом i-ro переключателя, выходы, элементов И группы являются первой груп пой выходов устройства, первый и второй входы i-ro блока вычитания группы (i 1, N-1} соединены с выходами i-ro и Cil)ro элементов И группы соответственно, выход каждого блока вычитания через соответствую,щий масштабный усилитель подключен к одному из входов соответствующего сумматора группы, выходы которых являются второй группой выходов устройства, другой вход i-ro сумматора группыЦ 1, N-1) подключен к выходу i-ro элемента И группы. На чертеже приведена структурная схема устройства для определения характеристик случайного процесса. Устройство содержит регистр 1 буферной памяти, генератор 2 импульсов, переключатели 3, регистр 4, первый коммутатор 5, счетчик 6 им- пульсов, счетчик 7 числа инверсий, схему 8, сравнения, второй ко 1мутатор 9, группу элементов И 10, блоки 11 вычитания, масштабные усилители 12, сумматоры 13, выходы 14 устройства для определения квантилей. Устройство реализует следующий алгоритм определения квантилей. На его вход поступает последовательност независимых отсчетов из некоторой генеральной совокупности х, интегральный закон распределения Р(х) и ллотность вероятности f(х) которой неизвестны. Из этой последовательности устройство для определения квантилей периодически делает выборку из N независимых значений (х , х,, .. и перестраивает ее в вариационный ряд, т.е. ранжирует в соответст; ви|{ с условием Х(7 . , . . . ёХ(7 « NJ- Индекс i означает номер член а выборки .в ранжированном ряду Ci 1,2,..,,N). Известно., что ранжированная выборка обладает особыми св.ойствами. Номер члена выборки в ранжированном ряду i позволяет заранее, не зная конкретного значения этого члена выборки Х(-)И вида F(x) , достаточно точно оценить соответствующую ему величину F(x.) Р по выражению (i) F(X(-7) - Р; j,T,-T . Конкретное значение члена выборки X/.-J получается после ранжирования. Таким образом, в совокупности обеспечивается вся Необходимая для формирования квантиля Хр информация. Из выражения .(1) очевидно, что при определении квантилей х-, соответствующих заданным -значениям, ве-. роятностей Р; (J 1,2,...,k), при известном объеме выборки N можно з.аранее определить номера членов выборки в ранжированном ряду (i , которые соответствуют искомым квантилям. Приравняв получим (i)/ Р.| CN-M (2) в связи с тем, что заданные значения Р; могут быть любЬ1МИ, величина (i),j может быть негХелочисленной. Поскольку дробных номеров, выборки не бывает, определяют ближайший меньший номер члена выборки в ранжированном ряду. Для этого необходимо взять целую часть от выражения (2) (i). P -CN+I, (3 где Е3 означает целую часть от . (i). . однако конкретное значе.ние члена выборки с номером, определенным таким образом, не будет т.очно соответствовать искомог у квантилю. Для определения более точного значения необходима интерполяция между ближайщими меньшим и большим членами выборки. Доля интерполяции подсчитывается заранее по разности выражений (2) и (.3). Af C.i,j - E(i)/l

Тогда уточненное- с учетом интерполяции значение квантиля, соответствующее заданному уровню вероятности Р; , можно определить из выражения

U); (ШР - %)

Выражение (5) представляет обобщенный алгоритм работы определителя квантилей, обеспечивающих заданный уровень вероятности Р; .

Из выражения (5) следует, что для определения квантиля х) , соответствующего заранее заданному уровню вероятности Р; при. известном объеме выборки N, можно и необходимо с помощью выражени й (2)-(4) заранее рассчитать номера , ,С(х )j J 1 разрядов регистра, содержащего, ранжированную выборку, и долю интерполяции .между ними &.J.

Извл.екая после ранжирования выборки из этих разрядов конкретные значения членов выборки х ) 1 X Г( i)j 1 и лроизйрдя интерполяцию в соответЬтвии с выражением (5), получаем искомое значение квантиля ху). , В том случае, когда из выражения. (2) сразу получается целочисленное значение номера члена выборки в ранжированном ряду ,и из (5) следует, что искомое значение квантиля X(i)j-можно получить прямо, из. разряда е номером (i) , регистра с ранжированной выборкой.

Количество выводо.в с интерполяцией и без интерполяции за.висит от заданных уровней вероятности Р; искомых квантилей.

Этот алгоритм реализован в устройстве для определения квантилей следующим образом. На вход регистра 1 буферной памяти с определенной скоростью поступает последовательность независимых отсчетов из некоторой генеральной совокупности х .интегральный закон распределения F(x) и плотность вероятности f(x) которой неизвестны.

Регистр 1 буферной памяти после заполнения выдает сигнал в генератор 2 импульсов. По этому сигналу генератор 2 импульсов выдает на тактовый йход регистра 4 пачку из N импульсов. Под воздействием тактовых импульсов значения последовательности из р.егистра 1 буферной памяти последовательно поступают через информационный вход в регистр 4 объемом N разрядов. Таким образом, в основном регистре 4 образуется неI упорядоченная выборка из значений

С J i . , . . . , ,

Частота следования тактовых имгпульсов выбирается таким .образом, чтобы согласовать скорость поступления исходной последовательности-на вход регистра 1 буф.ерной памяти со

скоростью записи выборки в регистр 4 и скоростью ее обработки. Значения выборки одновременно с записью в регистре 4 через информационные выходы каждого разряда регистра 4

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

Генератор 2 импульсов, закончив выдачу пачки из N тактовых импульсов начинает выдавать непрерывную послеовательность синхроимпульсов, поступающих на синхровходы первого

коммутатора 5, второго коммутатора 9 и на вход счетчика 6.

Под воздействием последовательности синхроимпульсов и в такт с. нии начинается процедура упорядочения (ранжирования), выборки. Частота следования синхроимпульсов выбирается такой, чтобы максимально сократить время ранжировки выборки.

Процедура ранжировки основана на

алгоритме попарной перестановки.

При первом просмотре каждой значение выборки сравнивается с соседним значением . Пара значений выборки, для котррых справедливо неравенство 7 , меняются местами. Таким образом, член выборки, имеющий наибольшее значение, уже при первом просмотре займет место X(j) . Попарное сравнение и перестановка членов выборки продолжается до тех пор, пока не закончится процесс ранжировки выборки, т.е. X (х. . S . .. X(N) . .

Факт выпрлнения неравенства 7 при попарном просмотре выоорки является инверсией, а функция суммы инверсий определяется выражением

. .

U(x. , х) О, X, - х. .

Значение Т вычисляется при каждрм Цикле попарного сравнения и перестановки членов выборки. Признаком окончания ранжировки выборки является значение Г 0.

Покажем на простом числовом приере, что алгоритм попарной перестановки приводит к ранжированию выборки. Пусть члены неупорядоченной выборки объема N 4 приняли следующие значения 1, 4, 3, 2.

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

Просмотр Из приведенного числового примера видно, что ранжировка выборки закончилась на втором цикле просмот ра, но чтобы убедиться в этсм потре бовалось провести третий цикл, так как во втором цикле С О, Алгоритм ранжировки выборки реал зуется следующим образом. Первый коммутатор 5 в такт с синхроимпульсами производит последо вательное подсоединение информацион ных выходов калсцой соседней пары разрядов основного регистра 4 к дву входам схемы 8 сравнения, В результате сравнения каждой пары соседних .членов выборки схема 8 сравнения вы дает значение инверсии U(x-, х ,.) в виде О или 1. Эти значения поступают в счетчик 7 числа инверсий, в соответствии с выражением (6) определяет сумму ийверсий tr за каждый цикл просмотра. Одновременно каждое значение инверсии поступает на вход второго комму татора 9. Работая синхронно с первым комму татором 5, второй коммутатор 9 посл довательно соединяет выход схемы 8 сравнения со входом того переключателя 3, который своими другими двумя входами, а также двумя выходами соединен соответственно с информационными выходами и инфо ч ационными входами каждого из пары разрядов регистра 4, содержимое которых анализировалось схемой 8 сравнения. Одновременно второй коммутатор 9, чтобы не усложнялась конструкция переключателей 3, преобразует поступившее на его вход значение U(x , ) О в значение на своем выходе -1, оставляя неизменным значение U{x, х..) 1. Переключатель 3 соединяет подключенные к нему информационные выходы сравниваемой пары соседних разрядов к своим выходам таким образом, чтобы при U{x , ) О на входе второго коммутатора 9 содержимое сравниваемых разрядов регистра осталось неизменным, а при- U(, ) 1 поменялось местами путем переписывания из одного разряда в другой. Затем переключатель 3 возвращают в нейтральное положение. В конце цикла просмотра, благодаря указанной вчпие работе коммутаторов 5 и 9, схепы 8 сравнения и группы переключателей 3, будет осуществляться однократное попарное сравнение и перестановка в соответствии с принятым алгоритмом всех членов выборки, содержащихся: в регистре- 4. Счетчик 7 инверсий сосчитает количество инверсий за цикл ив случае 177 О не препятствует генератору 2 импульсов продолжать выдавать последовательность синхроимпульсов для управления коммутаторами 5 и 9. Кроме того, при счетчик 7 числа инверсий, подавая н.а входы элементов И 10 группы тот же потенциал, что и на вход генератора 2 импульсов, запирает их- и не.разрещает выдачу информации, установленной на их входах для дальнейшего использования в целях формирования собственно квантилей. В конце просмотра счетчик 7 числа инверсий устанавливается в исход ное состояние счетчиком 6 импульсов, отсчитавшим N-1 синхроимпульсов, необходимых для выполнения одного цикла. Циклы просмотра продолжаются до тех пор, пока выполняется условие 070. При Т - о счетчик 7 числа инверсий прекращает подачу синхроимпульсов генератором 2 импульсов и отпирает элементы И 10. Этот момент соответствует формированию на входах элементов И 10 ранжированной выработки XCD , Х(.,), в соответствии с ранее описанным алгоритмом определения квантилей, искомые значения квантилей X(i)j поступают на выходы 14 определителя квантилей либо непосредственно с выхода элементов И 10 с заранее известным номером i) , либр поступаю на выход 14 после интерполяции. , Интерполяция, уточняютлая искомое значение квантиля, производится в с ответствии с выражением (5) следующим образом. Через элементы И 10 с заранее известными номерами (i), t(i)i информация с их выходов поступает на два входа одного из блоков 11 вычитания. Кроме того, вы ход элемента И 10 с .номером (i),j соединен с одним из. входов сумматора 13, входящего в данную цепочку .интерполяции. В блоке. 11 вычитания определяетс xTCDj + 1 - x(i)J. Разность поступает в масштабный усилитель 12, входящий.в данную цепочку интерполяции. .В масштабном усилителе 12 полученная разность умножается на заранее известную долю интер.поляции. 11рои.зведение из мабштабного усил теля 12 поступает на другой вход сумматора 13, где складывается с выходной информацией (i)- -го элемен та И 10 , ра.вной X {i); . На выходесумматора 13, являюще17ОСЯ однимИЗ интерполяционных выходов 14 устройства для определения :.квантилей, получается уточненное по необходимости интерполяцией- .значет ниб1 другого искомого квантиля. С выходов -14 устройства для опре деления квантилей значения квантилей, определенные по данной выборке и соответствующие заданным уровням вероятностей, поступают на входы других технических устройств для использования. .Затем процесс повторяется для новых- значений выборки. Таким образом, благодаря введени в прототип ряда новьрс блоков, дости гается цель изобретения - расшире- ние функциональных возможностей за счет определения заранее заданного числа требуемых квантилей. Главным техническим преимуществом предлагаемого устройства по сравнению с известным техническим решением являютсябол ее игирокие функциональные возмохщости за счет определения заранее заданного числа требуемых квантилей. Формула изобретения Устройство для определения харак теристик .случайного процесса, содержбвдее счетчик импульсов, счетчик числа инверсий, генератор импульсов, группу элементов И, первые входы которых объединены, отличающ.ее с я тем, что, с целью расширения функциональных возможностей путем определения заранее заданного числа требуемых квантилей, в него дополнительно введены- регистр буферной памяти, схема сравнения, группа переключателей, регистр, два коммутатора, группы сумматоров, масштабных усилителей и блоков вычитания, причем вход регистра буферной памяти является входом устройства, выход последнего разряда регистра буферной памяти соединен с входом запуска генератора импульсов, а информационный выход регистра буферной памяти соединен с информационным входом.регистра, тактовый вход которого соединен с первым выходом генератора импульсов, второй выход которого соединен с входом счетчика импульсов и управляющими входами первого и вторрго коммутаторов, выходы разрядов регистра соединены, с соответствующими входами первого коммутатора и первыми входами элементов И группы, выход первого разряда реги- . стра соединен с первым входом первого переключателя -группы, выход i-ro разряда (i 2, N-1) соединен с-вторым входом Ci-l)-ro п реключателя и первым входом i-ro переключателя группы., выход последнего N-ro разряда регистра соединен с вторым входом (N-l)-ro переключателя группы, первый и второй-выходы i-ro переключателя (i . 1, N-l) соединены соответственно с -входами 1т-го и (i+l)-ro разрядов регистра, оба выхода первого коммутатора соединены с соответствующими входами схемы сравнения, выход которой соединен с информационным входом второго коммутатора и с информационны - входом счетчика числа инверсий, установочный вход которого соединен с выходом счетчика импульсОв, а выход счетчика числа инверсий соединен с входом останова генератора импульсов и с вторыми входам.и элементов И группы, i-й выход (i 1, N-1) второго коммутатора соединен с управляющим входом i-ro переключателя, выходы элементов И группы являются первой группой выходов устройства, первый и второй входы 1-го блока вычитания группы (i 1, N-1 соединены с вы. ходами i-ro и (i + l)-io элементов И группы соответственно, выход каждого блока вычитания через соответствующий масштабный усилитель подключен к одному из входоЁ соответствующего сумматора группы, -выходы KOTOE JX являются второй группой выходов устройства, другой вход i-ro cy мaтopa

группы (, N-1} подключен к выходу i-ro элемента И группы.

Источники информации, принятые во внимание при экспертизе

2,Авторское свидетельство СССР №744606, кл. G Q6 F 15/36, 1977 (прототип)о