Обобщенные унимодулярные дельта-коррелированные последовательности тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Шорин, Виталий Владимирович

• Шорин, Виталий Владимирович
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Шорин, Виталий Владимирович

Введение

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

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

1.1 Основные понятия и определения

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

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

1.4 Классификация последовательностей длины п = р\р2 . рт, где pi — различные простые числа.

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

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

1.5.2 Случай п = p2m+1, р — простое.

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

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

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

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

2.4 Обобщенная конструкция May для п = sm2.

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

2.6 Конструкции Габидулина для п = ps.

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

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

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

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

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

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

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

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

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

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

3.2 Последовательности длины п = Р\Р2> Pi,P2 ~ простые

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

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

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

3.2.5 Случай Р\,Р2 > 3, Pi,P2 = 3 mod 4.

3.2.6 Другие случаи

3.3 Последовательности длины ps.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6.2 Индексная группа — GF{ps)

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

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

6.3 Индексная группа — GF(prn2) х ЪртГ.

Введение диссертации (часть автореферата) на тему «Обобщенные унимодулярные дельта-коррелированные последовательности»

Последовательности (или дискретные сигналы) с определенными структурными свойствами известны с середины 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- Таким образом, задача нахождения новых унимодулярных дельта-коррелированных последовательностей снова подразделяется на две: какие существуют последовательности длины, равной степени простого числа, и существуют ли последовательности длины П\П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 тезисов докладов на научных конференциях.

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

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

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

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

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

• п — Р1Р2, где Р\,Р2 ~ любые простые, удовлетворяющие pi,p2 = 3 mod 4.

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

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

5. Предложены новые конструкции для унимодулярных обобщенно-дельта-коррелированных последовательностей, в качестве индексных групп которых выступают аддитивные группы колец GF(pk), GF(pm2) X Zpm,, Ърн х . X Zpka.

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

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

Во второй главе приводятся известные конструкции унимодулярных дельта-коррелированиых последовательностей: квадратичная последовательность для нечетных длин последовательностей, обобщенная конструкция May для последовательностей длины sm2, двухфазные и трехфазные последовательности, CRT-конструкция (по "Китайской теореме об остатках"), конструкции Габидулина для п = 2р, п = р2т ип = p2m+1.

CRT-конструкция позволяет сконструировать унимодулярную дельта-коррелированную последовательность длины ЩП2, если числа п\ и П2 взаимно просты и известны унимодулярные дельта-коррелированные последовательности длин щ и П2. Вследствие этого поиск новых последовательностей можно условно сосредоточить на последовательностях длины ps, где р — простое, s > 1, и на конструкциях для последовательностей длин щщ, несводящихся к 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 собраны результаты, относящиеся к унимодуляр-ным дельта-коррелированным последовательностям длин pip2, где pi,p2 простые. Получена полная классификация последовательностей длин 6 (раздел 3.2.2) и 15 (раздел 3.2.3). Были найдены две конструкции, одна (раздел 3.2.4) для р\ — 3, р2 = 3 mod 4, другая (раздел 3.2.5) — для Р\,Р2 = 3 mod 4, р\ ^ р2. В обоих случаях найдены полиномы с целыми коэффициентами, которым удовлетворяют координаты последовательности. В разделе 3.3 описана новая конструкция унимодуляр-ной дельта-коррелироваиной последовательности длины ps, являющаяся обобщением ранее известных конструкций Габидулина; в отличие от них, конструкция пригодна для произвольной четности значения s.

Глава 4 посвящена обобщению понятия дельта-коррелированной последовательности на случай последовательности, индексированной конечной абелевой группой. Введены функции обобщенной автокорреляции и обобщенной взаимной корреляции, описаны их свойства. Показано, что границы Велча и Сарвате справедливы и для обобщенных функций взаимной корреляции и автокорреляции. Проанализирован вопрос, какие известные преобразования эквивалентности могут быть перенесены на обобщенный случай. В разделе 4.4 представлены работы, посвященные последовательностям, индексированным конечной абелевой группой. Описанию последовательностей, индексированных конечной абеле-вой группой, в терминах обобщения понятия бент-функции посвящены работы ([32, 1, 6]), работа ([8]) посвящена дельта-п-коррелированным сигналам.

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

