Разработка и построение распределенной вычислительной сети MarGrid

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

Цель НИР

– число последовательностей

V = 2

N

N

V

10

1 024

20

1 048 576

30

1 024

40

1.100 10

50

1.126 10

60

1.153 10

70

80

~

9

.

~

15

.

.

18

~

1.181 10

.

21

~

1.210 10

.

24

~

90

1.238 10

.

27

~

100

1.268 10

.

30

~

200

1.607 10

.

60

~

1000

1.072 10

.

301

~

1 год ~ 3.154 10 секунд

.

7

1 эксафлопс ~ 10 операций/с

18

Производительность = 3.154 10 операций/год

25

.

атомов
в человеке

27

атомов
во Вселенной

67

элементарных
частиц во
Вселенной

80

секунд
возраст
Вселенной

17

12

SL –боковой лепесток

сдвиг = 1

SL(сдвиг)=N-2*Вес

SL(1)=16-24= -8

N = 16 бит

- длина последовательности

0101101100100101

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

0101101100100101

0101101100100101

0101101100100101

0101011011001001

0101101100100101

0101011011001001

0000110111101100

Вес(0000110111101100) = 8

сдвиг = 2

SL(2)=16-16=0

ПАКФ={N, SL(1), SL(2) , … , SL(N-1) }

ПАКФ={16, -8, 0 , 4 , 0, -4, 0, 4, -8, 4, 0, -4, 0, 4, 0, -8 }

cдвиг = 1,2,3,…N-1

= 11

SL –боковой лепесток

сдвиг = 1

SL(сдвиг)=N-сдвиг-2*Вес

SL(1)=15-22= -7

N = 16 бит

- длина последовательности

0101101100100101

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

0101101100100101

0101101100100101

0101101100100101

01011011001001

01101100100101

01011011001001

00110111101100

Вес(00110111101100) = 8

сдвиг = 2

SL(2)=14-16=-2

ААКФ={N, SL(1), SL(2) , … , SL(N-1) }

ААКФ={16, -7, -2 , 7 , -4, -3, 2, -1, -4, 5, -2, -1, 4, -3, 2, -1 }

сдвиг = 1,2,3,…N-1

= 16 бит

первая

0101101100100101

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

SL(0)=16-16=0

ВКФ={SL(0), SL(1), SL(2) , … , SL(N-1) }

ВКФ={0, 0, 0 , 4 , -4, 4, 0, 0, 0, -4, 4, 0, -4, 0, 4, -4 }

сдвиг = 0,1,2,3,…,N-1

вторая

1100110001101001

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

1100110001101001

1110011000110100

сдвиг = 0

сдвиг = 2

Вес = 8

1011110100010001

Вес = 8

1001011101001100

Вес = 8

SL(1)=16-16=0

SL(2)=16-16=0

SL(сдвиг)=N-2*Вес

Объем ансамбля V – количество последовательностей в ансамбле

ААКФ и ВКФ

Идеальная:

ПАКФ={N, 0, 0 , 0 , 0, 0, …. , 0, 0, 0, 0, 0, 0, 0, 0, 0 }

Идеальная:

ААКФ={N, <1, <1 , <1 , <1, .. , <1, <1, <1, <1, <1, 1 }

Идеальная:

ВКФ={ … , }

с объемом ансамбля V=N

Области применения:

- системы связи: основы CDMA-стандартов: IS-95, CDMA2000,
WCDMA, UMTS; помехоустойчивые коды: RS, BCH, Viterbi и т.д.
- радионавигационные системы: GPS, ГЛОНАСС, Galileo
- криптография: ключи в симметричных системах шифрования,
псевдослучайные последовательности, цифровые «водяные» знаки
- системы синхронизации

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

2-х теорем Гёделя о неполноте:
две теоремы математической логики о
принципиальных ограничениях 
формальной арифметики и, как следствие,
всякой формальной системы, в которой
можно определить основные арифметические
понятия: натуральные числа, 0, 1, 
сложение и умножение

