Fourier Transform and its Applications

This is my short note on EE 261 Fourier transform and its applications for a brief review.

Fourier series

Basic sum

We can build complex periodic functions by take sums of sinusoids. Let us consider functions with period 1, then the fourier type sum is:

\[ \sum_{n=1}^N A_n \sin(2\pi nt + \phi_n), \]

where \(A_n\) is amplitude and \(\phi_n\) is phase. This form explicitly display the amplitude and phase of each harmonics. But it is more common to use:

\[ \sum_{n=1}^N a_n \cos(2\pi nt) + b_n\sin(2\pi nt) \]

By including a constant term (n=0):

\[ \frac{a_0}{2} + \sum_{n=1}^N a_n \cos(2\pi nt) + b_n\sin(2\pi nt) \]

The constant term \(\frac{a_0}{2}\) is called direct current (DC) component while the other terms, being periodic, 'alternate', as in AC. By using Euler's formula:

\[ \cos t = \frac{e^{it} + e^{-it}}{2}, \quad \sin t = \frac{e^{it} - e^{-it}}{2i} \]

we can rewrite the original sum:

\[ \sum_{n=-N}^N c_n e^{2\pi i n t} \]

Here the coefficients \(c_n\) are complext numbers and has conjugate symmetry property:

\[ c_{-n} = \overline{c_n} \]

i.e., they are complex conjugate, and, of course, have the same magnitude:

\[ |c_n| = |c_{-n}| \]

We can observe that \(c_0 = \overline{c_0}\) means that it is a real number. To derive conjugate symmetry property, let us consider if the signal is real, then \(f(t) = \overline{f(t)}\), and we then have:

\[ \sum_{n=-N}^N c_n e^{2\pi i n t} = \overline{\sum_{n=-N}^N c_n e^{2\pi i n t}} = \sum_{n=-N}^N \overline{c_n} \overline{e^{2\pi i n t}} =\sum_{n=-N}^N \overline{c_n} e^{-2\pi i n t} \]

It is clear \(c_{-n} = \overline{c_n}\). Now, if we group \(c_n e^{2\pi i n t}\) with \(c_{-n} e^{-2\pi i n t}\), we have

\[ c_n e^{2\pi i n t} + c_{-n} e^{-2\pi i n t} = c_n e^{2\pi i n t} + \overline{c_n e^{2\pi i n t}} = 2 \mathrm{Re} (c_n e^{2\pi i n t}) \]

Therefore, we know the sum is real (of course):

\[ \sum_{n=-N}^N c_n e^{2\pi i n t} = \sum_{n=0}^N 2\mathrm{Re}(c_n e^{2\pi i n t}) = 2\mathrm{Re}\{\sum_{n=0}^Nc_n e^{2\pi i n t}\} \]

Recover coefficients

Let us assume the signal \(f(t)\) has a period of 1 (Easily to scale time for this bit), to express \(f(t)\) as a sum:

\[ f(t) = \sum_{n=-N}^N c_n e^{2\pi i n t} \]

We have \(c_n\) as unknowns. To solve it, let us firstly multiply both side by \(e^{-2\pi i k t}\):

\[ e^{-2\pi i k t} f(t) = e^{-2\pi i k t} \sum_{n=-N}^N c_n e^{2\pi i n t} = \dots + e^{-2\pi i k t} c_k e^{2\pi i k t} + \dots = \dots + c_k + \dots \]

Thus,

\[ c_k = e^{-2\pi i k t} f(t) - \sum_{n=-N, n\neq k}^N c_n e^{-2\pi i k t} e^{2\pi i n t} = e^{-2\pi i k t} f(t) - \sum_{n=-N, n\neq k}^N c_n e^{2\pi i (n-k) t} \]

To solve this equation, we can take integration from 0-1 (period 1). We know that:

