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 dividido em subintervalos com largura . Especificamos os dados em . A transformada discreta de Fourier é definida como

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

para . 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 elementos no domínio transformado para os pontos amostrados, a transformada de Fourier discreta requer 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 .

 

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.

 

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).