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

ставления в дизъюнктивной совершенной нормальной форме ее следует записать «по единицам». Если же функция задана в произ­ вольной аналитической форме, то ДСНФ получают, применяя операции развертывания, правила де Моргана и другие формулы булевой алгебры.

Рассмотрим примеры. Пусть сложное событие z заключается в одновременном наступлении двух событий х г и х 2. Тогда %—

чайных величин могут быть заданы в виде

/(*i) = Р (*i) S (х1— 1) -f q (хД б (хД,

/(*Д = Р (хг) 6 (х2 — 1) + q (х2) б (х2).

Считая величины х х и х 2 независимыми, для плотности вероят­ ности сложного события z получим / (z) — / (хД / (х2). В последнем случае математическое ожидание z определим, вычисляя интег­ рал [8]

00 00

Подставляя в это уравнение выражение для плотности вероят­ ности, получим

+ 9 (*Д 9 (жД S (хД б (x2) + p (хД q (х.Д 6 (xx — 1) б (x2) +

+ P fa ) 9 (*Д б (жД S (x2 — 1)] dx2.

Так как

[ 6(x — a)f(x)dx = f(a),

TO

CO

M (z) = J* [xxp (хД p (x2) 6 (xx — 1) + Xjj? (x2) q (хД б (хД1 dxx =

-00

= p W Р а ­

спределим дисперсию z

2$

Подставляя выражение для / (z) и раскрывая скобки, после пре­ образований получим [73]

00

D (z) = j {х\р (хг) р (ж2) б (х: — 1) — 2ххр (жх) р (ж2) б (жх — 1)М (z) + -00

+'Aq (xi) Р Ы S (ж2) — 2ххМ (z) q (хх) р (ж2) б fo) +

+М 2 (z) [р fo) р (х2) б (zj - 1 ) 1 ? (ж:) q (ж2) б fo) -f

-I-р (xj) g (ж2) б (жх — 1) - ; q (х,) р (х2) б (xj)]} dxx =

= Р (xi) Р (я?я) [1 —Р (xi) Р (хг)]-

Во втором примере пусть z заключается в появлении хотя бы одного из двух событий х г и х 2. Переключательная функция в этом -случае имеет вид z = жх V х 2- Для получения совершенной формы применим операцию развертывания

Z= лх (х2 v Х2) V Х2 (хх v хх) = ххх2 V ХХХ2 V ЖхЖ2.

Считая события жх и х 2 независимыми и применяя формулы (1.29) и (1.30), определим численные характеристики выходной случайной функции z:

П (z) = [р (zj) + р (ж2) — р (®j) р (ж2)] [1 —р (®х) —р (ага) + Р (®i) Р (^2)1-

то, применяя операцию развертывания (первый член умножаем

(1.33)

После чего, применяя правила (1.29) и (1.30), определим:

М (г) = 1 —р (ж,) р (ж8) + р (ж2) р (ж3) —р (ж2) + р (жх) р (ж2),

D(z) = M (z ) [l - M ( z )] .

Заметим теперь, что в общем случае, когда исследуются функции от независимых событий, уравнение (1.29) с учетом (1.28) может быть записано в следующей форме:

СО 0 0 fO

2k

В уравнении (1.34; каждому из элементарных произведений, стоящих под знаком суммы, соответствует лишь одно из слага­ емых pfe, заключенных в квадратные скобки, такое, что га-мерный интеграл от их совместного произведения отличен от нуля и равен

00 00 со

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

xf'xf* . . . Хпп8 f a —aj) 8 f a — а ’2) . . . 8 (xn—a^) x

Xpal f a ) p a* f a ) . . . p an fa ) .

При этом, если хотя бы однажды а*, ф а и’ , то в силу свойств дельта­ функции получим

СО

j Xhk8 f a — ah) dxk = 0 ,

чем справедливость (1.35) доказана.

Таким образом, для формального перехода от булева выраже­

В работе [47] показано, что для нахождения м. о. сложной булевой функции в общем нет необходимости приводить заданную ДНФ к ДСНФ, а достаточно привести ее лишь к ортогональной дизъюнктивной нормальной форме (ОДНФ), которая может быть

25

Т а б л и ц а 1

Вероятностные функции на выходе логических элементов

= 0 при х Ф /.

Приведем один из алгоритмов перехода от произвольной ДНФ к ОДНФ, построенный в [47]. Алгоритм выполняется при этом

втри этапа:

1)в ДНФ производятся все поглощения и склеивания;

2)все элементарные произведения ДНФ перенумеровываются; элементарным произведениям, содержащим меньшее количество

букв, присваиваются меньшие номера;

26

3) применяется следующая лемма:

если

то

ф(хг, х2, . . ., хп)= уг V У1У2 V У1УгУз V ... V У1У2 ■ ■ - Vi-

В частности, функция алгебры логики (ФАЛ) (1.32), как не трудно заметить, уже представлена в ОДНФ, и, следовательно

M(z) = p (хг) р (х 2) + [\—р ( х ^ р (х3) + [1 — р Сг2)] [1 —р fe)l =

= 1 —р (x j р (х3) + р (х2) р (х3) —р (х2) + р {хг) р (х2).

Таким образом, мы получили результат значительно быстрее чем при использовании формулы (1.33).

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

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

5. Кодирование информации в СтВМ

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

Масштабные коэффициенты, связывающие машинные перемен­ ные (X, Y, Z, . . .) с переменными заданной для решения задачи (Х 0, Y о, Z 0, . . .) выбирают из известного условия

2?