Русская Википедия:Автокорреляционная функция
Автокорреляционная функция — зависимость взаимосвязи между функцией (сигналом) и её сдвинутой копией от величины временного сдвига.
Для детерминированных сигналов автокорреляционная функция (АКФ) сигнала <math>f(t)</math> определяется интегралом:
- <math>\Psi(\tau) = \int_{-\infty}^\infty f(t) f^*(t-\tau) \mathrm{d}t</math>
и показывает связь сигнала (функции <math>\;f(t)</math>) с копией самого себя, смещённого на величину <math>\tau</math>. Звёздочка означает комплексное сопряжение.
Для случайных процессов АКФ случайной функции <math>X(t)</math> имеет вид[1]:
- <math>K (\tau) = \mathbb{E}\{X(t)X^*(t-\tau)\}</math>,
где <math>\mathbb{E}\{\ \}</math> — математическое ожидание, звёздочка означает комплексное сопряжение.
Если исходная функция строго периодическая, то на графике автокорреляционной функции тоже будет строго периодическая функция. Таким образом, из этого графика можно судить о периодичности исходной функции, а, следовательно, и о её частотных характеристиках. Автокорреляционная функция применяется для анализа сложных колебаний, например, электроэнцефалограммы человека.
Применение в технике
Корреляционные свойства кодовых последовательностей, используемых в широкополосных системах, зависят от типа кодовой последовательности, её длины, частоты следования её символов и от её посимвольной структуры.
Изучение АКФ играет важную роль при выборе кодовых последовательностей с точки зрения наименьшей вероятности установления ложной синхронизации.
Другие применения
Автокорреляционная функция играет важную роль в математическом моделировании и анализе временных рядов, показывая характерные времена для исследуемых процессов (см., например: Турчин П. В. Историческая динамика. М.: УРСС, 2007. ISBN 978-5-382-00104-3). В частности, циклам в поведении динамических систем соответствуют максимумы автокорреляционной функции некоторого характерного параметра.
Скоростное вычисление
Шаблон:Орисс Часто приходится вычислять автокорреляционную функцию для временного ряда <math>x_i</math>. Вычисление «в лоб» работает за <math>O(T^2)</math>. Однако есть способ сделать это за <math>O(T \log T)</math>.
Метод основан на теореме Хинчина — Колмогорова (она же Винера-Хинчина), утверждающей, что автокорреляционная функция сигнала есть фурье-образ его спектральной плотности мощности. Поскольку для дискретных сигналов для вычисления их спектров существует алгоритм быстрого преобразования Фурье, имеющий порядок сложности <math>O(T \log T)</math>, то имеется возможность ускорить вычисление автокорреляционной функции за счет вычисления спектра сигнала, затем его мощности (квадрата модуля) и затем обратного фурье-преобразования.
Суть способа состоит в следующем. Можно сделать некое обратное взаимно однозначное преобразование данных, называемое преобразованием Фурье, которое поставит им во взаимно однозначное соответствие набор данных в другом пространстве, называемом пространством частот (частотный спектр сигнала --- набор спектральных амплитуд ). Вместо прямого вычисления автокорреляционной функции на наших исходных данных можно произвести соответствующую ей операцию над соответствующими данными в пространстве частот Фурье-спектра, что делается за линейное время O(T) — вычислению автокорреляционной функции в пространстве частот соответствует вычисление мощностей частот возведением в квадрат модулей спектральных амплитуд. После этого мы по полученным спектральным мощностям восстановим соответствующие им в обычном пространстве значения автокорреляционной функции. Вычисление спектра по функции и обратно делается с помощью быстрого преобразования Фурье за <math>O(T \log T)</math>, вычисление спектральной плотности мощности в пространстве частот — за O(T). Таким образом, мы получили выигрыш по времени при вычислениях.
Подготовка. Вычитаем из ряда среднее арифметическое. Преобразуем в комплексные числа. Дополняем нулями до <math>2^k</math>. Затем дописываем в конец ещё <math>2^k</math> нулей.
Вычисление. Автокорреляционная функция вычисляется с помощью быстрого преобразования Фурье и прямо пропорциональна первым <math>n</math> элементам последовательности
- <math>\Psi(\tau) \sim \operatorname{Re} \operatorname{fft}^{-1}\left(\left|\operatorname{fft}(\vec x)\right|^2\right)</math>
Квадрат комплексного модуля берётся поэлементно: <math>\left|\vec a\right|^2 = \left\{ \operatorname{Re}^2 a_i + \operatorname{Im}^2 a_i \right\}</math>. Если нет погрешностей вычисления, мнимая часть будет равна нулю. Коэффициент пропорциональности определяется из требования <math>\Psi(0)=1</math>.
См. также
- Теорема Хинчина-Колмогорова
- Корреляционная функция
- Взаимнокорреляционная функция
- Периодическая функция
- Корреляция
- Критерий Дарбина — Уотсона
- Дисперсия случайной величины
- Свёртка (математический анализ)
Примечания
Ссылки
