Устройство для определения характеристик случайного процесса

 

,,SUÄÄ1043665

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

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

РЕСПУБЛИН

y(sg G 06 F 15/36

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

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

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

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

1 (61) 962978 (21) 3414219/18-24 (22) 05.04.82 (46) 23.09.83. Бюл. М 35 (72) В.А.Поляков и P.Ã.Толпарев (53) 681.3(088.8) (56) 1. Авторское свидетельство СССР

1 962978, кл. G 06 F 15/36, 1981 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ХАРАКТЕРИСТИК СЛУЧАЙНОГО ПРОЦЕССА по авт.св. 11 962978, о т л и ч а ющ а е с я тем, что, с целью повыше", ния быстродействия, в него введены счетчик циклов, вход сброса в исходное состояние которого соединен с выходом счетчика числа инверсий, а счетный вход объединен с соответствующими управляющими входами первого и второго коммутаторов и подключен к выходу счетчика импульсов, дополнительный вход которого соединен а выходом счетчика циклов.

104

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

По основному авт.св. В 962978 известно устройство для определе- 10

:ния характеристик случайного процесса, содержащее счетчик импульсов, счетчик числа инверсий, генератор импульсов, группу элементов И, пер- -. вые входы которых объединены, ре- > 15 гистр буферной памяти, схему срав-нения, группу переключателе%, регистр, два коммутатора, группу сумматоров, масштабные усилители и блоки вычитаниЯ, пРичем 20 вход регистра буферной памяти является входом устройства, выход последнего разряда регистра буферной памяти соединен с входом запуска генератора импульсов, а информа- 25 ционный выход регистра буферной г а" мяти соединен с информационным входом регистра, тактовый вход которого соединен с первым выходом генератора импульсов, второй выход которого соединен со входом счетчика импульсов и управляющими входами первого и второго коммутаторов, выходы разрядов регистра соединены с соот ветствующими входами первого коммутатора и вторыми входами элементов группы И, выход первого разряда регистра соединен с первым входом первого переключателя группы, выход

i-ro разряда (i 2,l4 -1 ) соединен со вторым входом (1 -1)-го переключа- 40 теля и первым входом i -го переключателя группы, выход последнего )ц -ro разряда регистра соединен со вторым входом (f4-1 )-го переключателя группы, первый и второй выходы i -го переключателя (i =1, И-1 ) соединены соответственно с входами i-ro u (i +1 )-го разрядов регистра, оба выхода первого коммутатора соединены с соответствующими входами схемы

50 сравнения, выход которой соединен с информационным входом второго коммутатора и с информационным входом счетчика числа инверсий, установочный вход которого соединен с выходом 55 счетчика импульсов, а выход счетчика числа инверсий соединен со входом останова генератора импульсов и с

3665 3 первыми входами элементов И группы

1-й выход (= 1,)4 =1) второго коммутатора соединен с управлюящим входом i-ro переключателя, выходы элементов И группы являютая первой группой выходов устройства, первый и второй входы i.-го блока вычитания группы (t 1, N -1) соединены с выходами i-го и (1 +1)-го элементов

И группы соответственно, выход каждого блока вычитания через соответствующий масштабный усилитель подключен к одному из входов соответствующего сумматора группы, выходы которых являются второй группой выходов устройства, другой вход i-ro сумматора группы (i = l,l4 -1) подключен к выходу 1-г& элемента И группы fl ).

Однако в известном устройстве не до конца использованы возможности заложенного алгоритма упорядочения выборки методом попарных перестановок, что приводит к снижению быстродействия устройства, Целью изобретения является повышение быстродействия.

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

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

7 числа инверсий, схему 8 сравнения, второй коммутатор 9, группу элементов

И 10, блоки 11 вычитания, масштабные усилители 12, сумматоры 13, выходы

14 устройства для определения квантилей, счетчик 15 циклов.

Устройство реализует следующий алгоритм определения квантилей.

На его вход поступает последовательность независимых отсчетов из некоторой генеральной совокупности

3 1

