6.5. Программа расчета БПФ на ФОРТРАНе

Чтобы лучше усвоить основные идеи БПФ, полезно рассмотреть простую, составленную на ФОРТРАНе программу расчета БПФ с прореживанием по времени. Текст этой программы, заимствованный у Кули, Льюиса и Уэлча, приведен на фиг. 6.8. Входная последовательность представляет собой массив А, размером до 1024 комплексных чисел.

Фиг. 6.8. Составленная на ФОРТРАНе программа БПФ с основанием 2 при прореживании по времени, выполняемого с замещением (взята у Кули, Льюиса и Уэлча).

Фактический размер БПФ равен , причем  указывается в операторе обращения к подпрограмме. Все операторы от DO 7 I = 1, NM1 до оператора с меткой 7 предназначены для выполнения двоично-инверсной перестановки элементов входного массива. Остальные операторы используются для вычисления непосредственно БПФ и образуют три вложенных цикла. С помощью первого (внешнего) цикла выполняется  этапов, другой цикл предназначен для выполнения базовых операций в пределах каждого этапа, а третий цикл (внутренний) необходим для вычисления степеней , используемых при выполнении базовых операций в пределах одного этапа. Для вычисления степеней  используется рекуррентное соотношение (6.15), причем синусы и косинусы непосредственно вычисляются лишь для нахождения по приращениям. По утверждению Кули, Льюиса и Уэлча, при таком подходе (в случае, когда ) требуется всего на 15% больше операций (типа комплексных сложений или умножений), чем при использовании таблицы, содержащей все коэффициенты . Из фиг. 6.8 видно, насколько просто может быть запрограммирован алгоритм БПФ.

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

Таблица 6.2