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

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

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

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

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

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

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

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

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

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

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

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

• Періодична АКФ будь-якої М-послідовності має постійний рівень бічних пелюсток, що дорівнює ${\displaystyle -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.