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

Вершины этого графа соответствуют числам, накопленным в счет­ чике, а дугам придан вес, равный условным вероятностям пере­ хода из одного состояния в другое. С помощью этой модели можно для любого конечного числа тактов т рассчитать вероятности возможных состояний счетчика как вероятности использования соответствующих вершин графа, если задаться начальным состоя­ нием, т. е. распределением вероятностей использования вершин графа в такте t — т. Для расчета формулы (4.14), (4.15) и (4.16) приводятся к следующему виду:

Р ( — 1, t — k) = q(x) р (у) Р (0, t —k — l) + q ( x ) P { —l, t — k — 1),

Р ( 0, t — k) = q ( x ) p (y ) P ( l, t — k — l) + [p(x)p(y) +

+ q {x )q (y ))P { 0, t — k — l ) + p ( x ) P ( — l, t — k — 1),

в соответствии с (2.6) значения этой функции для прямой и инверс­

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

Р ( п = —1, t —т) = 1, Р(п + —1, *— т) = 0.

167

На рис. 77 показаны в полулогарифмическом масштабе кри­ вые К г (т) для некоторых конкретных значений р (у) и р (z). Числа у кривых указывают значение р (у). По рисунку можно судить, что автокорреляционная функция довольно быстро убы­ вает с увеличением т, а закон ее изменения при этом прибли­ жается к экспоненциальному. Корреляция максимальна при зна­ чениях р (z)i близких к 0,75, и возрастает с уменьшением р (у).

Рис. 77. Автокорреляционная функция выход­ ной последовательности в схеме, изображен­

Одно из возможных назначений схемы заключается в укруп­ нении масштаба переменной при несимметричном кодировании, например, в два раза (р (у) = 0,5). Тогда при р {£) = 0,75 авто­ корреляционная функция на интервале т = 60 составляет 0,0017 и в дальнейшем убывает на порядок при увеличении интервала примерно на каждые 70 тактов.

Наличие автокорреляции в выходной последовательности сви­ детельствует об инерционных свойствах схемы, т. е. о том, что значение выходной переменной с необходимой точностью устана­ вливается лишь спустя некоторое время, зависящее от первона­ чальной установки счетчика. Переходный режим можно воспро­ извести с помощью той же модели, что и расчет автокорреляцион­ ной функции, если принять t = т.

168

Пусть до начала отсчета времени решения р (z) = 0, что соот­ ветствует Р (п = —1, г ^ 0) = 1. Тогда значение выходной стохастической переменной как функции времени определяется вероятностью р (z, t) = Р (п ^ 0, t |п = —1, t = 0). При этом начальные условия для моделирования остаются такими же, как и в предыдущей задаче, так что моделирование можно вести в

один прием. Ap(zj Расчетная формула для

абсолютной ошибки представ­ ления выходной переменной имеет вид

Ap(z) = p ( z ) ~ p ( z , t) =

= p{z) — P(n>? 0,

t\n = —i, t = 0).

250тактов.

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

24. Реверсивный счетчик в режиме деления переменных при однолинейном симметричном кодировании

Если в схеме, рассмотренной в предыдущем параграфе, заме­ нить конъюнктор в цепи обратной связи логическим элементом, реализующим функцию эквивалентности (рис. 79), то граф пере­ ходов схемы примет вид, показанный на рис. 80. По условным ве­ роятностям переходов граф можно разделить на две части. Для правой (п (t — к) 0) среднее изменение числа, накопленного в счетчике, в каждом такте составляет

An = n(t — к + 1) — n(t — k ) = p ( x ) q {у) — q(x) р(у).

169

В левой части графа (п (t — к) < 0)

An = p(x)p(y) — q(x)q(y).

Объединяя эти два соотношения и усредняя по всем ге, полу чаем

+ p (x )p (y ) — q (x )q (y )= 0.

t

Рис. 80. Граф переходов схемы, изображенной на рис. 79

Решая последнее уравнение относительно р (z), получаем

p ( z ) = р М + р М - '

2р (у) — 1

При симметричном однолинейном кодировании

Р ( * ) = ~ ( 1X) и р(у) у (1 + П

1 7 0

С помощью простой подстановки нетрудно убедиться в том, что рассматриваемая схема действительно выполняет операцию деле­ ния переменных

Для определения условий устойчивости найдем распределение вероятностей состояний счетчика. Вновь обращаясь к графу переходов (рис. 80), можем записать:

Р (п) = р (х) q {у) Р (п —1) + [р (ж) p{y) + q (ж) q (у)] Р (в) +

по всем п от п до оо. После приведения подобных членов получим:

(4.17)

Эти рекуррентные соотношения позволяют определить вероят­ ность любого состояния счетчика, если известны Р (0) и Р (—1):

Для того чтобы найти оставшиеся неизвестными вероятности, необходимо еще раз обратиться к графу переходов (рис. 80):

Р(0) = р (ж) р (у) Р (—1) + [р (ж) р (у) + q (ж) q(y)]P (0) +

+ q(x)p(y)P (i),

(4.18)

P ( - i ) = p ( x )p ( jy ) P ( - 2 ) +

г [р (х) q (у) + q (ж) р(у)\р (—1) 'Г q (ж) р (у) Р (0).

Подстановкой

171

которую мы имеем право сделать в соответствии с формулами (4.17), неопределенность разрешить не удается, так как оба урав­ нения (4.18) при этом оказываются тождественными.

Обращаясь теперь к соотношению (4.19), находим

Р= (у)— р (х)]1р (х)+ Р (у)—1]

'p(x)p{y)[2p(y) — l\

Итак, распределение состояний счетчика в стационарном ре­ жиме имеет вид

172