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

ностью {ск}, получается в результате поразрядного сложения по

ностях {ak} и {bk} встречается соответственно 2m_i и 2п~1 раз, а набор из I нулей — (2m~l — 1) и (2"”г — 1) раз. Поэтому число появле­ ний произвольного ненулевого набора (сг, с2, . . ., ct) в последо­ вательности {ск} равно

[(2m — 1) — 2m~l] 2 n~l -f- 2m~l (2n~l — 1) = 2m f — 2т_г — 2 n~l = = 2- 1 [(2m- 1) (2n- 1 ) - 1 ] = 2- 1 (T — 1),

267

волов не более чем на единицу. Таким образом, распределение двоичных чисел, образованных из следующих один за другим символов последовательности {ск} за период Т = MN, практи­ чески равномерное.

Итак, псевдослучайная последовательность {ск}, образован­ ная суммированием по модулю 2 двух двоичных последователь­ ностей максимальной длины, у которых значения периодов пред­ ставляют собой взаимно простые числа, так же, как псевдослу­ чайная последовательность максимальной длины, обладает всеми свойствами, присущими случайной последовательности равно­ вероятных символов 0 и 1, и на практике может с успехом ее заменять. Свойства 3—5 являются ключевыми на пути к понима­ нию принципов построения двухрегистрового параллельного ГПСЧ.

С практической точки зрения важно установить соотношения между числом разрядов тп и п в регистрах сдвига для получения последовательности {ск}, имеющей период Т = MN. Из теории чисел [9] известно, что m и п будут взаимно просты, если взаимно просты числа М = 2m — 1 и N = 2" — 1. К сожалению, обратное утверждение в общем случае неверно. Поэтому о делимости чисел М и N можно судить только по разложению их на простые сомно­ жители (см. табл. 18). При этом оказывается, что числа М = = 2т — 1и./У = 2" — 1 для любых пг, п ^ 34 являются взаимно­ простыми, если взаимно просты числа m и п. Таким образом, получаем простое правило: для получения последовательности {ск} с периодом Т — MN необходимо применить регистры сдвига, разрядности тп и п которых — взаимно простые числа.

Определим интервал сдвига s для последовательностей, форми­ руемых на выходах полусумматоров ГПСЧ с двумя регистрами сдвига. Пусть последовательность {c*_s} получена в результате сложения по модулю 2 /-того разряда регистра сдвига с большим числом разрядов п и г-того разряда регистра с меньшим числом разрядов тп. Нетрудно видеть, что символы последовательности {ck-s} начнут повторять символы последовательности {ск} через такое число тактов работы ГПСЧ s, за которое в г-м и /-м разрядах регистров одновременно появятся символы последовательностей

268

Здесь х и у наименьшие целые числа, при которых выполняется

Оценим значения интервалов сдвига между последователь­ ностями, генерируемыми на выходах различных полусумматоров

а величину h = i — j назовем шагом полусумматора. Поскольку для каждого h существует единственная пара значений х, у, удовлетворяющая (7.23), то, как следует из (7.22), последователь­ ности, получаемые на выходах полусумматоров с одинаковым шагом, будут сдвинуты относительно друг друга на величину s < т. Если же полусумматоры ГПСЧ характеризуются различ­ ным шагом h, то генерируемые на их выходах псевдослучайные последовательности оказываются сдвинутыми на s > N — т сим­ волов.

Для определения величины сдвига s между последователь­ ностями на выходах полусумматоров удобнее воспользоваться выражением

ражению (7.24) нетрудно определить такие h, которые обеспечи­ вают наибольшие интервалы сдвига между последовательностями.

Так как h может принимать только следующий ряд значений:

—п + 1, —п + 2, . . ., —1, 0, 1, . . ., т — 2, т — 1, максималь­ ное число полусумматоров, имеющих различный шаг h, в ГПСЧ с регистрами сдвига из т и п разрядов равно т + п — 1.

Из рассмотренных соотношений следует вывод. В двух­ регистровом ГПСЧ на выходах полусумматоров, соединяющих разряды сдвигающих регистров с различным шагом h = i — /, генерируются псевдослучайные двоичные последовательности, сдвинутые относительно друг друга на интервал s, приблизи­ тельно кратный большему из периодов исходных последователь­ ностей максимальной длины. Значения интервалов сдвига очень просто могут быть вычислены по формулам (7.22, 7.24).

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

269

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

В первом случае двоичные числа формировались в результате поразрядного суммирования по модулю 2 содержимого регистров сдвига, характеризуемых многочленами х31 + х 3 + 1 и х 33 + х13+ 1 ,

30 полусумматоров, соединяющих разряды регистров сдвига, описываемых многочленами х17 + х3 + 1 и х18 + х7 + 1 . Для оценки качества генерируемых последовательностей применялись следующие тесты.

1. Для проверки равномерности одномерного, двумерного и трехмерного распределений двоичных чисел (по 64 точки в каж­ дом случае) [53]. В первом случае координаты точки определя­ лись 6 старшими разрядами двоичного числа, во втором — 3 стар­ шими разрядами пары чисел, в третьем — 2 разрядами трех смежных чисел.

2. Для проверки случайности следования чисел. Использо­ вался наиболее чувствительный к корреляции тест убывающих или возрастающих серий [80], в котором эмпирическое распре­ деление числа серий из последовательно убывающих или возраста­ ющих по величине псевдослучайных чисел сравнивалось с теоре­ тическим, рассчитанным для идеальной, случайной последова­ тельности.

В качестве критерия согласия в каждом из тестов применялся критерий %2. Объем испытаний — 50 выборок по 3200 чисел. Результаты тестов показали хорошее согласие эксперименталь­ ных распределений с теоретическими.

42. Влияние детерминированной структуры псевдослучайных чисел на точность вычислений

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

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

270