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

В БПФ с прореживанием по частоте выделяют два слагаемых, соответствующих двум следующим друг за другом половинам исходной последовательности:

.        (4.5)

Из второй суммы можно выделить множитель

.

После выделения множителя ±1 комплексные экспоненты в обеих суммах становятся одинаковыми и их можно вынести за скобки:

,                                        (4.6)                    

.                            (4.7)           

Записанные суммы представляют собой ДПФ суммы и разности половин исходной последовательности, при этом разность перед вычислением ДПФ умножается на комплексные экспоненты .

Таким образом, при вычислении БПФ с прореживанием по частоте из исходной последовательности  длиной N получают две последовательности  и  длиной N/2:

,                                       (4.8)

.                               (4.9)

ДПФ последовательности  дает спектральные отсчеты с четными номерами, ДПФ последовательности  - с нечетными номерами:

,                               (4.10)

.                       (4.11)

Рисунок 4.3 – вычисление 8-точечного ДПФ с использованием двух 4-х точечных ДПФ путем прореживания по частоте

Рисунок 4.4 – условное обозначение «бабочки» и ее структурная схема при прореживании по частоте

Свойства БПФ

1. Наибольшее ускорение вычислений при применении БПФ достигается при длине исходной последовательности, равной целочисленной степени 2. Снижение вычислительных затрат по сравнению с использованием ДПФ в этом случае составляет  раз.

2. Экономия вычислительных затрат достигается за счет объединения слагаемых, умножаемых на одинаковые множители и трансформации некоторых множителей в 1 или –1.

3. Если длина исходной последовательности – простое число (3, 5, 7, 11), вычисление ДПФ возможно только по формуле ДПФ либо за счет дополнения исходной последовательности нулями.

4. БПФ не является приближенным алгоритмом. При отсутствии вычислительных погрешностей он дает точно такой же результат, что и ДПФ.

5. Алгоритм БПФ предназначен для одновременного расчета всех спектральных отсчетов. Если необходимо получить отдельные гармоники, то может оказаться удобной формула ДПФ или известный алгоритм Герцеля.

Литература

Сергиенко А.Б. Цифровая обработка сигналов / А.Б. Сергиенко. – Спб.: БХВ -Петербург, 2011. - 768 с.