Обобщенные унимодулярные дельта-коррелированные последовательности Шорин Виталий Владимирович

Содержание к диссертации

Введение 6

Часть I. Унимодулярные дельта-коррелированные последо
вательности 18

1 Основы теории последовательностей 18

1. Основные понятия и определения 19

2. Преобразования эквивалентности 22

3. Классификация последовательностей длины п = р, р — простое 23

4. Классификация последовательностей длины п = pip₂ ... р_т,

где pi — различные простые числа 32

1.5 Классификация последовательностей длины п = p^s, где р

— простое число 35

5. Случай п = р^2т, р — простое 36

6. Случай n =p^2m+1, р — простое 38

2 Известные конструкции унимодулярных дельта-коррелированных
последовательностей 40

7. Квадратичная последовательность для нечетных п . . . . 41

8. Последовательности для п = р 41

9. Конструкция "прямого произведения" 42

10. Обобщенная конструкция May для п = sm² 44

11. Конструкция Габидулина для п = 2р 47

12. Конструкции Габидулина для п = p^s 50

13. Конструкция для двухфазной последовательности 51

14. Конструкция для трехфазной последовательности 57

3 Новые конструкции унимодулярных дельта-коррелированных
последовательностей 58

3.1 Последовательности простой длины 58

15. Сведение к системе алгебраических уравнений ... 59

16. Гауссовские циклотомические классы и гауссовские периоды 63

17. Последовательности, основанные на гауссовских периодах 65

18. Известные последовательности 68

19. Последовательности длины р = 3/ + 1 71

20. Последовательности длины р = 13 74

3.2 Последовательности длины п = р\Р2, Р\,Р2 — простые ... 80

21. Общие замечания 80

22. Классификация последовательностей длины б . . . 81 3.2.3 Классификация последовательностей длины 15 . . . 85

4. Случай р\ = 3, р2 = р = 3 mod 4 86

5. Случай р\,Р2 > 3, pi,P2 = 3 mod 4 90

6. Другие случаи 96

3.3 Последовательности длины p^s 97

Часть П. Обобщенные унимодулярные дельта-коррелированные
последовательности 100

4 Последовательности, индексированные конечной абеле-

вой группой 100

1. Основные определения 100

2. Дискретное преобразование Фурье 102

3. Свойства функций периодической автокорреляции и периодической взаимной корреляции 103

4. Известные результаты 108

5. Классы эквивалентности последовательностей 109

6. Унимодулярные дельта-коррелированные последовательности 112

7. Примеры последовательностей 114

5 Новые преобразования эквивалентности 116

8. Преобразования эквивалентности, индуцированные кольцевой структурой 116

9. Примеры преобразований 118

6 Новые конструкции унимодулярных дельта-коррелированных
последовательностей, определенных на кольце 121

10. Индексная группа — аддитивная группа кольца Z^ х... хЪ_рк_а 121

11. Индексная группа — GF{p^s) 122

12. Бент-последовательность 123

13. Модулированная последовательность 124

6.3 Индексная группа — GF(pⁿⁱ²) х Ъ_рт_Г 126

Заключение 129

Список обозначений 131

Литература 133

А Классификация последовательностей длин 2, 3, 4, 5, 7 138

АЛ п = 2 139

А.2 п = 3 139

А.З п = 4 139

А.4 п = 5 140

А.5 п = 7 140

В Полиномы, описывающие последовательности длины р =
3/ + 1 141

С Последовательности длины Зр 144

С.1 Шаблоны с 5 переменными 144

С.2 Шаблоны с 7 переменными 145

D Последовательности длины pip2 147

D.1 Доказательство корректности решения 147

Введение к работе

Последовательности (или дискретные сигналы) с определенными структурными свойствами известны с середины 50-х годов и нашли себе самое широкое применение в радиолокации, связи и измерениях. В качестве примеров использования можно привести определение параметров линейных систем, оценку канала в реальном времени, последовательности для быстрого поиска (последовательности, быстро входящие в синхронизм [38]), измерение времени в радарах и сонарах, обработку двумерных изображений, сигналов в антеннах с фазированной решеткой, частотно-временное кодирование. Кроме того, семейства последовательностей с хорошими взаимнокорреляционными свойствами требуются для систем широкополосного кодированного разграничения множественного доступа (CDMA/SSMA) и для широкополосных систем с плавающей частотой (FHSS).

Выяснилось, что наиболее желаемое свойство — нулевая автокорреляция или дельта-коррелированность (функция автокорреляции для всех ненулевых сдвигов) не может быть достигнута для самых простых и важ-

ных последовательностей — бинарных (или биполярных, то есть состоящих из ±1), единственным представителем является {1,1,1,-1}. Построить дельта-коррелированную последовательность, состоящую из произвольных комплексных значений, можно (напр, см. теорему 1), однако для практического использования нужны сигналы с хорошим отношением средней испускаемой энергии к максимальной (average-to-peak ratio). Оптимальными в данном отношении являются сигналы с одинаковой по модулю амплитудой, или, иначе, последовательности с одинаковыми по модулю членами. После нормировки можно говорить об унимодулярных последовательностях.

