автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Обобщенные унимодулярные дельта-коррелированные последовательности

Министерство общего и профессионального образования Российской Федерации

Московский физико-технический институт Государственный Университет

на правах рукописи

Шорин Виталий Владимирович

ОБОБЩЕННЫЕ УНИМОДУЛЯРНЫЕ ДЕЛЬТА-КОРРЕЛИРОВАННЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ

Специальность 05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Долгопрудный - 2003

Работа выполнена на кафедре радиотехники Московского физико-технического института

Научный руководитель:

доктор технических наук, профессор

Э. М. Габидулин

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

Официальные оппоненты:

доктор физ.-мат. наук В. А. Зиновьев (ИППИ РАН)

доктор физ.-мат. наук В. И. Левенштейн (ИПМ им. Келдыша РАН)

Ведущая организация:

Санкт-Петербургский Государственный Университет Аэрокосмического Приборостроения

диссертационного совета Д. 002.077.01 Института проблем передачи информации по адресу: 127994, г. Москва, ГСП-4, Б. Каретный пер., д. 19.

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации РАН.

Автореферат разослан « /3 » января 2004 г. Ученый секретарь Диссертационного совета

Защита состоится «ПО»

2004 г. в / часов на заседании

Доктор технических наук

•эОЬ^б

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

Унимодулярные дслъта-корролиропанныс последовательности, или, иначе, фазомодулированные последовательности с нулевой корреляцией, изучаются с 60-х годов XX века. Они нашли себе самое широкое применение в радиолокации, связи и измерениях. В качестве примеров использования можно привести определение параметров линейных систем, оценку канала в реальном времени, последовательности для быстрого поиска (последовательности, быстро входящие в синхронизм), измерение времени в радарах и сонарах, обработку двумерных изображений, сигналов в антеннах с фазированной решеткой, частотно-временное кодирование. Кроме того, семейства последовательностей с хорошими взаимнокорреляционными свойствами требуются для систем широкополосного кодированного разграничения множественного доступа (СБМА/БЯМА) и для широкополосных систем с плавающей частотой (И^Б).

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

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

1

«»С НАЦИОНАЛЬНАЯ ВМ6ЛМ0ТЕКА С.Я«»1р|||н

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

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

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

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

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

Для достижения поставленной цели в работе рассматриваются следующие задачи и вопросы.

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

2

«

»• »

t * «ч •,

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

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

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

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

Научная новизна

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

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

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

Научная и практическая ценность работы.

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

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

Положения, выносимые на защиту:

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

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

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

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

• п = Р\Ръ, где Pi,P2 любые простые, удовлетворяющие Pi,P2 = 3 mod 4.

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

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

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

Апробация. Основные результаты работы докладывались на научных

семинарах:

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

• ИППИ РАН,

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

• 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 ежегодных научных конференциях МФТИ;

Объем работы. Диссертация состоит из введения, б глав, заключения, 4 приложений, изложена на 150 страницах машинописного текста, включая список литературы из 39 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении сформулирована постановка задачи.

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

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

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

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

Дх(£) = £Г=о ХгХ^ц (modп) = п6(к) хо = 1, (1)

|xfc| = l, к = 1,...,п-1

заменяется системой алгебраических уравнений

Чхо = 1, (2)

I \хк\ = 1, к = 1,.. . ,п - 1.

Указанную систему можно решить аналитически, однако с практической точки зрения это возможно, если принять, что некоторые фазы (значения аргументов хг) равны между собой, и последовательность содержит не более 5 различных фаз. Для расположения этих фаз в последовательности, впервые было предложено используя гауссовы периоды.

В разделе 3.1.2 было предложено искать последовательности, используя гауссовы периоды. В разделе 3 1.3 показано, как с помощью гауссовых периодов можно ограничить количество разных фаз в последовательности. В разделе 3.1.4 описаны известные последовательности простой длины в терминах гауссовых периодов.

В разделе 3.1.5 построена новая конструкция, в том случае когда р = 3/ +1 - простая длина последовательности. Пусть 770, rji, % ~ гауссовы пе-