В разделе 5.1 описано обобщение преобразования "умножение индекса на число, взаимно простое с длиной". Так как в группе присутствует лишь одна операция (в аддитивной записи — сложение), то это преобразование не может быть использовано. Однако, можно рассмотреть все кольца, имеющие данную конечную абелеву группу в качестве аддитивной группы; в этом случае возникает преобразование эквивалентности "умножение на обратимый элемент кольца". В разделе 5.2 приведены примеры таких преобразований для аддитивных групп полей GF{23) и GF(24) в качестве индексных групп последовательностей. Замечательным свойством преобразования является количество генерируемых эквивалентных последовательностей. Так, для GF(23) преобразование даст 168 новых последовательностей, в то время как в обычном случае преобразование "умножение индекса на число, взаимно простое с длиной" дает 4 преобразования для последовательности длины 8.

Глава б содержит новые конструкции унимодулярных дельта- коррелированных последовательностей с различными индексными группами, а именно с аддитивными группами колец Z^ х . х Zрка, GF(pm2) х ЪртХ и с аддитивной группой поля GF(pk).

В Заключении сформулированы основные результаты диссертационной работы.

Заключение диссертации по теме «Теоретические основы информатики», Шорин, Виталий Владимирович

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

2. Найдена новая конструкция для унимодулярных дельта-коррелированных последовательностей длины р = 3f + 1, где р — любое простое, такое что / — целое.3. Найдена новая конструкция для унимодулярных дельта-коррелированных последовательностей длины п = Зр, где р — любое простое, удовле творяющее р = 3 mod 4.4. Найдена новая конструкция для унимодулярных дельта-коррелированных последовательностей длины п = piP2, где pi,p2 — любые простые, удовлетворяющие pi^2 = 3 mod 4.5. Найдена новая конструкция для унимодулярных дельта - коррели рованных последовательностей длины п = р^, являющаяся обобще нием двух ранее известных, и подходящая для любой четности s.6. Предложено новое структурное свойство: функция периодической автокорреляции последовательностей, индексированных конечной абелевой группой

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

8. Предложено новое преобразование эквивалентности, определяемое при помопщ любых колец, имеющих в качестве аддитивной груп пы конечную абелеву группу, индексируюп1ую последовательность.Данное преобразование эквивалентности задает существенно боль шее количество эквивалентных последовательностей, по сравнению с ранее известными преобразованиями эквивалентности.9. Предложено новое преобразование эквивалентности для последова тельностей, индексированных аддитивной группой поля GF{p^).10. Предложены новые конструкции для унимодулярных обобщенно дельта-коррелированных последовательностей, в качестве индекс ных групп которых выступают аддитивные группы колец GF{f^^) X Zpmi, GF{p^), Zyti X . . . X Zpfc„.

Список литературы диссертационного исследования кандидат физико-математических наук Шорин, Виталий Владимирович, 2003 год

1. А.С.Амбросимов Свойства бент-функций q-значной логики над конечными полями / / Дискретная Математика 1994, б, выпуск 3, стр. 50-60.

2. Ван дер Варден Б.Л. Алгебра / / М.: Наука. 1976.

3. Габидулин Э.М., Шорин В.В. Последовательности с нулевой автокорреляцией, определенной на кольце, / / Электронный журнал "Исследовано в России", 3194, 2011-2040, 2003. http://zhurnal.ape.relarn.ru/articles/2003/167.pdf

4. Габидулин Э.М., Шорин В.В. Новые последовательности с нулевой корреляцией, / / Пробл. передачи информации. 2002. Т.38. Вып. 4. 10-23.

5. Кокс Д., ЛиттлДою., О'Ши Д. Идеалы, Многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры// М.: Мир. 2000.

6. О.А.Логачев, А.А.Сальников, В.В.Ященко Бент-функции на конечной абелевой группе / / Дискретная математика 1997, 9, выпуск 4, стр. 3-20.

7. О.А.Логачев, В.В.Ященко Коды типа Рида-Маллера на конечной абелевой группе / / Школа-семинар "Синтез и сложность управляющих систем", Нижний Новгород, 1996.

