Файл: Яковлев, В. В. Стохастические вычислительные машины.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 77

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

определяется стохастической матрицей |р ц | и 'совокупностью начальных вероятностей состояний p t (0).

Аппарат марковских цепей широко используется при изучении поведения вероятностных автоматов [57]. При этом множество возможных переходов обычно представляется графом, т. е. схемой, образованной вершинами (соответствующими состояниями E t),

0,75

0,25

Рис. 4. Реализация случайного по­ тока

соединенными между собой ориентированными дугами (соответ­

ствующим переходом).

 

 

 

Пример. Дан автомат с

матрицей перехода

' *

0,75

0

0,25

 

0,25

0,25

0,5

 

0,5

0,5

0

 

и таблицей начальных вероятностей состояний

Ei

Ei

Ег

Ez

Pi (0)

0

1

0

На рис. 3 показан граф переходов этого автомата.

Для определения вероятности каждого из состояний E t в любой момент t через начальные вероятности состояний формулу (1.16) преобразуют к виду

Р (0 = Р (0) \\Pij II'■

(1-17

Случайные потоки. Случайным потоком, следуя [40], назы­ вают случайный процесс, реализации которого представляют ступенчатые неубывающие функции (рис. 4), принимающие цело­ численные значения при произвольном t. Число к реализаций

13

(например, выпадания к точек внутри интервала длиной т) является случайной величиной N. Вероятность того, что N = к обозначим p k (т).

Если: 1) p k (т) зависит только от т и не зависит от начального момента t0; 2) N (т) не зависит от числа реализаций события, происшедших в предшествующие интервалы; 3) вероятность того, что событие произойдет более одного раза в интервале времени dt, есть величина бесконечно малая но сравнению с dt, то говорят, что такой поток событий обладает свойствами стационарности, отсутствия последействия и ординарности.

Если поток событий обладает всеми этими свойствами, то он называется стационарным пуассоновским потоком, причем вероят­ ность того, что за время т произойдет к событий, равна

Р*(х) = - ^ е Л

к —0, 1,

2, 3, . . .

(1.18)

Величина X называется интенсивностью

потока, а среднее число

событий в интервале т равно Хт, т. е. линейно по т.

 

В литературе описаны и

некоторые

иные потоки.

Укажем,

например, поток с ограниченным последействием (поток Пальма или рекуррентный поток), где промежутки времени между сосед­ ними событиями — независимые величины, потоки Эрланга, обра­ зующиеся просеиванием простейшего потока, поток Бернулли, характеризующийся тем, что в фиксированный промежуток вре­ мени (О, Т) случайным образом реализуется заданное число собы­ тий, например, к (т. е. вероятность появления любого из к собы­ тий в бесконечно малом промежутке времени dt интервала равна

dtJT).

 

 

время t меняется диск­

Случайные последовательности. Если

ретно (£ = . . . , — 1, 0, 1,

2 , .. .), то говорят о случайных процессах

с дискретным временем или

о случайных последовательностях.

Для стационарных последовательностей

[1] =

М (£), К [t,

tx\ = K-i [f — lx]) по

аналогии с непрерывными

случайными

функциями вводится дискретная спектральная плотность:

 

СО

 

 

 

Sd (ai)=

2

К\т]е-/0)Т,

|® !< я,

 

 

т= -со

 

 

 

 

 

1C

 

 

К [т] =

J S d (со) e/“T dxa

 

(со безразмерна).

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

14

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

К ним может быть также отнесен процесс, известный в лите­

ратуре под названием последовательности испытаний

Бер­

нулли [66]. Повторные независимые испытания образуют

схему

испытаний Бернулли, если в каждом из них имеется только два

возможных исхода (например, 0 и 1)

и вероятности этих исходов

(р (1) = р, р (0) = q соответственно)

остаются неизменными для

всего процесса из п испытаний. При этом р ^ q = 1,

а вероятность

