ПРИЛОЖЕНИЕ А. ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ

Здесь приводится простой алгоритм формирования псевдослучайной последовательности чисел, который предназначен для использования в технических приложениях обработки сигналов. Этот алгоритм имеет следующие свойства:

1. Алгоритм реализуется на любой ЭВМ, допускающей работу со словами длиной до 32 бит, т. е. с положительными целыми числами от 0 до 231—11.

2. Алгоритм легко запускается начиная с любой позиции последовательности.

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

4. Отсчеты являются практически независимыми, а спектр последовательности — равномерным.

5. Период последовательности (106 отсчетов) является достаточным для большинства технических приложений.

Алгоритм

Данный алгоритм принадлежит множеству алгоритмов последовательностей на основе вычисления классов вычетов. Свойства таких последовательностей описаны в [1]. В рассматриваемом здесь частном случае целые числа формируются по рекуррентной формуле

Затем последовательность целых чисел нормируется для получения значений в интервале от 0 до 1. Ниже рассматривается начальное значение

Очевидно, что период последовательности не может быть больше М. В соответствии с [1] период равен М, в частности тогда, когда

где К и L — такие целые числа, что Наибольшее значение равно поэтому для формирования по (АЛ) чисел, только меньших 231, необходимо, чтобы

Таким образом, устанавливает соотношение между J и М в Отметим, что при малом начальном значении начинающийся с него сегмент является последовательностью монотонно возрастающих чисел до тех пор, пока не станет больше М. Например, в простейшем случае при последовательность имеет вид Таким образом, последовательность становится случайной при больших значениях

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

Помимо этого, выберем (произвольно)

тогда иервые 70 целых чисел

Отметим, что все целые числа лежат в интервале от 0 до 1 048 576 и оказывается, что эта короткая последовательность, по крайней мере, не обладает нежелательными свойствами.

Поскольку в обычной программе построения случайных чисел числа формируются в интервале от 0 до 1, можно задать отсчет формулой

так, чтобы все случайные числа находились в этом интервале.

По соотношениям можно написать подпрограмму формирования При наличии требования реализуемости этой программы мини-ЭВМ возникает проблема обеспечения автоматической инициализации. Схема инициализации обязательно зависит от типа ЭВМ. Однако для боль шинства ЭВМ работоспособной является версия 1:

Отметим, что во время загрузки данной программы внутренняя переменная IN IT не должна равняться 12357, а в интервалах между вызовами программы как INIT, так и не должны меняться. Начальная установка обеспечивает, как было описано выше, начало случайной последовательности. В данном варианте алгоритма X — фиктивная переменная.

Если не нужна автоматическая инициализация или она должна быть переменной, то представляет интерес версия 2:

В этой версии I изменяется только при инициализации, когда устанавливается ее начальное значение. Например, для установки начального значения и формирования первых двух случайных чисел можно испельзовать предположения

При обращении к подпрограмме RANDOM в версии 2 аргумент (К), естественно, не должен меняться при ее выполнении. Преимущества второго варианта по сравнению с первым состоят в том, что: 1) нет необходимости принимать предположение о том, что промежуточные переменные между обращениями к подпрограмме остаются неизменными; 2) инициализацию подпрограмм можно осуществлять в основной программе произвольным числом в интервале от 0 до 1 048 575.

К недостаткам относится то, что пользователю необходима помнить о правильной инициализации I (или эквивалента I в основной программе) в интервале от 0 до 1 048 575 и о том, что между последовательными вызовами подпрограмм I не должно меняться.

В приводимом ниже примере программы версии 2 рассчитаны первые 70 случайных чисел в соответствии с определенными выше данными. Поскольку в данном примере начальное значение в результате получены те же числа, что и в приведенном выше примере версии 1:

Отметим еще раз, что во втором варианте независимо от начального значения I период случайной последовательности равен 1 048 576.

Свойства случайной последовательности

