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

или

,q/p2(/-l)

ГН ^ = ~ i ; l 1 Г)Ч W ^ ° ’7 5 lrh{ (т),

т. e. нормированная автокорреляционная функция числовой по­ следовательности примерно в 0,75 I раз больше, чем у самой «слу­ чайной» из используемых опорных последовательностей.

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

В принципе можно обойтись одним ГОП, формируя от него

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

Компромисным решением является параллельно-последова­ тельный тип генератора, который представляет собой d параллель­ но работающих (//й)-разрядных генераторов последовательного типа.

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

30. Формирование стохастических констант

По определению стохастическая константа (СК) представляет собой случайную (псевдослучайную) последовательность двоич­ ных символов с заданной и не изменяющейся в процессе вычисле­ ний вероятностью появления единицы (нуля). В простейшем слу­ чае, если задано Р (с — 1) = Р (с = 0) = 0,5, константа может быть представлена обычной опорной последовательностью.

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

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

М(z) = exp [—М (.т)].

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

ехр \—М (ж)] = 1— М (х){ 1 — 0,5М (х) х X [1 — 0,34375М (х) (1 - 0,25М (ж))]},

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

вательности с математическими ожиданиями 0,5; 0,25 и 0,34375. В качестве первой из них можно использовать опорную последо­ вательность, а две другие могут быть сформированы из опорных с помощью схемы, изображенной на рис. 93, а. Конъюнктор & 1 осуществляет операцию возведения в куб и на его выходе ма­ тематическое ожидание последовательности равно 0,125 = 0,53. Конъюнкторы & 2 и & 3 выполняют возведение в квадрат и фор­ мируют последовательности с математическим ожиданием 0,25 = = 0,5 2. Промежуточные последовательности «0,125» и «0,25» объединяются с помощью дизъюнктора, выполняющего в соот­ ветствии с формулой (2.28) преобразование 0,25 + 0,125 — 0,25 х

X 0,125 = 0,34375.

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

196

Этих недостатков лишена схема на рис. 93, б. Однако, как можно видеть, она требует в три с половиной раза больше опорных последовательностей.

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

Рис. 93. Схемы формирования стохастических констант

явления того или иного числа может быть установлен с помощью дешифратора (рис. 93, в), а несовместность событий, заключа­ ющихся в появлении отличных друг от друга чисел, позволяет легко выполнять сложение вероятностей этих событий с помощью дизъюнкторов. Так, если Z-разрядный ГСЧ вырабатывает равно­ мерно распределенные числа, таким путем могут быть сформированы последовательности с математическим ожиданием

к = 1, 2, 3, . . (2» -1).

197

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

ходов дешифратора. При этом коэффициент пропорциональности констант (мас­

штаб) составляет

тс = 2 4

Дополнительные возможности для формирования СК откры­ вает использование генератора неравновероятных случайных чи­ сел. Так, например, если с помощью схемы, аналогичной той, которая показана на рис. 93, а или 93, б, или каким-либо другим путем получены независимые последовательности с математиче­ скими ожиданиями 0,5; 0,25 и 0,125, то их можно рассматривать как трехразрядный генератор случайных чисел, распределение которых описывается табл. 13.

С помощью таких чисел в схеме рис. 93, в может быть сформи­ рована любая из стохастических констант, определяемых выраже­ нием

Универсальным генератором стохастических констант является также устройство, структурная схема которого изображена на рис. 90. Если величина порога, характеризующая квантователь

198