5.2. Алгоритм Герцеля

Существует много методов вычисления ДПФ для отдельной частоты . Самым простым из всех является непосредственное применение (5.2). Это требует прове­дения N комплексных умножений и N комплексных сло­жений с использованием N коэффициентов . Обыч­но эти коэффициенты могут быть восстановлены из запомненной таблицы отсчетов одной четверти периода синусоидального колебания. Комплексное умножение тре­бует проведения четырех действительных умножений и двух действительных сложений, а комплексное сложе­ние— двух действительных сложений, так что общий объем вычислений, заключенный в выражении (5.2), составляет

, (5.35)

где —время, требуемое для действительного умноже­ния; — время, требуемое для действительного сложе­ния; — время, требуемое для других операций при обработке, и М — число различных вычисляемых частот­ных коэффициентов.

Другим алгоритмом для вычисления коэффициента на отдельной частоте является алгоритм Герцеля, осно­ванный на подходе с позиций цифровой фильтрации. Рассмотрим сначала фильтр с единственным комплексным полюсом при :

(5.36)

Здесь впервые вводится фильтр с комплексными коэффи­циентами, но с ним не связаны какие-либо принципиаль­ные трудности, особенно в том случае, когда фильтруют­ся комплексные данные. Подадим на вход фильтра по­следовательность х(пТ), для которой желательно вы­числить X(kΩ). Так как z-преобразование от х(пТ) есть Х(z), то выходной сигнал фильтра будет равен

(5.37)

И, в частности, когда , выходной сигнал определяется как вычет в полосе :

(5.38)

Но поскольку

,

То можно видеть, что

. (5.39)

Применение такого фильтра для вычисления преобра­зований Фурье не дает экономии в вычислительных опе­рациях, хотя оно уменьшает требуемую память для коэффициентов. Однако, если переписать (5.36) как

, (5.40)

можно прийти к реализации цифрового фильтра, пока­занной на рис. 5.5. Поскольку значение выходного сигнала фильтра необходимо иметь только при , то нет нужды выполнять действия той части цепи, что находит­ся справа от пунктирной линии при любом п, за исклю­чением случая п = N. Таким образом, требуемые опера­ции состоят из N умножений действительных коэффици­ентов на комплексные данные и 2N комплексных сложе­нии. По сравнению с ними объемом заключительных операций можно пренебречь, если число отсчетов велико.

Рис. 5.5. Цифровой фильтр для вычисления одной точки ДПФ с помощью алгоритма Герцеля.

Если пересчитать все к операциям над действительными числами, то получим

(5.41)

где есть время, требуемое для особых операций в алго­ритме Герцеля. Если, однако, частоты, при которых вы­числяются Х(kΩ), могут быть сгруппированы парами как k и N-k, то можно получить дополнительную экономию, поскольку только нуль фильтра на рис. 5.5 различен для этих двух частот. Поэтому, если частоты могут быть та­ким путем сгруппированы в пары, то

(5.42)

Откуда видно, что алгоритм Герцеля дает экономию при­мерно в 4 раза по сравнению с прямым способом вычис­ления по (5.2). Для действительных чисел как прямой метод, так и метод Герцеля дают дополнительную экономию.