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

Любопытно при этом отметить, что, если в первом случае1

в СтВМ оказывается недостаточно, необходима их полная стати­ стическая независимость.

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

Выражение для максимальной ошибки результата операции, выполняемой над к переменными, можно получить, рассуждая так же, как и в случае двух переменных. Так, при перемножении трех чисел А = (ах, .. ., af _ x, 1, 0, . . ., 0), В = (Ъх, .. ., bg_ x, 1 , 0 , . . ., 0) и '.С = (cx, . . ., ch_x, 1, 0, . . ., 0) и существовании линейной зависимости между псевдослучайными числами X , Y и Z

276

Окончательно

Р (uvw) = р (и) р (v) р (w) ± 2~U+g~h\ т. е. |emax I = 2_(/+й~Л>.

Таким образом, в общем случае при наличии линейной зави­ симости между к псевдослучайными числами вида

хс ф • • . ф Xf ® Уд 0 . . . ф уg ф . . . ф ze ф . . . ф zh = О,

максимальная ошибка результата операции с к переменными будет равна 2“(1+£+ •■•+h), где /, g, . . ., h — номера младших в этой зависимости разрядов. Как видим, с увеличением числа переменных, участвующих в операции, величина ошибки будет уменьшаться. Если (/ + g + . . . . + h) > I, то emax sg едоп, т. е. величина ошибки становится сравнимой с величиной естественных флуктуаций частоты появления единицы в последовательности. Это значит, что практически данная зависимость не будет оказы­ вать влияния на точность вычислений.

Если разряды псевдослучайных чисел связывает не одно, а несколько линейных соотношений, то для вычисления ошибки результата операции можно воспользоваться методом суперпо­ зиции, при котором суммарная погрешность результата вычис­ ляется как алгебраическая сумма погрешностей, вызванных воздействием каждого из соотношений в отдельности. Надо заме­ тить при этом, что для получения правильного результата должны быть учтены все без исключения зависимости между разрядами. Иными словами, если существует к независимых соотношений, связывающих разряды чисел, то все остальные получаются путем линейных комбинаций этих к соотношений, причем полное их число L = С\ -f- С% —(- - . - —f—Ck-

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

Из полного числа соотношений L выбираются два таких, которые имеют наименьшую сумму номеров (/ + £ + • • • + & ) * Суммируя выбранные соотношения по модулю 2, получим третье, связанное с ними уравнение. Далее, для этих трех соотношений вычисляется разность max (/ + g + . . . + h) — min (/ + g -f •••+fe)-

Если эта разность 2, то ошибка е2 max будет равна

J^-min (/Ч-gf . . . J-A) _j_ 2-max (f:-g Ь . . . +h) J_

В остальных случаях е2 max = 2_min (/+г+ •••+,‘).

Добавим к ним еще четыре, являющиеся их линейными комби­

Из этих семи уравнений первое и седьмое имеют наименьшую сумму (/ + g)i = 3 и (/ + g)l = 4, а уравнение (6) представляет их комбинацию, причем (/ + g)6 — 5. Таким образом,

max (/ + g) — min (/ + g) = 5— 3 = 2

и

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

зываться ни на вероятности появления единиц на выходе преобра­

генерируемыми на выходах ГПСЧ с задержкой на т тактов, при т = s < п будет отражаться на величине дисперсии D (w) числа появлений единицы на выходе преобразователя за п тактов (п — длина случайной последовательности).

Вычислим величину этой дисперсии, воспользовавшись фор­

2 7 8

— корреляционный момент между к-м и Z-м символами последо­ вательности {ик}.

Из (7.36) видно, что корреляционный момент K kl по своему виду совпадает с погрешностью результата операции возведения в квадрат, величина которой может быть вычислена рассмотрен­ ным ранее способом. Нетрудно показать, что максимальная

Разделив правую часть равенства (7.37) на п2, получим выра­ жение для дисперсии частоты появления единицы в последова­

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

в м = 4 ( - ! + т г ) ’

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

В общем случае, если в ГПСЧ имеется L пар разрядов, для которых интервалы сдвига тх, т 2, . . ., xL < п , то для дисперсии частоты будет справедливо следующее соотношение:

Выражение (7.39) характеризует лишь верхнюю границу диспер­ сии частоты со. В действительности же для конкретных значений преобразуемых кодов или вероятностей р (и) = р величина D (со) будет значительно меньше величины, определенной по (7.39). В целях приближенной оценки максимального значения диспер­

279