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

довых умножителей формулы (2.43) и (2.44) дают одинаковые результаты до т ^ 3, а при использовании трехвходовых элемен­ тов — до ш 5, что согласуется с выводом (2.46).

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

A. Из соображений экономии числа вентилей И общий ре­ гистр сдвига Рг (рис. 28) следует разделить на отдельные части

Опишем алгоритм синтеза устройства. Алгоритм состоит из ■последовательного выполнения пяти этапов.

1.Для заданных г и т п о формуле (2.44) определяется требу­ емое число вентилей 7V0.

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

3.Применяя замечание В , расставляем у выходов каждого

5. Последний разряд каждого регистра Pr i соединяем с г-м входом i + 1-го вентиля, I — 1-й разряд соединяем с r-м входом этого элемента и т. д. Первый вход всегда подключается к выходу предыдущего z'-го вентиля.

Пример. Пусть m = .11, а г = 3, то есть используются трех­ входовые схемы И.

<60

У\ 'РiXiIх [-2’

vl — Уiy i -ъУi-6’

zl = Vpi-lVi-.2-

Pr 2

Рис. 30. Устройство для возведения стохастической переменной р (ж,-) в степень то= 11

9. Другие схемы е разветвлением входящей последовательности

Таким же способом, как и для стохастических умножителей, можно определить математическое ожидание и составляющие суммарной дисперсии D (к/п) на выходе логических схем, реализу­ ющих иные зависимости в соответствии е табл. 1. Здесь мы вновь рассмотрим случаи, когда имеется всего одна входящая последова­ тельность Бернулли с м. о., равным р , а входы логических эле­ ментов статистически развязаны (с помощью триггеров или линий задержки).

Заметим, что из шестнадцати различных функций двух аргу­ ментов x t и х 2, представленных в табл. 1, шесть являются функ­ циями одной переменной {43]. Среди них две функции повторения

61

функций две (z/4 и г/41) не являются самостоятельными, так как они отличаются от функций у 2 и у 13 лишь порядком расположения аргументов.

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

nD (■Т ) = - Р)т 1 + 2 ^ А “ Р>* “ (2т - !) (1 - Р)п

При этом предполагаем, что включение цепочки дизъюнкторов проведено тем же способом как и включение конъюнкторов на рис. 28. При т = 2 (один включенный дизъюнктор)

и £ > ( А ) = р ( 1 - р ) 2(4 - З р ),

(2.47)

nD (zi) = p ( l —pf ( 2 ~ p ) .

62

Оти зависимости (рис. 31) симметричны относительно верти­ кали р = 0,5 с подобными зависимостями, вычисленными для конъюнктора, и имеют равные максимальные значения. Для логи­

Рис. 32. Последовательное соединение m элементов эквиваленции, в котором рассогласование Ap(zmi) = р (zmi) —

— 9 (zmi) убывает с ростом т; Рг — регистр сдвига

Поскольку входящая последовательность идеальна и ни одна из конъюнкций системы уравнений (2.48) не содержит тавтологий, вероятности функций z на выходе каждого элемента определим в виде следующего рекуррентного соотношения:

причем р (г1г) = 1 — 2р (1 — р).

Следовательно, для дисперсии результата на выходе получим:

Уравнение (2.49) определяет математическое ожидание про­ цесса на выходе т-го элемента в виде знакопеременного полинома от р, причем коэффициенты этого полинома представляют собой произведения биноминальных коэффициентов и членов геометри­ ческой прогрессии с основанием 2 в соответствии с формулой

Оба выражения (2.49) и (2.51) при возрастании т быстро схо­ дятся к результату 0,5 даже при значениях р сильно отличающихся от 0,5. Например, при р = 0,9 для т = 2 и т = 7 соответственно ползшим р (z2) = 0,76 и р (z7) = 0,57.

63

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

Запишем теперь значения выходной функции в последователь­ ные моменты времени для первого элемента цепочки на рис. 32:

zln — %tpn-1 V %rPn-1•

Как видно из уравнений, все соседние значения функции zx оказываются попарно коррелированными. Определим корреля­ ционный момент

Кг, (1) = Р (zuzli+1) —р (z1{)p (z li+1).

Сложное событие

Отсюда вероятность этого события

Р ( z l i z l i + l ) = р3 + (1 — Р)3,

а корреляционный момент

Кг, (1) = Р3 + (1 - Р)3+ (1 - 2 Р + 2р2)2= р (1 - р) (1 - 4р - 4 р2).

Применив теперь теорему о дисперсии суммы (2.36), получим дисперсию частоты появления единиц в последовательности zt

nD ( 1 ) = nD (zu) + 2 ( n - i ) K Zi (1) = 4p (1 - p) (1 - 3p + 3p2). (2.52)

Графики функций (2.50) и (2.52) представлены на рис. 31.

Как видно из рисунка суммарная дисперсия процесса на выходе логического элемента «эквиваленция» («альтернатива») больше, чем у процесса без последствия. Подобный же результат мы полу­ чили у дизъюнктора, однако в первом случае имеется седловая точка (рис. 31) с координатой р = 0,5, при которой изменений дисперсии не происходит.

Запрет: z = х хх 2.

Математическое ожидание и дисперсию последовательности на выходе цепочки из т последовательно соединенных элементов «запрет» получаем в виде

P(Z nd)=P(l— P)m*

D (Zmi) — Р (Zmt) И — Р (z m i) l

64