какой-либо конкретной последовательности равна

произведению,

полученному из этой последовательности путем замены символов 0 и 1 на вероятности р и q (например, для последовательности

110111

получаем ppqppp = />5<?).

В

большинстве случаев представляет интерес суммарное

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

pk,n ^ C nPkq ^ k,

(1-19)

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

независимых испытаний, каждое из которых может иметь не­

сколько исходов

[66]. Обозначим возможные исходы испытаний

через В х, В 2, . .

., B s, а соответствующие им вероятности появле­

ния в любом испытании через р г, р 2, • • ., p s.

событий,

Так

как

эти

события составляют полную группу

S

 

 

 

 

 

 

 

то 2 т ;

= 1-

Вероятность того, что в п испытаниях исход В 1 по-

i=i

 

 

 

 

 

 

 

является к г раз,

исход В% — к 2 раз и т. д., равна

 

 

 

 

 

А.-1 ! Аг2 ! —

A:s !

P i 1

( 1 . 20)

 

 

 

 

 

где к х + к 2 +

. . . + к5 = п.

При-s = 2 формула сводится к би­

номиальному

распределению

с

параметрами р г = p,

р %= q,

к г = к, к 2 = п — к.

Распределение (1.20), являющееся общим членом разложения многочлена (рх + . . . -f p s)n, называют полиномиальным.

Биномиальное и полиномиальное распределения и схемы реализующие их составляют основу одного класса СтВМ, к изуче­ нию которого мы и переходим.

15

3.Принципы представления информации вероятностью

ВСтВМ для представления машинных переменных и констант могут быть использованы различные случайные процессы. На­ пример, дискретные процессы, представляющие собой пуассонов­ ские потоки, применяются в так называемых «нетактированных» стохастических вычислительных машинах. В «тактированных» СтВМ случайное появление импульсов возможно лишь в строго фиксированные моменты времени (такты). Примером такого про­ цесса служит уже упоминавшаяся нами последовательность Бер­

 

 

 

нулли.

 

 

 

 

 

 

 

Независимо от вида случайного про­

 

 

 

цесса, применяемого

в СтВМ, некото­

 

 

 

рой входной переменной ставится в

 

 

 

соответствие

определенный

параметр

 

 

 

машинной переменной. Так,

в первом

 

 

 

случае им будет интенсивность импуль­

 

 

 

сов в потоке, во втором — вероятность

 

 

 

появления импульсов. Наиболее часто

Рис. 5. Входной преобра­

встречающаяся схема

преобразователя

входных переменных

для «нетактиро­

зователь

нетактированных

СтВМ, основанный на сов­

ванных» СтВМ представлена на рис. 5.

падении

детерминирован­

 

Генераторы Г 1 и Г 2, вырабатываю­

ных потоков: Х 0 — вход­

щие импульсы с частотами следования

ная переменная; | (г) — сто­

(»! и ю2, не синхронизированы, и по­

хастический поток;

Гу —

генератор

коротких

им­

этому входные сигналы вентиля И

 

пульсов

 

можно считать статистически незави­

 

 

 

симыми. Широтно-импульсный модуля­

тор (ШИМ) запускается генератором Г 2

и вырабатывает импуль­

сы, длительность т2 которых

пропорциональна входной перемен­

ной Х 0.

В качестве таких

модуляторов можно применить схе­

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

Процесс совпадения импульсов характеризуется временными параметрами. Это позволяет форму импульсов каждого входного потока (по отношению к схеме И) считать прямоугольной, а их амплитуду — единичной. Если к тому же оба потока стационарны, то в произвольно взятый момент времени ty равенство \ (ty) = 1

выполняется с вероятностью р (£) == cojX|, где — средняя

частота потока совпадений, a tg — м. о. длительности импульсов выходящего стохастического потока.

В работе [62] впервые найдена формула для определения средней частоты следования импульсов потока совпадения для случая п входящих потоков

ПП

Применительно к случаю п = 2 имеем

со-=со1о)2 (q -f-т.,).

