Week 10

Fourier analysis is a tool we use to break a signal into linear combinations of its constituent complex exponential frequencies. Here is a list of acronyms to get familiar with:
\begin{center}
$
\begin{tabular}{|c|c|}
\hline
DFS & Discrete Fourier Series \\
\hline
DFT (FFT) & Discrete Fourier Transform (a.k.a. Fast Fourier Transform) \\
\hline
FS & Fourier Series \\
\hline
DTFT & Discrete Time Fourier Transform \\
\hline
CTFT & Continuous Time Fourier Transform \\
\hline
\end{tabular}
$
\end{center}

Here is a list of acronyms in virtue the type of signal being analyzed:
\begin{center}
$
\begin{tabular}{|c|c|c|}
\hline
 & DT & CT \\
\hline
\hline
periodic & DFS, DFT (a.k.a FFT) & FS \\
\hline
aperiodic & DTFT & CTFT \\
\hline
\end{tabular}
$
\end{center}



Basics and Overview

We will also introduce a new representation of signals in the form of vectors. Consider the vector given by $\vec{x} = \left[ \begin{array}{r} 4 \\ 2 \\ \end{array} \right]$. This vector corresponds to a periodic signal $4\delta(n) + 2\delta(n-1)$. Notice that we can link a Finite Duration signal to a periodic signal by letting the entire duration be one period, and decompose a periodic signal conversely. 


Fourier analysis allows us to decompose signals into sums of orthogonal vectors. This signal $\vec{x}$ can also be written as the sum of the two vectors $\Psi_0 = \left[ \begin{array}{r} 1 \\ 0 \\ \end{array} \right]$, and $\Psi_1 = \left[ \begin{array}{r} 0 \\ 1 \\ \end{array} \right] $. Then we can see that $\vec{x} = 4\Psi_0 + 2\Psi_1$.


What if $\Psi_0 = \left[ \begin{array}{r} 1 \\ 1 \\ \end{array} \right]$ and $\Psi_1 = \left[ \begin{array}{r} 1 \\ -1 \\ \end{array} \right]$? \\

\begin{align*}
x(n) &= X_0\Psi(n) + X_1\Psi_1(n) \\
\left[ \begin{array}{r} x(0) \\ x(1) \\ \end{array} \right] &= X_0\left[ \begin{array}{r} \Psi_0(0) \\ \Psi_0(1) \\ \end{array} \right] + X_1 \left[ \begin{array}{r} \Psi_1(0) \\ \Psi_1(1) \\ \end{array} \right] \\ 
\left[ \begin{array}{r} 4 \\ 2 \\ \end{array} \right] &= 3\left[ \begin{array}{r} 1 \\ 1 \\ \end{array} \right] + 1 \left[ \begin{array}{r} 1 \\ -1 \\ \end{array} \right] \\ 
\end{align*}

In general, we could have used any orthogonal vectors, but the vectors $\{  \left[ \begin{array}{c} 1 \\ 1 \\ \end{array} \right],\left[ \begin{array}{c} 1 \\ -1 \\ \end{array} \right] \}$ are special.

\begin{align*}
\Psi_0 &= \left[ \begin{array}{c} \Psi_0(0) \\ \Psi_0(1) \\ \end{array} \right] =  \left[ \begin{array}{c} 1 \\ 1 \\ \end{array} \right] \\
\Psi_1 &= \left[ \begin{array}{c} \Psi_1(0) \\ \Psi_1(1) \\ \end{array} \right] =  \left[ \begin{array}{c} 1 \\ -1 \\ \end{array} \right] \\
\end{align*}

Where $\Psi_k(n) = e^{i k \omega_0 n}$. So when we use the basis $\{  \left[ \begin{array}{c} 1 \\ 1 \\ \end{array} \right],\left[ \begin{array}{c} 1 \\ -1 \\ \end{array} \right] \}$, we can decompose any DT signal of period 2 into linear combinations of $\Psi_0(n) = 1$ and $\Psi_1(n) = \lr{-1}^n$ in the Discrete Fourier Series expansion $X_0e^{i 0 \omega_0 n} + X_1e^{i\omega_0 n}$.


Let $\Psi = \{ \Psi_0, \Psi_1, \cdots , \Psi_{p-1} \}$ be an orthogonal basis. Then we can use the discrete fourier series exansion to decompose a signal $\vec{x}$ by projecting the signal onto the basis vectors, or writing the signal as a linear combination of the basis vectors:

