Радиотехника и электроника, 2019, T. 64, № 2, стр. 160-167

Формирование нелинейных псевдослучайных последовательностей и их свойства

В. Б. Федоров 1*, А. И. Стариковский 1**, А. А. Парамонов 1, О. В. Тихонова 1

1 МИРЭА – Российский технологический университет
119454 Москва, просп. Вернадского, 78, Российская Федерация

* E-mail: fdorov@mail.ru
** E-mail: starikovski@mirea.ru

Поступила в редакцию 12.04.2018
После доработки 01.06.2018
Принята к публикации 11.06.2018

Полный текст (PDF)

Аннотация

Изложена основанная на теории bеnt-функций теория генератора периодических псевдослучайных двоичных В‑последовательностей. Описан алгоритм построения генератора и приведены результаты компьютерного расчета для последовательностей некоторых периодов.

ВВЕДЕНИЕ

Псевдослучайные бинарные последовательности (ПСП) находят применение во многих радиоэлектронных системах, например, в многоканальных системах передачи цифровой информации с кодовым разделением каналов (CDMA), в криптосистемах и других. Например, используются, так называемые, M-последовательности, последовательности Голда и Касами, также формируемых на основе M-последовательностей. Это все примеры линейных последовательностей, поскольку их генерация основана на сдвиговом регистре с многоотводной линейной обратной связью и не использует нелинейных преобразований.

Известны и применяются на практике также нелинейные последовательности, так называемые B-последовательности. Методы генерирования B-последовательностей тоже основаны на теории конечного поля Галуа и используют сдвиговый регистр с линейной обратной связью. Однако при формировании B-последовательности содержимое сдвигового регистра подвергается уже некоторому нелинейному преобразованию с помощь одной из так называемых максимально-нелинейных булевых функций (bent-функций).

Это позволяет реализовать генератор, способный генерировать весьма широкий класс (и даже довольно много классов) B-последовательностей, равноценных по своим свойствам, что обеспечивается наличием целого ряда свободных параметров. При этом получаемые последовательности обладают следующими весьма привлекательными свойствами [1] (детальнее об этом см. в разд. 4).

1. Взаимно-корреляционные функции (ВКФ) и уровень боковых лепестков автокорреляционной функции (АКФ) В-последовательностей не превосходит величины ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} + 1.$

2. Последовательности хорошо “сбалансированы”, т.е. разность числа нулей и единиц в каждой последовательности равна 1.

3. Легко осуществляется “перенастройка” генератора с генерирования одной последовательности на генерирование другой, а также легко осуществляется временной сдвиг генерируемой последовательности.

4. Максимальная длина ${{n}_{{{\text{э к в }}}}}$ (см. ниже) линейного эквивалентного генератора (ЛЭГ), способного генерировать такую же последовательность, при n > 4 значительно превышает число элементов памяти нелинейного генератора.

5. В-последовательности обладают высокой структурной сложностью, поэтому они трудно поддаются расшифровке и не могут быть быстро раскрыты и использованы для подавления радиосистемы.

В связи с этим практический интерес к B-последовательностям неуклонно возрастает [2, 3]. Однако по настоящее время отсутствует доступная литература, где бы подробно описывалась методика расчета генераторов B-последовательностей. И в тоже время в математическом отношении эти расчеты, основанные на теории конечного поля и теории нелинейных булевых функций, достаточно сложны и требуют подробного изложения, чтобы стать доступными более широкой аудитории, а не только специалистам-математикам.

В данной работе, в целях ликвидации указанного пробела, детально рассматривается процедура формирования B-последовательностей, излагается оригинальный алгоритм построения генератора и приводятся результаты компьютерных расчетов для значения периода последовательности $N = {{2}^{n}} - 1,$ при т.е. для $N = 15,$ $\quad255,\quad\,4095,\,\quad65\,535$ соответственно.

Степень детализации описания алгоритма, местами доведенная до уровня псевдокода, позволяет легко запрограммировать все вычисления с использованием какой-либо библиотеки, поддерживающей вычисления в конечном поле. Имеется также соответствующая авторская компьютерная программа [4].

1. ОБЩАЯ СТРУКТУРА ГЕНЕРАТОРА B-ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Рассмотрим подробно процедуру формирования В-последовательности ${{\left\{ {s[t]} \right\}}_{{t = 0,1,\quad2, \ldots }}}$ периода $N = {{2}^{n}} - 1,$ где n – длина используемого сдвигового регистра, над конечным полем Галуа 2-го порядка, $s[t] \in GF(2) = \left\{ {0,1} \right\}.$ При этом требуется, чтобы длина сдвигового регистра n была кратна 4.

Пусть $GF({{2}^{n}})$ – конечное поле Галуа порядка ${{2}^{n}}$ и α – его некоторый примитивный элемент с минимальным многочленом

${{{\text{M}}}_{n}}(x) = {{x}^{n}} + {{a}_{1}}{{x}^{{n - 1}}} + \ldots + {{a}_{{n - 1}}}x + 1,$

${{a}_{k}} \in \left\{ {0,1} \right\},$ так что $GF({{2}^{n}}) = \quad\left\{ {0,1,\quad\alpha ,{{\alpha }^{2}}, \ldots ,{{\alpha }^{{{{2}^{n}} - 2}}}} \right\}.$

Рассмотрим в $GF({{2}^{n}}),$ как в n-мерном линейном пространстве над полем $\left\{ {0,1} \right\},$ стандартный базис

(1)
${{\left\{ {{{\alpha }^{{k - 1}}}} \right\}}_{{k = 1:n}}}.$

