Дополнительное задание по курсу «Статистическое моделирование» к лабораторной работе № 1
Дополнительное задание к лабораторной работе №1 состоит в выполнении программно одного из приведенных ниже 10 тестов оценки статистических свойств применяемого ГСЧ. Номер теста выбирается в соответствии с порядковым номером студента (по модулю 10 плюс 1) в списке группы. Результаты работы оформляются отчетными материалами.
Частотный тест в подпоследовательностях (Frequency Test Within a Block)
Цель теста - проверить равномерность появления 0 и 1 в подпоследовательностях.
Пусть ε=ε1ε2..εn - двоичная последовательность длины n. Разобьем ее на непересекающихся М -битных подпоследовательностей. Лишние биты отбрасываем. Определим долю единиц в каждой подпоследовательности:
Вычислим статистику
Полученный результат анализируется при помощи критерия с числом степеней свободы, равным N-1.
Проверка непересекающихся шаблонов (Non-overlapping Template Matching Test)
Цель теста - проверить равномерность распределения 0 и 1 в последовательности на основе анализа частоты встречаемости заранее определенных шаблонов.
|
|
Пусть ε = ε1ε2..ε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.
Тест: ε1=1010010010, ε2=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,
σ2=0.46875
χ2=2.1(3)
Проверка частот
Проверяется равномерность распределения символов в исследуемой последовательности.
Пусть ε= ε1ε2…εn – последовательность m – разрядных чисел длины n. Подсчитываем, сколько раз ν i, i=0..2m-1, встречается каждое число, и вычисляем статистику:
|
|
которая анализируется с помощью критерия χ2 с числом степеней свободы, равным 2m - 1.
Пример 3.10.
Вход: ε=3 5 4 2 1 4 6 1, n=8, m=3.
Тест: ν0=0, ν1=2, ν3=1, ν4=2, ν5=1, ν6=1, ν7=0.
Проверка корреляции
Описание теста приведено на стр. 146 [1].