Первая теорема: если формальная арифметика непротиворечива, то в ней существует невыводимая и неопровержимая формула.
Вторая теорема: если формальная арифметика непротиворечива, то в ней невыводима некоторая формула, содержательно утверждающая непротиворечивость этой арифметики.
Эти теоремы были доказаны Куртом Гёделем в 1930 году (опубликованы в 1931).

Награжден национальной медалью науки США, 1974

small correlation. Error correcting codes, New York, John Wiley and Sones, 1968.

- PSL=1 - Barker codes

R.H. Barker. Group synchronizing of binary digital systems, Communication
Theory (W. Jackson, ed.), Academic Press, New York, 1953, pp. 273–287

Результаты поиска
оптимальных минимаксных бинарных последовательностей

- PSL=3 for

Lindner J. Binary sequences up to length 40 with best possible autocorrelation function//
Electronics Letters, 16 October 1975, V. 11, № 21, p. 507.

Cohen M.N., Baden J.M., Cohen P.E. Biphase codes with minimum peak sidelobes//
Proceedings of the IEEE National Radar Conference, 1989, pp. 62–66.

Cohen M.N., Fox M.R., Baden J.M. Minimum peak sidelobes pulse compression codes// Proceedings of the IEEE International Radar Conference. – Arlington, VA, May 1990, pp. 633–638.

Extended results to length 48 in a 16 day run

exhaustive search in a 50 day run

H., Schotten H., Busboom A. A comparative study of optimization methods
for the synthesis of binary sequences with good correlation properties// In 5th IEEE
Symposium on Communication and Vehicular Technology in the Benelux/ IEEE, 1997, pp. 24–31.

Coxson G.E., Hirschel A., Cohen M.N. New results on minimum-PSL binary codes//
Proceedings of the 2001 IEEE Radar Conference. – Atlanta, GA, May 2001, pp. 153–156.

Coxson G.E., Russo J. Efficient exhaustive search for optimal-peak-sidelobe binary
codes// IEEE Trans. Aerospace and Electron. Systems, 2005, V. 41, pp. 302–308.

Kerdock A.M., R. Mayer, D. Bass. Longest binary pulse compression codes with given peak sidelobe levels// Proceedings of the IEEE, February 1986, vol. 74, no.2, p.366.

PSL=3 for N=51, PSL=4 for N=69, PSL=5 for N=88

PSL=4 for N=[49,61]

PSL=4 for N=[49,69]

PSL=4 for N=[61,70] and exhaustive search for N=64 – optimal PSL

PSL=4 for N=[71,82]

C.J.Nunn, G.E.Coxson. Best-Known Autocorrelation Peak Side Levels for Binary Codes of
Length 71 to 105// IEEE Trans. On Aerospace and Electronic Systems, Vol.44, No.1, 2008,
pp.392-395.

(optimal)

N=[2,48]

Best
known

C.J.Nunn, G.E.Coxson. Best-Known Autocorrelation Peak Side Levels for Binary Codes of Length 71 to 105// IEEE Trans. On Aerospace and Electronic Systems, Vol.44, No.1, 2008, pp.392-395.

40;
1990г. – Кохен - N ≤ 48;
2005г. – Коксон и Руссо - N = 64;
2013г. – Леухин, Потехин - N =[2, 74];
2014г. – Леухин, Потехин – 75 ≤ N ≤ 80;
Алгоритм brunch and bound
Впервые был предложен A.H. Land; A.G. Doig (1960)
Для модификации была выбрана реализация G.E. Coxon; J. Russo (2005).

Исчерпывающий поиск последовательностей

дерева в глубину

Каждое поддерево можно обходить независимо от остальных – возможность параллельного решения задачи

задачи

для осуществления межпроцессорного взаимодействия

Server 2012
Способы администрирования и контроля: приложение на WinForms, сайт (MVC Framework) на IIS сервере

файлов задач
Загрузка новый версий клиентов