8. Малоземов В.Н., Цветков К.Ю. Об оптимальных парах сигнал-фильтр / / Проблемы передачи информации, 2003. Т.39. Вып. 2. 63-74.

9. Прасолов В.В. Многочлены / / М.: МЦНМО. 2001.

10. Эдварде Г. Последняя теорема Ферма. / / М.: Мир. 1977. И. АШор W.O. Complex sequences with low periodic correlationw / / IEEE Trans. Inform. Theory, vol. IT-26(3), pp. 350-354, May 1980.

11. Cadet С Recent Results on Bent Functions// Proceedings of ICC'97 (International Conference on Combinatorics, Information Theory and Statistics).

12. Carlet C , Dubuc S., "On generalized bent and q-ary perfect nonlinear functions," in Finite fields and Apphcations (5th International Conference on Finite Fields), pages 81-94. Springer-Verlag, 2001.

13. Chu D. C. Polyphase Codes with Good Periodic Correlation Properties / / IEEE Trans. Inform. Theory, vol. IT-18, pp. 1487-1494, 1990.

14. Fan P., Darnell M. Sequences Design for Coramunicational Applications / / RSP Ltd, Taunton, Somerset, England, 1996.

15. Frank R.L. Comments on Polyphase Codes with Good Periodic Correlation Properties / / IEEE Trans. Inform. Theory, vol. IT-19, pp. 244, 1973.

16. Frank R.L. Polyphase Codes with Good Nonperiodic Correlation Properties / / IEEE Trans. Inform. Theory. 1963. V. IT-9. P. 43-45.

17. Frank R.L., Zadoff S.A. Phase Shift Pulse Codes with Good Periodic Correlation Properties / / IEEE Trans. Inform. Theory, vol. IT-8, pp. 381-382, 1962.

18. Gabidulin E.M. On Classification of Sequences with the Perfect Periodic Auto- Correlation Function / / Proc. third Int. Colloquium on Coding Theory. Dilijan, 1990. Yerevan, 1991. P. 24-30.

19. Gabidulin E.M. A Family of PSK Sequences with the Perfect Periodic Autocorrelation Function / / Proc. 5th Soviet-Swedish Workshop on Information Theory, January 1992, Moscow, USSR, P. 69-72.

20. Gabidulin E.M. Further Results on PSK-Sequences with the Perfect Periodic Autocorrelation Function / / B. Honary, M. Darnell, P. Farrell (Eds), COOMUNICATION THEORY AND APPLICATIONS I, pp. 171-176, HW Communications Ltd. 1993.

21. Gabidulin E.M. There Are Only Finitely Many Perfect Auto-Correlation Polyphase Sequences of Prime Length / / Proc. of the 1994 IEEE Int. Symp. on Inform. Theory. Trondheim, Norway, 1994. P.282.

22. Gabidulin E.M. New perfect sequences of length 2p, / / Proc. of the Sixth International Workshop on Algebraic and Combinatorial Coding Theory, Pskov, Russia, pp. 119-122, 1998.

23. Gabidulin E.M., Shorin V. V. New families of unimodular perfect sequences of prime length based on Gaussian periods, / / Proc. 2002'IEEE Int. Symp. Inform. Theory, .Tune 30 - July 05, 2002, p.68, Lausanne, Switzerland.

24. Gabidulin E.M., Shorin V.V. New families of unimodular perfect sequences of non- prime length, / / Proc. of the Eighth International Workshop on Algebraic and Combinatorial Coding Theory, Tsarskoe Selo, Russia, September 8-14, 2002.

25. Gabidulin E.M., Shorin V.V. Perfect sequences of length 3j9, / / Proc. 2003'IEEE Int. Symp. Inform. Theory, June 30 - July 04 2003, Yokohama, Japan.

26. Popovic D.M. Generalized Chirp-like Polyphase Sequences with Optimal Correlation Properties / / IEEE Trans. Inform. Theory, vol. IT-38, pp. 1406-1409, 1992.

27. Rothaus O.S. On 'Ъent" functions / / Journal of Combinatorial Theory, Series A 20, pp. 300-305, 1976.