2. Генерація m-послідовностей та послідовностей Голда

Дослідження ПВП доцільно почати з m-послідовностей, які являються одними з найбільш поширених. До їх переваг можна віднести можливість отримання значної кількості незалежних груп m-послідовностей, а до недоліків – дещо гірші значення АКФ та ВКФ, порівняно з іншими ПВП (послідовності Баркера, Голда). Варто зауважити, що послідовності Голда формуються саме на основі m-послідовностей, що вказує на необхідність їх детального дослідження.

Псевдовипадкові послідовності, частковим випадком яких являються m-послідовності, або послідовності максимальної довжини, можуть бути отримані за допомогою лінійного регістра зсуву з оберненим зв’язком (linear feedback shift register -LFSR) та логічних елементів виключаюче АБО, які фактично здійснюють сумування за модулем 2. На рис.7.12 приведено приклад регістру зсуву LFSR, який містить k окремих регістрів та може реалізувати значну кількість Q незалежних груп m-послідовностей, в залежності від того, виходи яких регістрів (позначені пунктиром) будуть підключені до входів логічного елементу виключаюче АБО.

Рис.7.12. Регістр зсуву LFSR, який містить n-1 окремих регістрів

Отримання m-послідовностей можна розділити (рис.7.13) на два етапи, кожен з яких містить декілька підетапів. Варто зауважити, що перший етап, де визначаються лише кількості, являється більш простим, а другий – на якому формується структура, являється більш складним.

Рис.7.13. Етапи отримання m-послідовностей

Максимальна довжина псевдовипадкової послідовності, отримана за допомогою регістру зсуву становить:

(7.11)

де k – кількість регістрів.

Далі отримана послідовність буде періодично повторюватись.

Кількість варіантів забезпечення зворотних зв’язків, а отже і кількість Q₁ незалежних груп m-послідовностей, для даних регістрів визначається наступним чином:

(М - не просте число) (7.12,а)

(М – просте число) ( 7.12,б)

де - φ(M), функція Ейлера, яка дорівнює кількості чисел в ряді 1,2,3,…,M -1, взаємно простих з числом N.

На рис. 7.14 приведена залежність Q₁(k) для ряду значень k

Рис.7.14. Залежність Q₁(k) при k≤14

На основі отриманої залежності можна зробити важливі висновки:

• для залежності Q₁(k) характерний нелінійний характер зміни, що пояснюється тим, що не всі значення М (4.8) являються простими числами;

• до вибору кількості регістрів треба підходити обґрунтовано, тому що не завжди збільшення кількості регістрів приводить до збільшення кількості незалежних груп Q₁(k) m-послідовностей (наприклад при k=13 отримаємо більше 600 незалежних послідовностей Q₁, а при k=14 – менше 200).

Варто зауважити, що всередині кожної з незалежних груп m-послідовностей також можна отримати досить значну кількість варіантів m-послідовностей, причому їх кількість в кожній групі визначається аналогічно (7.11) та становить:

(7.13)

Таким чином загальна кількість варіантів m-послідовностей, які можуть бути отримані на основі регістру зсуву (рис.7.12), що містить k окремих регістрів, становить:

Q=Q₂*Q₃ (7.14)

Суттєвим являється те, що за допомогою даного регістру зсуву можна отримати дві принципово відмінні групи послідовностей:

• максимальної довжини М, тобто m- послідовності, яким властиві кращі кореляційні властивості, завдяки чому вони знаходять широке застосування в системах зв'язку;

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

Очевидно, що кількість послідовностей немаксимальної довжини буде багато більшою.

Щоб визначити структуру регістра зсуву для формування m-послідовності з періодом 2^k-1, необхідно знати до яких виходів регістру підключати зворотні зв’язки. Варіанти забезпечення зворотнього зв'язку визначаються на основі формуючих поліномів. Очевидно, що саме кількість варіантів формуючих поліномів визначає кількість незалежних груп Q₁ (7.12), тобто кількість варіантів формуючих поліномів також становить Q₁. Пошук всіх можливих видів формуючих поліномів для заданої кількості регістрів зсуву являється досить складною проблемою. Але враховуючи особливу значимість m-послідовностей проблема визначення формуючих поліномів в даний час являється практично вирішеною та їх вид приведено в ряді робіт [8, 14]. Формуючий поліном при використанні n-регістрів має вид:

xⁿ+a_n-1x^n-1+… a_n-2x^n-2+1 ( 7.15)

причому в ньому завжди наявні перший та останній доданки (xⁿ та 1). Отже для компактної форми запису формуючих поліномів досить привести лише коефіцієти a_n-1, a_n-2 і т. д. Наприклад, при n=5 досить привести лише значення індексів (2,3,4) тих коефіцієнтів, які відмінні від нуля (наприклад, коефіцієнт 2 вказує на формуючий поліном х⁵+х²+1, коефіцієнт 432 – на формуючий поліном х⁵+х⁴+х³+х²+1, коефіцієнт 321 – на формуючий поліном х⁵+х³+х²+х¹+1 і т.д.). В табл. 7.1 приведені значення формуючих поліномів. В генераторі кодових послідовностей завжди вихід схеми виключаюче АБО під’єднується до входу першого зліва (В_n-1) регістра, а на вхід схеми виключаюче АБО подається сигнал від крайнього справа (В₀) регістра (рис.3.13). Крім того, на вхід схеми виключаюче АБО подаються сигнали з тих регістрів, на які вказує формуючий поліном, тобто подаються виходи тих регістрів, для яких коефіцієнти в формуючому поліномі не рівні нулю.

З врахуванням вказаної залежності між видом генеруючих поліномів та конфігурацією зворотніх зв’язків, а також даних ( табл.7.1) на рис.7.15 для 5-ти бітового регістру зсуву приведено всі 6 можливих варіантів зворотніх зв’язків. З приведених варіантів видно, що серед 6 різних типів формуючих поліномів наявні три пари, які містять по два дзеркальних поліноми.

Таблиця 7.1