Интернет магазин китайских планшетных компьютеров

Компьютеры - Тестирование псевдослучайных последовательностей

совокупность методов определения меры близости заданной псевдослучайной последовательности к случайной. В качестве такой меры обычно выступает наличие равномерного распределения, большого периода, равной частоты появления одинаковых подстрок и т. п.

Теоретическая основа

Принципы построения

Один из самых наглядных тестов — тест на равномерное распределение частот появления каждого символа. Пусть ξ₁,ξ₂...ξ_n — последовательность длиной n и размерности m. Тогда частоты ν_i должны принадлежать отрезку . Однако, большинство тестов используют другой метод — принятие или отклонение гипотезы о случайности последовательности, используя статистические распределения.

Зная вероятностные свойства истинно случайной последовательности, можно на их основе проверять гипотезу о том, насколько сгенерированная последовательность похожа на случайную. Для этого для каждого теста подбирается подходящая статистика, вычисляется её значения для идеальной и сгенерированной последовательности. Если разность этих значений превышает некоторое критическое значение, установленное заранее, то последовательность считается неслучайной. Для «хороших» последовательностей вероятность такого события крайне мала. Однако, существует вероятность того, что «плохая» последовательность удовлетворит критерию и будет сделан вывод о её случайности. На практике значения длины последовательности n, α и β связаны, задаётся α и подбирается n такое, чтобы минимизировать β.

Определим величину P-value как вероятность того, что идеальный генератор сгенерировал последовательность менее случайную, чем исследуемый. Тогда если P-value больше α, то исследуемая последовательность считается случайной и наоборот в противном случае.

Кратко шаги статистического тестирования можно изобразить в виде таблицы:

№ шага	Процесс	Комментарии
1	Постановка гипотезы	Предполагаем, что последовательность является случайной
2	Вычисление статистики исследуемой последовательности	Тестирование на битовом уровне
3	Вычисление P-value	P-value
4	Сравнение P-value с α	Задаем P-value в пределах; если P-value>α, то тест пройден

Интерпретация результатов

Пусть дана двоичная последовательность s. Требуется установить проходит ли данная последовательность статистический тест или нет. Разработчиками таких тестов применяются несколько различных подходов в определении этого факта:

• пороговое значение
• фиксированный диапазон значений
• значение вероятности

Пороговое значение

Данный подход заключается в подсчете какой-либо статистической величины двоичной последовательности с и его сравнении с некоторым пороговым значением. Если полученное значение с меньше порогового значения, то последовательность s не проходит данный тест.

Фиксированный диапазон значений

Подход также заключается в подсчете некоторой статистической величины двоичной последовательности с как и в первом случае. Однако теперь мы говорим, что если с выходит за пределы некоторого диапазона значений, то последовательность s не проходит данный тест.

Значение вероятности

Третий подход в определении того факта, что двоичная последовательность s проходит статистический тест, включает подсчет не только статистической величины с, но и соответствующее ей значение вероятности p. Обычно подсчет конкретной статистической величины производится таким образом, чтобы её большие значения предполагали неслучайный характер последовательности s. Тогда p есть вероятность получения значения с большего либо равного значению с, высчитанного для истинно случайной последовательности s'. Следовательно, малые значения вероятности p могут быть интерпретированы как доказательство того, что s не является случайной. Таким образом, если для некоторого фиксированного значения a значение вероятности p < a, то двоичная последовательность s не проходит данный тест. Как правило, a принимает значения из интервала.