Алгоритмы бпф с прореживанием по частоте. Вычисление обратного дпф.
Алгоритмы
БПФ с прореживанием по частоте.
Это другая, наиболее распространенная
форма алгоритмов эффективного вычисления
ДПФ при условии, что
В этом случае входная последовательность
разбивается на две подпоследовательности,
содержащие по
отсчетов каждая. Причём, первая
подпоследовательность
состоит из первых
отсчетов исходной последовательности
а вторая –
–
из остальных
отсчетов
т. е.
(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)
Таким образом, алгоритмы БПФ обеспечивают выполнение как прямого, так и обратного ДПФ.