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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Псевдослуча́йная двои́чная после́довательность — частный случай ПСП, в которой элементы принимают два возможных значения 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 — это техническое выражение того, что Голомб описал как понятие независимых испытаний: знание некоторого предыдущего значения последовательности в принципе не помогает предположениям о текущем значении. Еще одна точка зрения на АКФ состоит в том, что это некая мера способности, позволяющей различать последовательность и ее же копию, но начинающуюся в некоторой другой точке цикла.

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

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

Разновидности[править | править вики-текст]

См. также[править | править вики-текст]