Алгоритм БПФ с прореживанием по частоте

Другая распространенная форма алгоритма БПФ при условии, что 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. Операции могут быть выполнены с замещениями.