6.1. АЛГОРИТМ ГЕРЦЕЛЯ

Алгоритмом Герцеля [6] называется вычислительная процедура, несколько более эффективная, чем прямой метод. Этот алгоритм является примером того, как можно использовать периодичность последовательности для сокращения вычислений. Убедимся, что дискретное преобразование Фурье можно рассматривать, как отклик цифрового фильтра, который может быть построен так, чтобы уменьшить число арифметических операций.

Чтобы вывести алгоритм Герцеля, заметим, что

Это, конечно, непосредственный результат периодичности Согласно (6.4) можно умножать правую часть (6.1) на

Таким образом,

Для удобства записи определим последовательность

Из (6.5) и (6.6) следует, что Выражение (6.6) является, как нетрудно видеть, дискретной сверткой последовательности конечной длины с последовательностью Следовательно, можно рассматривать как отклик системы с импульсной характеристикой на входной сигнал . В частности, является значением выхода при Система с импульсной характеристикой изображена на рис. 6.1.

В силу того что вход — комплексные величины вычисление каждого нового значения требует четырех действительных умножений и четырех действительных сложений. Так как для вычисления необходимо вычисление всех промежуточных значений использование схемы рис. 6.1 потребует действительных умножений и действительных сложений при вычислении для каждого конкретного значения к. Таким образом, эта схема несколько менее эффективна, чем прямой метод. Однако можно заметить, что метод рис. 6.1 не требует ни вычисления, ни запоминания коэффициентов так как эти величины вычисляются посредством рекуррентного процесса, предполагаемого схемой рис. 6.1.

Возможно сохранение этого упрощения при уменьшении числа умножений в 2 раза. Чтобы увидеть, как это можно сделать, заметим, что передаточная функция системы рис. 6.1 равна

Умножая числитель и знаменатель на коэффициент получим

Направленный граф на рис. 6.2 соответствует передаточной функции (6.8).

Требуется только два умножения для реализации полюсов этой системы, так как коэффициенты действительны и не следует считать умножением. Как и прежде, для реализации полюсов требуется четыре сложения. Так как необходимо вычислить только комплексное умножение на требуемое для

реализации нуля, не нужно выполнять на каждой нтерадни разностного выражения, а только после итерации. Таким образом, необходимо действительных умножений и действительных сложений для полюсов плюс четыре действительных сложения для нуля. Следовательно, полное число вычислений равно действительных умножений и действительных сложений, что приблизительно вдвое меньше по числу умножений по сравнению с прямым методом.

Рис. 6.1. Направленный граф системы первого порядка для рекурсивного вычисления комплексных величин

Рис. 6.2. Направленный граф системы второго порядка для рекурсивного вычисления (алгоритм Герцеля)

В этой более эффективной схеме опять-таки имеется преимущество в том, что — единственные коэффициенты, которые нужно вычислить и запомнить. Множество коэффициентов опять вычисляется неявно с помощью схемы рис. 6.2.

Чтобы убедиться в дополнительном преимуществе этой цепи, рассмотрим вычисление z-преобразования от в сопряженных точках единичной окружности, т. е. вычисление Непосредственно проверяется, что цепь вида рие. 6.2, требуемая для вычисления имеет те же самые полюсы, что и цепь на рис. 6.2, а коэффициент, необходимый для реализации нуля, является комплексно-сопряженным по отношению к коэффициенту схемы рис. 6.2. Так как нуль реализуется только на последней итерации, то умножений и сложений, требуемых для полюсов, можно использовать для вычисления двух значений ДПФ. Таким образом, для вычисления дискретного преобразования Фурье во всех точках при использовании алгоритма Герцеля требуется приблизительно умножений и приблизительно сложений. Однако, как и при прямом методе, количество вычислений все еще пропорционально

При прямом методе или методе Герцеля нет необходимости вычислять все различных значений . В общем случае можно вычислить для любых М значений к. В этом случае общее число вычислений пропорционально Эти схемы привлекательны при малом М. Имеются более хитроумные алгоритмы, Для которых число вычислений пропорционально при являющемся степенью 2. Поэтому при М, меньшем как метод Герцеля, так и прямой метод могут быть наиболее эффективными методами. Но когда требуются все значения

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