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-послідовності періодичні і регістр зсуву проходить в циклі через кожне можливе двійкове значення (за винятком нульового вектора), регістри можуть бути ініціалізовані будь-яким початковим значенням (станом), за винятком нульового.

Взагалі в алгоритмі створення М-послідовності за допомогою регістра зсуву можуть підсумовуватись будь-яка кількість елементів із заданими індексами, але не кожна з таких схем буде видавати на виході M-послідовність. Такі регістри зсуву зручно описувати у термінах поліномів, де ступінь відповідає індексу елементу, а коефіцієнт $0$ або $1$ — включеності елементу у суму. Наприклад, описаній вище схемі відповідає поліном 4 ступеня із коефіцієнтами $0,0,1,1$, тобто $x^{4}+0x^{3}+0x^{2}+1x^{1}+1x^{0}=x^{4}+x+1$. Для того, щоб результатом роботи схеми була 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.