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

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

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

р < а, то последовательность ё признается неслучайной; в против­ном случае (при р ^ а) последовательность считается случайной.П.1.8. OVERLAPPING T E M P L A T E M A T C H I N G T E S TОбъектом исследования является количество повторений определен­ной фиксированной подпоследовательности (шаблона) в исходной последо­вательности.

Целью теста является выявление генераторов псевдослучай­ных чисел, порождающих последовательности со слишком часто встреча­ющимися апериодическими шаблонами.Для поиска шаблона длины т используется скользящее m-битное ок­но. В отличие от теста Non-overlapping Template Matching Test, рассмот­ренного в разделе П. 1.7, окно всегда сдвигается на одну позицию незави--184симо от того, был обнаружен шаблон или нет.Параметры.1) ё — исследуемая последовательность, ё = Е\, £2, • •; •,'-m£т2) п — длина исследуемой последовательности;3) гп — длина искомого шаблона;4) N — количество подпоследовательностей, на которые разбивается ис­ходная последовательность ё (фиксированное значение N = 968);5) М — длина каждой из подпоследовательностей, на которые разбивает­ся исходная последовательность (фиксированное значением = 1032);6) К — количество степеней свободы (фиксированное значение К = 5) Процедура тестирования.Описание процедуры тестирования приведено для фиксированного к о ­личества степеней свободы К = 5.1) исходная последовательность ё разбивается на N непересекающихсяподпоследовательностей длины М каждая; неиспользованные ч л е н ыв конце последовательности отбрасываются;2) подсчитывается количество Wj вхождений шаблона для каждой и з i vподпоследовательностей (j — порядковый номер подпоследовательно­сти, 1 ^ j ^ N); для поиска шаблона используется m-битное о к н о :если шаблон содержится в окне, значение Wj увеличивается на е д и н и ­цу; после выполнения сравнения осуществляется сдвиг окна на о д н упозицию независимо от обнаружения шаблона;3) все подпоследовательности разбиваются на классы щ, 0 ^ г ^ 5: .

/ - а яподпоследовательность принадлежит классу щ, если Wj = г; к к л а с с уvs также относятся все подпоследовательности с Wj > 5;4) вычисляется значение статистики£(И - мщуг—0где \щ\— число подпоследовательностей в классе щ, а значения в е р ° ~ятностей Кг могут быть получены из табл. 13;-1855) определяется достигаемый уровень значимостир = igamcТаблица 13.Значения вероятностей щтго7Г17^2тгз7Г47Г50,3640910,1856590,1393810,1005710,0704320,139865Рекомендации по выбору параметров.Длина исследуемой последовательности должна составлять не менее610 бит (п ^ 106). Размер шаблона т рекомендуется выбирать равным 9или 10.Интерпретация результатов.Если вычисленное значение достигаемого уровня значимости меньшеа, т.е. р < а, то последовательность ё признается неслучайной; в против­ном случае (при р ^ а) последовательность считается случайной.П.

1.9.MAURER'S UNIVERSAL STATISTICAL T E S TТест был разработан Ули Маурером [57] в начале 1990-х гг.Объектом исследования является количество бит, находящихся меж­ду повторяющимися шаблонами в последовательности. Тест позволяет оце­нить, насколько может быть сжата последовательность без потерь инфор­мации. Последовательности, допускающие значительное сжатие, призна­ются неслучайными.Параметры.1) ё — исследуемая последовательность, ё = Е\, £2, • • •, £п\2) 77, —длина исследуемой последовательности;3) L — длина блока;4) Q — количество блоков в сегменте инициализации (фиксированное зна­чение Q = 10 • 2 L ).Процедура тестирования.1) исходная последовательность ё длины п разбивается на два сегмен--186Сегмент инициализацииL битL битL битQ блоков, Q xL битТестовый сегментL битL битL битК блоков, KxL битп бит•4••Рис.

П . 1 . Разбиение исследуемой двоичной последовательности на сег­менты в универсальном статистическом тесте Маурерата: сегмент инициализации и тестовый сегмент (см. рис. П.1); сегментинициализации состоит из Q, а тестовый сегмент —из К = [|J — Qнепересекающихся блоков (подпоследовательностей) длины L каж­дый; оставшиеся члены в конце последовательности отбрасываются;2) строится массив Т с индексами, соответствующими всем возможнымL-битным шаблонам (всего 2L записей), первоначально заполненныйнулевыми значениями; в массив заносятся номера блоков из сегмен­та инициализации, в которых каждый из шаблонов был обнаружен впоследний раз;3) для всех значений г от Q + 1 до К (т. е. для каждого из К блоковтестового сегмента) выполняются следующие операции:3.1) вычисляется расстояние d между текущим блоком и блоком, вкотором соответствующий шаблон был обнаружен в последнийраз:d = г — Tj,где Tj — элемент массива с индексом, соответствующим текущемушаблону;3.2) логарифм полученного расстояния прибавляется к аккумулято­ру S, первоначально имеющему нулевое значение:S = S + log2 d\3.3) элементу Tj массива Т присваивается номер текущего блока:Tj = i;-1874) рассчитывается значение статистики5) определяется достигаемый уровень значимостир = erfcs — ipлД(Тгде ожидаемое значение ip и среднеквадратичное отклонение а дляразличных вариантов длины блока L могут быть получены из табл.

14.Таблица 14.Ожидаемые значения <р и среднеквадратичные отклонения а дляразличных вариантов длины блока L универсального статистическоготеста МаурераL67891011Ч>5,21770526,19625077,18366568,17642489,172324310,170032аLЧ>о2,9543,1253,2383,3113,3563,384121314151611,16876512,16807013,16769314,16748815,1673793,4013,4103,4163,4193,421Рекоме]ядации по выбору параметров.Длина исследуемой последовательности должна составлять не менее387840 бит (тт. ^ 387840). Значение длины блока L определяется в зависи­мости от длины последовательности п по табл. 15.Интерпретация результатов.Если вычисленное значение достигаемого уровня значимости меньшеа, т.

