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

1.В последовательности максимальной длины {ак} все воз­ можные выборки по т смежных символов образуют 2т — 1 раз­ личных двоичных наборов. Единственным отсутствующим является запрещенный набор, состоящий из т нулей.

Данное свойство очевидно, поскольку М = 2т — 1 пред­ ставляет период последовательности {ак}. Это означает, что в ре­ гистре сдвига произойдет смена ровно 2т — 1 состояний прежде, чем эти состояния начнут повторяться в новом цикле. Следова­ тельно, вид последовательности {ak} и ее свойства не зависят от исходного состояния схемы генератора.

2.Число единичных символов в периоде последовательности

{ak} равно 2т~1, а число нулевых символов — (2т~1 — 1), т. е. в периоде любой последовательности максимальной длины число символов 1 всегда на единицу больше числа нулей. Это зна­ чит, что, увеличивая число разрядов т регистра сдвига, можно

числа 2т~1 серий следующих друг за другом одинаковых символов серии из одного символа (0 или 1) встречаются 2т-2 раз, из двух символов (00 или И) — 2т-3 раз, из трех символов (000 или 111) — 2т~4 раз и т. д., серии из т — 1 нулей и т единиц встречаются по одному разу. у

244

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

Рассмотрим еще два интересных свойства, раскрывающих кор­ реляционную структуру последовательностей максимальной длины.

Данное свойство получило название свойства «сдвига и сложения» [44]. Оно представляет особый интерес по той причине, что именно им обусловлено подобие корреляционных свойств последователь­ ности максимальной длины и случайной последовательности двоич­ ных символов. Известно [63], что если случайную последователь­ ность равновероятных символов { ЕД почленно сравнивать с той же, но сдвинутой на любое число s позиций последовательностью {^/г-sb т0 разность между числом (п — d) позиций, на которых символы совпадают, и числом d позиций, где они отличаются, в вероятностном смысле будет равна нулю, т. е.

где п — длина последовательности {£Д. Если последовательность { £Д состоит из символов 1 и —1, то выражение (7.5) совпадает с выражением

(7.6)

определяющим автокорреляционную функцию (АКФ) последова­ тельности { £Д, значение которой будет равно 1 для^ s = 0 и нулю — для любого другого s.

Сравним выражение (7.6) с АКФ последовательности макси­ мальной длины. Обозначим через {аД последовательность из 1 и —1 с периодом М — 2т — 1, полученную из {аД преобразова­ нием а'и = 1 — 2ак. Тогда выражение

М-1

(7.7)

245

/

последовательности достаточно большим, можно получить зна­ чение К а’ (s) для любого s Ф 0 (mod М) сколь угодно близким к нулю. Следовательно, можно считать, что АКФ последователь­ ности максимальной длины и идеальной случайной последователь­ ности практически совпадают. Поэтому последнее свойство псевдо­ случайных последовательностей часто называют свойством «иде­ альной автокорреляции».

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

Следует отметить важное обстоятельство, отличающее псевдо­ случайную последовательность от случайной. Если для случайной последовательности рассмотренные числовые характеристики ре­ ализуются асимптотически в зависимости от объема выборки, то для псевдослучайной последовательности гипотетические харак­ теристики практически достигаются на интервале равном периоду последовательности. Это свойство псевдослучайных последователь­ ностей может быть выгодно использовано, например, для сокраще­ ния времени выполнения арифметических операций в СтВМ.

В заключение отметим, что более полные сведения из теории генерирования псевдослучайных последовательностей можно найти в работе [63].

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

Важной особенностью равномерно распределенных случ йных двоичных чисел X = (xlt х 2, . . ., xt) является тот факт, что зна­ чения отдельных разрядов xt, i — 1, 2, . . ., I, этих чисел можно рассматривать как реализации независимых случайных величин

246

£;• с распределениями

^ (g* = 0) = /> (g, = 1) -----1-, i = l,' 2, . . 1.

Благодаря этому последовательность таких чисел может быть образована из случайной последовательности { \k) равновероят­ ных символов 0 и 1 в виде непересекающихся выборок из I симво­ лов. ГСЧ, реализующий такой способ формирования случайных чисел, будет содержать генератор последовательности двоичных символов и Z-разрядный регистр сдвига, в котором за I последова-

m2

СдЬиг

Х=(хи хг , . . , х 1)

Рис. 117. Генератор псевдослучайных чисел последова­ тельного типа

тельных тактов работы формируется двоичное число (хг, х г, . . .

. . ., xt). Такой тип ГСЧ называют последовательным. Аналогичный принцип может быть положен в основу построе­

ния генераторов псевдослучайных чисел. Последовательным ГПСЧ может непосредственно служить генератор псевдослучайной дво­ ичной последовательности максимальной длины (рис. 117). В та­

ческой независимости смежных двоичных чисел в формируемой

ствии с выражением (7.8), являются периодическими. Нетрудно убедиться, что период последовательности равен частному от

247

регистра сдвига. Вид последовательности псевдослучайных чисел, а следовательно, ее характеристики не зависят от начального со­ стояния схемы только в том случае, когда ее период максимален и равен М = 2™ — 1. Очевидно, для получения такой последова­ тельности необходимо число сдвигов s выбрать взаимно простым к М. Для этого можно воспользоваться табл. 18, в которой при­ водится разложение чисел М = 2т —■1 на простые сомножители

[63].

Оценим статистические характеристики последовательности псев­ дослучайных чисел максимальной длины М — 2т — 1, генерируе­ мой в последовательном ГПСЧ. Прежде всего покажем, что рас­ пределение двоичных чисел в последовательности является равно­ мерным.

Действительно, поскольку период последовательности равен М = 2т — 1, то каждому числу в последовательности соответст­ вует одно из 2т — 1 различных состояний регистра сдвига. Из этого следует, что в периоде последовательности М — 2т — 1 любое двоичное число (хг, х 2, . . ., хг), образованное на выходах I разрядов регистра сдвига, встретится ровно 2т~1 раз, за исключе­ нием числа (0,0, . . ., 0), которое встретится на один раз меньше.

Если число появлений ^-разрядных двоичных наборов на выхо­ дах ГПСЧ разделить на период последовательности М = 2т — 1,

248