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

${\vec {F}}=\mathbf {W^{nk}} {\vec {f}}$ onde $\mathbf {W^{nk}}$ é definido como

$\mathbf {W^{nk}} ={\begin{bmatrix}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}\\\vdots &\vdots &\ddots &\vdots \\e^{-2\pi in\cdot 0/N}&e^{-2\pi in\cdot 1/N}&\cdots &e^{-2\pi in\cdot k/N}\end{bmatrix}}$

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}=\color {red}\sum _{n=0}^{N/2-1}f_{2n}\cdot e^{-i{\frac {2\pi }{N}}\cdot k\cdot 2n}\color {black}+\color {blue}\sum _{n=0}^{N/2-1}f_{2n+1}\cdot e^{-i{\frac {2\pi }{N}}\cdot k\cdot (2n+1)}$

$\color {black}F_{k}=\color {red}\sum _{n=0}^{N/2-1}f_{2n}\cdot e^{-i{\frac {2\pi }{N/2}}\cdot k\cdot n}\color {black}+\color {blue}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}$

$\color {black}F_{k}=\color {red}\sum _{n=0}^{N/2-1}f_{2n}\cdot e^{-i{\frac {2\pi }{N/2}}\cdot k\cdot n}\color {black}+\color {blue}~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$

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_k} e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle a(t) = sin(2\pi \cdot 1Hz \cdot t)} e fazemos quatro medidas no intervalo de 1 segundo, resultando em

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_0 = 0.00} Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1 = 1.00} Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_2 = 0.00} Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_3 = -1.00}

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

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_k = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}}

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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}}

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_k^j = (e^{-i\frac{2\pi}{N}k})^j} podemos calcular

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_0 = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00}

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1 = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00}

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_2 = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00}

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = 2^p} , esse dificilmente é o caso que encotramos. Ainda assim, para Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} altamente composto (Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = r_1\cdot r_2 \cdot ... \cdot r_m} ) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.