Раздел 2
Структурные свойства и алгоритмы синтеза во временной области совершенных
двоичных решеток
2.1. Введение, постановка задачи
Совершенными двоичными решетками (СДР) называют двумерные
последовательности-матрицы
(2.1)
имеющие идеальную двумерную периодическую автокорреляционную функцию (ДПАКФ):
(2.2)
где элементы ДПАКФ
(2.3)
Заметим, что поскольку здесь и в дальнейшем рассматриваются периодические
корреляционные функции, то все индексы при h в (2.1) и (2.3) редуцируются по
modN. В общем случае СДР могут быть прямоугольными, размера (), если , то такие
СДР называются квадратными или базовыми.
Поиску СДР или близких к ним структур посвящены многие работы [96—108].
Некоторые решетки были построены алгебраическими методами, например, с помощью
циклических разностных множеств [104]. В общем случае поиск СДР проводится
переборными методами с большими вычислительными затратами пропорциональными .
Известен алгоритм синтеза полных классов СДР [96], построение которого
выполнено с привлечением понятий алгебраических конструкций (двумерных
массивов) с равномерным энергетическим спектром в соответствующих базисах
дискретного преобразования Фурье (ДПФ) и использованием понятия негациклических
сдвигов. В настоящей работе показано, что синтез полных классов СДР, а также
синтез эквивалентных, порождающих и минимаксных классов СДР квадратных и
прямоугольных форм, можно провести без привлечения отмеченных понятий,
основываясь при этом исключительно на корреляционных и структурных свойствах во
временной области самих СДР и их прореженных решеток.
Заметим также, что в настоящее время недостаточно полно исследованы во
временной области структурные и корреляционные свойства СДР и их прореженных
решеток, которые допускали бы регулярную процедуру построения СДР заданного
порядка N и их размножения.
В связи с изложенным, в настоящем разделе поставлены следующие задачи:
Установление связи в аналитической форме между одномерными авто и
взаимокорреляционными функциями (АКФ и ВКФ) парциальных последовательностей
(строк) матрицы H и её двумерной ДПАКФ.
Построение и исследование ряда алгебраических конструкций, в частности,
уравнений локального и глобального баланса, соответственно для множеств АКФ и
ВКФ парциальных последовательностей (строк) матрицы H.
Формулировка в матричном виде необходимого и достаточного условий существования
СДР.
Исследование во временной области структурных свойств прореженных матриц для
множества СДР заданного порядка и разработка регулярных алгоритмов
рекуррентного синтеза полных классов СДР квадратной и прямоугольной форм.
Исследование структурных и корреляционных свойств эквивалентных классов
циклических СДР квадратной и прямоугольной форм.
Обоснование способа информационной модуляции на основе циклических сдвигов и
инверсий опорной СДР.
2.2. Структурные свойства СДР
Установим вначале связь в аналитическом виде между элементами ДПАКФ и
элементами одномерных периодических автокорреляционных (ПАКФ) и
взаимокорреляционных (ПВКФ) функций, которые определим следующими
соотношениями:
ПАКФ –
(2.4)
ПВКФ –
(2.5)
Заметим, что внутренняя сумма в (2.3) представляет собой либо ПАКФ, либо ПВКФ,
поэтому в общем случае связь между одномерными и двумерными корреляционными
функциями двоичных решеток, с учетом (2.4) и (2.5), определяется выражением
(2.6)
Представим теперь соотношение (2.6) в более наглядной матричной интерпретации.
Для этого обозначим через – n-ый циклический сдвиг влево i-ой вектор-строки
матрицы H, и пусть – скалярное произведение векторов a и b размерности N,
тогда
(2.7)
Из анализа (2.7) следует, что значение в точности равно следу () матрицы , где
T – оператор транспонирования, поэтому в общем случае выражение (2.7) для ДПАКФ
можно представить в виде [109— 111]
(2.8)
где – оператор циклического сдвига строк матрицы H вверх на m строк;
– оператор циклического сдвига столбцов матрицы H влево на n столбцов.
Ясно, что сдвиг вверх на m строк эквивалентен сдвигу вниз на (N-m) строк, а
сдвиг влево на n столбцов эквивалентен сдвигу вправо на (N-n) столбцов.
Непосредственно из анализа соотношения (2.8) устанавливаем свойства операторов
циклического сдвига и :
Свойство 2.2.1. Операторы и линейны и коммутативны по отношению к матрице H,
при этом их индексы редуцируются по модулю N.
Свойство 2.2.2. Транспонирование матрицы H с оператором равносильно применению
оператора к , и наоборот
. (2.9)
Свойство 2.2.3. Общее свойство транспонирования H с операторами и –
. (2.10)
Свойство 2.2.4. Основное свойство следа матрицы состоит в следующей цепочке
равенств для произвольных целых k1 и k2:
, (2.11)
действительно, в этом случае соответствующие суммы из (2.7) совпадают с
точностью до порядка следования слагаемых в этих суммах.
Установленные свойства 2.1 – 2.4 в виде соотношений (2.9 – 2.11) доказывают, по
сути, весьма важное для практики построения СДР утверждение следующей теоремы:
Теорема 2.2.1. Каждая матрица – СДР порядка N порождает класс эквивалентных
матриц – СДР путем операций циклического сдвига по строкам и столбцам и
инверсии, при этом мощность класса эквивалентных матриц
. (2.12)
Доказательство. Пусть H – СДР и ее ДПАКФ – . Построим произвольную матрицу вида
, тогда с учетом определения (2.8) и свойства 2.4 последовательно находим
что и требовалось доказать.
Таким образом, если каким-либо способом построена СДР, то тем самым, по сути,
задан класс эквивалентных СДР мощности (2.12).
Теорема 2.2.2. Если матрица H – CДР, то транспортированная матрица – тоже СДР.
Действительно, поскольку след
Теорема 2.2.3. Если матрица H – СДР п
- Київ+380960830922