и
а) Гістограма. Гістограма дозволяє визначити рівномірність розподілу символів в тестованої послідовності, а також оцінити частоту появи конкретного символу. Даний тест незамінний при перевірці послідовності на «випадковість», а також при дослідженні генераторів з довільним законом розподілу символів. Для того щоб послідовність задовольняла властивостям випадковості, необхідно, щоб у ній були присутні всі символи, при цьому розкид частот появи символів прагнув до нуля. Розглянутий тест може принести користь також у тих випадках, коли оцінюється якість послідовності з законом розподілу, відмінним від рівномірного, або послідовності, в якій деякі символи взагалі відсутні, і т. д.
б) Розподіл на площині. Тест дозволяє оцінювати рівномірність і незалежність розподілу символів в досліджуваній послідовності. Для побудови графічної залежності на полі розміром 256х256 наносяться точки з координатами
(Qi; Qi +1)
де Qi, - i-й елемент послідовності,, т - довжина послідовності. Далі аналізується отримана картина. У разі неякісної послідовності точки розподілені нерівномірно, або спостерігається якийсь візерунок.
Для послідовностей великої довжини (порядку 700 Кб і вище) позитивним результатом вважається графік, що представляє собою абсолютно чорний квадрат.
в) Байтові АКФ. Тест перевіряє взаімонезавісімие елементів досліджуваної послідовності на основі аналізу сплесків кореляції. Для розрахунку автокореляційної функції послідовність нормується. Нехай [q7 ... q1q0]-двійковий запис елемента послідовності довжиною m, qj {0, 1},. Тоді нормоване значення цього елемента обчислюється як
(3.1)
Після цього обчислюються сплески кореляції
(3.2)
Неважко помітити, що при=0 і=m значення К ()=1. У всіх інших випадках для якісної ПСП значення К () повинні прагнути до нуля.
г) Бітова АКФ. Тест перевіряє взаімонезавісімие бітів послідовності. Спочатку двійкове подання послідовності нормується 1 1, 0 - 1. Потім обчислюються сплески кореляції за формулою
(3.3)
де М - розмір послідовності в бітах, а - i-й біт нормованої послідовності. При=0 і=М значення К ()=1. У всіх інших випадках для якісної ПСП значення К () повинні прагнути до нуля.
д) Перевірка на монотонність. Тест перевіряє рівномірність розподілу символів у досліджуваній послідовності на основі аналізу довжин ділянок зростання та спадання. У якісній ПСП розкид довжин цих ділянок повинен прагнути до нуля.
е) Перевірка 0 і 1. Тест перевіряє рівномірність розподілу символів у досліджуваній послідовності. Для цього підраховується число 0 і 1. У якісній ПСП розкид між кількістю 0 і 1 близький до нуля.
ж) Перевірка серій. Тест перевіряє рівномірність розподілу символів у досліджуваній послідовності, аналізуючи частоту народження биграмм (00, 01, 10, 11) і триграм (000, 001, 010, 011, 100, 101, 110, 111). У якісній ПСП розкид між частотами зустрічальності биграмм (триграм) повинен прагнути до нуля.
3.2 Оціночні тести
а) Критерій. Нехай результати випробувань такі, що їх можна розділити на k категорій. Проводиться п незалежних випробувань. Позначимо ймовірність того, що результат випробування потрапить в s-у категорію, як ps, а число випробувань, які реально потрапили в s-у ка...
