close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
2005
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
№34
УДК 669.78.27
В.Е.Гантмахер, В.А.Едемский
О ПЕРИОДИЧЕСКИХ АВТОКОРРЕЛЯЦИОННЫХ И ВЗАИМНОКОРРЕЛЯЦИОННЫХ ФУНКЦИЯХ ДВОИЧНЫХ И ТРОИЧНЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ C ПЕРИОДОМ p ≡ 1 (mod 6)
Новгородский государственный университет им. Ярослава Мудрого
The procedure of using cyclotomic numbers for calculation values of the periodical autocorrelation and
cross-correlation functions of the binary and ternary periodic sequences, which coding rules are based on using
classes of residues on simple module p ≡ 1 (mod6) is proposed. Levels of PACF and PCCF are defined
2
2
through A and B values in expansion p = A + 3B .
Введение
Теория спектров разностей классов вычетов по простому модулю (СРКВ) [1,2] является универсальным математическим аппаратом, позволяющим осуществлять синтез двоичных (ДП), троичных последовательностей (ТП) и их ансамблей. Одним из недостатков
применения данной теории для указанных выше целей является сложность анализа таблицы
СРКВ, зависящей от большого числа переменных.
В данной статье изучаются периодические автокорреляционные функции (ПАКФ) и
периодические взаимно-корреляционные функции (ПВКФ) ДП и ТП с периодом p = 1+ 6 R ,
правила кодирования (ПК) которых основаны на использовании классов вычетов по модулю p . Среди таких последовательностей наиболее известны последовательности Холла с
периодом p = A 2 + 27 и одноуровневой ПАКФ, обладающие относительно редкой сеткой
периодов. Для уплотнения сетки периодов полезно исследовать ДП с квазиодноуровневой
ПАКФ и синтезировать регулярные ПК для этого случая.
Кроме того, в [2] были найдены необходимые условия существования пары ДП с одноуровневой, квазиодноуровневой ПВКФ для периода p = 1 + 6 R. Вопрос о достаточности
данных условий не был решен.
Цель данной работы заключается в совершенствовании методов анализа и синтеза
ДП и ТП на основе СРКВ за счет применения циклотомических чисел [3]. Использование
циклотомических чисел создает предпосылки для нахождения не только необходимых, но и
достаточных условий для существования последовательностей с заданными рельефами
ПАКФ и ПВКФ. Работа продолжает исследования авторов, начатые в [3].
Пусть p = 1+ 6 R — простое число и p > 13 . В [3] были изучены ПАКФ ДП и ТП для
нечетного R . Здесь рассмотрим случай четного R . В [2] показано, что изучение ПАКФ
сводится к исследованию СРКВ S (0, i ).
Значения si, j
(S ( 0, i ) = {si, j }) совпадают с циклотомическими числами
( j , i ) порядка
6. С учетом свойств СРКВ и циклотомических чисел [4] получаем следующие соотношения
для четного R :
S ( 0,0 ) = (( 0,0 ), ( 0,1), ( 0,2 ), ( 0,3), ( 0,4 ), ( 0,5)),
S ( 0,1) = (( 0,1), ( 0,5), (1,2 ), (1,3), (1,4 ), (1,2 )),
S ( 0,2 ) = (( 0,2 ), (1,2 ), ( 0,4 ), (1,4 ), ( 2,4 ), (1,3)),
S ( 0,3) = (( 0,3), (1,3), (1,4 ), ( 0,3), (1,3), (1,4) ).
Введем некоторые обозначения.
47
(1)
2005
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
№34
Если p ≡ 1 mod 6, то p = A 2 + 3B 2 . Согласно [5] это представление единственно с
точностью до знака A и B . Можно показать, что A = 1 + 3t. Обозначим через т наименьший положительный вычет ind Θ 2 по модулю 3. Тогда B ≡ − m (mod 3). Циклотомические
числа шестого порядка для четного R приведены в табл.1 [6].
36( 0,0)
т=0
p − 17 − 20 A
т =1
p − 17 − 8 A + 6 B
Таблица 1
т=2
p − 17 − 8 A − 6 B
36( 0,1)
p − 5 + 4 A + 18 B
p − 5 + 4 A + 12 B
p − 5 + 4 A + 6B
36( 0,2)
p − 5 + 4 A + 6B
p − 5 + 4 A − 6B
p − 5 − 8A
36( 0,3)
p − 5 + 4A
p − 5 + 4 A − 6B
p − 5 + 4 A + 6B
36( 0,4)
p − 5 + 4 A − 6B
p − 5 − 8A
p − 5 + 4 A + 6B
36( 0,5)
p − 5 + 4 A − 18 B
p − 5 + 4 A − 6B
p − 5 + 4 A − 12 B
36(1,2)
p + 1− 2 A
p + 1 − 2 A − 6B
p + 1 − 2 A + 6B
36(1,3)
p + 1− 2 A
p + 1 − 2 A − 6B
p + 1 − 2 A − 12 B
36(1,4)
p +1− 2A
p + 1 − 2 A + 12 B
p + 1 − 2 A + 6B
36( 2,4)
p + 1 − 2A
p + 1 + 10 A + 6 B
p + 1 + 10 A − 6 B
Значения боковых лепестков (БЛ) ПАКФ ДП и ТП определяются по изложенной в [3]
методике. Выделим наиболее интересные результаты.
ДП и ТП на основе трех классов
Пусть ДП X сформирована по ПК
⎧1, если i ∈ H k , H l , H n ,
U X (i ) = ⎨
⎩0 в ост. случаях.
(2)
Всего возможно 20 вариантов упорядоченных троек индексов ( k , l , n ), которые, с учетом
циклических сдвигов можно разбить на четыре множества:
I 0 = {( 0,2,4), (1,3,5)};
I 1 = {( 0,1,2), (1,2,3), ( 2,3,4), (3,4,5), ( 0,4,5), ( 0,1,5)};
I 2 = {( 0,1,3), (1,2,4), ( 2,3,5), ( 0,3,4), (1,4,5), ( 0,2,5)};
I 3 = {(0,1,4), (1,2,5), ( 0,2,3), (1,3,4), ( 2,4,5), ( 0,3,5)}.
Рельефы БЛ ПАКФ для «троек» из одного множества будут отличаться только циклическим
сдвигом.
Согласно [3] необходимо исследовать только два варианта: (0,1,2) и (0,1,3).
Обозначим через v1 , v2 ,... неупорядоченные уровни БЛ ПАКФ и ПВКФ дискретнокодированных последовательностей (ДКП), а через λ 0 , λ1 ,... — упорядоченные по возрастанию БЛ ПАКФ ДП. Как и в [2], Δλ i = λ i − λ 0 и ΔS = maxΔλ i . Пусть γ =
ΔS
, где R0 — чисR0
ло ненулевых символов на периоде.
Лемма 1. Если ( k , l , n ) = (0,1,2), то ПАКФ ДП Х, соответствующей ПК (2), задается
48
2005
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
№34
следующей таблицей 2.
36v1
т=0
9 p − 45 + 24 B
т =1
9 p − 45
Таблица 2
т=2
9 p − 45 − 12 A + 12 B
36v2
9 p − 45
9 p − 45 + 12 A + 12 B
9 p − 45 + 12 A − 12 B
36v3
9 p − 45 − 24 B
9 p − 45 − 12 A − 12 B
9 p − 45
36v4
9 p − 9 + 24 B
9 p − 9 − 12 A + 12 B
36v5
9p −9
9p −9
9 p − 9 + 12 A + 12 B
36v6
9 p − 9 − 24 B
9 p − 9 − 12 A − 12 B
9p −9
(0,1,2)
9 p − 9 + 12 A − 12 B
Доказательство. В этом случае согласно [2]
λ X ( τ ) ⇔ S ( 0,0) + DS ( 0,0) + D 2 S ( 0,0) + S ( 0,1) + D 3 S ( 0,1) +
+ S ( 0,2) + D 3 S ( 0,2) + D(S ( 0,1) + D 3 S ( 0,1)) .
Воспользовавшись (1) и табл.1, получаем табл.2.
Из анализа табл.2 получаем следующую теорему.
Теорема 1. Если R четно и ( k , l , n ) ∈ I1 , то ДП X с периодом p = A 2 + 108u 2 и ве-
p −5
p − 5 p −1
p −1
,
± 8u ⎫⎬, τ = 1, p − 1, относительно ПК
± 4u ,
имеет ПАКФ λ X ( τ) = ⎧⎨
⎭
⎩ 4
2
4
4
(2), пик-фактор pf ≈ 2.
сом
16 u ⎞
⎛
Для малых значений u ПАКФ будет близка к одноуровневой ⎜ γ =
⎟.
p − 1⎠
⎝
Из табл.2 ясно, что для m = 1,2 при поиске ДП с квазиодноуровневой ПАКФ наиболее интересен случай, когда A + B = ±3.
Теорема 2. Если ( k , l , n ) ∈ I 1 , то ДП X
с периодом
p = 13 − 60u + 144u 2 или
p = 49 + 156u + 144u 2 и весом 3R = 6 − 15u + 72u 2 или 3R = 24 + 78u + 72u 2 имеет четырех⎧36u 2 − 15u + 1,
или
уровневую ПАКФ λ(τ) = {λ 0 , λ 0 + 1, λ 0 + 2, λ 0 + 3}, τ = 1, p − 1, с λ 0 ( τ ) = ⎨
2
⎩36u + 39u + 10
p −9
, относительно ПК (2) и пик-фактор pf ≈ 2.
4
Доказательство. Так как p = 13 − 60u + 144u 2 , то A = 1+ 6u и B = 2 − 6u для т = 1
или B = 6u − 2 для т = 2. Подставляя данные значения в табл.2, получаем утверждение
теоремы.
Таким образом, при больших значениях p ПАКФ данной последовательности близλ0 =
6 ⎞
⎛
ка к одноуровневой ⎜ γ =
⎟.
p − 1⎠
⎝
Рассмотрим ТП Z , сформированную по ПК
⎧⎪1, если i ∈ H i , H k , H n ,
U Z (i ) = ⎨0, если i = 0,
⎪⎩− 1 в ост. случаях.
Известно [7], что
49
(3)
2005
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
№34
λ Z ( τ ) = 4λ X ( τ ) − p + 2 + Δ( 0),
⎧2, если i ∈ {k , l , n},
где Δ( 0) = ⎨
⎩− 2 в ост. случаях.
Таким образом, имеет место следующая теорема.
Теорема 3. Если ( k , l , n ) ∈ I1 , то для ТП Z с периодом p = 13 − 60u + 144u 2 или
p = 49 + 156u + 144u 2 значения ПАКФ λ Z ( τ) принадлежат множеству {−5,−1, 3}, относительно ПК (3).
p,
Первые
значения
удовлетворяющие
условиям
теоремы:
p = 37,97,313,349,709,877,937,1129,1489,…., показывают, что рассматриваемые ДП и ТП
имеют достаточно плотную сетку периодов.
Лемма 2. Если ( k , l , n ) = (0,1,3), то ПАКФ ДП Х, соответствующей ПК (2), определяется следующей таблицей 3.
(0,1,3)
т=0
Таблица 3
т=2
т =1
36v1
9 p − 45 + 18 B
9 p − 45 + 12 A − 6 B
9 p − 45 + 12 A − 12 B
36v2
9 p − 45 − 12 B
9 p − 45 − 18 B
9 p − 9 − 12 A − 42 B
36v3
9 p − 9 + 6B
9p −9
9 p − 9 − 12 A + 30 B
36v4
9 p − 45 − 6 B
9 p − 45 − 12 A − 30 B
9 p − 45
36v5
9 p − 45 + 12 B
9 p − 9 − 12 A + 42 B
9 p − 9 + 18 B
36v6
9 p − 45 − 18 B
9 p − 45 + 12 A + 12 B
9 p − 45 + 12 A + 6 B
Лемма 2 доказывается аналогично лемме 1.
Из анализа табл.3 получаем следующую теорему.
Теорема 4. Если R четно и ( k , l , n ) ∈ I 2 , то ДП X с периодом p = A2 + 108u 2 и веp −5
p −5
p −1
p−5 ⎫
p −1
± 3u,
± 2u,
+ u,
− u ⎬ , τ = 1, p − 1, отноимеет ПАКФ λ X ( τ ) = ⎧⎨
⎩ 4
⎭
2
4
4
4
сительно ПК (2), пик-фактор pf ≈ 2.
сом
12 u ⎞
⎛
Для малых значений u ПАКФ будет близка к одноуровневой ⎜ γ =
⎟. В [8] ошиp − 1⎠
⎝
бочно полагают, что здесь возможны два уровня.
ПВКФ ДП, синтезированных на основе одного класса вычетов
Исследуем ПВКФ пары ДП X , Y сформированных по ПК
⎧ 1, если i ∈ H k ,
U (i ) = ⎨
⎩ 0, если i ∉ H k .
(4)
Если ДП X и Y сформированы по ПК (4) и k − l = 1,2,3, то БЛ ПВКФ rX ,Y ( τ ) с
точностью до циклического сдвига совпадают со значениями S ( 0,1), S ( 0,2), S ( 0,3) .
Теорема 5. Если ДП X и Y сформированы по ПК (4), то ПВКФ rX ,Y ( τ ) имеет один
уровень тогда и только тогда, когда p = 1 + 108u 2 и k − l = 3 . В последнем случае
rX ,Y ( τ ) =
p −1
= 3u 2 .
36
50
2005
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
№34
Теорема 5 получается из анализа табл.2.
Теорема 6. Если ДП X и Y сформированы по ПК (4), то ПВКФ rX ,Y ( τ ) имеет два
уровня тогда и только тогда, когда период p определяется одной из следующих формул:
1) p = 1 + 36u + 432u 2 , p = 13 + 72u + 108u 2 , k − l = 1,
2) p = 1 + 12u + 144u 2 , k − l = 2,
3) p = 61 + 324u + 432u 2 , p = 13 + 72u + 108u 2 , k − l = 3,
4) p = A 2 + 108u 2 , A ≠ 1, k − l = 3.
Доказательство. Рассмотрим случай, когда k − l = 1. В этом случае согласно табл.1
и формуле (1) если m = 0, то два уровня возможны тогда и только тогда, когда A = 1 ± 3B, а
если же m = 1,2, то A = 1 . Отсюда и получаем требуемые соотношения для p с учетом четности R . Другие три случая получаются аналогично.
Следствие 6.1. ДП X и Y с периодом p = 1 + 36u + 432u 2 или p = 13 + 72u + 108u 2 и
R = 6u + 72u 2
весом
R = 2 + 12u + 18u 2
или
rX ,Y (τ) = {12u 2 , 12u 2 + 6u},
τ = 1, p −1,
имеют
ΔS = 6u ,
rX ,Y (τ) = {3u 2 + u, 3u 2 + 4u + 1}, τ = 1, p − 1, ΔS = 3u + 1 , γ =
двухуровневую
1
γ=
,
12u + 1
ПВКФ
или
1
, относительно ПК (4) для
2 3u + 1
k −l =1.
Следствие 6.2. ДП X и Y с периодом p = 1 + 12u + 144u 2 и весом R = 6u + 24u 2 имеют двухуровневую ПВКФ rX ,Y ( τ) = {4u 2 , 4u 2 + 2u}, τ = 1, p − 1, ΔS = 2 u , γ =
1
, от3 4u + 1
носительно ПК (4) для k − l = 2.
Следствие 6.3. ДП X и Y с периодом p = 61 + 324u + 432u 2 или p = 13 + 72u + 108u 2
и весом
R = 10 + 54u + 72u 2
или
rX ,Y ( τ ) = {12u 2 + 7u + 1 , 12u 2 + 10u + 2},
R = 2 + 12u + 18u 2
τ = 1, p − 1,
имеют двухуровневую ПВКФ
1
ΔS = 3u + 1 ,
γ=
,
или
2 12u + 5
rX ,Y ( τ) = {3u 2 + u , 3u 2 + 4u + 1}, τ = 1, p − 1, ΔS = 3u + 1 , γ =
1
, относительно ПК (4)
2 3u + 1
для k − l = 3.
Следствие 6.4. ДП X и Y с периодом p = A 2 + 108u 2 , A ≠ 1 , и весом R имеют
p − 5 + 4 A p + 1 − 2 A⎫
A −1
A −1
, γ=
,
двухуровневую ПВКФ rX ,Y ( τ) = ⎧⎨
,
⎬ , τ = 1, p − 1, ΔS =
⎩
6
36
36 ⎭
p −1
относительно ПК (4) для k − l = 3.
В качестве примера приведем результаты расчета параметров p, R, λ 0 , ΔS , γ для пары
ДП с двухуровневой ПВКФ для периода p , определяемого первой формулой в теореме 6.
u
p
R
–1
397
66
–2
1657
276
2
1801
300
4
7057
1176
1
193
32
–3
769
128
51
3
1201
200
–4
1453
242
4
2029
338
Таблица 4
–6
–7
3469 4801
578
700
2005
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
№34
λ0
ΔS
γ
6
36
48
192
4
19
30
37
52
91
127
6
12
12
48
4
8
10
11
13
17
20
0,09 0,043 0,04 0,02 0,09 0,04 0,035 0,03 0,027 0,02 0,019
Приведенный пример показывает, что рассматриваемые ДП и ТП имеют достаточно
плотную сетку периодов.
Теоремы 5-6 являются обобщением утверждения 6.4.5 из [2], так как не содержат ограничений на A, B, k − l .
Заключение
Таким образом, предложенная в работе методика синтеза и анализа ДКП с использованием СРКВ и циклотомических чисел позволила:
1) выразить все гармоники таблицы СРКВ через две переменные, последнее существенно упрощает анализ таблицы;
2) определить уровни боковых лепестков ПАКФ и ПВКФ и свести анализ ПАКФ и
ПВКФ ДКП к анализу разложения их периода, если ДП или ТП формируются по рассмотренным выше правилам кодирования;
3) упростить методику синтеза ДКП с помощью СРКВ, изложенную в [2].
В результате применения циклотомических чисел были найдены:
1) параметры p, R, λ 0 , ΔS , γ ДП с квазиодноуровневой ПАКФ с периодом p = 6 R + 1,
весом 3R, пик-фактором pf = 2 и ΔS = 3;
2) необходимые и достаточные условия одноуровневости и двухуровневности БЛ
ПВКФ для пары ДП с периодом p = 6 R + 1, весом R, формируемых на основе одного класса вычетов по модулю p.
1.
2.
3.
4.
5.
6.
7.
8.
Гантмахер В.Е // Вестник НовГУ. Сер.: Естеств. и техн. науки. 1995. №1. С.81-87.
Гантмахер В.Е., Быстров Н.Е., Чеботарев Д.В. Шумоподобные сигналы. Анализ, синтез, обработка. СПб.:
Наука и техника, 2005. 400 с.
Гантмахер В.Е., Едемский В.А. // Вестник НовГУ. Сер.: Техн. науки. 2005. №30. С.52-57.
Холл М. Комбинаторика. М.: Мир, 1970. 423 с.
Михелович Ш.Х. Теория чисел. М., 1967. 336 с.
Whiteman A.L // Acta arithmetica. 1960. №6. Р.53-76.
Винокуров В.И, Гантмахер В.Е. Дискретно-кодированные последовательности. Ростов н/Д., 1990. 293 с.
Ding C., Helleseth T., and Lam K.Y. // IEEE Trans. Inform. Theory. Nov. 1999. Vol. 45. P.2601-2606.
52
1/--страниц
Пожаловаться на содержимое документа