риоды, и их произведение равно в = щщщ — целому числу. Теория исключения приводит для каждого такого р к двум неприводимым над Z полиномам, соответственно, 12-й и 6-й степеней, унимодулярные корни которых и порождают дельта-коррелированную последовательность. Данные полиномы приведены в Приложении А. В свою очередь, возможно дальнейшее разложение этих многочленов в расширенном поле Щщ) на многочлены 4-й и 2-й степени, соответственно. Приведем эти разложения.

Для многочленов 4-й степени

+((2/ - 1)(чь + %2) - 3з)22 - {2з - (/ + 1 ){щ + т?2))* + в, (3)

+((2/ - 1)(тй + VI) ~ Зф2 - (2з - (/ + 1)0,1 + гЦ))г + я, (4) вг4 — (2в — (/ + 1)(т?2 + Чь))^ +

+((2/ - !)(»» + г,1) - 3з)г2 - (25 - (/ + !)(% + %2))г + я. (5)

Каждый многочлен имеет пару комплексно сопряженных упимодулярных корней, и пару неунимодулярных корней (последние нас не интересуют). Для многочленов 2-й степени

где целые коэффициенты А и В определяются соотношениями

Набор из уравнений 4 степени задает одно семейство последовательностей, набор из уравнений 2 степени - второе семейство. Последовательность в каждом случае будет состоять из единицы и трех разных фаз. Первое уравнение в обоих случаях задает значение первой фазы, второе — второй фазы, третье — третьей фазы. Необходим также правильный выбор между

Аг2-(В-(/-1)(1]1 + г}1^ + А, Л*2-(£-(/-!)(% +т,2))*+ Д

(6)

(7)

(8)

В = З^-Г + а.

А

0>)

сопряженными корнями уравнений, использовать ли е,1р или е~г1р. Можно привести алгоритм для выбора правильного сочетания корней, но в данном случае выбор проще осуществить перебором из 23-1 = 4 вариантов для каждого семейства.

Полная классификация последовательностей длины 13 с точностью до эквивалентности приведена в разделе 3.1.6. Существуют такие последовательности длины 13:

• 2 класса эквивалентности, по 338 эквивалентных последовательностей, представитель имеет вид

х = {1,20, го, 20, 2], 2], 21, 2о, г0, 2Ь г0}

• 2 класса эквивалентности, по 1014 эквивалентных последовательностей, представитель имеет вид

X = {1, 2о, 21, 21, 22, 2о, 22, 22, 2о, 22, 21; 2Ь 20}

• 2 класса эквивалентности, по 1352 эквивалентных последовательностей, представитель имеет вид

X — {1,2о,21,2о,22,21,21,2з,2з,2о, 22,23,22}

• 1 класс эквивалентности из 1014 эквивалентных последовательностей, Представители классов эквивалентности:

X = {1,2о,2х,24,22, 23,25, 25,23, 22, 24,21,20}

• 9 классов эквивалентности, по 2028 эквивалентных последовательностей, представитель имеет вид

х = {1>-го, 21, 24, 22, 23,25,25, 23,22, 24,21,20}

• 7 класса эквивалентности, по 4056 эквивалентных последовательностей, представитель имеет вид

X = {1, 2о, 21, 24, 22, 29, 25, 2ц, 2з, 28, 2ю, 27, 2б}

В разделе 3.2 собраны результаты, относящиеся к унимодулярным дельта-коррелированным последовательностям длин Р1Р2, где pi, р2 — простые. Получена полная классификация последовательностей длин 6 (раздел 3.2.2) и 15 (раздел 3.2.3). Были найдены две не сводящиеся к CRT конструкции:

1. Для pi = 3, Р2 — 3 mod 4 конструкция описана в разделе 3.2.4

2. Для р\,р2 = 3 mod 4, pi ф р2 конструкция описана в разделе 3.2.5.

В разделе 3.2.6 было сделано следующее предположение об общем виде последовательностей длины Р1Р2, Pi ф Pi простые.

