Grupo4 - FFT

A Transformada rápida de Fourier (em inglês Fast Fourier Transform, ou FFT) é um algoritmo que torna o cálculo da Transformada Discreta de Fourier (DFT) viável para a maior parte das aplicações.

Transformada Discreta de Fourier

Em muitas aplicações se tem informação sobre um conjunto de dados, ao invés de uma função contínua. A Transformada Discreta de Fourier transforma esse conjunto de dados em um conjunto de tamanho igual com informação sobre as frequências da função que satisfaz o conjunto de dados.

Para um conjunto de dados igualmente espaçados, pode-se, ao considerar os dados como um período de uma função periódica, cujo período normalmente é considerado entre $[-\pi ,\pi ]$ para facilitar o cálculo (e que pode sempre ser transformada em uma função nesse interválo), mostrar que a transformada discreta de Fourier pode ser dada pela equação:

$F_k=\sum _{n=0}^{N-1}{f}_n{e}^{-i2\pi nk/N}$

A sua inversa é, em paralelo ao caso da transformada contínua,

$f_n=\frac{1}{N}\sum _{n=0}^{N-1}{F}_k{e}^{i2\pi nk/N}$

A transformada também pode ser expressa em forma vetorial, como

$\overrightarrow{F}={\mathbf{𝐖}}^{\mathbf{𝐧}\mathbf{𝐤}}\overrightarrow{f}$ onde ${\mathbf{𝐖}}^{\mathbf{𝐧}\mathbf{𝐤}}$ é definido como

${\mathbf{𝐖}}^{\mathbf{𝐧}\mathbf{𝐤}}=\left[\begin{array}{cccc}{e}^{-2\pi i0\cdot 0/N}& e^{-2\pi i0\cdot 1/N}& \cdots & e^{-2\pi i0\cdot k/N}\\ e^{-2\pi i1\cdot 0/N}& e^{-2\pi i1\cdot 1/N}& \cdots & e^{-2\pi i1\cdot k/N}\\ ⋮& ⋮& \ddots & ⋮\\ e^{-2\pi in\cdot 0/N}& e^{-2\pi in\cdot 1/N}& \cdots & e^{-2\pi in\cdot k/N}\end{array}\right]$

O cálculo dessa expressão leva em torno de $N^2$ passos para o resultado. Uma amostra com 3,000 pontos precisa de 9,000,000 operações para a transformada ser obtida, tornando a DFT inviável para aplicações rápidas.

Transformada Rápida de Fourier

