Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей (1025663), страница 29

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 29)

е. pi < а или р 2 < <2, то последовательность ё признается неслучайной;в противном случае последовательность считается случайной.П. 1.12.APPROXIMATE E N T R O P Y T E S TОбъектом исследования является число вхождений всех возможныхm-битных пересекающихся шаблонов в последовательность. Целью тестаявляется сравнение разницы количества вхождений шаблонов длины т ит + 1 с ожидаемым для случайных последовательностей значением.Параметры.1) ё— исследуемая последовательность, ё — £\, £2, • • •, £п\-1922) n —длина исследуемой последовательности;3) т — длина шаблона.Процедура тестирования.1) для значений к=тик=т+1выполняются следующие шаги:1.1) формируется расширенная последовательность ё' путем приписы­вания справа (конкатенации) к последовательности ё ее первыхк — 1 членов;1.2) подсчитывается количество вхождений в расширенную последо­вательность ё' всех возможных шаблонов длины к; для обозначе­ния числа вхождений шаблона длины к далее будем использоватьзапись их, где х £ В& — двоичный набор из к элементов, соответ­ствующий шаблону;1.3) для всех возможных шаблонов вычисляются значения частот1Схх_)П—1.4) вычисляется величинаРКПЛ*)' =_ 5^cxbgCx]хеВ22) рассчитывается значение статистики3) определяется достигаемый уровень значимостиp = iganic(2rn-1,|).Рекомендации^по выбору параметров.Длина последовательности п и размер шаблона т должны выбиратьсятаким образом, чтобы выполнялось соотношение 777- < [log2 п\ — 5.Интерпретация результатов.Если вычисленное значение достигаемого уровня значимости меньшеа, т.е.

р < а, то последовательность ё признается неслучайной; в против­ном случае (при р ^ а) последовательность считается случайной.-193П.1.13. CUMULATIVE SUMS ( C U S U M ) T E S TОбъектом исследования являются максимальные отклонения от нуле­вого значения частичных сумм преобразованных членов последовательно­сти, полученных из исходных членов путем замены 0 ь-> — 1, 1 ь-> 1. Целью •теста является выявление последовательностей, в которых частичные сум­мы отклоняются от нулевого значения значительно сильнее, чем ожидаетсядля случайной последовательности.Параметры.1) ё — исследуемая последовательность, ё — £i, £2, • • •, £п\ .2) п — длина исследуемой последовательности.Процедура тестирования.Процедура тестирования выполняется дважды.

Первый раз проход попоследовательности осуществляется от ее начала к концу, а второй — в об­ратном направлении. Как следствие, в результате теста формируются двазначения достигаемого уровня значимости.1) по исходной последовательности ё = е\, €2, • • •, £п строится последова­тельность X — Xi, Х2, • • •, Хп, гдеXi — 2£i — 1,1 ^ г < п,т.е.

осуществляется замена членов последовательности0 н - > - 1 и Ы+1;2) вычисляются значения частичных суммкSk — 2_^ Xii=lдля всех значений к в интервале от 1 до п включительно (при проходепо последовательности в обратном направлении в приведенном вышевыражении необходимо для членов Xi произвести замену индексов г н->п — г + 1);3) рассчитывается значение статистикиs =вв-1^-1;-1944) вычисляется достигаемый уровень значимости(т-1)/4Ф'{4k + l)zпft=(=a+l)/4(?-1)/4+ЕФФп\4k + ?>)z-Фпft=(^-3)/4(4/с-1)^+'(±k + l)zпгде Ф (z) — кумулятивная функция нормального распределения с па­раметрами \i = 0 и <у = 1:Ф(*)2тге-" 2 / 2 &*.—ооРекомендации по выбору параметров.Рекомендуется использовать последовательности ё длиной не менее100 бит (n ^ 100).Интерпретация результатов.Если вычисленное в результате одного их проходов значение достига­емого уровня значимости меньше а, т.е. р < а, то последовательность ёпризнается неслучайной; в противном случае (если веер превосходят илиравны а) последовательность считается случайной.П.1.14.

RANDOM EXCURSIONS T E S TВ данном тесте последовательность частичных сумм рассматриваетсякак маршрут случайных блужданий по неориентированному графу. Значе­ние частичной суммы рассматривается в качестве номера вершины графа.Объектом исследования является количество циклов, содержащих опреде­ленные вершины ровно К раз (под циклом в тесте понимается последова­тельность вершин маршрута, первый и последний элементы которой равнынулю, а все остальные являются ненулевыми). Целью теста является вы­явление последовательностей, в которых количество вхождений вершин вциклы значительно отличается от ожидаемого для случайной последова­тельности значения.-195В результате теста вычисляется восемь значений достигаемого уровнязначимости.Параметры.1) £ — исследуемая последовательность, ё = ei, £2, • • •> £п\2) п — длина исследуемой последовательности.Процедура тестирования.1) формируется последовательность X — Х\, Х 2 , .

