 |
БПФ с прореживанием по времени
|
|
|
|
Рассмотрим идею БПФ с прореживанием по времени (decimation in time, DIT) на примере деления набора отсчетов пополам.
Итак, пусть N — четное число. Выделим в формуле дискретного преобразования Фурье два слагаемых, соответствующих элементам исходной последовательности с четными и нечетными номерами:
.
Введем обозначения у(m) = х(2m) и z(m) = x(2m+l), а также вынесем из второй суммы общий множитель 
. (1)
Две суммы в (5.13) представляют собой ДПФ последовательностей { у(m) } (отсчеты с четными номерами) и { z(m) } (отсчеты с нечетными номерами). Каждое из этих ДПФ имеет размерность N/2. Таким образом,
, (1)
где 
и 
— ДПФ соответственно последовательностей отсчетов с четными и нечетными номерами:
,
.
Так как ДПФ размерности N/2 дает лишь N/2 спектральных коэффициентов, непосредственно использовать формулу (2) можно только при 0<=n<N/2. Для остальных n (N/2<=n<N) следует воспользоваться периодичностью спектра дискретного сигнала (и, соответственно, периодичностью результатов ДПФ):
, 
.
С учетом этого при n>=N/2 формула (2) представляется в виде
.(3)
Процесс вычисления 8-точечного ДПФ путем разбиения его на два 4-точечных ДПФ иллюстрируется на рис. 1.
Рис. 1. Вычисление 8-точечного ДПФ с помощью двух 4-точечных ДПФ
 |
Блоки, выполняющие на рис. 1 объединение результатов двух ДПФ, требуют дополнительных комментариев. Каждый такой блок имеет два входных и два выходных сигнала. Один из входных сигналов умножается на комплексную экспоненту wk, после чего суммируется со вторым входным сигналом и вычитается из него, формируя таким образом два выходных сигнала. Это соответствует реализации формул (2) и (3). Данная операция получила название «бабочки» (butterfly). Расшифровка ее структуры (слева)представлена на рис. 2.
|
|
|
Рис. 2. Условное обозначение «бабочки» БПФ с прореживанием по времени и ее структурная схема (справа)
Оценим количество операций, необходимое для вычисления ДПФ указанным способом. Каждое из двух ДПФ половинной размерности требует N2/4 операций. Кроме того, при вычислении окончательных результатов каждый спектральный коэффициент Z(n) умножается на экспоненциальный комплексный множитель. Это добавляет еще N/2 операций. Итого получается 2 N/4 + N/2 = N(N + l)/2, что почти вдвое меньше, чем при вычислении ДПФ прямым способом.
Если N/2 тоже является четным числом (то есть если N делится на 4), можно продолжить описанную процедуру, выразив результат через четыре ДПФ размерности N/4. Это позволяет еще больше сократить число требуемых вычислительных операций.
С использованием условного обозначения, показанного на рис. 3, а., на рис. 3,б показан полный алгоритм восьмиточечного БПФ. Приняв какие-то конкретные значения а(0),..., a(7), нетрудно на собственном опыте убедиться, насколько легче найти значения b(0)..... b(7) по этому алгоритму, чем непосредственно по формуле ДПФ.
Рис.3 Условное обозначение одного преобразования (а) и возможный алгоритм быстрого преобразования Фурье (б)
Процесс полного преобразования можно условно разбить на три шага. На первом происходит преобразование входной последовательности 
в соответствии с двоичной инверсией номеров и последующим вычислением первого частичного преобразования согласно выражению «бабочка». На втором происходит вычисление второго частичного преобразования, на третьем – полного преобразования 
. Аналогично для вычисления БПФ 256 точек требуется 8 шагов, а 1024точки – 10 шагов, а в общем 
, где L- целое число и равно количеству шагов – этапов расчета.
|
|
|
