Быстрое преобразование Фурье(самостоятельно)

(1.50)

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

Дата добавления: 2014-01-04