4.9. Заключение

Основной задачей настоящей главы является вывод алгоритма БПФ. Рассматривался только одномерный алгоритм, когда исходные данные представляются в виде вектора. Из данных § 3.6 видно, что одномерный алгоритм БПФ можно применять раз для вычисления двумерного ДПФ, когда исходные данные представляются в виде матрицы размером . Существует метод вычисления двумерного ДПФ с помощью одномерного БПФ, когда матрица исходных данных записывается в виде вектора размером [14]. Такой подход применим и в более общем -мерном случае, .

Вывод алгоритма БПФ, приведенный в настоящей главе, основан на работе Кули и Тьюки [2]. Алгоритм БПФ можно также получить с помощью методов разбиения [22] и факторизации матриц [1, 23, 24]. Известен также ряд других модификаций БПФ [8], полученных Бреннером [15], Фишером [16], Синглтоном [3], Санде и Блюстейном [18]. Количественное сравнение четырех вариантов алгоритма БПФ, описанных в [2, 3, 15, 16], по времени

вычислений, объему памяти и точности проведено в [19] для выборок от до .

В заключение рассматривается несколько возможностей применения БПФ и приводятся соответствующие численные примеры. Обсуждение некоторых других методов, связанных с цифровой обработкой сигналов, дается в [1, 8, 11, 20, 21].