е. р < а, то последовательность ё признается неслучайной; в против­ном случае (при р ^ а) последовательность считается случайной.Большие различия между наблюдаемым значением s и ожидаемым крсвидетельствуют о возможности существенного сжатия последовательно­сти.-188Таблица 15.Длина блока L универсального статистического теста Маурера дляразличных вариантов длины последовательности пп> 387840^ 904960^ 2 068480^4654080^10 342400> 22 753 280П.1.10.LпL67891011> 49 643 520^ 107560 960^ 231669 760^496435 200^ 1059 0617601213141516LINEAR C O M P L E X I T Y T E S TОбъектом исследования является линейная сложность последователь­ности, т.е.

наименьшая длина регистра сдвига с линейными обратнымисвязями, порождающего последовательность. Тест позволяет определить,соответствует ли линейная сложность ожидаемому для случайных последо­вательностей значению. Последовательности, обладающие слишком низкойлинейной сложностью, признаются неслучайными.Параметры.1) ё — исследуемая последовательность, ё = е\, £2, • • • > £п]2) п —длина исследуемой последовательности;3) М — длина подпоследовательности;4) К — количество степеней свободы (фиксированное значение К — 6).Процедура тестирования.1) исходная последовательность ё разбивается на N непересекающихсяподпоследовательностей длины М каждая; неиспользованные членыв конце последовательности отбрасываются;2) по алгоритму Берлекэмпа-Мэсси определяется линейная сложность £jдля каждой из N подпоследовательностей (1 ^ г ^ JV);3) рассчитывается математическое ожидание \х линейной сложности по­следовательности длины М:М9 + (-l) M + 136мf +fм2-189г4) для каждой подпоследовательности вычисляется величина Т{ ( 1 ~~- ""N):мTi = (-1)• (А - М) +|5) все подпоследовательности разбиваются на классы Vj (0 ^ j— >зависимости от значения Ti (см.

табл. 16);6) вычисляется значение статистики s:6=Е_s(Wi\-Nm) 2^г=0N**где | ^ | — количество подпоследовательностей в классе щ, а з й 0 , 4 6 1 1вероятностей 7г^ находятся по табл. 17;7) рассчитывается достигаемый уровень значимостиP= igamc(||).Табл»^**1Разбиение подпоследовательностей на классыгрКлассTiTi ^ - 2 , 5-2,5 < Ti < - 1 , 5-1,5 < If < - 0 , 5-0,5 <Ti^ 0,516"^СлассUA0,5 < % < 1,51,5 < Т{^ 2,52,5 < Т{^U6"3Табли:^^аl 7'Значения вероятностей щ7Го0,0104177Гх0,0312507Г20,1250007Гз7Г47Г5-Z?*J>_0,5000000,2500000,062500O.O^g0833Рекомендации по выбору параметров.тт.._- менееДлина исследуемой последовательности п должна составлять н е г ^610 бит (п ^ 106). Длина подпоследовательности должна выбираться:^-190образом, чтобы выполнялись соотношения 500 ^ М ^ 5 000 и N = [^J^200.Интерпретация результатов.Если вычисленное значение достигаемого уровня значимости меньшеа, т.е.

р < а, то последовательность ё признается неслучайной; в против­ном случае (при р ^ а) последовательность считается случайной.П.1.11. SERIAL T E S TОбъектом исследования является количество вхождений всех возмож­ных га-битных пересекающихся шаблонов в последовательность. Тест поз­воляет определить, соответствует ли наблюдаемое число вхождений каж­дого из 2т шаблонов ожидаемому. Для случайных последовательностейожидается, что все шаблоны являются равновероятными, т. е. встречаютсяс равной частотой.Как и в тесте Overlapping Template Matching Test, для поиска вхож­дений шаблонов в последовательность используется скользящее окно, накаждом шаге сдвигающееся на одну позицию.Параметры.1) ё — исследуемая последовательность, ё = ei, £2, • • •, £п',2) п —длина исследуемой последовательности;3) т — длина шаблона.Процедура тестирования.1) формируется расширенная последовательность ё' путем приписыва­ния справа (конкатенации) к последовательности ё ее первых т — 1членов;2) подсчитывается количество вхождений в расширенную последователь­ность ё' всех возможных шаблонов длины т, т—1 и га—2; для обозна­чения числа вхождений шаблона длины к далее будем использоватьзапись их, где х € В^ — двоичный набор из к элементов, соответству­ющий шаблону;-1913) вычисляются суммык,22 тV-п/\2т2V-жбВтm_1л„22п.,22т"22ж€Вт22т~1^2\2 =' 2™~2^2v^/w \V-/П<-* = — £ О*-2^=0а?еВ т _ 2— Е ^-»;ж€Ит_24) рассчитываются значения статистик5) для каждой из статистик определяются величины достигаемого уров­ня значимости:P l= igamc ( 2 - 2 , | ) ,р 2 = igamc ( 2 - 3 , | ) .Рекомендации по выбору параметров.Длина исследуемой последовательности п и размер шаблона т долж­ны выбираться таким образом, чтобы выполнялось соотношение т<|_log2 п\ - 2.Интерпретация результатов.Если хотя бы одно значение достигаемого уровня значимости меньшеа, т.

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

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