http://fiscomp.if.ufrgs.br/api.php?action=feedcontributions&feedformat=atom&user=GabrgiovFísica Computacional - Contribuições do usuário [pt-br]2026-04-16T15:18:12ZContribuições do usuárioMediaWiki 1.39.4http://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=2341Grupo4 - FFT2018-01-29T02:35:38Z<p>Gabrgiov: </p>
<hr />
<div>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 [[https://pt.wikipedia.org/wiki/Transformada_de_Fourier Transformada de Fourier]]. <br />
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.<br />
<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
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 <math>[-\pi, \pi]</math> 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:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math><br />
<br />
A transformada também pode ser expressa em forma vetorial, como<br />
<br />
<math>\vec{A} = \mathbf{W^{nk}} \vec{a} ~ </math> onde <math> ~ \mathbf{W^{nk}} ~ </math> é definido como<br />
<br />
<br />
<math>\mathbf{W^{nk}} = \begin{bmatrix}<br />
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\ <br />
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\ <br />
\vdots & \vdots & \ddots & \vdots\\ <br />
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}<br />
\end{bmatrix}</math><br />
<br />
O cálculo dessa expressão leva em torno de <math>N^2</math> 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.<br />
<br />
== Transformada Rápida de Fourier ==<br />
<br />
É possível calcular a transformada com <math>N \log_{2} N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.<br />
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT<br />
<br />
<math><br />
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}<br />
</math><br />
<br />
podemos dividir o somatório em 2:<br />
<br />
<math><br />
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)}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
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>.<br />
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math><br />
<br />
<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><br />
<br />
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.<br />
<br />
<br />
=== Exemplo ===<br />
<br />
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 <br />
<br />
<math>a_0 = 0.00</math><br />
<math>a_1 = 1.00</math><br />
<math>a_2 = 0.00</math><br />
<math>a_3 = -1.00</math><br />
<br />
Com essas 4 medidas, podemos dividir a soma 2 vezes:<br />
<br />
<math>A_k = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math><br />
<br />
<math>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><br />
<br />
<math>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><br />
<br />
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular<br />
<br />
<math>A_0 = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math><br />
<br />
<math>A_1 = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math><br />
<br />
<math>A_2 = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math><br />
<br />
<math>A_3 = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math><br />
<br />
=== FFT para N diferente de uma potência de 2 ===<br />
<br />
Mesmo com a FFT sendo um algoritmo extremamente eficiente para <math>N = 2^p</math>, esse dificilmente é o caso que encotramos. Ainda assim, para <math>N</math> altamente composto (<math>N = r_1\cdot r_2 \cdot ... \cdot r_m</math>) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.<br />
<br />
Para o caso mais simples <math>N = r_1 \cdot r_2</math> a transformada pode ser escrita como<br />
<br />
<math>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}</math><br />
<br />
onde <br />
<br />
<math>k = k_1 \cdot r_1 + k_0 ~~~~~~~~ k_0 = 0,1,...,r_1-1 ~~~~~~~~ k_1 = 0,1,...,r_2-1</math><br />
<br />
<math>n = n_1 \cdot r_2 + n_0 ~~~~~~~~ n_0 = 0,1,...,r_2-1 ~~~~~~~~ n_1 = 0,1,...,r_1-1</math><br />
<br />
assim a transformada que antes necessitava de N cálculos, agora pode ser vista como <math>r_1 + r_2</math> cálculos.<br />
<br />
Uma outra alternativa para o calculo da FFT é adicionar pontos 0 no fim da sequência. Por exemplo, para uma FFT de 5 pontos, basta adicionar 3 pontos 0 e calcular uma FFT pelos métodos já mostrados. Uma dificuldade dessa alternativa é que a transformada terá também 8 pontos, e apesar de corresponder ao mesmo formato da função original, está amostrada numa frequência diferente.<br />
<br />
=== Algorítmo (usando recursão) ===<br />
<math>>>\mathbf{function} ~ FFT(N,\vec{a})</math><br />
<br />
<math> >>> ~~~~ \mathbf{if} ~ N = 1 ~ \mathbf{then}</math><br />
<br />
<math> >>> ~~~~~~~~ return ~ \vec{a};</math><br />
<br />
<math> >>> ~~~~ \mathbf{else}</math><br />
<br />
<math> >>>~~~~~~~~ E = FFT(N/2, (a_0, a_2, ..., a_{N-2}));</math><br />
<br />
<math> >>>~~~~~~~~ O = FFT(N/2, (a_1, a_3, ..., a_{N-1}));</math><br />
<br />
<math> >>>~~~~~~~~ \mathbf{for} ~ k = 0 ~ to ~ k <= N/2 -1 ~ \mathbf{do}</math><br />
<br />
<math> >>>~~~~~~~~~~~~ A_k=E_k+exp(-i2\pi k/N) * O_k;</math><br />
<br />
<math> >>>~~~~~~~~~~~~ A_{k+N/2}=E_k-exp(-i2\pi k/N) * O_k;</math><br />
<br />
<math> >>>~~~~ return ~ \vec{A};</math><br />
<br />
== Implementação ==<br />
<br />
A natureza recursiva do algoritmo da transformada rápida de fourier o torna ideal para implementações em linguagens funcionais como Haskell. Abaixo exibimos as partes mais relevantes do código, onde omitimos inclusões de bibliotecas e a definição das funções auxiliares evens e odds.<br />
<br />
<source lang="haskell" line='line'><br />
<br />
--esse termo multiplica o somatório de termos ímpares<br />
f xs n = exp $ -(0:+2*pi)*n / genericLength xs<br />
<br />
--caso a função seja chamada com apenas dois termos, temos o caso base<br />
ffti [x,y] n = x + y * (exp $ -(0:+pi)*n)<br />
<br />
--caso contrário aplique a função recursivamente separando o somatório em <br />
-- termos com índice par e com índice ímpar<br />
ffti xs n = ffti (evens xs) n + f xs n * ffti (odds xs) n<br />
<br />
--função que calcula os n coeficientes (ffti calcula um coeficiente)<br />
fft xs [] = []<br />
fft xs (y:ys) = (ffti xs y):(fft xs ys)<br />
<br />
--exemplo<br />
fft [0, 1, 4, 9] [0,1,2,3]<br />
<br />
--saída ( :+ indica número complexo em Haskell)<br />
[14.0 :+ 0.0, -4.0 :+ 8.0, -6.0 :+ 0.0, -4.0 :+ -8.0)]<br />
<br />
</source><br />
<br />
Embora não seja uma linguagem puramente funcional Wolfram Mathematica também se presta a uma implementação direta e clara. <br />
<br />
<source lang="css" line='line'><br />
// caso base de uma lista contendo apenas dois termos<br />
fft[{x_, y_}, n_] := x + y Exp[-I Pi n ]<br />
// caso contrário, divida a lista entre termos com índice ímpar e par <br />
// e aplique a função recursivamente<br />
fft[f_List, n_] := fft[Downsample[f, 2, 1], n] + <br />
Exp[-((I 2 Pi n )/Length[f])] fft[Downsample[f, 2, 2], n]<br />
//acima calcula-se com um coeficiente abaixo calcula-se todos<br />
fft[f_List] := Table[fft[f, n] // N, {n, 0, Length[f] - 1}]<br />
<br />
//exemplo<br />
fft[{0, 1, 4, 9}]<br />
{14., -4. + 8. I, -6., -4. - 8. I}<br />
<br />
</source><br />
<br />
== Exemplos ==<br />
<br />
Abaixo encontra-se alguns exemplos básicos da transformada de fourier com base no código acima porém com modificações para lidar com o caso em que o intervalo de amostragem é diferente de <math>[0, 2\pi]</math> e cuja taxa de amostragem é qualquer (diferente de <math>\frac{2\pi k}{N}</math> como assumido acima)<br />
<br />
=== Gaussiana ===<br />
<br />
A menos de uma normalização a função gaussiana é definida por: <math>f(x) = e^{-\frac{(x - <x>)^2}{2 \sigma^2}}</math><br />
Aplicando a transformada de fourier na curva gaussiana obtem-se outra gaussiana. <br />
<br />
[[Arquivo:gaussian1.png|700px]]<br />
<br />
Observa-se que uma curva larga no espaço real corresponde a uma curva estreita no espaço de fourier e vice-versa. Esse é um fato matemático amplamente conhecido e se exprime também na física pelo Princípio da Incerteza de Heisenberg.<br />
Abaixo uma curva gaussiana mais larga que a anterior e sua transformada correspondentemente mais estreita.<br />
<br />
[[Arquivo:gaussian2.png|700px]]<br />
<br />
Uma função par em relação à origem possui uma expansão em fourier com termos ímpares nulos, no entanto, deslocando a gaussiana um pouco para a direita e, portanto, quebrando sua simetria, vemos que a sua transformada possui uma parte complexa:<br />
<br />
[[Arquivo:gaussian3.png|700px]]<br />
<br />
=== Oscilador Harmônico Amortecido ===<br />
<br />
A curva que representa um oscilador harmônico amortecido é descrita por <math>f(x) = sin(a x) e^{-bx}</math> onde o termo senoidal, periódico, é amortecido pelo termo exponencial que leva a oscilação rapidamente a zero.<br />
<br />
[[Arquivo:osch.jpg|500px]]<br />
<br />
A transformada de fourier dessa curva possui parte real e imaginária, da parte imaginária dessa curva é possível obter a frequência de ressonância do fenômeno representado por ela. No caso abaixo vemos que a frequência de ressonância vale <math>\pm 10Hz</math><br />
<br />
[[Arquivo:oschim.png|500px]]<br />
<br />
Abaixo a parte real da transformada:<br />
<br />
[[Arquivo:oschre.png|400px]]<br />
<br />
== Aplicações ==<br />
<br />
=== Equação de Schrödinger: propagação de onda de probabilidade ===<br />
<br />
O cálculo da evolução temporal da equação de schrödinger é computacionalmente exigente. A cada passo de tempo é necessário recalcular a posição da onda de probabilidade que representa a partícula em cada ponto do domínio. Portanto, torna-se vantajoso o uso da transformada de fourier rápida. Além disso a própria transformada faz parte da solução, pois também deseja-se obter a sua evolução temporal no espaço de momento. O código foi desenvolvido em python por [https://jakevdp.github.io/blog/2012/09/05/quantum-python/ Jake Vanderplas], no entanto, sob extensas modificações foi possível não apenas entender o código mas também modifica-lo para representar situações diferentes das propostas pelo autor. No site do autor encontra-se a explicação da teoria por trás do problema e também o funcionamento do algoritmo. A seguir exploramos a interação de uma onda de probabilidade com potenciais de diferentes formas.<br />
<br />
A parte principal do código modificado é exibida abaixo. Nota-se que o autor utilizou o método Leapfrog para integrar as equações de movimento fazendo a seguinte sequência de operações: dar um meio passo no espaço real, tomar a transformada, dar um passo no espaço de momento, tomar a transformada inversa e finalmente dar um passo completo no espaço real.<br />
<br />
<source lang="python" line='line'><br />
def time_step():<br />
global t, psi_mod_x, psi_mod_k, t_max<br />
psi_mod_x *= x_evolve_half<br />
for i in range(N_steps):<br />
psi_mod_k = fft(psi_mod_x)<br />
psi_mod_k *= k_evolve<br />
psi_mod_x = ifft(psi_mod_k)<br />
psi_mod_x *= x_evolve_half*x_evolve_half<br />
psi_mod_k = fft(psi_mod_x)<br />
t += dt * N_steps<br />
t_max = t_max - 1<br />
</source><br />
<br />
O restante do código ocupa-se somente de inicialização de valores, definição do potencial e escrita dos resultados.<br />
<br />
==== Potencial Quadrado ====<br />
<br />
O potencial quadrado foi o exemplo escolhido pelo autor do código. Nesse exemplo fica visível que uma porção da onda de probabilidade atravessa o potencial embora classicamente não tenha energia suficiente para tal feito. Essa é uma demonstração numérica do efeito de tunelamento. <br />
<br />
[[Arquivo:Square.gif]]<br />
<br />
==== Potencial Triangular ====<br />
<br />
O potencial triangular, por ter uma base mais larga, coíbe o efeito de tunelamento, no entanto, uma pequena porção da onda incidente ainda consegue transpor a barreira.<br />
<br />
[[Arquivo:Triangular.gif]]<br />
<br />
==== Potencial Batman ====<br />
<br />
Em cursos básicos de quântica normalmente resolve-se apenas o potencial quadrado, às vezes, excepcionalmente, apresenta-se o potencial triangular. Isso se deve a dificuldade em tratar casos de potenciais irregulares analiticamente. Mas em casos reais os potenciais são extremamente irregulares. A solução numérica trata tais casos com naturalidade e sem qualquer alteração. Em particular, um potencial tipo batman é encarado sem problemas:<br />
<br />
[[Arquivo:Batman.gif]]<br />
<br />
A parte superior da curva é apenas ilustrativa (pois não faz sentido matemático nem físico)<br />
<br />
=== Padrões de Difração ===<br />
<br />
A transformada rápida é muito utilizada no tratamento de imagens. Software como ImageJ ou Matlab possuem muitas ferramentas que fazem uso da técnica. Uma aplicação específica da FFT é na análise de imagens de partículas nanométricas obtidas por um microscópio eletrônico de transmissão. Esse equipamento produz um interferograma que (a menos de correções) representa a imagem real do que se está observando mas também produz uma segunda imagem, localizada no ponto focal da lente, que é o padrão de difração da imagem real. Essa imagem é uma visualização do espaço recíproco, ou seja, da transformada do espaço real. <br />
<br />
Abaixo está uma imagem de um plano de átomos de ouro obtida por um microscópio de transmissão eletrônica com uma escala de 2 nanômetros na qual destacamos uma região (quadrado vermelho) na qual tomaremos a transformada de fourier. A imagem em si é representada por uma matrix 800x800 onde cada elemento da matrix é um valor de intensidade sendo 0 para totalmente escuro e 255 para totalmente claro.<br />
<br />
[[Arquivo:Region.png|600px]]<br />
<br />
Utilizando, por exemplo o software Matlab podemos tomar a transformada inversa dessa imagem. A transformada de fourier produz o padrão de difração que revela a periodicidade da imagem.<br />
O código em Matlab é bem simples:<br />
<br />
<source lang="python" line='line'><br />
function imagefft(I)<br />
F = fft2(I);<br />
F = fftshift(F); % centraliza a FFT<br />
F = abs(F); % obtem a magnitude (desnecessário, nossa imagem varia de 0 a 255)<br />
F = log(F+1); % escala logaritmica, +1 por que log(0) é indefinido<br />
F = mat2gray(F); % renormaliza a imagem de 0-255 para 0-1<br />
imshow(F,[]) % exibe o resultado<br />
end<br />
</source><br />
<br />
[[Arquivo:Matlab fft.png|600px]]<br />
<br />
Cada par de pontos simétricos em relação ao ponto central representa um conjunto de planos paralelos no espaço real, sendo a imagem real o conjunto de todos os planos representados por todos os pontos somado ao ruído da imagem. Observe que a imagem original, além de ruído, apresenta três planos diferentes como pode-se notar pela orientação dos átomos. Isso explica a presença de linhas claras ao redor dos pontos de difração. Um cristal perfeito, por outro lado, possuiria um padrão de difração de pontos localizados e não discos com linhas como vemos num cristal real.<br />
<br />
A seguir vejamos como decompor essas informações. Aplicando uma máscara sobre a imagem podemos selecionar apenas um par de pontos e ver a qual conjunto de planos do espaço real ele está relacionado:<br />
<br />
[[Arquivo:Applied mask.png|900px]]<br />
<br />
Para descobrir qual é o conjunto de planos tomamos a transformada inversa:<br />
<br />
[[Arquivo:Inverse fft.png|900px]]<br />
<br />
Como mencionado se selecionarmos todos os pontos e tomarmos a transformada inversa obteremos a imagem original, no entanto, removendo boa parte dos ruídos - a parte que deixamos de fora da máscara.<br />
<br />
[[Arquivo:Full mask.png|900px]]<br />
<br />
[[Arquivo:Removed all noise.png|900px]]<br />
<br />
Se quisermos ver a composição do ruído podemos tomar a máscara inversa e aplicar a transformada inversa, obtendo:<br />
<br />
[[Arquivo:Negative mask.png|900px]]<br />
<br />
[[Arquivo:Noise.png|900px]]<br />
<br />
<br />
<br />
<br />
<br />
== Referências Bibliográficas==<br />
<br />
[1] [https://web.stanford.edu/class/cme324/classics/cooley-tukey.pdf An Algorithm for the Machine Calculation of. Complex Fourier Series. By James W. Cooley and John W. Turkey].<br />
<br />
[2] Kreyszig, Erwin. Advanced Engineering Mathematics. Wiley, 2011.<br />
<br />
[3] Scherer, Claudio. Métodos Computacionais da Física.<br />
<br />
[4] Richard; Faires, Douglas. Numerical Analysis, 2011</div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo_-_Modelo_Sznajd&diff=2213Grupo - Modelo Sznajd2018-01-25T05:26:48Z<p>Gabrgiov: </p>
<hr />
<div>== Introdução ==<br />
O Modelo de Sznajd ou '''United we stand, divided we fall (USDF)''' é um modelo recente, proposto em 2000 para entender a dinâmica de opiniões através da física estatística. No ponto de vista de um físico, o comportamento de indivíduos a as interações entre eles constituem um nível microscópico de um sistema social. O modelo introduz o fenômeno chamado validação social:<br />
<br />
'''Validação Social:''' Se duas pessoas compartilham da mesma opinião, os seus vizinhos começarão a concordar com elas.<br />
<br />
'''Discordância Destrutiva:''' Se as pessoas discordam, os vizinhos começarão a argumentar com elas.<br />
<br />
== O método e Formulação Matemática == <br />
Opinião social é vinda de opiniões individuais, representadas neste modelo por spins de Ising de forma ''"yes"'' e ''"no"''. A dinâmica segue a relação da validação social:<br />
<br />
# A cada timestep um par de sping <math> S_{i}, S_{i+1}</math> são escolhidos para tentar mudar os seus vizinhos mais próximos<br />
# Se <math> S_{i} = S_{i+1}</math>, então <math> S_{i-1} = S_{i}</math> e <math> S_{i+2} = S_{i}</math> (''validação social'')<br />
# Se <math> S_{i} = -S_{i+1}</math>, então <math> S_{i-1} = S_{i+1}</math> e <math> S_{i+2} = S_{i}</math><br />
<br />
No modelo, dois tipos de estados estacionários são alcançáveis: consenso completo(ferromagnético) e impasse(antiferromagnético). A principal diferença para o Ising é que a informação flui para fora. O modelo de Sznajd ou USDF tem sido modificado e utilizado em marketing, política e finanças.<br />
<br />
== Modificações ==<br />
Fala-se que o estado antes mencionado, o antiferromagnetismo, pode ser considerado não realístico para representar o comportamento de indivíduos em uma sociedade. Para tentar evitar este caso, propõe-se o seguinte:<br />
<br />
# A cada timestep um par de sping <math> S_{i}, S_{i+1}</math> são escolhidos para tentar mudar os seus vizinhos mais próximos igual anteriomente<br />
# Se <math> S_{i} = S_{i+1}</math>, então <math> S_{i-1} = S_{i}</math> e <math> S_{i+2} = S_{i}</math> (''validação social'')<br />
# Se <math> S_{i} = -S_{i+1}</math>, então <math> S_{i-1} = S_{i}</math> e <math> S_{i+2} = S_{i}</math><br />
<br />
Estas regras ficaram conhecidas como algo do tipo: "Se você não sabe o que fazer, ou faz nada ou faz qualquer coisa." É um tanto quanto óbvio que o modelo unidimensional não representa bem um sistema social e que modelos bidimensionais são bem mais realistas. Algo interessante mencionar é a atualização simultânea para sistemas de duas dimensões: uma atualização simultânea leva a uma muito maior dificuldade de atingir o estado de consenso total. Isso foi mostrado por Stauffer<ref>D. Stauffer D, J Math Sociol 28 25 (2004)</ref> e a rezão para isso é que alguns recebem simultaneamente distintas informações de diferentes vizinhos, o que leva a não aceitar a opinião.<br />
<br />
Regras para rede quadrada <math>LxL</math>:<br />
<br />
# Se conjunto 2x2 de 4 vizinhos não tiverem todos os seus spins paralelos, deixam os seus oito vizinhos sem modificações<br />
# Um par de vizinhos convence seus seis vizinhos a seguirem a sua orientação se o par de spins for paralelo. <br />
<br />
A regra de atualização para duas dimensões pode ser obtida pela regra em uma dimensão: A regra e 1D é aplicada para cada uma das 4 cadeias de spins, como mostra a próxima figura:<br />
[[Arquivo:1.jpg]]<br />
<br />
Isto foi mostrado por Gallam<ref>S. Galam, J. Stat. Phys. 61, 943 (1990)</ref><br />
<br />
== Generalização ==<br />
Para a generalização desse método para a rede quadrada <math>L</math>x<math>L</math> onde cada spin pode estar para cima ou para baixo e utiliza-se condições periódicas de contorno. As regras <ref>D. Stauffer,A.O. Sousa,M. De Oliveira, Int. J. Mod. Phys. C 11 1239</ref> esquematizadas:<br />
[[Arquivo:2.jpg]]<br />
<br />
<math>I.</math> Um conjunto 2x2 de quatro vizinhos é escolhido e se todos não forem paralelos, deixa os seus oito vizinhos sem mudanças. Se não, seguem duas regras:<br />
#<math>I_a</math> Os vizinhos seguem a orientação do conjunto.<br />
#<math>I_b</math> Os vizinhos seguem a orientação oposta ao conjunto.<br />
<br />
<math>II.</math> Um par vizinho tenta convencer seus seis vizinhos a seguir a orientação do par apenas se o par tiver spins paralelos. Caso contrário, seguem três regras horizontais mas com regras verticais completamente análogas:<br />
#<math>II_a</math> Os vizinhos não mudam<br />
#<math>II_b</math> Os três vizinhos da esquerda seguem a orientação do spin da esquerda do par e os três da direita seguem o spin da direita<br />
#<math>II_c</math> Os três vizinhos da esquerda seguem a orientação do spin da direita do par e os três da direita seguem o spin da esquerda (oposto a anterior)<br />
<br />
<math>III.</math> A regra de 1D é aplicada para cada uma das quatro linhas de quatro spins cada.<br />
<br />
Regra <math>I_a:</math> pontos fixos com spins todos para cima ou para baixo<br />
<br />
Regra <math>I_b:</math> sem pontos fixos<br />
<br />
Regra <math>II_a</math> e <math>II_b:</math> pontos fixos com spins todos para cima ou para baixo<br />
<br />
Regra <math>II_c:</math> Para L par ten-se ou tudo para cima ou para baixo. Para L ímpar também a o ponto antiferromagnético<br />
<br />
Regra <math>III:</math> pontos fixos com spins todos para cima ou para baixo com L ímpar<br />
<br />
== Aplicações ==<br />
O modelo de Sznajd pode ser utilizado em política, marketing e finanças. Um caso especial está em <ref>A. T. BERNARDES et al, Int. J. Mod. Phys. C 12, 159 (2001)</ref><br />
<br />
Reproduzimos o modelo mostrado no paper, usando uma rede quadrada <math>NxN</math> com <math>N = 1000</math>. Ao invés de usar um modelo de spin (-1 ou 1), o modelo simula eleições brasileiras, usando um numero de políticos escolhido como <math>N_p = 600</math>. Usando a condição de seleção <math>IIa</math>, cada vez que dois vizinhos tem a mesma opinião, todos os seus 6 vizinhos adquirem a mesma opinião. <br />
<br />
Nossa condição inicial é montada selecionando todos os eleitores aleatoriamente, dando-os uma probabilidade <math>P = \frac{n^2}{N^2}</math> de escolher um candidato <math>n</math>. Ao escolher um candidado, ele tem uma mesma probabilidade <math>P</math> de tentar convencer seus vizinhos (<math>P</math> nesse caso age como o poder de convencimento de um candidato). Na imagem podemos ver [INSERIR IMAGEM INICIAL] a distribuição de votos por politico, que segue uma lei de potências. <br />
<br />
Em seguida, realizamos passos de Monte Carlo, selecionando aleatóriamente <math>N^2</math> eleitores (que podem se repetir) e os fazemos tentar convencer um de seus 4 vizinhos, seguindo a mesma regra.<br />
<br />
Nosso modelo tenta estudar a fase de transição do modelo (passos de Monte Carlo <math>1 << t << 10^5</math>), dado que num processo eleitoral os votos não atingem um equilíbrio. A imagem mostra a distribuição desses votos [INSERIR afterparty]<br />
<br />
Após essa distribuição, podemos estudar como se dividem os votos. A imagem mostra [INSERIR final] a distribuição acumulada dos votos, em azul logo após a distribuição inicial (lei de potência com inclinação -1/2), e após os passos de Monte Carlo (com inclinação -1). Vemos que muitos poucos candidatos recebem a maioria dos votos, fato que concorda com o caso real <ref>R. N. Costa-Filho, M. P. Almeida, J. S. Andrade Jr., and J. E. Moreira, Phys. Rev. E 60, 1067 (1999)</ref><br />
<br />
<br />
==Bibliografia==<br />
<references/></div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=725Grupo4 - FFT2017-10-24T01:35:50Z<p>Gabrgiov: </p>
<hr />
<div>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 [[https://pt.wikipedia.org/wiki/Transformada_de_Fourier Transformada de Fourier]]. <br />
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.<br />
<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
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 <math>[-\pi, \pi]</math> 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:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math><br />
<br />
A transformada também pode ser expressa em forma vetorial, como<br />
<br />
<math>\vec{A} = \mathbf{W^{nk}} \vec{a} ~ </math> onde <math> ~ \mathbf{W^{nk}} ~ </math> é definido como<br />
<br />
<br />
<math>\mathbf{W^{nk}} = \begin{bmatrix}<br />
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\ <br />
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\ <br />
\vdots & \vdots & \ddots & \vdots\\ <br />
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}<br />
\end{bmatrix}</math><br />
<br />
O cálculo dessa expressão leva em torno de <math>N^2</math> 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.<br />
<br />
== Transformada Rápida de Fourier ==<br />
<br />
É possível calcular a transformada com <math>N \log_{2} N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.<br />
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT<br />
<br />
<math><br />
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}<br />
</math><br />
<br />
podemos dividir o somatório em 2:<br />
<br />
<math><br />
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)}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
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>.<br />
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math><br />
<br />
<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><br />
<br />
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.<br />
<br />
<br />
=== Exemplo ===<br />
<br />
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 <br />
<br />
<math>a_0 = 0.00</math><br />
<math>a_1 = 1.00</math><br />
<math>a_2 = 0.00</math><br />
<math>a_3 = -1.00</math><br />
<br />
Com essas 4 medidas, podemos dividir a soma 2 vezes:<br />
<br />
<math>A_k = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math><br />
<br />
<math>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><br />
<br />
<math>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><br />
<br />
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular<br />
<br />
<math>A_0 = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math><br />
<br />
<math>A_1 = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math><br />
<br />
<math>A_2 = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math><br />
<br />
<math>A_3 = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math><br />
<br />
=== FFT para N diferente de uma potência de 2 ===<br />
<br />
Mesmo com a FFT sendo um algoritmo extremamente eficiente para <math>N = 2^p</math>, esse dificilmente é o caso que encotramos. Ainda assim, para <math>N</math> altamente composto (<math>N = r_1\cdot r_2 \cdot ... \cdot r_m</math>) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.<br />
<br />
Para o caso mais simples <math>N = r_1 \cdot r_2</math> a transformada pode ser escrita como<br />
<br />
<math>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}</math><br />
<br />
onde <br />
<br />
<math>k = k_1 \cdot r_1 + k_0 ~~~~~~~~ k_0 = 0,1,...,r_1-1 ~~~~~~~~ k_1 = 0,1,...,r_2-1</math><br />
<br />
<math>n = n_1 \cdot r_2 + n_0 ~~~~~~~~ n_0 = 0,1,...,r_2-1 ~~~~~~~~ n_1 = 0,1,...,r_1-1</math><br />
<br />
assim a transformada que antes necessitava de N calculos, agora pode ser vista como <math>r_1 + r_2</math> calculos.<br />
<br />
=== Algorítmo (usando recursão) ===<br />
<math>>>\mathbf{function} ~ FFT(N,\vec{a})</math><br />
<br />
<math> >>> ~~~~ \mathbf{if} ~ N = 1 ~ \mathbf{then}</math><br />
<br />
<math> >>> ~~~~~~~~ return ~ \vec{a};</math><br />
<br />
<math> >>> ~~~~ \mathbf{else}</math><br />
<br />
<math> >>>~~~~~~~~ E = FFT(N/2, (a_0, a_2, ..., a_{N-2}));</math><br />
<br />
<math> >>>~~~~~~~~ O = FFT(N/2, (a_1, a_3, ..., a_{N-1}));</math><br />
<br />
<math> >>>~~~~~~~~ \mathbf{for} ~ k = 0 ~ to ~ k <= N/2 -1 ~ \mathbf{do}</math><br />
<br />
<math> >>>~~~~~~~~~~~~ A_k=E_k+exp(-i2\pi k/N) * O_k;</math><br />
<br />
<math> >>>~~~~~~~~~~~~ A_{k+N/2}=E_k-exp(-i2\pi k/N) * O_k;</math><br />
<br />
<math> >>>~~~~ return ~ \vec{A};</math></div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=723Grupo4 - FFT2017-10-24T01:25:43Z<p>Gabrgiov: </p>
<hr />
<div>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 [[https://pt.wikipedia.org/wiki/Transformada_de_Fourier Transformada de Fourier]]. <br />
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.<br />
<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
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 <math>[-\pi, \pi]</math> 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:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math><br />
<br />
A transformada também pode ser expressa em forma vetorial, como<br />
<br />
<math>\vec{A} = \mathbf{W^{nk}} \vec{a}</math> onde <math>\mathbf{W^{nk}}</math> é definido como<br />
<br />
<math>\mathbf{W^{nk}} = \begin{bmatrix}<br />
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\ <br />
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\ <br />
\vdots & \vdots & \ddots & \vdots\\ <br />
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}<br />
\end{bmatrix}</math><br />
<br />
O cálculo dessa expressão leva em torno de <math>N^2</math> 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.<br />
<br />
<br />
== Transformada Rápida de Fourier ==<br />
<br />
É possível calcular a transformada com <math>N \log_{2} N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.<br />
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT<br />
<br />
<math><br />
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}<br />
</math><br />
<br />
podemos dividir o somatório em 2:<br />
<br />
<math><br />
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)}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
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>.<br />
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math><br />
<br />
<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><br />
<br />
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.<br />
<br />
<br />
=== Exemplo ===<br />
<br />
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 <br />
<br />
<math>a_0 = 0.00</math><br />
<math>a_1 = 1.00</math><br />
<math>a_2 = 0.00</math><br />
<math>a_3 = -1.00</math><br />
<br />
Com essas 4 medidas, podemos dividir a soma 2 vezes:<br />
<br />
<math>A_k = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math><br />
<br />
<math>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><br />
<br />
<math>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><br />
<br />
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular<br />
<br />
<math>A_0 = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math><br />
<br />
<math>A_1 = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math><br />
<br />
<math>A_2 = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math><br />
<br />
<math>A_3 = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math><br />
<br />
=== FFT para N diferente de uma potência de 2 ===<br />
<br />
Mesmo com a FFT sendo um algoritmo extremamente eficiente para <math>N = 2^p</math>, esse dificilmente é o caso que encotramos. Ainda assim, para <math>N</math> altamente composto (<math>N = r_1\cdot r_2 \cdot ... \cdot r_m</math>) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.<br />
<br />
Para o caso mais simples <math>N = r_1 \cdot r_2</math> a transformada pode ser escrita como<br />
<br />
<math>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}</math><br />
<br />
onde <br />
<br />
<math>k = k_1 \cdot r_1 + k_0 ~~~~~~~~ k_0 = 0,1,...,r_1-1 ~~~~~~~~ k_1 = 0,1,...,r_2-1</math><br />
<br />
<math>n = n_1 \cdot r_2 + n_0 ~~~~~~~~ n_0 = 0,1,...,r_2-1 ~~~~~~~~ n_1 = 0,1,...,r_1-1</math><br />
<br />
assim a transformada que antes necessitava de N calculos, agora pode ser vista como <math>r_1 + r_2</math> calculos.<br />
<br />
=== Algorítmo (usando recursão) ===<br />
<math>>>\mathbf{function} ~ FFT(N,a)</math><br />
<br />
<math> >>> ~~~~ \mathbf{if} ~ N = 1 ~ \mathbf{then}</math><br />
<br />
<math> >>> ~~~~~~~~ return ~ a;</math><br />
<br />
<math> >>> ~~~~ \mathbf{else}</math><br />
<br />
<math> >>>~~~~~~~~ E = FFT(N/2, (a_0, a_2, ..., a_{N-2}));</math><br />
<br />
<math> >>>~~~~~~~~ O = FFT(N/2, (a_1, a_3, ..., a_{N-1}));</math><br />
<br />
<br />
<math> >>>~~~~~~~~ \mathbf{for} ~ k = 0 ~ to ~ k <= N/2 -1 ~ \mathbf{do}</math><br />
<br />
<math> >>>~~~~~~~~~~~~ A_k=E_k+exp(-i2\pi k/N) * O_k;</math><br />
<br />
<math> >>>~~~~~~~~~~~~ A_{k+N/2}=E_k-exp(-i2\pi k/N) * O_k;</math></div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=722Grupo4 - FFT2017-10-24T01:18:44Z<p>Gabrgiov: </p>
<hr />
<div>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 [[https://pt.wikipedia.org/wiki/Transformada_de_Fourier Transformada de Fourier]]. <br />
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.<br />
<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
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 <math>[-\pi, \pi]</math> 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:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math><br />
<br />
A transformada também pode ser expressa em forma vetorial, como<br />
<br />
<math>\vec{A} = \mathbf{W^{nk}} \vec{a}</math> onde <math>\mathbf{W^{nk}}</math> é definido como<br />
<br />
<math>\mathbf{W^{nk}} = \begin{bmatrix}<br />
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\ <br />
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\ <br />
\vdots & \vdots & \ddots & \vdots\\ <br />
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}<br />
\end{bmatrix}</math><br />
<br />
O cálculo dessa expressão leva em torno de <math>N^2</math> 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.<br />
<br />
<br />
== Transformada Rápida de Fourier ==<br />
<br />
É possível calcular a transformada com <math>N \log_{2} N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.<br />
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT<br />
<br />
<math><br />
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}<br />
</math><br />
<br />
podemos dividir o somatório em 2:<br />
<br />
<math><br />
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)}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
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>.<br />
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math><br />
<br />
<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><br />
<br />
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.<br />
<br />
<br />
=== Exemplo ===<br />
<br />
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 <br />
<br />
<math>a_0 = 0.00</math><br />
<math>a_1 = 1.00</math><br />
<math>a_2 = 0.00</math><br />
<math>a_3 = -1.00</math><br />
<br />
Com essas 4 medidas, podemos dividir a soma 2 vezes:<br />
<br />
<math>A_k = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math><br />
<br />
<math>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><br />
<br />
<math>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><br />
<br />
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular<br />
<br />
<math>A_0 = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math><br />
<br />
<math>A_1 = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math><br />
<br />
<math>A_2 = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math><br />
<br />
<math>A_3 = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math><br />
<br />
=== FFT para N diferente de uma potência de 2 ===<br />
<br />
Mesmo com a FFT sendo um algoritmo extremamente eficiente para <math>N = 2^p</math>, esse dificilmente é o caso que encotramos. Ainda assim, para <math>N</math> altamente composto (<math>N = r_1\cdot r_2 \cdot ... \cdot r_m</math>) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.<br />
<br />
Para o caso mais simples <math>N = r_1 \cdot r_2</math> a transformada pode ser escrita como<br />
<br />
<math>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}</math><br />
<br />
onde <br />
<br />
<math>k = k_1 \cdot r_1 + k_0 ~~~~~~~~ k_0 = 0,1,...,r_1-1 ~~~~~~~~ k_1 = 0,1,...,r_2-1</math><br />
<br />
<math>n = n_1 \cdot r_2 + n_0 ~~~~~~~~ n_0 = 0,1,...,r_2-1 ~~~~~~~~ n_1 = 0,1,...,r_1-1</math><br />
<br />
assim a transformada que antes necessitava de N calculos, agora pode ser vista como <math>r_1 + r_2</math> calculos.<br />
<br />
=== Algorítmo (usando recursão) ===<br />
<math>\mathbf{function} ~ FFT(N,a)</math><br />
<br />
<math> ~~~~ \mathbf{if} ~ N = 1 ~ \mathbf{then}</math><br />
<br />
<math> ~~~~~~~~ return ~ a;</math><br />
<br />
<math> ~~~~ \mathbf{else}</math><br />
<br />
<math> ~~~~~~~~ E = FFT(N/2, (a_0, a_2, ..., a_{N-2}));</math><br />
<br />
<math> ~~~~~~~~ O = FFT(N/2, (a_1, a_3, ..., a_{N-1}));</math><br />
<br />
<br />
<math> ~~~~~~~~ \mathbf{for} k = 0 to k <= N/2 -1 \mathbf{do}</math><br />
<br />
<math> ~~~~~~~~~~~~ A_k=E_k+exp(-i\frac{2\pi}{N} k) * O_k;</math><br />
<br />
<math> ~~~~~~~~~~~~ A_{k+N/2}=E_k-exp(-i\frac{2\pi}{N} k) * O_k;</math></div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=715Grupo4 - FFT2017-10-24T00:24:58Z<p>Gabrgiov: </p>
<hr />
<div>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.<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
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 <math>[-\pi, \pi]</math> 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:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math><br />
<br />
A transformada também pode ser expressa em forma vetorial, como<br />
<br />
<math>\vec{A} = \mathbf{W^{nk}} \vec{a}</math> onde <math>\mathbf{W^{nk}}</math> é definido como<br />
<br />
<math>\mathbf{W^{nk}} = \begin{bmatrix}<br />
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\ <br />
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\ <br />
\vdots & \vdots & \ddots & \vdots\\ <br />
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}<br />
\end{bmatrix}</math><br />
<br />
O cálculo dessa expressão leva em torno de <math>N^2</math> 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.<br />
<br />
<br />
== Transformada Rápida de Fourier ==<br />
<br />
É possível calcular a transformada com <math>N \log_{2} N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.<br />
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT<br />
<br />
<math><br />
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}<br />
</math><br />
<br />
podemos dividir o somatório em 2:<br />
<br />
<math><br />
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)}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
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>.<br />
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math><br />
<br />
<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><br />
<br />
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.<br />
<br />
<br />
=== Exemplo ===<br />
<br />
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 <br />
<br />
<math>a_0 = 0.00</math><br />
<math>a_1 = 1.00</math><br />
<math>a_2 = 0.00</math><br />
<math>a_3 = -1.00</math><br />
<br />
Com essas 4 medidas, podemos dividir a soma 2 vezes:<br />
<br />
<math>A_k = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math><br />
<br />
<math>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><br />
<br />
<math>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><br />
<br />
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular<br />
<br />
<math>A_0 = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math><br />
<br />
<math>A_1 = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math><br />
<br />
<math>A_2 = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math><br />
<br />
<math>A_3 = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math><br />
<br />
=== FFT para N diferente de uma potência de 2 ===<br />
<br />
Mesmo com a FFT sendo um algoritmo extremamente eficiente para <math>N = 2^p</math>, esse dificilmente é o caso que encotramos. Ainda assim, para <math>N</math> altamente composto (<math>N = r_1\cdot r_2 \cdot ... \cdot r_m</math>) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.<br />
<br />
Para o caso mais simples <math>N = r_1 \cdot r_2</math> a transformada pode ser escrita como<br />
<br />
<math>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}</math><br />
<br />
onde <br />
<br />
<math>k = k_1 \cdot r_1 + k_0 ~~~~~~~~ k_0 = 0,1,...,r_1-1 ~~~~~~~~ k_1 = 0,1,...,r_2-1</math><br />
<br />
<math>n = n_1 \cdot r_2 + n_0 ~~~~~~~~ n_0 = 0,1,...,r_2-1 ~~~~~~~~ n_1 = 0,1,...,r_1-1</math><br />
<br />
assim a transformada que antes necessitava de N calculos, agora pode ser vista como <math>r_1 + r_2</math> calculos</div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=713Grupo4 - FFT2017-10-24T00:15:18Z<p>Gabrgiov: </p>
<hr />
<div>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.<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
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 <math>[-\pi, \pi]</math> 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:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math><br />
<br />
A transformada também pode ser expressa em forma vetorial, como<br />
<br />
<math>\vec{F} = \mathbf{W^{nk}} \vec{f}</math> onde <math>\mathbf{W^{nk}}</math> é definido como<br />
<br />
<math>\mathbf{W^{nk}} = \begin{bmatrix}<br />
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\ <br />
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\ <br />
\vdots & \vdots & \ddots & \vdots\\ <br />
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}<br />
\end{bmatrix}</math><br />
<br />
O cálculo dessa expressão leva em torno de <math>N^2</math> 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.<br />
<br />
<br />
== Transformada Rápida de Fourier ==<br />
<br />
É possível calcular a transformada com <math>N \log_{2} N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.<br />
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT<br />
<br />
<math><br />
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}<br />
</math><br />
<br />
podemos dividir o somatório em 2:<br />
<br />
<math><br />
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)}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
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>.<br />
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math><br />
<br />
<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><br />
<br />
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.<br />
<br />
<br />
=== Exemplo ===<br />
<br />
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 <br />
<br />
<math>a_0 = 0.00</math><br />
<math>a_1 = 1.00</math><br />
<math>a_2 = 0.00</math><br />
<math>a_3 = -1.00</math><br />
<br />
Com essas 4 medidas, podemos dividir a soma 2 vezes:<br />
<br />
<math>A_k = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math><br />
<br />
<math>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><br />
<br />
<math>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><br />
<br />
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular<br />
<br />
<math>A_0 = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math><br />
<br />
<math>A_1 = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math><br />
<br />
<math>A_2 = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math><br />
<br />
<math>A_3 = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math><br />
<br />
=== FFT para N diferente de uma potência de 2 ===<br />
<br />
Mesmo com a FFT sendo um algoritmo extremamente eficiente para <math>N = 2^p</math>, esse dificilmente é o caso que encotramos. Ainda assim, para <math>N</math> altamente composto (<math>N = r_1\cdot r_2 \cdot ... \cdot r_m</math>) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.<br />
<br />
Para o caso mais simples <math>N = r_1 \cdot r_2</math> a transformada pode ser escrita como<br />
<br />
<math>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}</math><br />
<br />
onde <br />
<math>k = k_1 \cdot r_1 + k_0</math> , <math>k_0 = 0,1,...,r_1-1</math> e <math>k_1 = 0,1,...,r_2-1</math><br />
<br />
<math>n = n_1 \cdot r_2 + n_0</math> , <math>n_0 = 0,1,...,r_2-1</math> e <math>n_1 = 0,1,...,r_1-1</math><br />
<br />
assim a transformada que antes necessitava de N calculos, agora pode ser vista como <math>r_1 + r_2</math> calculos</div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=707Grupo4 - FFT2017-10-24T00:02:33Z<p>Gabrgiov: </p>
<hr />
<div>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.<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
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 <math>[-\pi, \pi]</math> 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:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math><br />
<br />
A transformada também pode ser expressa em forma vetorial, como<br />
<br />
<math>\vec{F} = \mathbf{W^{nk}} \vec{f}</math> onde <math>\mathbf{W^{nk}}</math> é definido como<br />
<br />
<math>\mathbf{W^{nk}} = \begin{bmatrix}<br />
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\ <br />
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\ <br />
\vdots & \vdots & \ddots & \vdots\\ <br />
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}<br />
\end{bmatrix}</math><br />
<br />
O cálculo dessa expressão leva em torno de <math>N^2</math> 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.<br />
<br />
<br />
== Transformada Rápida de Fourier ==<br />
<br />
É possível calcular a transformada com <math>N \log_{2} N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.<br />
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT<br />
<br />
<math><br />
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}<br />
</math><br />
<br />
podemos dividir o somatório em 2:<br />
<br />
<math><br />
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)}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
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>.<br />
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math><br />
<br />
<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><br />
<br />
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.<br />
<br />
<br />
=== Exemplo ===<br />
<br />
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 <br />
<br />
<math>a_0 = 0.00</math><br />
<math>a_1 = 1.00</math><br />
<math>a_2 = 0.00</math><br />
<math>a_3 = -1.00</math><br />
<br />
Com essas 4 medidas, podemos dividir a soma 2 vezes:<br />
<br />
<math>A_k = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math><br />
<br />
<math>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><br />
<br />
<math>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><br />
<br />
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular<br />
<br />
<math>A_0 = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math><br />
<br />
<math>A_1 = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math><br />
<br />
<math>A_2 = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math><br />
<br />
<math>A_3 = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math><br />
<br />
=== FFT para N diferente de uma potência de 2 ===<br />
<br />
Mesmo com a FFT sendo um algoritmo extremamente eficiente para <math>N = 2^p</math>, esse dificilmente é o caso que encotramos. Ainda assim, para <math>N</math> altamente composto (<math>N = r_1\cdot r_2 \cdot ... \cdot r_m</math>) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.</div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=706Grupo4 - FFT2017-10-24T00:01:46Z<p>Gabrgiov: </p>
<hr />
<div>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.<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
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 <math>[-\pi, \pi]</math> 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:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math><br />
<br />
A transformada também pode ser expressa em forma vetorial, como<br />
<br />
<math>\vec{F} = \mathbf{W^{nk}} \vec{f}</math> onde <math>\mathbf{W^{nk}}</math> é definido como<br />
<br />
<math>\mathbf{W^{nk}} = \begin{bmatrix}<br />
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\ <br />
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\ <br />
\vdots & \vdots & \ddots & \vdots\\ <br />
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}<br />
\end{bmatrix}</math><br />
<br />
O cálculo dessa expressão leva em torno de <math>N^2</math> 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.<br />
<br />
<br />
== Transformada Rápida de Fourier ==<br />
<br />
É possível calcular a transformada com <math>N \log_{2} N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.<br />
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT<br />
<br />
<math><br />
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}<br />
</math><br />
<br />
podemos dividir o somatório em 2:<br />
<br />
<math><br />
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)}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
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>.<br />
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math><br />
<br />
<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><br />
<br />
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.<br />
<br />
<br />
=== Exemplo ===<br />
<br />
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 <br />
<br />
<math>a_0 = 0.00</math><br />
<math>a_1 = 1.00</math><br />
<math>a_2 = 0.00</math><br />
<math>a_3 = -1.00</math><br />
<br />
Com essas 4 medidas, podemos dividir a soma 2 vezes:<br />
<br />
<math>A = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math><br />
<br />
<math>A = \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><br />
<br />
<math>A = \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><br />
<br />
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular<br />
<br />
<math>A_0 = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math><br />
<br />
<math>A_1 = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math><br />
<br />
<math>A_2 = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math><br />
<br />
<math>A_3 = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math><br />
<br />
=== FFT para N diferente de uma potência de 2 ===<br />
<br />
Mesmo com a FFT sendo um algoritmo extremamente eficiente para <math>N = 2^p</math>, esse dificilmente é o caso que encotramos. Ainda assim, para <math>N</math> altamente composto (<math>N = r_1\cdot r_2 \cdot ... \cdot r_m</math>) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.</div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=698Grupo4 - FFT2017-10-23T15:35:08Z<p>Gabrgiov: </p>
<hr />
<div>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.<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
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 <math>[-\pi, \pi]</math> 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:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math><br />
<br />
A transformada também pode ser expressa em forma vetorial, como<br />
<br />
<math>\vec{F} = \mathbf{W^{nk}} \vec{f}</math> onde <math>\mathbf{W^{nk}}</math> é definido como<br />
<br />
<math>\mathbf{W^{nk}} = \begin{bmatrix}<br />
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\ <br />
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\ <br />
\vdots & \vdots & \ddots & \vdots\\ <br />
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}<br />
\end{bmatrix}</math><br />
<br />
O cálculo dessa expressão leva em torno de <math>N^2</math> 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.<br />
<br />
<br />
== Transformada Rápida de Fourier ==<br />
<br />
É possível calcular a transformada com <math>N \log_{2} N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.<br />
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT<br />
<br />
<math><br />
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}<br />
</math><br />
<br />
podemos dividir o somatório em 2:<br />
<br />
<math><br />
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)}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
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>.<br />
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math><br />
<br />
<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><br />
<br />
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.<br />
<br />
<br />
=== Exemplo ===<br />
<br />
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 <br />
<br />
<math>a_0 = 0.00</math><br />
<math>a_1 = 1.00</math><br />
<math>a_2 = 0.00</math><br />
<math>a_3 = -1.00</math><br />
<br />
Com essas 4 medidas, podemos dividir a soma 2 vezes:<br />
<br />
<math>\tilde{a_k} = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math><br />
<br />
<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><br />
<br />
<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><br />
<br />
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular<br />
<br />
<math>\tilde{a_0} = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math><br />
<br />
<math>\tilde{a_1} = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math><br />
<br />
<math>\tilde{a_2} = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math><br />
<br />
<math>\tilde{a_3} = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math><br />
<br />
=== FFT para N diferente de uma potência de 2 ===<br />
<br />
Mesmo com a FFT sendo um algoritmo extremamente eficiente para <math>N = 2^p</math>, esse dificilmente é o caso que encotramos. Ainda assim, para <math>N</math> altamente composto (<math>N = r_1\cdot r_2 \cdot ... \cdot r_m</math>) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.</div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=696Grupo4 - FFT2017-10-23T13:10:52Z<p>Gabrgiov: </p>
<hr />
<div>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.<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
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 <math>[-\pi, \pi]</math> 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:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math><br />
<br />
A transformada também pode ser expressa em forma vetorial, como<br />
<br />
<math>\vec{F} = \mathbf{W^{nk}} \vec{f}</math> onde <math>\mathbf{W^{nk}}</math> é definido como<br />
<br />
<math>\mathbf{W^{nk}} = \begin{bmatrix}<br />
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\ <br />
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\ <br />
\vdots & \vdots & \ddots & \vdots\\ <br />
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}<br />
\end{bmatrix}</math><br />
<br />
O cálculo dessa expressão leva em torno de <math>N^2</math> 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.<br />
<br />
<br />
== Transformada Rápida de Fourier ==<br />
<br />
É 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'''.<br />
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT<br />
<br />
<math><br />
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}<br />
</math><br />
<br />
podemos dividir o somatório em 2:<br />
<br />
<math><br />
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)}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
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>.<br />
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math><br />
<br />
<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><br />
<br />
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.<br />
<br />
<br />
=== Exemplo ===<br />
<br />
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 <br />
<br />
<math>a_0 = 0.00</math><br />
<math>a_1 = 1.00</math><br />
<math>a_2 = 0.00</math><br />
<math>a_3 = -1.00</math><br />
<br />
Com essas 4 medidas, podemos dividir a soma 2 vezes:<br />
<br />
<math>\tilde{a_k} = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math><br />
<br />
<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><br />
<br />
<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><br />
<br />
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular<br />
<br />
<math>\tilde{a_0} = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math><br />
<br />
<math>\tilde{a_1} = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math><br />
<br />
<math>\tilde{a_2} = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math><br />
<br />
<math>\tilde{a_3} = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math><br />
<br />
=== FFT para <math>N \neq 2^p</math> ====<br />
<br />
Mesmo com a FFT sendo um algoritmo extremamente eficiente para <math>N = 2^p</math>, esse dificilmente é o caso que encotramos. Ainda assim, para <math>N</math> altamente composto (<math>N = r_1\cdot r_2 \cdot ... \cdot r_m</math>) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.</div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=695Grupo4 - FFT2017-10-23T00:53:28Z<p>Gabrgiov: </p>
<hr />
<div>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.<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
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 <math>[-\pi, \pi]</math> 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:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math><br />
<br />
A transformada também pode ser expressa em forma vetorial, como<br />
<br />
<math>\vec{F} = \mathbf{W^{nk}} \vec{f}</math> onde <math>\mathbf{W^{nk}}</math> é definido como<br />
<br />
<math>\mathbf{W^{nk}} = \begin{bmatrix}<br />
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\ <br />
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\ <br />
\vdots & \vdots & \ddots & \vdots\\ <br />
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}<br />
\end{bmatrix}</math><br />
<br />
O cálculo dessa expressão leva em torno de <math>N^2</math> 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.<br />
<br />
<br />
== Transformada Rápida de Fourier ==<br />
<br />
É 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'''.<br />
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT<br />
<br />
<math><br />
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}<br />
</math><br />
<br />
podemos dividir o somatório em 2:<br />
<br />
<math><br />
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)}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
<math><br />
\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}<br />
</math><br />
<br />
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>.<br />
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math><br />
<br />
<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><br />
<br />
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.<br />
<br />
<br />
=== Exemplo ===<br />
<br />
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 <br />
<br />
<math>a_0 = 0.00</math><br />
<math>a_1 = 1.00</math><br />
<math>a_2 = 0.00</math><br />
<math>a_3 = -1.00</math><br />
<br />
Com essas 4 medidas, podemos dividir a soma 2 vezes:<br />
<br />
<math>\tilde{a_k} = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math><br />
<br />
<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><br />
<br />
<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><br />
<br />
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular<br />
<br />
<math>\tilde{a_0} = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math><br />
<br />
<math>\tilde{a_1} = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math><br />
<br />
<math>\tilde{a_2} = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math><br />
<br />
<math>\tilde{a_3} = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math></div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=694Grupo4 - FFT2017-10-22T23:46:28Z<p>Gabrgiov: </p>
<hr />
<div>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.<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
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 <math>[-\pi, \pi]</math> 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:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math><br />
<br />
A transformada também pode ser expressa em forma vetorial, como<br />
<br />
<math>\vec{F} = \mathbf{A} \vec{f}</math> onde <math>\mathbf{A}</math> é definido como<br />
<br />
<math>\mathbf{A} = \begin{bmatrix}<br />
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\ <br />
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\ <br />
\vdots & \vdots & \ddots & \vdots\\ <br />
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}<br />
\end{bmatrix}</math><br />
<br />
O cálculo dessa expressão leva em torno de <math>N^2</math> 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.<br />
<br />
<br />
== Transformada Rápida de Fourier ==<br />
<br />
É 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'''.<br />
<math><br />
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}<br />
</math><math><br />
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)} \\<br />
</math><math><br />
<br />
\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} \\<br />
</math><math><br />
\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}<br />
</math></div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=693Grupo4 - FFT2017-10-22T22:20:06Z<p>Gabrgiov: </p>
<hr />
<div>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.<br />
<br />
<br />
== Transformada Discreta de Fourier ==<br />
<br />
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.<br />
<br />
A transformada pode ser dada pela equação:<br />
<br />
<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math><br />
<br />
A sua inversa é, em paralelo ao caso da transformada contínua,<br />
<br />
<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math></div>Gabrgiovhttp://fiscomp.if.ufrgs.br/index.php?title=Grupo4_-_FFT&diff=692Grupo4 - FFT2017-10-22T17:27:29Z<p>Gabrgiov: Criou página com 'A Transformada rápida de Fourier (em inglês fast Fourier transform, ou FFT) é um algorítmo que torna o cálculo da Transformada Discreta de Fourier (DFT) viável para a ma...'</p>
<hr />
<div>A Transformada rápida de Fourier (em inglês fast Fourier transform, ou FFT) é um algorítmo que torna o cálculo da Transformada Discreta de Fourier (DFT) viável para a maior parte das aplicações.</div>Gabrgiov