Прореживание по частоте

Рассмотрим теперь другую, совершенно особую фор­му алгоритма быстрого преобразования Фурье — проре­живание по частоте. Эту форму алгоритма независимо друг от друга нашли Санди, Кули, Стокхем и др. Пусть функция f_l с четным числом точек N разделена на две последовательности по N/2 точек каждая, например, g_l и h_l где g_l образована из первых N/2 точек f_l, а h_l обра­зована из последних N/2 точек f_l . Формально можно за­писать

(5.51)

N-точечное ДПФ, обозначенное F_k , теперь может быть записано в значениях g_l и h_l :

(5.52)

(5.53)

Теперь рассмотрим четные и нечетные отсчеты F_k раз­дельно (отсюда и название - прореживание по частоте). Заменив в (5.53) k на 2k, получим

(5.54)

а заменив в (5.53) k на 2k+1, получим

(5.55)

Выражения (5.54) и (5.55) представляют собой (N/2) -точечные ДПФ от функций и . Таким образом, найден другой путь для того, чтобы вы­разить вычисления N-точечного ДПФ через результаты двух (N/2)-точечных ДПФ. На рис. 5.14 эта редукция показана для N = 8, а рис. 5.15 и 5.16 показывают, как выполняются последовательные деления па меньшие ДПФ до тех пор, пока число точек в подпоследователь­ностях делится на 2.

Рис. 5.16 представляет собой диаграмму для вычисления ДПФ в восьми точках, полно­стью сведенного к комплексному сложению и умножению. Как и прежде, количество вычислений оказывается пропорциональным . Интересно отметить, что рис. 5.16 имеет тот же вид, что и рис. 5.10, соответствующий слу­чаю прореживания по времени, однако коэффициенты в обоих графах различны.

В случае прореживанй по ча­стоте они следуют в естественном порядке. Вычисления опять могут быть произведены с замещением. Видоизменение рис. 5.16, приведенное на рис. 5.17, имеет тот же вид, что и рис. 5.8, но другие коэффициен­ты. Более сложная модификация показана на рис. 5.18, который, подобно рис. 5.10, соответствует форме алгорит­ма, не требующей двоично-инверсной перестановки вход­ного и выходного сигналов или коэффициентов, но в то же время невыполнимой с замещением. Наконец, на рис. 5.19 показана модификация, соответствующая алгоритму, ко­торый подходит для памяти с последовательной выбор­кой, подобно рис. 5.12, но уже с двоично-инверсной пере­становкой выходных, а не входных отсчетов.

Рис. 5.14. Восьмиточечное ДПФ, сведенное к двум четырехточечным ДПФ с помощью прореживания по частоте

В выражениях (5.50,а) и (5.50,6) прореживание по времени было обобщено на случай, когда множители N произвольны. Подобное обобщение может быть сделано и для прореживания по частоте. В результате получим

(5.56 а)

где

(5.56 б)

Рис. 5.15. Восьмиточечное ДПФ, редуцированное до четырех двух­точечных ДПФ

Эти выражения иллюстрируются рис. 5.20,а для случая N=6, р=2 и рис. 6.20,б —для случая N = 6, р = 3.

Рис. 5.16. Восьмиточечное ДПФ, полностью сведенное к комплексным умножениям и сложениям путем повторного прореживания по часто­те (здесь входные отсчеты следуют в нормальном порядке, так же как и коэффициенты, а выходные отсчеты - в двоично-инверсном порядке)

Рис. 5.17. Видоизменение рис. 5.16, для которого входные отсчеты и коэффициенты должны быть представлены в двоично-инверсном, а выходные отсчеты - в нормальном порядке

Рис. 5.18. Видоизменение рис. 5.16, при котором не нужна двоично-инверсная перестановка, но вычисления не могут быть сделаны с замещением.

Рис. 5.19. Видоизменение рис. 5.16, при котором сохраняется струк­тура от участка к участку.

Рис. 5.20. Прореживание по частоте для шеститочечного ДПФ

а) р=2; б) р=3.