§ 5. Алгоритмы вычисления ДПФ. Быстрое преобразование Фурье (БПФ)

А. Обзор методов вычисления ДПФ.

Если вычисляется -точечной последовательности при небольшом числе точек N или же в последовательности имеется небольшое количество ненулевых ее значений, то целесообразно непосредственное использование для проведения расчетов формулы (3.39) ДПФ:

при .

То же самое относится и к выполнению операции ОДПФ по формуле (3.40):

при

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

Говоря о вычислении ДПФ, будем учитывать, что при решении задач управления и связи возникает необходимость в определении ДПФ последовательностей значения которых могут быть вещественными или могут быть комплексными.

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

Приближенно оценивают прямой метод вычисления ДПФ по количеству выполняемых арифметических операций следующим образом: считают,

что для вычисления ДПФ комплексной -точечной последовательности нужно произвести умножений и сложений вещественных чисел или умножений и сложений комплексных чисел [85]. Так как выполнение операций умножения более сложно, чем выполнение операций суммирования, иногда в качестве характерной величины берут лишь необходимое количество умножений.

В указанных выше случаях, т.е. тогда, когда вычисляется -точечной последовательности при небольшом N или же в последовательности имеется немного ненулевых ее значений, представляется эффективным вычисление ДПФ методом, основанным на применении так называемого алгоритма Герцеля ([156]; см. также [30, 85]). При применении этого метода может быть несколько уменьшено по сравнению с прямым методом количество выполняемых вычислительных операций и не требуется запоминания коэффициентов так как они определяются в ходе вычислений.

Начало широкому применению ДПФ было положено в науке и в технике, в особенности в области управления и связи, созданием методов быстрого вычисления -точечных последовательностей при больших Эти методы известны как методы быстрого преобразования Фурье (БПФ). Сейчас известен ряд различных методов выполнения БПФ. Толчком к их созданию явилось опубликование в 1965 г. работы [151], в которой было описано БПФ.

Особенностью БПФ является значительное, тем большее, чем большее сокращение количества выполняемых для вычисления ДПФ арифметических операций. Общее их количество считают здесь примерно равным что при больших N намного меньше, чем величина указанная для прямого метода. Метод БПФ основан на том, что вычисление -точечной последовательности сводится к вычислению ДПФ последовательностей длины, меньшей чем

В последние годы ведутся интенсивные работы по дальнейшему усовершенствованию БПФ и работы, направленные на то, чтобы получили практическое применение отличающиеся от традиционных алгоритмов БПФ новые перспективные алгоритмы быстрых вычислений ДПФ. Основное внимание при этом уделяется алгоритму Винограда преобразования Фурье Краткие сведения об этих модификациях БПФ будут приведены в разделе 3 § 5; о методах, используемых при разработке алгоритмов их выполнения, будет сказано в § 9 этой главы.

Рассмотрим методы вычисления ДПФ в том порядке, в каком они были упомянуты выше.