Принципы генерирования случайных и псевдослучайных последовательностей
В задачах активных экспериментальных исследований современных сложных технических систем с применением статистических методов важное место принадлежит генерированию сигналов возбуждения. Диктуется это не только необходимостью подачи на объект требуемого числа воздействий с заданными свойствами, но и максимальной скорости их выработки. Одним из наиболее распространенных в настоящее время методов формирования таких процессов является преобразование сигналов, получаемых с помощью так называемых генераторов белого шума (ГБШ). В применении к цифровым методам генерирования под белым шумом понимается последовательность некоррелированных чисел или цифр, распределенных, как правило, по равномерному закону.
Известны два основных метода получения цифрового белого шума: физический — генерирование случайных двоичных чисел с помощью специальных устройств — генераторов случайных чисел (ГСЧ); математический— формирование псевдослучайных числовых последовательностей (ПСЧП) по специальным программам или с использованием генераторов псевдослучайных чисел (ГПСЧ).
Возможен также и третий путь, совмещающий в себе физический и математический принципы.
Принцип действия ГСЧ состоит в преобразовании случайного сигнала на выходе физического источника шума в импульсную последовательность с вероятностью появления импульса р (1) = 0,5.
В зависимости от способа формирования числовых последовательностей ,существующие ГСЧ можно разделить на четыре основных типа:
1) ГСЧ, основанные на использовании случайных состояний бистабильной схемы при периодическом включении и выключении источника питания;
2) ГСЧ с пересчетом импульсов периодической последовательности за случайный интервал времени;
3) ГСЧ с пересчетом импульсов случайной последовательности за фиксированный интервал времени;
4) ГСЧ, основанные на дискретизации непрерывного шумового сигнала по двум уровням.
Наиболее часто при разработке быстродействующих и высококачественных ГСЧ применяются последних два способа.
В генераторах с пересчетом случайных импульсов за фиксированный интервал времени равновероятность символов выходной последовательности достигается путем выполнения суммирования по модулю два. В то же время данная операция, протекающая последовательно во времени, снижает быстродействие ГСЧ, что ограничивает область их применения. Более высоким быстродействием обладают ГСЧ, основанные на дискретизации непрерывного шумового сигнала по двум уровням. Однако данным устройствам свойственна высокая чувствительность к изменениям параметров первичного шумового сигнала, главным образом его среднего значения.
Общими и наиболее существенными недостатками, затрудняющими применение ГБШ, являются следующие факторы:
1. ограниченное быстродействие, определяемое первичным аналоговым источником шума;
2. низкая стабильность основных вероятностных характеристик, объясняемая нестабильностью первичных источников, дрейфом параметров преобразующих схем, источников питания и др., что требует периодической статистической проверки качества генерируемой последовательности;
3. сложность аппаратурной реализации, вызываемая наличием нескольких источников питания (для физического источника шума и цифровых схем), необходимостью стабилизации и фильтрации их напряжения, развязки линий питания от линий устройства, коррекции выходной последовательности и др.;
4. невозможность воспроизведения и предсказания генерируемых последовательностей в силу их случайной природы; неоднородность структуры генераторов вследствие наличия как аналоговых, так и цифровых узлов, что затрудняет миниатюризацию ГСЧ.
Указанные недостатки физических ГСЧ явились причиной все более широкого распространения математических методов получения шумовых числовых последовательностей. Мгновенные значения таких псевдослучайных последовательностей в отличие от случайных последовательностей в принципе, могут быть предсказаны заранее. В то же время все оценки статистических характеристик конкретной реализации ПСЧП совпадают с оценками соответствующей ей случайной выборки. Любую статистическую характеристику псевдослучайной числовой последовательности можно получить, используя реализацию длиной в один период повторения ПСЧП. Для истинно случайной последовательности это потребовало бы бесконечно большую длину реализации. Искусственное увеличение периода ПС-сигнала неограниченно приближает его структуру к структуре одной из возможных реализаций истинно случайного процесса. Однако и при ограниченных величинах периода в определенных условиях псевдослучайные числовые последовательности могут заменить случайные. При анализе псевдослучайной реализации равной или меньшей длине периода вообще практически невозможно определить, является ли она отрезком регулярной или случайной последовательности. С другой стороны, если записать конкретную случайную реализацию на каком-либо носителе, и периодически воспроизводить ее, то получим регулярную ПСЧП.
Таким образом, с точки зрения реальных характеристик трудно установить границу между случайными и псевдослучайными числовыми последовательностями. В то же время применение ПСЧП имеет ряд существенных преимуществ:
1. периодический характер псевдослучайного сигнала обусловливает низкий уровень дисперсии оценок, получаемых при усреднении в течение целого числа периодов; характеристики ПСЧП абсолютно стабильны и определяются алгоритмом формирования псевдослучайных чисел;
2. последовательность можно повторить с любого желаемого участка реализации, для чего не требуется сложных запоминающих устройств и др.
Наиболее часто при генерировании ПСПЧ с равномерным распределением используются два метода. Первый, лежащий в основе большинства современных программных датчиков и некоторых специализированных устройств, описывается рекуррентным соотношением:
Xk=AXk-1+C(mod R), k=1,2,3,…
где A,C,R - постоянные числа; X0>0, A>0, C>0, R>X0, R> A, R>C.
Данный метод получил название мультипликативного конгруэнтного (при с=0) или смешанного конгруэнтного (при с>0), а формируемая в соответствии последовательность – линейной конгруэнтной.
Второй метод наиболее часто используется в аппаратурных псевдослучайных датчиках и узлах ЭВМ и заключается в получении линейной двоичной последовательности по рекуррентному выражению:
k = 0, 1, 2, 3, . . . , (2.1)
где k — номер такта; —символы выходной последовательности;
— постоянные коэффициенты; знак
означает суммирование по модулю два.
При соответствующем выборе коэффициентов генерируемая числовая последовательность (ЧП) имеет максимальную величину периода и называется M-последовательностью.
Оценка эффективности представленных методов математического генерирования предусматривает исследование свойств формируемых ПСЧП.