Код Баркера

Код Баркера або Послідовність Баркера — скінченна знакова послідовність (така послідовність, кожен елемент якої дорівнює +1 або −1) довжиною $N$

\{a_{i}\}_{i=1}^{N}|a_{i}\in \{+1,-1\}

Графічне представлення одинадцятипозиційного коду Баркера

Автокореляційна функція одинадцятипозиційного коду Баркера

з ідеальними автокореляційними властивостями, за яких модуль коефіцієнтів автокореляційної функції

c_{j}=\sum _{i=1}^{N-j}a_{i}a_{i+j}

набуває мінімально можливого значення $|c_{j}|\leq 1$ для ненульового зсуву $1\leq j<N$ [1].

Відомі коди Баркера

Відомо лише дев'ять[2] кодів Баркера, найдовший з яких має довжину 13[3]. Наразі вважається, що інших кодів Баркера не існує.[4] (доведено, що не існує ніяких інших кодів непарної довжини,[5] або парної довжини корочше ніж $N<10^{22}$ .[6])

**Відомі коди Баркера**
$N$	Коди		$PSLR$	$ISLR$
2	+1 −1	+1 +1	−6.02 дБ	−3.01 дБ
3	+1 +1 −1		−9.54 дБ	−6.53 дБ
4	+1 +1 −1 +1	+1 +1 +1 −1	−12.04 дБ	−6.02 дБ
5	+1 +1 +1 −1 +1		−13.98 дБ	−7.96 дБ
7	+1 +1 +1 −1 −1 +1 −1		−16.90 дБ	−9.12 дБ
11	+1 +1 +1 −1 −1 −1 +1 −1 −1 +1 −1		−20.83 дБ	−10.83 дБ
13	+1 +1 +1 +1 +1 −1 −1 +1 +1 −1 +1 −1 +1		−22.28 дБ	−11.49 дБ

У 1953 році Баркер запропонував більш жорсткі вимоги: $c_{j}\in \{-1,0\}$ , з усіх дев'яти кодів лише чотири задовільняють таким вимогам (у таблиці вони позначені жирним шрифтом).

Завдяки властивостям автокореляційної функції та знакової послідовності для кожного з кодів Баркера можна змінити порядок слідування елементів таким чином, щоб лишити незмінними значення коефіцієнтів автокореляційної функції. Для кожного коду Баркера можна:

змінити порядок слідування елементів на зворотній;
змінити кожен з елементів на зворотній за знаком;
змінити порядок слідування елементів та кожен з елементів на зворотній.

Так, наприклад для п'ятипозиційного коду Баркера $\{+1,+1,+1,-1,+1\}$ можна побудувати наступні коди, які разом з вихідним будуть мати однакові значення автокореляційної функції.

$\{+1,-1,+1,+1,+1\}$ ;
$\{-1,-1,-1,+1,-1\}$ ;
$\{-1,+1,-1,-1,-1\}$ .

Параметри продуктивності[7]

Автокореляційні функції кодів Баркера, що утворюють комплементарну пару

Автокореляційна функція

Автокореляційною функцією послідовності Баркера є скінченна дискретна послідовність що утворюється за допомогою операції згортки над послідовністю та її власною копією:

R(j)=\sum _{i=1}^{N-j}a[i]{a^{*}}[i+j]

, де

i

дискретний індекс зсуву між послідовностю та її копією (у часі), а позначка

*

вказує на комплексне поєднання.

Автокореляційна функція симетрична відносно головної пелюстки, що випливає з її загальних властивостей. Можна побачити, що довжина автокореляційної функції завжди непарна для послідовності довільної довжини.

Рівень головної пелюстки

Рівень головної пелюстки (англ. Mainlobe level) — модуль коефіцієнта автокореляційної функції для нульового зсуву $j=0$ .

ML=\left|\sum _{i=1}^{N}a_{i}a_{i}\right|=N

Рівень головної пелюстки має найбільше значення порівняно з іншими коефіцієнтами автокореляційної функції та дорівнює його довжині $N$ .

Рівень бокових пелюсток

Рівень бокових пелюсток (англ. Peak sidelobe level) — максимальне абсолютне значення серед коефіцієнтів автокореляційної функції для ненульового зсуву $1\leq j<N$ .

PSL=max\left\{\left|\sum _{i=1}^{N-j}a_{i}a_{i+j}\right|\right\}\leq 1

Рівень бокових пелюсток для кодів Баркера на перевищує 1.

