FFT-DFT-Transformada-de-Fourier-Rapida-e-Discreta-Conceitos-e-Algoritmos

Links que podem ajudar httpsyoutubeBPfpw1Mg4 httpsyoutubemkGsMWij4Q A DFT e a IDFT são descritas da seguinte forma DFT Xk Σn0N1 xnWNkn 0 k N 1 IDFT xn 1N Σk0N1 XkWNkn 0 n N 1 Onde WN ej 2πN A fim de calcular transformadas para sequências de cumprimento N é preciso realizar em torno de N2 multiplicaçōes complexas e N 1N adições Isso limita severamente seu uso prático X 𝑒𝑗𝑗Ω 2 cos Ω 2 2 cos 3Ω 2 𝑒𝑗𝑗3Ω2 Ω𝑘 2𝜋𝑘 𝑘 0 3 4 Ω𝑘 2𝜋𝑘 3 𝑘 0 2 Introdução Com a contribuição de Cooley e Tukey em 1965 propuseram um algoritmo eficiente para calcular a DFT o qual requer um número de multiplicações complexas da ordem de 𝑁 log2 𝑁 Isso pode representar um decréscimo extraordinário na complexidade Por exemplo mesmo para sinais de cumprimento N1024 amostras seria 𝑁2 1 048 576 e 𝑁 log2 𝑁 10 240 uma redução na complexidade da ordem de 100 vezes O advento do algoritmo abriu um leque inesgotável de aplicações para a DFT indo desde a análise de sinais até filtragem linear rápida Introdução Hoje há um número enorme de algoritmos rápidos para cálculo da DFT coletivamente conhecidos como algoritmos FFT Fast Fourier Transform Quanto a redução de operações duas formas Dizimação no tempo e Dizimação na frequência Quanto a decomposição das raízes Radix2 Radix4 Radix8 Radix16 ou raízes duplas Radix2 e Radix4 por exemplo Ou a decomposição para valores arbitrários de N Algoritmo Radix 2 de raiz 2 com dizimação no tempo Suponha que temos uma sequência xn de comprimento potência de dois isto é N 2l Podemos representar o somatório dos coeficientes em duas partes uma com os elementos xn de índice par e outra os elementos xn de índice ímpar obtendo as relações Xk Σn0N1 xnWNnk Índice par Índice ímpar Σn0N21 x2nWN2nk Σn0N21 x2n 1WN2n1k Σn0N21 x2nWN2nk WNk Σn0N21 x2n 1WN2nk k 0 1 N 1 Se notarmos que para N termos amostras temos WN2nk ejj 2πN 2nk ejj 2π N2 nk WN2nk Então a equação se torna Xk Σn0N21 x2nWN2nk WNk Σn0N21 x2n 1WN2nk k 0 1 N 1 Podemos ver que cada somatório pode representar uma DFT distinta de tamanho N2 Portanto uma DFT de tamanho N pode ser calculada através de duas DFTs de tamanho N2 além das multiplicaçōes por WNk Algumas relações importantes WN2 WN2 WNk N2 WNk WNk N WNk Xk n0 N1 xnWnkN Xk n0 N21 x2nWnkN2 WkN2 n0 N21 x2n 1WnkN2 Xk X11k WkN X12k k 0N 1 Por exemplo para oito amostras 𝑁 2 𝑁 2 Portanto o cálculo da DFT requer 2 2 𝑁 𝑁2 2 𝑁 multiplicações complexas e 2 2 𝑁 𝑁2 2 o número total de adições complexas resultando num decréscimo de complexidade quando comparada ao cálculo usual da DFT de maneira direta só para uma redução Por exemplo se N1024 o cálculo direto da DFT requer 10241024 1048576 multiplicações complexas e 10241023 1047552 adições complexas enquanto que o cálculo pelo método descrito requer 25125121024 525312 multiplicações complexas e 25125111024 524288 adições complexas 𝑁 2 Se formos continuar reduzindo o procedimento completo é formalizado num algoritmo Primeiro descrevemos a equação como Xk Xpk WkN Xiik Onde Xpk e Xiik são respectivamente as DFTs de comprimento N2 das amostras com índices pares é ímpares do sinal xn a ser representado Isto é Xpk n0 N21 x2nWnkN2 n0 N21 xpnWnkN2 k 01N21 Xiik n0 N21 x2n 1WnkN2 n0 N21 xiinWnkN2 k 01N21 Se Xk Xpk WkN Xiik Das DFTs Xpk n0 N21 xpnWnkN2 Xiik n0 N21 xiinWnkN2 Outras DFTs podem ser calculadas a seguir como Xpk n0 N41 xp2nWnkN4 WkN2 n0 N41 xp2n 1WnkN4 k 01N41 Xiik n0 N41 xii2nWnkN4 WkN2 n0 N41 xii2n 1WnkN4 k 01N41 𝐿 X𝑘 X𝑝𝑘 W𝑘X𝑖𝑖 𝑘 𝑁 X𝑟𝑘 X𝑟𝑝𝑘 W𝑘X𝑟𝑖𝑖 𝑘 𝐿 De forma que Onde X𝑝𝑝𝑘 X𝑝𝑖𝑖 𝑘 X𝑖𝑖𝑝𝑘 e X𝑖𝑖𝑖𝑖 𝑘 correspondem agora as DFTs de comprimento N4 Genericamente em cada etapa calculamos DFTs de comprimento L usando DFTs de comprimento L2 ou seja A aplicação recursiva do procedimento descrito pode conduzir o cálculo da DFT de comprimento 𝑁 2𝑙 ao longo de 𝑙 etapas até o cálculo de 2𝑙 DFTs de comprimento 1 porque cada etapa converte uma DFT de comprimento L em duas DFTs de comprimento L2 mais uma multiplicação complexa por W𝑘 e uma soma complexa X𝑝𝑘 X𝑝𝑝𝑘 W𝑘X𝑝𝑖𝑖 𝑘 𝑁 2 X𝑖𝑖 𝑘 X𝑖𝑖𝑝𝑘 W𝑘X𝑖𝑖𝑖𝑖 𝑘 𝑁 2 Esse algoritmo de FFT é conhecido como algoritmo com dizimação no X 𝑘 X 𝑘 W𝑘X 𝑘 𝑟 𝑟𝑝 𝐿 𝑟𝑖𝑖 𝐿 𝑘 0 1 2 X𝑟 𝑘 X𝑟𝑝 𝑘 W𝐿 𝐿 𝐿 𝑘𝐿 2 2 2X𝑟𝑖𝑖 𝑘 𝐿 2 𝑘 0 1 𝐿 2 X𝑟𝑝𝑘 W𝐿 2X𝑟𝑖𝑖𝑘 𝑘𝐿 W𝑘 𝐿 1 tempo porque divide recursivamente a sequencia xn de L pontos em subsequências Portanto se temos as DFTs de comprimento 𝐿 podemos calcular a DFT de 2 comprimento L com X𝑟𝑝𝑘 𝑘 0 𝐿 2 1 1 X𝑟𝑘 X𝑟𝑖𝑖 𝑘 𝐿 𝑘 X𝑟 𝐿 𝑘 2 Célula básica por vezes chamada de borboleta W𝐿 2 O processo descrito de repetição da célula básica para 𝑁 𝐿 𝑁 2 𝐿 2 e para 𝑘 0 1 2 A figura ilustra para N8 No processo podese obter alguma economia adicional no número de 1 1 W W 2 W𝑘W2 W𝑘W2 W𝑘 𝑘𝐿 𝐿 𝐿 𝐿 𝐿 𝐿 𝐿 Então as equações podem ser rescritas como X 𝑘 X 𝑘 W𝑘X 𝑟 𝑟𝑝 𝐿 𝑟𝑖𝑖 𝑘 onde 𝐿 𝑘 0 1 2 X𝑟 𝑘 𝐿 2 X𝑟𝑝𝑘 W𝑘X𝑟𝑖𝑖 𝑘 𝐿 𝐿 onde 𝑘 0 1 2 multiplicações requeridas sendo 1 1 X𝑟𝑝𝑘 X𝑟𝑘 X𝑟𝑖𝑖 𝑘 𝑘 𝐿 X𝑟 1 𝐿 𝑘 2 L tem que ser potência de dois permitindo a implementação mais eficiente da célula básica Repetindo o processo descrito para o caso N8 Exemplo Determine as expressões do algoritmo FFT para uma sequência de 8 amostras n 0 1 2 3 4 5 6 7 xn x0 x1 x2 x3 x4 x5 x6 x7 Partindo da DFT temos Xk n07 xnW8nk Xiik m03 xiimW4mk para ii 12 E em seguida Xk X1k W8kX2k Xk 4 X1k W8kX2k para k 0123 Sendo assim temos m 0 1 2 3 x1m x0 x2 x4 x6 x2m x1 x3 x5 x7 X1k X11k W4kX12k X1k 2 X11k W4kX12k X2k X21k W4kX22k X2k 2 X21k W4kX22k Decompondo mais uma vez temos Xiijjk m01 xiijjmW2mk xiijj0 W2kxiijj1 Xiijjk 1 xiijj0 W2kxiijj1 para ii 12 jj 12 k 0 Sendo assim temos m 0 1 x11m x0 x4 x12m x2 x6 x21m x1 x5 x22m x3 x7 logo X11k x0 W2kx4 x0 x4 X11k 1 x0 W2kx4 x0 x4 X12k x2 W2kx6 x2 x6 X12k 1 x2 W2kx6 x2 x6 X21k x1 W2kx5 x1 x5 X21k 1 x1 W2kx5 x1 x5 X22k x3 W2kx7 x3 x7 X22k 1 x3 W2kx7 x3 x7 para k 0 logo 4 4 4 4 4 8 8 8 8 8 X10 X110 W0X120 X0 X 0 W0X 0 4 X11 X111 W1X121 1 8 2 1 4 X12 X110 W0X120 X13 X111 W1X121 X20 X210 W0X220 X21 X211 W1X221 X22 X210 W0X220 X23 X211 W1X221 X1 X11 W8 X21 X2 X12 W2X22 X3 X13 W3X13 X4 X10 W0X20 X5 X11 W1X21 X6 X12 W2X22 X7 X 3 W3X 3 4 1 8 2 k 0 1 2 3 4 5 6 7 X𝑘 X0 X1 X2 X3 X4 X5 X6 X7 Dízimação na Frequência proposto por Sande e Tukey um algoritmo alternativo para o cálculo da DFT isto é a divisão de Xk em subsequências O algoritmo é gerado para uma sequencia xn como segue Xk n0N1 xnWNnk n0N21 xnWNnk nN2N1 xnWNnk n0N21 xnWNnk n0N21 xn N2WNN2 k WNnk n0N21 xn WNN2 k xn N2 WNnk Agora podemos calcular separadamente as amostras pares e ímpares de Xk isto é X2lsumn0fracN21 xn WNn x leftnfracN2right WN2nl sumn0fracN21 leftx n x leftnfracN2rightright WN2nl Para l012leftfracN21right e X2 l1sumn0fracN21 leftx n WNn2 l1 fracN2 xleftnfracN2rightright WN2 l1 n sumn0fracN21 leftxnxleftnfracN2rightright WN2 l1 n sumn0fracN21 leftxnxleftnfracN2rightright WNn WN2 n l Para l012leftfracN21right Temos as equações X2 lsumn0fracN21 leftx n x leftnfracN2rightright WN2nl e X2 l1sumn0fracN21 leftx n x leftnfracN2rightright WNn WN2 n l Para l012leftfracN21right Podem ser reconhecidas como DFTs de comprimento N2 já que WN2 n lWfracN2n l Antes de avaliarmos as DFTs calculamos os sinais intermediários spn e siin de comprimento N2 dados por e naturalmente repetidos por spnxn xleftnfracN2right siinleftxn xleftnfracN2rightright WNn srpnxr n xrleftnfracN2right srinleftxrn xrleftnfracN2rightright WNn Do resultando destas duas expressões é possível obter dois elementos de Xk Um produto e duas somas A figura mostra o algoritmo completo da FFT com dizimação na frequência 1 1 W para N8 A estrutura do algoritmo aponta para a sua realização andar a andar num total de log2𝑁 andares e de N2 borboletas butterflies por andar cada uma das quais do tipo 𝑠𝑟𝑛 𝑠𝑟𝑝𝑛 𝑠𝑟 𝐿 𝑛 2 1 𝑛 𝐿 𝑠𝑟𝑖𝑖 𝑛 Os de raiz dupla baseiamse no uso simultâneo das raízes 2 e 4 Comparando para N8 Se N1024 Para o cálculo da iDFT pode ser usado com simples adaptações da DFT Uma possibilidade consiste em notar que xnN1DFTXk e que xn obtémse de xn de modo circular Assim a iDFT pode ser calculada utilizando o programa de cálculo da DFT com os coeficientes Xk dividindo os resultados obtidos por N e reordenando refletindo as posições dos elementos de ordem n e Nn Ou alternativamente xnN1DFTXkN1sumk0N1 XkWNnkN1sumk0N1 XkWNnk