дослучайных чисел применялась система тестов, служащих для проверки частот появления символов 0 и 1 в отдельных разрядах, распределения числа наборов с весом d = 1, 2, . . ., 10, где (d — число единиц в наборе), а также для проверки среднего значения и дисперсии псевдослучайных чисел. Для проверки случайности вычислялся эмпирический коэффициент корреляции между сосед ними числами, а также выполнялся тест по методу серий [21 ]. Испытанию подвергались 20 выборок по 1000 чисел в каждой. Все тесты свидетельствовали о согласии полученных характери стик с теоретическими.
Таким образом, результаты аналитического и эксперименталь ного исследований статистических характеристик последователь ностей двоичных чисел, генерируемых последовательным ГПСЧ, свидетельствуют об их высоком качестве. С точки зрения простоты реализации рассмотренному генератору нет равных: необходимое для построения ГПСЧ оборудование состоит из регистра сдвига с сумматором по модулю 2, генератора тактовых импульсов, счет чика по модулю s и i выходных вентилей. В качестве недостатка следует назвать меньшую в s раз по сравнению с тактовой частотой регистра сдвига частоту выдачи псевдослучайных чисел. При больших s (s )> 10) это накладывает существенные ограничения на скорость или связанную с ней точность стохастических вычисле ний. В связи с этим необходимо рассмотреть способы построения ГПСЧ, позволяющие устранить указанные недостатки.
40. Параллельный генератор псевдослучайных чисел
Для достижения максимального быстродействия ГСЧ обычно используют параллельный принцип формирования разрядов слу чайного двоичного числа. Для этого в схему ГСЧ включают не обходимое число автономных генераторов случайных двоичных символов, выходы которых в каждом такте работы схемы выраба тывают очередное двоичное число.
По такому же принципу может быть построен и параллельный ГПСЧ. В этом случае для генерирования Z-разрядных двоичных чисел требуется I генераторов псевдослучайных последовательно стей максимальной длины, разрядность которых будет опреде ляться длиной последовательности псевдослучайных чисел. Оче видно, такое решение страдает существенным недостатком — зна чительной сложностью устройства.
Известен однако более оригинальный способ построения па раллельного ГПСЧ [28, 37 ]. В основе его лежит идея использова ния в качестве независимых последовательностей, формируемых в разрядах ГПСЧ, различных участков одной и той же псевдослу чайной последовательности максимальной длины. Идея эта при влекательна тем, что одновременное генерирование различных участков этой последовательности можно осуществить с помощью несложных схем — дополнительного набора сумматоров по
модулю 2 (рис. 118). На выходах этих сумматоров будут генериро ваться идентичные, но сдвинутые относительно друг друга псевдо случайные двоичные последовательности, образуя псевдослучай ные двоичные числа V = (vlt v2, •. ., v{). Рассмотрим более подробно принцип построения такого ГПСЧ.
Возможность одновременного генерирования различных участ ков псевдослучайной последовательности от одного регистра сдвига обусловлена уже известным свойством «сдвига и сложения». Согласно этому свойству при поразрядном сложении по модулю 2 символов последовательности максимальной длины с символами
|
|
|
|
|
|
|
|
|
|
|
|
этой |
же |
последовательности, |
сдвинутой |
относительно исходной |
|
|
|
|
|
на г |
символов, |
получается |
|
|
|
|
|
та же самая последователь |
|
|
|
|
|
ность, |
но сдвинутая |
относи |
|
|
|
|
|
тельно |
исходной |
последова |
|
|
|
|
|
тельности на s =f= |
т символов. |
|
|
|
|
|
При |
этом сложение последо |
|
|
|
|
|
вательностей |
с |
различным |
|
|
|
|
|
сдвигом гг и г2 |
дает |
резу |
|
|
|
|
|
льтирующие |
последователь |
|
|
|
|
|
ности |
|
также |
с |
различным |
Рис. |
118. Параллельный генератор псев |
сдвигом Si |
и s2. |
|
|
|
дослучайных чисел: |
|
Если за исходную принять |
|
v t , ............. .. — разряды |
ГПСЧ |
|
последовательность, образую |
|
|
|
|
|
щуюся в цепи обратной связи |
генератора (рис. 1 1 8 ), |
то последовательности, |
генерируемые в |
разрядах |
регистра сдвига, |
будут |
иметь |
задержки |
rt = |
i, i = |
= 1, |
2, . . |
., in. Суммируя по модулю 2 символы в отдельных разря |
дах регистра, можно получить последовательности, сдвинутые относительно исходной на s символов. При этом оказывается, что полное число различных задержек s, которые можно получить
от |
m-разрядного регистра сдвига (рис. 118), равно |
|
m |
|
'£ C ml = M = 2m~ i , |
|
i-i |
где |
Cm — число сочетаний из тп элементов по г. |
Таким образом, для последовательности максимальной длины
{ак} |
справедливо следующее утверждение. Для любого |
целого |
s (0 |
sc: s |
М — 1) |
существует тп коэффициентов бх, |
б2, . . . |
. . ., |
бт (6*- = 0 или 1) таких, что для каждого к |
|
|
|
ak. s = |
m |
|
|
|
k = 0 , 1, 2, . . М - 1 . |
(7.11) |
Выражение (7.11) означает, что в генераторе с регистром сдвига с помощью дополнительно включенных сумматоров по модулю 2, соединения которых с разрядами регистра определяются наборами коэффициентов 6 lt б2, . . ., 8т, можно получать псевдослучай
ные последовательности, сдвинутые относительно исходной на лю бое число символов от 1 до М.
Значения коэффициентов 6 lt б2, . . 6т , определяющих ве личину задержки s, зависят от функции цепи обратной связи, т. е. от характеристического многочлена ф (х) генератора с реги стром сдвига. Очевидно, если набор этих коэффициентов совпадает с набором а 1, а 2, ••., а т, определяющим ф (х), то величина s будет равна нулю, так как в этом случае выражение (7.11) совпа дает с выражением (7.2), в соответствии с которым формируются символы последовательности {ак}.
Обозначим через sl5 s2, . . ., st число позиций, на которые ока зываются сдвинутыми процессы на выходах I сумматоров парал
лельного |
ГПСЧ (рис. 118). Тогда формирование искомой после |
довательности двоичных чисел V0, F l5 . . ., Vk будет |
опре |
деляться |
выражением |
|
|
V k~ (&k-S,j O'k-Sil . ••) |
(7.12} |
Период этой последовательности не зависит от величин sx, s2, ...
..., Si и равен периоду последовательности максимальной длины {aft}
M = 2m — 1.
Рассмотрим корреляционные свойства последовательности псе вдослучайных чисел Vk, зависящие от значений величин slt s2, . . .
..., st. Поскольку последовательности п15 v2, . . ., vt идентичны с точностью до сдвига фазы, для них справедливы следующие соотношения:
v2 (Jc) = |
v1 (к— s21), v3 (k) = v1 (k — s31), |
. . ., |
vl (k) = v1(k — stl), |
|
v3(k) = v2(k — s32), |
. . ., |
vl (k) = v2(k— s[2), |
|
|
vi(k) = v[. 1 (k— s[il. 1), |
|
k = 0, 1, 2, . . ., |
M - 1, |
гpfiSji = |
Sj — Si — число позиций, на которые сдвинута последо |
вательность в /-м разряде относительно последовательности, фор мируемой в г-м разряде ГПСЧ. Это значит, что в последователь ности псевдослучайных чисел будут коррелированными такие пары чисел Vk и Vk+%, для которых т принимает следующий ряд
значений. s2^, Sgj, . . . |
, s^, s32, |
. . ., s^2, |
. . ., |
i- При всех |
остальных значениях х |
(1 sc; т ^ |
М — 1) |
двоичные |
числа, гене |
рируемые параллельным ГПСЧ, благодаря присущему последо вательностям максимальной длины свойству идеальной автокорре ляции оказываются некоррелированными.
|
|
|
|
|
|
|
Из этого |
следует, что отрезки |
последовательности длиной |
п |
min (sji) |
можно принять за реализации независимых псевдо |
случайных |
чисел, а |
следовательно, значения slt s2, . . ., S[ не |
обходимо |
выбирать |
таким образом, |
чтобы получить величину |
min (s,i) наибольшей. Очевидно, величина max min (s/7) равна
м
целой части от деления М на I. При этом s{ *=« (i —1) -у , т. е.
последовательность {щ,} разбивается на I равных участков, одно временно генерируемых в разрядах ГПСЧ: первый участок полу чается непосредственно на выходе цепи обратной связи, остальные (/ — 1) — на выходах дополнительных сумматоров по модулю 2.
Параллельный ГПСЧ, построенный по такому принципу, ис следуется в работе [37]. В качестве основного недостатка генера тора отмечается сложность схем формирования сдвинутых после довательностей, определяемая числом входов сумматоров по мо дулю 2. Каждый сумматор в среднем имеет т/2 входов. При этом затраты оборудования, необходимые для построения схем форми рования сдвинутых последовательностей, в несколько раз пре вышают затраты, идущие на построение кольцевого регистра сдвига.
Как отмечается в [35], сложность ГПСЧ может быть умень шена, если вблизи границ разбиения периода последовательности (i — 1) Mjl осуществить поиск величин s{ с малым числом единич ных коэффициентов б1? б2, . . ., 8т . Там же приводится пример построения многоразрядного ГПСЧ (I = 15) на основе сдвига ющего регистра с т — 22, в котором произведено разбиение пе риода последовательности на участки с максимальным отклонением их длины от значения MJI, не превышающим 5% . Такое разбиение позволило сократить количество полусумматоров в схеме генера тора до 41. Тем не менее это почти в три раза превышает затраты, необходимые для создания простейшего параллельного ГПСЧ, под которым понимается устройство с количеством полусуммато ров, равным количеству разрядов псевдослучайного числа.
Следует заметить, что не всегда требуется обеспечить генери рование максимально длинной последовательности некоррели рованных чисел. Так, например, если псевдослучайные числа ис пользуются для преобразования переменных, участвующих в вы полнении стохастических операций, реализуемых схемами с раз ветвлением входной последовательности, которые содержат q элементов памяти, то необходимо, чтобы эти числа были некоррелированы при всех т ^ q. Поэтому в этом случае можно восполь зоваться простейшей схемой ГПСЧ, предварительно убедившись, что
min (s/7)> g .
В любом случае при синтезе ГПСЧ возникает задача определе ния величины сдвига s по известному набору коэффициентов бх, б 2, . . ., бт , определяющих топологию соединений выходных сумматоров по модулю 2, или обратная задача. Прямая задача
может быть решена аналитически путем |
деления |
многочлена |
бгх + 62х 3 -[- . . . |
+ бтхт |
на многочлен |
^ (x ) |
= |
l + a i x + |
+ a 2x2 + ••• + a |
m _ i X m_ 1 |
+ xm, сопряженный с |
характеристи |
ческим |
многочленом |
схемы |
с |
регистром сдвига ср (х) = хт + |
+ а ] Х т |
- 1 + а 2хПг~ 2 + |
• • • + |
а ™ |
- I х + 1 (79 ] . Это деление про |
должают до тех пор, пока не получится остаток в виде одночлена X s . Показатель степени этого одночлена будет равен искомому сдвигу s.
Пример: Определим величину сдвига s последовательности, генерируемой на выходе полусумматора схемы (рис. 119). Так
как б1 = |
б3 = 1 (б2 = |
б4 = 0), |
то интересующие нас много |
члены будут иметь вид х + х3 и $ |
(х) = 1 |
X + X4 |
Выполним |
деление этих |
многочленов. |
|
X |
|
I 1 + X + X4 |
|
X |
|
|
|
|
Рис. 119. К определению задержки s последователь ности, генерируемой на вы
|
|
|
|
|
|
Итак, |
s = 9, что и определяет искомый |
ходе |
сумматора по модулю |
сдвиг. Проверим результат, занеся в |
2 в |
параллельном ГПСЧ: |
регистр сдвига исходный код 1000. |
При |
ak , |
— |
С И М В О Л Ы исходной и |
этом на выходах полусумматоров полу |
сдвинутой |
последовательностей |
чим |
следующие последовательности: |
|
|
|
... 111101011001000... — {ак} |
....011001000111101... — |
(s = 9).
Необходимо заметить, что при большом числе разрядов регист ра сдвига тп (т > 20) деление многочленов становится достаточно трудоемкой задачей. Поэтому для определения величины сдвига s более экономным может оказаться непосредственное моделиро вание ГПСЧ на ЦВМ.
Обратная задача — определение набора коэффициентов б1( б2, . . ., бт по заданному сдвигу s не имеет простого аналитиче ского решения [63 ]. В общем случае она также трудно поддается решению путем моделирования на ЦВМ. Однако в частном случае, когда схема цепи обратной связи регистра сдвига состоит только из одного полусумматора, эта задача решается сравнительно просто
[35].
Допустим, что сумматор цепи обратной связи ттг-разрядного регистра сдвига соединяется с т-м и £-м разрядами регистра (рис. 120). Занесем в регистр двоичный набор с единицей только в (г + 1)-м разряде
00 . . . 010 . . . 00. (7.13)
Тогда в течение т тактов работы схемы в регистре сдвига будет циклически перемещаться единственная единица, занимая после довательно следующие разряды
i + 1, £ + 2, . . ., /те — 1 , т, 1 , 2, . . ., г — 1 , г.
