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

Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — это одно из преобразований Фурье, широко применяемых валгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать дифференциальные уравнения в частных производных и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье.

Прямое преобразование:

Обратное преобразование:

Обозначения:

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

· — измеренные значения сигнала (в дискретных временных точках с номерами , которые являются входными данными для прямого преобразования и выходными для обратного;

· — комплексных амплитуд синусоидальных сигналов, слагающих исходный сигнал; являются выходными данными для прямого преобразования и входными для обратного; поскольку амплитуды комплексные, то по ним можно вычислить одновременно и амплитуду, и фазу;

· — обычная (вещественная) амплитуда k-го синусоидального сигнала;

· — фаза k-го синусоидального сигнала (аргумент комплексного числа);

— индекс частоты. Частота k-го сигнала равна , где — период времени, в течение которого брались входные данные.

Из последнего видно, что преобразование раскладывает сигнал на синусоидальные составляющие (которые называются гармониками) с частотами от N колебаний за период до одного колебания за период. Поскольку частота дискретизации сама по себе равна N отсчётов за период, то высокочастотные составляющие не могут быть корректно отображены — возникает муаровый эффект. Это приводит к тому, что вторая половина из N комплексных амплитуд, фактически, является зеркальным отображением первой и не несёт дополнительной информации.

Свойства ДПФ:

1. Дискретное преобразование Фурье обладает свойством линейности: линейной комбинации дискретных сигналовсоответствует линейная комбинация их ДПФ.

2. Коэффициент представляет собой среднее значение (постоянную составляющую) всех дискретных отсчетов сигнала

.

3. Число различных коэффициентов равно числу отсчетов за длительность сигнала ; при коэффициент .

Быстрое преобразование Фурье (БПФ, FFT) — алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем , требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющий сложность

.

Многократно сократить число операций позволяет быстрое преобразование Фурье (БПФ), обеспечивающее вычисление коэффициентов ДПФ за меньшее число операций. В основу БПФ положен принцип разбиения заданной последовательности отсчетов дискретного сигнала на несколько промежуточных последовательностей. Для этого число отсчетов N разделяется на множители (например, ). Затем определяются спектры этих промежуточных последовательностей и через них находится спектр всего сигнала. В зависимости от состава, числа и порядка следования указанных множеств можно создать различные алгоритмы БПФ. В цифровой технике удобно обрабатывать сигнальные последовательности со значениями N, являющимся степенью числа два (4, 8, 16 и так далее). Это позволяет многократно делить входную последовательность отсчетов на подпоследовательности.

Соотношения , и ,

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

Вычисление коэффициентов ДПФ последовательности из N отсчетов по алгоритмам БПФ требует примерно операций умножения. Алгоритмы БПФ сокращают число операций по сравнению с алгоритмами ДПФ в раз. Например, при количестве отсчетов , имеем и сокращение числа операций составляет . При очень больших массивах отсчетов входного сигнала выигрыш в скорости обработки может достигать нескольких тысяч.

Таким образом, в алгоритмах БПФ выполняются операции сложения и вычитания с умножением одного из компонентов на экспоненциальный множитель . Эту базовую для БПФ операцию очень удобно представлять сигнальным графом, называемым в цифровой технике «бабочкой».

Рис. 9.18. Операция «бабочка», используемая

при реализации алгоритма БПФ

Базовые операции и показывают, как два входных числа А и В объединяются для получения двух выходных чисел X и Y. Для метода прореживания во времени базовая операция изображается «бабочкой», представленной на рис. 9.18. Надпись у стрелки, идущей вверх, означает умножение на величину В.

Построим граф вычисления БДНФ с прореживанием во времени для N=4 (рис. 9.19).

Рис. 9.19. Граф для вычисления БПФ при N=4

Учитывая, что , , получаем согласно приведенному графу

На рис. 9.20 показан граф вычисления БДПФ с прореживанием во времени для N=8.

Рис. 9.20. Граф для вычисления БПФ при N=8