Проверка непересекающихся шаблонов (Non-overlapping Template Matching Test)

Дополнительное задание по курсу «Статистическое моделирование» к лабораторной работе № 1

Дополнительное задание к лабораторной работе №1 состоит в выполнении программно одного из приведенных ниже 10 тестов оценки статистических свойств применяемого ГСЧ. Номер теста выбирается в соответствии с порядковым номером студента (по модулю 10 плюс 1) в списке группы. Результаты работы оформляются отчетными материалами.

 

Частотный тест в подпоследовательностях (Frequency Test Within a Block)

Цель теста - проверить равномерность появления 0 и 1 в подпоследовательностях.

Пусть ε=ε₁ε₂..ε_n - двоичная последовательность длины n. Разобьем ее на  непересекающихся М -битных подпоследовательностей. Лишние биты отбрасываем. Определим долю единиц в каждой подпоследовательности:

Вычислим статистику

Полученный результат анализируется при помощи критерия  с числом степеней свободы, равным N-1.

 

Проверка непересекающихся шаблонов (Non-overlapping Template Matching Test)

Цель теста - проверить равномерность распределения 0 и 1 в последовательности на основе анализа частоты встречаемости заранее определенных шаблонов.

Пусть ε = ε₁ε₂..ε_n - двоичная последовательность длины n. Разобьем ее на  непересекающихся M-битных подпоследовательностей.

Лишние биты отбрасываются.

Пусть ν _j - количество появлений шаблона (подпоследовательности определенного типа) в j -й подпоследовательности (j =1.. N). Поиск осуществляется следующим образом. Пусть m – размер шаблона в битах. Начинаем сканировать j -ю подпоследовательность. Если рассматриваемый набор

ε_N(j-1)+k,…, ε_N(j-1)+k+m-1, k =1.. M - m +1

совпадает с шаблоном, то значение ν _j, увеличиваем на 1 и рассматриваем набор

ε_N(j-1)+k+m,…, ε_{N(j-1)+k+2m-1}

в противном случае значение ν _j не изменяем и рассматриваем

ε_N(j-1)+k+1,…, ε_N(j-1)+k+m

Сканирование прекращаем, когда часть элементов набора выходит за пределы рассматриваемой подпоследовательности

Находим

Вычислим статистику

Полученный результат анализируется при помощи критерия  с числом степеней свободы, равным N-1.

Пример 3.5.

Вход:              ε = 1010010010111001011010,

n = 22,

М=10,

m = 3,

шаблон равен 001.

Тест:              ε₁=1010010010, ε₂=1110010110.

 

Позиции битов	ε1=1010010010		ε2=1110010110
	Биты	ν1	Биты	ν2
1-3	101	0	111	0
2-4	010	0	110	0
3-5	100	0	100	0
4-6	001	1(+1)	001	1(+1)
5-7	Пропуск	1	Пропуск	1
6-8	Пропуск	1	Пропуск	1
7-9	001	2(+1)	011	1
8-10	010	2	110	1

Μ=(10-3+1)/8=1,

σ²=0.46875

χ²=2.1(3)

 

Проверка частот

Проверяется равномерность распределения символов в исследуемой последовательности.

Пусть ε= ε₁ε₂…ε_n – последовательность m – разрядных чисел длины n. Подсчитываем, сколько раз ν _i, i=0..2^m-1, встречается каждое число, и вычисляем статистику:

которая анализируется с помощью критерия χ² с числом степеней свободы, равным 2^m - 1.

 

Пример 3.10.

Вход:              ε=3 5 4 2 1 4 6 1, n=8, m=3.

Тест:      ν₀=0, ν₁=2, ν₃=1, ν₄=2, ν₅=1, ν₆=1, ν₇=0.

Проверка корреляции

 

Описание теста приведено на стр. 146 [1].