Радиотехника и электроника, 2023, T. 68, № 7, стр. 676-682

ВВЕДЕНИЕ

Современные системы передачи цифровой информации (СПЦИ) по радиоканалам характеризуются широким использованием сигналов с расширенным спектром (СРС), формируемых с помощью псевдослучайных последовательностей (ПСП) [1–4]. Наряду с двоичными последовательностями в современных и перспективных СПЦИ могут применяться недвоичные ПСП, обладающие заданными корреляционными и структурными свойствами [3, 5–13]. Повышение помехозащищенности СПЦИ достигается применением ПСП с малым уровнем пиков корреляционной функции. К классу минимаксных последовательностей с двухуровневой периодической автокорреляционной функцией (ПАКФ) относятся как двоичные, так и недвоичные М-последовательности (МП) и последовательности Гордона–Миллса–Велча (ГМВП) [14–16]. При этом ГМВП имеют более высокую структурную скрытность, характеризуемую эквивалентной линейной сложностью (ЭЛС), что определяет приоритетность их применения в СПЦИ, к которым предъявляются повышенные требования по конфиденциальности [17, 18].

Недвоичные ГМВП характеризуются более высоким по сравнению с двоичными последовательностями выигрышем в структурной скрытности, который определяется отношением ЭЛС ГМВП и МП M = l_sГМВП/l_sМП при сопоставимых периодах. Например, для пятеричных ГМВП с периодом N = 15624 выигрыш составляет М = 50, а для двоичных ГМВП с периодом N = 16383 выигрыш составляет М = 32. С увеличением периода и значности p выигрыш возрастает. Так, для семеричных ГМВП с периодом N = 117648 выигрыш составляет М = 196, а для двоичных ГМВП с периодом N = 262143 выигрыш М = 128.

1. ПОСТАНОВКА ЗАДАЧИ

Формирование недвоичных ГМВП осуществляется над конечными полями GF(p). Все вычисления производятся в полях

Период последовательностей является составным числом, т.е. N = p^mn – 1. Символы d_i ГМВП определяются выражением [3, 15] где tr_a,b(⋅) – след элемента, принадлежащего полю GF(p^a), в поле GF(p^b); α ∈ GF[(p^m)ⁿ] – примитивный элемент; r – натуральное число, взаимно простое с порядком мультипликативной группы подполя GF(p^m), равным p^m – 1.

Формирование недвоичных ГМВП в соответствии с (1) характеризуется достаточной вычислительной сложностью, определяемой необходимостью построения расширенного поля GF[(p^m)ⁿ] и двухэтапного вычисления функций следа tr_a,b(⋅). Для построения поля GF[(p^m)ⁿ] требуется не менее 2(mn – 2)p^mn операций модульного сложения и умножения.

Основную вычислительную нагрузку при прямом формировании ГМВП составляют вычисления функций следа. Например, при формировании троичной ГМВП с периодом N = 3⁶ – 1 = 728 и параметрами m = 3, n = 2, r = 5 для определения символа d₁ выполняются следующие операции в поле GF(3⁶), построенном по полиному f(x) = х⁶ + + x + 2:

– вычисление функции следа из поля GF(3⁶) в подполе GF(3³)

– возведение элемента α²⁸⁰, принадлежащего подполю GF(3³), в степень r = 5 – вычисление функции следа из подполя GF(3³) в простом поле GF(3)

При вычислениях необходимо выполнить несколько переходов от степенной формы записи элементов поля к векторной и обратно. Всего для нахождения всех символов ГМВП необходимо выполнить N = p^mn – 1 таких вычислительных процедур.

Для полей GF[(p^m)ⁿ] при n = 2 известны алгоритмы формирования троичных, пятеричных и семеричных ГМВП [11, 14, 16], основанные на представлении базисной МП в виде матрицы размерности [(p^m–1) × (p^m + 1)]. Вычислительная сложность определяется необходимостью определения правил формирования циклических сдвигов столбцов матрицы базисной МП, нахождения проверочного полинома ГМВП по алгоритму Берлекемпа–Месси, позволяющего вычислить вектор индексов децимации, и решения системы уравнений для вычисления вектора сдвигов базисной МП при формировании ГМВП.