$$\vec{x} = X_0\Psi_0 + X_1\Psi_1 + \cdots + X_{p-1}\Psi_{p-1}$$
In general the discrete fourier series expansion is
$$ \sum \limits_{k=0}^{p-1}X_ke^{ik\omega_0n} =  \sum \limits_{k=0}^{p-1}X_k\Psi_k  $$


We can determine the coefficients by the fact that the basis is orthogonal. We can take the dot product over the norm squared to find the cofficients. Given that $\vec{x} =  \left[ \begin{array}{c} x_0 \\ x_1 \\ \vdots \\ x_{p-1} \\ \end{array} \right]$, we can write this as a projection onto the orthogonal basis:

$$\vec{x} = \frac{\vec{x} \cdot \Psi_0}{\norm{\Psi_0}^2}\Psi_0 +  \frac{\vec{x} \cdot \Psi_1}{\norm{\Psi_1}^2}\Psi_1 + \cdots +  \frac{\vec{x} \cdot \Psi_{p-1}}{\norm{\Psi_{p-1}}^2}\Psi_{p-1} $$

The dot product is denoted as $a \cdot b$, which can also be written as 

$$a^Tb = a_0b_0 + a_1b_1 + \cdots + a_{p-1}b_{p-1} = \sum_{\ell=0}^{p-1}a_\ell b_\ell = a \cdot b$$

Here we can prove that the coefficients of the projection formula are equal to the dot product of the original signal and the respective basis vector or the norm of that vector squared:

\begin{proof}
We can write the signal as a linear combination of some orthogonal basis $\Psi = \{ \Psi_0, \Psi_1, \cdots , \Psi_{p-1} \}$.
\begin{align*}
\vec{x} &= X_0\Psi_0 + X_1\Psi_1 + \cdots + X_k\Psi_k  + \cdots + X_{p-1}\Psi_{p-1} \\
\vec{x}\cdot\Psi_k &= X_0\Psi_0\cdot\Psi_k + X_1\Psi_1\cdot\Psi_k + \cdots + X_k\Psi_k\cdot\Psi_k  + \cdots + X_{p-1}\Psi_{p-1}\cdot\Psi_k \\
\vec{x}\cdot\Psi_k &=  X_k\Psi_k\cdot\Psi_k \quad \mbox{since the dot product of any orthogonal vectors is zero} \\
\frac{\vec{x}\cdot\Psi_k}{\Psi_k\cdot\Psi_k} &= X_k \\
\frac{\vec{x}\cdot\Psi_k}{\norm{\Psi_k}^2} &= X_k \\
\end{align*}
\end{proof}

When writing a signal as a linear combination of an orthogonal basis, we are writing it as a sum of complex exponentials where $\Psi_k(n) = e^{ik\omega_0 n}$ some frequency component of the signal, $\omega_0 = 2\pi/p$ is the fundamental frequency and $p$ is the period of the signal.

If we have a period of 2, note that $\Psi_k(n+2) = e^{i\omega_0\lr{n+2}} = e^{i\omega_0 n}e^{i2\omega_0} = e^{i\omega_0 n}e^{i2\pi} = e^{i\omega_0 n} = \Psi_k(n)$. In general, for a period $p$, $\Psi_k(n+p) = \Psi_k(n)$.


How do we project complex-valued vectors onto each other? We cannot use the dot product for projections involving the dot product. For example, $\left[ \begin{array}{r} 1 \\ i \\ \end{array} \right] \cdot \left[ \begin{array}{r} 1 \\ i \\ \end{array} \right] = 0 \neq 2 = \norm{\left[ \begin{array}{r} 1 \\ i \\ \end{array} \right]}^2$. Say hello to the \emph{inner product}. Now we can define $\langle f,g\rangle = f^Tg^*$. This way we take the conjugate of the second term in the inner product. Now we can accomplish projections using the formula:

$$ X_k = \frac{\langle \vec{x},\Psi_k \rangle}{\langle\Psi_k,\Psi_k\rangle}  $$

Signals as Vectors

Fourier analysis keeps our attention focused on frequency content, the $\omega_0$ in $e^{i\omega_0 n}$. Note that $\omega_0 = \frac{w\pi}{p}$, where $p$ is the \emph{period}, and $\omega_0$ is the \emph{fundamental frequency}. Every signal can be decomposed into linear combinations of harmonically related complex exponentials. Harmonically related simply means each has a frequency that is an integer multiple of the fundamental frequency. Assume for now that this decomposition can be done. Then we can sum over any continguous interval of length $p$ and a signal can be written as

