close

Вход

Забыли?

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

?

О семействах бинарных последовательностей простого периода с квазиидеальной автокорреляцией.

код для вставкиСкачать
ПРОБЛЕМЫ ЕСТЕСТВЕННЫХ НАУК
УДК 621.391.15
В.Е. Гантмахер, В.А. Едемский
О СЕМЕЙСТВАХ БИНАРНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
ПРОСТОГО ПЕРИОДА С КВАЗИИДЕАЛЬНОЙ АВТОКОРРЕЛЯЦИЕЙ
Синтезированы бинарные последовательности, сформированные на
основе классов степенных вычетов по модулю p=dR+1 для d=6,8 с автокорреляцией, близкой к нулевой.
V.E. Gantmaher, V.A. Edemsky
ABOUT SIMPLE PERIOD BINARY SEQUENCES FAMILIES
WITH QUASI-IDEAL AUTOCORRELATION
Synthesized binary sequences are presented in this article, formed on base of
power residue classes by module p=dR+1 for d=6,8 with autocorrelation near zero.
Введение
Бинарные последовательности zi={1} (БП) с хорошей периодической автокорреляционной функцией (ПАКФ) часто используются в системах связи, радиолокации и гидролокации. Хорошо известны БП, соответствующие разностным множествам, сформированным
на основе классов вычетов [1]. В [2] была разработана теория спектров разностей классов
вычетов (СРКВ). В [3] предложена методика анализа и синтеза дискретно-кодированных последовательностей, сформированных на основе классов степенных вычетов по простому модулю, заключающаяся в комплексном использовании теории СРКВ и циклотомических чисел. Данная методика позволяет рассчитывать рельеф ПАКФ БП посредством разложения
периода p на сумму квадратов целых чисел.
Цель настоящей работы заключается в синтезе БП простого периода p=dR+1, d=6,8 с
ПАКФ (), удовлетворяющей условию:  ()  R , то есть в синтезе БП с относительно небольшими значениями боковых лепестков (БЛ) ПАКФ. Исследование ПАКФ БП будет проведено, согласно [3], по следующей методике:
1. Разложение периода БП p на сумму квадратов целых чисел.
2. Расчет СРКВ.
3. Вычисление гармоник СРКВ с использованием явных формул для нахождения циклотомических чисел.
4. Анализ полученных соотношений для ПАКФ БП.
Пусть H k  {k dt , t  0, R  1} – класс степенных вычетов с номером k, k  0, d  1 , где
 – первообразный корень по модулю p.
Рассмотрим БП Z, сформированную по правилу кодирования (ПК):
1, если i  H l , H k , H n ,
(1)
U Z (i )  

 1, в остальных случаях.
Анализ рельефов ПАКФ БП и синтез БП с квазиидеальной ПАКФ,
сформированных на основе классов вычетов по модулю p для p=6
При d=6 возможно 20 вариантов упорядоченных троек индексов (k,l,n), которые, с
учетом циклических сдвигов, можно разбить на 4 множества.
I 0  0,2,4, 1,3,5,
I1  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 .
Рельефы БЛ ПАКФ для троек индексов каждого из множеств Ii отличаются только
циклическим сдвигом. В первом случае (I0) ДП X соответствует множеству квадратичных
вычетов (невычетов), ее ПАКФ изучена [1]. Четвертый (I3) – сводится к третьему (I2) заменой
 на –1и был изучен Холлом [4]. Таким образом, для определения возможных рельефов
ПАКФ БП достаточно исследовать только I1.
Если p  1 (mod 3) , то справедливо разложение: p=A2+3B2, где A=3f+1, A, B, f – целые
числа [5]. Обозначим через m – наименьший положительный вычет ind 2 по модулю 3, где
ind 2 – логарифмическая функция (ind 2= означает, что   2(mod p) ). Пусть S – разница между наибольшим и наименьшим уровнями БЛ ПАКФ БП.
Теорема 1. Если d=6, то уровни БЛ ПАКФ БП, сформированной по ПК (1) для нечетного R и (k,l,n)I1, определяются следующими формулами:
 1  8B , если m  0,