Таким образом, изучение унимодулярных дельта-коррелированных последовательностей имеет огромное теоретическое и практическое значение.

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

полной классификации неизвестно ни для каких длин последовательностей, за исключением 2, 3, 4, 5, 6, 7, 13, 15. Классификация последовательностей этих длин приведена в Приложении А.

Было установлено, что количество неэквивалентных унимодулярных дельта-коррелированных последовательностей зависит от арифметических свойств числа — длины последовательности. Так, если длина последовательности — простое число или произведение разных простых чисел, то существует конечное число неэквивалентных последовательностей. Если же длина последовательности несвободна от квадратов, то существует бесконечное количество неэквивалентных последовательностей, причем была найдена максимальная размерность пространства параметров семейства унимодулярных дельта-коррелированных последовательностей.

Важнейшее место в теории последовательностей занимает CRT-конст-рукция (от Chinese Remainder Theorem), или "конструкция прямого произведения". Она позволяет получить унимодулярную дельта-коррелированную последовательность длины П1П2, если известны уни-модулярные дельта- коррелированные последовательности взаимно простых длин щ и щ. Таким образом, задача нахождения новых унимодулярных дельта-коррелированных последовательностей снова подразделяется на две: какие существуют последовательности длины, равной степени ПРОСТОГО ЧИСЛа, И Существуют ЛИ ПОСЛеДОВатеЛЬНОСТИ ДЛИНЫ П\П2, не

сводящиеся к CRT-конструкции.

Исторически сложилось так, что свойства автокорреляции и взаимной корреляции рассматривались относительно линейных временных и пространственных сдвигов. Отчасти это было обусловлено требованиями простоты анализирующей аппаратуры. С появлением цифровой аппаратуры возможности анализа сигналов существенно возросли, появился целый ряд новых задач.

С формальной точки зрения можно описать циклический сдвиг в функциях периодической взаимной корреляции и автокорреляции как сдвиг на элемент циклической группы порядка п.

ЦЕЛЬЮ диссертационной работы является построение новых семейств унимодулярных дельта-коррелированных последовательностей и новых преобразований эквивалентности, а также изучение возможности обобщения понятия автокорреляции и взаимной корреляции для создания новых структурных свойств.

Для достижения поставленной цели в работе рассматриваются следующие ЗАДАЧИ И ВОПРОСЫ.

1. Поиск новых унимодулярных дельта-коррелированных последовательностей простой длины

2. Поиск новых унимодулярных дельта-коррелированных последовательностей длины, свободной от квадратов и неэквивалентных известной т.н. CRT-конструкции

3. Обобщение понятия автокорреляции для последовательностей, ин-

дексированных конечной абелевой группой

4. Поиск новых преобразований эквивалентности для последовательностей, индексированных конечной абелевой группой

5. Поиск новых классов эквивалентности (или неэквивалентных конструкций) для унимодулярных дельта-коррелированных последовательностей, индексированных конечной абелевой группой

Для решения поставленных задач в работе использовались МЕТОДЫ алгебры и вычислительной математики.

НАУЧНАЯ НОВИЗНА результатов, полученных в диссертации, заключается в следующем.

1. Предложен новый метод построения унимодулярных дельта-коррелированных последовательностей

2. Найдены в явном виде новые бесконечные семейства унимодулярных дельта-коррелированных последовательностей, как для длин, свободных от квадратов, так и для длин, равных степени простого.

3. Исследованы свойства обобщенных дельта-коррелированных последовательностей, в качестве индексного множества которых выступает конечная абелева группа.

Теоретическая и практическая ценность.

Построены новые семейства последовательностей, которые могут быть использованы в существующих и новых приложениях унимодулярных дельта-коррелированных последовательностей.

Рассмотрены новые структурные свойства последовательностей — обобщенная взаимная корреляция и обобщенная автокорреляция, которые могут быть использованы при анализе сигналов.

Апробация работы.

Основные результаты работы докладывались на научных семинарах:

Кафедры радиотехники МФТИ,

ИППИ РАН,

на научных конференциях:

The 7th International Symposium on Communication Theory and Applications (Ambleside, UK, 2003);

2003'IEEE International Symposium on Information Theory ISIT'03 (Pacifico Yokohama, Japan, 2003);

The Eighth International Workshop On Algebraic And Combinatorial Coding Theory ACCT-VIII (St.Petersburg, Russia, 2002)

2002'IEEE International Symposium on Information Theory ISIT'02 (Lausanne, Switzerland, 2002);

XLIV и XLV ежегодных научных конференциях МФТИ;