. . , Хп, гдеХг = 2в{ — 1,1 ^ г ^ п,т.е. осуществляется замена членов последовательности0 ь-> — 1 и 1 н->+1;2) вычисляются значения частичных сумм/сг=1для всех значений А; в интервале от 1 до п включительно;3) строится новая числовая последовательность 5" = 0, Si, S2, • • •, Sn, 0;4) подсчитывается количество J нулевых элементов, за исключением пер­вого, в последовательности S"; отметим, что если рассматривать пол• ный неориентированный граф, вершины которого пронумерованы чис­лами 0, 1, ..., то число J также является количеством циклов в марш­руте, задаваемом последовательностью S" номеров вершин графа;5) для каждого цикла и каждого номера х вершины графа, удовлетво­ряющего условию —4 ^ х ^ — 1 или 1 ^ х ^ 4, подсчитывается числовхождений вершины с номером х в цикл;6) для каждого из восьми указанных выше значений х определяется ве­личина Uk(х) — количество циклов, в которые вершина с номером хвходит ровно к раз для 0 < fc ^ 4 и 5 или более раз —для к — 5;ихотметим, что Y2k=o к{ ) — J\7) для каждого из восьми указанных выше значений х рассчитывается-196значение статистики$х£(Ук(х) - J7Tk(x)YJlTk(x)KV;fc=0где вероятности ттк(х) могут быть получены из табл.

18;8) вычисляются значения достигаемых уровней значимости для каждогономера вершины х:p x = igamcf-, Л ,хе[-4;-1] U [1;4].Таблица 1 8 .Значения вероятностей 7г&(я;)х =1х =2х =3ж= 4а; = 5а; = 6х =7щ(х)7Ti(x)0,50000,75000,83330,87500,90000,91670,92860,25000,06250,02780,01560,01000,00690,0051К2(х)тгз(^)7Г 4 (ж)7Г5(»0,12500,04690,02310,01370,00900,00640,00470,06250,03520,01930,01200,00810,00580,00440,03120,02640,01610,01050,00730,00530,00410,03120,07910,08040,07330,06560,05880,0531РекомендацИИ по вы[бору параметров.Рекомендуется использовать последовательности ё длиной не менее610 бит (п ^ 10 6 ).Интерпретация результатов.Если хотя бы одно из вычисленных значений достигаемого уровня з н а ­чимости меньше а, то последовательность ё признается неслучайной; впротивном случае (если рх ^ а для всех х £ [—4; —1] U [1;4]) последова­тельность считается случайной.-197П.1.15.

RANDOM EXCURSIONS VARIANT T E S TКак и в рассмотренном выше тесте Overlapping Template MatchingTest, последовательность частичных сумм рассматривается как маршрутслучайных блужданий по неориентированному графу, заданный номерамивершин. Объектом исследования является количество проходов маршрутачерез различные вершины.В результате теста формируется 18р-значений, соответствующих раз­личным вершинам.Параметры.1) ё — исследуемая последовательность, ё = е\, Е2-, • • • > £п\2) п — длина исследуемой последовательности.Процедура тестирования.1) формируется последовательность X — Xi, Х 2 , .

. . , Хп, гдеXi = 2£i — 1,1 ^ I ^ П,т.е. осуществляется замена членов последовательности0 »->• — 1 и 1 (-»•+1;2) вычисляются значения частичных суммкг=1для всех значений к в интервале от 1 до п включительно;3) строится новая числовая последовательность S' = 0, <5i, 62, • • • > Sn, 0;4) подсчитывается количество J нулевых элементов, за исключением пер­вого, в последовательности S'; отметим, что если рассматривать пол­ный неориентированный граф, вершины которого пронумерованы чис­лами 0, 1, ..., то число J также является количеством циклов в марш­руте, задаваемом последовательностью S' номеров вершин графа;5) для каждого номера вершины х, удовлетворяющего условию — 9 ^ х ^— 1 или 1 ^ х ^ 9, определяется значение статистики sx — количествовхождений вершины с номером х в маршрут, задаваемый последова­тельностью 5";-1986) вычисляются значения достигаемых уровней значимости:рх = erfc [Sx.\J~ *=) ,хе[-9; -1] U [1; 9].Рекомендации по выбору параметров.Рекомендуется использовать последовательности ё длиной не менее6610 бит ( п ^ 10 ).Интерпретация результатов.Если хотя бы одно из вычисленных значений достигаемого уровня зна­чимости меньше а, то последовательность ё признается неслучайной; впротивном случае (если рх ^ а для всех х £ [—9; —1] U [1;9]) последова­тельность считается случайной.П.2.КРАТКОЕОПИСАНИЕАВТОМАТИЗАЦИИПРОГРАММНОГОКОМПЛЕКСАСТАТИСТИЧЕСКОГОТЕСТИРОВА­НИЯВ рамках диссертационной работы был разработан программный ком­плекс, предназначенный для автоматизации процедур статистического те­стирования генераторов псевдослучайных последовательностей на основеклеточных автоматов и поиска параметров генераторов, при которых ихвыходные последовательности обладают хорошими статистическими свой­ствами (далее — программный комплекс).Программный комплекс реализован в виде набора консольных прило­жений, функционирующих в операционных системах семейства MicrosoftWindows (версии ХР или выше) под управлением среды Microsoft .NETFramework 4.0.

Характеристики

Список файлов диссертации