É possível calcular a transformada com $N{\log }_{2}N$ passos. Para isso se dispõe de um algoritmo chamado Transformada Rápida de Fourier. Considera-se um conjunto de pontos $N=2^p$ (com $p$ inteiro, então, da definição da DFT

$F_k=\sum _{n=0}^{N-1}{f}_n\cdot e^{-i\frac{2\pi }{N}\cdot k\cdot n}$

podemos dividir o somatório em 2:

$F_k=\sum _{n=0}^{N/2-1}{f}_{2n}\cdot e^{-i\frac{2\pi }{N}\cdot k\cdot 2n}+\sum _{n=0}^{N/2-1}{f}_{2n+1}\cdot e^{-i\frac{2\pi }{N}\cdot k\cdot (2n+1)}$

$F_k=\sum _{n=0}^{N/2-1}{f}_{2n}\cdot e^{-i\frac{2\pi }{N/2}\cdot k\cdot n}+e^{-i\frac{2\pi }{N}k}\sum _{n=0}^{N/2-1}{f}_{2n+1}\cdot e^{-i\frac{2\pi }{N/2}\cdot k\cdot n}$

$F_k=\sum _{n=0}^{N/2-1}{f}_{2n}\cdot e^{-i\frac{2\pi }{N/2}\cdot k\cdot n}+C(k)\sum _{n=0}^{N/2-1}{f}_{2n+1}\cdot e^{-i\frac{2\pi }{N/2}\cdot k\cdot n}$

onde a soma em vermelho é a parte par e a soma em azul é a parte ímpar da transformada. As duas somas tem o mesmo expoente, que agora é dividido por $N/2$. Desse expoente, é evidente a relação entre o ponto $k$ e o ponto $k+N/2$

$e^{-i\frac{2\pi }{N/2}\cdot k\cdot n}=e^{-i\frac{2\pi }{N/2}\cdot (k+N/2)\cdot n}=e^{-i\frac{2\pi }{N/2}\cdot k\cdot n}\cdot e^{-i\frac{2\pi }{N/2}\cdot N/2\cdot n}=e^{-i\frac{2\pi }{N/2}\cdot k\cdot n}\cdot 1$

Com essa relação, podemos ver que $F_k$ e $F_{k+N/2}$ tem o mesmo expoente e podem ser calculadas ao mesmo tempo. Mais que isso, a nova forma da transformada pode ser sucessivamente dividida, cada vez produzindo somas com limites menores.

Exemplo

Suponha que temos a função sinusoidal $a(t)=sin(2\pi \cdot 1Hz\cdot t)$ e fazemos quatro medidas no intervalo de 1 segundo, resultando em

$a_0=0.00$ $a_1=1.00$ $a_2=0.00$ $a_3=-1.00$

Com essas 4 medidas, podemos dividir a soma 2 vezes:

$A_k=\sum _{t=0}^3{a}_t\cdot e^{-i\frac{2\pi }{4}\cdot k\cdot t}$

$A_k=\sum _{t_1=0}^1{a}_{2t_1}\cdot e^{-i\frac{2\pi }{2}\cdot k\cdot t_1}+C_k^1\sum _{t_1=0}^1{a}_{2t_1+1}\cdot e^{-i\frac{2\pi }{2}\cdot k\cdot t_1}$

$A_k=\sum _{t_2=0}^0{a}_{4t_2}\cdot e^{-i\frac{2\pi }{1}\cdot k\cdot t_2}+C_k^2\sum _{t_2=0}^0{a}_{4t_2+2}\cdot e^{-i\frac{2\pi }{1}\cdot k\cdot t_2}+C_k^1\sum _{t_2=0}^0{a}_{4t_2+1}\cdot e^{-i\frac{2\pi }{1}\cdot k\cdot t_2}+C_k^3\sum _{t_2=0}^0{a}_{4t_2+3}\cdot e^{-i\frac{2\pi }{1}\cdot k\cdot t_2}$

e como temos $C_k^j=(e^{-i\frac{2\pi }{N}k}{)}^j$ podemos calcular

$A_0=1.00\cdot C_0^1-1.00\cdot C_0^3=0.00+i0.00$

$A_1=1.00\cdot C_1^1-1.00\cdot C_1^3=0.00-i2.00$

$A_2=1.00\cdot C_2^1-1.00\cdot C_2^3=0.00+i0.00$

$A_3=1.00\cdot C_3^1-1.00\cdot C_3^3=0.00+i2.00$

FFT para N diferente de uma potência de 2

Mesmo com a FFT sendo um algoritmo extremamente eficiente para $N=2^p$, esse dificilmente é o caso que encotramos. Ainda assim, para $N$ altamente composto ($N=r_1\cdot r_2\cdot ...\cdot r_m$) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.

Para o caso mais simples $N=r_1\cdot r_2$ a transformada pode ser escrita como

$F(k_1,k_0)=\sum _{n_0=0}^{r_2-1}[\sum _{n_1=0}^{r_1-1}x(n_1,n_0)e^{-i2\pi \cdot k\cdot n_1\cdot r_2}]e^{-i2\pi \cdot k\cdot n_0}$

onde $k=k_1\cdot r_1+k_0$ , $k_0=0,1,...,r_1-1$ e $k_1=0,1,...,r_2-1$

$n=n_1\cdot r_2+n_0$ , $n_0=0,1,...,r_2-1$ e $n_1=0,1,...,r_1-1$

assim a transformada que antes necessitava de N calculos, agora pode ser vista como $r_1+r_2$ calculos