М послідовності або послідовності максимальної довжини англ Maximum length sequence MLS псевдовипадкові послідовності що

М-послідовності або послідовності максимальної довжини (англ. 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.

Примітки

Голомб, 1967

[1] Голомб, 1967