Um procedimento computacional que é mais eficiente que o método direto é chamado Algoritmo de Goertzel. Esse método é um exemplo de como a periodicidade de WN pode ser utilizada para reduzir o número de operações aritméticas.
Para construir o algoritmo de Goertzel,
note-se inicialmente que
(4) |
(5) |
(6) |
A equação (6) é claramente
uma convolução discreta da sequência finita x(n), 0£n£N-1,
com a sequência .
Assim, yk(n) pode
ser visto como a resposta do sistema, com resposta impulsional ,
a uma entrada x(n).
Em particular, X(k) é o valor da
saída quando n = N
O diagrama de fluxo de um sistema com tal resposta impulsional é mostrado na fig.1, reproduzida de Oppenheim e Schafer, Digital Signal Processing,1975.
É possível porém manter
esta simplificação enquanto o número de multiplicações
é reduzido por um fator 2. Para isso, note-se que a função
de transferência do sistema da fig.1 é dada por:
(7) |
(8) |
Somente duas multiplicações
e quatro adições são necessárias para o cálculo
dos pólos do sistema. Como deseja-se calcular yk(N),
a multiplicação complexa pelo coeficiente -
necessária para o cálculo do
zero só precisa ser realizada após a N-ésima iteração.
Tem-se então um total de 2N multiplicações
reais e 4N adições reais para os pólos e quatro multiplicações
e adições reais para o zero, totalizando 2(N+2) multiplicações
reais e 4(N+1) adições reais, ou seja, aproximadamente metade
das multiplicações necessárias no método direto.
Tanto no método direto quanto no
método de Goertzel, não é necessário avaliar
todos os N valores de X(k). Pode-se em geral avaliar X(k) para quaisquer
M valores de k. Nesse caso o número de operações é
proporcional a NM, o que torna esse esquema interessante para M pequeno.
No entanto, algoritmos mais sofisticados, nos quais o número de
operações é proporcional a N log2
N, sendo N uma potência de 2, estão disponíveis. Assim,
quando M< log2 N tanto o método direto
quanto o de Goertzel podem ser, de fato, os mais eficientes, mas quando
todos os N valores de X(k) são requeridos, os algoritmos considerados
a seguir são bem mais eficientes do que tanto o método direto
quanto o método de Goertzel.