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

Алгоритмы БПФ основаны на том, что при уменьшении длины последовательности решения задачи также уменьшается, но не пропорционально, а гораздо больше.

Пусть сигнал x(n) имеет N отсчетов, причём N=2m.

Разобьем сигнал на две последовательности:

Тогда спектры этих последовательностей будут определены как:

Тогда общий спектр будет выглядеть как:

Этот алгоритм называется БПФ с прореживанием по времени. Число отсчетов в этом алгоритме не зря выбрано как степень числа 2. Это позволяет разбивать последовательность к двухточечной преобразования Фурье:

рис. 25 Вычисления 8-точечного БПФ в трех каскадах с использованием прореживания по времени

Пример вычисления БПФ для 8 отсчетов Дискретное преобразование Фурье:

ФормулаЭйлера: e jθ= cos θ + j sin θ

Обратная ДПФ: