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

длиной п<С 1\1 и разрядности чисел IT sg т, то для параллельного

ГПСЧ, первое условие заменяется на п < min (s/7), а вторым является линейная независимость выходов vx, v2, . . ., vt.

Результаты статистических испытаний последовательностей псевдослучайных чисел, генерируемых параллельным ГПСЧ, под­ тверждают это предположение [28, 35]. В [28] исследовался гене­ ратор, построенный по критерию минимума затрат оборудования и состоящий из 31-разрядного регистра сдвига с полусумматором

вцепи обратной связи (ср (х) = х31 -f- х3 + 1) и 30 полусуммато­ ров, которые использовались для формирования трех последова­ тельностей 10-разрядных двоичных чисел. Статистическим тестам были подвергнуты в общей сложности 24 выборки по 16 000 чисел

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

врегистр сдвига заносилось 31-разрядное слово, представляющее собой последовательность максимальной длины, генерируемую многочленом ф (х) = х5 + х2 -f- 1; при испытании второй после­

довательности — число 00...01; при испытании третьей — число И ...И .

Для проверки равномерности распределения анализировалось

и теоретического распределений применялись критерий Колмо­ горова и х 2- Произведена также оценка дисперсии и третьего центрального момента этого распределения. Проверка случай­ ности появления чисел в последовательности производилась по методу серий.

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

В [35 ] исследуются статистические характеристики двадцати двоичных последовательностей, формируемых в разрядах парал­ лельного ГПСЧ (ф (х) = х18 + х11 + 1) и представляющих раз­ личные участки псевдослучайной последовательности максималь­ ной длины (по M il = 13107 символов в каждом). В ходе испытаний производилась оценка вероятностей появления единиц на каждом из участков, а также значений авто- и взаимокорреляционных функций. Кроме того, согласно критерию х2 определялось соот­ ветствие распределения числа серий из единиц (от одной до четы­ рех единиц в серии) геометрическому распределению числа этих серий при независимом и равновероятном появлении символов 0 и 1.

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

262

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

Увеличивая количество разрядов в регистре сдвига, можно получать сколь угодно длинные последовательности некоррели­ рованных псевдослучайных чисел. Так, уже при т = I = 31 можно достичь величины минимального сдвига между последова­ тельностями в разрядах ГПСЧ min (s;-j) M jl >50000000. Прак­ тически это означает, что, например, при тактовой частоте работы устройства со х = 1 МГц генератор будет выдавать случайные двоичные числа со скоростью 10е 31-разрядных чисел в секунду

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

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

263

длины. Причем интервал сдвига между генерируемыми последо­

Свойство 1 вытекает из того факта, что последовательность {cft} начнет повторяться с того момента, когда регистры одно­ временно вернутся в начальные состояния. Если М и У — взаимно простые числа, т. е. (М , N) = 1, то период последовательности

ЫТ = M N .

элемента одной последовательности со всеми элементами другой.

264

Выражение (7.17) означает, что в результате сложения по модулю 2 двух последовательностей {ak_f} и { b k_g}, сдвинутых относительно исходных соответственно на / и g символов, форми­

Из свойства 3 следует, что, последовательности, формируемые на выходах полусумматоров ГПСЧ, изображенного на рис. 121,

исложения» последовательностей {аЛ и {&Д).

Из (7.18)

{c kj © {Ck-sl ■= {a ki © { b k } © \a k\ © [bk-g\ = {bk-e\,

265

eh = 1 — 2 ck, определяет автокорреляционную функцию центри-

Т- 1

рованной последовательности {с*}. Так как 2 c 'kPk-s представляет и=о

собой разность между числом совпадающих и несовпадающих символов в последовательностях {ск} и {с*_5}, которая тожде­ ственна разности между числом нулей и единиц в результирующей

1при s = 0 (mod Т),

—ЛТПРИ s = Xj^' х = 1, 2, . . ., М — 1,

имеет автокорреляционную функцию (АКФ), близкую к идеаль­ ной, поскольку для любых s не кратных М и N значения АКФ

одинаковы и равны — . Отличие ее от АКФ псевдослучайной

последовательности максимальной длины заключается в том, что при значениях s кратных периодам М и N она имеет всплески, равные по величине значениям АКФ порождающих последователь­

накового числа единиц и нулей встречаются одинаково часто, причем количество серий в последовательности по мере увеличе­

числа серий различной длины для некоторых последовательностей {ck}, полученное путем моделирования генератора с двумя реги­ страми сдвига на ЭВМ. В верхней строке таблицы для каждой последовательности {ck} записаны период последовательности Т и характеристические многочлены <р(х), соответствующие порож­

на одну. Максимальная длина серии 11... 1 в последовательности {сА} равна тп + п символов, а серии 00...0 — тп + п — 1 сим­ волов.

266