3.1.3. Разновидности дпф

Кратковременное дискретное преобразование Фурье. В задачах спектрального анализа нестационарных сигналов используется, так называемое, кратковременное преобразование Фурье (КПФ)

, (50)

где w[n] – весовая последовательность. КПФ зависит от двух параметров: целочисленного временного индекса n и значения непрерывной частоты . КПФ является периодической функцией с периодом 2. Модуль часто называют спектрограммой.

Дискретизация КПФ в частотной области в точках приводит к дискретному кратковременному преобразованию Фурье, которое можно трактовать как R-точечное ДПФ функции (x[n-m]w[m]), N  R:

,

, . (51)

При равенстве размеров ДПФ и массива анализируемых данных N = R получаем взвешенное ДПФ

. (52)

Многомерное преобразование Фурье. При решении ряда задач (например, обработки сигналов в многопозиционной радиолокации) приходится иметь дела с многомерными дискретными сигналами. Так двумерный дискретный сигнал – это функция, определенная на совокупности упорядоченных пар чисел Для многомерной или M-мерной последовательности с опорной областью можно определить многомерное или М-мерное ДПФ

,

,

где - диагональная матрица.

Пример. Рассмотрим обратное, двумерное ДПФ - точечной последова­тельности, заданной соотношением

, .

Последовательность выражается следующим образом

3.2. Алгоритмы вычисления дискретного преобразования Фурье

Существует два класса алгоритмов вычисления преобразований Фурье: обычное дискретное преобразование Фурье (ДПФ) и быстрое дискретное преобразование Фурье (БПФ).

1. Дискретным преобразованием Фурье условно называют непосредственное вычисление формул (33, 34). При этом допускают все известные способы распараллеливания векторно-матричных операций. Если пользоваться обычным правилом умножения матрицы на вектор, то вычисления векторов x и X требуют N ² операций комплексного умножения и N(N - 1) операций комплексного сложения.

2. Быстрое преобразование Фурье включает набор эффективных алгоритмов, предназначенных для вычисления ДПФ. В основе алгоритмов лежит стратегия divide et impera (разделяй и властвуй). Идея БПФ по своей природе является алгебраической и заключается в следующем. Величина N, определяющая длину входной последовательности отсчетов, раскладывается на сомножители, затем вычисляются отдельные ДПФ меньших длин, чем N, из которых потом формируется выходная последовательность. Происходит так называемое расщепление исходного алгоритма на комбинацию подобных алгоритмов меньшего размера.

Положим, что для N-точечной последовательности нужно вычислить ее ДПФ и что N представляет собой составное число

,

где {r_i } – это набор множителей числа N, которые не обязательно являются простыми. Алгоритм расщепления для вычисления такого ДПФ через комбинацию преобразований меньших размеров потребуют число операций, пропорциональное . Такие алгоритмы называются алгоритмами быстрого преобразования Фурье . Наиболее важный частный случай имеет место, когда . Для БПФ число операций в этом случае пропорционально .

Разберем возможность сокращения числа операций при вычислении ДПФ на примере двух сомножителей N = N₁ N₂.