М-последовательность

У этого термина существуют и другие значения, см. MLS (значения).

М-последовательность или последовательность максимальной длины (англ. maximum-length sequence, MLS) — псевдослучайная двоичная последовательность, порожденная регистром сдвига с линейной обратной связью и имеющая максимальный период. М-последовательность является линейной рекуррентой над полем GF(2).

М-последовательности применяются в широкополосных системах связи.

Свойства

М-последовательности обладают следующими свойствами (Голомб, 1967):

• М-последовательности являются периодическими с периодом ${\displaystyle N=2^{n}-1}$;
• количество символов, принимающих значение единица, на длине одного периода М-последовательности на единицу больше, чем количество символов, принимающих значение нуль;
• любые комбинации символов длины ${\displaystyle n}$ на длине одного периода М-последовательности за исключением комбинации из ${\displaystyle n}$ нулей встречаются не более одного раза. Комбинация из ${\displaystyle n}$ нулей является запрещённой: на её основе может генерироваться только последовательность из одних нулей;
• сумма по модулю 2 любой М-последовательности с её произвольным циклическим сдвигом также является М-последовательностью;
• периодическая АКФ любой М-последовательности имеет постоянный уровень боковых лепестков, равный ${\displaystyle -1/N}$^[1];
• АКФ усечённой М-последовательности, под которой понимается непериодическая последовательность длиной в период N, имеет величину боковых лепестков, близкую к ${\displaystyle -1/{\sqrt {N}}}$. Поэтому с ростом N величина боковых пиков уменьшается^[1].

Взаимоотношение с преобразованием Адамара

Кон и Лемпель (1977) обнаружили взаимоотношение между М-последовательностями и преобразованием Адамара^[англ.], благодаря чему стало возможным вычисление автокорреляционной функции М-последовательности с помощью быстрого алгоритма наподобие БПФ.

См. также

• Псевдослучайная двоичная последовательность
• Адамар, Жак