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

то получим распределение вероятностей появления чисел в этой последовательности, определяемое значением Р (X) = 2" (1 +

+ ~2тL f ) для всех X , за исключением X = (0,0, . . ., 0), для

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

Для оценки качества псевдослучайной последовательности необходимо также исследовать ее на соответствие критерию слу­ чайности. В этом смысле важной характеристикой может служить распределение числа w появлений /-разрядных двоичных наборов (хг, х 2, . . ., xt) на отдельных отрезках последовательности. Если последовательность чисел удовлетворяет критерию случайности, то независимо от длины отрезка п распределение величины w будет одинаковым для любого из различных наборов, причем параметрами распределения будут М (и>) = 2"1п и D (w) = 2~l (1 —

— 2~1) п. Таким образом, анализируя на отрезках последователь­ ности отклонения действительного числа появлений различных наборов от ожидаемого числа, можно получить дополнительное представление о качестве псевдослучайных чисел. Рассмотрим для примера вопрос о числе появлений в последовательности на­ боров (хг, х 2, . . ., хг), состоящих из всех единиц.

Предположим, что последовательность /-разрядных двоичных чисел X = (хх, х 2, . . ., Х[) получена из псевдослучайной после­ довательности максимальной длины {ак} путем последователь­ ных выборок по I символов, т. е.

=2’ ■•ч

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

По аналогии с (7.9) для произвольного отрезка последователь­ ности длиной п можно записать

249

где O s g r = ^ M — 1. В выражениях (7.10) значения характе­ ризуют предельные отклонения действительного числа появлений /-разрядных единичных наборов от ожидаемого числа для отрезков псевдослучайной последовательности длиной п. Очевидно, эти значения будут расти по величине с ростом п и в среднем будут

последовательности с максимальным периодом М = 2т — 1 спра­ ведливо соотношение

Поэтому распределение числа появлений единичных наборов в кон­ кретной последовательности можно оценить по максимальному значению отклонения (обозначим как Ц). Значения Я/, / = 1, 2, 3, 4, для некоторых ГПСЧ, заданных характеристическим много­ членом ср (х) (табл. 19), экспериментальным путем получены в

[871.

Эти значения интересно сравнить со среднеквадратическим отклонением числа появлений /-разрядных двоичных наборов для реализации случайной последовательности длиной п = М/2

°i = V ‘^ 4 T ^ 2-г) п. Для этого в последнем столбце таблицы вычислено отношение 2-i h'i/oi■ Во всех случаях величина отно­ шения не превышает 3. Это означает, что действительные отклоне­ ния числа появлений наборов (ху, ж2, . . ., xt) = (1, 1, . . ., 1) в последовательности псевдослучайных чисел, как и в идеальной случайной последовательности двоичных чисел, лежат в пределах Зн, т. е. отдельные отрезки последовательности псевдослучайных

2 5 0

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

Аналитическому исследованию статистических характеристик последовательности двоичных чисел, получаемых от генератора псевдослучайной двоичной последовательности максимальной длины, посвящена работа [96 ]. Основные результаты этой работы сводятся к следующему.

Если Х 0, X j, . . ., Xk, . . ., Х„_ х — последовательность двоичных чисел, изменяющихся в интервале (0,1) и образованных

резка, для которого фиксированы первые d разрядов в двоичном представлении, т. е. длиной 2~d, имеет среднее значение

Л/(со) =

для любого числа п точек X*, где g (0) = 1 — если все d разрядов, задающие интервал, равны нулю; g (0) = 0 — в остальных случаях.

Дисперсия со ограничена величиной

л « < Ш + 1 ^ ) ( ‘ + > = г Ь т г -

2. Частота ю попадания точек (Х*+1, Xft+2, . . ., Xk+q) в интервал из единичного g-мерного куба, для которого фикси­

251

c Xfe соотношением X* = 1 — 2 Xk — 2 г, усредненные по всем значениям Х'0 статистические характеристики имеют следующий

4. Выборочная автокорреляционная функция последователь­ ности, определенная как

Приведенные результаты свидетельствуют о том, что последо­ вательность двоичных чисел Xk, образованных из псевдослучай­ ной двоичной последовательности максимальной длины {щ,}, характеризуется не только идеальным равномерным распределе­ нием (пн. 1, 2, 3), но также и идеальной автокорреляционной функцией (п. 4). Следует заметить, что последнее справедливо

зуются те же самые символы последовательности {ak}, что приво­ дит к появлению корреляции между числами Xk и X k+x, где т — целое число, удовлетворяющее условию

Результаты экспериментального исследования псевдослучай­ ных чисел, формируемых последовательным ГПСЧ, приводятся

252