Алгоритмы бпф с прореживанием по частоте. Вычисление обратного дпф.

Алгоритмы БПФ с прореживанием по частоте. Это другая, наиболее распространенная форма алгоритмов эффективного вычисления ДПФ при условии, что В этом случае входная последовательность разбивается на две подпоследовательности, содержащие по отсчетов каждая. Причём, первая подпоследовательность состоит из первых отсчетов исходной последовательности а вторая – – из остальных отсчетов т. е.

(1.165)

При таком разбиении N-точечное ДПФ исходной последовательности x(n) можно записать в виде:

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

(1.166)

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

(1.167)

так как для четных k

(1.168)

так как для k – нечетных,

Из этих выражений видно, что четные и нечетные отсчеты ДПФ N – точечной последовательности x(n) можно получить из -точечных ДПФ последовательностей и равных:

(1.169)

Таким образом, на основании всего рассмотренного N-точечное ДПФ можно вычислить путем формирования последовательностей и и вычисления -точечных ДПФ от этих двух последовательностей. Эта процедура для иллюстрируется на рисунке 1.28.

Описанную методику можно применить повторно и представить каждую из -точечных ДПФ в виде комбинации двух -точечных ДПФ. Для это будет соответствовать переходу от четырехточечных ДПФ к двухточечным, причем двухточечные ДПФ вычисляются прямым методом (рис. 1.29 и 1.30).

Рис. 1.28. Вычисление ДПФ N = 8 на основе двух 4-х точечных

Рис. 1.29. Вычисление ДПФ для N = 8 на основе четырех 2-х точечных

Сравнив полученный алгоритм с алгоритмом БПФ с прореживанием по времени, можно выявить два очевидных различия между ними.

1. При прореживании по времени порядок следования входных отсчетов двоично-инверсный, выходных – прямой, а при прореживании по частоте – наоборот. Однако это отличие несущественно, поскольку в обоих алгоритмах порядок следования входных отсчетов может быть прямым, а выходных – двоично-инверсным и наоборот.

2. При прореживании по частоте базовая операция выполняется несколько иначе. Здесь комплексное умножение выполняется после сложения – вычитания (рис. 1.31).

Рис. 1.30. Направленный граф алгоритма БПФ с прореживанием по частоте для N = 8

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

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

Вычисление обратного ДПФ. Для вычисления обратного ДПФ можно без каких-либо изменений использовать уже рассмотренные алгоритмы БПФ. Обратное ДПФ N-точечной последовательности определяется следующим образом:

(1.170)

Выполнив операцию комплексного сопряжения правой и левой частей данного выражения и умножив его на N, получим

(1.171)

Правая часть полученной формулы представляет собой ДПФ последовательности и поэтому она может быть вычислена с использованием одного из рассмотренных алгоритмов БПФ. Искомая последовательность получается, если еще раз взять комплексно-сопряженное с этим выражением и разделить его на N, т. е.

(1.172)

Таким образом, алгоритмы БПФ обеспечивают выполнение как прямого, так и обратного ДПФ.