7.8. Программирование алгоритма

После того как мы получили рекуррентные уравнения, описывающие БПФ, программирование выполняется очень просто. Заметим, что вычисления включают три цикла длиной соответственно. Самый длительный среди них цикл по поскольку диапазон изменения и и I зависит от На фиг. 7.14 показана блок-схема вычислений, соответствующая рекуррентным уравнениям (7.22). Руководствуясь ей, легко написать программу или подпрограмму на ФОРТРАНе для вычисления БПФ. На фиг. 7.15 а приведен текст подпрограммы представляющей самое простое воплощение алгоритма БПФ. Как следует из комментариев, несколько первых операторов выполняют двоичную инверсию. Остальные касаются выполнения БПФ с прореживанием по времени.

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

Согласно определению, подпрограмма выполняет вычисления, соответствующие формуле (7.16). Для вычисления ДПФ в

(кликните для просмотра скана)

Фиг. 7.15 a. Программа на ФОРТРАНе реализации основного алгоритма ДПФ, заданного соотношением (7.16). (см. скан)

соответствии с формулами (7.17) и (7.18) дополнительно к EASY вызывается подпрограмма SCALE (фиг. 7.16). Наконец, для выполнения ОДПФ в соответствии с формулами (7.19) и (7.20) перед исполнением EASY вызывается подпрограмма SORT (фиг. 7.17).

(кликните для просмотра скана)

Фиг. 7.16. Подпрограмма для умножения на результатов вычисления по программе

Фиг. 7.17. Подпрограмма для выполнения двоичной инверсии при вычислении ОДПФ с помощью программы ДПФ EASY.