Fourier transform: Difference between revisions
| (12 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 23: | Line 24: | ||
and IFFT is defined as: | and IFFT is defined as: | ||
<math display="block">a_m = \frac{1}{n} \sum_{k=0}^{n-1} \hat{f}(\xi) \exp \left\{ 2 \pi i \frac{mk}{n} \right\}</math> | <math display="block">a_m = \frac{1}{n} \sum_{k=0}^{n-1} \hat{f}(\xi) \exp \left\{ 2 \pi i \frac{mk}{n} \right\}</math> | ||
That the main difference between the FFT and IFFT is the negative symbol in the exponent. | |||
You can implement IFFT as <code>IFFT(x) = (1/len(x))*conj(FFT(conj(x)))</code><ref name="siembida2010ifft"></ref>. | |||
==Properties== | ==Properties== | ||
Note <math>\bar{x}</math> refers to the complex conjugate | Note <math>\bar{x}</math> refers to the complex conjugate | ||
Let <math>F(s) = FFT(f(s))</math>. | |||
'''Linearity'''<br> | |||
<math>FFT(\lambda f + g) = \lambda FFT(f) + FFT(g)</math> | |||
'''Shift'''<br> | |||
<math>FFT(f(x-a)) = e^{-i \omega_k a} F(\omega_k)</math> | |||
* Note <math>\omega_k = 2 \pi k/N </math> | |||
'''Similarity'''<br> | |||
* <math>IFFT(f) = (1/n) | <math>FFT(f(ax)) = |a|^{-1} F(s/a)</math> | ||
* <math>FFT2(f) = FFT_{x}(FFT_{y}(f)) = FFT_{y}(FFT_{x}(f))</math> | |||
'''Convolution Theorem'''<br> | |||
<math>f *g \Leftrightarrow F(s) \times G(s)</math><br> | |||
<math>f \times g \Leftrightarrow F(s) * G(s)</math> | |||
'''Parseval's Theorem'''<br> | |||
<math>\int |f(x)|^2 dx = \int |F(s)|^2 ds</math> | |||
See [[Wikipedia: Parseval's theorem]]<br> | |||
More generally, | |||
<math>\int f(x) g^*(x) dx = \int F(s) G^*(s) ds</math> | |||
'''Autocorrelation'''<br> | |||
<math>\int f(x') f^*(x' - x) dx' \Leftrightarrow |F(x)|^2</math> | |||
This is a case of the convolution theorem. | |||
'''IFFT'''<br> | |||
<math>IFFT(f) = (1/n) FFT^*(f^*)</math> | |||
* Where <math>^*</math> is the conjugate. | |||
'''2D FFT'''<br> | |||
<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== | ||
| Line 35: | Line 73: | ||
The STFT applies FFT using a sliding window over the signal.<br> | The STFT applies FFT using a sliding window over the signal.<br> | ||
This produces a matrix of FFT values over time which allow you to see how the signal is changing. | This produces a matrix of FFT values over time which allow you to see how the signal is changing. | ||
==References== | |||
{{reflist|refs= | |||
<ref name="siembida2010ifft">Siembida, A. (2010, March 11). How to compute the IFFT using only the forward FFT. Adam Siembida Personal Webpage. Retrieved January 24, 2023, from https://adamsiembida.com/how-to-compute-the-ifft-using-only-the-forward-fft/ </ref> | |||
}} | |||