Х,.интегральный закон распределения -Г(х) и плотность вероятности

f (х) которой неизвестны. Мз этой последовательности устройство пери.одически делает выборку из М независимых. значений (х.,х2,...,хп) и перестраивает ее в вариационный ряд т.е. ранжирует в соответствии с условием х (ах 2 j». (x 11... x(g)

Индекс (i) означает номер члена выборки в ранжированном ряду (i

2,...,й).

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

Номер члена выборки в ранжированном ряду (i) позволяет заранее, не зная конкретного значения этого члена вы-. борки х(-)и вида Р(х) достаточно точно оценить соответствующую ему величину F(x,-1) = Р; по выражению

043665 4, ствовать искомому квантилю. Для опре". деления. более точного значения необходима интерполяция между ближайшими меньшим и большим членами .выборки. Доля интерполяции подсчитывается заранее по разности выражений (2) и (3):

10 л (i) (1)

Конкретное значение члена выборки х(;1получается после ранжирования.

Таким образом, в совокупности обеспечивается вся необходимая для формирования квантиля х(;) информация.

Из выражения (1) очевидно, что при on ределении ква нтилей х Р, соответствующих заданным значениям вероятностей Pf (j = 1,2...,k) при известном объеме выборки М, можно заранее определить номера членов вйборки в ранжировочном ряду (I) которые соответствуют искомым квантилям. Приравняв . (i).

М+4 1 получим ((1 I.7=P. (N+1), (3) где t. ) - целая часть от (i).

Однако конкретное значение члена выборки с номером, определенным таким образом, не будет точно соответ(1).=Р. ()+ ) . (u)

В связи с тем, что заданные значения могут быть любыми, величина ()); может быть нецелочисленной.

Поскольку дробных номеров выборки не бывает, определяют ближайший меньший номер члена выборки в pawжированном ряду. Для этого необходимо взять целую часть от выражения (2):

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

15 Р, можно определить из выражения

Х(, = )(.) „-Х „ Д.+Х .. ($) Выражение (5) представляет обоб20 щенныи алгоритм работы определителя квантилей, обеспечивающих заданный уровень вероятности Р .

Из выражения (5) следует, что для определения квантиля х(,1, соответствующего заранее заданному уровню вероятности P при известном объеме выборки М, можно и необходимо с помощью выражени «2)-(4) заранее рас.считать номера j(i ))), (()-) + 1 разрядов регистра, содержащего ранжированную выборку и долю интерполяции между ними Д).

Извлекая после ранжирования вы-. борки из. рязрядов конкретные значения

35 х . этих членов выборки Г().1+ (1) 4 и производя интерполяцию в соответтвии с выражением (5), получим искомое значение квантиля х<,. -. В том

9 случае, когда из выражения (2) сразу получается целочисленное значение номера члена выборки в ранжированном ряду (i), то clj = О и из (5) следует, что искомое значение квантиля х, можно получить прямо из разряда (il7 с номером (i ) регистра с ранжироfÄ ванной выборкой.

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

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

На вход регистра 1 буферной памяти

55 с определенной скоростью поступает последовательность независимых отсчетов из некоторой генеральной сово" ( купности х, интегральный закон рас-, где

S 10 пределения Г1х) и плотность вероят-, ности т(х) которой неизвестны.

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

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

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

5, переключателей 3 и соответствую" щих им входах каждого из элементов

И группы.

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

9 и на вход счетчика 6 импульсов.

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

Процедура ранжировки основана на алгоритме попарной перестановки.

При первом: просмотре каждое зяачение выборки х 1 сравнивается с соседним значением х . Пара значений выборки, для которйх справедливо неравенство х х +„, меняется местами.

Таким образом, уже в первом цикле просмотра и попарных сравнений член выборки иэ Й"элементов, имеющий наибольшее значение, займет крайнее место х() в ранжированном ряду, и необходимость сравнения с ним в по43665 следующих циклах непосредственно . предшествующих ему членов отпадает.

