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

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

4.1. Постановка задачи

Пусть обозначает последовательность , получаемую в результате дискретизации сигнала с ограниченной полосой частот. Требуется получить алгоритм для вычисления

(4.1.1)

где и . Напомним, что уравнение (4.1.1) описывает ДПФ последовательности . Искомый алгоритм называется быстрым преобразованием Фурье [1]. Поскольку этот глгоритм был первоначально описан Кули и Тьюки [2], то его также называют алгоритмом Кули—Тьюки. Ниже предполагается, что . При этом общность не теряется, так как N выбирается достаточно большим для того, чтобы удовлетворять теореме , т. е. , где В — полоса частот сигнала , Гц, a L — его длительность. Случай N, отличный от , обсуждается в [1, 3, 4, 5].