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

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

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

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

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

${\displaystyle a_{k}[n+1]={\begin{cases}a_{0}[n]+a_{1}[n],&k=3\\a_{k+1}[n],&k\neq 3\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 1}$, на одиницю більша, ніж кількість знаків, які набувають значення ${\displaystyle 0}$.

• Будь-які поєднання знаків довжини ${\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.