\[ \begin{aligned} \int_0^1 e^{2\pi i (n-k) t} dt &= \frac{1}{2\pi i (n-k)} e^{2\pi i (n-k) t} \Big|_0^1\\ &= \frac{1}{2\pi i (n-k)} (e^{2\pi i (n-k)} - e^0)\\ &= \frac{1}{2\pi i (n-k)} (\cos(2\pi(n-k)) + i\sin(2\pi(n-k)) - e^0)\\ &= \frac{1}{2\pi i (n-k)}(1-1) = 0 \end{aligned} \]

Since \(\int_0^1 c_k dt = c_k\), we have

\[ c_k = \int_0^1 e^{-2\pi ikt} f(t) dt \]

To summarize:

\[ f(t) = \sum_{n=-N}^N c_n e^{2\pi i n t},\hspace{2pt} \text{where} \hspace{2pt} c_n = \int_0^1 e^{-2\pi int} f(t) dt \]

The \(c_n\) is called fourier coefficients of \(f(t)\) (sometimes people also use \(\hat{f}(n)\) to represent it), and the sum \(\sum_{n=-N}^N c_n e^{2\pi i n t}\) is called a (finite) Fourier series. Here we know \(c_0\) is simply average value of the function:

\[ c_0 = \int_0^1 f(t) dt \]

Period, Frequency and spectrum

Let us consider a fourier series representation of \(f(t)\)

\[ f(t) = \sum_{n=-N}^N \hat{f}(n) e^{2\pi i n t} \]

Spectrum: The set of frequencies present in a given periodic signal is the spectrum of the signal

Bandwidth: If the coefficients are all zero for some point on: \(\hat{f}(n) = 0\) for \(|n|>N\), then we say the spectrum is limited to the points between \(-N\) and \(N\), i.e., bandwidth is \(N\).

Power (energy) spectrum: The sequence of squared magnitudes \(|\hat{f}(n)|^2\).

ALL coefficients are real when the signal is real and even.

What if period isn't 1? We can scale it with period \(T\):

\[ f(t) = \sum_{n=-N}^N c_n e^{2\pi i n t/T} \]

where the coefficients are given by:

\[ c_n = \frac{1}{T} \int_0^T e^{-2\pi int/T} f(t) dt \]

As in the case of period 1, we can integrate over any interval of length \(T\), e.g.

\[ c_n = \frac{1}{T} \int_{-T/2}^{T/2} e^{-2\pi int/T} f(t) dt \]

Here we can see in the time domain the signal repeats after \(T\) seconds while the points in spectrum is \(\boldsymbol{1/T}\) apart (\(e^{2\pi i n t/T}\))

The math, the majesty the end

I will leave the conclusion here. Let \(f(t)\) be in \(L^2([0, 1])\) and let:

\[ \hat{f}(n) = \int_0^1 e^{-2\pi int} f(t) dt, \quad n=0, \pm 1, \pm 2, \dots \]

be its Fourier coefficients. Then:

\[ \lim_{N\rightarrow \infty} \|\sum_{-N}^N\hat{f}(n)e^{2\pi int} - f(t) \| = 0 \]

The energy of \(f(t)\) can be calculated from its Fourier coefficients:

\[ \int_0^1 |f(t)|^2 dt = \sum_{-\infty}^{\infty} |\hat{f}(n)|^2 \]

Fourier transform

Basic definition

Now we pass from periodic to non-periodic functions in that \(T\rightarrow\infty\). We could define the Fourier transform of a function \(f(t)\):

\[ \hat{f}(s) = \int_{-\infty}^{\infty} e^{-2\pi ist}f(t)dt \]

Spectrum: The spectrum of a periodic function is a discrete set of frequencies while the Fourier transform of a non-periodic signal produces a continuous spectrum.

We can define inverse Fourier transform:

\[ f(t) = \int_{-\infty}^{\infty} e^{2\pi ist} \hat{f}(s) ds \]

The domain of the Fourier transform is the set of real numbers \(s\). We can say \(\hat{f}(s)\) is defined on the frequency domain. Note that NOT ALL frequencies need occur, i.e., we might have \(\hat{f}(s) = 0\) for \(|s|\) large, then we call the signal bandlimited.

Notations: It is common to use \(\mathcal{F}f(s)\) for \(\hat{f}(s)\) and \(\mathcal{F}^{-1}\) as inverse Fourier transform.

