Grupo4 - FFT

A Transformada rápida de Fourier (em inglês Fast Fourier Transform, ou FFT) é um algoritmo que torna viável o cálculo da Transformada Discreta de Fourier (DFT), que é a forma discretizada da [Transformada de Fourier]. A FFT permite transformar de forma rápida uma série de sinais discretos em uma amostra contendo as frequências desses sinais, desde que satisfaça algumas propriedades.

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 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 [-\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:

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 = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}}

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

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_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

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 \vec{A} = \mathbf{W^{nk}} \vec{a}} onde 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 \mathbf{W^{nk}}} é definido como

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

O cálculo dessa expressão leva em torno de 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} 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 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 \log_{2} N} passos. Para isso se dispõe de um algoritmo chamado Transformada Rápida de Fourier. Considera-se um conjunto de pontos 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} (com 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 p} inteiro, então, da definição da DFT

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 =\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:

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 =\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)} }

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 \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} }

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 \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 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} . Desse expoente, é evidente a relação entre o ponto 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 k} e o ponto 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 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.

Para o caso mais simples 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} a transformada pode ser escrita como

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_1,k_0) = \sum_{n_0=0}^{r_2-1}\left [ \sum_{n_1=0}^{r_1-1} x(n_1,n_0) e^{-i2\pi\cdot k \cdot n_1 \cdot r_2} \right ] e^{-i2\pi \cdot k \cdot n_0}}

onde

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 k = k_1 \cdot r_1 + k_0 ~~~~~~~~ k_0 = 0,1,...,r_1-1 ~~~~~~~~ k_1 = 0,1,...,r_2-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 n = n_1 \cdot r_2 + n_0 ~~~~~~~~ n_0 = 0,1,...,r_2-1 ~~~~~~~~ n_1 = 0,1,...,r_1-1}

assim a transformada que antes necessitava de N calculos, agora pode ser vista como 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 r_1 + r_2} calculos.

Algorítmo (usando recursão)

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 \mathbf{function} ~ FFT(N,a)}

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 ~~~~ \mathbf{if} ~ N = 1 ~ \mathbf{then}}

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 ~~~~~~~~ return ~ a;}

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 ~~~~ \mathbf{else}}

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 = FFT(N/2, (a_0, a_2, ..., a_{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 ~~~~~~~~ O = FFT(N/2, (a_1, a_3, ..., a_{N-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 ~~~~~~~~ \mathbf{for} k = 0 to k <= N/2 -1 \mathbf{do}}

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=E_k+exp(-i\frac{2\pi}{N} k) * O_k;}

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+N/2}=E_k-exp(-i\frac{2\pi}{N} k) * O_k;}