$$ x(n) = \sum \limits_{k=0}^{p-1}X_ke^{i k \omega_0 n} $$

Lets compare this with the decomposition of a signal as shifted impulses:

$$ x(n) = \sum \limits_{m\in\Z} x(m) \delta(n-m)  $$

When we pass this signal through a system $h$, we get the convolution sum. Lets derive this through the properties of a linear time invariant system $h$:
\begin{align*}
\delta(n) \to &\fbox{h} \to h(n) \\
\delta(n-m) \to &\fbox{h} \to h(n-m) \\
x(m)\delta(n-m) \to &\fbox{h} \to x(m)h(n-m) \\
\sum_m (m)\delta(n-m) \to &\fbox{h} \to \sum_m x(m)h(n-m) \\
\end{align*}

We know what happens when we pass a complex exponential into an LTI system:
\begin{align*}
e^{i\omega_0n} \to & \fbox{H} \to H(\omega_0)e^{i\omega_0n} \\
e^{ik\omega_0 n}\to & \fbox{H} \to H(k\omega_0)e^{ik\omega_0 n} \\
X_ke^{ik\omega_0 n}\to & \fbox{H} \to X_kH(k\omega_0)e^{ik\omega_0 n} \\
\sum_k e^{ik\omega_0 n}\to & \fbox{H} \to \sum_k X_kH(k\omega_0)e^{ik\omega_0 n} \\
\end{align*}
So we can generalize this for a decomposed signal $x(n) = \sum_{k=0}^{p-1}X_ke^{i k \omega_0 n}$:
$$ x(n) = \sum \limits_{k=0}^{p-1}X_ke^{i k \omega_0 n} \to \fbox{H} \to \sum \limits_{k=0}^{p-1}X_kH(k \omega_0)e^{i k \omega_0 n}  $$

\begin{claim}
Given a discrete fourier series expansion of a signal $x(n) = \sum_{k=0}^{p-1}X_ke^{i k \omega_0 n}$, the signal convolved with a signal $h$ can be given by:
$$(x*h)(n) =  \sum \limits_{k=0}^{p-1}X_kH(k \omega_0)e^{i k \omega_0 n}  $$
\end{claim}

\begin{proof}
\begin{align*}
(x*h)(n) &= \sum \limits_{k=-\infty}^{\infty} h(k) x(n-k) \\
(x*h)(n) &= \sum \limits_{k=-\infty}^{\infty} h(k) \sum_{\ell=0}^{p-1}X_\ell e^{i \ell \omega_0 (n-k)} \\
(x*h)(n) &= \sum \limits_{k=-\infty}^{\infty} h(k) \sum_{\ell=0}^{p-1}X_\ell e^{i \ell \omega_0 n}e^{-i \ell \omega_0k} \\
(x*h)(n) &=  \sum_{\ell=0}^{p-1} \sum \limits_{k=-\infty}^{\infty} h(k) X_\ell e^{i \ell \omega_0 n}e^{-i \ell \omega_0k} \\
(x*h)(n) &=  \sum_{\ell=0}^{p-1} X_\ell \lr{\sum \limits_{k=-\infty}^{\infty} h(k) e^{-i \ell \omega_0k}} e^{i \ell \omega_0 n}\\
(x*h)(n) &=  \sum_{\ell=0}^{p-1} X_\ell H(\ell\omega_0) e^{i \ell \omega_0 n}\\
\end{align*}
\end{proof}


Hence, we have the description of what happens to a signal when passed through a system. This mathematically describes what an audio equalizer does when we pass in a signal described by its constituent frequencies.


Harmonic Relations and Frequency Content

What frequencies can be present in a signal $\vec{x}$? The harmonics are given by a signal with period $p$ are $\{0,\omega_0,2\omega_0,\dots,(p-1)\omega_0\}$. Notice that $p\omega_0$ is missing. This is because $e^{ip\omega_0n}=e^{i2\pi n} = e^{i0n}$. Keep in mind that $\omega_0 = 2\pi/p$. In fact, the complex exponential basis of vectors is periodic with respect to $n$ and their indices $k$. 
\begin{align*}
\Psi_k(n+p) &= e^{ik\omega_0(n+p)}=e^{ik\omega_0n}e^{ik\omega_0p}=e^{ik\omega_0n} = \Psi_k(n) \\
\Psi_{k+p}(n) &= e^{i(k+p)\omega_0n} = e^{ik\omega_0n}e^{ip\omega_0n} = \Psi_k(n) 
\end{align*}

