Пора дополнить раздел 2 и описать алгоритм прореживания по частоте (DIF, Decimation In Frequency). Именно на нем отчетливо видно, как снизить необходимое число арифметических операций до упомянутого выше значения.
Разобьем входную последовательность x[k] (-T≤n≤T, T=(N-1)/2, N=3q) на три:
x0[k]=x[k],
x+[k]=x[k+N/3],
x-[k]=x[k-N/3], -t≤k≤t,
Найдем значения для F[3n], F[3n+1] и F[3n-1]:
Обозначим выражения в скобках за X0[k], X+[k] и X-[k]. Как видно, вычисление УТ БПФ от N отсчетов сводится к нахождению данных величин, после чего к каждому из них применяется УТ БПФ пониженной степени. Процедуру можно продолжать рекурсивно.
Граф «бабочка» совпадает с тем, который получился для алгоритма с прореживанием по времени, но ее нужно читать в обратную сторону.