General properties and formulas

According to the definition of Fourier transform, we can observe the duality of the Fourier transform pair:

\[ \begin{aligned} \mathcal{F}f(-s) &= \mathcal{F}^{-1}f(s)\\ \mathcal{F}^{-1}f(-t) &= \mathcal{F}f(t) \end{aligned} \]

Discrete Fourier transform

From Continouous to Discrete

Consider a signal \(f(t)\), we suppose it is zero outside \(0\le t \le L\), and its Fourier transform \(\mathcal{F}f(s)\) is zero or effectively zero outsider of \(0\le s \le 2B\) (Note here we assume \(\mathcal{F}f\) lies in intervale from \(0\) to \(2B\) instead of \(-B\) to \(B\)). Thus, here the assumption is \(f(t)\) is both time-limited and band-limited.

According to the sampling theorem, we can reconstruct f(t) at the rate of \(2B\) samples per second i.e., samples are \(1/2B\) apart, which means we want a total of

\[ N = \frac{L}{1/2B} = 2BL \]

evenly spaced samples, at the points

\[ t_0 = 0, t_1 = \frac{1}{2B}, \dots, t_{N-1} = \frac{N-1}{2B} \]

Now we can represent the discrete version of \(f(t)\) continuoosly with the aid of a finite impulse train at the sample points:

$$ \sum_{n=0}^{N-1}\delta(t-t_n) $$ that is,

\[ f_{\mathrm{discrete}}(t) = f(t)\sum_0^{N-1}\delta(t-t_n) = \sum_0^{N-1}f(t_n)\delta(t-t_n) \]

The Fourier transform of \(f_{\mathrm{discrete}}\) is thus:

\[ \begin{aligned} \mathcal{F}f_{\mathrm{discrete}}(s) &= \sum_0^{N-1}f(t_n)\mathcal{F}\delta(t-t_n) \quad f(t_n) \hspace{2pt}\text{is constant here}\\ &=\sum_{n=0}^{N-1} f(t_n)e^{-2\pi ist_n} \end{aligned} \]