So we know that $\Psi_{-1}(n) = e^{-i\omega_0n} = \Psi_{p-1}(n) = e^{i(p-1)\omega_0n }$. So we can see that in general, we can write out a discrete fourier series expansion over any continuous set of $p$ integers. The notation used is
$$ x(n) = \sum \limits_{k=\langle p\rangle} X_ke^{ik\omega_0n}$$


Periodicity

\begin{claim}
For a signal written in terms of vectors that represent complex exponentials,
$$x(n) = \sum_{k=\langle p\rangle}X_k\Psi_k$$
the spanning set that makes up the set of vectors is an orthogonal set, in other words, 
$$ \Psi_k \perp \Psi_\ell \quad k \neq \ell$$
\end{claim}

\begin{proof}

For $\Psi_k(n) = e^{ik\omega_0}$, and $\Psi_\ell = e^{i\ell\omega_0n}$, we can write
$\Psi_k = 
\left[
\begin{array}{c}
\Psi_k(0) \\
\Psi_k(1) \\
\vdots \\
\Psi_k(p-1) \\
\end{array}
\right]
$, and 
$\Psi_\ell =
\left[
\begin{array}{c}
\Psi_\ell(0) \\
\Psi_\ell(1) \\
\vdots \\
\Psi_\ell(p-1) \\
\end{array}
\right]
$. 

Note that for an aperiodic signal, the inner product can be written as $\langle \Psi_k,\Psi_\ell\rangle  = \sum \limits_{n=-\infty}^{\infty}\Psi_k(n)\Psi_\ell^*(n) $ or $\int_{-\infty}^{\infty}\Psi_k(t)\Psi_\ell^*(t)dt$. For this proof, we will use the summation for a periodic signal. We can take the inner product
\begin{align*}
\langle \Psi_k,\Psi_\ell\rangle  &= \sum \limits_{n=0}^{p-1}\Psi_k(n)\Psi_\ell^*(n) \\
\langle \Psi_k,\Psi_\ell\rangle  &= \sum \limits_{n=0}^{p-1} e^{ik\omega_0n}e^{-i\ell\omega_0n} \\
\langle \Psi_k,\Psi_\ell\rangle  &= \sum \limits_{n=0}^{p-1} e^{i(k-\ell)\omega_0n} \\
\langle \Psi_k,\Psi_\ell\rangle  &= \sum \limits_{n=0}^{p-1} \lr{e^{i(k-\ell)\omega_0}}^n \\
\end{align*}
Before we arrive at our answer, lets take a slight mathematical detour. Recall that we can write a sum $S$ as 
\begin{align*}
S &= \sum \limits_{k=0}^{\infty}\alpha^k \\
S &= 1 + \alpha + \alpha^2 + \cdots  \\
\alpha S &= \alpha + \alpha^2 + \alpha^3 + \cdots  \\
(1-\alpha)S &= 1 \\
S &= \frac{1}{1-\alpha} \quad \mbox {if } \alpha \neq 1 
\end{align*}

or for a finite sum

\begin{align*}
S &= \sum \limits_{n=A}^{B}\alpha^n \\
S &= \alpha^A + \alpha^{A+1} + \cdots + \alpha^B \\
\alpha S &= \alpha^{A+1} + \alpha^{A+2} + \cdots + \alpha^{B+1} \\
(1-\alpha)S &= \alpha^{B+1} - \alpha^A \\
S &= \frac{\alpha^{B+1}-\alpha^{A}}{1-\alpha} \quad \mbox{if }\alpha \neq 1 \\
S &= \begin{cases}
\frac{\alpha^{B+1}-\alpha^{A}}{1-\alpha} & \alpha\neq1 \\
B-A+1 & \alpha=1 \\
\end{cases}
\end{align*}

Now back to our proof:

\begin{align*}
\langle \Psi_k,\Psi_\ell\rangle  &= \sum \limits_{n=0}^{p-1} \lr{e^{i(k-\ell)\omega_0}}^n \\
\langle \Psi_k,\Psi_\ell\rangle  &= \begin{cases} \frac{\lr{e^{i(k-\ell)\omega_0}}^p-\lr{e^{i(k-\ell)\omega_0}}^0}{1-e^{i(k-\ell)\omega_0}} & k\neq\ell \\ (p-1)-0+1 & k=l \\ \end{cases} \\
\langle \Psi_k,\Psi_\ell\rangle  &= \begin{cases} 0 & k\neq\ell\\ p & k=l \\ \end{cases}
\end{align*}

