Радиотехника и электроника, 2021, T. 66, № 8, стр. 810-814

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

В качестве ПСП часто используются как М‑последовательности (МП), так и последовательности, формируемые на их основе, такие как последовательности Голда, малого и большого множеств Касами [3, 6]. Основной причиной широкого применения МП является то, что данная последовательность является минимаксной, т.е. имеющей минимально возможный для бинарных кодов боковой лепесток ПАКФ. При этом ЭЛС как двоичных, так и недвоичных МП, формируемых в конечных полях GF(p^S) = GF[(p^m)ⁿ], равна l_S = S [2, 6–8].

Наряду с МП к классу минимаксных последовательностей относятся последовательности Гордона–Миллса–Велча (ГМВП). Однако ЭЛС ГМВП существенно превышает ЭЛС МП, причем в зависимости от периода выигрыш может составлять от 2 до 50 и более раз [8–10]. Данное обстоятельство определяет целесообразность применения ГМВП вместо МП в СПЦИ, в которых требуются минимаксные ПСП с повышенной структурной скрытностью.

Одним из направлений повышения эффективности функционирования СПЦИ является переход к многопозиционным сигналам, которые формируются на основе недвоичных ПСП. Вопросам разработки алгоритмов формирования и анализа корреляционных и структурных свойств недвоичных ПСП посвящено большое количество работ как в нашей стране, так и за рубежом [11–20]. В [11] разработан алгоритм формирования и проведен анализ корреляционных свойств семейства р-ичных последовательностей с небольшими значениями взаимной корреляционной функции. В [12] проведен достаточно подробный анализ состояния вопроса формирования недвоичных ПСП и систем ПСП с заданными корреляционными и структурными свойствами. В работах [13, 14] выполнен анализ свойств недвоичных последовательностей, формируемых путем децимации недвоичных МП. В [15] проведен анализ применения недвоичных последовательностей для контроля функционирования устройств декодирования помехоустойчивых кодов. В [16] разработан алгоритм формирования и выполнена оценка линейной сложности пятеричных ГМВП с периодом N = 624. В [17, 18] приведены результаты по формированию семейств недвоичных последовательностей с низкими уровнями взаимно корреляционных функций. В работах [19, 20] рассмотрены вопросы формирования и оценки корреляционных и структурных свойств ГМВП.

Для формирования недвоичных СРС с заданными характеристиками предварительно требуется определить корреляционные и структурные свойства ПСП. Для двоичных ГМВП известны выражения для ЭЛС данных последовательностей [5, 8–10]. Для недвоичных ГМВП выражения для ЭЛС в известной литературе отсутствуют.

Алгоритмы формирования троичных и пятеричных ГМВП с периодами N = 80, 728 и N = 24, 124, 624 рассмотрены в [16, 21], где приведены величины ЭЛС данных последовательностей для различных значений параметра r.

Цель статьи – получение выражений для ЭЛС недвоичных ГМВП.

Формирование недвоичных ГМВП с периодом N = p^mn – 1 осуществляется над конечными полями

Символы d_i (i = 0…N – 1) ГМВП определяются выражением [5, 9, 10]

где tr_a,b(α) – след элемента α из поля GF(p^a) в поле GF(p^b); α ∈ GF[(p^m)ⁿ] – примитивный элемент; параметр r – натуральное число, взаимно простое с порядком мультипликативной группы подполя GF(p^m), равным p^m – 1.

ЭЛС двоичных ГМВП определяется выражением [5, 8, 9]

где g(r) – количество единиц в двоичном представлении числа r в (1).

Известно, что любая двоичная ГМВП может быть представлена в виде суммы по mod 2 нескольких ПСП, формируемых на основе неприводимых проверочных полиномов h(x) степени S = mn [9, 10]. В качестве ПСП могут выступать как МП с периодом N = 2^S–1, так и последовательности с периодами, являющимися делителями периода N. Тогда выражение (2) может быть представлено в виде

где М = n^g(r) – 1 – число суммируемых двоичных последовательностей.

Важным следствием выражения (3) является то, что число суммируемых последовательностей при формировании ГМВП определяется только параметрами n и r и не зависит от параметра m.

При формировании МП функция g(r) = 1, поэтому в суммировании участвует только одна последовательность, образуемая на основании примитивного полинома степени S = mn. Параметр r в этом случае может принимать значения 1, 2, 4, …, 2^{m– 1}, для которых g(r) = 1.

