М-послідовності або послідовності найбільшої довжини (також "максимальної довжини", , MLS) — псевдовипадкові послідовності, що мають широке застосування у широкосмугових системах зв'язку. Зазвиай користуються двійковими М-послідовностями, елементи яких — це числа 1 або 0.
Створення М-послідовності
М-послідовності створюють за допомогою регістрів зсуву з лінійним зворотнім зв'язком. Наприклад, варіант системи побудови М-послідовності з регістром, що має довжину 4, зображено на рисунку 1. Цю схему можна також виразити таким рекурентним співвідношенням:
де n — часу, k — позиція біту в регістрі, а "" означає додавання за модулем 2.
M-послідовності періодичні і регістр зсуву проходить в циклі через кожне можливе двійкове значення (за винятком нульового вектора), регістри можуть бути ініціалізовані будь-яким початковим значенням (станом), за винятком нульового.
Загалом в алгоритмі створення М-послідовності за допомогою регістра зсуву можна підсумовувати будь-яку кількість елементів із заданими індексами, проте не кожна з таких схем буде видавати на виході M-послідовність. Такі регістри зсуву зручно описувати за допомогою многочленів, де ступінь відповідає індексу елемента, а коефіцієнт або — включеності елементу в суму. Наприклад, описаній вище схемі відповідає многочлен 4-го степеня з коефіцієнтами , тобто . Для того, щоб результатом роботи схеми була M-послідовність, необхідною і достатньою умовою є те, що відповідний многочлен є примітивним.
Властивості
М-послідовності мають такі властивості.Голомб, 1967
М-послідовності є періодичними з періодом .
Протягом одного періоду М-послідовності кількість знаків, які набувають значення , на одиницю більша, ніж кількість знаків, які набувають значення .
Будь-які поєднання знаків довжини впродовж одного періоду М-послідовності за винятком комбінації з нулів трапляються не більше одного разу. Комбінація з нулів заборонена, адже на її основі може генеруватися лише послідовність з одних нулів.
Сума за модулем 2 будь-якої М-послідовності з її довільним циклічним зсувом також є М-послідовністю.
Періодична самокореляційна функція будь-якої М-послідовності має сталий рівень бічних пелюсток, що дорівнює .
Зв'язок із перетворенням Адамара
Кон і Лемпель (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.
Примітки