Введение в численные методы. Дулов Е.Н. - 56 стр.

    Приведем один из возможных вариантов реализации алгоритма БПФ для числа
точек, являющегося степенью двойки. Алгоритм предполагает, что операции с
комплексными числами уже реализованы.
    1) Выборка из N = 2 q дискретных значений подвергается пересортировке, как
показано в Таблице 1. Значения записываются в массив A , всего N элементов в
массиве. Массив A должен быть предназначен для хранения комплексных чисел.
Диапазон индексов массива 0,.., N − 1 .
    2) Вводится целочисленная переменная m , пробегающая значения от 1 до q .
Начальное значение m = 1 .
    3) Производится обработка элементов массива по следующей схеме:
            1               2πi                                     
     A[i ] =  A[i0 ] + exp       ( (         ) )          
                                  i − i \ 2 m ⋅ 2 m ⋅ 2 q −m  A[i1 ]     (9.13)
            2               N                                      

     i0 , i1 получаются заменой (m − 1) -го бита в двоичной записи числа i на 0 и 1,

соответственно.
     i \ 2 m означает целочисленное деление, когда вещественная часть результата

деления отбрасывается. Выражение i − (i \ 2 m )⋅ 2 m представляет остаток от деления i
на 2 m , что практически в любом языке программирования записывается как одна
операция. Отметим также, что операции умножения и деления на числа, являющие
степенью двойки, в двоичной системе удобно представлять через сдвиги битов
числа влево и вправо, соответственно.
    Хотя выражение (9.13) описывает операцию над одним массивом, удобно
вводить вспомогательный массив, в котором хранится результат операций над A .
По окончанию обработки всего массива A , в него переписывается вспомогательный
массив.
    4) Увеличивается на единицу m . Если m > q , то основная работа алгоритма
закончена, массив A содержит Фурье-образ исходной выборки, умноженной на N .
В противном случае выполняется переход на п.3.
    5) Выполняется деление всех элементов на N .




                                                                   56