Тогда $\forall $xGF(2n)

(2)
$x = \sum\limits_{k = 1}^n {{{x}_{k}}{{\alpha }^{{k - 1}}}} ,$
где ${{x}_{k}} \in \left\{ {0,1} \right\}$ – координаты элемента поля x в стандартном базисе.

В состав генератора В-последовательности входит n-элементный сдвиговый регистр, охваченный линейной обратной связью, соответствующей многочлену $\quad{{{\text{M}}}_{n}}(x),$ (см. рис. 1). В каждый момент дискретного времени t регистр содержит координаты какого-либо ненулевого элемента поля $x[t] = {{\alpha }^{t}} \in GF({{2}^{n}})$ в базисе (1), $t = 0,\,\,1,\,\,2 \ldots .$ Эти координаты обозначим ${\mathbf{x}} = {{\left[ {{{x}_{1}}, \ldots ,{{x}_{n}}} \right]}^{T}} \in {{\left\{ {0,1} \right\}}^{n}},$ где T символ операции транспонирования. Чтобы не загромождать обозначения, зависимость от времени t элементов этого вектора мы явно не указываем, но подразумеваем, так что ${\mathbf{x}} = {\mathbf{x}}[t].$

Рис. 1.

Структурная схема генератора В-последовательностей.

Очередной элемент генерируемой В-последовательности получается в результате применения к ${\mathbf{x}}\left[ t \right]$ некоторой нелинейной булевой функции от n переменных ${\text{F}}\,:{{\left\{ {0,1} \right\}}^{n}} \to \left\{ {0,1} \right\},$ т.е.

(3)
$s[t] = {\text{F}}\left( {{\mathbf{x}}[t]} \right),$
где ${\mathbf{x}}[t] = {{\left[ {{{x}_{1}}, \ldots ,{{x}_{n}}} \right]}^{T}} \in {{\left\{ {0,1} \right\}}^{n}}$ – текущее содержимое сдвигового регистра.

Если бы функция$\quad{\text{F(}} \cdot {\text{)}}$ была линейной, то получился бы просто генератор некоторой M-последовательности. Однако в генераторе B‑последовательностей эта функция представляет собой сумму некоторой линейной функции и композиции некоторого линейного отображения в пространство вдвое меньшей размерности и некоторой нелинейной функции, относящейся к классу так называемых bent-функций. А именно [1]

