4. Быстрое преобразование Фурье

Как видно из формулы (8), для того чтобы найти частотный спектр сигнала, представленного N отсчетами, нужно сделать N² операций умножения. Для выполнения вычислительной работы такого объема требуется значительное время. Например, при N=4096 компьютер типа IBM PC AT затратит на вычисление спектра около 30 минут. Это обстоятельство долгое время препятствовало широкому применению преобразования Фурье для обработки данных. Ситуация изменилась в 1965 году, когда Джеймс Кули (фирма IBM) и Джон Тьюки (Bell Laboratories) разработали очень эффективный алгоритм вычисления, получивший известность как быстрое преобразование Фурье.

Метод основан на симметрии и периодичности тригонометрических функций в формуле (8). В самом деле, если в качестве N выбрать степень двойки, то в сумме (8) будет много одинаковых членов, которые не имеет смысла каждый раз вычислять. Как оказывается, можно обойтись всего N*log2N операциями умножения. При N=4096 (размер буферной памяти АЦП-101SK, АЦП ФК-4225) алгоритм БПФ работает примерно в 300 раз быстрее чем решение задачи "в лоб".

5. Функция корреляции

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

Функция автокорреляции R(t ) и функция взаимной корреляции R12(t ) определяются для действительных U(t), U1(t) и U2(t) следующим образом:

(10)

Корреляционная функция характеризует степень связи между сигналом и его сдвинутой на t копией – R(t ) или между двумя различными сигналами – R12 (t ).

Некоторые свойства корреляционной функции:

а) автокорреляционная функция периодического процесса есть периодическая функция с тем же периодом;

б) R(t) – действительная, четная функция и имеет максимум при t=0, равный мощности сигнала;

в) если скрытая в шумах периодическая функция отсутствует, то R(t) асимптотически стремится к квадрату среднего значения (к нулю, если сигнал не имеет постоянной составляющей);

г) функция автокорреляции и спектр мощности связаны преобразованием Фурье:

(11)

Поскольку корреляционная функция действительная и четная, ее преобразование Фурье (спектр мощности) является действительной, неотрицательной, четной функцией частоты.

Как видно из (11) и (12), автокорреляционная функция зависит только от квадратов модулей комплексных амплитуд спектрального разложения сигнала, следовательно, автокорреляционная функция не содержит информации о фазовом спектре сигнала. Таким образом, одной и той же автокорреляционной функции соответствует множество сигналов с различными фазовыми спектрами. Поэтому по автокорреляционной функции восстановить форму сигнала невозможно, хотя некоторые параметры сигнала можно оценить, например, задержку одного импульса относительно другого, соотношение амплитуд, длительность.

Взаимнокорреляционная функция отличается от автокорреляционной прежде всего тем, что частично сохраняет информацию о фазовом спектре сигналов в виде разности фаз соответствующих гармоник, хотя взаимной однозначности между сигналами и их функцией взаимной корреляции и в этом случае нет.

По аналогии с (11), (12) функция взаимной корреляции имеет своим Фурье-изображением так называемый взаимный энергетический спектр мощности:

(13)

где <=> означает соответствие относительно преобразования Фурье.

Как видно из (10), время, необходимое для численного расчета корреляционной функции дискретизированного сигнала, как и в случае преобразования Фурье, примерно равно N². Поэтому корреляционные функции удобнее вычислять "в обход" с помощью алгоритма БПФ, пользуясь соотношениями (12), (13). Сначала нужно вычислить спектр или спектры для R₁₂(t ), затем найти его модуль и сделать обратное преобразование Фурье.