3.2.4 Aproximação de Funções — Análise de Fourier — A Transformada Discreta de Fourier

1. A Transformada Discreta de Fourier

Para problemas reais, tais como processamento de sinais, não precisamos conhecer todo o domínio transformado, obtido pela transformada contínua. Ao contrário, as funções podem ser representadas por conjuntos finitos de valores discretos. Em geral, queremos transformar apenas alguns pontos amostrados.

Seja o intervalo\([0,t]\) dividido em \(N\) subintervalos com largura \(\Delta t = \frac{T}{N}\) . Especificamos os dados em\(n=0,1,2,\ldots, N – 1\) . A transformada discreta de Fourier é definida como

\( F_k = \sum_{n=0}^{N-1} f_n e^{-i k \omega_0 n}\)

para \(k=0,1,2,\ldots, N – 1 \) . De forma análoga, a transformada inversa na forma discreta é

\( f_n = \sum_{k=0}^{N-1} F_k e^{i k \omega_0 n}\)

As duas equações acima podem ser utilizadas para calcular tanto a transformada de Fourier direta quando a inversa para dados discretos. Como temos um conjunto de transformações de \(n\) elementos no domínio transformado para os \(n\) pontos amostrados, a transformada de Fourier discreta requer \(N^2\) operações complexas.

Para facilitar a implementação computacional da TFD, utilizaremos a identidade de Euler para decompormos as fórmulas em funções trigonométricas

\( e^{\pm i a} = cos(a) \pm i sin(a)\)

para reescrevermos a transformada e a sua inversa como

\( F_k = \frac{1}{N} \sum_{n=0}^{N} \left[ f_n cos(k \omega n) – i f_n sin(k \omega n) \right]\)

e
\( f_n = \sum_{k=0}^{N} \left[ F_k cos(k \omega n) + i F_k sin(k \omega n) \right]\)

onde \(\omega = \frac{2 \pi}{N}\) .

 

2. Implementação

A transformada de Fourier discreta:

def dft(inputF):
    """
    Return a list with the coeficients of Discrete Fourier Transform.
 
    f = dft(inputF)
 
    INPUT:
    * f: list with discrete points of frequency-domain
 
    return: list discrete points of time-domain
 
    Author: Pedro Garcia [sawp@sawp.com.br]
    see: http://www.sawp.com.br
 
    License: Creative Commons
             http://creativecommons.org/licenses/by-nc-nd/2.5/br/
 
    Mar 2011
    """
    F = map(complex, inputF)
    m = len(F)
    f = [complex(0.0) for i in xrange(m)]
    omega = 2.0 * pi / m
    for k in xrange(m):
        (real, imag) = (0.0, 0.0)
        for n in xrange(m):
            angle = k * omega * n
            real = real + F[n] * cos(angle)
            imag = imag + F[n] * sin(angle)
        f[k] = complex(real, imag)
    return f

e sua inversa:

def idft(inputf):
    """
    Return a list with the coeficients of Inverse Discrete Fourier Transform.
 
    F = idft(inputf)
 
    INPUT:
    * f: list with discrete points of time-domain
 
    return: list discrete points of frequency-domain
 
    Author: Pedro Garcia [sawp@sawp.com.br]
    see: http://www.sawp.com.br
 
    License: Creative Commons
             http://creativecommons.org/licenses/by-nc-nd/2.5/br/
 
    Mar 2011
    """
    f = map(complex, inputf)
    m = len(f)
    F = [complex(0.0) for i in xrange(m)]
    omega = 2.0 * pi / m
    for k in xrange(m):
        (real, imag) = (0.0, 0.0)
        for n in xrange(m):
            angle = k * omega * n
            real = real + f[n] * cos(angle) / m
            imag = imag - f[n] * sin(angle) / m
        F[k] = complex(real, imag)
    return F

Estas funções estão disponíveis em http://www.sawp.com.br/code/interpolation/dft.py assim como um exemplo de como utilizá-las.

 

3. Copyright

Este documento é disponível sob a licença Creative Commons. As regras dos direitos de cópia deste conteúdo estão acessíveis em http://creativecommons.org/licenses/by-nc-nd/2.5/br/.

References

[1]Anthony Ralston and Philip Rabinowitz, A First Course in Numerical Analysis (2nd ed.), McGraw-Hill and Dover, (2001).
[2]N.B Franco, Cálculo Numérico, Pearson Prentice Hall (2006).