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

(Л

а

Изобретение относится к специализированным средствам вычислительной техники и может быть использовано для определения выборочных квантилей. Цель изобретения - расширение функциональных возможностей за счет обеспечения возможности вычисления оценок дисперсий выборочных квантилей и оценок исходной плотности вероятности в точках квантилей. Устройство содержит регистр 1 буферной памяти, генератор 2 импульсов, переключатели 3, регистр 4, два коммутатора 5 и 9, счетчик 6 импульсов, счетчик 7 числа инверсий, схему 8 сравнения, группу элементов И 10, две группы блоков вычитания 11 и 15, группу масштабных усилителей 12, сумматоры 13, счетчик 14 циклов, группу блоков вычисления обратной величины 16, группу квадраторов 17. 1 ил.

4 i

со со со со

N)

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

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

На чертеже изображена структурная схема устройства.

Устройство содержит регистр 1 буферной памяти, генератор 2 импульсов, переключатели 3, регистр 4, первый коммутатор 5, счетчик 6 импульсов,счетчик 7 числа инверсий, схему 8 сравнения, второй коммутатор 9, группу элементов И 10, первую группу блоков 11 вычитания, rpvn пу масштабных усилителей 12, сумматоры 13, счетчик 14 циклов, вторую группу блоков 15 вычитания, группу блоков 16 вычисления обратной величины, группу квадраторов 17.

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

На вход устройства поступает последовательность независимых отсчетов, закон распределения F(x) и плоность распределения f(x) которых не известны.

Устройство периодически делает выборку объемом N членов и ранжирует ее в соответствии с

