2.8.5 Правило для решения(на 1% уровне)
Если вычисленное значение P-value < 0.01 , тогда заключаем, что последовательность не случайна. Иначе считаем, что последовательность случайна.
2.8.6 Вывод по результатам теста их интерпретация
С тех пор как P-value, полученное на шаге 4, секции 2.8.4 больше или равно 0,01 {P-value = 0.274932), считаем, что последовательность случайна.
Обратите внимание, что для двухбитового шаблона (В=11), полная
последовательность имеет очень много пробегов по 2 бита, поэтому: 1.) V5 слишком большое; 2.) статистика теста также будет слишком большой: 3.) P-value будет маленьким; 4.) последовательность будет не случайной,
2.8.7 Рекомендации по вводимым размерам
Значения К, М и N должны быть выбраны так, что каждая тестовая последовательность состояла из как минимум 106 бит. Можно выбирать значение т, но в настоящее время, NIST рекомендует m = 9 или m = 10. Если желательны другие значения, выберите их следующим образом:
• n
MN
• N
должно быть выбрано так, чтоб N*(min
i)
> 5
•
• m
должно быть выбрано так, чтоб
• Выберите
К таким образом, чтоб
.
Обратите внимание, что значения TCi должны
быть пересчитаны для значения К отличного
от 5.
2.8.8 Пример
(ввод) 8 двоичное расширение е до 1,000,000 бит
(ввод) п-1000000, В=111111111
(обработка данных) vo=329; Vi=164; V2=150; Уз=111; V4=78; V5=136;
(обработка данных) X^bs) = 8.965859 (вывод) P-value = 0.110434
(результат) Начиная с P-value > 0.01 считаем последовательность случайной
3.8 Тест "Накладывающегося шаблона соответствия" (Overlapping Template Matching)
Этот тест отклоняет последовательности, которые показывают слишком большую или слишком маленькую величину m, но могут быть модифицированы для обнаружения нерегулярных возникновений любого периодического образца В.
Чтобы осуществлять этот тест, параметры М и N должны быть такими, чтобы п = MN, т.е. первоначальная последовательность разделяется на N блоков, каждый длиной М.
Пусть W J• = W J(т,п) будет число (возможно накладывающихся) пробегов длиньи
m в j-ом блоке. Асимптотическое распределение Wj есть ни что иное, как сложное распределение Пуассона:
когда (М - т + 1)2 "' —> Л > 0 (t переменная типа Real).
Соответствующие вероятности могут быть выражены в терминах вырожденных гипергеометрических функций Ф =; F,. Если U обозначает случайную переменную с составленным асимптотическим распределением Пуассона, тогда для и>1сг/=Л/2.
Дополнение к функции распределения этой случайной величины является следующая форма:
Выберите К+1 классов или ячеек для U, т.е. {U=0},{U=1},...,{U=K-1},{U^K}.
Теоретические вероятности 7To,7li,..., 71к+1 этих ячеек находятся по вышеприведенным формулам. Подходящий выбор, это К=5, ?i=2, r|=l.
После того как Ui.. .UN найдены, оцениваем частоты Vo,Vi,... ,Ук Для каждой ячейки, VQ + Vi +...+ VK = N, и вычисляем значение у2'.
Выражение для P-value такое же как секции 3.7. Для очень маленьких P-values последовательность показывает нерегулярные возникновения т.
Ссылки к тесту
1. О. Chrysaphinou and S. Papastavridis, "A Limit Theorem on the Number of Overlapping Appearances of a Pattern in a Sequence of Independent Trials." Probability Theory and Related Fields, Vol. 79 (1988), pp. 129-143.
2. N.J. Johnson, S. Kotz, and A. Kemp, Discrete Distributions. John Wiley, 2nd ed. New York, 1996 (especially pp. 378-379).