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

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

Случайные числа с основанием, отличным от 2, могут быть получены путем простого укрупнения или преобразования двоич­ ных чисел. Наиболее просто получить числа в системе счисления с основанием 2к, к = 1, 2, 3, . . . Так, последовательность одно­ разрядных восьмеричных чисел (к = 3) может быть получена простым объединением трех параллельных двоичных последова­

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

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

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

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

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

Если рассматривать «короткие» реализации псевдослучайного

190

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

Генератор псевдослучайного сигнала под воздействием помех может случайным образом изменять длительность периода и тогда регулярность процесса нарушается.

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

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

Более подробно генераторы случайных и псевдослучайных двоичных последовательностей рассмотрены в последующих двух главах книги.

29.Получение двоичных чисел

сравномерным законом распределения

Докажем, что в простейшем случае равновероятные Z-разряд- ные двоичные числа H t могут быть получены объединением I опор­ ных последовательностей с учетом веса каждого разряда. При этом случайное число представляет собой линейную комбинацию двоичных случайных величин h x, h 2, . . ., ht\

i

H t = 2°^ + 2Ш2+ 22h3+ . . . + 2l~1hl = 2

i= 1

где hi — мгновенное значение i-й опорной последовательности. Таким образом, появление конкретного числа Н представляет собой сложное событие, являющееся пересечением I событий вида ht = 1 и hj = 0.

191

Если опорные последовательности {/^}, { h 2} , . . ., {h t} не­ зависимы, то вероятность такого слояшого события равна произ­ ведению вероятностей элементарных событий, и для числа, содер­ жащего ровно d единиц, имеем

роятность не должна зависеть от с? и для любого из 21 возможных чисел должна быть равной

р ® - 7 -

что возможно лишь в случае р (h) = 1 — р (К) = 0,5.

Таким образом, необходимыми и достаточными ^условиями равновероятности генерируемых чисел являются независимость

а)

Рис. 91. Схема генератора случайных чисел: а — параллельного типа; б — последовательного типа

опорных последовательностей и равенство вероятностей появле­ ния в них символов 0 и 1.

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

192

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

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

По определению

К н (г) = М {\П— М (Я)] [Я, - М (Н))} = М (ЯЯТ) - М 2 (Я).

Математическое ожидание произведения Я Я Х найдем с помощью подстановки

М (ННХ) = М {[2°/^ (Z) + 21/г2 (Z) + . . . + 2l~1hl (Z)] X

Х 1 2 °М *-г ) + 2 1 М *- т ) + . • . + 2г- 1 М *- т )]} =

Разобьем сумму под знаком математического ожидания на две части и воспользуемся формулой математического ожидания суммы

i

М(ННТ) = 2 ‘^ h2M [hi (t) h j ( t - x ) ] + t, J=i

i¥=i

i

+ 2 22(i_1)ikT [h( (t) h t (t — t)]. ;=/=i

По условиям задачи случайные двоичные величины hi и hj под знаком первой суммы независимы. Следовательно,

М [ht (t) hj (t — x)] — M (ht) M (h}) = M2 (h).

При наличии же автокорреляции в i-й опорной последовательности

Подставляя полученные выражения в исходную формулу для К ц (т), имеем

i

Кн(т) =22»('-1)А :а.(г).

(=1

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

Если статистические свойства всех опорных последовательно­

i =1

Определим в этом случае нормированную корреляционную функцию последовательности случайных чисел

Кн (т)

гн (х)

D ( H ) •

С другой стороны,

Тогда

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

Если между автокорреляционными функциями опорных после­ довательностей выполняется соотношение

Я Л<(т) = 2 - * « - « Д : А 1 ( г ) ,

то

1 9 4