Transformada Discreta de Fourier - Definição, Fórmula e Aplicações

Transformada Discreta de Fourier Com o advento do computador digital foi necessária uma adequação da transformada de Fourier para sinais de tempo discreto Considere uma sequência xn que é periódica com período N tal que xn xn kN para qualquer inteiro k e N é o período fundamental da sequência A sequência periódica xn pode ser expressa como Da periodicidade no domínio da frequência da transformada de Fourier discreta no tempo concluímos que existe um número finito de harmônicos as frequências 2πNk k 0 1 2 N1 Transformada Discreta de Fourier onde Xk k 0 1 são chamados de coeficientes da série discreta de Fourier sendo dados por onde xn é a sequência discreta no domínio do tempo que descreve os valores amostrados da variável contínua xt e N é o número de amostras da sequência da entrada Observe que Xk também é uma sequência periódica com período fundamental igual a N Ou seja Xk N Xk As equações 1 e 2 são a representação discreta em série de Fourier de sequências periódicas Transformada Discreta de Fourier Por conveniência de notação podemos chamar e assim o par de equações tornase Equação de análise Equação de síntese Tanto xn quanto Xk são sequências periódicas Transformada Discreta de Fourier Transformada Discreta de Fourier A Transformada Discreta de Fourier de uma sequência de Npontos é dada por Note que Xk também é uma sequência de Npontos ou seja ela não é definida fora do intervalo de 0 k N 1 A transformada discreta de Fourier inversa de uma DFT de Npontos Xk é dada por Novamente xn não é definida fora do intervalo 0 n N 1 Transformada Discreta de Fourier Exemplo Encontre a representação em série de Fourier da sequência xn 0 1 2 3 0 1 2 3 0 1 2 3 O período fundamental da sequência é N 4 Assim W4 ej2π4 ejπ2 cosπ2 jsenπ2 0 j1 j Dessa forma Transformada Discreta de Fourier Assim Transformada Discreta de Fourier Uma outra forma de ver a transformada discreta de Fourier é através de uma representação em matrizes Considere que x e X são vetores coluna correspondendo aos períodos primários das sequências xn e Xk respectivamente Então as equações de análise e síntese podem ser vistas como Transformada Discreta de Fourier Seja xn com N 4 podemos representar o cálculo da DFT de forma matricial Transformada Discreta de Fourier A matriz WN é chamada de matriz DFS Essa forma de calcular os coeficientes da série discreta de Fourier pode ser implementado no Matlab da seguinte forma Transformada Discreta de Fourier A transformada inversa pode ser obtida como Transformada Discreta de Fourier Transformada Discreta de Fourier Exemplo Considere uma sequência representando uma onda quadrada periódica apresentada na Figura a seguir Calcule a série discreta de Fourier para 20 amostras N20 Considere L5 o número de amostras iguais a 1 Transformada Discreta de Fourier Exemplo Considere uma sequência representando uma onda quadrada periódica apresentada na Figura a seguir Calcule a série discreta de Fourier para 20 amostras N20 Considere L5 o número de amostras iguais a 1 Transformada Discreta de Fourier Solucao Exemplo Considere uma sequência representando uma onda quadrada periódica apresentada na Figura a seguir Calcule a série discreta de Fourier para 20 amostras N20 Considere L5 o número de amostras iguais a 1 Transformada Rápida de Fourier FFT As transformadas rápidas de Fourier mais conhecidas por FFT Fast Fourier Transforms nada mais são do que algoritmos para computador desenvolvidos especialmente para realizar a transformada discreta de Fourier de forma rápida e eficiente Existem inúmeras variantes desses algoritmos cada um otimizando o desempenho para um tipo de resultado diferente que se espera obter no final Transformada Discreta de Fourier FFT DFS Transformada Rápida de Fourier FFT Transformada Discreta de Fourier FFT é o método computacional mais eficiente para implementação da DFT Discrete Fourier Transform O algoritmo foi desenvolvido por volta de 1960 por dois matemáticos Cooley e Tukey e consegue executar a DFT a partir de uma série de pontos amostrados do sinal original sem conhecer a função matemática que os gerou Transformada Rápida de Fourier FFT Transformada Discreta de Fourier Transformada Rápida de Fourier FFT Fast Fourier Transform Embora a DFT seja o melhor procedimento matemático para determinar o conteúdo espectral de uma sequência no domínio do tempo ela é muito ineficiente Em 1965 um artigo foi publicado por JWCooley e JWTukey descrevendo um algoritmo eficiente para implementação da DFT este algoritmo ficou conhecido como Transformada rápida de Fourier FFT Antes do advento da FFT a DFT com muitos pontos estava restrita a grandes centros de pesquisas Graças a Cooley e Tukey e a indústria dos semicondutores DFTs com 1024 pontos podem ser calculadas em apenas alguns segundos em computadores pessoais Transformada Rápida de Fourier FFT Fast Fourier Transform A FFT foi implementada com o objetivo de diminuir complexidade temporal necessária para calcular uma DFT Transformada Discreta de Fourier visando aplicações em tempo real Para uma sequência de N pontos o algoritmo comum para cálculo da DFT realiza N2 multiplicações enquanto o algoritmo FFT realiza apenas N2log2N Transformada Rápida de Fourier FFT Fast Fourier Transform Algoritmos Rápidos Existem diversos algoritmos para executar computações Por exemplo há diversos algoritmos dedicados à ordenação de uma sequência O que difere esses algoritmos é o tempo de resposta deles ou a chamada complexidade do algoritmo No entanto a análise de complexidade de um algoritmo não considera detalhes de implementação Nesse sentido os algoritmos rápidos propõem modificações na forma de resolver algum problema a fim de conseguir um ganho de tempo de processamento Transformada Rápida de Fourier FFT Fast Fourier Transform Por exemplo considere a computação da variável A dada por A ac ad bc bd Esse cálculo direto leva o programa a executar 4 multiplicações e 3 adições Essa expressão no entanto pode ser simplificada para A a bc d provocando uma redução das operações para apenas 1 multiplicação e 2 adições Em geral a multiplicação é o elemento de maior custo considerado Observamos que essa expressão é equivalente à primeira apenas executando menos operações aritméticas Transformada Rápida de Fourier Decimação no Tempo Algoritmo de CooleyTukey ou Decimação no Tempo JWCooley IBM em colaboração com JWTukey Bell Labs conseguiram uma revolução maior no tratamento digital de sinais em 1965 com a publicação da transformada rápida de Fourier a FFT Tratase de um método engenhoso e altamente eficiente de reagrupar os cálculos dos coeficientes de uma DFT A idéia é representar uma DFT de tamanho arbitrário N N1N2 em termos de DFTs menores de tamanhos N1 e N2 procedendo recursivamente Lembrando que os coeficientes da DFT são definidos por onde k 0 1 2 N 1 Calculada assim diretamente a DFT requer o N2 operações A idéia do algoritmo de CooleyTukey é dividir a sequência xn em duas sequências uma com os coeficientes de índice par e outra com os coeficientes de índice ímpar Como a quebra é em duas sequências o algoritmo é conhecido também como Radix2 Algoritmos no qual a sequência é decomposta sucessivamente em sequências menores são chamados de algoritmos de decimação em tempo Transformada Rápida de Fourier Decimação no Tempo O princípio do algoritmo de decimação em tempo pode ser analisado considerando que N é um inteiro potência de 2 ie N 2v Como N é um inteiro par podemos considerar calcular Xk separando xn em duas sequências de N2 pontos consistindo dos pontos de índice par em xn e os pontos de índice ímpar em xn Como Xk é dado pela Equação Transformada Rápida de Fourier Decimação no Tempo Separando xn no pontos de índice par e ímpar Substituindo as variáveis n 2r para n par e n 2r 1 para n ímpar Transformada Rápida de Fourier Decimação no Tempo Consequentemente a equação pode ser escrita como Transformada Rápida de Fourier Decimação no Tempo Transformada Rápida de Fourier Decimação no Tempo Cada parcela na equação é reconhecida como uma DFT de N2 pontos Sendo que a primeira parcela uma DFT de N2 pontos que são os pontos de índice par da sequência original e o segundo termo uma DFT de N2 pontos os pontos de índice ímpar da sequência original Transformada Rápida de Fourier Decimação no Tempo Para uma DFT de N 8 pontos temos o seguinte cálculo com duas DFTs de 4 pontos Transformada Rápida de Fourier Decimação no Tempo Transformada Rápida de Fourier Decimação no Tempo Este algoritmo consegue a partir de combinações realizadas entre os valores das amostras gerar o espectro de frequências do sinal original e viceversa A principal diferença entre a FFT e a transformada de Fourier é que para aplicar se a transformada de Fourier é necessário conhecer a função no domínio do tempo para obterse a função no domínio da frequência porém quando aplicase a FFT basta conhecer os pontos que compõe a função no domínio do tempo para gerar os pontos que compõe a função no domínio da frequência A FFT é uma ferramenta muito aplicada no processamento digital de sinais pois na maioria dos casos a função do sinal amostrado é desconhecida Transformada Rápida de Fourier FFT Transformada Discreta de Fourier Transformada Discreta de Fourier Exemplo Transformada Discreta de Fourier Sequencia Magnitude da Resposta em Frequencia Fase Transformada Discreta de Fourier Observe que como o sinal xn é real a magnitude da resposta em frequência apresenta uma imagem refletida Assim precisamos apenas da primeira metade dela Para a fase o padrão também aparece refletido no eixo da freqüência novamente só precisamos de metade da plotagem Para a questão da magnitude podemos fazer halfm 0ceillengthX2 stemhalfmfslengthX absXhalfm 1 b ylabelmagnitude xlabelfrequencia Hz titleMagnitude da Resposta em Frequencia Transformada Discreta de Fourier n 0199 fs200 Ts1fs x cos2pi20nTs pi4 3cos2pi40nTs 2pi5 2cos2pi60nTs pi8 X fft x subplot 311 plot x hold on stemx xlabeln ylabel xn title sequencia subplot 312 stemhalfmfslengthX absXhalfm 1b ylabel magnitude xlabelfrequencia Hz title magnitude subplot 313 stemhalfmfslengthX angleXhalfm 1 b ylabel Angulo xlabelfrequencia Hz title Fase Transformada Discreta de Fourier secuencia magnitude Fase Transformada Discreta de Fourier Transformada Discreta de Fourier Transformada Discreta de Fourier Transformada Discreta de Fourier A Série Discreta de Fourier A Série Discreta de Fourier