|
= м |
|
2 |
h i |
|
|
|
|
пЪ |
|
|
|
= -Ь 2 |
2 |
м {1 х ‘ -■м (х)] [х>- |
м (х)]}= - к 2 |
2 Кх {i ~ f)- |
i= 1 |
h |
i |
|
|
h i |
/=. 1 |
Произведем замену переменной т = t — / и, разбив внутрен нюю сумму на две части, поменяем порядок суммирования
п |
i-n |
Г я £-1 |
га |
-1 |
в | м * ( х ) 1 = ^ 2 2 |
х ' ( т ) = ^ |
2 2 ' М т ) + 2 |
2 х * (т) |
£=1 т«£-1 |
U £-i т=о |
£=1 х=1-п |
«2 |
' п -1 п |
|
-1 П+Т |
|
|
2 2 Kh )+ 2 2х-(т) |
|
_ |
1_ |
|
|
|
|
|
|
|
. т=0г=т+1 |
|
т=1-гг i= l |
|
|
1 |
|
|
|
-1 |
|
|
^ ( п — х )К х {%) + |
2 ("- |
- х) К х (т) |
|
П2 |
|
|
-т«о |
|
т=1-/г |
|
|
П-1 |
|
|
|
+42 (i■- i ) |
к, и. |
«2 2 (*—I^I) к„(т)=^ |
|
|
|
|
Т=1 |
|
Если расчет ГСДП выполнен правильно, то оставшаяся сумма |
конечна и дисперсия оценки М * (х) |
стремится к нулю при п оо. |
Следовательно, М * |
(х) является состоятельной оценкой и требуе |
мая точность измерения может быть обеспечена достаточно боль шим объемом выборки п .
Используя полученную ранее верхнюю оценку автокорреля ционной функции (6.9), можно определить минимально необхо димую величину п при заданной точности измерения
D [М* (х)|< Л | ).+ X 2 (1 - X ) |
= |
|
|
Т=1 |
|
|
|
|
Г |
п~ 1 |
|
__ D ( я ) . |
/кв |
1 — га |
. ^ |
1 |
га |
л2 А/га |
га |
т=х |
т |
|
|
L |
|
При достаточно большом п
2 т ~ 1п (п _ 1 )’
т=1
а наибольшая возможная величина дисперсии двоичной последо вательности составляет 1Ji .
Таким образом
~ — 1 + 1п(и — 1)
0 [ M * ( x ) ] < ^ - + 4 f |
я2га |
Для реально приемлемых значений /КВ/А/ и п второе слагаемое в правой части неравенства пренебрежимо мало по сравнению с первым. В то же время для достаточно большого п закон распре деления М * (х) близок к нормальному. Поэтому с вероятностью, близкой к единице,
|
ДМ* (х) = |М * (х) - М (х) |< 3 У D [М* (х)\ |
. |
Отсюда |
|
|
|
|
2 |
(6. 12) |
|
min — [ДМ * ( х ) ] 1 оа ’ |
где |
nmin — минимально |
необходимый |
объем выборки; |
[ДМ* (я)]доп — допустимая |
ошибка определения М (х). |
Для измерения автокорреляционной функции можно восполь зоваться оценкой
|
П |
М * (XiXi+T) = |
-J- 2 Xtxux. |
|
i*1 |
Эта оценка также является |
несмещенной и состоятельной |
[3]. Однако определить ее точность до эксперимента трудно, поскольку для этого необходимо знать смешанные моменты иссле дуемой последовательности до четвертого порядка включительно. Выход может быть найден в А;-кратном измерении оценки с по следующим анализом полученных результатов.
Считая выборочное среднее М * +г) при больших п рас пределенным по закону, близкому к нормальному, введем обо значение
[М * (*£Ж4+Т) — М (ххх) ] ] / Т
V |
r_ |
= |
tk -L - |
D * (x{xi+z) |
|
Здесь: |
|
ft |
|
|
|
|
М * {xiXUr) |
= х 2 |
М ‘* (XiXi+T')' |
|
|
/=1 |
|
|
k |
|
|
D* (х м fT) |
2 |
(xi*i+x) —M * (XiXixx)\2. |
|
i=i |
|
Как известно, величина tk_ L подчиняется i-распределению Стьюдента с к — 1 степенями свободы, таблицы которого имеются в справочниках и книгах по математической статистике (например [3]). Тогда можно утверждать, что действительное значение М (ххх) с доверительной вероятностью (1 — а) находится внутри
интервала
М * (XiXi+x) ■ i/ s*
|
V k |
|
< |
V D * ( x ix i+ x) th - l , a /2 |
M * (а д +т) + - |
|
|
V T |
|
где tk-i, a/2 — значение случайной величины |
tk_ r, для которого |
выполняется соотношение Р (tk_ г > tk_ 1: ац ) |
— а /2. С увеличе |
нием к доверительный интервал может быть уменьшен до любой
наперед заданной величины. |
точные значения |
Полученные таким образом практически |
М (х) ж М (ххх) дают возможность рассчитать |
автокорреляцион |
ную функцию по известной формуле |
|
К х (т) = М (ххх) - М 2(х). |
|
Все сделанные выводы остаются справедливыми и для взаимнокор реляционной функции с заменой переменной xi+x на у/ + т, т. е.:
П
|
м * (г0 = |
т |
2 |
у<> |
|
|
|
|
|
i=l |
|
|
|
|
|
|
п |
|
|
|
м * { х ш и х) = 4 * 2 |
х ‘ т + х ’ |
|
|
|
и |
i=i |
|
|
|
|
|
|
|
|
М * { X jlji :-т) = |
4 |
2 |
М |
1* ^ |
£+Т) ’ |
|
|
h |
/=1 |
|
|
|
|
|
|
|
|
D * { X i V u x ) = х = Т 2 |
[ М * |
|
|
( Ъ У и т ) ) 2, |
|
/=1 |
|
|
|
|
м * |
Vi>*(xiyi+Z) |
<h_1<a/2 |
C M (xyx) < |
(Xii/i+x) |
|
Vk |
|
|
|
|
|
|
|
|
< |
M * (Xiy{+x) |
V D* {xi}!i+x) |
a/2 |
|
|
|
vT |
J ! |
|
|
|
|
|
K X Vy) = Л/ (zy-r) —M {x)M (y).
Рассмотренные здесь оценки статистических характеристик случайных двоичных последовательностей не являются единствен но возможными, однако техническая реализация алгоритмов их вычисления наиболее проста.
Одна из возможных схем коррелятора, определяющего М * (ж), М * (Х[Хц.х) и М * (£,у(+х), приведена на рис. 114, а. Она состоит
из двух счетчиков Сч1 и Сч2, сдвигающего регистра Р г, конъюнктора & и триггера Т. Для вычисления М * (х) переключатель П устанавливается в положение 2. По сигналу «пуск» производится установка в 0 обоих счетчиков, а триггер Т устанавливается в со стояние 1, открывая входной последовательности {ж} доступ к счетчику Сч1. На вход второго счетчика Сч2 поступают синхро низирующие импульсы, следующие с тактовой частотой исследуе-
а)
X
Рис. 114. Схемы цифровых корреляторов
мой последовательности. При переполнении Сч2 триггер Т уста навливается в 0 и цикл вычислений заканчивается. Таким обра зом, емкость Сч2 определяет объем выборки, сумма которой оказы вается накопленной в Сч1. Если емкости обоих счетчиков оди наковы, то деление на п осуществляется размещением запятой в двоичном коде суммы перед старшим разрядом счетчика Сч1. Для достижения заданной точности измерений разрядность счет чиков в соответствии с формулой (6.12) выбирается равной1
1 ^ l0ga [ДМ*(*Щ0П ’
где I — наименьшее целое число, удовлетворяющее этому нера венству.
Для измерения взаимнокорреляционной функции переключа тель П устанавливается в положение 1, а конъюнктор не только
236
выполняет функцию вентиля, но и осуществляет стохастическое умножение последовательностей {х} и {у}, причем последняя оказывается задержанной на интервал т, определяемый длиной
сдвигающего регистра Рг. Изменяя |
разрядность этого регистра, |
можно вычислить величину оценки |
М * (хгуг+х) для различных |
значений аргумента т. |
|
Эта же схема вычисляет оценку М * (хг-х,-+т), если на оба входа х и у поступает одна и та же последовательность {х}.
Вторая схема коррелятора, показанная на рис. 114, б, отли чается от первой решением узла задержки, предложенным В. А. Прянишниковым [59]. Здесь ждущий мультивибратор МВ1 играет роль динамической памяти, осуществляющей задержку информации на время, примерно равное половине периода такто вой частоты входных последовательностей.
Счетчик СчЗ работает в режиме деления этой частоты на коэф фициент, равный т. В момент переполнения счетчика СчЗ триггер Т1 устанавливается в 0, а записанная в нем информация с помощью мультивибратора М В2 передается на входконъюнктора &. Состоя ние входа у, соответствующее этому моменту, спустя полтакта записывается в триггер Т1, где и остается до прихода следующего импульса переполнения СчЗ. Таким образом, осуществляется задержка последовательности {у} на время т.
Эта схема требует для построения узла задержки меньшего числа элементов памяти, чем предыдущая. Однако, поскольку на счетчик Сч1 поступают выборки из входных последовательно стей с интервалом т, время вычисления оценки при том же объеме выборки п возрастает в т раз.
Более подробные сведения о цифровых корреляторах и спо собах оценки статистических характеристик случайных процессов можно найти в специальной литературе [3, 22, 49].
Г л а в а VII
ГЕНЕРАТОРЫ ПСЕВДОСЛУЧАЙНЫХ ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
37. Основные способы получения псевдослучайных чисел в СтВМ
Создание высококачественных, быстродействующих идостаточно простых генераторов случайных чисел является одной из основ ных проблем, возникающих при реализации принципов стохасти ческих вычислений. От решения этой проблемы в конечном счете зависит успех построения всей СтВМ, так как характеристики ГСЧ во многом определяют параметры СтВМ: сложность, точность и скорость производимых вычислений, а также сложность всего устройства.
Современное состояние развития физических ГСЧ, в которых получение случайных чисел основано на использовании каких-либо физических явлений, например, излучения радиоактивных эле ментов, шумов электронных ламп и полупроводниковых приборов, свидетельствует о существовании серьезных трудностей в этой области. Стремление улучшить качество случайных чисел (опре деляемое степенью соответствия между теоретическим и эмпири ческим распределениями) и быстродействие (максимальную ско рость выборки случайных чисел) приводит к значительному ус ложнению аппаратуры. Кроме того, для генераторов этого класса характерна неустойчивость статистических характеристик во вре мени, обусловленная нестабильностью характеристик источников шума и параметров преобразующих схем, колебаниями напряже ния источников питания и т. д. В связи с этим приходится исполь зовать специальные схемы регулировки статистических характе ристик генерируемой последовательности случайных чисел. Вы текающая отсюда необходимость периодической проверки харак теристик генератора по статистическим тестам, а также сложность устройства затрудняют эксплуатацию и препятствуют широкому внедрению ГСЧ.
Вследствие указанных недостатков ГСЧ более широкое при менение находят математические методы получения последователь ностей псевдослучайных чисел. Псевдослучайными числа называ ются потому, что, имея не случайную природу генерирования, последовательности этих чисел отвечают всем основным свой ствам, присущим последовательностям действительно случайных чисел.