Любая унимодулярная дельта-коррелированная последовательность длины Р1Р2 эквивалентна последовательности следующего вида:

где pi = ei/i + 1,р2 = е2/2 + 1, (Go1', • • •, ^1) и ..., G^,) - гаус-

совы циклотомические классы для pj и рг, соответственно.

В Приложении С приведены некоторые найденные последовательности, подтверждающие сделанное предположение.

В случае р\ — 3, рг = 3 mod 4 предложено искать последовательности, содержащие фазы 1,А, D,E. Эти фазы следует расположить в последовательности так:

(10)

= Xnl2, i\ = i mod 3, h = г mod p.

(П)

(12)

(13)

Фаза D последовательности будет задаваться корнями полинома

b0D4 + biD3 + b2D2 + biD + b0 = 0, 9

где bo, bi, í>2 удовлетворяют уравнениям

1.

Ш = j(p+l)2(p + 3), blip) = ^(р+1)(р + 7), Ш = |(р* + у + 13р-1).

(16) (17)

Для каждого корня djt соответствующие фазы сц.., е* будут полиномами третьей степени от с коэффициентами, являющимися рациональными функциями от р.

(р + 7)2 2(р + 7)(Зр, + 14р-1) _ 6fc 3(р + 3)(р - 5) (р + 3)»(р - 5)(р + 1) 4(Зр» + 14р-1Ь _ 2(р+1)(р + 7) з (p + 3)2(p-5)dfc 3(p + 3)(p-5)dfc U8J

8(р + I)2 р5 + Зр4 - бр3 + 54р2 + 277р - 73

ак - ~

-dk -

3(р - 5)(р - 1)(р + 3) (р - 5)(р - 1)(р + 1)(р + З)2 8(Зр2 + 14р-1) « _ 4(р+1)(р+7) ^

(í7 — 5)(р — 1)(р + З)2 3(р— 5)(р— 1)(р + 3) ^

Для случая pi,p2 = 3mod4, Р\ ^ p-i (раздел 3.2.5) найденная конструкция задает последовательности с фазами 1, A, D, Е. Пусть Гх — множество квадратичных вычетов по модулю р\, и Г2 — множество квадратичных вычетов по модулю рг- Матрица Xlít2 размера р\ х рг заполняется так:

1, íi € Гх, ¿2 6 Г2, Е, иеГьга^Га,

д »1^гь»2ег2,

, Л, г, £Г1,г2£Г2. Не сводящиеся к CRT-конструкции унимодулярные дельта-коррелированные последовательности имеют в качестве D унимодулярные корни полинома

ао D* + aiD7 + a2D6 + a3D5 + a4D4 + a3D3 + a2D2 + ах£> + ао = 0, (21)

где коэффициенты ао,ai, аг,a3: а4 " полиномы с целыми коэффициентами от переменных q\ — |(pi — 3),g2 = |(Р2 — 3), q\,Q2 (= Z. Значения фаз j4 и

(20)

Е задаются полиномами седьмой степени от (корней приведенного выше полинома) с рациональными коэффициентами от <71, ¡72 ■ Доказательство корректности решения помещено в Приложение Б.

В разделе 3.3 описана новая конструкция последовательности длины р", являющаяся обобщением ранее известных конструкций Габидулина. В отличие от них, конструкция пригодна для произвольной четности значения е. Пусть р простое, п = и к = тпх + т2, гщ > т,2 > 0. Пусть С - примитивный корень из единицы степени п. Пусть р = {р,} произвольная унимодулярная дельта-коррелированная последовательность длины рт 1-т2, а 'ф — {фг} произвольная унимодулярная последовательность длины р7™2. Пусть тг(у) — перестановка элементов из сг(у) - произвольная функция <т : 2рш2 н-► Тогда последовательность х длины п, определяемая как

Х3 = хи,с^ = С^^^^РЖ, (22)

является унимодулярной дельта-коррелированной. Здесь ] € Ъ^ представлено в виде

2 = и -р™1 +с-р™2 + и,ь € 2^2,0 е грт,-т2 (23)

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

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