(4)
${\text{F(}}{\mathbf{x}}{\text{)}} = {\text{B}}\left( {{\mathbf{Lx}}} \right) + {{{\mathbf{\tau }}}^{T}}{\mathbf{x}},$
где ${\mathbf{L}}$ – постоянная матрица над $\left\{ {0,1} \right\}$ размера ${n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2} \times n,$ ${\mathbf{\tau }}$ –постоянный вектор-столбец длины n, с элементами из $\left\{ {0,1} \right\},$ ${\text{B:}}\,\,{{\left\{ {0,1} \right\}}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} \to \left\{ {0,1} \right\}$ – одна из bent-функций от ${n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}$ логических переменных, имеющая следующую структуру:
(5)
${\text{B(}}{\mathbf{z}}{\text{)}} = {\mathbf{z}}_{{\left( {1:{n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4}} \right)}}^{T}{{{\mathbf{z}}}_{{\left( {{n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4} + 1:{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}} \right)}}} + {\text{G}}\left( {{{{\mathbf{z}}}_{{\left( {1:{n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4}} \right)}}}} \right) + {{{\mathbf{c}}}^{T}}{\mathbf{z}}.$
Здесь ${\mathbf{z}} = {{\left[ {{{z}_{1}}, \ldots ,{{z}_{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}} \right]}^{T}},$ ${{{\mathbf{z}}}_{{\left( {1:{n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4}} \right)}}} = {{\left[ {{{z}_{1}}, \ldots ,{{z}_{{{n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4}}}}} \right]}^{T}}$ – первая половина вектора z, ${{{\mathbf{z}}}_{{\left( {{n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4} + 1:{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}} \right)}}} = {{\left[ {{{z}_{{{n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4} + 1}}}, \ldots ,{{z}_{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}} \right]}^{T}}$ – вторая его половина, ${\mathbf{c}} = {{\left[ {{{c}_{1}}, \ldots ,{{c}_{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}} \right]}^{T}} \in {{\left\{ {0,1} \right\}}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}$ – вектор-столбец произвольных параметров, ${\text{G:}}\,\,{{\left\{ {0,1} \right\}}^{{{n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4}}}} \to \left\{ {0,1} \right\}$ – произвольная нелинейная булева функция от ${n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4}$ переменных.

Bent-функции относятся к классу, так называемых, максимально нелинейных функций, т.е. функций максимально далеких от аффинных булевых функций в смысле расстояния Хемминга [5]. Вообще, по определению [1], булева функция $B{\text{:}}\,\,{{\left\{ {0,1} \right\}}^{m}} \to \left\{ {0,1} \right\}\quad$называется bent-функцией, если она имеет преобразование Фурье $\tilde {B}{\text{:}}\,\,{{\left\{ {0,1} \right\}}^{m}} \to \mathbb{R}{\text{,}}$ все ${{2}^{m}}$ значений которого по модулю равны 1; преобразование Фурье (Уолша–Адамара) для булевых функций определяется формулой

$\tilde {B}({\mathbf{\lambda }}) = {{2}^{{{{ - m} \mathord{\left/ {\vphantom {{ - m} 2}} \right. \kern-0em} 2}}}}\sum\limits_{{\mathbf{z}} \in {{{\left\{ {0,1} \right\}}}^{m}}} {{{{( - 1)}}^{{B\left( {\mathbf{z}} \right)}}}} {{( - 1)}^{{{\mathbf{z}},{\mathbf{\lambda }}}}},$
где ${\mathbf{z}},{\mathbf{\lambda }}$ – скалярное произведение в ${{\left\{ {0,1} \right\}}^{m}}$ (можно говорить также, что это есть преобразование Фурье биполярной функции ${{\left( { - 1} \right)}^{{B\left( {\mathbf{z}} \right)}}}$). Доказано [1], что все функции вида (5) являются bent-функциями. Отметим также, что bent-функции – это максимально нелинейные функции четного порядка, хотя в общем случае максимально нелинейные функции могут иметь порядок любой четности [5].

Определения основных констант алгоритма, т.е. матрицы L и вектора-столбца τ, входящих в (4), и способ их вычисления приведены в следующем разделе. Общая структура алгоритма изображена на рисунке.

Как видно из (4), при заданном минимальном многочлене ${{{\text{M}}}_{n}}\left( x \right)$ и при предварительно вычисленных основных константах L, τ, вид генерируемой B-последовательности зависит лишь от выбора нелинейной функции G(⋅) и вектора параметров ${\mathbf{c}} = {{\left[ {{{c}_{1}}, \ldots ,{{c}_{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}} \right]}^{T}}.$

Таким образом, для каждой фиксированной функции G(), получается семейство из ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}$ различных B-последовательностей. Причем, если две нелинейные функции, скажем ${{{\text{G}}}_{1}}\left( \cdot \right)$ и ${{{\text{G}}}_{2}}\left( \cdot \right),$ различаются только линейным слагаемым, то они порождают один и тот же класс В-последовательностей, что непосредственно следует из (5). Порядок выбранной нелинейной функции влияет на длину сдвигового регистра ЛЭГ, способного генерировать такую же последовательность. Эта длина равна [1] $\sum\nolimits_{k = 1}^m {C_{m}^{k}} ,$ где $m \leqslant {n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4}$ – порядок функции ${\text{G}}\left( \cdot \right),$ а максимальная длина ЛЭГ ${{n}_{{{\text{э к в }}}}}$ достигается при $m = {n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4}.$ Уровень боковых лепестков периодической АКФ и уровень периодических ВКФ любых B-последовательностей, имеют максимальные значения равные ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} + 1,$ при пиковом значении АКФ, равном $N = {{2}^{n}} - 1$ [1].

Кроме того, описываемая далее процедура вычисления основных констант $\quad{\mathbf{L}},{\mathbf{\tau }}$ имеет некоторые степени свободы (дополнительные параметры), о которых будет сказано ниже.

2. АЛГОРИТМ ПОСТРОЕНИЯ ГЕНЕРАТОРА B‑ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Согласно [1, 6], введенный ранее вектор-столбец $\quad{\mathbf{\tau }} = {{\left[ {{{\tau }_{1}}, \ldots ,{{\tau }_{n}}} \right]}^{T}}$ содержит коэффициенты линейной формы

${\text{t}}{{{\text{r}}}_{n}}\left( {\sigma x} \right) = {{{\mathbf{\tau }}}^{T}}{\mathbf{x}}$

в базисе (1), действующей из $GF({{2}^{n}})$ в $GF\left( 2 \right),$ где $\quad{\text{t}}{{{\text{r}}}_{n}}\left( z \right) = \sum\nolimits_{k = 0}^{n - 1} {{{z}^{{{{2}^{k}}}}}} $ – след соответствующего элемента поля $z \in GF({{2}^{n}}),$ $\sigma \in GF({{2}^{n}})\,\backslash \,\left\{ 0 \right\}$ = = $\{ {{\alpha }^{0}},{{\alpha }^{1}}, \ldots ,{{\alpha }^{{{{2}^{n}} - 2}}}\} $ – произвольный не равный нулю элемент поля, т.е. $\sigma = {{\alpha }^{m}},\quad$ $m = 0,\,\,\quad1, \ldots ,\quad{{2}^{n}} - 2.$

Причем, как показано в [6], ${\text{t}}{{{\text{r}}}_{n}}(\sigma {{\alpha }^{{k - 1}}})$ = = ${\text{t}}{{{\text{r}}}_{n}}({{\alpha }^{{m + k - 1}}})$ = ${\text{tr(}}{\mathbf{A}}_{\alpha }^{{k + m - 1}}{\text{)}}$, где

(6)
${{{\mathbf{A}}}_{\alpha }} = \left[ {\begin{array}{*{20}{c}} 0&0&0& \ldots &0&1 \\ 1&0&0& \ldots &0&{{{a}_{{n - 1}}}} \\ 0&1&0& \ldots &0&{\quad{{a}_{{n - 2}}}} \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0&0&0& \ldots &0&{{{a}_{2}}} \\ 0&0&0& \ldots &1&{{{a}_{1}}} \end{array}} \right]$
– матрица линейного оператора ${\text{A:}}GF({{2}^{n}}) \to $ $\quad \to GF({{2}^{n}})$ в базисе (1), действующего по формуле: $A(x) = \alpha x,$ ${\text{tr(}}{\mathbf{A}}_{\alpha }^{{k + m - 1}}{\text{)}}$ – след матрицы ${\mathbf{A}}_{\alpha }^{{k + m - 1}}.$ Таким образом, для $k = 1:n$
(7)
${{\tau }_{k}} = {\text{tr}}\left( {{\mathbf{A}}_{\alpha }^{{k + m - 1}}} \right),$
где число $m \in \left\{ {0,\quad1, \ldots ,\quad{{2}^{n}} - 2} \right\}$ – может быть выбрано произвольно.

Далее отметим, что при любом n в поле $GF({{2}^{n}}),$ как линейном пространстве над полем $\left\{ {0,1} \right\},$ определено скалярное произведение

${{\left\langle {x,y} \right\rangle }_{n}} = {\text{t}}{{{\text{r}}}_{n}}\left( {xy} \right).$

В [6] показано, что в базисе (1)

${{\left\langle {x,y} \right\rangle }_{n}} = {{{\mathbf{x}}}^{T}}{\mathbf{Ry}},$
где ${\mathbf{x}} = {{\left[ {{{x}_{1}}, \ldots ,{{x}_{n}}} \right]}^{T}},$ ${\mathbf{y}} = {{\left[ {{{y}_{1}}, \ldots ,{{y}_{n}}} \right]}^{T}}$ $ \in {{\left\{ {0,1} \right\}}^{n}}$ – координатные вектор-столбцы произвольных элементов x и y поля $GF({{2}^{n}}),$

(8)
${\mathbf{R}} = {{\left[ {{{r}_{{km}}}} \right]}_{{k,m = 1:n}}},\,\,\,\,\quad{{r}_{{km}}} = {\text{tr}}\left( {{\mathbf{A}}_{\alpha }^{{k + m - 2}}} \right).$

Далее наряду с обозначением ${{\left\langle {x,y} \right\rangle }_{n}}$ скалярного произведения в $GF({{2}^{n}})$ также будет использоваться обозначение $\left\langle {{\mathbf{x}},{\mathbf{y}}} \right\rangle = {{{\mathbf{x}}}^{T}}{\mathbf{y}}$ скалярного произведения в ${{\left\{ {0,1} \right\}}^{n}}.$

Отметим, что R не является диагональной матрицей, поэтому базис (1) не является ортогональным. В работе [1] предлагалось использовать ортогональный базис, проведя процедуру ортогонализации базиса (1). Однако процедура ортогонализации достаточно громоздкая, и мы, следуя [6], обойдемся без нее.

Перейдем к определению введенной ранее матрицы L. Согласно [1], это матрица линейного над $GF(2)$ отображения $L{\text{:}}\,\,GF({{2}^{n}}) \to {{\left\{ {0,1} \right\}}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}},$ такого, что сопряженное отображение $L*{\text{:}}\,\,{{\left\{ {0,1} \right\}}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} \to $ $ \to GF({{2}^{n}})$ имеет вид:

$L{\text{*(}}{\mathbf{y}}{\text{)}} = \hat {x}y,$
где $\hat {x} \in GF({{2}^{n}})$ – корень уравнения

(9)
${{x}^{2}} + x = w.$

В уравнении (9) $w \in GF({{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}) \subset GF({{2}^{n}})$ – произвольный параметр, удовлетворяющий условию ${\text{t}}{{{\text{r}}}_{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}(w) = 1.$ При этом $y \in GF({{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}})$ – элемент поля, которому соответствует вектор-столбец $\quad{\mathbf{y}} \in {{\left\{ {0,1} \right\}}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}$ его координат в базисе подполя $GF({{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}).$ Этот базис определим следующим образом: в $GF({{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}})$ в качестве примитивного элемента выберем, элемент $\quad\beta = {{\alpha }^{{{{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} + 1}}},$ тогда $GF({{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}})$ = = $\left\{ {0,\,\,1,\,\,\beta ,\,\,{{\beta }^{2}}, \ldots ,\,\,{{\beta }^{{{{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} - 2}}}} \right\},$ и среди перечисленных элементов подполя выберем стандартный базис

(10)
${{\left\{ {{{\beta }^{{k - 1}}}} \right\}}_{{k = 1:{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}.$

То, что линейное отображение $L{\text{*}}\left( \cdot \right)$ является сопряженным линейному отображению означает, что $\forall x \in GF({{2}^{n}}),\quad$ $\forall {\mathbf{y}} \in {{\left\{ {0,1} \right\}}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}$

$\left\langle {L(x),{\mathbf{y}}} \right\rangle = {{\left\langle {x,L{\text{*(}}{\mathbf{y}}{\text{)}}} \right\rangle }_{n}},$
где $L(x) \in {{\left\{ {0,1} \right\}}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}$ – вектор-столбец координат элемента подполя $GF({{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}})$ в базисе (10).

В матричном виде где ${\mathbf{L}}{\text{*}}$ – матрица сопряженного оператора, в которой каждый k‑ый столбец состоит из коэффициентов разложения элемента поля $\hat {x}{{\beta }^{{k - 1}}} \in GF({{2}^{n}})$ по базису (1). С учетом сказанного нетрудно показать [5], что

(11)
${\mathbf{L}} = {\mathbf{L}}{{{\text{*}}}^{T}}{\mathbf{R}}.$

Требуемые здесь коэффициенты разложения элемента поля $\hat {x}{{\beta }^{{k - 1}}} \in GF({{2}^{n}})$ по базису (1) получаются самым естественным образом. Как видно из (2), все элементы поля $GF({{2}^{n}})$ представляют собой многочлены степени не выше $n - 1$ от примитивного элемента α, и произведение (в других случаях – сложение) элементов поля есть произведение (сложение) соответствующих многочленов, вычисляемое по модулю ${{{\text{M}}}_{n}}\left( \alpha \right).$ В частности, в соответствии с этим вычисление $\hat {x}{{\beta }^{{k - 1}}}\quad$дает искомое разложение вида (2). Все сказанное в равной мере относится и ко всем другим обсуждаемым нами вычислениям в поле $GF({{2}^{n}}).$ Поэтому для компьютерной реализации рассматриваемых алгоритмов требуется использовать библиотеки программ, осуществляющих вычисления в конечном поле. Такие библиотеки содержатся во многих популярных пакетах программ, реализующих операции компьютерной алгебры.

Теперь остается только указать способ выбора параметра w уравнения (9) и метод решения самого уравнения. Найти подходящее значение параметра w можно простым перебором элементов поля $GF({{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}),$ следуя алгоритму

(12)
$\begin{gathered} w = \beta \hfill \\ {\mathbf{while}}\quad\,\,\,\,{\text{t}}{{{\text{r}}}_{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}(w) \ne 1 \hfill \\ \,\,\,\,\,\,\,\,w = w*\beta \hfill \\ {\mathbf{end}} \hfill \\ \end{gathered} $

% В результате w равно искомому значению, при котором$\quad{\text{t}}{{{\text{r}}}_{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}(w) = 1.$

При этом на каждом шаге алгоритма функция

(13)
${\text{t}}{{{\text{r}}}_{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}(w) = w + {{w}^{2}} + \ldots + {{w}^{{{{2}^{{{n \mathord{\left/ {\vphantom {n {2 - 1}}} \right. \kern-0em} {2 - 1}}}}}}}}$

вычисляется как выражение над $GF({{2}^{n}})$ описанным выше способом, поскольку $w \in GF({{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}) \subset $ $ \subset GF({{2}^{n}});$ то же относится и к строке (12) алгоритма.

При решении уравнения (9) используем метод, предложенный в [6]. Прежде всего, отметим, что, поскольку характеристика поля $GF({{2}^{n}})$ равна 2, то правая часть уравнения (9) ${\text{P(}}x{\text{)}} = {{x}^{2}} + x$ – линейный над $GF(2)$ оператор, действующий в т.е. уравнение (9) – линейное неоднородное уравнение, записанное в операторной форме. Рассмотрим сначала соответствующее однородное уравнение ${\text{P(}}x{\text{)}} = 0,$ которое в $GF({{2}^{n}})$ имеет ровно два решения: ${{x}_{{(1)}}} = 0$ и $\quad{{x}_{{(2)}}} = 1.$ Таким образом, ранг линейного оператора ${\text{P(}} \cdot {\text{)}}$ и, следовательно, ранг его матрицы P, в частности, в интересующем нас базисе (1), равен $n - 1.$ При этом из того, что $\quad{\text{P(1)}} = 0,$ следует, что первый столбец матрицы P состоит из одних нулей. Обозначим подматрицу, состоящую из остальных $n - 1$ столбцов матрицы P, и содержащую n строк, символом D. Эта подматрица имеет ранг $n - 1.$

Уравнению (9) соответствует следующее неоднородное матричное уравнение

(14)
${\mathbf{Px}} = {\mathbf{w}},$
где ${\mathbf{x}} \in {{\left\{ {0,1} \right\}}^{n}}$ – координаты искомого корня в базисе (1), ${\mathbf{w}} \in {{\left\{ {0,1} \right\}}^{n}}$ – координаты свободного члена уравнения (9) в том же базисе. Следовательно, решение уравнения (14) сводится к решению системы уравнений вида
(15)
${\mathbf{D}}{{{\mathbf{x}}}_{{\left( {2:n} \right)}}} = {\mathbf{w}},$
где ${{{\mathbf{x}}}_{{\left( {2:n} \right)}}} = {{\left[ {{{x}_{2}}, \ldots ,{{x}_{n}}} \right]}^{T}}.$ Эта система имеет единственное решение ${{{\mathbf{\hat {x}}}}_{{\left( {2:n} \right)}}} = {{\left[ {{{{\hat {x}}}_{2}}, \ldots ,{{{\hat {x}}}_{n}}} \right]}^{T}},$ которое можно найти, например, путем приведения расширенной матрицы системы (15), т.е. матрицы $\left[ {{\mathbf{D}},{\mathbf{w}}} \right],$ к ступенчатому виду и с последующим исключением неизвестных стандартным способом. Полное решение системы (14) получается на основе решения системы (15) и имеет ровно два частных решения

(16)
${\mathbf{\hat {x}}} = {{\left[ {0,{{{\hat {x}}}_{2}}, \ldots ,{{{\hat {x}}}_{n}}} \right]}^{T}},\,\,\,\,{\mathbf{\hat {x}}} = {{\left[ {1,{{{\hat {x}}}_{2}}, \ldots ,{{{\hat {x}}}_{n}}} \right]}^{T}}.$

Любое решение может быть использовано при вычислениях по формуле (11).

Остановимся теперь на способе вычисления элементов матрицы D или, что равнозначно, матрицы P, в которой первый столбец уже был определен. Очевидно, что ${\mathbf{P}} = {\mathbf{\Phi }} + {\mathbf{I}},$ где I – единичная матрица, а Φ – матрица оператора $\quad{\Phi (}x{\text{)}} = {{x}^{2}}.$ Воспользуемся разложением (2), а также учтем, что характеристика поля $GF({{2}^{n}})$ равна 2, и запишем ${{x}^{2}}$ в виде

${{x}^{2}} = {{\left( {\sum\limits_{k = 1}^n {{{x}_{k}}{{\alpha }^{{k - 1}}}} } \right)}^{2}} = \sum\limits_{k = 1}^n {{{x}_{k}}{{\alpha }^{{2\left( {k - 1} \right)}}}} .$

Следовательно, матрица Φ состоит из столбцов, каждый из которых содержит коэффициенты разложения соответствующего элемента ${{\alpha }^{{2\left( {k - 1} \right)}}}$ по базису (1), т.е. k-ый столбец матрицы $\quad{\mathbf{\Phi }}$ равен 1‑му столбцу матрицы ${\mathbf{A}}_{\alpha }^{{2\left( {k - 1} \right)}},$ причем матрица ${\mathbf{A}}_{\alpha }^{{}}$ определена формулой (6).

3. РЕЗУЛЬТАТЫ КОМПЬЮТЕРНОГО РАСЧЕТА ГЕНЕРАТОРА ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ НЕКОТОРЫХ ПЕРИОДОВ

В этом разделе приведены результаты компьютерных расчетов генератора по изложенной выше методике с помощью авторской компьютерной программы [4].

В программе для заданной длины сдвигового регистра n, или что эквивалентно, для заданного периода последовательности N и для заданного минимального многочлена ${{{\text{M}}}_{n}}(x)$ вычисляются матрица L и вектор-столбец τ. Эти параметры мы называем основными параметрами, т.к. они являются общими (одинаковыми) для всех генераторов, формирующих последовательности данного периода. Чтобы переключить генератор на формирование какой-либо другой последовательности в пределах одного класса, необходимо лишь изменить свободный векторный параметр c. А для того, чтобы переключить генератор на формирование какой-либо последовательности другого класса, требуется изменить вид нелинейной булевой функции ${\text{G(}} \cdot {\text{)}}$ (при $n = 4$ в генераторе функция ${\text{G(}} \cdot {\text{)}}$ не используется). В программе всегда используются максимально возможные степени этой функции, чтобы получить наибольшую длину ЛЭГ.

Отметим также, что при расчете основных параметров L и τ имеются некоторые степени свободы, которые для определенности всегда будут разрешаться одним и тем же способом. А именно, в формуле (7) положим $m = 0$ и из двух решений, представленных в (16), будем всегда выбирать первое. Базис (10) также определяется неоднозначно, т.е. этот базис можно было бы заменить другим, и от этого зависел бы результат, но мы остановимся на сделанном выборе. В принципе, можно было бы указанные неоднозначности в (7), (16) и (10) разрешить и как-то иначе, например, задавшись целью минимизировать число единиц в L и τ [6].

В итоге для случаев $n = 4,\quad\,\,8,\,\,\quad12,\,\,\quad16$ получены следующие результаты.

1. При $n\quad\, = 4,$ ${{{\text{M}}}_{4}}(x) = {{x}^{4}} + x + 1$ имеем

${\mathbf{L}} = \left[ {\begin{array}{*{20}{c}} 0&0&1&0 \\ 1&1&0&1 \end{array}} \right],\,\,\,\,\quad{\mathbf{\tau }} = {{\left[ {\begin{array}{*{20}{c}} 0&0&0&1 \end{array}} \right]}^{T}}.$

Весь ансамбль (класс) состоит из ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} = 4$ последовательностей (каждая из них определяется соответствующим набором двоичных коэффициентов $c = {{\left[ {{{c}_{1}},{{c}_{2}}} \right]}^{T}},$ функция ${\text{G(}} \cdot {\text{)}}$ – не используется). Сами эти последовательности (только один период) имеют вид:

$\begin{gathered} \begin{array}{*{20}{c}} 0&0&0&1&0&1&0&1&1&1&0&1&0&1&1 \end{array}, \\ \begin{array}{*{20}{c}} 1&1&0&0&0&0&1&0&0&1&0&1&1&1&1 \end{array}, \\ \begin{array}{*{20}{c}} 0&0&1&1&0&0&1&1&0&1&1&0&1&0&1 \end{array}, \\ \begin{array}{*{20}{c}} 1&1&1&0&0&1&0&0&1&1&1&0&0&0&1 \end{array}. \\ \end{gathered} $

Их период $N = {{2}^{n}} + 1 = 15,$ максимальная длина ЛЭГ ${{n}_{{{\text{э к в }}}}} = 4.$

Приведенные для $n = 4$ результаты компьютерного расчета совпадают с результатами, полученными в [6] без использования компьютерных вычислений.

2. При $n\quad\, = 8,$ ${{{\text{M}}}_{8}}(x) = {{x}^{8}} + {{x}^{4}} + {{x}^{3}} + {{x}^{2}} + 1$ имеем

${\mathbf{L}} = \left[ {\begin{array}{*{20}{c}} 0&0&1&1&0&1&0&1 \\ 0&1&1&1&0&1&0&1 \\ 0&1&0&1&0&0&0&0 \\ 1&1&0&0&0&0&1&0 \end{array}} \right],\,\,\,\,\quad{\mathbf{\tau }} = {{\left[ {\begin{array}{*{20}{c}} 0&0&0&0&0&1&0&0 \end{array}} \right]}^{T}}.$

Весь ансамбль состоит из ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} = 16$ последовательностей. Причем имеется единственная, с точностью до линейного слагаемого, нелинейная функция 2-го порядка ${\text{G}}\left( {\left[ {{{z}_{1}},{{z}_{2}}} \right]} \right) = {{z}_{1}}{{z}_{2}}.$ Период последовательностей $N = 255,$ максимальная длина ЛЭГ ${{n}_{{{\text{э к в }}}}} = 36.$

3. При $n = 12,$ ${{{\text{M}}}_{{12}}}(x) = {{x}^{{12}}} + {{x}^{6}} + {{x}^{4}} + x + 1$ имеем

$\begin{gathered} {\mathbf{L}} = \left[ {\begin{array}{*{20}{c}} 0&1&1&1&0&0&1&0&1&0&1&1 \\ 1&0&1&1&0&1&1&0&1&1&0&0 \\ 1&1&0&0&1&1&0&1&0&1&0&0 \\ 1&0&1&1&0&1&0&0&1&1&0&1 \\ 1&1&0&0&0&0&1&0&1&1&1&0 \\ 1&0&0&0&0&1&1&1&0&1&1&0 \end{array}} \right], \\ {\mathbf{\tau }} = {{\left[ {\begin{array}{*{20}{c}} 0&0&0&0&0&0&0&0&0&0&0&1 \end{array}} \right]}^{T}}. \\ \end{gathered} $

В этом случае имеется восемь ансамблей последовательностей по ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} = 64\quad$ последовательности в каждом. Каждый ансамбль определяется одной из нелинейных функций 3-го порядка вида ${\text{G}}\left( {\left[ {{{z}_{1}},{{z}_{2}},{{z}_{3}}} \right]} \right)$ = ${{z}_{1}}{{z}_{2}}{{z}_{3}} + {{g}_{1}}{{z}_{1}}{{z}_{2}} + {{g}_{2}}{{z}_{1}}{{z}_{3}} + {{g}_{3}}{{z}_{2}}{{z}_{3}},$ где ${{g}_{1}},{{g}_{2}},{{g}_{3}} \in \left\{ {0,1} \right\}$ – произвольные коэффициенты и всего имеется восемь различных комбинаций значений этих коэффициентов. Период последовательностей $N = 4095,$ максимальная длина ЛЭГ ${{n}_{{{\text{э к в }}}}} = 298.$

4. При $n = 16,$ ${{{\text{M}}}_{{12}}}(x) = {{x}^{{16}}} + {{x}^{{12}}} + {{x}^{3}} + x + 1$ имеем

$\begin{gathered} {\mathbf{L}} = \left[ {\begin{array}{*{20}{c}} 0&0&0&1&1&0&0&1&0&0&0&1&1&1&1&1 \\ 1&1&1&1&1&0&1&1&1&1&0&0&1&1&1&0 \\ 1&1&0&0&1&1&1&0&0&0&0&0&1&1&1&1 \\ 0&1&1&0&1&0&1&0&0&1&1&0&1&1&0&0 \\ 1&0&1&1&1&0&0&1&1&1&0&1&0&0&0&0 \\ 0&1&0&1&0&0&1&1&0&0&1&1&0&0&0&1 \\ 0&0&1&1&1&1&0&0&1&1&0&0&1&0&0&0 \\ 1&0&1&0&0&0&0&0&1&0&1&0&1&1&0&1 \end{array},} \right]{\;} \\ {\mathbf{\tau }} = {{\left[ {\begin{array}{*{20}{c}} 0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&1 \end{array}} \right]}^{T}}. \\ \end{gathered} $

В этом случае имеется уже 1024 ансамбля последовательностей по ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} = 256\quad$ последовательности в каждом. Каждый ансамбль определяется одной из нелинейных функций 4-го порядка вида

$\begin{gathered} {\text{G}}\left( {\left[ {{{z}_{1}},{{z}_{2}},{{z}_{3}},{{z}_{4}}} \right]} \right) = {{z}_{1}}{{z}_{2}}{{z}_{3}}{{z}_{4}} + \\ + \,\,\sum\limits_{\left\{ {{{k}_{1}}{{k}_{2}}{{k}_{3}}} \right\} \subset \left\{ {1,2,3,4} \right\}} {{{g}_{{{{k}_{1}}{{k}_{2}}{{k}_{3}}}}}{{z}_{{{{k}_{1}}}}}{{z}_{{{{k}_{2}}}}}{{z}_{{{{k}_{3}}}}}} + \sum\limits_{\left\{ {{{m}_{1}}{{m}_{2}}} \right\} \subset \left\{ {1,2,3,4} \right\}} {{{g}_{{{{m}_{1}}{{m}_{2}}}}}{{z}_{{{{m}_{1}}}}}{{z}_{{{{m}_{2}}}}}} \\ \end{gathered} $
где ${{g}_{{{{k}_{1}}{{k}_{2}}{{k}_{3}}}}},\quad{{g}_{{{{m}_{1}}{{m}_{2}}}}} \in \left\{ {0,1} \right\}$ – произвольные коэффициенты, причем суммирование в первой сумме осуществляется по всем трехэлементным подмножествам, а во второй – по всем двухэлементным подмножествам множества $\left\{ {1,2,3,4} \right\}.$ Таким образом, первая сумма дает $C_{4}^{3} = 4,$ а вторая – $C_{4}^{2} = 6,$ т.е. всего десять слагаемых с произвольными коэффициентами из {0,1}, что и дает 1024 варианта. Период последовательностей $N = 65{\kern 1pt} 535,$ максимальная длина линейного эквивалентного генератора ${{n}_{{{\text{э к в }}}}} = 2516.$

Ясно, что в общем случае при заданном n каждый ансамбль определяется одной из функций порядка ${n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}$ за вычетом ее аффинной составляющей в представлении в виде многочлена Жегалкина.

4. СРАВНИТЕЛЬНЫЙ АНАЛИЗ СВОЙСТВ B-ПОСЛЕДОВАТЕЛЬНОСТЕЙ И ЛИНЕЙНЫХ ПСП

Для сравнения в таблице 1 приведены основные характеристики B‑последовательностей, а также последовательностей Голда и Касами, которые наиболее часто используются в радиосистемах различного назначения. Как известно, последовательности Голда и Касами получаются на основе M‑последовательностей. Непосредственно сами M‑последовательности исключены из сравнения, т.к. хорошо известно, что они существенно уступают двум последним по показателю уровня их взаимной корреляции, но вполне сравнимы с ними по другим показателям.

Таблица 1.  

Сравнение свойств ПСП

Тип ПСП Длина сдвигового регистра Период ПСП Число различных ПСП заданного периода Максимальный уровень побочных пиков
АКФ и ВКФ
Максимальная длина ЛЭГ Баланс нулей и единиц на периоде
М-последовательность n ${{2}^{n}} - 1$ $\frac{{\varphi ({{2}^{n}} - 1)}}{n}\quad$ ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}$ n 1
Касами $n$ – четно ${{2}^{n}} - 1$ ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}$ ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} + 1$ $\frac{{3n}}{2}$ ${{2}^{{n/2}}} - 1$
Голд $n$ – нечетно ${{2}^{n}} - 1$ ${{2}^{n}} + 1$ ${{2}^{{\frac{{n + 1}}{2}}}} + 1$ $2n$ $1 \ldots {{2}^{{\frac{{n + 1}}{2}}}} + 1$
bent $n$ – кратно 4 ${{2}^{n}} - 1$ ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}$ ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} + 1$ $\sum\limits_{k = 1}^{{n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4}} {C_{{{n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4}}}^{k}} $ 1

Из таблицы видно, что по длине периода и максимальному уровню боковых пиков AКФ и ВКФ все сравниваемые ПСП практически эквиваленты. По числу всех различных последовательностей заданного периода класс B‑последовательностей (при фиксированной нелинейной функции ${\text{G(}} \cdot {\text{)}}$) не уступает последовательностям Касами и значительно превосходят М‑последовательности (в таблице φ(x) – функция Эйлера). По показателю баланса нулей и единиц на периоде B-последовательности эквивалентны М‑последовательностям. Но главное преимущество B-последовательностей заключается в их существенно более высокой структурной сложности, что исключительно важно, например, для проектирования криптостойких систем.

Так при $n = 12$ для B-последовательностей максимальная длина линейного эквивалентного генератора составляет 298, в то время как для последовательностей Голда – 24, а для последовательностей Касами – только 18. При этом за счет возможности произвольного (в пределах соответствующего класса функций) выбора вида нелинейной функции ${\text{G(}} \cdot {\text{)}}$ общее количество различных B-последовательностей той же длины может быть увеличено в восемь раз.

При $n = 16$ картина получается еще более впечатляющей. Для B-последовательностей максимальная длина линейного эквивалентного генератора составляет 2516, а для последовательностей Голда и Касами – 32 и 24, соответственно, при возможности увеличения общего числа В‑последовательностей той же длины в 1024 раза за счет произвольного выбора того или иного вида нелинейной функции.

ЗАКЛЮЧЕНИЕ

В статье подробно изложен алгоритм построения генератора B‑последовательностей, который заключается в вычислении, при заданном минимальном многочлене ${{{\text{M}}}_{n}}(x),$ матрицы L и вектора τ. Генератор способен генерировать, в общем случае, целый набор ансамблей (классов) B‑последовательностей. Вид выбранной нелинейной функции ${\text{G}}\left( {\left[ {{{z}_{1}}, \ldots ,{{z}_{{{n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0em} 4}}}}} \right]} \right)$ определяет некоторый класс генерируемых B-последовательностей, при этом степени свободы генератора внутри выбранного класса определяются наличием произвольно устанавливаемых коэффициентов ${\mathbf{c}} = {{\left[ {{{c}_{1}}, \ldots ,{{c}_{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}}} \right]}^{T}}.$ Наличие указанных параметров позволяет практически мгновенно переключать генератор на генерирование новой последовательности.

Сравнительный анализ свойств линейных и нелинейных ПСП показывает, что B-последовательности являются серьезной альтернативой линейным ПСП для использования в широкополосных и сверхширокополосных системах, например, в системах связи, основанных на технологии CDMA, и в системах с повышенными требованиями к криптостойкости.

Список литературы

  1. Olsen J.D., Scholtz R.A., Welch L.R. // IEEE Trans. 1982. V. IT-28. № 6. P. 858.

  2. Токарева Н.Н. Нелинейные булевы функции: бент-функции и их обобщения. Saarbrucken: LAP LAMBERT Academic Publishing, 2011.

  3. Cheng F., Hua J., Zhu J. et al. // 2010 WASE Int. Conf. on Information Engineering. Beidaihe. 14–15 Aug. N.Y.: IEEE, 2010. V. 3. P. 328.

  4. Федоров В.Б., Стариковский А.И., Парамонов А.А., Куликов Г.В. Библиотека функций для системы MATLAB для расчета параметров нелинейного генератора псевдослучайных последовательностей и генерации таких последовательностей. Свидетельство о гос. рег. программы для ЭВМ № 2012611440. Реестр программ для ЭВМ 07.02.2012 г.

  5. Мак-Вильямс Ф.Дж., Слоен Н.А. Теория кодов, исправляющих ошибки. М.: Связь, 1977.

  6. Артамкин И.В., Стариковский А.И. // Изв. вузов СССР. Радиоэлектроника. 1986. Т. 29. № 9. С. 46.

Дополнительные материалы отсутствуют.