Fourier transform: Difference between revisions
| (5 intermediate revisions by the same user not shown) | |||
| Line 16: | Line 16: | ||
===Discrete Fourier Transform=== | ===Discrete Fourier Transform=== | ||
{{Main | Wikipedia: Discrete Fourier transform}} | |||
A naive DFT would compute the matrix of <math>e^{-i2 \pi \xi x}</math> and multiply it with the signal. This would take <math>\mathcal{O}(n^2)</math> time.<br> | A naive DFT would compute the matrix of <math>e^{-i2 \pi \xi x}</math> and multiply it with the signal. This would take <math>\mathcal{O}(n^2)</math> time.<br> | ||
However, most languages have an FFT library which can compute the DFT in <math>\mathcal{O}(n \log n)</math> time. | However, most languages have an FFT library which can compute the DFT in <math>\mathcal{O}(n \log n)</math> time. | ||
| Line 47: | Line 48: | ||
'''Parseval's Theorem'''<br> | '''Parseval's Theorem'''<br> | ||
<math>\int |f(x)|^2 dx = \int |F(s)|^2 ds</math> | <math>\int |f(x)|^2 dx = \int |F(s)|^2 ds</math> | ||
See [[Wikipedia: Parseval's theorem]]<br> | See [[Wikipedia: Parseval's theorem]]<br> | ||
| Line 54: | Line 56: | ||
'''Autocorrelation'''<br> | '''Autocorrelation'''<br> | ||
<math>\int f(x') f^*(x' - x) dx' \Leftrightarrow |F(x)|^2</math> | <math>\int f(x') f^*(x' - x) dx' \Leftrightarrow |F(x)|^2</math> | ||
This is a case of the convolution theorem. | This is a case of the convolution theorem. | ||
'''IFFT'''<br> | '''IFFT'''<br> | ||
<math>IFFT(f) = (1/n) | <math>IFFT(f) = (1/n) FFT^*(f^*)</math> | ||
* Where <math>^*</math> is the conjugate. | |||
'''2D FFT'''<br> | '''2D FFT'''<br> | ||
<math>FFT2(f) = FFT_{x}(FFT_{y}(f)) = FFT_{y}(FFT_{x}(f))</math> | <math>FFT2(f) = FFT_{x}(FFT_{y}(f)) = FFT_{y}(FFT_{x}(f))</math> | ||
==Phase correlation== | |||
{{main | Wikipedia: Phase correlation}} | |||
==Short-time Fourier transform== | ==Short-time Fourier transform== | ||