Другая распространенная форма алгоритма БПФ (при условии, что N равно степени 2) – так называемый алгоритм БПФ с прореживанием по частоте. В этом варианте алгоритма БПФ входная последовательность разбивается на две последовательности, содержащие по отсчетов каждая, следующим образом: первая последовательность состоит из первых отсчетов последовательности , а вторая – из остальных отсчетов последовательности , т.е.
. (1.38)
При таком разбиении -точечное ДПФ последовательности можно записать в виде:
. (1.39)
Учитывая, что , получим:
. (1.40)
Запишем выражения отдельно для четных и нечетных отсчетов ДПФ:
(1.41)
Из выражения (1.41) видно, что четные и нечетные отсчеты ДПФ можно получить из -точечных ДПФ последовательностей и , равных:
(1.42)
Таким образом, снова вычисление N-точечного ДПФ удалось свести к вычислению двух -точечных ДПФ. На рис. 1.20 эта методика иллюстрируется для случая N = 8.
Описанную методику можно применить повторно и представить каждое из -точечных ДПФ в виде комбинации двух -точечных ДПФ. Переход от четырехточечных ДПФ (рис. 1.20) к двухточечным ДПФ с последующим прямым вычислением двухточечных ДПФ показан на рис. 1.21, 1.22.
Сравнение алгоритмов (рис. 1.17 и 1.22) позволяет выявить два очевидных различия между ними. Во-первых, при прореживании по времени порядок следования входных отсчетов двоично-инверсный, а выходных отсчетов – прямой и, наоборот, при прореживании по частоте (рис.1.22). Однако это отличие кажущееся, поскольку в обоих алгоритмах порядок следования входных отсчетов может быть прямым, а выходных – двоично-инверсным и наоборот.
Говорят, что алгоритмы БПФ с прореживанием по времени и прореживанием по частоте полностью изоморфны. Второе отличие заключается в несколько ином выполнении базовой операции (см. рис. 1.23 и 1.18): при прореживании по частоте комплексное умножение выполняется после сложения – вычитания.
Легко заметить и сходство между алгоритмами с прореживанием по времени и по частоте. В обоих случаях при вычислении ДПФ требуется около N log2 N операций, вычисления могут быть проведены с замещением и должно быть предусмотрено выполнение двоичной инверсии.
Обсуждавшиеся до сих пор БПФ представляют алгоритм БПФ по основанию 2, то есть их вычисление основано на 2-точечных базовых операциях типа «бабочка». Подразумевается, что число точек в БПФ должно быть степенью числа 2. Если число точек в БПФ является степенью числа 4, то БПФ может быть разделено на множество 4-
точечных ДПФ (рис. 1.24). Такое преобразование называ