5,336
edits
Line 31: | Line 31: | ||
Let <math>F(s) = FFT(f(s))</math>. | Let <math>F(s) = FFT(f(s))</math>. | ||
'''Linearity''' | '''Linearity'''<br> | ||
<math>FFT(\lambda f + g) = \lambda FFT(f) + FFT(g)</math> | <math>FFT(\lambda f + g) = \lambda FFT(f) + FFT(g)</math> | ||
'''Shift''' | '''Shift'''<br> | ||
<math>FFT(f(x-a)) = e^{-i \omega_k a} F(\omega_k)</math> | <math>FFT(f(x-a)) = e^{-i \omega_k a} F(\omega_k)</math> | ||
* Note <math>\omega_k = 2 \pi k/N </math> | * Note <math>\omega_k = 2 \pi k/N </math> | ||
'''Similarity''' | '''Similarity'''<br> | ||
<math>FFT(f(ax)) = |a|^{-1} F(s/a)</math> | <math>FFT(f(ax)) = |a|^{-1} F(s/a)</math> | ||
'''Convolution Theorem''' | '''Convolution Theorem'''<br> | ||
<math>f *g \Leftrightarrow F(s) \times G(s)</math><br> | <math>f *g \Leftrightarrow F(s) \times G(s)</math><br> | ||
<math>f \times g \Leftrightarrow F(s) * G(s)</math> | <math>f \times g \Leftrightarrow F(s) * G(s)</math> | ||
'''Parseval's Theorem''' | '''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 52: | Line 52: | ||
<math>\int f(x) g^*(x) dx = \int F(s) G^*(s) ds</math> | <math>\int f(x) g^*(x) dx = \int F(s) G^*(s) ds</math> | ||
'''Autocorrelation''' | '''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''' | '''IFFT'''<br> | ||
<math>IFFT(f) = (1/n) \bar{FFT}(\bar{f})</math> | <math>IFFT(f) = (1/n) \bar{FFT}(\bar{f})</math> | ||
'''2D FFT''' | '''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> | ||