О периодических автокорреляционных функциях двоичных и троичных последовательностей c периодом p ? 1 mod 6

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 669. 78. 27
В. Е. Гантмахер, В.А. Едемский
О ПЕРИОДИЧЕСКИХ АВТОКОРРЕЛЯЦИОННЫХ ФУНКЦИЯХ ДВОИЧНЫХ И ТРОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ C ПЕРИОДОМp = 1 mod 6
This article investigates the possible values of the periodic autocorrelation functions of binary and ternary periodic successions for the period p=1 mod 6. The rules of coding those successions are based on using classes of residues by module 6. The levels of periodic autocorrelation function are being determined by decomposition p to sums of squares of two integer numbers.
В данной статье исследуются возможные значения периодических автокорреляционных функций (ПАКФ) двоичных и троичных периодических последовательностей с периодом p = 1mod6. Правила кодирования (ПК) рассматриваемых последовательностей основаны на использовании классов вычетов по модулю 6. Уровни боковых лепестков (БЛ) ПАКФ определяются посредством разложения p на сумму квадратов двух целых чисел. Работа является продолжением исследований авторов [1,2].
Введение
Пусть p = 1 + 6R — простое число и p & gt- 7. Рассмотрим случай нечетного R.
В [3] показано, что если двоичные последовательности (ДП) X и Y сформированы
по ПК
1, если i е Hk,, f1, если i е H,
UX (i) = r uy (i) = r (1)
(О, если i г Hk- |0, если i г H,
то для ПАКФ X справедливо соотношение
IX (х)" S (k, к).
Аналогично, если Z = X ± Y, то
IZ (т)" S (k, k) + S (I, I) ± S (k, I) ± S (I, k), (2)
где Hk, Ht — классы степенных вычетов по mod 6- S (k, I) — спектры разности классов вычетов (СРКВ).
Следовательно, изучение ПАКФ сводится к исследованию СРКВ.
В [3], в частности, было показано, что
S (k, I) = DkS (0, (I — k)6), (3)
где D — оператор циклического сдвига Хаффмена- (I — k)6 — наименьший положительный вычет по модулю 6.
Значение stj (S (0,i) = (Si--}) совпадает с циклотомическим числом (i, j) порядка 6.
С учетом свойств СРКВ и циклотомических чисел [4] получаем следующие соотношения для нечетного R:
S (0,0) = ((0,0), (1,0), (2,0), (0,0), (1,0), (2,0)),
S (0,1) = ((0,1), (2,0), (2,1), (1,0), (0,5), (1,2)),
S (0,2) = ((0,2), (1,2), (1,0), (2,0), (1,2), (0,4)), ()
S (0,3) = ((0,3), (0,4), (0,5), (0,0), (0,1), (0,2)).
Введем некоторые обозначения.
Если p = 1mod6, то p = A2 + 3B2. Согласно [5] это представление единственно. Пусть A = 1 + 3t. Обозначим через т наименьший положительный вычет ind @ 2 по модулю 3. Тогда B =-m mod3. Циклотомические числа по mod 6 приведены в табл. 1.
Таблица 1
т = 0 т = 1 т = 2
36(0,0) 00 1 1 А 2 — 1- р р-11 — 2А
36(0,1) р +1 — 2 А + 12 В р +1 + 4 А р +1 — 2А — 12В
36(0,2) р +1 — 2 А + 12 В р +1 — 2 А + 12 В р +1 — 8 А + 12В
36(0,3) р +1 +16 А р +1 +10А — 12 В р +1 +10 А + 12В
36(0,4) р +1 — 2А — 12 В р +1 — 8А — 12 В р +1 — 2 А — 12В
36(0,5) р +1 — 2А — 12 В р +1 — 2 А + 12 В р +1 + 4 А
36(1,0) р — 5 + 4 А + 6 В р — 5 — 2А + 6 В р — 5 + 4А + 6В
36(2,0) р — 5 + 4А — 6 В р — 5 + 4А — 6 В В 6 — 2 — 5 — р
36(1,2) р +1 — 2 А р +1 + 4 А р +1 + 4 А
36(2,1) р +1 — 2 А р +1 — 8А — 12 В р +1 — 8 А + 12В
Сразу же отметим, что согласно (2), (3) и в силу симметрии ?(0,0), а также суммы? (к, I) +? (I, к) ПАКФ ДП и троичных последовательностей (ТП) относительно ПК (1) всегда будут иметь не более трех уровней БЛ. Обозначим их и1, и2, и3 для ДП и у1, у2, у3 для ТП.
ДП на основе одного класса
Рассмотрим ПАКФ ДП X, сформированную по ПК (1).
Теорема 1. ПАКФ ДП X имеет два уровня БЛ тогда и только тогда, когда р определяется одной из следующих формул:
1) р = 4(2 + 3и)2 + 27(3 + 4м)2 = 468 м 2 + 696 м + 259,
2) р = 4(2 + 3м)2 + 3 = 36 м 2 + 48 м +19,
3) р = 4(2 + 3м)2 + 3(5 + 6м)2 = 144 м 2 + 228 м + 91.
В остальных случаях три уровня БЛ.
Доказательство следует из анализа табл. 2, полученной из (4) и табл. 1.
_________________________________________________________Таблица 2
о =? т = 1 т = 2
а 6 3 8 — 1- А 2 — 1 р р-11 — 2 А
36 м² р — 5 + 4 А + 6 В р — 5 — 2А + 6 В р — 5 + 4 А + 6В
36 м³ р — 5 + 4А — 6 В р — 5 + 4А — 6 В р 1 5 1 2 А 1 6 В
Следствие. Для р, соответствующего первой формуле теоремы 1, уровни БЛ отличаются на 4 м + 3, а для двух других формул — на 1 + м.
Приведем несколько значений р, удовлетворяющих условиям теоремы 1: р = 19, 31, 103, 463, 1423… Они показывают, что рассматриваемые ДП имеют достаточно плотную сетку периодов.
ДП и ТП на основе двух классов Правила кодирования на основе двух классов:
1, если I е Нк,
Г1, если I е Нк, Н,
их 0'-) = -{ и2 (о = -!-1 если Iе Н, (5)
[0 в ост. случаях-
[0 в ост. случаях.
Теорема 2. Если |к — /| = 1, то ПАКФ ДП X, сформированной по правилу (5), имеет два уровня БЛ тогда и только тогда, когда р определяется одной из формул:
1) р = 16(1 + 3у)2 + 27(1 + 2у)2 = 252у 2 + 204у + 43,
2) р = 16(1 + 3у)2 + 3(1 + 6у)2 = 252у 2 + 132у +19.
В остальных случаях три уровня БЛ.
Доказательство следует из анализа табл. 3, полученной из (4) и табл.1. ________________________________________________________________Таблица 3
т = 0 т = 1 т = 2
3 1 4р — 20 — 2А + 12 В 4р — 20 + 4А 4р — 20 — 2А — 12В
36 м 2 4р — 20 — 2А — 12 В 4р — 20 — 2А + 12 В 4р — 20 + 4А
36 м³ 4 р — 8 + 4 А 4р — 8 — 2А — 12 В 4р — 8 — 2А + 12В
Таким образом, ДП с одноуровневой ПАКФ не существует, а два уровня возможны тогда и только тогда, когда, А = -2 ± 2 В для т = 0 или, А = 2 ± 2 В для т = 1,2. Для указанных в теореме 2 случаев уровни БЛ отличаются на 2(1 + 2у) и 4у +1 соответственно.
Ряд первых значений р из теоремы 2 — р = 19, 43, 139, 499, 643, 1291, 1459… показывает, что и в этом случае ДП имеют достаточно плотную сетку периодов.
Аналогично доказывается следующая лемма.
Лемма 1. Если к — /| = 1 и р Ф 43, то ПАКФ ТП 1 всегда имеет три уровня БЛ, заданные табл.4.
Таблица 4
т = 0 т = 1 т = 2
6 3 -12 — 6А — 24 В -12 — 12 В -12 — 6 А
36У2 -12 — 6 А + 24 В -12 — 6 А -12 + 12В
33 -12+12А -12 + 6 А + 12 В -12 + 6А — 12В
Отметим, что с ростом р разница между наименьшим и наибольшим уровнями будет существенной. Если т = 0, то для малых В уровни их и и2 близки. Если же р = 43, то мх = 1, и 2 = -3, и3 = 1.
Теорема 3. Если |к — /| = 2, то ПАКФ ДП X, определяемой ПК (5), имеет два уровня БЛ тогда и только тогда, когда р = 19 или определяется одной из следующих формул:
1) р = 16(1 + 3у)2 + 27(1 + 2у)2 = 252у 2 + 204у + 43,
2) р = 4(1 + 3у)2 + 3(5 + 6у)2 = 144у 2 + 228у + 91,
3) р = 16(1 + 3у)2 + 3(7 + 18у)2 = 1116у 2 + 852у +163.
В остальных случаях три уровня БЛ.
Доказательство. В этом случае Xх (т) определяется табл. 5.
Таблица 5
о = т т = 1 т = 2
36м^ 4р — 20 — 2А + 12 В 4р — 20 — 2А + 12 В 4р — 20 — 8А + 12В
36 м² 4 р — 8 + 4 А 4 р — 8 +10 А 4 р — 8 +10 А
36 м³ 4р — 20 — 2А — 12 В 4р — 20 — 8А — 12 В 4р — 20 — 2А — 12В
Как и в теореме 1, ДП с одноуровневой ПАКФ не существует, а при двух уровнях БЛ, А = 2 ± 2 В для т = 0 или, А = -1 ± В, ЗА = 2 ± 2 В для т = 1,2. Отсюда и получим соответствующие выражения для р.
Для р = 19 уровни БЛ и = {1,3}, а в остальных указанных случаях они отличаются на 2(1 + 2у), 4 + 5у, 4 + 5у соответственно.
Первые значения р = 43, 163, 463, 2131… показывают, что плотность сетки периодов и для этого случая мало отличается от рассматриваемых выше.
Теорема 4. Если к — /| = 2, то ПАКФ ТП 7, задаваемой ПК (5), всегда имеет два
уровня и и -2и +1 для р = 4(1 + 3и)2 + 3В2.
Доказательство следует из анализа табл.6.
Таблица 6
О =? т = 1 т = 2
6 3 -12 — 6 А -12 — 6 А -12+12А
362 -12 +12 А -12 — 6 А -12 — 6 А
33 -12 — 6 А -12 +12 А -12 — 6 А
Из таблицы видно, что уровней всегда не более двух. Заметим, что уровень БЛ в рассматриваемом случае не зависит от В.
Теорема 5. Если к — /| = 3, то ПАКФ ДП X, задаваемой ПК (5), имеет два уровня БЛ тогда и только тогда, когда
р = (4 + 6м)2 + 3 = 36 м 2 + 48 м +19.
В остальных случаях три уровня БЛ.
Теорема 5 получается аналогично предыдущим из анализа табл.7.
______________________________________________________________Таблица 7
о = т т = 1 т = 2
3 1 4р — 32 — 8А 4р — 32 + 4А — 12 В 4р — 32 + 4А + 12В
36 м² 4р — 8 + 4А + 12 В 4 р — 8 — 8 А 4 р — 8 + 4 А — 12В
36 м³ 4 р — 8 + 4 А — 12 В 4 р — 8 + 4 А + 12 В 4 р — 8 — 8А
2
Следствие. Если р = 4(2 + 3и) + 3, то уровни отличаются на 1 + 2и.
Первые значения р = 19, 67, 103, 199, 487…
Лемма 2. У ПАКФ ТП 7, определяемой правилом (5), уровни БЛ задаются табл. 8.
Таблица 8
о = т т = 1 т = 2
6 3 -12 — 24А -12 -12 А + 12 В -12 -12А — 12В
362 -12 +12 А + 12 В -12+24 В -12 + 12А + 36В
33 -12 +12 А — 12 В -12 +12А — 36 В -12 — 24В
Анализ таблицы показывает, что в этом случае ПАКФ ТП 7 всегда имеет три уровня.
ДП на основе трех классов Пусть Д П X определяется правилом кодирования:
их 0) =
1, если I е Ик, И1, Ип
(6)
[0 в ост. случаях.
Всего возможны 20 вариантов для упорядоченных троек индексов (к, I, п), из них только четыре циклически независимых:
10 ={(0,2,4), (1,3,5)},
11 = {(0,1,2), (1,2,3), (2,3,4), (3,4,5), (0,4,5), (0,1,5)},
12 = {(0,1,3), (1,2,4), (2,3,5), (0,3,4), (1,4,5), (0,2,5)},
13 = {(0,1,4), (1,2,5), (0,2,3), (1,3,4), (2,4,5), (0,3,5)}.
В первом случае ДП X соответствует множеству квадратичных вычетов (невычетов), ее ПАКФ хорошо известна.
Теорема 6. Если (к, I, п) е /1, то ПАКФ ДП X, соответствующей ПК (6), всегда имеет три уровня БЛ, при этом для
1) р = 4(3у -1) + 3(1 + 6у)2 = 144у 2 + 12у + 7,
2) р = 4(2 + 3у)2 + 3(1 + 6у)2 = 144у2 + 84у +19 уровни БЛ отличаются на единицу.
Доказательство. Достаточно изучить случай (0,1,2) без нарушения общности, т. е.
Xх (т) ?(0,0) + Б8(0,0) + Б 25(0,0) + 5(0,1) + Б35(0,1) + 5(0,2) + Б35(0,2) + б ((0,1) + Б35(0,1))
Уровни Б Л определяются табл.9.
Таблица 9
т = 0 т = 1 т = 2
361 9р — 27 + 24 В 9р — 27 9р — 27 -12А + 12В
36и2 9р — 27 9р — 27 +12А + 24 В 9р — 27 +12А — 12В
36 м³ 9р — 27 — 24 В 9р — 27 -12А — 12 В 9р — 27
Для первого столбца табл. 9 ПАКФ ДП X имеет уровни для второго и третьего
4 3
р — 3 А ± В р — 3 р — 3 А ± В
р — 3 2 В р — 3 р — 3 2В
---------, ----, ----±, а
4 4 3
4
3
4
4
— + -
3
. Следовательно, если
А±В
3
= ±1, то в последнем случае уровни БЛ будут отличаться на единицу.
Разностное множество, приведенное в [4], соответствует случаю (0, 1, 3) (табл. 10).
Таблица 10
0 = т т = 1 т = 2
361 9р — 45 + 6 В 9р — 45 — 18 В 9р — 45 + 6А — 6В
36и2 9р — 27 9р — 27 — 6А + 12 В 9р — 27 — 6А — 12В
36и3 9р — 9 — 6 В 9 р — 9 + 6 А + 6 В 9 р — 9 + 18В
В [4] определено, что множество Н0 и Их и И3 является разностным, т. е. ПАКФ ДП X имеет один уровень, тогда и только тогда, когда р = А2 + 27 и 3 е И1. Если же 3 г Их,
В±3
то уровни для данного р будут отличаться на единицу. В общем случае — на ------------------ для
6
т = 0.
Теорема 7. Если (к,І, п) є 12 или 13 и т Ф 0, то ПАКФ ДП X имеет два уровня БЛ тогда и только тогда, когда р определяется формулами:
1) р = (5 В ± 3)2 + 3В2,
2) р = (4 В ±6)2 + 3В2,
3) р=()2+3В
3(В -1)
В первом и втором случаях уровни БЛ отличаются на -----------2----, а в третьем — на
3(В -1)
4 '-
Таким образом, зная разложение р = А + 3 В, можно сразу определить уровни боковых лепестков ПАКФ, если двоичные или троичные последовательности формируются по рассмотренным выше правилам кодирования.
1. Гантмахер В. Е. // Вестник НовГУ. Сер.: Естеств. и техн. науки. 1999. № 13. С. 76−80.
2. Гантмахер В. Е., Едемский В. А. // Вестник НовГУ. Сер.: Техн. науки. 2004. № 28. С. 73−76.
3. Гантмахер В. Е. // Вестник НовГУ. Сер.: Естеств. и техн. науки. 1995. № 1. С. 81−87.
4. Холл М. Комбинаторика. М.: Мир, 1970. 423 с.
1. Михелович Ш. Х. Теория чисел. М., 1967. 336 с.

ПоказатьСвернуть
Заполнить форму текущей работой