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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Створення М-послідовності[ред.ред. код]

Рисунок 1. Наступне значення регістру а3 у петлі зворотного регістру зсуву, що має довжину 4, визначається сумою a0 та a1 за модулем-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-послідовності періодичні і регістр зсуву проходить в циклі через кожне можливе двійкове значення (за винятком нульового вектора), регістри можуть бути ініціалізовані будь яким початковим значенням (станом), за винятком нульового.

Властивості[ред.ред. код]

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

  • М-послідовності є періодичними з періодом  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.

Примітки[ред.ред. код]