Цель данной статьи – разработка метода формирования недвоичных ГМВП, основанного на аналитическом определении вектора индексов децимации А_m,n,r символов базисной МП и упрощенном вычислении вектора ее сдвигов для суммируемых последовательностей.

Метод формирования недвоичных ГМВП является обобщением метода для двоичных последовательностей [18] и включает алгоритм формирования вектора индексов децимации А_m,n,r символов базисной недвоичной МП, методику определения полных наборов векторов индексов децимации А_m,n,r для произвольных МП и алгоритм определения вектора сдвигов C_m,n,r базисной МП при формировании суммируемых последовательностей.

Разработанный метод характеризуется низким уровнем вычислительной сложности, обусловленным отсутствием необходимости построения конечных полей GF[(p^m)ⁿ] и двухэтапного вычисления функций следа. Формируется только одна базисная МП в каноническом виде по заданному примитивному полиному и известному начальному состоянию. При реализации алгоритма формирования вектора индексов децимации А_m,n,r основные преобразования выполняются с множеством целых чисел, что характеризуется низкой вычислительной сложностью.

2. АЛГОРИТМ ФОРМИРОВАНИЯ ВЕКТОРА ИНДЕКСОВ ДЕЦИМАЦИИ А_m,n,r

Основной составляющей метода является алгоритм формирования вектора индексов децимации А_m,n,r. Число компонент вектора А_m,n,r = = (I_d1, I_d2, …, I_dМ) равно отношению ЭЛС ГМВП и МП M = l_sГМВП/l_sМП. Тогда ЭЛС формируемой ГМВП определяется выражением

Формирование ГМВП может быть реализовано аппаратным и программным способом. При аппаратной реализации формирование ГМВП выполняется на основе совокупности из M регистров сдвига с линейными обратными связями, определяемыми коэффициентами неприводимых полиномов h_сi(x), являющихся множителями проверочного полинома ГМВП h_ГМВП(x).

При программной реализации алгоритма структура полиномов h_сi(x) не учитывается. Используется понятие вектора индексов децимации А_m,n,r, компоненты которого I_di соответствуют индексам полиномов h_сi(x).

Алгоритм формирования вектора индексов децимации А_m,n,r символов базисной недвоичной МП основан на модифицированном алгоритме формирования аналогичного вектора для двоичных последовательностей, разработанном в [19]. Первое отличие, определяющее научную новизну, заключается в модернизации выражения для вспомогательного параметра k_i

где параметр T равен числу компонент I_bi вектора альтернатив B_m,n,r, в котором содержатся все индексы децимации I_di , являющиеся компонентами вектора А_m,n,r. Для конечного поля GF[(p^m)ⁿ] параметр T определяется по выражению

Вторым отличием является порядок вычисления функции g(r). В двоичном случае ее значение определяется числом единиц в двоичном представлении параметра r. При p > 2 она равна арифметической сумме значений разрядов p-го представления данного параметра.

Компоненты I_bi вектора альтернатив B_m,n,r вычисляются в соответствии с заданным значением параметров r и k_i

Отметим, что при i > T–1 наступает циклическое повторение значений компонент I_bi по mod(p^mn – 1).

Для перехода от вектора альтернатив B_m,n,r к вектору индексов децимации А_m,n,r необходимо представить значения компонент I_bi в p-й системе счисления, выбрать те из них, которые удовлетворяют значению функции g(r), и исключить компоненты, которые относятся к одинаковым циклотомическим классам.

При формировании ГМВП базисная МП представляется в каноническом виде, ее символы определяются выражением (1) при r = 1

требующим построения расширенного поля GF[(p^m)ⁿ].

Формирование МП вместо (6) может быть реализовано без построения конечного поля на основании полинома

в соответствии с выражением где d_j – символы начального состояния МП (0 ≤ j < < S), а операции выполняются по mod p.

Для получения базисной МП в каноническом виде для различных сочетаний параметров p, m, n используются примитивные полиномы h₁(x) степени S = mn и начальные символы d_i (i = 0, 1, …, S – 1), приведенные в табл. 1. При других начальных символах формируются МП не в каноническом виде.

В качестве примера определим вектор индексов децимации А_3,2,17 в расширенном поле GF[(p^m)ⁿ] = GF[(3³)²] с примитивным полиномом h₁(x) = х⁶ + x + 2 для значения параметра r = 17₁₀ = = 122₃ и функции g(r) = 1+2+2 = 5.