3
1Z  1 ,  2 Z ,  3Z  
4( A  B)
 1 
, если m  0.

3
Доказательство. Известно [1], что БЛ ПАКФ X() ДП X и БЛ ПАКФ Z() БП Z связаны соотношением:
 Z    p  4 ( RX   X  ) ,
(2)
X
где zi  {1}, xi  {0,1}, zi  2 xi  1 , RX – вес ДП. Для ПК (1) R =3R. Таким образом,
 Z    4 X    p  2 . СРКВ классов вычетов Hk и Hl обозначим через S(k,l). Согласно [2], в
этом случае уровни БЛ ПАКФ ДП X определяются СРКВ:
 X ()  S (0,0)  S (0,1)  S (0,2)  D 3 S (0,1)  DS (0,0)  DS (0,1)  D 3 S (0,2)  D 4 S (0,1)  D 2 S (0,0) ,
где D – оператор циклического сдвига Хаффмена. В [3] показано, что СРКВ S(0,q) определяется циклотомическими числами шестого порядка. Воспользовавшись явными формулами
для вычисления циклотомических чисел шестого порядка [4], получаем следующие соотношения для БЛ ПАКФ ДП X:
 3 p  9  8B , если m  0,

p 3
12
,  2 X , 3 X  
1 X 
3

9  4( A  B)
p
4

, если m  0.

12
Подстановка полученных значений X() в (2) завершает доказательство теоремы.
16 B , если m  0,

Следствие 1.1. В условиях теоремы 1 S   3
8 A B

, если m  0.
 3
A B
Таким образом, наименьшие БЛ ПАКФ БП Z будут, если
 1 . Этому условию
3
удовлетворяют периоды, определяемые следствием.
Следствие 1.2. Для (k,l,n)I1 значения ПАКФ Z()БП Z , сформированной по ПК (1)
при d=6, принадлежат множеству {–5,–1,3} в случае, когда период БП определяется следующими формулами:
1) p  144u 2  12u  7 ,
2) p  144u 2  84u  19 , где u – целое число.
Доказательство. Если p  43u  1  3 1  6u   144u 2  12u  7 , то A  2  6u,
B  1 6u для m=1 и A  2  6u , B  1  6u для m=2, то есть: v2,3  1  4 . Второй вариант
2
рассматривается аналогично.
Условиям следствия 1.2 удовлетворяют периоды: p=19, 79, 139, 163, 607, 1063, …
По изложенной ранее методике доказывается и следующая теорема.
Теорема 2. Если d=6, то уровни БЛ ПАКФ БП, сформированной по ПК (1) для четного R и (k,l,n)I1, определяются следующими формулами:
 3  8B , если m  0,
1  8B , если m  0,


3
3
1Z  3 ,  2 Z  1 ,  3 Z ,  4 Z  
, 5Z , 6Z  
.
4( A  B)
4( A  B)
 3 
1 
, если m  0.
, если m  0.


3
3
8 A B
Для m  0 S 
 4 , поэтому при синтезе БП Z с квазиидеальной ПАКФ наи3
более интересен случай, когда A  B  3 . В этом случае получаем следствие.
Следствие 2.1. Если (k,l,n)I1, то для БП Z, сформированной по ПК (1) при d=6 значения ПАКФ Z() принадлежат множеству {–7,–3, 1, 5}, если:
3) p  13  60u  144u 2 ,
4) p  49  156u  144u 2 , где u – целое число.
Значения p, удовлетворяющие условиям следствия 2.1: p= 37, 97, 313, 349, 709, 877,
937, 1129, 1489,… показывают, что рассматриваемые БП имеют достаточно плотную сетку
периодов.
Теоремы 1, 2 обобщают результаты [2] на случай, когда при кодировании используются три класса вычетов и определяют семейства БП с квазиидеальной ПАКФ.
Используя изложенную выше методику, исследуем БП при d=8, нечетном R. В этом
случае справедливо разложение: p  x 2  4 y 2  a 2  2b 2 , x  1 (mod 4), a  1 (mod 4) , где
x,y,a,b – целые числа [5].
Пусть БП Z сформирована по ПК:
1, если i  H k , H l , H n , H q ,
U Z (i )  
(3)
 1, в остальных случаях.
