Псевдослучайная двоичная последовательность

Псевдослуча́йная двои́чная после́довательность — частный случай псевдослучайной последовательности, в которой элементы принимают два возможных значения 0 и 1 (или -1 и +1 ). Является периодической.

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

Одна из первых формулировок некоторых основополагающих правил для статистических свойств периодических псевдослучайных последовательностей была представлена Соломоном Голомбом. Три основных правила получили известность как постулаты Голомба.

  1. Количество "1" в каждом периоде должно отличаться от количества "0" не более, чем на единицу.
  2. В каждом периоде половина серий (из одинаковых символов) должна иметь длину один, одна четверть должна иметь длину два, одна восьмая должна иметь длину три и т.д. Более того, для каждой из этих длин должно быть одинаковое количество серий из "1" и "0".
  3. Предположим, у нас есть две копии одной и той же последовательности периода p, сдвинутые относительно друг друга на некоторое значение d. Тогда для каждого d, 0 <= d <= p-l, мы можем подсчитать количество согласованностей между этими двумя последовательностями Ad, и количество несогласованностей Dd. Коэффициент автокорреляции для каждого d определяется соотношением (Ad - Dd)/p и эта функция автокорреляции принимает различные значения по мере того, как d проходит все допустимые значения. Тогда для любой последовательности, удовлетворяющей правилу 3, автокорреляционная функция (АКФ) должна принимать лишь два значения.

Постулат 3 — это техническое выражение того, что Голомб описал как понятие независимых испытаний: знание некоторого предыдущего значения последовательности в принципе не помогает предположениям о текущем значении. Еще одна точка зрения на АКФ состоит в том, что это некая мера способности, позволяющей различать последовательность и её же копию, но начинающуюся в некоторой другой точке цикла.

Последовательность, удовлетворяющая постулатам Голомба часто именуется псевдо-шумовой последовательностью или ПШ-последовательностью.

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

Разновидности

См. также