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

Покажем на примере, что данное выражение не занижает действительного значения дисперсии.

Пример. Допустим, что между разрядами двоичных чисел Xk, ■составляющих псевдослучайную последовательность, имеют место

min(/ + g) Ss 6,

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

Итак, мы рассмотрели основные виды ошибок, возникающих при стохастических вычислениях вследствие неидеальности ГПСЧ

280

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

Задача выбора типа и синтеза ГПСЧ решается в следующей последовательности:

1)выбирается тип генератора — последовательный или парал­ лельный;

2)определяются разрядности регистров сдвига и функции цепей обратной связи;

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

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

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

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

последовательности, необходимо на вход преобразователя «код — вероятность» подавать случайные числа статистически независи­ мые в пределах q тактов работы генератора. Данное требование к ГПСЧ можно выполнить, если длина регистра сдвига т будет не меньше, чем ql, в противном случае разряды псевдослучайных чисел окажутся связанными линейной зависимостью. Заметим, что условие т = ql эквивалентно условию получения в ГПСЧ q независимых последовательностей /-разрядных двоичных чисел^

281

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

т + п.

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

При этом между смежными во времени псевдослучайными чис­ лами X = (хг, £ 2, . . ., х г1) и X ' = {х{, х'2, ..., хД), появля­ ющимися на выходах генератора, будут иметь место следующие зависимости:

причем последняя зависимость будет определять максимальную погрешность операции, поскольку для нее / + g = min (/ -f- g)t = = 15. Следовательно, |emax |= 2~1ъ <^2~12.

Если же разряды генератора выбрать в соответствии с есте­ ственной нумерацией разрядов регистра сдвига, то псевдослу­ чайные числа X и X ' будут связаны соотношениями:

при этом |етах = 2 ~а >- 2-12.

Таким образом, в рассмотренном примере правильно выбран­ ная нумерация разрядов генератора позволила сократить число разрядов в регистре сдвига до 18, в то время как из условия статистической независимости чисел X и X ' т = ql = 22. Мини-

2 8 2

мальная разрядность регистра сдвига определяется из условия генерирования последовательности псевдослучайных чисел дли­ ной п 22! и равна 21.

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

Наибольшие трудности при синтезе ГПСЧ связаны с выбором отводов от разрядов регистра сдвига к сумматорам по модулю 2 в параллельном ГПСЧ. Эта задача имеет два аспекта. Первый связан с получением необходимого сдвига между последователь­ ностями на выходах генератора и был рассмотрен в п. п. 40 и 41. Второй связан с обеспечением линейной независимости символов на этих выходах. Остановимся подробней на втором вопросе.

Будем, как и раньше, формирование двоичных чисел в парал­

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

Как известно [41], наличие линейной зависимости между компонентами вектора V можно установить, вычислив ранг матрицы коэффициентов |б ||. Компоненты вектора V (или строки матрицы I б I) будут линейно независимы, если ранг матрицы г равен числу компонентов I вектора V. Если ранг матрицы г <^1, то компоненты вектора V являются линейно зависимыми.

Условие г •< I означает, что в матрице |б |существует хотя бы один минор порядка г (определитель составленный из элементов

отличный от нуля, а все миноры порядка больше г равны нулю. Минор Д называют базисным, а строки, входящие в него, — базисными строками. При этом, любая из I—г оставшихся строк

может быть представлена линейной комбинацией базисных.

283

Таким образом, если компоненты вектора V линейно зави­ симы, то все миноры Z-ro порядка (Z sg т) матрицы ||8|| равны нулю. Для отыскания Z— г уравнений, связывающих компо­ ненты ух, и2, . . ., vt линейной зависимостью, необходимо выпол­ нить такую последовательность действий.

1. Составить матрицу размерности (г X т) из г — 1 базисных строк и одной из оставшихся (Z — г) строк, например, с номером t.

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

3.Составить новую матрицу, заменив следующую базисную строку той же самой и поставив вычеркнутую базисную строку

на прежнее место. Повторить пункт 2 и т. д. Всего г раз.

4. Компоненты вектора V, соответствующие отмеченным базис­ ным строкам ур, . . ., vq, будут представлять искомую линейную комбинацию для одного из Z—г компонентов vt, т. е.

Щ = и р Ф • • • ® * v

5. Выполнить пункты 1—4 для остальных Z—г—1 строк. Следует заметить, что сумма по модулю 2 коэффициентов

8Р1, . . ., &qi, бн каждого г-го столбца для совокупности линейно зависимых строк должна быть равна нулю, т. е.

бр/0 •••0 б 9/© б(£ = 0, i = l, 2, . . ., т.

Анализ линейной зависимости между выходами параллель­ ного ГПСЧ можно произвести и другим способом, если предвари­ тельно определены интервалы сдвига s x, s2, ..., st между последо­ вательностями, генерируемыми на этих’ выходах, и последова­ тельностью, получаемой на выходе цепи обратной связи. Для этого необходимо многочлен вида

делится без остатка на ф (х), то это свидетельствует о наличии линейной связи между задержанными последовательностями, для которых коэффициенты у{ = 1. Придавая набору коэффи­ циентов Yi> Y2’ ■• ч Y/ все возможные сочетания значений 0 и 1, можно определить все линейные соотношения, связывающие выходы ГПСЧ.

Если в результате анализа установлено, что I ^ т выходов оказались связанными линейной зависимостью, то это значит, что отводы от разрядов регистра сдвига к выходным сумматорам выбраны неудачно, и необходимо изменить соединения входов для

„284