Алгоритмы БПФ с прореживанием по времени и по частоте

Быстрые алгоритмы БПФ являются “обратимыми”, т.е. вычисления по графу БПФ (см., например, рис. 3.1) могут выполняться как “слева направо”, так и “справа налево”.

В первом случае алгоритм БПФ основан на “бабочке” вида:

(8.11)

и называется алгоритмом с прореживанием по времени (алгоритм Кули- Тьюки) [21,25].

Во втором случае (при вычислении по графу “справа налево”) алгоритм БПФ производится на основе бабочки вида:

(8.12)

и называется алгоритмом БПФ с прореживанием по частоте (алгоритмом Сэнди-Тьюки). Такие алгоритмы были впервые опубликованы в середине 60-х годов [21,25].

Графы подобных базовых операций приведены на рис. 8.2, а) и б) соответственно.

а)

б)

Рис. 8.2. Графы базовых операций БПФ с прореживанием по времени (а) и по частоте (б)

Заметим, что для алгоритма БПФ с прореживанием по частоте не выполняется двоично-инверсная перестановка элементов вектора X перед первой итерацией, но зато необходимо переставлять элементы векторов результата по закону двоичной инверсии.

8.5. Алгоритм БПФ по основанию r (N = r^m, r³3)

До сих пор мы рассматривали БПФ только для случая, когда N = 2^m . На практике, однако, достаточно часто возникает необходимость вычисления ДПФ при , где r отлично от 2 (например, N=125=5³, N= 625=5⁴; N=27 и т.д.).

Для таких случаев несколько позднее Сэнди и Радемахором были разработаны алгоритмы БПФ, основу которых составляют базовые операции “бабочка” следующего вида для алгоритмов с прореживанием по времени:

(8.13)

и для алгоритмов с прореживанием по частоте соответственно:

(8.14)

Графически каждая из представленных базовых операций может быть изображена так, как это указано на рис.8.3.

а)

б)

Рис. 8.3. Графы базовых опeраций БПФ по основанию r

Остановимся на правилах перестановки элементов в таком случае. На входе выполняется перестановка по закону r - ичной инверсии, т.е. на входе элементы вектора X объединяются в подвектора из r - элементов, причём шаг выборок составит:

С помощью системы рекуррентных соотношений, подобных выражению (8.9), алгоритм БПФ для N=r^M с прореживанием по времени можно описать

следующим образом [6,15]:

(8.15)

где - матрица ДЭФ порядка r (т.е. ДПФ для вектора N сводится к ряду ДПФ размера r над блоками), k=(n)_{mod l}, n текущий индекс элемента вектора ( ), ,

, , ,

Граф БПФ для N=9 имеет вид, представленный на рис.8.4

Рис.8.4. Граф БПФ