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

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

Очевидно, число тактов работы схемы, за которое регистр сдвига из состояния (7.13) переходит в состояние, соответствующее набору (7.14), будет равно (т + s). Из этого следует, что если на­ чальным состоянием регистра является слово (7.13), то любое

(т -f к)-е состояние будет определять расстановку входов сумма­ тора, реализующего сдвиг на к символов. Если первые (т — t) символов слова, полученного в регистре после (т + s) тактов работы, перенести в его конец, то новое слово будет представлять искомый набор коэффициентов.

Следует отметить, что после яг-кратного применения оператора цепи обратной связи к слову (7.13) в регистре сдвига окажется слово, отличающееся от слова (7.13) наличием «1» в первом разряде. Поэтому определение коэффициентов б1? б2, . . ., 8т на ЦВМ можно производить путем s-кратного применения оператора цепи обратной связи к этому слову.

Рассмотренный метод также с успехом может быть использо­ ван для определения величины сдвига, реализуемого сумматорами с малым числом входов L (например, L = 2). Для этого в последо­ вательности та-разрядных слов, представляющих состояния ре­ гистра сдвига, фиксируются слова с соответствующим числом единиц и их номера к, которые будут равны искомым величинам сдвига s.

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

258

Для этого обозначим последовательность состояний регистра сдвига как последовательность m-мерных векторов X*. = (£]% x2ky, . . ., Хт1), образованных из символов двоичной последова­ тельности максимальной длины {ак}

а последовательность двоичных чисел на выходах ГПСЧ — как последовательность Z-мерных векторов Vk —- (j^ , vlky, •• v}ky). Тогда процесс формирования псевдослучайных чисел в параллель­ ном ГПСЧ можно представить в виде линейного преобразования векторов Хк в соответствующие им векторы Vk, причем компоненты векторов будут связаны следующей системой уравнений:

v[h) = 6 u 4 ft)Ф 8uxih)Ф •■•Ф тх(т\ z;№) = 6214 fe)0 6 224 ft)© . . .0 б 2та:<£\

yifc) = S a 4 h)© 6/24ft)©- ••©bimx%\ .

или в матричной форме:

В (7.15) наборы коэффициентов 8ql, 692, . . 8?m, q = 1, 2 , Z,

определяют топологию связей от разрядов регистра к сумматорам по модулю 2.

Отметим важное свойство линейного преобразования. Как известно, компоненты вектора Vk могут быть линейно независимы только при условии I sg т. В частности, если каждая строка мат­ рицы состоит только из двух не равных нулю элементов (что со­ ответствует простейшей реализации генератора), то максималь­ ное число линейно независимых выходов будет равно (т — 1). Это значит, что максимальная разрядность двоичных чисел, ге­ нерируемых параллельным ГПСЧ, не может превышать длины регистра сдвига т. В противном случае символы в разрядах числа оказываются линейно зависимыми.

Рассмотрим распределение псевдослучайных чисел в последо­ вательности, формируемой ГПСЧ, за период М — 2т — 1.

Допустим, что I т и коэффициенты 6qi удовлетворяют тре­ бованию линейной независимости компонентов вектора Vk, т. е.

. . ., Vt) и подставим в (7.15). Тогда (7.15) представит совместную

систему I уравнений с т неизвестными х г, х 2, . . ., хт, принима­ ющими только два значения 0 и 1. Поэтому число решений такой системы будет равно 2m_i. Причем полной совокупности из 2г наборов (ylt v2, . . vt) соответствует 2т решений. Иначе говоря, m-мерное векторное пространство из 2т двоичных векторов X преобразуется в J-мерное пространство из 21двоичных векторов V таким образом, что каждому вектору V соответствует 2т~ 1 векто­ ров X.

Но в пространстве из М = 2т — 1 векторов Xk, образованных псевдослучайной последовательностью максимальной длины, от­ сутствует единственный — нулевой вектор, который преобразуется также в нулевой вектор Vk.

Из этих рассуждений следует, что в периоде М = 2т — 1 последовательности псевдослучайных чисел, генерируемых па­ раллельным ГПСЧ, любое двоичное число (vx, v2, . . ., vt) встре­ тится точно 2т~1 раз, за исключением числа (0, 0, . . ., 0), которое встретится 2m-i — 1 раз.

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

Рассмотрим еще одно интересное свойство последовательности псевдослучайных чисел { Vk), формируемой в параллельном ГПСЧ, которое может служить отражением идеальной «случайности» появления чисел в этой последовательности. Это свойство касается распределения числа двоичных наборов, получаемых на выходах ГПСЧ, в функции от интервала т, через который они повторяются.

дение {р*а*} определяется почленным умножением соответству­ ющих символов в {рй}и{а*}. Тогда интервал х между идентичными наборами из I символов на выходах параллельного ГПСЧ выра­ жается равенством {pfeaft} = {pk^k-т}-

Определим число идентичных наборов в периоде последова­ тельности {Vk}, отделенных друг от друга интервалом т. Пусть

Ыопределяет произвольный набор из I линейно независимых

260

для всех х (1 ^ х ^ М — 1). Отыщем такое г, для которого все символы последовательности {рkak -r) равны 0. Тогда в силу (7.16) {Pkak} = {Pkak-x}, что означает наличие одинаковых на­ боров из I символов в последовательности { ak}, интервал между которыми равен т.

Как следует из предыдущего свойства, число нулевых наборов из I символов в периоде последовательности {ak} равно (2m_i — 1), поэтому существует такое же число идентичных наборов для каж­ дого т, удовлетворяющего (7.16).

Для х = М имеем {pfeaft} — {р&^-м}. где к — 0, 1, 2, . . .

. . ., М — 1, так как М = 2т — 1 — период последовательности. Следовательно, существует (2т — 1) одинаковых наборов, разделен­ ных интервалом х — М. Таким образом, число появлений иден­ тичных наборов (vlt у2, . . ., vt), формируемых в разрядах парал­ лельного ГПСЧ и разделенных интервалом т за период последо­

х ^ 1, равно 2т~1. Как показано в [77], последовательность чи­ сел, генерируемая последовательным ГПСЧ, имеет такое же распределение числа одинаковых наборов в функции от т.

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

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

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

261