Постулаты Голомба.

Соломон Голомб предложил следующие необходимые свойства для периодической последовательности с периодом T:

Пусть -двоичная периодическая последовательность с периодом T.

Обозначим через и число 0 и 1 в последовательности

Обозначим через и соответственно число s-грамм, составленных из 0 и число s-грамм, составленных из 1.

Рассмотрим последовательность

где индексы рассматриваются по модулю T.

Определим для этой последовательности величины

Определим функцию автокорреляции последовательности :

Постулаты Голомба таковы:

 

1.

2.

3. Функция автокорреляции должна принимать лишь 2 значения.

Пример.

1. ,

2.

 

3.

 

Последовательность, удовлетворяющая постулатам Голомба, называется pn-последовательностью.

Также используются статистические тесты, которые проверяют полезные гипотезы:

· (monobit test) равно ли количество 0 и 1;

· (two bit test) равно ли количество 00, 01, 10, 11:;

· (poker test) равно ли количество различных последовательностей длины n;

· (runs test) подходящее ли количество последовательностей идущих подряд 0 и 1 различной длины;

· (autocorrelation test) одинаковая ли автокорреляция на разных сдвигах.

· (Maurer test) хорошо ли получается сжать получившийся поток.

Хорошая псевдослучайная последовательность должна проходить все эти тесты.