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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
График 100 случайных величин со скрытой синусоидой. Автокорреляционная функция позволяет увидеть периодичность в ряде данных.

Автокорреляция — статистическая взаимосвязь между случайными величинами из одного ряда, но взятых со сдвигом, например, для случайного процесса — со сдвигом по времени.

Автокорреляционная функция (АКФ, ACF).

В обработке сигналов автокорреляционная функция (АКФ) определяется интегралом:

\Psi(\tau) = \int f(t) f(t-\tau) \mathrm{d}t

и показывает связь сигнала (функции \;f(t)) с копией самого себя, смещённого на величину \tau.

В теории случайных функций АКФ является корреляционным моментом двух значений одной случайной функции \;X(t):

K (t_1, t_2) = \mathbb{E}\left\{\left[X(t_1)-\overline{x}(t_1)\right]\left[X(t_2)-\overline{x}(t_2)\right]\right\}/\mathbb{D}

Здесь \overline{x}(t)=\mathbb{E}\left[X(t)\right], а \mathbb{E}\left[X(t)\right] — математическое ожидание.

График автокорреляционной функции можно получить, отложив по оси ординат коэффициент корреляции двух функций (базовой и функции сдвинутой на величину \tau), а по оси абсцисс величину \tau. Если исходная функция строго периодическая, то на графике автокорреляционной функции тоже будет строго периодическая функция. Таким образом, из этого графика можно судить о периодичности базовой функции, а следовательно, и о её частотных характеристиках. Автокорреляционная функция применяется для анализа сложных колебаний, например, электроэнцефалограммы человека.

Применение в технике[править | править вики-текст]

Корреляционные свойства кодовых последовательностей, используемых в широкополосных системах, зависят от типа кодовой последовательности, её длины, частоты следования её символов и от её посимвольной структуры.

Изучение АКФ играет важную роль при выборе кодовых последовательностей с точки зрения наименьшей вероятности установления ложной синхронизации.

Другие применения[править | править вики-текст]

Автокорреляционная функция играет важную роль в математическом моделировании и анализе временных рядов, показывая характерные времена для исследуемых процессов (см., например: Турчин П. В. Историческая динамика. М.: УРСС, 2007. ISBN 978-5-382-00104-3). В частности, циклам в динамике систем соответствуют максимумы на соответствующей автокорреляционной функции.

Скоростное вычисление[править | править вики-текст]

Часто приходится вычислять автокорреляционную функцию для временного ряда x_i. Вычисление «в лоб» работает за O(T^2). Однако есть способ сделать это за O(T \log T).

Подготовка. Вычитаем из ряда среднее арифметическое. Преобразуем в комплексные числа. Дополняем нулями до 2^k. Затем дописываем в конец ещё 2^k нулей.

Вычисление. Автокорреляционная функция вычисляется с помощью быстрого преобразования Фурье и прямо пропорциональна первым n элементам последовательности

\Psi(\tau) \sim \operatorname{Re} \operatorname{fft}^{-1}\left(\left|\operatorname{fft}(\vec x)\right|^2\right)

Квадрат комплексного модуля берётся поэлементно: \left|\vec a\right|^2 = \left\{ \operatorname{Re}^2 a_i + \operatorname{Im}^2 a_i \right\}. Если нет погрешностей вычисления, мнимая часть будет равна нулю. Коэффициент пропорциональности определяется из требования \Psi(0)=1.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]