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

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

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

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

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

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

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

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