Псевдослучайная двоичная последовательность
Псевдослуча́йная двои́чная после́довательность — частный случай псевдослучайной последовательности, в которой элементы принимают два возможных значения 0 и 1 (или -1 и +1 ). Является периодической.
Постулаты Голомба
правитьОдна из первых формулировок некоторых основополагающих правил для статистических свойств периодических псевдослучайных последовательностей была представлена Соломоном Голомбом. Три основных правила получили известность как постулаты Голомба.
- Количество "1" в каждом периоде должно отличаться от количества "0" не более, чем на единицу.
- В каждом периоде половина серий (из одинаковых символов) должна иметь длину один, одна четверть должна иметь длину два, одна восьмая должна иметь длину три и т.д. Более того, для каждой из этих длин должно быть одинаковое количество серий из "1" и "0".
- Предположим, у нас есть две копии одной и той же последовательности периода p, сдвинутые относительно друг друга на некоторое значение d. Тогда для каждого d, 0 <= d <= p-l, мы можем подсчитать количество согласованностей между этими двумя последовательностями Ad, и количество несогласованностей Dd. Коэффициент автокорреляции для каждого d определяется соотношением (Ad - Dd)/p и эта функция автокорреляции принимает различные значения по мере того, как d проходит все допустимые значения. Тогда для любой последовательности, удовлетворяющей правилу 3, автокорреляционная функция (АКФ) должна принимать лишь два значения.
Постулат 3 — это техническое выражение того, что Голомб описал как понятие независимых испытаний: знание некоторого предыдущего значения последовательности в принципе не помогает предположениям о текущем значении. Еще одна точка зрения на АКФ состоит в том, что это некая мера способности, позволяющей различать последовательность и её же копию, но начинающуюся в некоторой другой точке цикла.
Последовательность, удовлетворяющая постулатам Голомба часто именуется псевдо-шумовой последовательностью или ПШ-последовательностью.
К анализируемой последовательности применяется широкий спектр различных статистических тестов для исследования того, насколько хорошо она согласуется с допущением, что для генерации использовался совершенно случайный источник.
Разновидности
правитьСм. также
править- Генератор псевдослучайных чисел
- Псевдослучайная последовательность
- Тестирование псевдослучайных последовательностей
- Теорема «О амплитудно-частотной характеристике идеальной бинарной случайной последовательности» . "Проблемы современной науки и образования"; № 1 (31)/2015.