Код Баркера

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

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

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

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

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

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

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

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

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

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

${\displaystyle N}$	Коди		${\displaystyle PSLR}$	${\displaystyle 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 році Баркер запропонував більш жорсткі вимоги: ${\displaystyle c_{j}\in \{-1,0\}}$, з усіх дев'яти кодів лише чотири задовільняють таким вимогам (у таблиці вони позначені жирним шрифтом).

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

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

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

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

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

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

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

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

${\displaystyle R(j)=\sum _{i=1}^{N-j}a[i]{a^{*}}[i+j]}$, де ${\displaystyle i}$ дискретний індекс зсуву між послідовностю та її копією (у часі), а позначка ${\displaystyle *}$ вказує на комплексне поєднання.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle ISL={\frac {E}{ML}}}$.

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

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

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

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

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

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

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

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

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

Деякі коди з низьким рівнем бокових пелюсток

${\displaystyle N}$	Код	${\displaystyle PSL}$	${\displaystyle PSLR}$	${\displaystyle 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 дБ

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

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

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

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

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

Див. також

• Псевдовипадкова двійкова послідовність
• M-послідовність
• Символ Лежандра

Примітки

1. Barker, R. H. (1953). Group Synchronizing of Binary Digital Sequences. Communication Theory. London: Butterworth. с. 273—287.
2. . Архів оригіналу за 19 Січня 2017. Процитовано 17 Січня 2017.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
3. ; 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 .
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
7. (PDF). Архів оригіналу (PDF) за 21 Жовтня 2016. Процитовано 17 Січня 2017.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
8. . Архів оригіналу за 18 Січня 2017. Процитовано 22 Січня 2017.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
9. Introduction to Radar Systems, 3rd Edition, Merrill I. Skolnik, McGraw–Hill, 2001
10. A. N. Leukhin and E. N. Potehin. «Binary Sequences with Minimum Peak Sidelobe Level up to Length 68» [ 12 Лютого 2017 у Wayback Machine.], arXiv, 2012.
11. C. J. Nunn and G. E. Coxson. «Best-Known Autocorrelation Peak Sidelobe Levels for Binary Codes of Length 71 to 105» [ 31 Жовтня 2017 у Wayback Machine.], , 1, January 2008.
12. https://github.com/Gluttton/PslRK/tree/master/Solutions
13. . Radar waveforms. Fundamentals of Radar Signal Processing, Second Edition. с. 199.
14. . Mismatched Phase Code Filters. Fundamentals of Radar Signal Processing, Second Edition. с. 206.

Посилання

• Послідовність A011758 на OEIS [ 19 Січня 2017 у Wayback Machine.] — код Баркера довжиною 13 (знакове представлення).
• Послідовність A011759 на OEIS [ 19 Січня 2017 у Wayback Machine.] — код Баркера довжиною 13.
• Послідовність A281476 на OEIS [ 12 Лютого 2017 у Wayback Machine.] — максимальні довжини послідовностей з відповідним рівнем бокових пелюсток.
• LowPslCodes.xml [ 14 Березня 2022 у Wayback Machine.] — Список кодів Баркера та кодів з низьким рівнем бокових пелюсток у форматі XML.
• CodeManager — Програма для маніпуляцій з двійковими послідовностями та вимірювання їх параметрів продуктивності.