Приведенные ниже рисунки иллюстрируют некоторые свойства случайной последовательности. На рис. А.1 показано примерное распределение амплитуд последовательностей длиной 10 000. Здесь построена гистограмма для каждой из 100 подпоследовательностей длиной 10000. Каждая гистограмма содержит 10 подынтервалов в интервале от 0 до 1, и на рис. А.1 построены все 100 гистограмм. По оси ординат отложены относительные значения частоты. Из рис. АЛ видно, что значение частоты незначительно отклоняется от 0,1 — идеального для 10 подынтервалов. Аналогично этому на рис. А.2 приведены гистограммы для последовательностей длиной 512. На рис. А.3 показан отрезок белого шума, построенный по первым 1000 числам в соответствии с

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

Автокорреляционная функция первых 132 000 значений в (А.7) имеет вид

и приведена на рис. А.4.

Рис. А.1. Гистограммы для 100 последовательностей длиной 10000

Рис. А.2. Гистограммы для 100 последовательностей длиной 512

Рис. А.3. Первые 1000 значений, построенных по программе RANDOM ( ) - 0,5

Рис. А.4. Автокорреляционная функция первых 132 000 значений, построенных по программе RANDOM ( ) -0,5

Рис. А.5. Автокорреляционная функция следующих 132 000 значений, построенных по программе RANDOM ( ) - 0,5

Рис. А.6. Энергетический спектр случайной последовательности

При наличии нормирующего множителя а значения (1) ...R( 100) достаточно малы, поэтому можно сделать вывод о том, что значения последовательности X(N) являются некоррелированными, т. е. независимыми. На рис. А.5 построен аналогичный график для следующих 132 000 значений. Здесь также значения R(K) составляют менее 1% от R(0).

На рис. А.6 приведен энергетический спектр всей случайной последовательности, который рассчитан по 513 точкам в соответствии с формулой j 1023

Каждое слагаемое в (А.9) представляет собой квадрат амплитуды составляющей дискретного преобразования Фурье (ДПФ). По последовательным неперекрывающимся сегментам последовательности случайных чисел рассчитано 1024 ДПФ по формуле

Таким образом, на рис. А.6 приведен усредненный спектр, практически равномерный на всех частотах. Кроме того, поскольку дисперсия равномерного распределения равна 1/12 от интервала распределения, теоретическое значение на рис. А.6

и все спектральные составляющие близки к этой величине.

Наконец, на рис. А.7 и А.8 приведены результаты для сравнения подпрограмм формирования случайных чисел RANDOM и RANF, используемых в ЭВМ CDC-6600. Здесь случайная последовательность чисел длиной 1 044 480 разбита на 102 сегмента длиной 10 240 каждый. Для каждого сегмента рассчитан, как это описано в связи с (А.9) и (А.10), энергетический спектр, при этом для каждой последовательности вместо 10 взято 1024 неперекрывающихся отрезка. На рис. А.7 и А.8 построены минимальный и максимальный из всех 102 спектров для подпрограмм соответственно RANDOM и RANF. Как следует из сравнения, между обеими подпрограммами нет заметной разницы.

Из сказанного можно прийти к заключению, что подпрограмма RANDOM обладает удовлетворительными свойствами для моделирования процессов обработки сигналов. Помимо относительно короткого (106) периода единственным известным недостатком подпрограммы RANDOM является сравнительно большое время счета при ее реализаций приведенными выше версиями на языке Фортран. Можно считать, что это является платой за портативность.

Рис. А.7. Максимальный и минимальный из 102 энергетических спектров последовательностей длиной 10240

Рис. А.8. Энергетические спектры, аналогичные рис. А.7, полученные на ЭВМ CDC-6600 при замене подпрограммы RANDOM на подпрограмму RANF

Например, при использовании на ЭВМ версии 2 подпрограммы RANDOM для формирования 105 случайных чисел необходимо в среднем около 2,55 с в противоположность 0,47 с, требуемым при использовании на этой же ЭВМ имеющейся в библиотеке подпрограммы RANF. Безусловно, время счета можно сократить, если реализовать программу в машинных кодах.