ГИПОТЕЗА БАРКЕРА


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

nПоследовательностьВерсия
2 Belevitсh type*1,-11,1
3 Mersenne type1,1,-1
4 Hadamard type1,1,-1,11,1,1,-1
5 Raghavarao type1,1,1,-1,1
7 Mersenne type1,1,1,-1,-1,1,-1
11 Mersenne type*1,1,1,-1,-1,-1,1,-1,-1,1,-1
13 Raghavarao type1,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.

Оптимальные матрицы удовлетворяют условию A'A=(n–1)I+O, O – матрица из единиц, они существуют только на порядках n=1 (mod 4). Пару таких матриц (15 и 25 порядков) нашел и опубликовал Raghavarao. Матрицы Рагхаварао порядков 5, 13, 25, [41, 61, 85, 113, 145, 181, 221, 265, 313, 365, 421, 481, 545, 613, 685 и т.п.] сходны с адамаровыми в том, что достигают по значению детерминанта отмеченной границы.



Циклическая матрица Рагхаварао R13


Остальные матрицы могут быть оптимальными, но границы не достигают. Матрица типа Рагхаварао и округленная до целых значений матрица Ферма пятого порядка имеют одинаковый определитель, на 17-м порядке конструкция Ферма конкурента не имеет и представляет собой оптимальную матрицу. На классе квазиортогональных матриц она только локальна оптимальна. Предположение о том, что подобного сорта матрицы всегда лучшие по определителю опроверг в 2003 году эксперимент с матрицей 65-го порядка Уорика и Соломона.

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