При формировании ГМВП функция g(r) > 1. Добавление каждой единицы в двоичном представлении параметра r приводит к увеличению числа суммируемых последовательностей и линейной сложности формируемой ГМВП в n раз. С точки зрения структурных свойств конечных полей увеличение числа единиц при вычислении p‑сопряженных элементов для элемента α соответствует аналогичному увеличению числа переходов через границу, равную порядку мультипликативной группы подполя GF(2^m). Например, в подполе GF(2⁴) при вычислении p-сопряженных элементов для примитивного элемента α¹¹, т.е. при r = 11₁₀ = 1011₂ и g(r) – 1 = 2, наблюдается два перехода через α¹⁵:

А в подполе GF(2⁵) для примитивного элемента α¹⁵, т.е. при r = 15₁₀ = 1111₂ и g(r) – 1 = 3, наблюдается три перехода через α³¹:

Соответственно, ЭЛС ГМВП увеличивается в n² или в n³ раз по сравнению с ЭЛС МП.

Можно дать следующую интерпретацию изменения ЭЛС в зависимости от параметра r при синтезе МП и ГМВП. В силу свойства цикличности расширенное поле GF[(2^m)ⁿ], его подполе GF(2^m) и простое поле GF(2) можно представить в виде вложенных окружностей различных радиусов, пропорциональных числу элементов полей, с распределением данных элементов по окружностям. Тогда функции следа tr_a,b(α) отображаются в виде ребер, соединяющих элементы расширенного поля GF[(2^m)ⁿ] с элементами подполя GF(2^m) и далее с элементами простого поля GF(2). При формировании МП функция g(r) = 1 и ребра проходят напрямую через подполе GF(2^m), т.е.

При формировании ГМВП увеличение функции g(r) соответствует изменению значения функции следа [tr_mn,m(αⁱ)]^r элемента αⁱ в подполе GF(2^m) и вычислению функции следа в поле GF(2) для элемента, отличного от элемента tr_mn,m(αⁱ). Данное преобразование можно рассматривать как сдвиг подполя GF(2^m) относительно поля GF[(2^m)ⁿ]. Величина сдвига пропорциональна значению g(r) –1, что приводит к соответственному увеличению линейной сложности ГМВП.

В общем случае функциональная зависимость ЭЛС от параметров конечного поля имеет вид l_S = = f(p, m, n, r), где параметр r принимает значения, являющиеся взаимно простыми с порядком мультипликативной группы подполя GF(p^m), равным (p^m – 1). В отличие от выражения (2) для ЭЛС двоичных ГМВП, в котором применяется функция g(r), при решении задачи определения ЭЛС недвоичных ГМВП над конечными полями GF[(p^m)ⁿ] = = GF(p^S) используются непосредственно значения и кратности разрядов p-ичного представления параметра r.

При выводе выражения для ЭЛС недвоичных ГМВП использован подход, аналогичный двоичному случаю. Данный подход связан с определением числа переходов через границу, равную порядку мультипликативной группы подполя GF(p^m), в зависимости от структуры p-ичного представления параметра r, а именно от значений p-ичных разрядов и их кратности. Анализ проведен на основании результатов определения ЭЛС троичных и пятеричных ГМВП, полученных в [16, 21].

Формирование недвоичных ГМВП, как и в случае двоичных ГМВП, осуществляется путем суммирования нескольких ПСП с проверочными полиномами степени S = mn. В качестве ПСП могут выступать как недвоичные МП с периодом N = p^mn – 1, так и недвоичные ПСП с периодами, являющимися делителями периода N. Для заданных значений m и n величина ЭЛС двоичных и недвоичных ГМВП отличается только значением числа суммируемых последовательностей. Поэтому выражение (3) для недвоичных ГМВП принимает вид

где M_p – число суммируемых p-ичных последовательностей.

Таким образом, задача определения ЭЛС недвоичных ГМВП сводится к вычислению параметра M_p, т.е. числа суммируемых последовательностей.

При выводе выражения для ЭЛС недвоичных ГМВП анализ проведен для троичных и пятеричных последовательностей, построенных в конечных полях

т.е. для значения n = 2. Данные последовательности обладают максимальным значением ЭЛС при фиксированном значении параметра S = mn и могут быть представлены в виде матрицы размерности [(p^m – 1) × (p^m + 1)], ненулевые столбцы которой являются различными циклическими сдвигами короткой МП с периодом J = p^m – 1 [9, 10].

