МАТРИЦА БАРКЕРА


Баркер поставил задачу [1] о поиске кодовых последовательностей из {1, –1}, близких по свойствам к белому шуму в том смысле, что автокорреляционная функция (скалярное произведение вектора кода Баркера v на вектор с любым, по величине, нециклическим сдвигом элементов влево v) ограничена по амплитуде |v'v|≤1. Задача Баркера интересна в том смысле, что она имеет решением последовательности, длиною не большей 13.

nПоследовательностьВерсия
21,-11,1
31,1,-1
41,1,-1,11,1,1,-1
51,1,1,-1,1
71,1,1,-1,-1,1,-1
111,1,1,-1,-1,-1,1,-1,-1,1,-1
131,1,1,1,1,-1,-1,1,1,-1,1,-1,1


Циклические матрицы, построенные на кодах Баркера, обладают рядом экстремальных свойств, в частности, они дают единственную циклическую матрицу Адамара 4-го порядка, две циклические матрицы максимального детерминанта Рагхаварао 5-го (отвечает также матрице Ферма) и 13-го порядков, и три циклические матрицы Мерсенна 3-го, 7-го (и 11-го, после инверсии знаков) порядков с точностью до величины отрицательного элемента: –1 трактуется как как –b. Последовательности 9-го порядка, как и матрицы Ферма, нет.

Особняком стоит второй порядок, соотносимый, по структуре, с матрицей Белевича. Класс циклических матриц максимального детерминанта уже класса циклических матриц Баркера, последние уже класса циклических матриц Мерсенна. Ограничению знака автокорреляционной функции значением –1 отвечает случай только порядков матриц Мерсенна 3, 7, 11.

Storer J.E., Turyn R. (1958) доказали, что не cуществует последовательностей Баркера нечетной длины, превосходящей 13 [2]. В работе [3] высказано предположение, что это правило общее. Причем, если существует бинарный код Баркера четной длины n>4, тогда длина кода должна быть записана в виде n=4k2, где k – некоторое целое, не являющееся степенью простого числа. Теорема была доказана для случая k≤55 [4]. Практический вывод заключается в том, что для четных длин 13<n≤4*552=12100 основное предположение верно. Этот результат не был улучшен на протяжении следующих 25 лет. На сегодняшний день рекордная ширина диапазона не существования бинарных кодов Баркера нечетных длин была получена Mossinghoff в 2009 году: верхняя граница диапазона составляет 2*1030 (с одним возможным исключением).

Порог порядка 13 встречается также в теории квазиортогональных матриц: критичный порядок для решений в виде малоуровневых матриц максимального детерминанта. Субоптимальные циклические матрицы Мерсенна могут служить примером обобщения матриц Баркера на порядки, большие 13-ти.

1. Barker R.H. Group synchronization of binary digital systems, in Jackson. W. (ed.) // Communication Theory. – Academic Press, London, 1953, pp. 273-287.

2. Storer J.E., Turyn R. Optimum finite code groups // roceedings IRE (Correspondence), 1958, V. 46, pp. 1649.

3. Turyn R.J., Storer J. On binary sequences // Proc. Amer. Math. Soc., 12, 1961, pp. 394–399.

4. Turyn R. On Barker codes of even length // Proceedings of the IEEE, September 1963, V. 51, № 9, pp. 1256.

ВИКИ | КОДЫ БАРКЕРА | ПОСЛЕДОВАТЕЛЬНОСТИ
БИНАРНЫЕ ЦИКЛИЧЕСКИЕ МАТРИЦЫ | РАСШИРЕННЫЕ КОДЫ


Rambler's Top100