ПУБЛИКАЦИИ. По теме диссертации опубликовано 8 работ, из них 2 статьи в научных журналах, 6 тезисов докладов на научных конференциях.

Научные положения, выносимые на защиту.

4. Сведение общей задачи классификации унимодулярных дельта- коррелированных последовательностей к задаче классификации унимодулярных решений некоторых систем алгебраических уравнений специального вида над кольцом целых чисел

5. Найдены новые конструкции для унимодулярных дельта- коррелированных последовательностей длин, свободных от квадратов:

п = р = 3/ + 1, где р — любое простое, такое что / — целое,

п = Зр, где р — любое простое, удовлетворяющее р = 3 mod 4,

П — Р\Р2, ГДЄ Pl,P2 ~ Любые ПрОСТЫе, уДОВЛЄТВОрЯЮЩИЄ Pl,P2 =

3 mod 4.

3. Для любого целого s > 1 найдена новая конструкция, описывающая множество классов эквивалентности максимальной размерности для унимодулярных дельта-коррелированных последовательностей длины п = p^s, р — простое.

4. Исследованы свойства обобщенной функции периодической автокорреляции и обобщенной функции периодической взаимной корреляции для последовательностей, индексированных конечной абелевой

группой. Найдены новые преобразования эквивалентности. 5. Предложены новые конструкции для унимодулярных обобщен но-дельта-коррелированных последовательностей, в качестве индексных групп которых выступают аддитивные группы колец GF(p^k), GF{p^m*) х Zpm,, Ъ_рн х ... х Z_pk_a.

Работа построена следующим образом.

Первая глава посвящена изложению основ теории унимодулярных дельта-коррелированных последовательностей. Описывается дискретное преобразование Фурье и его свойства, вводится понятие преобразования эквивалентности. Приводятся существующие результаты теории последовательностей, относящиеся к подсчету количества различных классов эквивалентности унимодулярных дельта-коррелированных последовательностей. Показано, что существует только конечное число неэквивалентных унимодулярных дельта-коррелированных последовательностей в случае, если длина последовательности — простое число или произведение различных простых. Для унимодулярных дельта-коррелированных последовательностей, длина которых несвободна от квадратов, найдена максимальная размерность семейства неэквивалентых последовательностей.

Во второй главе приводятся известные конструкции унимодулярных дельта-коррелированных последовательностей: квадратичная последовательность для нечетных длин последовательностей, обобщенная кон-

струкция May для последовательностей длины sm², двухфазные и трехфазные последовательности, CRT-конструкция (по "Китайской теореме об остатках"), конструкции Габидулина для п = 2р, п = р^Ъп ип = р^2т+¹. CRT-конструкция позволяет сконструировать унимодулярную дельта-коррелированную последовательность ДЛИНЫ ЩГІ2, ЄСЛИ ЧИСЛа П\ И ГО2

взаимно просты и известны унимодулярные дельта-коррелированные последовательности длин п\ и П2. Вследствие этого поиск новых последовательностей можно условно сосредоточить на последовательностях длины p^s, где р — простое, s > 1, и на конструкциях для последовательностей длин ЩП2, несводящихся к CRT-конструкции.

В главе 3 приведены найденные конструкции. Раздел 3.1 посвящен унимодулярным дельта-коррелированным последовательностям простой длины, основанным на гауссовских периодах. В разделе 3.1.1 описан основной подход к нахождению последовательностей, состоящий в переходе к системе алгебраических уравнений, ограничении количества переменных (количества различных фаз) и решении системы методами теории исключений. В разделе 3.1.2 описаны известные свойства гауссовых циклотомических классов и гауссовых периодов. В разделе 3.1.3 показано, как с помощью гауссовых периодов можно ограничить количество разных фаз в последовательности. В разделе 3.1.4 описаны известные последовательности простой длины в терминах гауссовых периодов. В разделе 3.1.5 построена новая конструкция, в том случае когда р = 3/ + 1

простая длина последовательности. Полная классификация последовательностей длины 13 с точностью до эквивалентности приведена в разделе 3.1.6. В разделе 3.2 собраны результаты, относящиеся к унимодуляр-ным дельта-коррелированным последовательностям длин Р1Р2, где pi,P2

простые. Получена полная классификация последовательностей длин б (раздел 3.2.2) и 15 (раздел 3.2.3). Были найдены две конструкции, одна (раздел 3.2.4) для р\ = 3, р₂ = 3 mod 4, другая (раздел 3.2.5) — для pi,p2 = 3 mod 4, р\ ^ Р2- В обоих случаях найдены полиномы с целыми коэффициентами, которым удовлетворяют координаты последовательности. В разделе 3.3 описана новая конструкция унимодуляр-ной дельта-коррелированной последовательности длины p^s, являющаяся обобщением ранее известных конструкций Габидулина; в отличие от них, конструкция пригодна для произвольной четности значения s.