При условии, если т2 > тх,

сое^ с 1т2 = с2Х 0 (q, с2 —константы).

Отметим, что количественные соотношения, определяемые этими зависимостями, охватывают случаи любых потоков, в том числе и детерминированных, при условии, если они стационарны и не­ зависимы. В частности, если генераторы Г 1 и Г 2 синхронизиро­ ваны так, что выполняется со­

отношение

= т 2Т 2, где пг1

и т 2 — целые взаимно простые

числа, то входные потоки яв­

ляются зависимыми. Это приво­ дит к появлению на выходе схе­ мы регулярной последователь­

ности импульсов с частотой

 

следования

 

Рис. 6. Преобразователь код — ве­

 

 

m i

т ‘2

роятность

 

ТГ = ^ Г '

Вэтой книге мы будем в основном касаться устройств преобра­ зования, характерных для «тактированных» СтВМ. Одна из воз­

можных

структур преобразователя таких машин представлена

на рис.

6.

 

В регистре Рг1 содержится код детерминированного числа А,

(i =

1,

2, . . .), подлежащего преобразованию.

Случайное

число Ху (; = 1, 2, . . .) формируется в регистре

Рг2.

Процесс,

протекающий здесь, состоит в том, что система

в дискретные

моменты времени переходит из одного состояния

в другое (например, из Х 2 в Х 3). В любой момент времени t она может находиться только в одном из них с вероятностью ру (t).

Очевидно, что для любого t 2 Р (О — 1. При заданных вероят­

ностях Pj (t) распределение случайных чисел может быть задано плотностью вероятности

/(X) = S p /6 ( X - X /),

(1.21)

/

 

 

 

где

 

 

 

б (X — Х у) = /(Х /)

оо

при

X = Ху

о

при

X ф Ху

 

2 в. В . Яковлев

Гос. публичная

научно-техническая библиотека С С С Р

— распределение фиксированной величины1 Ху, определяемое функцией Дирака. Причем, из свойств данной функции

ХуД £о

J б (Х — Xy)dX = l при любом е0> 0

Xу-8о

И

ХуД £о

/ф ( Х ) б ( Х - Х /)йХ = ф(Х/)

х'г е„

вытекает

 

 

Ху-г£о

lim

/ f ( X j) d X = P j.

£°+ °

Ху-е0

Рассмотрим событие a: (f), заключающееся в том, что появляется хотя бы одно из состояний Ху, удовлетворяющих условию Д,- 5=г 3s X s. Тогда вероятность этого события р (х) согласно [11]

р ( х ) =

Х 2, . . ,)d,X1dX 2 . . . dXs . . .

x s

 

 

 

 

и, учитывая (1.21), получим

 

 

 

 

s

Ху+8о

 

р (z) =

lim 2

J

Руб (X - Ху) dX.

(1.22)

 

е„-*-0/=1 Ху-е0

 

Следовательно, если процесс, протекающий в

Ра?, — стацио­

нарный и без последействия,

то для заданного

состояния из

множества Д,- вероятность р (ж) в каждый тактовый момент по­ стоянна и определяется лишь законом распределения дискретной случайной величины X.

В частности, если р }- = 2_/, где I — разрядность регистров Рг1 и Рг2, то распределение состояний регистра Рг2 равномерно и, используя (1.22), получим р (х) = s*2~1. Так реализуется линейное преобразование.

Последовательность событий х во времени образует случайную последовательность Бернулли, которая обращается в регулярную при р (х) = 1.

Зададимся задачей определения вероятности p kt „ появления события х (t) в п испытаниях точно к раз. Пусть некоторая слу­ чайная величина уп представляет собой сумму п независимых случайных величин xt

уп = Ъ х1

(1.23)

t=l

 

18

Смотрите также файлы