\end{proof}

We can generalize the result of the above proof further as

$$ \langle \Psi_k,\Psi_\ell\rangle  = p\delta(k-\ell) $$

This works well because the inner product of a vector with itself as the \emph{norm} squared, and the inner product with any other orthogonal vector is 0.
$$\langle \Psi_k,\Psi_k\rangle  = \norm{\Psi_k}^2 = p$$

A few properties about the inner product:
\begin{align*}
\langle f,g\rangle  &= f^Tg^* \\
\langle \alpha f,g\rangle  &= \alpha\langle f,g\rangle  \\
\langle f,\beta g\rangle  &= \beta^* \langle f,g\rangle  \\
\langle \sum_k \alpha_k f_k, g\rangle  &= \sum_k \alpha_k\langle f_k,g\rangle  \\
\end{align*}

So to find $X_\ell$, we can project $\vec{x}$ onto $\Psi_\ell$. 
\begin{align*}
\langle \vec{x}, \Psi_\ell\rangle  &= \langle X_0\Psi_0 + \cdots + X_\ell\Psi_\ell + \cdots + X_{p-1}\Psi_{p-1}, \Psi_\ell\rangle  \\
\langle \vec{x}, \Psi_\ell\rangle  &= X_0\langle \Psi_0,\Psi_\ell\rangle  + \cdots + X_\ell\langle \Psi_\ell,\Psi_\ell\rangle  + \cdots + X_{p-1}\langle \Psi_{p-1},\Psi_\ell\rangle  \\
\langle \vec{x}, \Psi_\ell\rangle  &= X_\ell\langle \Psi_\ell,\Psi_\ell\rangle  \quad \mbox{(all other inner products were 0)}\\
X_\ell &= \frac{\langle \vec{x}, \Psi_\ell\rangle  }{\langle \Psi_\ell,\Psi_\ell\rangle }\\
X_\ell &= \frac{\langle \vec{x}, \Psi_\ell\rangle  }{p}\\
X_\ell &= \frac{\vec{x}^T\Psi_\ell^* }{p}\\
X_\ell &= \frac{1}{p}\sum \limits_{n=0}^{p-1}x(n)\Psi_\ell^*(n) \\
X_\ell &= \frac{1}{p}\sum \limits_{n=0}^{p-1}x(n)e^{-i\ell\omega_0n} \\
\end{align*}

With the discrete fourier series, we can write signals in two distinct forms. We can write a signal in the time domain as a series of complex exponentials which can tell us what happens in the frequency domain:

\begin{nicebox}
\begin{align*}
 x(n) &= \sum \limits_{k=\langle p\rangle }X_ke^{ik\omega_0n}  \quad &\mbox{(synthesis equation)}
\end{align*}
\end{nicebox}

The coefficient in the frequency domain tells us the amount that a certain frequency contributes to the overall signal, which is given by the running sum of the product of the signal in the time domain and the frequency of interest:

\begin{nicebox}
\begin{align*}
 X_k &= \frac{1}{p} \sum \limits_{n=\langle p\rangle }x(n)e^{-ik\omega_0n} \quad &\mbox{(analysis equation)}
\end{align*}
\end{nicebox}

\begin{example}
Find the period and DFS expansion of $x(n) = \sin(2\pi n/3)$. 

To find the period, simply set the inside of the sine function to $2\pi$:
\begin{align*}
\frac{2\pi p}{3} &= 2\pi \\
p &= 3
\end{align*}

Here is a cool method for solving. Luckily, the sine is easily written as the sum of complex exponentials:

\begin{align*}
x(n) &= \sin(2\pi n/3) \\
x(n) &= \frac{e^{i2\pi n/3}-e^{-i2\pi n/3}}{2i} \\
x(n) &= \frac{-1}{2i}e^{-i2\pi n/3} + 0 \cdot e^{i0n} + \frac{1}{2i} e^{i2\pi n/3} \quad \mbox{since } p = 3
\end{align*}
So quickly we can see that we have $e^{-i2\pi n/3}, e^{i0n}, e^{i2\pi n/3}$. This tells us we have $X_{-1} = \frac{-1}{2i}, X_0 = 0, X_1 = \frac{1}{2i}$.
\end{example}


10.1 Fourier Analysis