новое преобразование, в то время как описание всех преобразований эквивалентности остается открытой проблемой.

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

шск! П>

где 5 — взаимно просто с длиной последовательности. Преобразование эквивалентности связано с обобщением данного преобразования эквивалентности на случай последовательностей, индексированной конечной абелс-вой группой. На группе определена только одна операция, поэтому для обобщения понадобится кольцо, не обязательно коммутативное, аддитивная группа которого является индексирующей конечной абелевой группой. Пусть группа С используется для определения функции автокорреляции, и пусть последовательность х = {.т3}, д € С, является унимодулярпой дельта-коррелированной. Пусть А — произвольное кольцо, имеющее в каг честве аддитивной группы группу С. Тогда для любого обратимого (по умножению) элемента 8 кольца А последовательность х' = {ж^}, к € <5, полученная умножением индекса справа (слева) на з,

х'н ■= (24)

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

Принципиальным моментом является то, что для такого обобщения подходит любое кольцо, и можно рассматривать группу перестановок индексов элементов последовательности, образующие которой порождены разными кольцами с общей аддитивной группой С. Такое преобразование генерирует существенно большее количество эквивалентных последовательностей по сравнению с группой перестановок на основе умножения на ненулевой элемент всего одного кольца Так, если рассмотреть п качестве индексной группы аддитивную группу поля СР(24), то при рассмотрении "умножения на обратимый элемент поля СР(24)" мы получим 15 — 1 новых

последовательностей; В то время как при рассмотрении всех возможных колец можно получить 20160 — 1 новую последовательность.

Глава 6 содержит новые конструкции последовательностей с различными индексными группами, а именно с аддитивными группами колец Zpfc, х ... х Zpk„, GF(pmi) х Zpm> и с аддитивной группой поля GF(]/).

На основе найденной в разделе 3.3 последовательности длины п = j/1, с индексной группой 2у., можно при помощи конструкции прямого произведения построить последовательность длины п = с индексной группой Zp*t х ... х Zp*,,. Эта последовательность помещена в раздел 6.1.

Пусть р - простое, к\,..., ка — положительные целые числа, п — fc-) и каждое кг представлено в виде кг = mi, 4- т.2г, т,\г > тп^ > 0. Пусть £ ~ примитивный корень из единицы степени п. Пусть рг = {рг,с}, 1 < г < о — произвольные унимодулярные дельта-коррелированные последовательности длин ртпь-пч.) 1 < i < a, ipi = {фг!У}, I < г < а, произвольные унимодулярные последовательности длин рт*'. Пусть тгг, 1 < г < а - перестановки элементов из Zp>»2,, ajv), 1 < i < а - произвольные функции а : Zpm2, I—> Zpmi,-m2,. Тогда последовательность х длины п, определяемая как

а

,=1 (25) 9 =(Л>h, ■ ■ ■ da) G Zpk! x ... x jt € Zpk,, 1 < г < a,

является упимодулярной дельта-коррелированной на группе Zp*! x ... x Zp*„. Здесь j, € Zpi, представлено в виде

jt - Ut • Pmu + С, • pm21 -I- V„ Ui, V, £ Zpm2l, c, G ZpmL-mj, , 1 < t < в. (26)

В разделе 6.2 предлагаются две конструкции последовательностей с аддитивной группой поля GF(p") в качестве индексной группы. Первая конструкция, представленная в разделе 6.2.1, является модификацией известных квадратичных бент- последовательностей.

Пусть M — матрица размера к над 14, где 14 — векторное поле над GF(p), р > 3. Последовательность дтМд mod р, g G 14 является бент-

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

А(А(М + Мт) /0. (27)

В разделе 6.2.2 описана вторая новая конструкция.

Пусть р — простое, п = р*, и к = ТП1Ч-ТП2, т,\ > т^ > 0. Пусть ( — примитивный корень из единицы степени р. Пусть р = {рг} — произвольная унимодулярная дельта-коррелированная (над Ут1-т2) последовательность длины рт1_т2, а гр = {?/>,} — произвольная унимодулярная последовательность длины р™2. Пусть функция /] : УШ2 > является перестановкой элементов из 14,2, /г(г;) — произвольная функция /2 : н-> Ут1_;а2, /(г;)

произвольная функция / : (-> СР(р). Тогда последовательность х длины п с индексной группой \4, определяемая как

= *ц,с,„ = ^м)+мм)+трефвг (28)

является унимодулярной дельта-коррелированной.

Здесь ] £ 14 представлено в виде

