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

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

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

Свойства

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

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

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

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

См. также

Примечания

↑ ¹ ² Варакин Л. Е. Системы связи с шумоподобными сигналами. — М.: Радио и связь, 1985. — С. 49.

Литература

McEliece R. J. Finite Field for Scientists and Engineers, Kluwer Academic Publishers, 1987.
Golomb S. Shift Register Sequences, San Francisco, Holden-Day, 1967.
Cohn M., Lempel A. On Fast M-Sequence Transforms, IEEE Trans. Information Theory, vol. IT-23, p. 135—137, January, 1977.
Варакин Л. Е. Системы связи с шумоподобными сигналами. — М.: Радио и связь, 1985. — С. 49—65.
Ширман Я. Д., Манжос В. Н. Теория и техника обработки радиолокационной информации на фоне помех. — М.: Радио и связь, 1981. — С. 138—146.

Ссылки

m-sequence generation program for matlab

[svoystva_Varakin-1] ¹ ² Варакин Л. Е. Системы связи с шумоподобными сигналами. — М.: Радио и связь, 1985. — С. 49.

[1]