Методика статистичного тестування: Технічний звіт ІІТ – 001-2004, страница 10

Нехай xkk-тий біт, де k = 1, …, n... Покладемо, що біти мають значення 1 і –1. Нехай

де exp(2πikj/n) = cos(2πkj/n) + i sin(2πkj/n), j = 0, …, n-1, і i. Через симетрію дійсного комплекснозначного перетворення розглядаються тільки значення від 0 до (n/2 - 1). Нехай modj – модуль комплексного числа fj. При допущенні випадковості серій xi, довірчий інтервал може бути обраний як значення з modj. Більш точно, 95% значень з modj повинні бути менше, ніж .

Р-значення, засноване на цій границі, має біноміальний розподіл. Нехай N1 – кількість піків, менше чим h. Розглядаються тільки перші n/2 піків. Нехай N0 = 0,95 N/2 і . Р-значення має вид

 ,

де - інтегральна функція імовірності стандартного нормального розподілу.

Можливо й інше Р-значення, засноване на серіях fj чи modj, що є чутливими до відхилення від випадковості. Однак, основне значення перетворення походить від графіка серій modj.

Відсутність даних про частотні компоненти

 
Подпись: Амплітуда

Наявність даних про частотні компоненти

 
Подпись: Амплітуда

Рис.1. Результати тестування генераторів

На представленому рисунку верхній графік відображає серії з modj для 4096 біт, згенерованих гарним генератором. Лінія, що проходить через графік, позначає 95% довірчу границю. Р-значення для цих серій дорівнює 0,8077. Нижній графік відображає відповідний графік для генератора, що робить статистично пов'язані біти. На даному графіку значно більше, ніж 5% величин, лежать за межами довірчої границі. Р-значення для цих серій дорівнює 0,0001.

Приклад.

Вхід: e = 1001010011,

n=10.

Тест:

х = 1, -1, -1, 1, -1, 1, -1, -1, 1, 1,

S = DFT(x),

M1 = modulus(1,618-1,175i) = 2,

M2 = modulus(1,381-4,253i) = 4,472,

M3 = modulus(-0,618-1,902i) = 2,

M4 = modulus(3,618+2,628i) = 4,472,

M5 = modulus(-2 - 7,04·10-19 i) = 2,

- тест пройдено.

4.7. Перевірка шаблонів, що не перекриваються

Даний тест відбраковує послідовності, які занадто часто чи дуже рідко з'являються в даному аперіодичному шаблоні.

Нехай  - дане слово ( шаблон чи паттерн, тобто фіксована послідовність нулів і одиниць) довжини m. Даний шаблон вибирається як параметр тесту. Покладемо, тест заснований на шаблонах фіксованої довжини m. Нижче представлені таблиці обраних аперіодичних слів таких шаблонів для m = 2, …, 8...

Безліч періодів В

ß

відіграє важливу роль. Наприклад, коли В відповідає серії з m одиниць, ß = {1, …, m - 1}. Для вищезгаданого В ß=0, і В є аперіодичним шаблоном (тобто він не може бути записаний як СС…СС’ для шаблона З, що коротше чим В, де С’ позначає префікс С). У даній ситуації поява В в рядку є такою, що не перекривається.

У загальному випадку, нехай W = W(m, M) позначає кількість входжень даного шаблону В в строку. Помітимо, що статистика W визначена також для шаблонів В з ß ≠ 0. Найкращим шляхом обчислення W є обчислення W як суми

Випадкові величини  є m-залежними, таким чином Центральна Гранична Теорема здійсненна для W. Середнє і дисперсія апроксимуючого нормального розподілу мають вид

Для стандартних кодів програми M і N обрані таким чином, що n = MN і N = 8.

Вхідна строка розбивається на N блоків довжиною M. Нехай Wj = Wj (m, M) позначає кількість входжень шаблону В в блок j, j = 1, …, N.

Нехай µ = E Wj = (Mm + 1)2-m. Тоді , для великих M, Wj виконується нормальний розподіл із середнім µ і дисперсією σ2, і статистика

наближається до χ2 – розподілу з N  ступенями свободи. Р-значення має вид .

Тест може бути інтерпретований як відсікання послідовностей, що мають нерегулярне входження даного неперіодичного шаблона.

Таблиця 11. Неперіодичні шаблони для малих значень 2 ≤ m ≤ 5