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

Анализируя условные вероятности переходов для стационарлого режима, можем записать:

P ( n ) = p ( x ) ( i — L ) p ( n - t ) + [ J ^ l

+ ^ ± Р ( п + 1), 0 < п < 1 ,

]P(Z ).

Применяя к этим выражениям метод математической индукции, нетрудно, как и ранее, доказать, что

Р { 0), 0 ^ п ==£ I.

Поскольку все п от 0 до I включительно составляют полную группу событий, суммируя по п, имеем

Ь - 2 Д „ М

Последняя формула позволяет выбрать разрядность регистра и соотношение тактовых частот, обеспечивающие заданный уро­ вень неравновероятности символов в опорной последовательно­ сти {/г}.

Как самостоятельный способ выравнивания вероятностей в ли­ тературе [5, 25] предлагается попеременное использование пря­ мых и инверсных значений символов неравновероятной последо­ вательности. Однако с точки зрения логики преобразования, это есть не что иное, как сложение по модулю 2 исходной случайной последовательности с регулярной, обладающей средним значением 0,5 и автокорреляционной функцией вида

К у {х) = \ { - 1 ) \

221

Результирующая последовательность {h} характеризуется ве­ роятностью

Р{Щ —Р (х) + 0,5 — 2-0,5р (х) = 0,5,

Др (h) — 0

и автокорреляционной функцией

^ ( т) = { й:,( т) + - ^ ^ } ( - 1 Г .

Таким образом, существует большое число способов уравнять вероятности появления нуля и единицы в опорной последователь­ ности, однако в каждом случае либо приходится считаться с по­ явлением дополнительной корреляции, либо применять допол­ нительные источники шума, увеличивая объем оборудования.

34. Способы декорреляции случайных последовательностей

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

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

К г (т) = 4К х (т) К у (т) - Ы 1 - 2 М (x)f К у (т) + [ 1 - 2 М (г/)]2 К х (т).

222

Для опорных последовательностей М (х) ^ М (у) 0,5. Поэтому

Kh( t ) ~ i K x(x)Ky(%.

Если автокорреляция в последовательностях {я} и {у} выз­ вана их выравниванием с помощью триггера со счетным входом, то после сложения по модулю 2 получим

K h (*) = j [1 — 2р (ж)Г [1 —2p(y)\x = j [4 Ар (х) Ар (у)]\

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

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

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

Пронумеруем символы последовательности в порядке возра­ стания номеров разрядов регистра и рассмотрим положение этих символов в к последовательных тактах, заключая в скобки номера считываемых символов (табл. 16).

тельно считываемых в каждом такте символов отличаются внутри цикла на четыре, одиннадцать, десять. Следовательно,

К г (т = 1) = К г (1) = \ [Кх (4) + К х (10) + К х (11)1.

Рассматривая аналогичным образом разности номеров симво­ лов, считываемых через такт, через два такта и т. д. можно об­ наружить, что

к г (2) = | [Кх (1) + К х (7) + К х (14)],

Кг (3) = К х(3),

Кг (4) = { [Кх (7) + К х (8) + Кг (13)1,

223

Т а б л и ц а 16

И т . д .

Эффект декорреляции на интервалах, некратных числу точек считывания, основан на знакопеременное™ автокорреляционной функции исходной последовательности, в связи с чем при переме­ шивании происходит ее частичная компенсация и перенос с одних

224

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

ствами отсутствует.

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

свероятностью доступа к каждому разряду, равной 1//. Запись

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

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

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

0,5 (рис. 108).

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

к — 1 будут соответствовать интервалам такой же длительности на входе, а один — входному интервалу величиной к + 1. Таким образом, средневзвешенное значение автокорреляционной функции