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

Другая распространенная форма алгоритма БПФ (при условии, что 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.23 и 1.18): при прореживании по частоте комплексное умножение выполняется после сложения – вычитания.

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

Обсуждавшиеся до сих пор БПФ представляют алгоритм БПФ по основанию 2, то есть их вычисление основано на 2-точечных базовых операциях типа «бабочка». Подразумевается, что число точек в БПФ должно быть степенью числа 2. Если число точек в БПФ является степенью числа 4, то БПФ может быть разделено на множество 4-

точечных ДПФ (рис. 1.24). Такое преобразование называ