Fourier Transform
Continuous-time Fourier Transform
Fourier Series
In Euclidean space, we usually represent a vector by a set of independent and orthogonal base vectors (basis). Orthogonality means the inner product between two basis is zero. Inner product can also be defined on some common interval between two functions, and thus the orthogonality.
Frequency Domain
It is intuitive to model after the inner product between vectors. Function (signal) on its domain can be viewed as an “infinite-dimension” vector. We represent this infinity in the definition of function inner product by integration. In particular, given two functions \(s\) and \(g\), an interval \(I\), the inner product is \[ \int\limits_{x \in I}s(x)g(x)dx \] \(s\) and \(g\) are orthogonal on interval \(I\) if their inner product \(\int_{x \in I}s(x)g(x)dx = 0\).
A set of basis of \(\R^N\) Euclidean space contains \(N\) independent orthogonal basis. For an “infinite-dimension” function space, there are an infinite number of basis, among which a group of sine and cosine functions satisfy. For integer \(k\) and positive integers \(m, n\), \[ \begin{aligned} \left\{ \begin{array} \\ \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \cos(mx) \cos(nx)dx = \pi, m = n, m, n \ge 1 \\ \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \cos(mx) \cos(nx)dx = 0, m \ne n, m, n \ge 1 \\ \end{array} \right. \\ \left\{ \begin{array} \\ \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \sin(mx) \sin(nx)dx = \pi, m = n, m, n \ge 1 \\ \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \sin(mx) \sin(nx)dx = 0, m \ne n, m, n \ge 1 \\ \end{array} \right. \\ \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \cos(mx) \sin(nx)dx = 0, m, n \ge 1 \end{aligned} \]
Proof
\(m = n\) \[ \begin{aligned} \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \cos(mx) \cos(nx)dx &= \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \cos^2(nx)dx \\ &= \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \frac{1 - \cos(2nx)}{2}dx \\ &= \pi \end{aligned} \]
\[ \begin{aligned} \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \sin(mx) \sin(nx)dx &= \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \sin^2(nx)dx \\ &= \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \frac{1 + \cos(2nx)}{2}dx \\ &= \pi \end{aligned} \]
\[ \begin{aligned} \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \cos(mx) \sin(nx)dx &= \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \sin(nx) \cos(nx)dx \\ &= \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \frac{\sin(2nx)}{2}dx \\ &= 0 \end{aligned} \]
\(m \ne n\) \[ \begin{aligned} \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \cos(mx) \cos(nx)dx &= \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \frac{\cos((m+n)x) + \cos((m-n)x)}{2}dx \\ &= \frac{\frac{\sin((m+n)x)}{m+n}\bigg|^{x=\pi + 2k\pi}_{x=-\pi + 2k\pi} + \frac{\sin((m-n)x)}{m-n}\bigg|^{x=\pi + 2k\pi}_{x=-\pi + 2k\pi}}{2} \\ &= 0 \end{aligned} \]
\[ \begin{aligned} \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \sin(mx) \sin(nx)dx &= \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \frac{\cos((m+n)x) - \cos((m-n)x)}{2}dx \\ &= \frac{\frac{\sin((m+n)x)}{m+n}\bigg|^{x=\pi + 2k\pi}_{x=-\pi + 2k\pi} - \frac{\sin((m-n)x)}{m-n}\bigg|^{x=\pi + 2k\pi}_{x=-\pi + 2k\pi}}{2} \\ &= 0 \end{aligned} \]
\[ \begin{aligned} \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \cos(mx) \sin(nx)dx &= \int_{-\pi + 2k\pi}^{\pi + 2k\pi} \frac{\sin((n+m)x) + \sin((n-m)x)}{2}dx \\ &= -\frac{\frac{\cos((m+n)x)}{m+n}\bigg|^{x=\pi + 2k\pi}_{x=-\pi + 2k\pi} + \frac{\cos((m-n)x)}{m-n}\bigg|^{x=\pi + 2k\pi}_{x=-\pi + 2k\pi}}{2} \\ &= 0 \end{aligned} \]
In other words, we can use the linear combination of \(1, \cos(x), \sin(x), \cos(2x), \sin(2x), \dots\) to fit any continuous function on interval \([-\pi, \pi]\). Or use \(1, \cos(2\pi fx), \sin(2\pi fx), \cos(2\pi f2x), \sin(2\pi f2x), \dots\) to fit any function on interval \([\frac{-1}{2f} + \frac{k}{f}, \frac{1}{2f} + \frac{k}{f}]\), which can be any interval by choosing the value of \(f\) (frequency) and the integer \(k\).
A continuous function \(s\) approximated with such series up to level \(N\) can be written as: \[ \begin{align} &\begin{split} s_N(x) &= a_0 + \sum_{i=1}^N \big( \underbrace{a_n}_{A_n\sin(\varphi_n)} \cos(2\pi fnx) + \underbrace{b_n}_{A_n\cos(\varphi_n)} \sin(2\pi fnx) \big) \\ &= a_0 + \sum_{n=1}^N \bigg( A_n\sin(2\pi fnx + \varphi_n) \bigg) \text{, where} \\ \end{split} \\ \notag &A_n = \sqrt{a_n^2 + b_n^2}, \sin(\varphi_n) = \frac{a_n}{\sqrt{a_n^2 + b_n^2}}, \cos(\varphi_n) = \frac{b_n}{\sqrt{a_n^2 + b_n^2}} \end{align} \] \(A_n\) can be interpreted as the amplitude, \(\varphi_n\) as the phase, \(nf\) as the frequency.
Complex Frequency Domain
By Euler’s Formula we have \[ e^{ix} = \cos x + i\sin x \] Thus \(s_N(x)\) can be re-written as \[ \begin{alignat}{2} s_N(x) &= a_0 &&+ \sum_{n=1}^N \bigg( \underbrace{a_n}_{A_n\cos \phi_n} \cos(2\pi fnx) + \underbrace{b_n}_{A_n\sin \phi_n} \sin(2\pi fnx) \bigg) \\ &= a_0 &&+ \sum_{n=1}^N \bigg( A_n\cos(2\pi fnx - \phi_n) \bigg) \\ &= a_0 &&+ \sum_{n=1}^N \frac{A_n}{2} \bigg( \cos(2\pi fnx - \phi_n) + i\sin(2\pi fnx - \phi_n) \bigg) \\ & &&+ \sum_{n=1}^N \frac{A_n}{2} \bigg( \cos(2\pi fnx - \phi_n) - i\sin(2\pi fnx - \phi_n) \bigg) \\ & &&\Downarrow_\text{by multiplication rule between complex numbers in polar form} \\ &= && \sum_{n=-N}^N c_ne^{i 2\pi fnx} \\ \end{alignat} \] where \[ \begin{eqnarray} c_n &= \begin{cases} \frac{A_n}{2}(\cos \phi_n - i\sin \phi_n) = \frac{1}{2}(a_n - ib_n), &n > 0 \\ \overline{c_{|n|}} =\frac{A_n}{2}(\cos \phi_n + i\sin \phi_n), &n < 0 \\ a_0, &n = 0 \end{cases} \end{eqnarray} \]
When \(N \to +\infty\), \(s\) can be reconstructed as the Fourier Series: \[ s(x) = \lim_{N \to +\infty} s_N(x) = a_0 + \sum_{n=1}^{+\infty} \bigg( a_n \cos(2\pi fnx) + b_n \sin(2\pi fnx) \bigg) \\ \] The problem comes how \(a_i\) can be computed. By the orthogonality mentioned before, we have \[ \begin{gather} \int_{-1/2f+f/k}^{1/2f+f/k} s(x) \d x = \int_{-1/2f+f/k}^{1/2f+f/k} [a_0 + \sum_{n=1}^{+\infty} \bigg( a_n \cos(2\pi fnx) + b_n \sin(2\pi fnx) \bigg)] \d x = \frac{1}{f} a_0 \\ \int_{-1/2f+f/k}^{1/2f+f/k} s(x) \cos(2\pi fkx) \d x = \int_{-1/2f+f/k}^{1/2f+f/k} [a_0 + \sum_{n=1}^{+\infty} \bigg( a_n \cos(2\pi fnx) + b_n \sin(2\pi fnx) \bigg)] \cos (2\pi fkx) \d x = \frac{1}{2f} a_k \\ \int_{-1/2f+f/k}^{1/2f+f/k} s(x) \sin(2\pi fkx) \d x =\int_{-1/2f+f/k}^{1/2f+f/k} [a_0 + \sum_{n=1}^{+\infty} \bigg( a_n \cos(2\pi fnx) + b_n \sin(2\pi fnx) \bigg)] \sin (2\pi fkx) \d x = \frac{1}{2f} b_k \\ \end{gather} \] The computation of \(a_k\) and \(b_k\) can be combined together by the Euler’s Formula: \[ \begin{aligned} \int_{-1/2f+f/k}^{1/2f+f/k} s(x) e^{-i 2\pi fkx} \d x & = \int_{-1/2f+f/k}^{1/2f+f/k} (a_k \cos(2\pi fkx) + b_k \sin(2\pi fkx)) (\cos(2\pi fkx) - i \sin(2\pi fkx)) \d x \\ &= \frac{1}{2f} (a_k - i b_k) = \frac{1}{f} c_k \end{aligned} \]
Fourier Transform
We have been through representing a continuous function on a certain interval using the Fourier Series. This can be quite useful for periodic functions. As long as we figure out the representation on its repeating interval, we obtain the representation on its whole domain. The problem is more of computing the factor for each sine and cosine function.
The process of finding out factors for an arbitrary continuous function \(s\) is called Fourier Transform. It transforms the function \(s\) from the time domain to the frequency domain. When \(s\) is periodic, it can be easily represented by the Fourier Series as discussed in previous section. When \(s\) is not periodic, we can treat the periodic interval as \([-\infty, +\infty]\). Its Fourier Transform and the inverse will be \[ \begin{gather*} \hat s \stackrel{\mathcal F}\Longleftrightarrow s \\ \hat s(f) = \int_{-\infty}^{+\infty} s(t) e^{-i 2\pi f x} \d t \\ s(x) = \int_{-\infty}^{+\infty} \hat s(f) e^{i 2\pi f x} \d f \end{gather*} \]
Discrete-time Fourier Transform
The domain (time axis) of the function (signal) is continuous in our discussion by now. When the time axis is discrete (and usually takes on a series of integers), we are facing the Discrete-time Fourier Transform. We will be using the term signal instead of the function from now on.
For a discrete signal \(s\), its Fourier Transform is \[ \hat s(\omega) = \sum_{k=-\infty}^{+\infty} s[k] e^{-i\omega k} \] where \(\omega\) is the angular speed. \(\omega\) is in the unit of radian/sample. \(\hat s(\omega)\) is the weight of the component which walks \(\omega\) between two signal samples. \[ \hat s(f) = \sum_{k=-\infty}^{+\infty} s[k] e^{-i 2\pi f k} \] where \(f\) is the “frequency”. \(f\) is in the unit of cycles/sample. \(\hat s(f)\) is the weight of the component which walks \(f\) cycles between two signal samples.
Todo
- Laplace Transform
- \(Z\)-transform
- Fast Fourier Transform