Реализация алгоритма БПФ с прореживанием по времени

1. Выполнить предварительную перестановку входных значений (бит-инверсию), как показано на рис. 6.

2. Программа строится на основе трех вложенных циклов. Внешний цикл – перебор этапов, число которых L =log₂ N. Счетчик цикла l в этом случае изменяется от 0 до L -1 (использование оператора цикла for). Удобно для перебора этапов использовать переменную M, не вводя дополнительно переменную L. M изменяется от 2 до N путем умножения на 2 старого значения при переходе на следующий этап: M=2∙M (использование оператора цикла while).

3. Средний цикл определяется перебором доменов на этапе. Счетчик цикла d, определяющий номер домена, изменяется от 0 до D-1 (D= N/M). Переход в новый домен осуществляется увеличением d на 1.

4. Внутренний цикл – перебор бабочек в домене. Счетчик цикла k, определяющий номер бабочки, изменяется от 0 до K - 1 с шагом 1 (K= M/2).

5. Операции внутреннего цикла – операции бабочки (рис. 3, ф. (4) и (6), только N необходимо заменить на M). После вычисления , сначала необходимо получить нижнюю точку бабочки (разность), затем верхнюю (сумма). Ответьте на вопрос – почему? Из рис. 5 видно, что абсолютный номер точки для верхних точек бабочек складывается из суммы d · M + k. Соответственно нижние точки бабочек имеют абсолютный номер, отстоящий от номера верхней точки на M/2, т.е. d · M + k + M /2.

6. Полученные коэффициенты Фурье необходимо нормализовать (разделить на N).

Date: 2016-05-23; view: 871; Нарушение авторских прав