Способ уменьшения числа операций в алгоритме быстрого преобразования Фурье

摘要

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