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

Подведем итог. В этой работе были рассмотрены пути уменьшения вычислительных затрат при использовании ДПФ. Рассмотрены наиболее распространенные алгоритмы БПФ с прореживанием по времени и по частоте и показана эффективность данных алгоритмов.

Необходимо отметить, что алгоритмы БПФ не ограничиваются алгоритмом с прореживанием по времени и по частоте. Существует множество других алгоритмов, например, алгоритмы по основанию четыре, обобщенные алгоритмы для произвольных длин и т. д. Существует также алгоритм Винограда, обеспечивающий минимальное количество умножений из всех возможных алгоритмов. Но на практике наиболее широко используются именно алгоритмы по основанию два. Это обусловлено несколькими причинами:

• 1. Простота программной реализации алгоритмов и в тоже время высокая эффективность.
• 2. Выигрыши получаемые альтернативными алгоритмами БПФ незначительные по сравнению с алгоритмами по основанию два и нивелируются экспоненциально растущими вычислительными мощностями процессоров.

Все это переводит альтернативные алгоритмы БПФ в разряд «экзотики», и на практике как правило алгоритмы по основанию два являются оптимальным выбором. Однако если возникнет необходимость всегда можно обратится к литературе.

Есть ли у алгоритмов БПФ недостатки? Оказывается есть. В результате того что ускорение вычислений достигается за счет максимального использования данных рассчитанных на предыдущем этапе, в алгоритме БПФ происходит когерентное накопление ошибок округления при умножении и сложении. Однако данный эффект оказывает сколь-нибудь существенное влияние при арифметике с фиксированной точкой и представлении чисел с количеством разрядов менее 8-ми. При представлении чисел с плавающей точкой или 8-ми или большей разрядности данным эффектом можно пренебречь, так как он практически не повлияет на точность расчета спектра.