Сводные исходные данные для анализа ЭЛС представлены в табл. 1. Анализ показал, что число суммируемых последовательностей М_p при фиксированном значении параметра n = 2 зависит только от p-ичного представления параметра r , а именно от значений p-ичных разрядов этого представления и их кратности, и не зависит от значений параметров p и m. Например, в строках 1–3, 5, 6, 11 число М_p = 3, так как разложение параметра r содержит одну единицу и одну двойку, хотя параметры p и m, а также ЭЛС l_S ГМВП имеют различные значения. Аналогичная картина наблюдается для строк 4, 8, 9, в которых число М_p = 9, а разложение параметра r содержит одну единицу и две двойки.

Рассмотрение p-сопряженных элементов для элемента α в степени r показало, что значение каждого разряда p-ичного представления параметра r определяет число переходов через границу, равную порядку мультипликативной группы подполя GF(p^m), при вычислении очередного p‑сопряженного значения.

Например, в подполе GF(5^m) = GF(5²) при вычислении p-сопряженных элементов для элемента α¹³, т.е. при r = 13₁₀ = 23₅, наблюдаются два перехода через порядок мультипликативной группы от элемента α¹³ к элементу α^{13 × 5mod 24} = α^65mod24 = α¹⁷ и три перехода от элемента α¹⁷ обратно к элементу α^{17 × 5mod24} = α^85mod24 = α¹³. А при r = 19₁₀ = 34₅ – три и четыре перехода соответственно (табл. 1, строки 14, 15).

Для двоичных ГМВП, построенных над GF[(2^m)²], т.е. при n = 2, добавление единицы в двоичном представлении параметра r приводит к увеличению ЭЛС в два раза. Для p-ичных ГМВП, построенных над GF[(p^m)²], наличие разряда со значением 1 < i < p приводит к увеличению параметра M_p и ЭЛС l_S в (i + 1) раз. При наличии двух одинаковых разрядов увеличение будет в (i + 1)² раз, т.е. увеличение кратности разряда p-ичного представления параметра r приводит к росту ЭЛС в степенной зависимости. При отсутствии разряда, равного единице, ЭЛС уменьшается в два раза.

Таким образом, выражение для числа суммируемых последовательностей при формировании p-ичных ГМВП, построенных в конечных полях GF[(p^m)²], может быть представлено в виде произведения множителей, пропорциональных значениям и кратности разрядов p-ичного разложения параметра r

где t_i – кратность разрядов, равных i, в p-ичном представлении параметра r.

Тогда ЭЛС недвоичных ГМВП при значении параметра n = 2 определяется выражением (4) при подстановке числа суммируемых последовательностей из (5)

В качестве примера определим число суммируемых последовательностей M_p при формировании троичных ГМВП с периодом N = 3⁸–1 = 6560 для значений параметра r = 41₁₀ = 1112₃ и r = 53₁₀ = = 1222₃:

Число M_p при формировании пятеричных ГМВП с периодом N = 5⁴–1 = 624 для значений параметра r = 7₁₀ = 12₅ и r = 19₁₀ = 34₅:

где отсутствие единичных разрядов в p-ичном представлении соответствует делению на два.

Полученные результаты совпадают с приведенными в табл. 1, что подтверждает справедливость выражений (5) и (6).

Кроме того, при p = 2 и n = 2 выражение (6) переходит в (2) для ЭЛС ГМВП, так как t₁ = g(r), а выражение под знаком произведения становится равным n^g(r). Таким образом, выражение (2) для ЭЛС двоичных последовательностей является частным случаем для ЭЛС недвоичных ГМВП при n = 2.

В соответствии с выражениями (5) и (6) были получены значения числа суммируемых последовательностей M_p и, соответственно, ЭЛС l_S для троичных, пятеричных, семеричных, одиннадцатеричных и тринадцатеричных ГМВП с периодами N = 3¹⁰ – 1, N = 5⁶ – 1, N = 7⁴ – 1, N = 11⁴ – 1, N = 11⁶ – 1, N = 13⁶ – 1 для некоторых значений параметра r. Результаты вычислений представлены в табл. 2.

Таким образом, в статье получено выражение для числа суммируемых последовательностей и ЭЛС недвоичных ГМВП, формируемых в конечных полях GF[(p^m)²].

Недвоичные ГМВП могут быть использованы вместо МП при формировании недвоичных сигналов с расширенным спектром с повышенной структурной скрытностью в системах передачи цифровой информации, системах навигации и радиолокации, функционирующих в условиях радиоэлектронного противодействия.