M-послідовність

М-послідовності або послідовності максимальної довжини (англ. Maximum length sequence, MLS) — псевдовипадкові послідовності, що знайшли широке застосування у широкосмугових системах зв'язку. Як правило, використовуються двійкові М-послідовності, члени яких є числами 1 або 0.

Створення М-послідовності

Рисунок 1. Наступне значення регістру а₃ у петлі зворотного регістру зсуву, що має довжину 4, визначається сумою a₀ та a₁ за модулем-2.

М-послідовності створюються за допомогою регістрів зсуву з лінійним зворотнім зв'язком. Система створення М-послідовності з таким регістром, що має довжину 4, зображена на рисунку 1. Створення можна також виразити таким рекурентним співвідношенням:

$a_k[n+1] = \begin{cases} a_0[n] + a_1[n], & k = 3 \\ a_{k+1}[n], & \mbox{otherwise} \end{cases}$

де n - індекс часу, k - позиція біту в регістрі, а $+$ означає додавання за модулем-2.

M-послідовності періодичні і регістр зсуву проходить в циклі через кожне можливе двійкове значення (за винятком нульового вектора), регістри можуть бути ініціалізовані будь яким початковим значенням (станом), за винятком нульового.

Властивості

М-послідовності мають такі властивості.

• М-послідовності є періодичними з періодом $N = 2^n-1$;

• На протязі одного періоду М-послідовності кількість символів, які приймають значення одиниця, на одиницю більша, ніж кількість символів, які приймають значення нуль;

• Будь-які комбінації символів довжини $n$ на довжині одного періоду М-послідовності за винятком комбінації з $n$ нулів зустрічаються не більше одного разу. Комбінація з $n$ нулів заборонена, оскільки на її основі може генеруватися лише послідовність з одних нулів;

• Сума по модулю 2 будь якої М-послідовності з її довільним циклічним зсувом також є М-послідовністю;

• Періодична АКФ будь-якої М-послідовності має постійний рівень бічних пелюсток, що дорівнює $-1/N$.

Взаємовідносини з перетворенням Адамара

Кон і Лемпела (1977) виявили взаємовідношення між М-послідовностями та перетворенням Адамара (англ.), завдяки чому стало можливим обчислення АКФ М-послідовності за допомогою швидкого алгоритму на зразок БПФ.

Див. також

• Псевдовипадкова двійкова послідовність
• Генератор псевдовипадкових чисел
• Жак Адамар
• Амплітудно-частотна характеристика
• Кільце многочленів
• Коди Голда
• Коди Касамі

Література

• 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. and Lempel, A. On Fast M-Sequence Transforms, IEEE Trans. Information Theory, vol. IT-23, pp. 135—137, January, 1977.