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

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

При таком разбиении N-точечное ДПФ последовательности можно записать в виде

Учитывая, что , получим

Запишем выражения отдельно для четных и нечетных отсчетов ДПФ:

Фиг. 6.9. Переход от восьмиточечного ДПФ к двум четырехточечным ДПФ при прореживании по частоте.

Из выражений (6.21) и (6.23) видно, что четные и нечетные отсчеты ДПФ можно получить из -точечных ДПФ последовательностей и , равных

Таким образом, снова вычисление -точечного ДПФ удалось свести к вычислению двух -точечных ДПФ. На фиг. 6.9 эта методика иллюстрируется для случая N = 8.

Описанную методику можно применить повторно и представить каждое из -точечных ДПФ в виде комбинации двух -точечных ДПФ. На фиг. 6.10 и 6.11 показан переход от четырехточечных ДПФ (фиг. 6.9) к двухточечным ДПФ с последующим прямым вычислением двухточечных ДПФ.

Сравнение алгоритмов, иллюстрированных на фиг. 6.3 и 6.11, позволяет выявить два очевидных различия между ними. Во-первых, при прореживании по времени порядок следования входных отсчетов двоично-инверсный, а выходных — прямой и наоборот при прореживании по частоте (фиг. 6.11). Однако это отличие кажущееся, поскольку в обоих алгоритмах порядок следования входных отсчетов может быть прямым, а выходных — двоично-инверсным и наоборот. Второе отличие заключается в несколько ином выполнении базовой операции (см. фиг. 6.12 и 6.4): при прореживании по частоте комплексное умножение выполняется после сложения — вычитания.

Фиг. 6.10. Переход от четырехточечных ДПФ на фиг. 6.9 к двухточечным ДПФ.

Фиг. 6.11. Полный направленный граф восьмиточечного ДПФ с замещением и прореживанием по частоте.

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

Легко заметить и сходство между алгоритмами с прореживанием по времени и по частоте. В обоих случаях при вычислении ДПФ требуется около N log2 N операций, вычисления могут быть проведены с замещением и должно быть предусмотрено выполнение двоичной инверсии. В разд. 6.8 будет строго показано, почему эти, казалось бы, различные алгоритмы имеют такое сходство. Будет рассмотрен единый подход к БПФ, для которого алгоритмы с прореживанием по времени и по частоте оказываются частными случаями. С помощью такого подхода проанализирован также случай, когда N является составным целым числом, но не обязательно равным степени 2.