Алгоритм Гёрцеля
Способ вычислить одну частотную составляющую сигнала; дешевле полного БПФ, когда нужна лишь горстка тонов.
Опубликовал его Джеральд Гёрцель в 1958 году. Алгоритм считает один отсчёт дискретного преобразования Фурье рекурсивным фильтром второго порядка: одно умножение и два сложения на отсчёт, а после последнего отсчёта — короткий завершающий шаг, дающий амплитуду. Состояние — всего два числа.
БПФ выдаёт сразу все частоты, но если нужны только восемь из них, выигрывает Гёрцель. Это и есть задача тонового набора: цифра DTMF — пара частот из четырёх нижних и четырёх верхних, и восьми фильтров Гёрцеля на недорогом DSP хватает, чтобы понять, какую клавишу нажали. Тот же приём встречается в гитарных тюнерах и в модемах, ждущих определённую несущую. Как и у БПФ, при попадании тона не в центр бина возникает спектральная утечка.