Grupo4 - FFT: mudanças entre as edições

De Física Computacional
Ir para navegação Ir para pesquisar
Sem resumo de edição
Sem resumo de edição
Linha 16: Linha 16:
A transformada também pode ser expressa em forma vetorial, como
A transformada também pode ser expressa em forma vetorial, como


<math>\vec{F} = \mathbf{A} \vec{f}</math> onde <math>\mathbf{A}</math> é definido como
<math>\vec{F} = \mathbf{W^{nk}} \vec{f}</math> onde <math>\mathbf{W^{nk}}</math> é definido como


<math>\mathbf{A} = \begin{bmatrix}
<math>\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 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}\\  
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\  
Linha 31: Linha 31:


É possível calcular a transformada com <math>N log N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.
É possível calcular a transformada com <math>N log N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT
<math>
<math>
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}
</math><math>
</math>
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)} \\
 
</math><math>
podemos dividir o somatório em 2:


\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} \\
<math>
</math><math>
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)}
</math>
 
<math>
\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}
</math>
 
<math>
\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}
\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}
</math>
</math>
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 <math>N/2</math>.
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math>
<math>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</math>
Com essa relação, podemos ver que <math>F_k</math> e <math>F_{k+N/2}</math> 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 <math>a(t) = sin(2\pi \cdot 1Hz \cdot t)</math> e fazemos quatro medidas no intervalo de 1 segundo, resultando em
<math>a_0 = 0.00</math>
<math>a_1 = 1.00</math>
<math>a_2 = 0.00</math>
<math>a_3 = -1.00</math>
Com essas 4 medidas, podemos dividir a soma 2 vezes:
<math>\tilde{a_k} = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math>
<math>\tilde{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}</math>
<math>\tilde{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}</math>
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular
<math>\tilde{a_0} = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math>
<math>\tilde{a_1} = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math>
<math>\tilde{a_2} = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math>
<math>\tilde{a_3} = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math>

Edição das 21h53min de 22 de outubro de 2017

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 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{F} = \mathbf{W^{nk}} \vec{f}} 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 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 \tilde{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 \tilde{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 \tilde{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 \tilde{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 \tilde{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 \tilde{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 \tilde{a_3} = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00}

Disponível em “http://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&oldid=695”