Принципы генерирования случайных и псевдослучайных последовательностей

В задачах активных экспериментальных исследова­ний современных сложных технических систем с приме­нением статистических методов важное место принадле­жит генерированию сигналов возбуждения. Диктуется это не только необходимостью подачи на объект требуе­мого числа воздействий с заданными свойствами, но и максимальной скорости их выработки. Одним из наибо­лее распространенных в настоящее время методов фор­мирования таких процессов является преобразование сигналов, получаемых с помощью так называемых гене­раторов белого шума (ГБШ). В применении к цифровым методам генерирования под белым шумом понимается последовательность некоррелированных чисел или цифр, распределенных, как правило, по равномерному закону.

Известны два основных метода получения цифрового белого шума: физический — генерирование случайных двоичных чисел с помощью специальных устройств — генераторов случайных чисел (ГСЧ); математический— формирование псевдослучайных числовых последова­тельностей (ПСЧП) по специальным программам или с использованием генераторов псевдослучайных чисел (ГПСЧ).

Возможен также и третий путь, совмещающий в себе физический и математический принципы.

Принцип действия ГСЧ состоит в преобразовании случайного сигнала на выходе физического источника шума в импульсную последовательность с вероятностью появления импульса р (1) = 0,5.

В зависимости от способа формирования числовых последовательностей ,существующие ГСЧ можно разде­лить на четыре основных типа:

1) ГСЧ, основанные на использовании случайных состояний бистабильной схемы при периодическом вклю­чении и выключении источника питания;

2) ГСЧ с пересчетом импульсов периодической по­следовательности за случайный интервал времени;

3) ГСЧ с пересчетом импульсов случайной последо­вательности за фиксированный интервал времени;

4) ГСЧ, основанные на дискретизации непрерывного шумового сигнала по двум уровням.

Наиболее часто при разработке быстродействующих и высококачественных ГСЧ применяются последних два способа.

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

Общими и наиболее существенными недостатками, за­трудняющими применение ГБШ, являются следующие факторы:

1. огра­ниченное быстродействие, определяемое первичным ана­логовым источником шума;

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

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

4. невозможность воспроизведения и предсказания генерируемых последовательностей в силу их случайной природы; неоднородность структуры генераторов вследст­вие наличия как аналоговых, так и цифровых узлов, что затрудняет миниатюризацию ГСЧ.

Указанные недостатки физических ГСЧ явились при­чиной все более широкого распространения математических методов получения шумовых числовых последова­тельностей. Мгновенные значения таких псевдослучайных последовательностей в отличие от случайных последовательностей в принципе, могут быть предсказаны заранее. В то же время все оцен­ки статистических характеристик конкретной реализации ПСЧП совпадают с оценками соответствующей ей слу­чайной выборки. Любую статистическую характеристику псевдослучайной числовой последовательности можно получить, используя реализацию длиной в один период повторения ПСЧП. Для истинно случайной последова­тельности это потребовало бы бесконечно большую дли­ну реализации. Искусственное увеличение периода ПС-сигнала неограниченно приближает его структуру к структуре одной из возможных реализаций истинно слу­чайного процесса. Однако и при ограниченных величинах периода в определенных условиях псевдослучайные чис­ловые последовательности могут заменить случайные. При анализе псевдослучайной реализации равной или меньшей длине периода вообще практически невозможно определить, является ли она отрезком регулярной или случайной последовательности. С другой стороны, если записать конкретную случайную реализацию на каком-либо носителе, и периодически воспроизводить ее, то по­лучим регулярную ПСЧП.

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

1. периодический характер псевдослучайного сигнала обусловливает низкий уровень дисперсии оценок, получаемых при усреднении в течение целого числа периодов; характеристики ПСЧП абсолют­но стабильны и определяются алгоритмом формирования псевдослучайных чисел;

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

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

X_k=AX_k-1+C(mod R), k=1,2,3,…

где A,C,R - постоянные числа; X₀>0, A>0, C>0, R>X₀, R> A, R>C.

Данный метод получил название мультипликативного конгруэнтного (при с=0) или смешанного конгруэнтного (при с>0), а формируемая в соответствии последовательность – линейной конгруэнтной.

Второй метод наиболее часто используется в аппаратурных псевдослучайных датчиках и узлах ЭВМ и заключается в получении линейной двоичной последовательности по рекуррентному выражению:

k = 0, 1, 2, 3, . . . , (2.1)

где k — номер такта; —символы выходной по­следовательности; — постоянные коэффициен­ты; знак означает суммирование по модулю два.

При соответствующем выборе коэффициентов генерируемая числовая последовательность (ЧП) имеет мак­симальную величину периода и назы­вается M-последовательностью.

Оценка эффективности представленных методов мате­матического генерирования предусматривает исследова­ние свойств формируемых ПСЧП.