Статистические свойства последовательностей. Постулаты Голомба

n₁ – число единиц («1») на периоде последовательности.

n₀ – число нулей («0») на периоде последовательности.

S_1,r – число серий из единиц длины r. (r штук единиц подряд)

S_0,r – число серий из нулей длины r.

– число единиц («1») в последовательности

- число нулей («0») в последовательности

Функция автокорреляции

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

·

· где ,

· принимает не более двух значений

Если последовательность удовлетворяет этим постулатам, то она псевдошумовая..

Примером псевдошумовых последовательностей может служить ЛРС (линейный регистр сдвига) максимального периода. (Период ЛРС максимального периода равен )

Д-во:

1)

2) нестрого, но выполняется.

3) Доказать самостоятельно.(Так в лекциях)

Для проверки генераторов применяются статистические тесты

· Частотные

· Автокорреляционный

· Последовательный

· Тест серий

· Универсальный тест

· Тест повторений

· Их комбинации

При комбинировании тестов применяются статистики Фишера-Пирсона(если кол-во тестов небольшое) и Колмогорова-Смирнова.

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