Другая распространенная форма алгоритма БПФ при условии, что N – равно степени 2 – алгоритм БПФ с прореживанием по частоте.
Разобьем входную последовательность x(n) на две равные последовательности.
x1(n)=x(n); n=0, 1, 2, … , (N/2)-1
x2(n)=x(n+N/2); n=0,1,2, … , (N/2)-1
Тогда:
Учитывая, что
Запишем выражение (*) отдельно для четных и нечетных отсчетов ДПФ:
Из выражений (**) и (***) видно, что четные и нечетные отсчеты ДПФ можно получить из N/2 – точечных ДПФ последовательностей f(n) и g(n), равных:
Т.о. снова вычисление N – отсчетов ДПФ удалось свести к вычислению двух (N/2) – точечных ДПФ
Описанную методику можно применить повторно и каждая из (N/2) – точечных ДПФ в виде комбинации двух (N/4) – точечных ДПФ, и т.д.
Отличия алгоритма БПФ с прореживанием по частоте, от алгоритма БПФ с прореживанием по времени.
1. При прореживании по времени входные отсчеты – в двоично-инверсном порядке следования, а входные в прямом. При прореживании по частоте – наоборот, входные – в прямом, выходные – в инверсном.
2. Несколько иная базовая комбинация:
Сходство алгоритмов:
1. В общих случаях требуется примерно
Операций.
2. Операции могут быть выполнены с замещениями.