|
|
то сразу будет понятно, как работает быстрое (причем оба - с прореживанием по частоте и с прореживанием по времени).
Вот алгоритм для прореживания по времени: основан он на том, что N-точечное ДПФ можно посчитать через 2 штуки N/2-точечных ДПФ, взятых от четных отсчетов и от нечетных.
Считаем ДПФ для четных отсчетов, и считаем ДПФ для нечетных отсчетов. Получаем 2 спектра - и их объединяем в один спектр при помощи оператора, в просторечии называемого "бабочка" :
X1(k)------*------+------> X(k)
\ /
\ /
\/
/\
/ \
/ \
X2(k)------*------+------> X(k+N/2)
W(k,N) -1
смысл его такой - результаты DFT нечетных (X1) и результаты DFT четных выборок (X2) объединяются в общий результат при помощи элементарных операций - одно умножение на коэфф. W(k,N), одно умножение на -1 и два сложения.
То есть - конкретный пример. Надо посчитать 16-точечное DFT методом FFT. Его можно представить как 2 8-ми точечных. Каждое из 8-ми точечных представляется как 2 4-х точечных. 4-х точечные DFT считаются крайне просто. В результате получаем необходимость подсчета 4-х 4-хточечных DFT и 16-ти "бабочек" (2 раза по 4 бабочки чтобы перейти от 4-х 4-хточечных к 2-м 8-миточечным, и 8 бабочек для перехода от двух 8-ми точечных к конечному 16-титочечному).
Этим достигается сильное уменьшение количества необходимых вычислений. (против обычного DFT).
А литературу какую - посмотри практически любой учебник по ЦОС - там это расписано.
E-mail: 
info@telesys.ru
