- •2.1 Частотный тест (на монотонность бит)
- •2.1.1 Назначение теста
- •2.1.2 Исходные данные
- •2.1.3 Тестовая статистика и исходное распределение
- •2.2 Частотный тест в пределах блока
- •2.2.3 Тестовая статистика
- •2.2.7 Рекомендуемый размер входной последовательности
- •2.2.8 Пример
- •3.2 Техническое описание
- •2.3 Тест Прогонов (Runs).
- •2.3.1 Цель теста.
- •2.3.2 Вызов функции.
- •2.3.3 Статистика теста и описание ссылок.
- •2.3.4 Описание теста.
- •2.3.5 Правила решения (на уровне 1%)
- •2.3.6 Вывод и интерпритация результатов теста.
- •2.3.7 Вводные рекомендации размера
- •3.3 Тест прогонов
- •2.4 Тест на самую длинную последовательность единиц в блоке
- •2.4.1 Цели теста
- •2.4.2 Вызов функции
- •2.4.3 Статистика теста и начальное распределение
- •2.4.4 Описание теста
- •2.4.6 Заключение и интерпретация результатов теста
- •2.4.8 Пример
- •3.4 Тест на самую длинную последовательность единиц в блоке
- •2.5 Тест ранга бинарной матрицы
- •2.5.Цели теста
- •2.5.2 Вызов функции Rank(n), где:
- •2.5.4 Описание теста
- •2.5.6 Заключения и интерпретация результатов теста
- •2.5.7 Рекомендации по размерам вводимых последовательностей
- •3.5 Тест ранга бинарной матрицы
- •2.7. Испытание на не перекрывание сравнений с шаблонами
- •2.7.7. Цели испытаний.
- •2.7.2. Функции запроса. NonOverlappmgTemplateMatching (м, п)
- •2 7.3. Статистическая проверка и ссылка на распределение.
- •2.7.4. Описание теста.
- •2.7.5. Правила (на уровне 1 %).
- •2.7.6. Заключения и Интерпретация Испытательных Результатов.
- •2.7.8. Пример.
- •3.7. Испытание на не перекрывание сравнений с шаблонами.
- •2.8 Тест "Накладывающегося шаблона соответствия" (Overlapping Template Matching)
- •2.8.2 Вызов функции
- •2.8.3 Статистика теста и рекомендуемое распределение
- •2.8.4 Описание теста
- •2.8.5 Правило для решения(на 1% уровне)
- •2.8.6 Вывод по результатам теста их интерпретация
- •2.9 "Универсальное Статистическое" Тест Mауpepa
- •2.9.1 Цель теста
- •2.9.2 Запрос Функции
- •2.9.3 Проверить Статистический и Сослаться на Распределение
- •2.9.4 Описание теста
- •2.9.5 Правило Решения (на 1%-ом Уровне)
- •2.9.6 Заключение и интерпретация результатов теста
- •2.9.7 Рекомендация входных размеров
- •3.9 "Универсальный статистический" тест Моурера
- •1. Цели теста
- •2. Вызов функции
- •3. Статистика теста и ссылочное распределение
- •4. Описание теста
- •5. Правило 1%
- •6. Интерпретация результатов теста
- •7. Рекомендации входного размера
- •1. Цел и теста
- •2. Вызов функции
- •3. Тестовая статистика
- •4. Описание теста
- •5. Правила решения
- •6. Заключения и интерпретация результатов тестирования
- •7. Рекомендации размера на входе
- •2.11 Тест линейной сложности
- •2.11.3 Статистика Теста и Распределение
- •2.11.4 Описание Теста
- •2.11.6 Вывод и Интерпретация Результатов Теста
- •2.11.7 Рекомендации По Входным Величинам
- •2.11.8 Пример
- •3.11 Тест линейной сложности
- •2.12 Серийный тест
- •2.12.1 Назначение теста
- •2.12.2 Вызов функций
- •2.12.3 Статистика теста и контрольное распределение
- •2.12.4 Описание теста
- •2.12.5 Решающее правило (при 1% уровне допуска)
- •2.12.6 Вывод и интерпретация результатов теста
- •2.12.7 Рекомендации по входным размерам
- •3.12 Серийный тест
- •2.13 Тест аппроксимация энтропии
- •2.13.1 Цель теста
- •2.13.2 Вызов функции
- •2.13.3 Тестирование статистического и эталонного распределения.
- •2.13.4 Описание теста.
- •2.14 Совокупные cyммы (Cusum) тест.
- •2.14.1 Цель теста
- •2.14.2 Вызов функции
- •2.14.3 Статистический тест и относительное распределение
- •2.14.4 Описание теста
- •2.14.5 Правила принятия решений (at the I % Level)
- •2.14.6 Вывод и интерпретация пункта 2.14.5
- •2.14.7 Рекомендации по размеру входной последовательности
- •2.14.8 Пример
- •3.14 Коммулятивные суммы (Cusum) тест
- •2.15 Тест произвольные отклонения.
- •2.15.1 Цель теста
- •2.15.2 Вызов функции
- •2.15.3 Статический тест и распределение ссылок
- •2.15.4 Описание теста
- •Ссылки для теста
- •2.16 Испытание варианта случайных отклонений
- •2.16.1 Цель испытания
- •2.16.3 Статистика испытаний и контрольное распределение
- •2.16.4 Описание
- •3.16 Испытание варианта случайных отклонений
2.15 Тест произвольные отклонения.
2.15.1 Цель теста
f Идея этого теста в том, что количество циклов, имеющих точно К входов на
совокупной сумме произвольной последовательности. Совокупная сумма произвольной последовательности, производное от частичных сумм после того, как на интервале (0,1) последовательность будет попадать в пределы (-!,+!). Цикл произвольной последовательности состоит из последовательности отрезков длин устройства принятого произвольно, что начинается и возвращается в начало. Цель этого теста в том, чтобы определить, что количество попаданий в конкретное состояние в пределах цикла отклоняется из которого одно попадание должно ожидаться для произвольной последовательности. Этот тест -действительно серия восьми тестов (и выводов), один тест и вывод для каждых состояний: -4, -3, -2, -1 и +1, +2, +3, +4.
2.15.2 Вызов функции
RandomExcursions(w), где:
n - это длина строки битов.
- последовательность битов сгенерированных функцией RNG или PRNG; это
существует как глобальная структура на момент функционального вызова;
2.15.3 Статический тест и распределение ссылок
x2(obs): Для данного состояния х, мера того как хорошо наблюдаемый номер состояния находиться в пределах цикла ожидаемое количество раз, исходя из предположения произвольности.
Распределение ссылки для статистического теста - это распределение x2.
2.15.4 Описание теста
(1) Форма нормализованной последовательности для интервала (-1,+1) и X: нули и та входная последовательность (е) измененные в интервале от -1 до +1; X; = 2е; -1.
Например, если £=0110110101, тогда n - 10 и Х = -1, 1, 1,-1, 1, 1,-1, 1,-1, 1.
(2) Вычислите частичные суммы S, последовательно больших подпоследовательностей, каждая начинающаяся с X,.
Сформировать набор S = {Si}.
S1 =Х1
S2 =X1+X2
Для примера в этой секции,
(3) Сформировать новую последовательность 5" включая нули перед и после набора S. То есть, S'= 0,S1, S2, ... ,Sn,0.
Для примера в этой секции, S' = 0, -1, 0, I, 0, 1, 2, I, 2, I, 2, 0. Результирующий произвольный проход, показан ниже.
Пример произвольного прохода (S )
(4) J - это общее число нулевых пересечений в S', где нулевое пересечение является величиной нуля в S', что происходит после стартового нуля. J - также количество циклов в S , где цикл S' -подпоследовательность S, состоящая из случайных нулей, сопровождаемая нулевыми величинами, и заканчиваясь нулем. Заканчивающий нуль в одном цикле может быть начальным нулем в другом цикле. Количество циклов в S' - количество нулевых пересечений. Если J < 500, прекратите тест.
Для примера в этой секции, если S'= {0,-1,0 1,0, 1,2, 1,2, 1, 2, 0}, то J= 3 (есть нули в позициях 3, 5 и 12 для S'). Нулевые значения легко пронаблюдать на вышеуказанном графике. Для J = 3, есть 3 цикла, состоящих из {0,-1,0}, {0, 1,0} и {0, 1,2,1,2,1,2,0}.
(5) Для каждого цикла и для каждой не равной нулю величины х может иметь величины -4 <х < -1 и 1 <х < 4, вычислять частоту каждого х в пределах каждого цикла.
Для примера в этой секции, на этапе 3, первый цикл имеет один случай для -1, второй цикл имеет один случай для 1, и третий цикл имеет три случая каждый из 1 и 2. Это может быть представлено используя следующую таблицу.
|
|
Циклы
|
|
Значение X
|
Цикл 1 (0,-1,0)
|
Цикл 2 (0,1,0)
|
Цикл З (0,1,2,1,2,1,2,0)
|
-4
|
0
|
0
|
0
|
-3
|
0
|
0
|
0
|
-2
|
0
|
0
|
0
|
-1
|
1
|
0
|
0
|
1
|
0
|
1
|
3
|
2
|
0
|
0
|
3
|
3
|
0
|
0
|
0
|
4
|
0
|
0
|
0 |
(6) Для каждых восьми состояний х, вычислите Vk(x) - общее число циклов в которых состояние х происходит точно k время среди всех циклов, для k = 0, 1,...,5
5 (для k = 5), все частоты > 5 сохранены в V5 (х)). Отметьте, что (х) = J.
Для примера в этой секции,
V0 (-l) = 2 (состояние -1 происходит точно 0 времени в двух циклах),
Vi(-l) = 1 (состояние -1 происходит только один раз в одном цикле), и
V2(-l) = Vз(-1) = V4(-l) = Vs5(-l) = 0 (состояние -1 происходит точно {2, 3,4, >5} времени в 0 циклах).
• Vо (1) = 1 (состояние 1 происходит точно О времени в одном цикле),
V1 (1) = 1 (состояние 1 происходит только один раз в одном цикле),
V3 (1) = 1 (состояние 1 происходит 3-й раза в одном цикле ), и
V2(l) = V4(1) =V5 (1) = 0 (состояние 1 происходит точно {2, 4, >5} времени в 0 циклах).
• Vo(2) = 2 (состояние 2 происходит точно 0 времени в 2-х циклах),
V1 (2) = 1 (состояние 2 происходит 3-й раза в одном цикле), и
V1 (2) = V2(2) = V4(2) = V5(2) = 0 (состояние 1 происходит точно
{1,2, 4, >5} времени в 0 циклах).
• Vo(-4) = 3 (состояние -4 происходит точно 0 времени в 3-х циклах), и
V1(-4) = V2(-4) = V3(-4)=V4(-4)=V5(-4) = 0 (состояние -4 происходит точно
{1, 2, 3, 4, >5} времени в 0 циклах).
И так далее....
Это может быть показано используя следующую таблицу:
х
|
Номера циклов
|
|||||
0
|
1
|
2
|
3
|
4
|
5
|
|
-4
|
3
|
0
|
0
|
0
|
0
|
0
|
-3
|
3
|
0
|
0
|
0
|
0
|
0
|
-2
|
3
|
0
|
0
|
0
|
0
|
0
|
-1
|
2
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
2
|
2
|
0
|
0
|
1
|
0
|
0
|
3
|
3
|
0
|
0
|
0
|
0
|
0
|
4
|
3
|
0
|
0
|
0
|
0
|
0
|
- здесь - это вероятность, что состояние х
происходит k раз в произвольном распределении (смотри Секцию 3.15 для таблицы переменных). Величины для л^ (х) и их метод вычисления приведен в Разделе
3.15. Отметьте, что восемь x2 статистики будут произведены (то есть, для х = -4, -3, -2,-1,1, 2, 3,4).
(8) Для каждого состояния, вычислите Р-value = igamc(5/2, x2 (obs)/2). Восемь Р-
values будут произведены.
2.15.5 Правила решения (для уровня 1%)
Если вычисленный P-value < 0.01, тогда решите, что последовательность непроизвольная. В противном случае, решать, что последовательность произвольная.
2.15.6 Вывод и Интерпретация Результатов Теста
С тех пор как P-value полученное на этапе 8 Секции 2.15.4 ^0.01 (P-value 0.502529), вывод - в том, что последовательность произвольная.
Отметьте, что если значения X2{obs}, были слишком большими, тогда последовательность должна отобразить отклонение от теоретического распределения для данного состояния через все циклы.
2.15.7 Рекомендации для входных данных
Рекомендовано, что каждая последовательность, которую нужно тестировать состоит минимум из 1,000,000 битов (то есть, n 106).
2.15.8 Пример
(ввод) =11001001000011111101101010100010001000010110100011
00001000110100110001001100011001100010100010111000
(ввод) n = 1000000 = 106
(обработка) J = 1490
Значения
|
X1
|
P-value
|
Вывод
|
-4
|
3.83569
|
0.573306
|
Random
|
-3
|
7.31870
|
0.197996
|
Random
|
-2
|
7.86192
|
0.164011
|
Random
|
-1
|
15.6926
|
0.007779
|
Non-random
|
+1
|
2.48590
|
0.778616
|
Random
|
+2
|
5.42938
|
0.365752
|
Random
|
+3
|
2.40417
|
0.790853
|
Random
|
+4
|
2.39392
|
0.792378
|
Random
|
(Вывод)
Для семи из состояний х, P-value > 0.01, и вывод должен быть в том, что последовательность будет произвольной. Тем не менее, для одного состояния х (х=1), P-value < 0.01, так что вывод должен быть в том, что последовательность непроизвольная. Когда возникают противоречия, дальнейшие последовательности должны быть изучены, чтобы определить что такое поведение характерное.
Ссылки для теста:
[1] Frank Spitzer, Principles of Random Walk. Princeton: Van Nostrand, 1964 (especially p. 269).
[2] Pal Revesz, Random Walk in Random And Non-Random
Qirxrorx-trp- World Scientific- 1990.
3.15 Тест произвольные отклонения.
Этот тест основан на рассмотрении последующих сумм двоичных битов (плюс или минус простой те) как одномерный произвольный проход. Тест обнаруживает отклонения из распределения количества попаданий произвольного прохода в определенное "состояние", то есть, любая величина целого.
Рассматривайте произвольный проход
как последовательность
отклонений от нуля
Здесь J обозначает общее число таких отклонений в строке, ограничивающее распределение для этого числа (произвольных) J (то есть, количество нулей среди Sk сумм, k = 1, 2,..., n где
S0 = 0) известно, что будет:
z >0
Тест отвергает гипотезу произвольности немедленно если J слишком небольшая, то есть, если следующая Р - величина небольшая:
Если J < тах(0.005 л/и , 500), гипотеза произвольности отвергается. В противном случае количество попаданий произвольного прохода S в определенное состояние будет оценен.
Обозначим (х)- это количеством попаданий для х,х 0, в течение одного 0 - отклонения. Распределение приведено в Revesz (1990) и ВагопиКикЫп(1999):
Это означает, что (х) = 0 с вероятностью 1 - 1/2|х|; в противном случае (с вероятностью 1/2 |х|), (х) совпадает с геометрической произвольной переменной с параметром 1/2|х|.
Это легко можно увидеть
(15)
Вышеуказанные результаты использованы для произвольности, тестирующей следующим образом. Для сбора "представителя" х-переменной (при этом скажем, что 1 < х < 7 или -7 < х < - 1 : - 4 < х < 4 использованы в коде блока теста), оценены наблюдаемые частоты V ^ (х) числа k попаданий в состояние х в течение отклонений J, которые происходят в строке.
Итак Vk (х) = (х), где 0 (х)=1,
если количество попаданий х в течение j-ых отклонений (j = 1,...,J) точно равно k, в противном случае (х) = 0. Значение величины (х) в классе, где k = 0,1,... 4 с дополнительным классом k > 5.
Теоретическая вероятность для этих классов:
Эта вероятность имеет форму
Сравните эти частоты с теоретическими используя X2 - тест.
которое, для любого х под гипотезой произвольности, должно иметь приблизительно X2 - распределение с 5 градусами свободы. Это -правильный тест, когда Jminn- (х) > 5, то есть, если J > 500. (Код блока теста использует (х = 4) для (х). Если это условие не выполняется, то величина £(x), должна быть переведена в большие классы.
Соответствующая Р - величина сообщения. Эти величины может быть получена из формулы: