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

.,80.10436 зло 15/36 ОПИСАНИЕ ИЗОБРЕТЕН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и ия че ое ых че во ССС981 вог чен пол а в ЕЛЕНИЕССА ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54)(57) УСТРОЙСТВО ДЛЯ ОПРЕДХАРАКТЕРИСТИК СЛУЧАЙНОГО ПРОЦ вт.св. 11 962978, о т л и ч а юе с я тем, что, с целью повыше", быстродействия, в него введены чик циклов, вход сброса в исход" состояние которого соединен с дом счетчика числа инверсий, а ный вход объединен с соответющими управляющими входами пери второго коммутаторов и подклюк выходу счетчика импульсов, доительный вход которого соединен ходом счетчика циклов.1Изобретение относится к специализированным средствам вычислительнойтехники.и может найти применениепри определении статистических характеристик случайных величин, конкретнее для определения квантилейпри произвольном неизвестном распределении случайных величин,По основному авт,св. И 962978известно устройство для определе:ния характеристик случайного процесса, содержащее счетчик импульсов,счетчик числа инверсий, генераторимпульсов, группу элементов И, пер-вые входы которых объединейы, регистр буферной памяти, схему сравнения, группу переключателе%, регистр, два коммутатора, группусумматоров, масштабные усилителии блои вычитания, причемвход регистра буферной памяти является входом устройства, выходпоследнего разряда регистра буферной памяти соединен с входом запуска генератора импульсов, а информационный выход регистра буферной памяти соединен с информационным входом регистра, тактовый вход которогосоединен с первым выходом генератора импульсов, второй выход которого соединен со входом счетчика импульсов и управляющими входами первого и второго коммутаторов, выходыразрядов регистра соединены с соот"ветствующими входами первого коммутатора и вторыми входами элементовгруппы И, выход первого разряда регистра соединен с первым входомПервого переключателя группы, выход1-го разряда (1 2, Й -1 ) соединенсо вторым входом 1 -1)-го переключателя и первым входом 1 -го переключателя группы, выход последнего М -горазряда регистра соединен со вторымвходом 8-1 )-го переключателя группы,первый и второй выходы 1 -го переключателя 1 =1, И) соединены соответственно с входами 1-го и1+1 )-го разрядов регистра, оба выхода первого коммутатора соединеныс соответствующими входами схемысравнения, выход которой соединенс информационным входом второго коммутатора и с информационным входомсчетчика числа инверсий, установочныйвход которого соединен с выходомсчетчика импульсов, а выход счетчикачисла инверсий соединен со входомостанова генератора импульсов и с1043665 3 первыми входами элементов И группы1-й выход 1 = 1,)4 1) второго коммутатора соединен с управлюящим входом .1-го переключателя, выходы элементов И группы являютая первойгруппой выходов устройства, первыйи второй входы 1.-го блока вычитаниягруппы (1 1, )Ч -1) соединены с выходами 1-го и (1 +1)-го элементовИ группы соответственно, выход каж 5 10 дого блока вычитания через соответствующий масштабный усилитель подключен к одному из входов соответствующего сумматора группы, выходыкоторых являются второй группой вы 15 ходов устройства, другой вход 1-го сумматора группы (1 = 1, И -1) подключен к выходу 1-г 9 элемента Игруппы 1,).Однако в известном устройстве не 20 до конца использованы возможности за. ложенного алгоритма упорядочения выборки методом попарных перестановок,что приводит к снижению быстродействия устройства,25 Целью изобретения является повыше.ние быстродействия,З 0 Эта цель достигается тем, чтоустройство для определения характеристик случайного процесса дополнительно содержит счетчик циклов, входсброса в исходное состояние которого35соединен с выходом счетчика чмсла инверсий,а счетный вход объединен с соответствующими управляющими входами первого и второго коммутаторов и подключен к выходу счетчика импульсов, до 40 полнительный вход которого соединенс выходом счетчика циклов.На чертеже приведена структурнаясхема устройства для определения характеристик случайного процесса.Схема включает регистр 1 буфернойпамяти, генератор 2 импульсов, переключатели 3, регистр 4, первый коммутатор 5, счетчик 6 импульсов, счетчикчисла инверсий, схему 8 сравнения,второи коммутатор 9, группу элементов50И 10, блоки 11 вычитания, масштабныеусилители 12, сумматоры 13, выходы14 устройства для определения квантилей, счетчик 15 циклов.Устройство реализует следующийалгоритм определения квантилей.На его вход поступает последовательность независимых отсчетовиз некоторой генеральной совокупности3 1 Хинтегральный закон распределения .Г(х) и плотность вероятности т(х) которой неизвестны. Из этой последовательности устройство периодически делает выборку из М независимых.значений (хх 2хп) и перестраивает ее в вариационный ряд т.е. ранжирует в соответствии с условием х(г х(2)Фс х 1 с "ОХОЧ Индекс ( означает номер члена выборки в ранжированном ряду (1 = 1, 2М).Известно, что ранжированная выборка обладает особыми свойствами. Номер члена выборки в ранжированном ряду (1) позволяет заранее, не зная конкретного значения этого члена вы-. борки х(.)и вида Р(х) достаточно точно оценить соответствующую ему величину Г(х ;1) = Р; по выражению 043665 4, ствовать искомому квантилю. Для опре"деления. более точного значения необходима интерполяция между ближайшими меньшим и большим членами ,выборки. Доля интерполяции подсчиты" вается заранее по разности выражений (2) и (3): й.д(1). -1.1. (Ф.1.) 0 л (11 (1) Конкретное значение члена выборки х(;1 получается после ранжирования. Таким образом, в совокупности обеспечивается вся необходимая для формирования квантиля х(;) информация.Из выражения (1) очевидно, что при оп ределении ква нтилей х р, соответствующих заданным значениям вероятностей Р= 1,2,к) при известном объеме выборки М, можно заранееопределить номера членов вйборки в ранжировочном ряду (1) которые соответствуют искомым квантилям. Приравняв. (1)8+4 1 получим где Гф 3 - целая часть от (1),Однако конкретное значение члена выборки с номером, определенным таким образом, не будет точно соответ(1). = Р, (М+1), (р)3В связи с тем, что заданные значения могут быть любыми, величина (; может быть нецелочисленной. Поскольку дробных номеров выборки не бывает, определяют ближайший меньший номер члена выборки в ранжированном ряду, Для этого необходимо взять целую часть от выражения (2): Тогда уточненное с учетом интерполяции значение квантиля, соответствующее заданному уровню вероятности 15 Р;, можно определить из выражения Выражение (5) представляет обоб 20щенныи алгоритм работы определителяквантилей, обеспечивающих заданныйуровень вероятности Р,Из выражения (5) следует, что дляопределения квантиля х(,1), соответствующего заранее заданному уровнювероятности Р при известном объемевыборки М, можно и необходимо с помощью выражений (2)-(ч) заранее рас.считать номера ) (1) , (1 ) ) + 1разрядов регистра, содержащего ранжированную выборку и долю интерполяции между ними Д).Извлекая после ранжирования вы-.борки из.рязрядов конкретные значения35 х х.этих членов выборки Г,ф(1)и производя интерполяцию в соответтвии с выражением (5), получим искомое значение квантиля х; . В том3случае, когда из выражения (2) сразу получается целочисленное значениеномера члена выборки в ранжированномряду (, то й 1 = 0 и из (5) следует, что искомое значение квантилях , можно получить прямо из разряда(111с номером ( регистра с ранжиро 3ванной выборкой,Количество выводов с интерполяцией и без интерполяции зависит от заданных уровней вероятности Р искомыхквантилей.Этот алгоритм реализован в устройстве следующим образом.На вход регистра 1 буферной памяти55 с определенной скоростью поступает последовательность независимых отсчетов из некоторой генеральной сово"купности х, интегральный закон рас-,65 8 10436 7ном порядке, сумма инверсий сразу примет значение ь = О.В результате проведения в каждом цикле попарных сравнений. в уже ранжированной части выборки и необхо димости .обязательного выполнения условияТд 0 часть времени работы известного устройства затрачивается неэффективно, что и снижает быстро= действие его работы. ЮВовьмеж один из наиболее показательных случаев случайного первичного расположения членов выборки, ког- да они расположены в порядке, точно обратном тому, который должен быть. 15 получен в результате ранжировки.Известное устройство в каждом цикле просмотра выборки Йз М элементов производят Й - 1 попарных сравнений. Таких циклов для обеспечения 20 ь = 0 необходимо М. Таким образом, в рассматриваемом случае известное устройство произведет М(Й) попарных сравнений.Предлагаемое устройство, с учетом 25 устранения недостатков в первом циклепросмотра произведет Йпо" парных сравнений, во втором цикле- (Й) лопарных сравнения, в третьем (Й) и .т.д.,вплоть до последнего 30 цикла, на котором ранжировка закан-чивается и в котором будет всего од.но попарное сравнение. Всего в рассматриваемом случае предлагаемое устройство произведет 1+2Й= М(М) попарных сравнений. В результате в указанном случае по числу попарных сравнений будет получен выигрыш в 2 раза. аоИзвестно, что количество необходимых операций в методе ранжировки путем попарных перестановок зависит от исходного порядка расположения членов выборки. Поэтому в среднем выигрыш в количестве операций будет существенным, но меньше, чем в рассмотренном случае,Алгоритм ранжировки выборки реализуется следующим образом..50В каждом цикле просмотра первый коммутатор 5 в такт синхроимпульсам производит последовательное подсоединение информационных выходов каждой соседней пары разрядов регистра 4 к двум входам схемы 8 сравнения. В результате сравнения каждой пары соседних членов выборки схема 8 срав-нения выдает значение инверсии ОХ, х , (в виде "0"или "1".Эти значения поступают в счетчик 7 числа инверсий, который в соответствии с.выражением (6) определяет сумму инверсий ь за каждый цикл просмотра. Одновременно каждое значение инверсии поступает на вход второго коммутатора 9.Работая синхронно с первым ком мутатором 5, второй коммутатор 9 по- последовательно соединяет выход схемы 8 сравнения со входом того переключателя 3, который своими другими двумя входами, а также.двумя выходами соединен соответственно с информационными выходами и информационными входами каждого из пары раз рядов регистра 4, .содержимое которых анализировалось схемой 8 сравге ния, Одновременно второй коммутатор Я, чтобы не усложнялась конструкция , переключателей 3, преобразует поступившее на его вход значение О(х х + ) = О в значение на своем выходе1", оставлял неизменным зна чение О(х , х +., ) = 1.Переключатель 3 соединяет подклю ченные к нему информационные выходы сравниваемой пары соседних разрядов со своими выходами таким образом, чтобы при О(х;, х) = О на входе второго коммутатора 9 содержимое сравниваемых разрядов регистра осталось неизменным, а при О (х, х,1+ )"1 - поменялось местами путем йе", реписывания из одного разряда в другой. Затем переключатель 3 возвращается в нейтральное положение. Конец каждого цикла просмотра определяется с помощью счетчика 6импульсов и счетчика 15 циклов. В первом цикле просмотра счетчик 6 импульсов отсчитывают Мимпульс из последовательности синхроимпульсов, поступающих на его вход из генератора 2 импульсов (М - объем выборки) . Этим определяется граница первого цикла. В результате осуещствляется однократное попарное сравнение и перестановка в соответствии с принятым алгоритмом всех членов выборки, содержащихся в регистре 4.Бсли при этом за цикл счетчик 7 числа инверсий получит Г Ъ 1, то осуществляется переход ко второму циклу просмотра, При Т 1 потенциал, подаваемый на управляющие входы гене.9 10436 ратора 2 импульсов и группы элемен- тов И 10 с выхода счетчика 7 числа инверсий, не меняется, Поэтому генератор 2 импульсов продолжает выдавать последовательность синхроимпульсов для управления коммутаторами 5 и 9, в группа элементов И 10 продолжает оставаться запертой, не разрешая выдачу информации, установленной на их входах, для дальнейшего использова 10 ния. СчетЧик б импульсов, закончив счет до М, своим выходным сигналом сбрасывает в исходное состояние счетчик 7 числа инверсий и возвращает в исходное состояние первый коммута тор 5 и второй коммутатор 9, так что каждый оцередной цикл просмотра будет начинаться с одних и тех же разрядов регистра 4. Одновременно счетчик б импульсов своим выходным сигна лом записывает "1" в счетчик 15 циклов.Счетик 15 циклов передает записан ную в нем сумму ( в данном случае "1 на второй вход счетчика 6 импульсов, где эта сумма вычитается из записанного там установочного числа, до которого должен считать счетчик 6 импульсов. В результате колицество по- парных сравнений членов выборки во 30 втором цикле просмотра уменьшится на "1", до Н,и самый большой член выборки в ранжированном ряду, уже занявший в первом цикле просмотра крайнее место,в попарном сравнении во втором и последующих циклах про- смотра принимать участие не будет, так как первый коммутатор 5 и второй коммутатор 9 произведут до своего возвращения на исходные позиции 40 меньшее количество переклюцений,Циклы просмотра с уменьшением числа попарных сравнеНий на 1 в каждом очередном цикле продолжаются до тех пор, пока выполняется усло вие 7, ) 1. При Т 4 1 счетчик 7 числаОинверсий своим выходным сигналом пре" кращает подачу, синхроимпульсов генератором 2 импульсов, сбрасывает в исходное состояние счетчик 15 циклов и отпирает элементы И 10. Этот моментсоответствует формированию на входахэлементов И 10 ранжированной выборки("(1) (2)" (" )н 1 ОВ соответствии с ранее описанным алгоритмом определения квантилей искомые значения квантилей х; поступают на выходы 14 устройства либо непосредственно с выхода элементов И 1 О с заранее известным номером ; либо поступают на выход 14 после интерполяции.Интерполяция, уточняющая искомое -значение квантиля, производится в соответствии с выражением (5) следующим образом, Через элементы И 10 с заранее известными номерами ( а,)+1 Йнфорнация с их выходов поступает на два входа одного из блоков 11 вычитания. Кроме того, выход элемента И 1 О с номером ; соединен с одним из входов сумматора 1.3, входящего в данную цепочку интерполяции.В блоке 11 вычитания определяетсяфР) ая (1 1Разность поступает в масштабный -усилитель 12, входящий в данную цепочку интерполяции, В масштабном рсилителе 12, полученная разностьлумножается на заранее известную долю , интерполяции,Произведение из масштабного усилителя 12 поступает на другой вход сумматора 13, где складывается с выходной информацией (1) -го элемента И О, равной х г(1) д1 аНа выходе сумматора 13, являющегося одним из интерполяционных выходов 14 устройства, получается уточненное по необходимости интерполяцией значение другого искомого квантиля.С выходов 14 устройства значения квантилей, определенные по данной выборке и соответствующие заданным уровням вероятностей, поступают навходы других технических устройствдля использования. Затем процесс повторяется для новых значений выборки.Таким образом, благодаря введению в известное устройство нового блокаи ряда новых связей, достигается повышение быстродействия за счет уменьшения количества операций в алгоритме работы устройства.