Transformada Discreta de Fourier – Algoritmo de Goertzel

Introdução

As transformadas discretas de Fourier ou DFTs (Discrete Fourier Transforms) permitem que o espectro de frequências de um sinal à qual essa transformada é aplicada seja disponibilizado para sistemas digitais ou computacionais. Elas transformam um sinal real, contínuo no tempo, amostrado adequadamente, numa decomposição discreta de suas frequências. Neste artigo técnico vamos abordar uma particularização da transformada conhecida por algoritmo de Goertzel (ou transformada de Goertzel).

.

A DFT de Goertzel

A transformada discreta de Goertzel é uma simplificação da DFT tradicional. Ela calcula o conteúdo espectral de uma única raia e não o espectro todo. Isso diminui consideravelmente o volume de cálculos necessários, podendo facilmente ser utilizado em aplicações práticas. Por exemplo, em telefonia digital é necessário realizar a detecção dos tons de linha, ocupado ou chamada. Também é necessário realizar a captura de teclas digitadas por usuários, quando esses acessam um serviço de computação digital do tipo URA (Unidade de Resposta Audível) ou semelhante. O sistema de tons das teclas do telefone é conhecido por sistema DTMF (Dual-Tone Multi-Frequency signaling). Para compreender melhor o sistema DTMF de telefonia, veja a Tabela 1, onde é mostrado como é composto o tom multi-frequencial de cada tecla do telefone.

Tabela 1 – Composição frequencial do teclado DTMF

.

Quando o DTMF foi criado, a detecção dos tons das teclas era realizada por meio de filtros analógicos passa-faixas sintonizados. Com a chegada dos sistemas digitais, essa detecção passou a ser realizada por técnicas de processamento digital de sinais usando-se o algoritmo de Goertzel. Para maiores detalhes consulte as referências [1] e [3].

Para ilustrar a diferença entre a transformada discreta de Fourier e a de Gortzel podemos observar nas figuras a seguir o resultado simulado de uma operação de DFT num sinal hipotético (Figura 1) e o cálculo da DFT de Goertzel para uma determinada frequência desse sinal (Figura 2).

 

.

Figura 1 – Espectro de um sinal hipotético

.

Figura 2 – DFT de Goertzel calculada no mesmo sinal hipotético

.

Observe que numa situação ideal, após o cálculo da DFT de Goertzel as demais frequências do espectro são totalmente suprimidas. Em situações reais, isto não é bem assim. Mas adiante serão abordados alguns cuidados que deverão ser tomados quando se utiliza esse algoritmo.

A seguir vamos mostrar as fórmulas resultantes do desenvolvimento do algoritmo de Goertzel. O desenvolvimento completo dessas fórmulas pode ser encontrado nas referências. O resultado da DFT de Goertzel é calculado em duas fases: A primeira em que se processam N amostras do sinal e a segunda em que se calcula o resultado final.

 

Primeira fase (Repetir N vezes)

Onde:

 

x(n) = amostra atual do sinal a ser processado;

z(2) = z(0) atrasado de duas amostras;

z(1) = z(0) atrasado de uma amostra;

z(0) = resultado acumulado da primeira fase;

coefk = 2 * cos(2 * π * k/N);

N = número de amostras a serem utilizadas no cálculo;

k = N * Fi/Fs => Fi = frequência desejada e Fs = frequência de amostragem.

 

Segunda fase (Cálculo final da amplitude na frequência desejada)

 

Ou então a magnitude:

 

A função a seguir, desenvolvida para o programa Scilab, implementa o algoritmo de Goertzel. O algoritmo é muito simples!

Observe que quanto mais k se aproximar de um número inteiro, maior a precisão na detecção da amplitude da frequência desejada. Para citar um exemplo, voltamos ao caso do DTMF. Como se trata de um sistema de telefonia, podemos pressupor que a taxa de amostragem do canal telefônico é de 8 kHz. Na referência [3], é apresentada a seguinte tabela exemplo para N = 105  e o “k” calculado para cada frequência do DTMF (Tabela 2).

 Tabela 2 – Valores de k para N = 105

.

Note que para 697 Hz o valor de k calculado é de 105 * 697 / 8.000 = 9,148 e foi truncado para 9. A detecção das frequências de DTMF com os valores calculados na Tabela 2 tem um erro máximo de ± 3,0% .

Tanto a escolha de N como k,  como tudo na vida real, é uma solução de compromisso. Quanto maior N, maior a resolução em frequência no espectro, maior a atenuação das frequências indesejadas e mais estreito o filtro para a frequência desejada. Quanto maior o N, maior o tempo de processamento que será necessário para calcular a DFT. Nas Figuras 3 e 4 são ilustradas duas situações onde a relação de k/N = 4, porém K e N diferentes em cada figura.

 

Figura 3 – Resposta em frequência da DFT de Goertzel p/ k = 1 e N = 4

 

Figura 4 – Resposta em frequência da DFT de Goertzel p/ k = 8 e N = 32

.

Conclusão

A DFT de Goertzel é um recurso muito interessante do ponto de vista de aplicação de processamento digital de sinais, pois realiza uma filtragem bastante seletiva e com baixo gasto de processamento. As aplicações em telefonia são as mais conhecidas e óbvias. Mas seu uso também pode ser interessante em sensores com excitação em corrente alternada senoidal, tais como sensores de posicionamento linear, ou sensores de massa, torque ou pressão, que utilizem pontes de Wheatstone.

 .

Saiba mais

Para um melhor embasamento teórico, recomendo a leitura dos artigos técnicos:

• Introdução ao Processamento Digital de Sinais – DSP – Parte 1;
• Processamento Digital de Sinais – DSP – Parte 2.

 

Referências

[1] Discrete Time Signal Processing – Allan V. Oppenheim, Ronald W. Schafer, John R. Buck

[2] The Scientist and Engineer’s Guide to Digital Signal Processing  – Steven W. Smith 

[3] Modified Goertzel Algorithm in DTMF Detection Using the TMS320C80

.

Esta obra, “Transformada Discreta de Fourier – Algoritmo de Goertzel“, de Henrique Frank W. Puhlmann, foi licenciada sob uma Licença Creative Commons Atribuição-NãoComercial-CompartilhaIgual 3.0 Não Adaptada.