9.13. Методы генерации псевдослучайных чисел

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

                                          (9.3)

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

На фиг. 9.28 иллюстрируется еще один распространенный метод генерации случайных последовательностей. Предполагается,

Фиг. 9.28. Метод генерации равномерно распределенных случайных чисел.

что в  регистрах памяти содержатся предварительно записанные случайные числа в диапазоне от -1/2 до 1/2 (их можно взять из таблицы случайных чисел). Новое случайное число  генерируется по правилу

                                   (9.4)

причем выполнение операции по модулю 1/2 пояснено на фиг. 9.28 внизу: если результат сложения больше 1/2 , из него вычитается единица; если же результат меньше -1/2 , к нему добавляется единица. Поэтому будет всегда находиться в пределах от -1/2  до 1/2 . Из фиг. 9.29 видно, что если, как и предполагалось, случайные величины  и  равномерно распределены на одном и том же интервале (-1/2 1/2), то и случайная величина  также будет распределена равномерно на том же интервале, так что именно в результате взятия значения суммы по модулю 1/2 треугольное распределение, получающееся после суммирования двух равномерно распределенных величин, опять преобразуется к равномерному. Это означает, что если использовать представление чисел в дополнительном коде, то при условии, что максимально возможное машинное число равно 1/2 , вычисления с использованием формулы (9.4) можно выполнить, просто складывая числа в дополнительном коде и не учитывая переполнений. Итак, преимущество рассматриваемого метода состоит в том, что все вычисления в пределах итерации сводятся к одному сложению. Кроме того, для хранения псевдослучайных последовательностей показывают, что их распределения близки к равномерному, причем их энергетический спектр тоже почти равномерный, т. е. генерируемый шум близок к белому. Таким образом, рассмотренный генератор можно с успехом использовать для цифровой обработки чисел от  до  обычно требуется порядка 50 регистров. Измерения статистических свойств образуемых таким методом псевдослучайных последовательностей показывают, что их распределения близки к равномерному, причем их энергетический спектр тоже почти равномерный, т.е. генерируемый шум близок к белому. Таким образом, рассмотренный генератор можно с успехом использовать для цифровой обработки сигналов.

Фиг. 9.29. Пояснение заворачивания при переполнениях, используемого для генерации равномерно распределенных случайных чисел.

Третий метод получения случайных чисел иллюстрируется на фиг. 9.30. Формирование очередного -разрядного случайного числа  осуществляется на основе двух предшествующих отсчетов  и  по следующему правилу:

,                                           (9.5)

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

Фиг. 9.30. Блок-схема генератора псевдослучайных чисел с равномерным распределением

Фиг. 9.31. Гистограмма генератора случайных чисел с равномерным распределением. (Количество слагаемых = 1,  размер выборки = 49 984, среднее = 5,16, дисперсия=18909,97)

В схеме на фиг. 9.30 принято, что . Данному алгоритму свойственны высокие быстродействие и эффективность. Единственная выполняемая здесь операция —-разрядное сложение по модулю 2, а объем памяти ограничен двумя -разрядными словами для хранения  и . Показано, что при определенных значениях  распределение генерируемых чисел приблизительно равномерное, а спектральная плотность соответствует белому шуму. Например, при  период последовательности будет равен 14942265, т.е. примерно 1500 с при частоте дискретизации 10 кГц. Благодаря своей простоте данный генератор был построен в виде специализированного цифрового устройства с . На фиг. 9.31 приведена гистограмма, полученная приблизительно по 50 000 выходным отсчетам, которые были пронормированы таким образом, что оказались лежащими в диапазоне (—32768, 32767). Пунктиром показано теоретическое значение частоты повторения, соответствующее равномерному распределению (ее значения на краях диапазона несколько меньше, чем в остальной его части, что свидетельствует о меньшей вероятности генерации чисел вблизи краев диапазона). В целом равномерное распределение аппроксимируется достаточно хорошо.