х(о к(1 ,6 ...х(| (1

где 1 - номер члена в ранжированном

ряду.

Каждый член ранжированного ряда х( представляет выборочный квантиль х pj с уровнем вероятности Р , удовлетворяющим соотношению

(j) P:-N

(2)

В случае, если по заданной Р: из (2) получается

(i)j Р- N

(3)

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

0

5

х

(

(х

+ X,

+ i

- X

№}

Hi

(4)

где у- (i)j - (i)j J - доля

терполяции;

Г 1 в данной формуле - операция взятия целой части;

хС()П+

Хг-г-,.- - соответственно ближайший

больший и ближайший мень- 0ший к промежуточному между ними х(- члены ранжированной выборки с указанными целочисленными номерами.

5 Выборочные квантили, удовлетворяющие соотношению (2), а также полученные на основе (4), выводятся из устройства для использования.

Для N-2W-2 выборочных квантилей 0 х р: с номерами членов ранжированной выборки от (i) 2 + W до (i) N-W-1, т.е. полученных без интерполяции, evflyT определены оценки дисперсий D(xpi) и оценки исходной плотности вероятности в точках х

Pi

квантилей f(xp:). С этой

целью заранее, с помошью выражения

W -4N1

(5)

где Ј 3 - операция взятия целой части, определяется значение W.

Для каждого из квантилей оценка дисперсии производится с помощью

R Sii

x(i)-w) A

(6)

50

где R

- III N

4W

Учитывая, что в данном случае (j) i+W, из (6) следует, что операции, необходимые для определения дисперсии, надо проделать для каждой пары членов выборки с номером (1+2W) и (i), где i 24- (N-2W-1)

Для каждого из квантилей оценка исходной плотности в точках квантилей производится с помощью

Л

f(x

р;

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

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

1

Л1 Ц

Частота следования тактовых им1- пульсов выбирается таким образом, чтобы согласовать скорость поступления исходной последовательности на вход регистра буферной памяти со скоростью записи выборки в регистр 4 и скоростью ее обработки. Значения выборки одновременно с записью в регистре 4 через информационные выходы каждого разряда регистра 4 устанавливаются на соответствующих им входах первого коммутатора 5 переключателей 3. и соответствующих им входах каждого из элементов И 10 группы

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

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

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

Попарное сравнение и перестановка членов выборки продолжается до тех пор, пока не закончится процесс ранжировки выборки, т.е. Х(, хсз) 6 ... х ...бх jN).

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

Г J (х;, x-t, ), (8) 1, х х +, ;

где и(х; , х-+1 )

О, х- Ј х-+, .

Значение с вычисляется при каждом цикле попарного сравнения и перестановок членов выборки. Признаком окончания ранжировки выборки является значение Ъ 1, сосчитанное за цикл просмотра.

Алгоритм ранжировки выборки реализуется следующим образом. В каждом цикле просмотра первый коммутатор 5 в такт синхроимпульсам производит последовательное подсоединение информационных выходов каждой соседней пары разрядов регистра 4 к двум входам схемы 8 сравнения. В результате сравнения каждой пары соседних членов выборки схема 8 сравнения выдает значение инверсии u(xj, х - ) в виде О или 1.Эти значения поступают в счетчик 7 числа инверсий, который в соответствии с выражением (8), определяет сумму инверсий Ъ за каждый цикл просмотра. Одновременно каждое значение инверсии поступает на вход второго коммутатора 9.

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

поступившее яа его О Б значение на оставляя неизмен.

соединяет под- информационные выпары соседних раздам таким обрапи

ча им ся го та та чл см и жи пе ст и пр пе му вр ше

зом, чтобы при и Ј 0 на входе второго коммутатора 9 содержимое сравниваемых разрядов регистра оставалось неизменным, а при и 1 поменялось -, местами путем переписывания из одного разряда в другой. Затем переключатель 3 возвращается в нейтральное положение.

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

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

Счетчик 14 циклов передает записанную в нем сумму (в данном слу

5

0

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

Циклы просмотра с уменьшением числа попарных сравнений на 1 в каждом очередном цикле продолжаются

5 ДО тех пор, пока выполняется уело- вие Ј 1. При Г 1 счетчик 7 числа инверсий своим выходным сигналом прекращает подачу синхроимпульсов генератором 2 импульсов, сбра„ сывает в исходное состояние счетчик 14 циклов и отпирает элементы И Ю. Этот момент соответствует формированию на входах элементов И 10 ранжированной выборки. Искомые значения квантилей, удовлетворяющих

5 выражению (2), поступают на выходы устройства непосредственно с выходов тех элементов И 10, номера которых соответствуют (2).

Уточняющая интерполяция произ - водится в соответствии с (4) следующим образом. Информация с каждой пары элементов И 10 с известными номерами (i)jj и C(i) + 1 поступает на два входа блока 11 вычитания, соответствующего этой паре. Кроме того, выход элемента И 10 с номером (i)j j соединен с одним из входов сумматора 13, входящего в данную цепочку интерполяции. В блоке 11 определяется разность Хгд,У1 - xt(.ui которая поступает в масштабный усилитель 12, входящий-в эту же цепочку. В усилителе 12 полученная разность умножается на известную долю интерполяции jf: . Произведение поступает на второй вход сумматора 13, где складывается с выходной информацией L(i)j -го элемента И 10,

0

5

0

5

равной хг

в результате полу, посту ПЫП „ чается искомый квантиль хщ1-т

пающий ка соответствующий выход устройства,,

Оценка дисперсии квантилей произ- водится в соответствии с (6). Для этого информация с выходов каждой пары элементов И 10 с номерами (i) и (1+2W) поступает на два входа второго блока 15 вычитания,соответствующего данной паре элементов. В блоке

15определяется разность x/:14.w - кн. w. , поступающая в соответствующие этой паре элементов И 10 блок

16вычисления обратной величины и квадратор 17„ Выходы блоков 17 являются выходами оценки дисперсии квантилей устройства.

Для оценки функции плотности в точках квантилей разность, полученная при оценке дисперсии, преобразуется блоком 16 в обратную величину, где,согласно (7), окончательно формируется оценка f(xp;). Вых-о- ды блоков 16 являются выходами оценки плотности вероятности устройства.

С выходов устройства значения

А А , К , J , ..

хр. , 1)(хр:) и f(xpj), определенные по данной выборке, поступают на чходы других технических устройств

0

5

0

5

0

для использования. Затем процесс повторяется.

Ф ормула изобретения

Устройство для определения характеристик случайного процесса по авт.св. № 1043665, отличающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности вычисления оценок дисперсий выборочных квантилей и оценок исходной плотности вероятности в точках квантилей, в Него введены вторая группа блоков вычитания, группа блоков вычисления обратной величины и группа квадраторов, причем вход уменьшаемого блока вычитания второй группы подключен к выходу 1-го элемента И группы (i 2,...,(N - 2W - - 1), W - целая часть от величины vfN, - объем выборки) , а вход вычитаемого - к выходу (i+2W)-ro элемента И группы, выход 1-го блока вычитания подключен к входу одноименного блока вычисления обратной величины группы, выход которого является выходом оценки плотности вероятности устройства, и подключен к входу одноименного квадратора группы, выход которого является выходом оценки дисперсии квантилей устройства.