|
|
(5 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) |
Linha 167: |
Linha 167: |
| | | |
| então | | então |
− | :<math> e^{j(2 \pi /N)k} = \omega_N^k \ </math> | + | :<math> e^{-j(2 \pi /N)k} = \omega_N^k \ </math> |
| | | |
| Essa frequência corresponde a uma posição no circulo unitário do plano complexo <math> z \ </math>. | | Essa frequência corresponde a uma posição no circulo unitário do plano complexo <math> z \ </math>. |
Linha 272: |
Linha 272: |
| | | |
| === Transformada Rápida de Fourier (FFT) === | | === Transformada Rápida de Fourier (FFT) === |
− | O cálculo da TDF e TDFI para uma sequência de dados de comprimento <math> N \ </math> necessita de <math> N^2 \ </math> multiplicações complexas, limitando o seu uso em aplicações práticas. Em 1965, Cooley e Tukey propuseram um algoritmo rápido (FFT) para calcular a TDF com um número de multiplicações complexas na ordem de <math> \mathrm{ O(N \times log_2(N)} \ </math>N. Esse mudança faz com que uma sequência de comprimento 1024, calculado com a TDF demanda 1024x1024 multiplicações, enquanto que com a FFT apenas 1024x10. Isso representa neste caso uma redução de complexidade de 100 vezes. | + | O cálculo da TDF e TDFI para uma sequência de dados de comprimento <math> N \ </math> necessita de <math> N^2 \ </math> multiplicações complexas, limitando o seu uso em aplicações práticas. Em 1965, [https://www.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1/S0025-5718-1965-0178586-1.pdf Cooley e Tukey] propuseram um algoritmo rápido (FFT) para calcular a TDF com um número de multiplicações complexas na ordem de <math> \mathrm{ O(N \times log_2N)} \ </math>. Esse mudança faz com que uma sequência de comprimento 1024, calculado com a TDF demanda 1024x1024 multiplicações, enquanto que com a FFT apenas 1024x10. Isso representa neste caso uma redução de complexidade de 100 vezes. |
| | | |
| Atualmente existem diversos algoritmos de FFT, que obtêm exatamente o mesmo valor que o uso da TDF, mas eles podem ser classificados de forma geral em decimação no tempo, ou decimação na frequência, dependendo de qual vetor será decimado e reordenado, se o sinal no tempo <math> x(n) \ </math> ou as frequencia <math> X(k) \ </math>. | | Atualmente existem diversos algoritmos de FFT, que obtêm exatamente o mesmo valor que o uso da TDF, mas eles podem ser classificados de forma geral em decimação no tempo, ou decimação na frequência, dependendo de qual vetor será decimado e reordenado, se o sinal no tempo <math> x(n) \ </math> ou as frequencia <math> X(k) \ </math>. |
| | | |
| + | Ver este e-book [https://cnx.org/exports/d2c6d393-3590-403d-8a18-c892055b046b@2.2.pdf/the-dft-fft-and-practical-spectral-analysis-2.2.pdf The DFT, FFT, and Practical Spectral Analysis] em OpenStax CNX, e também a [https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm wikipedia] que tem esse artigo muito bem escrito sobre o assunto. |
| | | |
| *Para relembrar os conceitos vistos acima, recomendo assistir os vídeos sobre DFT e FFT do prof. Steve Brunton da University of Washington | | *Para relembrar os conceitos vistos acima, recomendo assistir os vídeos sobre DFT e FFT do prof. Steve Brunton da University of Washington |
Linha 284: |
Linha 285: |
| ! The Fast Fourier Transform (FFT) | | ! The Fast Fourier Transform (FFT) |
| ! The Fast Fourier Transform Algorithm | | ! The Fast Fourier Transform Algorithm |
| + | | What is a Fast Fourier Transform (FFT)? |
| |- | | |- |
| |{{#ev:youtube|nl9TZanwbBk|300}} | | |{{#ev:youtube|nl9TZanwbBk|300}} |
Linha 289: |
Linha 291: |
| |{{#ev:youtube|E8HeD-MUrjY|300}} | | |{{#ev:youtube|E8HeD-MUrjY|300}} |
| |{{#ev:youtube|toj_IoCQE-4|300}} | | |{{#ev:youtube|toj_IoCQE-4|300}} |
| + | |{{#ev:youtube|XtypWS8HZco|300}} |
| |} | | |} |
| | | |
Transformada de Fourier no tempo contínuo (TFTC)
O sinal
é contínuo no tempo, e o sinal
é contínuo na frequência.
- A equação de análise
- É uma transformação de um domínio de uma variável real
de tempo continuo em uma variável complexa
de frequência contínua.
.
.
![{\displaystyle \mathrm {X(j\Omega )\equiv {\mathcal {F}}\{x(t)\}\ {\overset {\underset {\mathrm {def} }{}}{=}}\int _{-\infty }^{\infty }x(t)\ e^{-j\Omega t}\operatorname {d} \!t} }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/97e853c598ef08c8c929a7d36a2d5edb86da8c3d)
- A equação de síntese
- É uma transformação de um domínio de uma variável complexa
de frequência contínua em uma variável real
de tempo continuo.
.
.
![{\displaystyle \mathrm {x(t)\equiv {\mathcal {F}}^{-1}\{X(j\Omega )\}\ {\overset {\underset {\mathrm {def} }{}}{=}}{\frac {1}{2\pi }}\int _{-\infty }^{\infty }X(j\Omega )\ e^{j\Omega t}\operatorname {d} \!\Omega } }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/e73403c5442554e3cca8a1a3d65aa90941923cd5)
- A transformada de Fourier
, por simplificação é muitas vezes representada apenas por
ou
, mas é importante lembrar que tratasse de uma frequência complexa, representada pelo eixo imaginário do plano s.
Figura 1 - Sinal
e sua transformada de Fourier
Fonte: Elaborado pelo autor.
- Para relembrar os conceitos vistos em Sinais e Sistemas, recomendo assitir os vídeos sobre Transformada de Fourier do prof. Luis Antonio Aguirre da UFMG
Introdução a Transformada de Fourier
|
Existência da Transformada Fourier
|
Transformada de Fourier: Propriedades 1
|
Transformada de Fourier: Propriedades 2
|
Transformada de Fourier para Sinais Periodicos
|
|
|
|
|
|
Transformada Z
A transformada Z de um sinal de tempo discreto
é a função
definida como
![{\displaystyle X(z)=Z\{x(n)\}=\sum _{n=-\infty }^{\infty }x(n)z^{-n}\ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f7a02f60f965c8048bbcbf2b3edc157c8e7db37f)
- onde
é um inteiro;
é um número complexo, com
sendo sua magnitude, e
sua frequência angular (em radianos por amostra).
A transformada Z inversa é
![{\displaystyle x(n)=Z^{-1}\{X(z)\}={\frac {1}{2\pi j}}\oint _{C}X(z)z^{n-1}dz\ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ac8dd3e55754bc1cde3414979d78f8563dbedb72)
onde
é o caminho antihorário envolvendo a origem, dentro da região de convergencia (ROC) de
.
Transformada de Fourier de tempo discreto (TFTD)
O sinal
é discreto no tempo, e o sinal
é contínuo e periódico em
.
- A equação de análise
- É uma transformação de um domínio de uma variável real
de tempo discreto em uma variável complexa
frequência contínua periódica.
.
.
![{\displaystyle \mathrm {X(e^{j\omega })\equiv {\mathcal {F}}\{x(n)\}\ {\overset {\underset {\mathrm {def} }{}}{=}}\sum _{n=-\infty }^{\infty }x(n)\ e^{-j\omega n}} }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ead240740c78145db36922dc995013e104d99033)
- A equação de síntese
- É uma transformação de um domínio de uma variável complexa
de frequência contínua periódica em uma variável real
continua.
.
.
![{\displaystyle \mathrm {x(n)\equiv {\mathcal {F}}^{-1}\{X(e^{j\omega })\}\ {\overset {\underset {\mathrm {def} }{}}{=}}{\frac {1}{2\pi }}\int _{-\infty }^{\infty }X(e^{j\omega })\ e^{j\omega n}\operatorname {d} \omega } }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/d785cc49f67a3c4b49f32bf8a2b15585b819309f)
Como a transformada de Fourier
é periódica com período
, pois
, para
, ela pode ser calculada em qualquer faixa de
, por exemplo
.
![{\displaystyle \mathrm {x(n)\equiv {\mathcal {F}}^{-1}\{X(e^{j\omega })\}\ {\overset {\underset {\mathrm {def} }{}}{=}}{\frac {1}{2\pi }}\int _{-\pi }^{\pi }X(e^{j\omega })\ e^{j\omega n}\operatorname {d} \omega } }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/3a322e00420513b2d921eee1fefbde306164d6fa)
Figura 2 - Sinal discreto
e sua TFDT
Fonte: Elaborado pelo autor.
Série de Fourier de tempo contínuo (SF)
O sinal
é contínuo e periódico no tempo (com período
) , e o sinal
é discreto na frequência.
- A equação de análise
- É uma transformação de um domínio de uma variável real
de tempo continuo em uma variável complexa
de frequência discreta.
.
.
![{\displaystyle X(k)={\frac {1}{T}}\int _{0}^{T}x(t)e^{-j(2\pi /T)kt)}\mathrm {d} t}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/53c0134337f64986a2f6f54e56246ccd12e5bc04)
- A equação de síntese
- É uma transformação de um domínio de uma variável complexa
de frequência contínua em uma variável real
de tempo continuo.
.
.
![{\displaystyle x(t)=\sum _{k=-\infty }^{\infty }X(k)e^{j(2\pi /T)kt)}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/27dbe5d69c419d58786be0e8f151374f5e638562)
- A série de Fourier
, indicada acima é a série exponencial onde as funções de base são exponenciais complexas
, onde
. Também existem as séries de Fourier usando funções de base senoidais e cossenoidais, as quais podem ser derivadas da série exponencial.
Figura 3 - Sinal
periódico e sua série de Fourier
800 px
Fonte: Elaborado pelo autor.
Transformada de Discreta de Fourier (TDF)
Discrete Fourier Transform (DFT).
Obtenção da TDF a partir da amostragem da TFTD
Sinais discretos no tempo podem ser representados pela sua TFTD, que é uma função continua periódica em
de
:
![{\displaystyle \mathrm {X(e^{j\omega })=\sum _{n=-\infty }^{\infty }x(n)e^{-j\omega n}} }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/5b4de9a45e47a991d44a93387985800a43014ab1)
Para que a mesma possa ser utilizada no processamento de sinais digitais é necessário que a variável frequência seja também discreta. Se amostrarmos uniformemente a frequência
em N amostras entre 0 e
é possível obter a TDF (ou DFT - Discrete Fourier Transform). Assim se tomarmos N frequências
com
, and
, obtemos o espectro amostrado uniformemente:
.
![{\displaystyle \mathrm {X'(e^{j\omega })=\sum _{n=-\infty }^{\infty }x(n)e^{-j{\frac {2\pi }{N}}kn}} }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/a94b348aebcf4cbe67df632d69b565e6f2f1d504)
O sinal equivalente no tempo pode ser obtido aplicando a transformada inversa e a convolução:
.
O que mostra que o sinal Esse sinal
são repetições periódicas (com período N) do sinal discreto
original.
- Note que N o período de repetição do sinal
é o mesmo período de repetição das N amostras da TFTD
original.
- Se o comprimento L o sinal do
for maior que N o período de repetição do sinal
, haverá sobreposição das amostras no tempo (time aliasing), e não será possível recuperar o sinal original.
- Por outro lado, se
então
é a repetição periódica exata de
.
, para
ou
.
Portanto, é possível recuperar as amostras do sinal digital no tempo
a partir das suas amostras digitais na frequência, desde que o período de repetição das N amostras de frequência seja maior ou igual ao comprimento L do sinal no tempo.
TDF e TDFI
O sinal
é discreto no tempo pode ser representado pelo o sinal
ou
discreto e periódico em
.
Para obter a equação de análise (DFT) pode ser feito o cálculo das amostras do espectro de frequências em
em:
![{\displaystyle \mathrm {X(e^{j\omega })=\sum _{n=-\infty }^{\infty }x(n)e^{-j\omega n}} }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/5b4de9a45e47a991d44a93387985800a43014ab1)
![{\displaystyle \mathrm {X(e^{j(2\pi /N)k})=\sum _{n=-\infty }^{\infty }x(n)e^{-j(2\pi /N)kn}} }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/efb4acc1db7873e79ddf191bbda97b620f6bac71)
Conforme mostrado, o espectro é periódico em N, e portanto é suficiente calcular apenas os valores para
. Assim obtém-se
- A equação de análise (TDF)
- É uma transformação de um domínio de uma variável real
de tempo discreto em uma variável complexa
frequência discreta periódica.
.
.
, para ![{\displaystyle \mathrm {0\leq k\leq N-1} \ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/62546c1f2d40d8f67fd5811c6dc4c1026e4b932f)
- A equação de síntese (TDFI)
- É uma transformação de um domínio de uma variável complexa
de frequência discreta periódica em uma variável real
discreta.
.
.
, para ![{\displaystyle \mathrm {0\leq n\leq N-1} \ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ca3b6990577482ad48c8d10dc2961a3c7107f902)
Ao usar a equação de análise, se o comprimento L de
for menor que o período de repetição N, é necessário que
seja preenchido com amostras nulas até atingir o comprimento N (zero-padding).
Equação simplificada da TDF e TDFI
Para simplificar a notação pode-se utilizar para representar as frequência discreta:
,
definir a frequência fundamental
como:
![{\displaystyle \omega _{N}=e^{-j2\pi /N}\ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/3d3a85308e749a4bb0eef21147c7ed18a8762403)
então
![{\displaystyle e^{-j(2\pi /N)k}=\omega _{N}^{k}\ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ddb422ad8e7bbd1cffb207a39dcef1144f97ed84)
Essa frequência corresponde a uma posição no circulo unitário do plano complexo
.
Alguns valores de
que ajudam a lembrar as simplificações:
![{\displaystyle \omega _{1}=e^{-j2\pi }=+1\ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/8ac50d80db50ac16d5ab079abd89a95dd00d5869)
![{\displaystyle \omega _{-1}=e^{j2\pi }=+1\ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/c5d7d792f58506f1ae9ebfd3fa44238300514bcc)
![{\displaystyle \omega _{2}=e^{-j\pi }=-1\ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b2402296f047b8621862921fa386a1cbf3587c25)
![{\displaystyle \omega _{-2}=e^{j\pi }=-1\ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/3326ffe13cb6db9d5523bd53b753250de7e6e802)
![{\displaystyle \omega _{4}=e^{-j\pi /2}=-j\ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/6ab1a54dd83a3abfef0dd00e5e23c0e16842ae0c)
![{\displaystyle \omega _{-4}=e^{j\pi /2}=+j\ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/e689aadcdb49e2a8a6d109b0b16f92fb816341c8)
Também é importante lembrar que se
é múltiplo de
então:
![{\displaystyle \omega _{N}^{k}=e^{-j(2\pi /N)k}=e^{-j2\pi /(N/k)}=\omega _{N/k}\ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/d18046b1df801e3bf4313247100193a6203c866a)
Dessa forma as equações da TDF e TDFI passam a ser escritas de forma simplificada como:
- Equação de análise
, para ![{\displaystyle \mathrm {0\leq k\leq N-1} \ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/62546c1f2d40d8f67fd5811c6dc4c1026e4b932f)
- Equação de síntese
, para ![{\displaystyle \mathrm {0\leq n\leq N-1} \ }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ca3b6990577482ad48c8d10dc2961a3c7107f902)
Dessas equações é possível perceber que o cálculo da TDF e da TDFI requerem a
multiplicações e
somas, sendo portanto um algoritmo de
.
Notação matricial de TDF e TDFI
Em notação matricial cada
na TDF e
na TDFI podem ser calculado como:
![{\displaystyle X(k)={\begin{bmatrix}\omega _{N}^{0}&\omega _{N}^{k}&\omega _{N}^{2k}&...&\omega _{N}^{(N-1)k}\\\end{bmatrix}}\times {\begin{bmatrix}x(0)\\x(1)\\x(2)\\\vdots \\x(N-1)\end{bmatrix}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/168955ae42bc70460e93c3a226005f5b1bfffe4f)
![{\displaystyle x(k)={\frac {1}{N}}{\begin{bmatrix}\omega _{N}^{0}&\omega _{N}^{-k}&\omega _{N}^{-2k}&...&\omega _{N}^{-(N-1)k}\\\end{bmatrix}}\times {\begin{bmatrix}X(0)\\X(1)\\X(2)\\\vdots \\X(N-1)\end{bmatrix}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b8c960fbb6d0ecf93df73844a75c9bcfe26da2b4)
Porém como
as equações TDF e TDFI podem ser escritas em notação matricial:
- Equação de análise
![{\displaystyle {\begin{bmatrix}X(0)\\X(1)\\X(2)\\\vdots \\X(N-1)\end{bmatrix}}={\begin{bmatrix}1&1&1&...&1\\1&\omega _{N}^{1}&\omega _{N}^{2}&...&\omega _{N}^{(N-1)}\\1&\omega _{N}^{2}&\omega _{N}^{4}&...&\omega _{N}^{2(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\omega _{N}^{(N-1)}&\omega _{N}^{2(N-1)}&...&\omega _{N}^{(N-1)^{2}}\\\end{bmatrix}}\times {\begin{bmatrix}x(0)\\x(1)\\x(2)\\\vdots \\x(N-1)\end{bmatrix}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/096b579416ffaa3939fa40e14b8b29298e29575c)
- Equação de síntese
![{\displaystyle {\begin{bmatrix}x(0)\\x(1)\\x(2)\\\vdots \\x(N-1)\end{bmatrix}}={\frac {1}{N}}{\begin{bmatrix}1&1&1&...&1\\1&\omega _{N}^{-1}&\omega _{N}^{-2}&...&\omega _{N}^{-(N-1)}\\1&\omega _{N}^{-2}&\omega _{N}^{-4}&...&\omega _{N}^{-2(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\omega _{N}^{-(N-1)}&\omega _{N}^{-2(N-1)}&...&\omega _{N}^{-(N-1)^{2}}\\\end{bmatrix}}\times {\begin{bmatrix}X(0)\\X(1)\\X(2)\\\vdots \\X(N-1)\end{bmatrix}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/c57894d78cc1527961f36b3b6bf7c389c58120fa)
Transformada Rápida de Fourier (FFT)
O cálculo da TDF e TDFI para uma sequência de dados de comprimento
necessita de
multiplicações complexas, limitando o seu uso em aplicações práticas. Em 1965, Cooley e Tukey propuseram um algoritmo rápido (FFT) para calcular a TDF com um número de multiplicações complexas na ordem de
. Esse mudança faz com que uma sequência de comprimento 1024, calculado com a TDF demanda 1024x1024 multiplicações, enquanto que com a FFT apenas 1024x10. Isso representa neste caso uma redução de complexidade de 100 vezes.
Atualmente existem diversos algoritmos de FFT, que obtêm exatamente o mesmo valor que o uso da TDF, mas eles podem ser classificados de forma geral em decimação no tempo, ou decimação na frequência, dependendo de qual vetor será decimado e reordenado, se o sinal no tempo
ou as frequencia
.
Ver este e-book The DFT, FFT, and Practical Spectral Analysis em OpenStax CNX, e também a wikipedia que tem esse artigo muito bem escrito sobre o assunto.
- Para relembrar os conceitos vistos acima, recomendo assistir os vídeos sobre DFT e FFT do prof. Steve Brunton da University of Washington
The Discrete Fourier Transform (DFT)
|
Computing the DFT Matrix
|
The Fast Fourier Transform (FFT)
|
The Fast Fourier Transform Algorithm
|
What is a Fast Fourier Transform (FFT)?
|
|
|
|
|
|
Soma dos termos de uma Progressão Geométrica
A soma aritmética dos termos de uma P.G. a partir do primeiro termo, é definida por:
![{\displaystyle S_{n}==a_{1}+a_{1}q+a_{1}q^{2}+\ldots +a_{1}q^{n-1}=\sum _{i=1}^{n}a_{1}q^{i-1}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b3749a8a8cd2640813dd0a20148d3c56cd020e1d)
Caso
, a soma pode ser descrita por:
![{\displaystyle S_{n}={\frac {a_{1}(1-q^{n})}{1-q}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/32d0491382e2119527192147c5d8161d4dd2c2fc)