Радиотехника и электроника, 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
Аннотация
Изложена основанная на теории 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}}$ и α – его некоторый примитивный элемент с минимальным многочленом
${{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\},$ стандартный базис
Тогда $\forall $x ∈ GF(2n)
где ${{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].$
Очередной элемент генерируемой В-последовательности получается в результате применения к ${\mathbf{x}}\left[ t \right]$ некоторой нелинейной булевой функции от n переменных ${\text{F}}\,:{{\left\{ {0,1} \right\}}^{n}} \to \left\{ {0,1} \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}},$(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}}.$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; преобразование Фурье (Уолша–Адамара) для булевых функций определяется формулой
Определения основных констант алгоритма, т.е. матрицы 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}}$ содержит коэффициенты линейной формы
в базисе (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]$Далее отметим, что при любом n в поле $GF({{2}^{n}}),$ как линейном пространстве над полем $\left\{ {0,1} \right\},$ определено скалярное произведение
В [6] показано, что в базисе (1)
где ${\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}})$ имеет вид:
где $\hat {x} \in GF({{2}^{n}})$ – корень уравненияВ уравнении (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}}}}$
В матричном виде где ${\mathbf{L}}{\text{*}}$ – матрица сопряженного оператора, в которой каждый k‑ый столбец состоит из коэффициентов разложения элемента поля $\hat {x}{{\beta }^{{k - 1}}} \in GF({{2}^{n}})$ по базису (1). С учетом сказанного нетрудно показать [5], что
Требуемые здесь коэффициенты разложения элемента поля $\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) соответствует следующее неоднородное матричное уравнение
где ${\mathbf{x}} \in {{\left\{ {0,1} \right\}}^{n}}$ – координаты искомого корня в базисе (1), ${\mathbf{w}} \in {{\left\{ {0,1} \right\}}^{n}}$ – координаты свободного члена уравнения (9) в том же базисе. Следовательно, решение уравнения (14) сводится к решению системы уравнений вида где ${{{\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}}$ в виде
Следовательно, матрица Φ состоит из столбцов, каждый из которых содержит коэффициенты разложения соответствующего элемента ${{\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$ имеем
Весь ансамбль (класс) состоит из ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} = 4$ последовательностей (каждая из них определяется соответствующим набором двоичных коэффициентов $c = {{\left[ {{{c}_{1}},{{c}_{2}}} \right]}^{T}},$ функция ${\text{G(}} \cdot {\text{)}}$ – не используется). Сами эти последовательности (только один период) имеют вид:
Их период $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$ имеем
Весь ансамбль состоит из ${{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$ имеем
В этом случае имеется восемь ансамблей последовательностей по ${{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$ имеем
В этом случае имеется уже 1024 ансамбля последовательностей по ${{2}^{{{n \mathord{\left/ {\vphantom {n 2}} \right. \kern-0em} 2}}}} = 256\quad$ последовательности в каждом. Каждый ансамбль определяется одной из нелинейных функций 4-го порядка вида
Ясно, что в общем случае при заданном 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, и в системах с повышенными требованиями к криптостойкости.
Список литературы
Olsen J.D., Scholtz R.A., Welch L.R. // IEEE Trans. 1982. V. IT-28. № 6. P. 858.
Токарева Н.Н. Нелинейные булевы функции: бент-функции и их обобщения. Saarbrucken: LAP LAMBERT Academic Publishing, 2011.
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.
Федоров В.Б., Стариковский А.И., Парамонов А.А., Куликов Г.В. Библиотека функций для системы MATLAB для расчета параметров нелинейного генератора псевдослучайных последовательностей и генерации таких последовательностей. Свидетельство о гос. рег. программы для ЭВМ № 2012611440. Реестр программ для ЭВМ 07.02.2012 г.
Мак-Вильямс Ф.Дж., Слоен Н.А. Теория кодов, исправляющих ошибки. М.: Связь, 1977.
Артамкин И.В., Стариковский А.И. // Изв. вузов СССР. Радиоэлектроника. 1986. Т. 29. № 9. С. 46.
Дополнительные материалы отсутствуют.
Инструменты
Радиотехника и электроника