Файл: Яковлев, В. В. Стохастические вычислительные машины.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 139
Скачиваний: 0
Вторая сумма в квадратных скобках накладывает дополнитель ное условие на обеспечение устойчивости:
Ч(s) Ч(V) < 1 или р(х) + р ( у )> 1 .
Р (®) Р (У)
Наконец, общее выражение математического ожидания п, полученное после очевидных преобразований
м (п\ = |
р ^ |
Г q(y') |
|
п _ р (у ) [ р ( у ) —p W ] |
~| |
1 1 |
2p(y) — l |
L |
р ( у ) — р ( х ) |
Р(х) + Р(У) — 1 |
J ’ |
определяет третье необходимое условие
2р(у) — 1ф0 или р ( у ) ф 0,5.
При переходе к нормированным переменным X и Y условия устойчивости приобретают вид
Y — Х > 0 , X + F > 0 , Y=h0
или, что то же самое,
|X |<У , Г > 0.
Первое из этих условий является следствием того, что стохасти ческая переменная М (z) определена лишь на интервале (0,1), и выполняется масштабированием. Требование знакоопределенно сти делителя объясняется непрерывной формой представления информации в стохастических ВМ, а то, что делитель должен быть положительным, является особенностью схемы. Для отри цательного делителя необходимо инвертировать представляющую его последовательность или заменить в обратной связи эквивалент ность альтернативой.
Вероятность положительного переполнения счетчика при ко нечном числе I его разрядов:
Р ( п ^ 2 ') = 2 Р (п) |
Р ( ж ) + Р (у)— 1 |
2Р (У) — 1 |
|
П=21 |
|
То же для отрицательного переполнения:
Р(у) — Р(х)
Р ( п ^ ~ 21) = 2 р ( ~ п) = 2 р ( У ) ~ 1
п=2 1
Л
Р (х) д (у) 1 2
Ч(х) Р(У) J
д(х) д (у) 12‘ 1
р(х)_р(у) J
Автокорреляционную функцию выходной последовательности, как и ранее, можно рассчитать с помощью модели, реализующей на ЦВМ граф переходов (рис. 80), по формуле
К г {т) = \\ — p(z)][p(z) — P(nSaO, 11тг<0, t —т)].
173
Для определения |
начальных условий |
моделирования восполь |
||
зуемся равенством |
|
|
|
|
|
00 |
|
оо |
Я(д) Я (у) |
р (п < о, |
|
|
[ |
|
|
|
Р (х) Р (у) |
||
|
|
|
п=1 |
|
Отсюда |
|
|
|
|
|
|
|
р (х) + р (у) — 1 |
|
|
|
|
|
р (*) д Ы |
|
|
Р ( - 1 , * - т ) = |
||
|
Д (х) + Р (у) —1 |
Г? (s) |
g (у) |
1 ” |
|
Я (х) Я (у) |
1д (х) Р(у) J ' |
||
Естественно, что |
Р (п, t — т) = 0, |
п ^ |
0. |
|
Расчет вероятностей использования вершин графа в последу ющие моменты времени производится по рекуррентным соотно шениям:
Р ( —п, t —k) = p { x ) p ( y ) P ( —n — 1, t — к — 1) +
+ [р (ж) q(y) + q (х) р (у)] Р (—п, t — k — 1) + |
|
||
+ q ( x ) q ( y ) P ( —n + 1, t —k — 1), nss 2, |
|
||
P ( —1. t —k) = p ( x ) p ( y ) P ( —2, £ —Л — l) - f |
|
||
+ [P («) 9 (p) + q (x) p (у)]P (—1, t — к — 1) + |
q (x) p (у) P (0, |
t —к — 1)» |
|
P (0, t — k) = p ( x ) p ( y ) P ( —l, |
t —k — 1) + |
|
|
+ \P(x)p(y) + q(x)q(y)]P (0, t — k — i) + |
q (x ) p (y ) P ( l, |
t — k — i), |
|
P(n, t —k) = p {x)q {y)P {n — 1, |
£ — /e — l) + |
|
|
+ q (x )p (y )P (n + 1, t — k — 1), n s s l, |
|
||
P(reSsO, |
f — ft) = P ( n ^ O , f — fc— 1) — |
|
|
— q (x ) p (y ) P ( 0, |
/ —/с — 1) + p (a:) p (y) P (—1, ^ — A:— 1), |
||
к —0, 1, 2, . . ., ( т - 1 ) .
Начальные условия для последней формулы:
Р (п ^ 0, t — т) = 0 .
Результаты моделирования (рис. 81) свидетельствуют о том, что корреляционная функция возрастает при р (у) —> 0,5 и не за висит от знака Z [кривые для р (z) = 0,25, Z — —0,5 и р (z) = = 0,75, Z = 0,5 совпадают при различных р (у)]. Представление
1 7 4
об инерционных свойствах схемы дает рис. 82, соответствующий режиму удвоения масштаба переменной Z = 2Х, р (у) = 0,75. Кривые, показанные на этом рисунке, рассчитаны на той же
l&p(z)l
\ v \ \ ^ |
|
|
|
|
|
|
|
|
|
V \ |
|
|
|
л З |
|
|
|
||
V |
\ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
^ |
|
|
|
|
|
V \ |
X |
' I 2 |
|
|
|
|
|
|
|
\ |
|
|
|
|
|
|
|
|
\ |
|
V |
|
|
|
|
|
|
|
\\ |
|
/ \ |
|
|
|
|
|
|
|
\ |
V |
\ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
\ |
|
|
|
|
|
|
\ |
|
-----^ |
|
|
|
|
||
|
|
|
\ |
|
|
|
|
||
|
|
\ |
|
|
|
|
|
|
|
|
|
|
|
|
ч |
|
|
|
|
|
|
\ |
|
|
|
|
|
|
|
|
|
\ |
|
|
|
|
\ S |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А _____ |
|
|
|
|
|
|
|
0 |
10 |
20 |
30 |
4 0 |
50 |
т |
|
|
|
Рис. 81. Автокорреляционная функ |
Рис. 82. Переходные процессы в схе |
||||||||
ция выходной |
последовательности в |
ме, изображенной на рис. 79: |
|||||||
схеме, изображенной |
на |
рис. |
79: |
-------------------- р (z) = 1 ; ----------------- р (2) =* |
|||||
1 — V (у) = |
0,875; |
2 |
— р |
( у ) = |
0,75; |
= 0,75 |
СО,25) |
||
3 — р (у) = |
0 ,6 2 5 ; ----------р (2) = |
0,75(0,25) |
|
|
|||||
|
------------— р |
(z) = 0,5 |
|
|
|
|
|||
модели, |
что |
и |
корреляционные функции, однако, |
при других на |
|||||
чальных |
условиях, |
а именно: |
|
|
|||||
При этом |
|
p(z, |
|
0 )= 0 ,5 , |
т. е. Z(£=s0) = 0. |
||||
|
|
|
|
|
|
|
|||
|
|
ии |
|
|
|
|
|
|
|
|
Р (ж) g (у) |
"I" |
|
2 |
Г |
|
J ”p (0) = 0 ,5 , |
л~0 |
О(*)Р (У) |
|
|
Отсюда |
|
|
|
Р(0) = 1- |
2Р (у) |
и |
Р (ге) = |
|
|
|
|
Аналогично
p(x) = q(x) = 0,5.
я (у) |
, ress 0. |
|
• ] [
2 |
д(*)д{у) |
] " -1 Р (—1) = 0,5, |
[р ( * ) р (у) |
||
Л-1 |
|
|
Р ( - ! ) = !• 2Р (у) »
1 7 5
По результатам моделирования можно судить о том, что пере ходный процесс замедляется при возрастании Z по абсолютной величине и для |Z |= 1 \р (z) = 0 и р (z) = 1] ошибка составляет 0,0617 при t = 60, уменьшаясь в дальнейшем на порядок при мерно через каждые 250 тактов.
Схема сохраняет свои свойства, если вместо инверсного выхода знакового разряда использовать прямой, а в обратную связь вместо элемента, реализующего эквивалентность, включить сум матор по модулю 2. Существуют также эквивалентные преобразо вания схемы, связанные с переменой местами входов счетчика.
25. Реверсивный счетчик в режиме сложения стохастических переменных
Рассмотрим схему (рис. 83), состоящую из реверсивного счет чика PC и нескольких логических элементов, управляющих зане сением информации в счетчик и формирующих выходной сигнал z.
Рис. 83. Схема стохастического сумматора на основе реверсивного счетчика
Выходная последовательность в каждый момент времени (такт) определяется логической функцией
z = x\Jy\Js, |
(4.20) |
где ж и у — мгновенные значения входных сигналов, s — значение знакового разряда счетчика,
S = |
11, |
если |
н < 0 , |
|0, |
если |
|
|
п — содержимое счетчика |
(его |
состояние). |
|
Занесение единицы в счетчик осуществляется в соответствии с ло гической функцией
п+1 = ху,
а вычитание единицы
n_x = x\/y\Js.
176
На основании этих формул поведение схемы во времени можно описать направленным графом (рис. 84). Граф определяет
t
Рис. 84. Граф переходов стохастического сумматора на основе реверсивного счетчика
следующие |
соотношения между состояниями счетчика в последо |
|||
вательные |
моменты времени: |
|
|
|
Р(п, t —k) = q (x)q(y)P (п + \, |
t —k — l) + |
|
||
|
+ tP (ж) я (у) + я (x) P (P)l P (n, |
t —k — 1) + |
|
|
|
+ P ( x ) p ( y ) P ( n ~ 1, t — k — 1), |
n SaO, |
(4.21) |
|
P ( —1, t — k) = [l —p ( x )p (y )]P ( —l, |
t — k — 1)4 |
|
||
|
+ Я (x) q (у) P (0, t — k — 1). |
|
||
В установившемся режиме имеем: |
|
|
|
|
P(n) = |
q (х) q (у) P (n + t) + [p (х) q (у) + q (х) р (у )] Р (п) |
|
||
|
+ Р (х) Р (У) Р ( п — 1), |
|
0, |
|
р (—1) = [1 —р (*) р (г/)1 р (—1) + я (*) я (у) р (0).
Как и прежде, просуммируем первое уравнение по п от п до оо
о о СО
2 |
р (п) = q (х) q(y)2i Р (п) + |
|
|
п |
|
п+ 1 |
|
|
о о |
о о |
|
+ [р (?) я(у) + |
я И Р (*/)] 2 |
Р («) + Р (х) Р (у) 2 |
Р (п)■ |
|
п |
п- |
1 |
|
|
00 |
|
Вынесем в правой части за скобки |
2-Р (я), прибавив и отняв не- |
обходимые члены |
п |
|
|
О == —q {х) q (у) Р (п ) + р (х) р (у) Р (п — 1). |
|
12 в. В. Яковлев |
177 |
Отсюда |
|
|
|
|
Pin) |
р (х) р (у) Р ( п - 1), п ^ |
0. |
||
|
q (х ) ч (у ) |
|
|
|
В другом виде |
|
|
|
|
Р ( п ) = |
' р ( х ) р (у) |
П+1 |
(4.22) |
|
. q (х) q (у) |
Р [(- D- |
|||
|
|
|
|
|
Для определения Р (—1) посмотрим, как изменяется в среднем содержимое счетчика в такте t. Если в (t — 1)-м такте было п =
— —1, то Дп = р (х) р (у). Если п (f — 1) За 0, или, что то же самое, п (t — 1) =f= —1, то Ап = р (х) р (у) — q (х) q (у). Усред няя Ап по всем возможным значениям п и приравнивая прираще ние нулю, получаем
0 = р {х) р {у) Р (—1) + \р {х) p(y) — q (x ) q ( y ) ] [ l — P (—1)].
Отсюда находим
. |
р ( х ) р ( у) |
(4.23) |
* ( - 1 ) |
q (х ) q (у ) |
|
|
|
|
Примем во внимание, что Р (—1) = р (s). Тогда |
|
|
М (z) = р (z) = Р (х V УV s) = I —Р (xys) = |
|
|
= l — q(x)q (у) |
(х)+ р {у)= м { х ) + м { у ) |
|
1 - |
||
Таким образом, рассматриваемая схема выполняет функцию сложения стохастических переменных без изменения их масштаба.
Подставляя (4.23) в (4.22), можно получить распределение ве роятностей состояний счетчика в стационарном режиме
Р(и) = [1 |
Р (х) р (у) ~ |
' р ( х ) Р (у) ~|я и |
S s - 1 . |
||
q ( x ) q{ y) . |
. |
q (*) q (у) J |
|||
|
|
||||
Для выяснения условий устойчивости найдем математическое ожидание содержимого счетчика
|
|
' р ( х ) р (у) 1«+1 |
|
п= - 1 |
|
. q (х) q (у) J |
|
|
1 |
|
|
|
|
СО |
|
р (х ) р (у) |
Р (я) Р (у) |
Г" р (х) р (у) 1 п |
|
q (*) q (у) J M |
q (х ) q (у) |
Т-2п=0 L q ( x )q (у) |
J |
С суммой первого вида мы уже встречались ранее (стр. |
165). Она |
||
сводится к сумме второго вида. Таким образом обе суммы конечны,
если р (х) р (y)Jq (х) q (у) < 1 или р (х) + р (у) < 1.
1 7 8