Аналогично во втором цикле npo" смотра надлежащее ему место займет второй по величине член выборки

x(g<), и необходимость сравнения с ним в третьем и последующих циклах непосредственно предшествующих ему членов также отпадает. То же

10 справедливо для х < 2), х (g 3j и т.д., начиная с соответствующих им номеров циклов просмотра, и далее.

Попарное сравнение и перестановка членов выборки продолжается до тех

15 пор,пока не. закончится процесс ранжирования выборки, т.е. х< 1(х< (.; .4 х<,.1(° . (х(„ ).

Факт выполнения неравенства х > х +„ при попарном просмотре вы20 борки является инверсией, а функция суммы инверсий определяется выражением

Й-1 ь = U(Х,, Х. ), (6) Значение с вычисляется при каждом ,цикле попарного сравнения и перестановок членов выборки. Признаком окон чания ранжировки выборки является значение «(1, сосчитанное за цикл просмотра.

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

Кроме того, признаком окончания ранжировки в известном устройстве принято выполнение условия, когда значение суммы инверсий Т = О, хотя

55 реально ранжирование практически всегда заканчивается при ь = 1. И лишь в единственном случае, когда члены выборки без ранжировки случайным образом сами расположатся в нуж65 8

10436

7 ном порядке, сумма инверсий сразу примет значение ь= О.

В результате проведения в каждом цикле попарных сравнений- в уже ранЖированной части выборки и необхо- 5 димости .обязательного выполнения условия .. Т 0 часть времени работы известного устройства затрачивается неэффективно, что и снижает быстро= действие его работы. !О

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

Известное устройство в каждом цикле просмотра выборки йз М элементов производят Й - 1 попарных сравнений. Таких циклов для обеспечения 20 ь = 0 необходимо й. Таким образом, в рассматриваемом случае известное устройство произведет й(й-1) попарных сравнений.

Предлагаемое устройство, с учетом 25 устранения недостатков в первом цикле просмотра произведет й-1 по" парных сравнений, во втором цикле(N-2) лопарных сравнения, в третьем (й-3) и .т.д.,вплоть до последнего З0 цикла, на котором ранжировка закан- чивается и в котором будет всего одно попарное сравнение. Всего в рассматриваемом случае предлагаемое устройство произведет 1+2+...+N-1

= N(N"1) попарных сравнений. В результате в указанном случае по числу понарных сравнений будет получен выигрыш в 2 раза. 40

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

Алгоритм ранжировки выборки реализуется следующим образом. .50

В каждом цикле просмотра первый коммутатор 5 в такт синхроимпульсам производит последовательное подсоединение информационных выходов каждой соседней пары разрядов регистра 4 к двум входам схемы 8 сравнения.

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

-нения выдает значение инверсии 0(Х,", х . (в виде "0" или "1".

Эти значения поступают в счетчик

7 числа инверсий, который в соответствии с.выражением (6) определяет сумму инверсий ь за каждый цикл просмотра. Одновременно каждое значение инверсии поступает на вход вто-: рого коммутатора 9.

Работая синхронно с первым ком мутатором 5, второй коммутатор 9 попоследовательно соединяет выход схемы 8 сравнения со входом того переключателя 3, который своими другими двумя входами, а также .двумя выходами соединен соответственно с информационными выходами и информационными входами каждого из пары раз рядов регистра 4, содержимое которых анализировалось схемой 8. сравге-! ния. Одновременно второй коммутатор

Я, чтобы не усложнялась конструкция,. переключателей 3, преобразует поступившее на его вход значение

U(x;, x ..+„ ) =. 0 в значение на своем выходе 1", оставлял неизменным зна чение U(x;, x„+., ) = 1.

Переключатель 3 соединяет подклю ченные к нему информационные выходы сравниваемой пары соседних разрядов со своими выходами таким образом, чтобы при U(x, x +„ ) = 0 на входе второго коммутатора 9 содержимое сравниваемых разрядов регистра осталось неизменным, а при U (x>, х 1 „: )"

1 — поменялось местами путем йе" . реписывания из одного разряда в другой. Затем переключатель 3 возвращается в нейтральное положение.

Конец каждого цикла просмотра определяется с помощью счетчика 6 импульсов и счетчика 15 циклов. В первом цикле просмотра счетчик 6 импульсов отсчитывают N-1 импульс из последовательности синхроимпульсов, поступающих на его вход из генератора 2 импульсов (N - объем выборки) .

Этим определяется граница первого цикла. В результате осуещствляется однократное попарное сравнение и перестановка в соответствии с принятым алгоритмом всех членов выборки, содержащихся в регистре 4.

1, Если при этом за цикл счетчик

7 числа инверсий получит Г el, то осуществляется переход ко второму циклу просмотра. При Т >1 потенциал, подаваемый на управляющие входы гене 9 10436 ратора 2 импульсов и группы элемен- тов И 10 с выхода счетчика 7 числа инверсий, не меняется. Поэтому генератор 2 импульсов продолжает выдавать последовательность синхроимпульсов для управления коммутаторами 5 и 9, в группа элементов И 10 продолжает оставаться запертой, не разрешая выдачу информации, установленной на их входах, для дальнейшего использова.10 ния. Счетчик б импульсов, закончив счет до N-1, своим выходным сигналом сбрасывает в исходное состояние счетчик 7 числа инверсий и возвращает в исходное состояние первый коммута- 15 тор 5 и второй коммутатор 9, так что каждый очередной цикл просмотра будет начинаться с одних и тех же разрядов регистра 4. Одновременно счетчик

6 импульсов своим выходным сигна- 20 лом записывает "1" в счетчик 15 циклов.

Счетик 15 циклов передает записан ную в нем сумму (в данном случае "1"7 на второй вход счетчика 6 импульсов, где эта сумма вычитается из записанного там установочного числа, до которого должен считать счетчик 6 импульсов. В результате количество попарных сравнений членов выборки во 30 втором цикле просмотра уменьшится на "1нф до N-2,и самый большой член выборки в ранжированном ряду, уже занявший в первом цикле просмотра крайнее место,в попарном сравнении во втором и последующих циклах просмотра принимать участие не будет, так как первый коммутатор 5 и второй коммутатор 9 произведут до своего возвращения на исходные позиции 40 меньшее количество переключений.

Циклы просмотра с уменьшением числа попарных сравне1(и)1 íà 1 в каждом очередном цикле продолжаются до тех пор, пока выполняется усло- 45 вие 7 > 1. При т 4 1 счетчик 7 числа

О инверсий своим выходным сигналом пре" кращает подачу, синхроимпульсов генератором 2 импульсов, сбрасывает в исходное состояние счетчик 15 циклов и отпирает элементы И 10. Этот момент соответствует формированию на входах элементов И 10 ранжированной выборки ((1) (2) " ii) " )4(i

В соответствии с ранее описанным алгоритмом определения квантилей искомые значения квантилей х(i); поступают на выходы 14 устройства либо непосредственно с выхода элементов

И 10 с заранее известным номером (i); либо поступают на выход 14 после интерполяции.

Интерполяция, уточняющая искомое .значение квантиля, производится в соответствии с-выражением (5) следующим образом. Через элементы И 10 с заранее известными номерами (()) 1, (()))+1 Информация с их выходов поступает на два входа одного из блоков 11 вычитания. Кроме того, выход элемента И 10 с номером

f(i);) соединен с одним из входов сумматора 1.3, входящего в данную цепочку интерполяции.

В блоке 11 вычитания определяется

) ) (i1 1

Разность поступает в масштабный

-усилитель 12, входящий в данную цепочку интерполяции. В масштабном ,усилителе 12, полученная разность умножается на заранее известную долю, интерполяции. 11.

Произведение из масштабного усилителя 12 поступает на другой вход сумматора 13, где складывается с выходной информацией (i) -го элемента

И 10, равной x p )

1 j

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

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

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

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

ВНННпМ Заказ 7340/53 Тираж 706 Подписное

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4