Важно отметить, что, хотя (6.18) содержит две суммы по
точек, каждая из этих сумм не является
-точечным ДПФ, так как
каждой из сумм стоит
а не
Объединяя две суммы в (6.18) и используя соотношение
получим
Рассмотрим теперь отдельно четные и нечетные
обозначив через
суммы соответственно четных и нечетных точек, так что
Нетрудно видеть, что (6.20) и (6.21) являются
-точечными
в случае (6.20) — от суммы первой и последней половины входной последовательности, а в случае (6.21) — от произведения
на разность первой и второй половины входной последовательности. В отличие от (6.19), суммы в (6.20) и (6.21) соответствуют
-точечным ДПФ потому, что
Таким образом, на основании (6.20) и (6.21) с
можно вычислить путем формирования последовательностей
затем вычисления
, наконец, вычислением
-точечных ДПФ от этих двух последовательностей. Процедура, даваемая выражениями (6.20) и (6.21), иллюстрируется рис. 6.15 для случая восьмиточечного ДПФ.
Рис. 6.15. Направленный граф, иллюстрирующий разложение
-точечного ДПФ на два
-точечных ДПФ в алгоритмах с прореживанием по частоте
Рис. 6.16. Направленный граф, иллюстрирующий разложение восьмиточечного ДПФ на четыре двухточечных для алгоритмов с прореживанием по частоте
Поступая так же, как и в случае вывода алгоритма с прореживанием по времени, замечаем, что так как
является степенью
четно, и, следовательно,
-точечные ДПФ могут быть найдены путем вычисления по отдельности четных и нечетных выходных точек этих ДПФ. Как и в случае исходного разложения, приводящего к (6.20) и (6.21), это делается путем объединения первой и второй половины входных точек для каждого из
-точечных ДПФ и затем вычисления
-точечных ДПФ. Направленный граф, соответствующий этому шагу для восьмиточечного ДПФ, показан на рис. 6.16. Для восьмиточечного ДПФ вычисления теперь сводятся к вычислению двухточечных ДПФ, которые, как мы видели раньше, получаются путем сложения и вычитания входных точек. Таким образом, двухточечные ДПФ на рис. 6.16 могут быть замечены вычислениями, показанными на рис. 6.17 так, что в результате для восьмиточечного ДПФ получим граф, изображенный на рис. 6.18.
Рис. 6.17. Направленный граф двухточечного ДПФ на последней ступени разложения для алгоритмов с прореживанием по частоте
Рис. 6.18. Направленный граф при полном разложении восьмиточечного ДПФ для алгоритмов с прореживанием по частоте
Подсчитывая число арифметических операций на рис. 6.18 и обобщая на случай
убеждаемся, что вычисления по рис. 6.18 требуют
комплексных умножений и
комплексных сложений. Таким образом, общее количество вычислений для алгоритмов с прореживанием по частоте и с прореживанием по времени одинаково.