Окремо рівень головної та бокових пелюсток не дають достатнього уявлення про продуктивність того чи іншого коду. Натомість широке застосування отримало відношення бокових пелюсток (англ. Peak sidelobe level ratio) яке показує відносне значення рівня бокових пелюсток коду до його головної пелюстки та вимірюється в децибелах

PSLR=20\log _{10}\left({\frac {PSL}{ML}}\right)

.

Сумарний рівень бокових пелюсток

Енергія (англ. Energy) знакової послідовності визначена як:

E=2\cdot \sum _{n=1}^{N-1}\left(\sum _{i=1}^{N-j}a_{i}a_{i+j}\right)^{2}

.

Сумарний рівень бокових пелюсток (англ. Integrated sidelobe level) визначений як:

ISL={\frac {E}{ML}}

.

Аналогічно як $PSL$ так і $ISL$ зручніше представляти в децибелах як відношення сумарного рівня бокових пелюсток (англ. Integrated sidelobe level ratio):

ISLR=10\log _{10}\left({\frac {E}{ML}}\right)

.

Застосування

Сигнал модульований за законом кода Баркера довжиною 13

Коди Баркера довжиною 11 та 13 використовуються в DSSS та системах стискання імпульсів[8] радіолокаційних станцій через їхні властивості автокореляційної функції — низький рівень бокових пелюсток[9]. Коди Баркера за властивостями автокореляційної функції схожі на лінійно частотно модульовані імпульси які також використовуються в радіолокації. Зміна амплітуди сигналу на позитивну та негативну у відповідності до кодів Баркера покладена в основу двійкової фазової маніпуляції; тобто зсув фази опорного сигналу на $\pi$ радіан.

Аналогічно до кодів Баркера існують компліментарні послідовності (англ. complementary sequences), які компенсують бокові пелюстки при додаванні; коди Баркера парної довжини також є комплементарними парами. Так наприклад для кодів довжиною $N=4$ коефіцієнти автокореляційної функції будуть дорівнювати (без головної пелюстки): $\{+1,0,-1\}$ та $\{-1,0,+1\}$ , що при додаванні дасть $\{0,0,0\}$ . Існує простий конструктивний спосіб побудувати довгу компліментарну послідовність.

Послідовності з низьким рівнем бокових пелюсток[10]

Автокореляційна функція коду з низьким рівнем бокових пелюсток довжиною 51

Через обмежену кількість кодів Баркера на практиці застосовуються коди з низьким рівнем бокових пелюсток, які не є кодами Баркера, оскільки не виконується вимога щодо рівня бокових пелюсток $|c_{j}|>1$ , але при цьому мають кращі показники відношення рівня бокових пелюсток, ліпші ніж у кодів Баркера. Деякі з таких кодів наведені нижче у таблиці. Коди представлені у двійковій системі, коли кожен з бітів описує елемент послідовності, а для компактності запису коди надані у шістнадцятковій системі.

**Деякі коди з низьким рівнем бокових пелюсток[11]**
$N$	Код	$PSL$	$PSLR$	$ISLR$
28	0xc7015b2	2	−22.92 дБ	−8.94 дБ
51	0x71c077376adb4	3	−24.61 дБ	−8.76 дБ
82	0x3ea5a9bbb71cc072e934f	4	−26.24 дБ	−8.17 дБ
105	0x1c6387ff5da4fa325c895958dc5	5	−26.44 дБ	−7.70 дБ

Наразі не існує конструктивного алгоритму побудови кодів з низьким рівнем бокових пелюсток, натомість використовуються різні алгоритми[10][12] пошуку таких кодів шляхом перебору в довільному діапазоні та визначення рівня їх бокових пелюсток.

Автокореляційна функція коду отриманого шляхом комбінації кодів Баркера з довжиною 3 та 5

