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

т. е. автокорреляционная функция на единичном интервале умень­ шается почти на порядок. С увеличением числа разрядов регистра эффект будет еще большим.

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

35. Некоторые практические схемы ГСДП

Рассмотрим несколько известных схем, в которых в той или иной степени нашли применение изложенные выше принципы построения генераторов случайных двоичных последовательно­ стей (ГСДП).

Функциональная схема датчика равномерно распределенных случайных чисел, предложенная Р. М. Акчуриным 1 (рис. 109),

1 Авт. свидетельство СССР № 210471. Бюллетень «Изобретения, промышл. образцы и тов. знаки», 1968, № 6.

226

по существу представляет собой схему Z-канального генератора случайных последовательностей с математическим ожиданием М (h) = 0,5. В каждом канале имеется самостоятельный источник шума ГШ . По сигналу У1 квантованный шум подается на счетные входы триггеров Т1 . . . Т1, которые выполняют функцию вырав­ нивания вероятностей. Каждая из полученных таким образом

Рис. 109. Функциональная схема датчика случайных чисел, предложенная Р. М. Акчуриным

последовательностей складывается по модулю 2 с последователь­ ностью, вырабатываемой (Z+ 1)-м аналогичным каналом. Это преобразование осуществляется логической схемой, состоящей из набора конъюнкторов и дизъюнкторов и выполняющей задачу декорреляции последовательностей.

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

В этом можно убедиться следующим образом:

K h.ht - Р (Kb,;) —М (ht) М (hj) = Р \(xz \J xz) (yz \Jуz)\ —

— P (xz\ J xz) P (yz \Jyz) = P (xyz) + P (xyz) —

— [P (xz) -j- P (xz)) [P (yz) + P (yz)].

Поскольку по условию x, у и z независимы и ранее установлено, что на выходе триггера со счетным входом/? (х) = р (у) = р (z) = = q (х) — q (у) = q (z) = 0,5, имеем

Khihj = Р И Р (у) Я (z) ч (ж) q (у) Р (z) —

— [Р (х) q(z) + q (х) р (z)] [р (у) q(z) + q (у) р (z)] =

=0,125 + 0Д25 - (0,25 + 0,25) (0,25 + 0,25) = 0,

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

довательностей осуществляется по сигналу У2.

Рис. 110. Функциональная схема блока формирования опорных последо­ вательностей генератора «GENAP-2»

Другой характерный пример — схема блока формирования опорных последовательностей (рис. 110) чехословацкого генера­ тора «GENAP-2» [86]. Она состоит из двух идентичных каналов, управляемых общим источником шума. В схеме использован

Работу одного из каналов иллюстрирует рис. 111. Другой канал работает аналогичным образом со сдвигом на один такт.

Шум первичного источника ГШ подвергается усилению и огра­ ничению с помощью формирователя телеграфного сигнала Ф.

2 2 8

Дифференцирующая цепочка R — С — Д вырабатывает импульсы, соответствующие по времени переходу шумового сигнала через нуль в одном из направлений. Полученная таким образом случай­ ная нетактированная последовательность импульсов поступает на счетный вход триггера Т1 незаблокированного канала. В течение

Рис. 111. Временная диаграмма работы блока форми­ рования опорных последовательностей генератора

«GENAP-2»

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

При заблокировании канала, с помощью управляющего сиг­ нала У1 производится исследование состояния триггера Т1, в соответствии с которым вырабатывается символ выходной после­ довательности 0 или 1. Этим же сигналом с задержкой, вносимой элементом D, триггер Т1 устанавливается в 0, и схема оказывается подготовленной к следующему циклу пересчета. Время задержки

229

выбирается большим длительности импульса У1, но меньшим длительности блокирующего импульса.

Имеющийся в генераторе «GENAP-2» блок синхронизации (на рисунке не показан), вырабатывающий импульсы У1 и У2, коор­ динирует работу каналов таким образом, что их выходные сиг­ налы вырабатываются поочередно, через такт. Поэтому их можно либо использовать раздельно, либо объединить в одну последова­ тельность с вдвое большей тактовой частотой, равной тактовой частоте работы генератора.

В работе [64] предложена схема датчика равномерно распре­ деленных случайных чисел, основанная на пересчете тактовых импульсов за случайный интервал времени (рис. 112). Схема состоит из двух /-разрядных счетчиков Сч1 и Сч2, динамического триггера Д Т , анализатора результата А , ряда вспомогательных элементов и работает следующим образом (рис. 113).

Генератор случайных импульсов ГС И вырабатывает пуассо­ новский импульсный поток, который с помощью схемы синфазирования СС синхронизируется с тактовыми импульсами устрой­ ства. Последние с выхода генератора тактовых импульсов Г Т И непрерывно поступают на вход счетчика Сч2, предназначенного для формирования непересекающихся отрезков времени, длитель­ ность которых определяет цикл работы схемы.

Сигналом начала (конца) цикла является импульс переполне­ ния Сч2, который с задержкой, реализуемой элементом D и при­ мерно равной полупериоду тактовой частоты, устанавливает в О счетчик Сч1 (вход УО) и запускает динамический триггер Д Т . По­ следний генерирует разрушающие импульсы, поступающие на вход вентиля & 1, на второй вход которого подаются импульсы от ГТ И .

Счетчик Сч1 начинает подсчет числа тактовых импульсов, по­ ступающих на его вход через & J. Процесс счета продолжается до тех пор, пока динамический триггер не окажется установленным

в0 первым же случайным импульсом, поступившим из схемы СС. Импульс начала'следующего цикла через схему А разрешает вы­ дачу накопленного в Сч1 случайного числа на выход устройства.

Назначение анализатора А состоит в регистрации поступления

впределах цикла более, чем одного случайного импульса от СС.

Втаком случае разрешение на передачу числа на выход устройства не выдается, а состояние выхода А сигнализирует о том, что цикл

был холостым.

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

230

Рис. 112. Схема генератора слуяайных чисел, осно­ ванная на пересчете тактовых импульсов за случай­ ный интервал времени

Разряды Сч 1

Рис. И З. Временная диаграмма работы схемы, изобра­ женной на рис. 112 (I — 3)

36. Методика экспериментального исследования ГСДП

Формулы для расчета генераторов случайных последователь­ ностей, приведенные в данной главе, позволяют проектировать ГСДП с требуемыми характеристиками. Однако, поскольку рас­ чет основывается на усредненных характеристиках первичных источников шума, можно ожидать, что свойства реальных гене­ раторов будут отличаться от расчетных.

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

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

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

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

П

м * ( * ) = т 2 х* *

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

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

232