Fourier transform: Difference between revisions
| (3 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 64: | Line 65: | ||
'''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== | ||