Інший спосіб[13] отримати послідовності великої довжини (більшої ніж у існуючих кодів Баркера) з потрібним значенням автокореляційної функції це використання вкладених кодів Баркера. Вкладені коди утворюються з допомогою Добуток Кронекера двох звичайних кодів Баркера. Так для довільного коду Баркера кожен з його позитивних елементів замінюється на інший код Баркера (не обов'язково інший), а негативний елемент на його інверсний аналог. Наприклад, якщо побудувати вкладений код $\{+1,+1,-1\}\otimes \{+1,+1,+1,-1,+1\}$ на базі трьохпозиційного коду Баркера $\{+1,+1,-1\}$ з заповненням п'ятипозиційним кодом Баркера $\{+1,+1,+1,-1,+1\}$ , то буде отриманий наступний код: $\{+1,+1,+1,-1,+1,+1,+1,+1,-1,+1,-1,-1,-1,+1,-1\}$ . Такі коди мають відносно високий рівень бокових пелюсток.

Існує техніка[14], що дозволяє зменшувати відношення рівня бокових пелюсток шляхом застосування неузгодженої (англ. mismatched) фільтрації. Розрахунок таких фільтрів з необхідними імпульсними характеристиками є складною розрахунковою задачею.

Використання імпульсів різної форми для кодів Баркера також може поліпшити автокореляційні властивості[7].

Див. також

Примітки

Barker, R. H. (1953). Group Synchronizing of Binary Digital Sequences. Communication Theory. London: Butterworth. с. 273–287.
https://oeis.org/A091704
Borwein, Peter; Mossinghoff, Michael J. (2008). Barker sequences and flat polynomials. У James McKee; Chris Smyth. Number Theory and Polynomials. LMS Lecture Notes 352. Cambridge University Press. с. 71–88. ISBN 978-0-521-71467-9.
Weisstein, Eric W. Barker Code(англ.) на сайті Wolfram MathWorld.
Turyn and Storer, «On binary sequences», Proceedings of the AMS, volume 12 (1961), pages 394—399
Leung, K., and Schmidt, B., «The Field descent method», Design, Codes and Cryptography, volume 36, pages 171—188
http://paper.uscip.us/jaece/JAECE.2014.1003.pdf
http://www.radartutorial.eu/08.transmitters/Intrapulse%20Modulation.en.html
Introduction to Radar Systems, 3rd Edition, Merrill I. Skolnik, McGraw–Hill, 2001
A. N. Leukhin and E. N. Potehin. «Binary Sequences with Minimum Peak Sidelobe Level up to Length 68», arXiv, 2012.
C. J. Nunn and G. E. Coxson. «Best-Known Autocorrelation Peak Sidelobe Levels for Binary Codes of Length 71 to 105», IEEE Transactions on Aerospace and Electronic Systems, 1, January 2008.
https://github.com/Gluttton/PslRK/tree/master/Solutions
Richards, Mark. Radar waveforms. Fundamentals of Radar Signal Processing, Second Edition. с. 199.
Richards, Mark. Mismatched Phase Code Filters. Fundamentals of Radar Signal Processing, Second Edition. с. 206.

Посилання

Послідовність A011758 на OEIS — код Баркера довжиною 13 (знакове представлення).
Послідовність A011759 на OEIS — код Баркера довжиною 13.
Послідовність A281476 на OEIS — максимальні довжини послідовностей з відповідним рівнем бокових пелюсток.
LowPslCodes.xml — Список кодів Баркера та кодів з низьким рівнем бокових пелюсток у форматі XML.
CodeManager — Програма для маніпуляцій з двійковими послідовностями та вимірювання їх параметрів продуктивності.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Barker, R. H. (1953). Group Synchronizing of Binary Digital Sequences. Communication Theory. London: Butterworth. с. 273–287.

[2] ttps://oeis.org/A091704

[BM-3] Borwein, Peter; Mossinghoff, Michael J. (2008). Barker sequences and flat polynomials. У James McKee; Chris Smyth. Number Theory and Polynomials. LMS Lecture Notes 352. Cambridge University Press. с. 71–88. ISBN 978-0-521-71467-9.

[4] Weisstein, Eric W. Barker Code(англ.) на сайті Wolfram MathWorld.

[5] Turyn and Storer, «On binary sequences», Proceedings of the AMS, volume 12 (1961), pages 394—399

[6] Leung, K., and Schmidt, B., «The Field descent method», Design, Codes and Cryptography, volume 36, pages 171—188

[:0-7] ttp://paper.uscip.us/jaece/JAECE.2014.1003.pdf

[8] ttp://www.radartutorial.eu/08.transmitters/Intrapulse%20Modulation.en.html

[9] Introduction to Radar Systems, 3rd Edition, Merrill I. Skolnik, McGraw–Hill, 2001

[:1-10] A. N. Leukhin and E. N. Potehin. «Binary Sequences with Minimum Peak Sidelobe Level up to Length 68», arXiv, 2012.

[11] C. J. Nunn and G. E. Coxson. «Best-Known Autocorrelation Peak Sidelobe Levels for Binary Codes of Length 71 to 105», IEEE Transactions on Aerospace and Electronic Systems, 1, January 2008.

[12] ttps://github.com/Gluttton/PslRK/tree/master/Solutions

[BM1-13] Richards, Mark. Radar waveforms. Fundamentals of Radar Signal Processing, Second Edition. с. 199.

[BM2-14] Richards, Mark. Mismatched Phase Code Filters. Fundamentals of Radar Signal Processing, Second Edition. с. 206.