This the continous Fourier transform of the smapled form of \(f(t)\). Now if we look from the Frequency domain, the function \(f(t)\) is limited to \(0\le t\le L\), and this deterimines a sampling rate for reconstrucing \(\mathcal{F}f(s)\) from its samples in the frequency domain, i.e. the sampling rate would be \(1/L\) (Look into "what if period is not 1" section if you don't understand this bit). Thus, we sample the \(\mathcal{F}f(s)\) over the interval from \(0\) to \(2B\) in the frequency domain at points spaced \(1/L\) apart. The number of sample points is

\[ \frac{2B}{1/L} = 2BL = N \]

the same number of sample points \(s_m\) as for \(f(t)\), they are

\[ s_0 = 0, s_1 = \frac{1}{L}, \dots, s_{N-1} = \frac{N-1}{L} \]

Now we come up with the discrete verison of \(\mathcal{F}f(s)\):

\[ F(s_m) = \sum_{n=0}^{N-1} f(t_n)e^{-2\pi is_m t_n} \]

And by using the definition of the points:

\[ t_n = \frac{n}{2B}, n=0, 1, \dots, N-1\qquad s_m = \frac{m}{L}, m=0, 1, \dots, N-1 \]

We have

\[ \begin{aligned} F(s_m) &= \sum_{n=0}^{N-1} f(t_n)e^{-2\pi is_m t_n} \\ &= \sum_{n=0}^{N-1} f(t_n)e^{-2\pi i\frac{m}{L} \frac{n}{2B}} \quad\text{NOTE:}\hspace{2pt} N=2BL\\ &= \sum_{n=0}^{N-1} f(t_n)e^{-2\pi inm/N} \end{aligned} \]

Discrete Fourier Transform (DFT)

Now let us define DFT formally. Given a discrete function \(\mathbf{f}\) and write as N-tuple as:

\[ \mathbf{f} = (\mathbf{f}[0], \mathbf{f}[1], \dots, \mathbf{f}[N-1]) \]

The DFT of \(\mathbf{f}\) is the N-tuple \(\mathbf{F} = (\mathbf{F}[0], \mathbf{F}[1], \dots, \mathbf{F}[N-1])\) defined by:

\[ \mathbf{F}[m] = \sum_{n=0}^{N-1}\mathbf{f}[n]e^{-2\pi imn/N}, \quad m=0, 1, \dots, N-1 \]

We can rewrite it in a vector form:

\[ \underline{\mathcal{F}}\mathbf{f} = \sum_{k=0}^{N-1} \mathbf{f}[k]\boldsymbol{\omega}^{-k} \]

where

\[ \boldsymbol{\omega}^k = (1, \omega^k, \omega^{2k}, \dots, \omega^{(N-1)k}), \quad \omega^k = e^{2\pi ik/N} \]

The components of \(\underline{\mathcal{F}}\mathbf{f}\) would be the values of \(\underline{\mathcal{F}}\mathbf{f}\) at the points \(m=0, 1, \dots, N-1\):

\[ \underline{\mathcal{F}}\mathbf{f}[m] = \sum_{k=0}^{N-1} \mathbf{f}[k]\boldsymbol{\omega}^{-k}[m] = \sum_{k=0}^{N-1} \mathbf{f}[k]\boldsymbol{\omega}^{-km} = \sum_{k=0}^{N-1} \mathbf{f}[k]e^{-2\pi ikm/N} \]

Positive and negative frequencies

Let us recall that \(\mathcal{F}f(-s) = \overline{\mathcal{F}f(s)}\). In DFT, we have a same property (need re-index a bit). Suppose that \(N\) is even, we can find that at the midpoint:

\[ \begin{aligned} \underline{\mathcal{F}}\mathbf{f}[N/2] = \sum_{k=0}^{N-1} \mathbf{f}[k]\boldsymbol{\omega}^{-k}[N/2] &= \sum_{k=0}^{N-1} \mathbf{f}[k]\omega^{-kN/2}\\ &= \sum_{k=0}^{N-1} \mathbf{f}[k] e^{-\pi ik} = \sum_{k=0}^{N-1} (-1)^{-k}\mathbf{f}[k] \end{aligned} \]

That is to say \(\underline{\mathcal{F}}\mathbf{f}[N/2]\) is real, and the spectrum "splits" at \(N/2\). Let us consider \(\underline{\mathcal{F}}\mathbf{f}[N/2+1]\) and \(\underline{\mathcal{F}}\mathbf{f}[N/2-1]\):

\[ \underline{\mathcal{F}}\mathbf{f}[N/2+1] = \sum_{k=0}^{N-1} \mathbf{f}[k]\boldsymbol{\omega}^{-k}[N/2+1] = \sum_{k=0}^{N-1} \mathbf{f}[k]\omega^{-k}\omega^{-kN/2} = \sum_{k=0}^{N-1} \mathbf{f}[k]\omega^{-k}(-1)^{-k}\\ \underline{\mathcal{F}}\mathbf{f}[N/2-1] = \sum_{k=0}^{N-1} \mathbf{f}[k]\boldsymbol{\omega}^{-k}[N/2-1] = \sum_{k=0}^{N-1} \mathbf{f}[k]\omega^{k}\omega^{-kN/2} = \sum_{k=0}^{N-1} \mathbf{f}[k]\omega^{k}(-1)^{-k} \]

Thus, we can see

\[ \underline{\mathcal{F}}\mathbf{f}[N/2+1] = \overline{\underline{\mathcal{F}}\mathbf{f}[N/2+1] } \]

This extends to

\[ \underline{\mathcal{F}}\mathbf{f}[m] = \overline{\underline{\mathcal{F}}\mathbf{f}[N-m] } \]

Inverting the DFT

The iDFT can be written as:

\[ \underline{\mathcal{F}}^{-1}\mathbf{f} = \frac{1}{N} \sum_{k=0}^{N-1}\mathbf{F}[k]\omega^{k} \]

Reference

EE261: The Fourier Transform and its Applications