Fourier transform: Difference between revisions
| (4 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 59: | Line 60: | ||
'''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== | ||