 |
Процедура объединения. Граф «Бабочка»
|
|
|
|
Теперь рассмотрим вторую половину спектра 
, 
:
| (8) |
Рассмотрим подробнее множитель
 .
| (9) |
Учтем что
 ,
| (10) |
тогда выражение (10) справедливо для любого целого 
, тогда (9) можно записать с учетом (10):
 .
| (11) |
Рассмотрим теперь поворотный коэффициент в (8):
 .
| (12) |
Тогда выражение (8) с учетом (11) и (12) принимает вид:
| (13) |
Таким образом, окончательно можно записать:
| (14) |
Выражение (14) представляет собой алгоритм объединения при прореживании по времени. Данную процедуру объединения можно представить в виде графа (рисунок 3), который называется «Бабочка».
Рисунок 3: Процедура объединения на основе графа «Бабочка»
БПФ прореживанием по частоте
Снова запишем выражение для дискретного преобразования Фурье сигнала 
:
| (1) |
В алгоритме БПФ с прореживанием по времени производилось разделение исходного сигнала в соответствии с двоично-инверсной перестановкой. И получали первую и вторую половину спектра. В алгоритме с прореживанием по частоте наоборот исходный сигнал делится пополам, т.е. 
и 
. Тогда выражение (1) можно переписать:
| (2) |
Учтем что
| (3) |
Тогда
| (4) |
Рассмотрим теперь четные отсчеты спектра 
| (5) |
Учтем что
| (6) |
Тогда
| (7) |
Таким образом, четные отсчеты спектра рассчитываются как ДПФ суммы первой и второй половины исходного сигнала.
Рассмотрим теперь нечетные отсчеты спектра 
| (8) |
Окончательно выражение для четных и нечетных отсчетов спектра:
| (9) |
Прокомментируем полученный результат, опираясь на все вышесказанное и с оглядкой на алгоритм с прореживанием по времени. При делении сигнала на четные и нечетные отсчеты, в алгоритме с прореживанием по времени получали первую и вторую половины спектра. В данном случае алгоритм с прореживанием по частоте наоборот по первой и второй половине сигнала позволяет рассчитать четные и нечетные спектральные отсчеты (поэтому и называется прореживание по частоте). Разница алгоритмов еще и в том, что при прореживании по времени умножение на поворотные коэффициенты производилось после ДПФ четной и нечетной последовательности, а в данном алгоритме умножение на поворотные коэффициенты производится до ДПФ.
|
|
|
Граф алгоритма с прореживанием по частоте
Граф бабочка для алгоритма с прореживанием по частоте представлен на рисунке 4:
Рисунок 4: Граф бабочка для алгоритма БПФ с прореживанием по частоте
Поворотные коэффициенты в алгоритме с прореживанием по частоте полностью совпадают с поворотными коэффициентами алгоритма БПФ с прореживанием по времени.
Поворотные коэффициенты
Рассмотрим подробнее поворотные коэффициенты 
.
На первом уровне требуется всего один поворотный коэффициент 
, это означает, что на первом уровне расчета спектра операции умножения не требуются (умножения на 
называются тривиальными, так как при умножении на множитель остается неизменным или меняет свой знак на противоположный).
На втором уровне имеем два поворотных коэффициента:
| (17) |
Умножение на мнимую единицу также можно считать тривиальным, так как реальные и мнимые части комплексного числа просто меняются местами и изменяют свой знак.
На третьем уровне имеем уже 4 поворотных коэффициента:
| (18) |
Графически поворотные коэффициенты можно представить как векторы на комплексной плоскости:
Рисунок 5: Поворотные коэффициенты алгоритма БПФ с прореживанием по времени при N=8
Можно заметить, что на всех уровнях объединения количество поворотных коэффициентов удваивается, причем все поворотные коэффициенты предыдущего уровня объединения присутствуют и на следующем уровне. Таким образом для того чтобы перейти на следующий уровень необходимо между поворотными коэффициентами текущего уровня вставить поворотные коэффициенты следующего. Графически для перехода на следующий уровень при N =16 необходимо дополнить рисунок 5 как это показано на рисунке 6. Серые вектора показывают поворотные коэффициенты, которые будут присутствовать на последнем уровне при 
, которых нет при 
.
|
|
|
Рисунок 6: Поворотные коэффициенты алгоритма БПФ с прореживанием по времени при N=16
Необходимо также отметить, что все поворотные коэффициенты за исключением нулевого 
находятся в нижней полуплоскости комплексной плоскости.
|
|
|
