3.4 Тест на самую длинную последовательность единиц в блоке

Для проверки того, случайная величина или нет, используется такая характеристика, как длина самой длинной последовательности единиц. Строка длины п такой, что n = M*N, должна быть разделена на N подстрок, каждая длиной М.

Для тестирования, основанного на длине самых длинных последовательностей единиц Vj в j-ой подстроки размером М выбирается класс К+1(в зависимости от М). Для каждой из

этих подстрок оцениваются частоты Vo, V1 ..Ук (Vo+ V1+...+ VK =N то есть, вычисленные значения самых длинных последовательностей единиц в пределах каждого из этих подстрок, принадлежащих любому из К + 1 выбранных классов). Если есть г единиц и (М - г) нолей в т-битовом блоке, тогда условная вероятностьтого, что самый длинный ряд V в этом блоке - меньше или равен чем т, имеет следующий вид U=min(M-r+l,[r/(m+l)]):

следовательно:

Теоретические вероятности этих классов считаются по формуле. Частоты V_i где i=0...К, полученные опытным путем выражаются через х2 -статистику

который согласно гипотезе о случайности имеет примерное х²- распределение с К степенями свободы. Соответственно P-value будет следующим:

с Р(а,х) определяющм неполную гамма функцию описанную в разделе 3.2.

2.5 Тест ранга бинарной матрицы

2.5.Цели теста

Объектом тестирования является ранг непересекающихся матриц, составляющих полную

последовательность. Цель тестирования состоит в проверке линейной зависимости между

подстроками установленной длины исходной последовательности. Обратите внимание,

что это тест фигурирует в наборе тестов DIEHARD.

2.5.2 Вызов функции Rank(n), где:

n - длина строки битов. Дополнительные входные данные, используемые функцией, из кода программы теста:

-тестируемая последовательность единиц сгенерированная RNG или PRNG; При вызове функции она представляет собой глобальную структуру;

= ₁, ₂, ..., n.

М - число строк в каждой матрице. М должно быть равным 32. В противном случае, если используются другие значения М, необходимо провести аппроксимацию заново.

Q - Число колонок в каждой матрице. Q должно быть равным 32. В противном случае, если используются другие значения, необходимо провести аппроксимацию заново.

2.5.3 Статистика теста и начальное распределение

х²(obs) мера того на сколько совпадает наблюдаемое значение ранга в разном порядке с ожидаемым значением ранга при случайном распределении.

Начальное распределение для составления статики – это х2 распределение.

2.5.4 Описание теста

(1) Поочередно последовательность делится на М* 0-битовых блоков; Таким образом

будет N= n/M*Q блоков. Отброшенные биты не будут принимать участие в вычислении

каждого блока. М*0-битовые сегменты собираются в матрицы размером [М,0]. Каждая

строка матрицы заполняется соответствующим 0-битовым блоком исходной

последовательности.

Например, если п= 20, М= О = 3, и е= 01011001001010101101, делим поток HaN= n\3*3=2

и получаем 2-е матрицы кардинальностью M*Q (3* 3 = 9). Обратите внимание, что

последние биты(1и0) отбрасываются. Получается две матрицы:

Обратите внимание на то, что первая строка первой матрицы состоит из первых 3-х битов, вторая из следующих 3-х бит и третья соответственно из 3-х следующих за ними.

(2) Определяется ранг (R_L) бинарной матрицы, где L=l. .N. Метод определения ранга описан в приложении А. Например в этом разделе ранг первой матрицы равен 2 (R₁=2), a ранг второй равен 3 (R₂=3).

(3) Пусть Fm = числу матриц с RL= M (полный ранг), Рт-1=числу матриц с RL= М-1(полный ранг-1), N- Fm - Fm-1 = числу остальных матриц.

(4) Вычислить

2.5.5 Правило, по которому строится вывод

Если вычисленный P-value < 0.01, то можно сделать заключение, что последовательность

неслучайна. Иначе - последовательность случайна.