Как уже отмечалось ранее, достаточно рассмотреть случай, когда k=0. Для (0,l,n,q)
всего возможно 35 вариантов, среди которых выберем шесть циклически независимых и не
сопряженных (варианты, сводящиеся к квадратичным или биквадратичным вычетам, здесь
не рассматриваем):
L1  (0,1,2,3); (0,1,2,7); (0,1,6,7); (0,5,6,7) ,
L2  (0,1,2,4); (0,1,3,7); (0,2,6,7); (0,4,5,6) ,
L3  (0,1,2,5); (0,1,4,7); (0,3,4,5); (0,3,6,7) ,
L4  (0,1,3,4); (0,1,5,6); (0,2,3,7); (0,4,5,7) ,
L5  (0,1,3,5); (0,2,4,7); (0,2,5,6); (0,3,4,6) ,
L6  (0,1,3,6); (0,2,5,7); (0,2,3,5); (0,3,5,6) .
Согласно (2),  Z    4 X    p  2 , где ДП X, сформирована по ПК:
1, если i  H k , H l , H n , H q ,
U X (i )  
0, в остальных случаях.
Воспользовавшись формулами для вычисления циклотомических чисел восьмого порядка [4] для расчета соответствующих СРКВ, определим уровни БЛ БП, сформированных
по ПК (3). Их значения приведены в таблице.
Уровни БЛ ПАКФ БП Z для p = 8R + 1.
(0,1,2,3)
21Z
22Z
23Z
24Z
(0,1,2,4)
41Z
42Z
43Z
44Z
(0,1,2,5)
21Z
22Z
23Z
24Z
(0,1,3,4)
21Z
22Z
23Z
24Z
(0,1,3,5)
41Z
42Z
43Z
44Z
y  0 (mod 4)
 2  x  2y  a
 2  x  2 y  a  4b
 2  x  2 y  a  4b
 2  x  2y  a
y  0 (mod 4)
 2  x  2 y  a  4b
 2  x  2y  a
 2  x  2y  a
 2  x  2 y  a  4b
 12  3x  8 y  a  4b
 4  3x  4 y  a
 4  3x  4 y  a
4  3 x  8 y  a  4b
 12  x  4 y  a
 2  x  2y  a
 6  2 x  2a
 2  x  2y  a
 2  x  2y  a
2
–6
 2  x  2y  a
2  2 x  2a
 2  x  2y  a
 4  3x  4 y  a
 12  3x  8 y  a  4b
8  3x  8 y  a  4b
 4  3x  4 y  a
 4  x  a  4b
 4  x  a  4b
4  x  4y  a
–6
 2  x  2y  a
2  2 x  2a
 6  2 x  2a
 2  x  2y  a
2
 2  x  2y  a
 4  x  a  4b
 12  x  4 y  a
4  x  4y  a
 4  x  a  4b
Окончание таблицы
(0,1,3,6)
21Z
22Z
23Z
24Z
 2  x  2y  a
 2  x  2y  a
 2  x  2 y  a  4b
 2  x  2 y  a  4b
 2  x  2 y  a  4b
 2  x  2 y  a  4b
 2  x  2y  a
 2  x  2y  a