Компоненты I_bi вектора альтернатив B_3,2,17, число которых равно Т = 28, вычисляются в соответствии с (3) и (5)

После проверки функции g(r) = 5 и приведения компонент I_bi к минимальным значениям в циклотомических классах определяется вектор индексов децимации

Линейная сложность ГМВП с периодом N = 728, сформированной путем сложения ПСП с данными индексами децимации базисной МП, в соответствии с (2) равна l_s = 54, т.е. в 9 раз превышает ЭЛС МП.

Методика определения полных наборов векторов индексов децимации А_m,n,r для произвольных МП основана на свойстве повторяемости соотношений между корнями проверочных полиномов базисной и произвольной МП и соответствует аналогичной методике для двоичного случая [18]. Символы произвольной МП с аналогичным периодом образуются путем децимации символов базисной МП по некоторому индексу I_МП. Компоненты вектора А_m,n,r преобразуются в компоненты вектора ${\mathbf{А}}_{{m,n,r}}^{{{\text{МП}}}}$ в соответствии с выражением

Полученные компоненты приводятся к минимальным значениям в соответствующих циклотомических классах.

В качестве примера рассмотрим формирование ГМВП в поле GF[(3³)²], если произвольная МП образуется из базисной по индексу I_МП = 97. Преобразуя вектор индексов децимации вида (8) в соответствии с (9), получим новый вектор

на основании которого может быть синтезирована новая ГМВП.

Число различных ГМВП, которые могут быть сформированы для заданных значений параметров p, m, n и r, равно числу МП с периодом N = p^mn – 1.

3. АЛГОРИТМ ОПРЕДЕЛЕНИЯ ВЕКТОРА СДВИГОВ C_m,n,r

Алгоритм определения вектора сдвигов C_m,n,r базисной МП для суммируемых последовательностей при формировании недвоичных ГМВП является обобщением аналогичного алгоритма для двоичного случая. При p = 2 децимация всех последовательностей производится с символа d₀ базисной МП. Особенностью формирования недвоичных ГМВП является то, что децимация суммируемых последовательностей может начинаться с некоторого сдвига базисной МП. Анализ формирования ГМВП при p = 3, 5, 7 [11, 14, 16] показал, что возможные сдвиги определяются выражением

Таким образом, основная проблема при формировании недвоичных ГМВП с известным вектором индексов децимации А_m,n,r мощностью M заключается в нахождении начальных сдвигов λ_i базисной МП, образующих вектор сдвигов C_m,n,r аналогичной мощности, для каждого индекса децимации I_di.

В общем случае для определения вектора сдвигов C_m,n,r требуется выполнить число операций вычисления ПАКФ формируемых последовательностей

Для уменьшения числа операций был проведен анализ распределения сдвигов λ_i с учетом p-го представления индексов децимации I_di. Анализ показал, что последовательности, формируемые по индексам децимации, имеющим одинаковое распределение ненулевых цифр на позициях p-го представления, обладают одинаковыми начальными сдвигами. Например, при р = 5 и g(r) = 3 последовательности с индексами децимации I_d1 = 7₁₀ = = 12₅, I_d2 = 11₁₀ = 21₅, I_d3 = 27₁₀ = 102₅, I_d4 = 51₁₀ = 201₅, I_d5 = 127₁₀ = 1002₅ имеют одинаковый начальный сдвиг λ₁ = λ₂ = λ₃ = λ₄ = λ₅ = 3N/4.

Данное свойство позволяет уменьшить число операций при определении вектора сдвигов C_m,n,r. Объединим в группы индексы децимации I_di с одинаковым в каждой группе распределением цифр на позициях их p-го представления. Можно показать, что число M₁ групп для различных значений функции g(r) ограничено сверху произведением mn(p – 1)/2 и всегда меньше общего числа индексов децимации. При этом число операций вычисления ПАКФ равно

Выигрыш в вычислительной сложности составляет

Алгоритм определения вектора сдвигов C_m,n,r при децимации базисной МП записывается в следующем виде.

Шаг 1. Перевод компонент I_di вектора индексов децимации А_m,n,r в p-ю систему счисления.

Шаг 2. Объединение индексов децимации в группы с одинаковым распределением цифр на позициях их p-го представления.

