Вычисление корреляционных функций при помощи БПФ

Вычисление корреляционных функций при помощи БПФ является, особенно для длинных числовых рядов, в десятки и сотни раз более быстрым методом, чем последовательными сдвигами во временной области при больших интервалах корреляции. Суть метода вытекает из формул (6.21) для АКФ и (6.25) для ВКФ. Учитывая, что АКФ можно рассматривать как частный случай ВКФ при одном и том же сигнале, процесс вычисления рассмотрим на примере ВКФ для сигналов x(k) и y(k) с числом отсчетов К. Он включает:

1. Вычисление БПФ спектров сигналов x(k) → X(k) и y(k) → Y(k). При разном количестве отсчетов более короткий ряд дополняется нулями до размера большего ряда.

2. Вычисление спектров плотности мощности W_xy(k) = X*(k) Y(k).

3. Обратное БПФ W_xy(k) → B_xy(k).

Отметим некоторые особенности метода.

При обратном БПФ, как известно, вычисляется циклическая свертка функций x(k) ③ y(k). Если число отсчетов функций равно К, число комплексных отсчетов спектров функций также равно К, равно как и число отсчетов их произведения W_xy(k). Соответственно, число отсчетов B_xy(k) при обратном БПФ также равно К и циклически повторяется с периодом, равным К. Между тем, при линейной свертке полных массивов сигналов по формуле (6.18) размер только одной половины ВКФ составляет К точек, а полный двусторонний размер составляет 2К точек. Следовательно, при обратном БПФ с учетом цикличности свертки произойдет наложение на главный период ВКФ ее боковых периодов, как и при обычной циклической свертке двух функций.

На рис. 6.11 приведен пример двух сигналов и значения ВКФ, вычисленные линейной сверткой (В1ху) и циклической сверткой через БПФ (В2ху). Для исключения эффекта наложения боковых периодов необходимо дополнить сигналы нулями, в пределе, до удвоения количества отсчетов, при этом результат БПФ (график В3ху на рисунке 6.11) полностью повторяет результат линейной свертки (с учетом нормировки на увеличение количества отсчетов).

Рис. 6.11

В1 – линейная свертка, В2 – БПФ без продления сигналов нулями,
В3 – БПФ с продлением сигналов нулями

На практике число нулей продления сигналов зависит от характера корреляционной функции. Минимальное количество нулей обычно принимается равным значимой информационной части функций, т.е. порядка (3-5) интервалов корреляции.