Анализ формул таблицы показывает, что для того чтобы уровни БЛ ПАКФ были
близки к нулю, необходимо выполнение следующих условий: y0 и ax для первого, третьего, четвертого и шестого вариантов или y0 и a–3x для второго и пятого вариантов.
Исследуем найденные необходимые условия. Если a–3x, то: y 2  8 x 2  2b 2 , тогда с
ростом p условие y0 не будет выполняться. Таким образом, в вариантах L2,L5 при относительно больших значениях p ПАКФ не будет квазиидеальной.
Равенство a=x невозможно, так как 4 y 2  2b 2 . В этом случае: a  x  4 и
b 2  8 x  16  4 y 2 , то есть при малых значениях y и относительно большом p значение b
также будет велико, таким образом, в вариантах L1,L6 ПАКФ не будет квазиидеальной.
В вариантах L3,L4 при малом значении y и ax ПАКФ будет иметь небольшие уровни
БЛ, в частности, имеет место теорема 3.
Теорема 3. Если (k,l,n,q)L3, то значения ПАКФ Z() БП Z, сформированной по ПК
(3) при d=8, принадлежат множеству {–7,1}, если p  89  80u  96u 2  256u 3  256u 4
( p  x 2  64  ( x  4) 2  2b 2 ), множеству {–7,–3, 1, 5}, если p  41  80u  144u 2  128u 3  64u 4
множеству
{–7,–3,–3, 9},
если
p  25  48u 2  64u 4
( p  x 2  16  ( x  8) 2  2b 2 ) ,
( p  x 2  16  ( x  8) 2  2b 2 ) и, для указанных периодов, соответственно множествам
{–7,–3, 1, 5}, {–11, 1, 1, 5}, {–7,–3, 1, 5}, если (k,l,n,q)L4. При достаточно больших периодах
 Z ()  p , БП является квазиидеальной.
Доказательство. Если p  x 2  64  ( x  4) 2  2b 2 , то y  4, a  x  4 и, согласно таблице, 1Z  7,  2,3, 4 Z  1 . Другие варианты рассматриваются аналогично.
Ряд значений p, удовлетворяющих условиям теоремы 3: p=73, 89, 1913, 5689, 26633,
80153, 41, 457, 27241, 60041, 525641, 137, 5641, 84697, 156041… показывает, что рассматриваемые БП имеют достаточно плотную сетку периодов.
Заключение
Определены рельефы ПАКФ для БП, сформированных на основе классов степенных
вычетов по модулю p=dR+1 для d=6,8. Найдены новые и обобщены известные ПК БП с квазиидеальной ПАКФ. Найдены семейства БП с одинаковым рельефом ПАКФ, имеющие одинаковые формулы для вычисления периода p, боковых лепестков ПАКФ (()).
ЛИТЕРАТУРА
1. Винокуров В.И. Дискретно-кодированные последовательности / В.И. Винокуров,
В.Е. Гантмахер. Ростов-н/Д., 1990. 293 с.
2. Гантмахер В.Е. Шумоподобные сигналы. Анализ, синтез, обработка /
В.Е. Гантмахер, Н.Е. Быстров, Д.В. Чеботарев. СПб.: Наука и техника, 2005. 400 с.
3. Гантмахер В.Е. Методика анализа и синтеза ДКП, формируемых на основе классов
вычетов по модулю p / В.Е. Гантмахер, В.А. Едемский. НовГУ. Новгород, 2005. 49 с. Рус. –
Деп. в ВИНИТИ № 1737-В2005 26.12.05.
4. Холл М. Комбинаторика / М. Холл. М.: Мир, 1970. 423 с.
5. Бухштаб А.А. Теория чисел / А.А. Бухштаб. М.: Наука, 1966. 384 с.
Гантмахер Владимир Ефимович –
доктор технических наук,
профессор кафедры «Радиосистемы»
Новгородского государственного университета
Едемский Владимир Анатольевич –
кандидат физико-математических наук,
докторант кафедры «Прикладная математика и информатика»
Новгородского государственного университета
Статья поступила в редакцию 05.09.06, принята к опубликованию 10.10.06
Документ
Категория
Без категории
Просмотров
4
Размер файла
228 Кб
Теги
бинарных, автокорреляции, простого, квазиидеальной, период, семейство, последовательность
1/--страниц
Пожаловаться на содержимое документа