Шаг 3. Вычисление ПАКФ формируемой последовательности для различных значений сдвига в каждой группе.

Шаг 4. При получении двухуровневой ПАКФ, соответствующей ГМВП, переход к окончанию алгоритма с определением финального вектора сдвигов C_m,n,r.

В качестве примера определим вектор сдвигов C_m,n,r = C_3,2,17 для вектора индексов децимации А_3,2,17 мощностью M = 9 из (8) при формировании ГМВП с периодом N = 3⁶ – 1 = 728 в расширенном поле GF[(3³)²] с примитивным полиномом h₁(x) = х⁶ + x + 2 для значения параметра r = 17₁₀ = = 122₃.

Шаг 1. Перевод компонент вектора А_3,2,17 в троичную систему счисления:

Шаг 2. Объединение индексов децимации в M₁ = 3 группы:

Шаг 3. Максимальное число вычислений ПАКФ равно L₂ = 2³ = 8. Выигрыш в вычислительной сложности по сравнению с L₁ = 2⁹ = 512 составляет W = 2⁶ = 64. С увеличением p и M выигрыш возрастает.

Двухуровневая ПАКФ для ГМВП была получена при сдвигах λ_G1 = 0, λ_G2 = N/2 = 364, λ_G3 = 0. Финальный вектор сдвигов C_m,n,r при децимации базисной МП имеет вид

Шаг 4. Базисная МП строилась по проверочному полиному

в соответствии с выражением

где суммирование символов выполняется по mod 3 с начальными символами d₀, d₁, d₂, d₃, d₄, d₅, равными 0, 0, 0, 0, 0, 1 соответственно.

Двухуровневая ПАКФ была получена для ГМВП F_ГМВП, образованной путем суммирования девяти ПСП F_j (значение j соответствует индексу децимации) с символами d_i базисной МП из (16) и вектором сдвигов вида (15). В табл. 2 представлены сегменты данных последовательностей длиной 14 символов.

Отметим, что при формировании F_ГМВП все суммируемые по mod 3 последовательности являются МП, кроме ПСП F₄₉, период которой равен 104. Значения индексов i в d_i вычисляются по mod 728.

Полученный вектор сдвигов C_3,2,17 вида (15) может быть использован при формировании ГМВП для произвольной МП, например, образуемой из базисной МП по индексу I_МП = 97 с вектором индексов децимации ${\mathbf{А}}_{{{\text{3,2,17}}}}^{{{\text{97}}}}$ вида (10). Основное требование заключается в неизменности порядка следования компонентов векторов. Отметим, что в обоих случаях при формировании ГМВП используются только символы базисной МП вида (16).

Для некоторых значений параметров получены наборы векторов индексов децимации и векторов сдвигов базисных МП, которые представлены в табл. 3. Формирование МП проводилось в соответствии с исходными данными из табл. 1.

ЗАКЛЮЧЕНИЕ

Таким образом, разработан метод формирования недвоичных ГМВП, включающий алгоритм формирования вектора индексов децимации А_m,n,r для базисной МП, методику определения полных наборов векторов индексов децимации для произвольных МП и алгоритм определения вектора сдвигов C_m,n,r базисной МП при формировании суммируемых последовательностей. Отличие алгоритма формирования вектора А_m,n,r от двоичного случая заключается в выражении для вспомогательного параметра k_i при определении вектора альтернатив B_m,n,r и числа T его компонент. Вычисление вектора А_m,n,r не требует построения расширенных полей GF[(p^m)ⁿ]. Новизна алгоритма определения вектора C_m,n,r определяется вычислением сдвигов базисной МП при ее децимации для получения суммируемых последовательностей в соответствии с индексами децимации I_di. Практическая значимость алгоритма заключается в уменьшении числа вычислительных операций, которое определяется тем, что процедура децимации символов базисной МП по индексам, имеющим одинаковое распределение цифр на позициях p-го представления, начинается с одинаковых начальных сдвигов МП.

Для различных значений параметров p, m, n и r определены векторы индексов децимации А_m,n,r и сдвигов C_m,n,r, позволяющие синтезировать ГМВП по символам базисной МП.

Полученные результаты могут быть использованы в современных и перспективных СПЦИ с многофазными СРС, к которым предъявляются повышенные требования как по структурной скрытности, так и по корреляционным свойствам.