= («,с,«), и,« £ с € КГО1_т2. (29)

В разделе 6.3 предлагается конструкция последовательности с аддитивной группой кольца СР(рП12) х Ъ^ в качестве индексной группы. Пусть р — простое, п — р*, и к = т\ + гпг, гпх > > 0. Пусть (р примитивный корень из единицы степени р, £Р"ч — примитивный корень из единицы степени рт'. Пусть р = {/),} — произвольная унимодулярная дельта-коррелированная (над последовательность длины рт 1_г™2,

а. -ф = {фг} — произвольная унимодулярная последовательность длины р™2. Пусть функция /1 : Ърт2 н-> Ут2, является биекцией, /2{и) — произвольная функция /2 : Zpm2 2р»ч -г„2. /(у) - произвольная функция / : Хрш2 I—> 1»1. Тогда последовательность ж длины п с индексной группой ОР(рт2) х ХрШ!, определяемая как

является унимодулярной дельта-коррелированной.

Здесь j € GF{pm2) х Zpmi представлено в виде

j = (и, с, v) = (и,ер"12 + и), и е Vm2, с 6 Zpm^mj v е Zpm2. (31)

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

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

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

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

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

- п = pip2, где РьР2 — любые простые, удовлетворяющие Pi,P2 = 3 mod 4.

• Найдена универсальная конструкция для унимодулярных дельта-коррелированных последовательностей длины п — ps s > 1.

• Предложено новое структурное свойство: функция периодической автокорреляции последовательностей, индексированных конечной абе-левой группой

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

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

• Предложено новое преобразование эквивалентности для последовательностей, индексированных аддитивной группой поля GF(p*).

• Предложены новые конструкции для унимодулярных обобщенно-дельта-коррелированных последовательностей, в качестве индексных групп которых выступают аддитивные группы колец GF(pt), GF(pm') х Zp^.Zp», х ... xZpk..

Представленные в диссертации результаты опубликованы в следующих работах.

1. Габидулин Э.М., Шорин В.В. Последовательности с нулевой автокорреляцией, определенной на кольце, // Электронный журнал "Исследовано в России", 167, 2011-2041, 2003.

http://zhurn al. ape.relarn.ru/articles/2003/167. pdf

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

3. Gabiduhn Е.М, Shorin V. V. Perfect sequences of length P\P2, 11 Proc. Seventh International Symposium on Communication Theory and Applications, July 13 - 18, 2003, Ambleside, Lake District, UK.

4. Gabiduhn E.M., Shonn V.V. Perfect sequences of length 3p, // Proc. 2003'IEEE International Symposium on Information Theory, June 30 - July 04 2003, Yokohama, Japan.

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

2002. д

6. Gabidulin E.M., Shorin V. V. New families of unimodular perfect sequences of prime length based on Gaussian periods, // Proc. 2002'IEEE International Symposium on Information Theory, June 30 - July 05, 2002, p.68, Lausanne, Switzerland.

7. Шорин В.В. "Унимодулярные дельта-коррелированные последовательности составной длины"// Тезисы докладов ХЬУ ежегодной научной конференции МФТИ (Ноябрь 2002).

8. Шорин В.В. "Унимодулярные дельта-коррелированные последовательности простой длины"// Тезисы докладов ХЫУ ежегодной научной конференции МФТИ, декабрь 2001г.

РНБ Русский фонд

2005-4 50526

Подписано в печать 06.01.2004 Формат 60x88 1/16. Объем 1.5 пл. Тираж 100 экз. Заказ №5 ' Отпечатано в ООО «Соцветие красок» 119992 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. 102

Введение

Часть 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„.

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.