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

вательность с математическим ожиданием, как угодно близким к 0,5.

На практике, однако, обходятся сложением по модулю 2 двух­ трех последовательностей. Так, например, чехословацкий генератор случайных сигналов «GENAP-2» [86] имеет схему образования альтернативы двух независимых последовательностей. Наиболее широкое применение этот способ выравнивания вероятностей

Рис. 103. Схемы выравнивающих сумматоров по модулю 2

нашел в генераторах псевдослучайных последовательностей (см.

гл. VII).

С целью экономии оборудования иногда используют сложение по модулю 2 одной и той же последовательности с задержкой т3, обеспечивающей практическую независимость сигналов на входе сумматора (рис. 103, б). Однако, в этом случае в выходной после­ довательности появляется корреляция с интервалом т3, величину

=Р [(ххх \Jxx%) (ххх2Х V хт2т)]— 4р2 (х) q2 (х) =

=Р (ххгх2х) + Р (хххх2Х) — 4р2 (х) q2 (х) = р (х) q2(х) + р2 (х) q (х) —

—4р 1 (х) q2 {х) — q{x)p {х) [1 —4р (х) q {х)\ =

= [0,5 + Ар (х)[ [0,5 + Ар (г)] {1 —4 [0,5 + Ар (z)[ [0,5 —Ар (г)]} =

= [Ар {х)\2{1 —4 [Ар (х)]2} ^ [Ар {х)]2.

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

z(t) = x (t) z(t — 1) \ Jx (t)z{t~ l) .

217

Смена состояний триггера в соответствии с этой формулой, опи­ сывается графом переходов, изображенным на рис. 104.

Используя, как и ранее, условные вероятности переходов для стационарного режима [р (ж, t) = const], можем записать

P {i) = p{x)P {0) + q{x )P {i).

Но Р (1) = 1 — Р (0) = р (z). Следовательно,

Р (z) — Р (ж) [1 —р (z)l + р (z) [1 —р (ж)].

Отсюда

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

(рис. 104):

К г (1) = Р (zzj) —~ = р (z) q ( x ) - ~ j = ~ [ l — 2p (ж)],

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

Следовательно, если имеется возможность уменьшения частоты генерирования опорной последовательности, то можно применить

Если после каждого считывания информации устанавливать триггер в состояние 0 (рис. 103, в), то дополнительная корреляция выходной последовательности устраняется, но качество выравни­ вания становится хуже. Так, при независимости входных импуль­ сов оказывается справедливой формула (6.11). Если же автокорре­

218

ляционная функция входной последовательности отлична от

ние из исходной неравновероятпой по­ следовательности нулей и единиц комбинаций вида 000... и 111...

и использование равновероятных комбинаций вида 10 и 01, по­ скольку

m2

Рис. 105. Схема выравнивания вероятностей с исполь­ зованием равновероятных комбинаций

на двухразрядный сдвигающий регистр, работающий с тактовой частотой /кв. Содержимое регистра через такт анализируется с по­ мощью сумматора по модулю 2 и в случае обнаружения полезной комбинации один из составляющих ее символов (всегда один и тот же, первый или второй) передается через конъюнктор на выход z. На выходе у вырабатываются метки, указывающие вре­ менное положение полезных символов в последовательности {z}.

219

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

Извлечение информации из ^-разрядного регистра В Р г про­ изводится с постоянной частотой /вых, которая по крайней мере не превышает среднюю частоту появления единиц в последова­ тельности {у}, равную р (х) q (х) /кв. Естественно, что для син­ хронизации работы буферного регистра обеспечивается соотно­ шение 2/вых = /кв/т, где т = 2, 3, 4, . . .

Рис. 106. Граф переходов буферного регистра

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

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

где Р (0) — вероятность нулевого заполнения буферного регистра.

т. е. неравновероятность выходной последовательности пропор­ циональна вероятности отсутствия информации в буферном реги­ стре.

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

220