единиц в точности соответствуют значениям входных переменных.
Такие |
последовательности |
могут быть получены, |
например, |
на выходе преобразователя «код — вероятность», если идеальны |
статистические характеристики последовательности |
случайных |
чисел, |
используемых для |
преобразования. |
|
Можно ожидать, что параметры последовательности на выходе преобразователя будут близки параметрам бернуллиевской после довательности и в случае применения ГПСЧ, поскольку, как мы знаем, последовательность псевдослучайных чисел по своим характеристикам практически совпадает с идеальной случайной последовательностью. Тем не менее, фактор закономерности получения псевдослучайных чисел может отрицательно сказы ваться на точности вычислений. Примером тому может служить влияние линейной зависимости между разрядами псевдослучай ного числа на вероятность появления единицы на выходе преобра зователя «код — вероятность» р (и). Как отмечалось в п. 40, при наличии такой зависимости распределение вероятностей появле ния двоичных чисел в последовательности будет отличаться от равномерного, а следовательно, вероятность р (и) может не соот ветствовать преобразуемому коду, т. е. ошибка может возникать уже на этапе преобразования входных переменных СтВМ.
Детерминизм, присущий ГПСЧ, в конечном счете проявляется в виде линейной зависимости символов в разрядах генерируемых
чисел. Поэтому рассмотрим влияние |
такого рода зависимостей |
на результаты |
операций. |
|
Определим |
вначале погрешность |
преобразования «код — ве |
роятность» при наличии линейной зависимости между разрядами псевдослучайного числа X = (хх, х 2, . . ., xt) вида хс ® . . . ® xf ^ 0 Условимся считать, что в последнем выражении разряды записаны
в порядке возрастания |
индексов, т. е. с |
|
/. |
|
|
|
Пусть в регистре детерминированного числа преобразователя |
«код — вероятность» |
(рис. 37) |
записано |
двоичное |
число |
А = |
=- |
(аг, а 2, |
. . ., |
а г), |
в котором разряд аг = |
1, а остальные йг+ 1 = |
= |
. . . = |
й/ = |
0, |
причем г < / . |
|
|
|
|
|
|
|
|
Представим |
|
логическую функцию |
схемы |
преобразователя |
в |
ДСНФ |
|
|
|
|
u = \ J |
. . . xAi, |
|
|
|
(7.25) |
|
|
|
|
|
|
|
|
|
где произведения берутся по всем наборам а = |
( а х, а 2, . . ., |
а,) |
<; |
С А = (й], . . ., |
а,). |
|
|
|
|
|
|
|
|
|
|
Так как в нашем примере число А = |
(а1, . . ., |
аг_ 1, |
1,0, . . ., |
0), |
то в (7.25) |
произведения х га '. . |
. |
будут попарно склеиваться, |
в |
результате чего выражение |
(7.25) |
преобразуется |
к виду |
|
|
|
|
|
и = |
\Jxf' |
. . . х^г. |
|
|
|
|
(7.26) |
|
|
|
|
|
(“•........ °>)<(а>’ -Г- -- |
аг-1- Ч |
|
|
|
|
Из (7.26) видим, что выход и преобразователя зависит только от г случайных переменных x v . . ., хг, причем по условию эти
переменные являются независимыми. Принимая во внимание, что вероятности р (xj) = . . . — р (xt) = 1/2, получим, что в данном случае вероятность появления единицы на выходе преобразова
теля р (и) |
будет пропорциональна двоичному числу А р (и) = |
— А 2~1, |
т. е. погрешность преобразования равна нулю. |
Пусть теперь преобразуемое число Л (а,, а 2, . . ., a r_l , 1, 0...0) |
таково, что г — /. Очевидно, переменные, входящие в (7.26), теперь |
уже будут линейно зависимыми, поэтому для вычисления вероят
ности р (и) необходимо |
выполнить |
несложные преобразования |
в (7.26): |
|
V xi' . . |
|
= |
|
и |
- |
. X a r |
|
|
(Oil, |
r |
1) |
|
|
. • ar)<(a,, |
■ ■ |
|
|
|
. . . Xa r - 1 1 |
VV ^l' ■•• |
(7.27) |
•- |
“г-1)< (a., /*•—l•,J V -l) |
' |
|
В (7.27) первый |
член не содержит |
переменных, |
связанных |
линейной зависимостью, поэтому вероятность появления единицы на выходе преобразователя, определяемая этим членом, будет равна (А 2~1 — 2-г). Второй член содержит только г — 1 линейно независимых переменных, поэтому вероятность появления на выходах ГПСЧ набора символов, определяемого данным членом,
равна |
2“(г_1), если |
ас ф ... |
ф af — 0 (af |
= 0) |
или нулю, |
если |
ас 0 |
••• ® af = 1 |
(а-f — 0). |
Следовательно, |
вероятность |
р (и) |
будет |
равна |
|
|
|
|
|
|
р (и) = (А 2- 1— 2-г) + (2-г "1 или 0) |
= А 2' 1 ± 2~г. |
|
Таким образом, имеет место ошибка преобразования еи, равная по абсолютной величине 2 ~г, где г = f.
Покажем, что если г > /, то ошибка преобразования по абсо лютной величине будет меньше, чем 2~f. Пусть г = / + 1. Тогда логическую функцию и преобразователя «код — вероятность» можно преобразовать к следующему виду:
и = |
j^\/х“>. . |
. X“ r - 2j |
V |
|
|
(“'------ ссг_2)<(аи Г. 2 ., |
аг_2) |
если аг. 1 |
= |
0, или |
|
|
lt = |
[V i j 1 . . • |
V xi ‘ •••xr- 1 V Xl' ■■■xr-lxr, |
(“ <........... a r -2 ) < ( “ ‘. ” 2 -- ar-2) |
|
если йг_1 |
= |
1. |
|
|
Переходя к вероятности p (и), в первом случае получим
р (и) = (А2~1— 2~r) + (2_rfl или 0) = А2~1 ± 2~г.
Во втором случае, |
учитывая, что |
Р (х°' . . . |
у |
. . . хУрг?) = 2~г+- или 2-?+1, |
так как ас ф . . . ® af — 0 либо при af = О, либо при af = 1, получим
р (и) — (А2~1 — 2_rfl — 2~г) |
-j- (2~г |
или 2~г ~1) = |
= А2~1 ± 2~г, |
т. е. |8 |= |
2 - '= 2-<'+!>< 2-'. |
Аналогичным образом |
можно показать, |
что при любом г > / |
погрешность преобразования е„ по абсолютной величине будет меньше чем 2 ~f.
Таким образом, при наличии линейной зависимости между разрядами псевдослучайного числа вида хс ® . . . ® xf ~~ 0 может возникать ошибка преобразования, вызывающая отклонение ве роятности р (и) от точного значения, определяемого кодом числа А . При этом максимальная величина этой ошибки |еитах |зави
сит от номера / |
младшего из связанных |
линейной зависимостью |
разрядов псевдослучайного числа |
X и равна 2 ~f . |
|
Исследуем |
теперь вопрос |
о |
влиянии |
линейной |
зависимости |
между псевдослучайными |
числами |
на |
|
точность |
вычислений. |
В качестве примера рассмотрим операцию умножения. |
Пусть случайные |
двоичные |
переменные и |
и к, |
участвующие |
в операции, получаются |
на |
выходах |
двух |
преобразователей |
«код — вероятность», |
на |
входы |
которых |
от |
ГПСЧ поступают |
двоичные числа |
X = |
(хх, |
х 2, |
. . |
., |
x t) |
и Y = |
(ух, |
у 2, . . ., уд- |
Будем считать, что случайные переменные в каждом из чисел
статистически независимы |
и |
имеют вероятности р (х х) |
= . . . = |
= Р fo) = Р ( у д = * •• |
= |
Р (Уд = |
Очевидно, |
при этих |
условиях вероятности появления единиц на выходах преобразо вателей р (и) и р (v) будут строго пропорциональны преобразуе мым числам А = (ах, а 2, . . ., ад и Z? = (Ъх, Ъ2, . . ., Ъд-
Покажем, как влияет на результат операции наличие функцио |
нальной зависимости вида |
хс ® |
. . . ф xf = |
yd ® . . . ф yg. Как |
и раньше, будем считать, |
что |
переменные |
записаны в порядке |
возрастания номеров, т. е. с |
< . . . < / |
и d < . |
. . < ig ■ Отметим |
также, что в случае преобразования кодов А = |
(а,, |
а 2, . . |
., а д |
и В = (Ъх, |
Ь2, . |
. ., Ъд, |
в которых символы аг и Ъ5 |
равны |
1, а |
остальные |
аг+1, |
. . ., a t |
и |
bs + 1, . . ., |
bL — нулю, |
выход пре |
образователя есть функция от первых г или s переменных, |
т. е. |
а ~ фх (%i, ^2, ••ш, |
^д ^ v = g>2 (ух. У2, |
* • Уэ)' |
(7.28) |
При |
этом номера г и s могут принимать любые значения в преде |
лах |
(1 Eg г, s ss I)- Рассмотрим два случая. |
1. |
Пусть перемножаются двоичные числа А и В , для которых |
г < |
/ |
или s < ig . Рассмотрим выражение для вероятности произ |
ведения Р (uv), которое в случае статистической независимости
переменных и и к равно Р (uv) = |
р (и) р ( v). |
|
Из (7.28) |
следует, что |
|
|
uv = % (x x, х 2, . . ., av)cp2 |
( У г , у2, ■. У 5) , |
(7.29) |
18 В. В. |
Яковлев |
|
273 |
причем все переменные, входящие в (7.29), статистически незави симы, так как по условию не включают полной группы линейно
зависимых переменных. |
Следовательно, Р (uv) = р (и)р ( v), что |
соответствует точному |
результату. |
|
2. Допустим теперь, |
что г |
/ и s 5^ g. Тогда |
произведение |
(7.29) , которое перепишем в |
виде |
|
uv ==ср(^2, |
^2» •••> |
••*т £/s)> |
(7.30) |
будет включать полную группу линейно зависимых переменных. Выражая одну из этих переменных через остальные и подставляя в (7.30), сократим таким образом на единицу число переменных
в (7.30). Следовательно, ф Ф ф', |
где ф — исходная функция (7.30) |
при |
независимых переменных; |
ф' — преобразованная |
функция |
(7.30) |
с числом переменных (г + s — 1). |
|
Легко убедиться, что при этом Р (uv) ф р (u)p(v). |
|
Пример: Вычислим Р (uv) и ошибку е для случая А = |
0,10101, |
В = 0,01010 и |
= |
(7.31) |
|
|
Переключательные функции преобразователей и и к запишем в ДСНФ и произведем все возможные склеивания произведений; получим:
и = |
\J хф . . . х^ |
= |
ху V хлх2х3 Vxlx.2x3xix5, |
|
|
(а,, . . |
а 6) < ( 1 , о , 1 , |
0 , |
1 ) |
|
|
V= |
VуЬ •••уЬ |
|
= У1У2 V УхУьУзУ*- |
|
Тогда |
( P i , • ■ . , P i ) 0<, ( 1 , |
О, 1) |
|
|
|
|
|
|
uv = |
хгуху2 V xlx2xay1y2 V Ххх 2х гxixbyly2 VХ\У\УгУзУь V |
|
|
v |
x1x2xay1y2yayi Vххх2х3х^хьуру2у3у^. |
(7.32) |
Выражение (7.32) представляет собой ДНФ, в которой все про изведения суть взаимоисключающие события. Поэтому вероят ность Р (uv) равна сумме вероятностей каждого из этих событий. Учитывая наличие зависимости (7.31), получим
|
Р (uv) = 2'2 + 0 + 0 + 0 + 2~® |
2~8 = |
|
. |
|
При этом ошибка |
|
|
|
|
|
е = Р (uv) — p(u)p(v) = -Цг |
21 |
10 |
33 |
1 |
|
32 |
32 |
512 |
^ 16 ‘ |
|
|
Приведенный пример подтверждает вывод, что вероятность появления единицы на выходе конъюктора Р (uv) во втором случае отличается от произведения вероятностей р (и) и р (v).
Таким образом, линейная зависимость между разрядами псевдослучайных чисел при выполнении операции умножения в СтВМ приводит к методическим ошибкам, которые, как показы
вает пример, могут превышать допустимый предел е = 2_t,+1). В частных случаях, когда соотношение между младшими из не равных нулю разрядов чисел А и В таково, что г < / или s < g , результат операции будет точным.
Вычислим максимальное значение ошибки произведения. Та кая ошибка, как и в случае преобразования кодов, будет иметь место при выполнении операции над числами А ж В , для которых
г = / и s = g. Поэтому с |
учетом (7.28) можем записать: |
и = |
V |
|
(«1, . . |
a |
1) |
v = V уЬ • • • уЪ-
(Р>.........Pg)<(*>- ••■- V i - в
Воспользовавшись разложением функций и ж v таким же, как (7.27), представим произведение uv в следующем виде:
u v = |
[ V |
|
[ V ' ■■■У%] |
|
(“•......... |
“м ) < ( аь •••,.«/_!) |
(Р............ |
Pg)<(fcb •••, »g-l' |
1) |
|
V х°' . . . |
х) [ v |
уЬ •••ylii1} |
|
|
|
(Pi, •••, Pg-i)<(feb |
•••> hg-l) |
|
|
V Я?1•••xaf h i x by^f |
. . . ybgg-iyg. |
(7.33) |
В (7.33) первые два члена не содержат полной группы линейно зависимых переменных. Поэтому, переходя к вероятностям, можно записать
Р (uv) = [р (и) — 2~f] р (и) + 2-Г [р (и) — 2-Ц +
+ Р (* 1 1 ■■■ |
xj у\' . . . |
yViJ/g). |
(7.34) |
Вероятность же появления набора из / + g символов, в кото ром один из символов получается линейной комбинацией других, равна
|
|
|
|
|
|
|
|
|
ж |
2-(f+«-D) |
если ас 0 |
. . . 0 |
a f = bd ® . . . |
® b g, |
|
О, |
если ас ф . . . |
ф а { =£ bd ® . . . ф bg, |
|
|
|
где af |
= bg == |
0. |
значения |
в (7.34), |
получим |
|
|
Подставляя |
эти |
|
|
|
|
|
Р (uv) = р (и ) р (v) ± |
2- |
|
|
т. е. максимальная |
ошибка етах по |
абсолютной |
величине |
равна |
2~{fn\ |
Как видим, |
величина |
этой |
ошибки зависит не от |
числа |
разрядов, связанных линейной зависимостью, а только от их наибольших номеров / и g. Это значит, например, что зависимость вида xf is yg оказывает такое же влияние на точность вычисле ний, как и зависимость хс ф ... ф xf -- yd ф . . . ф уг
