My Lecture Note on Discrete Fourier Transform

June 6th, 2024

Ok, let me explain the Discrete Fourier Transform (DFT). I won't delve into why the Fourier Transform is important, but it is used in many fields: physics, image processing, signal processing, and many more. Let's start with the Fourier series. A periodic function $f(x)$ can be approximated by an infinite summation of sine and cosine functions. Sine and cosine can be represented using the Euler formula, $e^{ix} = \cos(x) + i\sin(x)$ . Thus,

f(x) = \sum_{n=-\infty}^{\infty} C_n e^{inx},

where $x\in(-\pi,\pi)$ . Use $t$ instead of $x$ and normalize it a bit to $\omega t$ , so we get

f(t) = \sum_{n=-\infty}^{\infty} C_n e^{in\omega t},

where $\omega = \frac{2\pi}{T}$ and $T$ is the period. The Fourier series shows the periodic property very clearly. If we shift time by one period $T$ ,

f(t+T) = \sum_{n=-\infty}^{\infty} C_n e^{in\omega(t+T)}.

Then,

f(t+T) = \sum_{n=-\infty}^{\infty} C_n e^{in\omega t} e^{in\omega T} = \sum_{n=-\infty}^{\infty} C_n e^{in\omega t} e^{in\frac{2\pi T}{T}}

f(t+T) = \sum _{n=-\infty}^{\infty}C_n e^{in\omega t} e^{in2\pi} = \sum_{n=-\infty}^{\infty} C_n e^{in\omega t}=f(t).

Here is my intuition again. In fact, $e^{inx}$ is a basis function of a periodic function $f(x)$ . To show that $e^{inx}$ is a basis, we first have to show that it is:

Linearly independent
Spanning

The first one is quite easy. To show that it is linearly independent, we need to show that given $\sum_n b_n e^{inx} = 0,$ then $b_n = 0 \text{ for all } n \in \mathbb{Z}.$ But we know that for $m \neq n$ ,

\int_{-\pi}^{\pi} e^{i(m-n)x} dx = \left[ \frac{e^{i(m-n)x}}{i(m-n)} \right]_{-\pi}^{\pi} = \frac{e^{i(m-n)\pi} - e^{-i(m-n)\pi}}{i(m-n)}

\int_{-\pi}^{\pi} e^{i(m-n)x} dx = \frac{2i\sin((m-n)\pi)}{i(m-n)} = 0,

because $m-n \in \mathbb{Z}$ resulting in $sin(\text{integer}*\pi)=0$ . For $m = n$ ,

\int_{-\pi}^{\pi} e^{i(m-m)x} dx = 2\pi.

Thus,

\int_{-\pi}^{\pi} e^{i(m-n)x} dx = \delta_{mn} 2\pi.

Applying this with

\sum_n b_n e^{inx} = 0,

we get $b_n = 0$ for all $n \in \mathbb{Z}$ . For the spanning property, here is the proof from this link. By first assuming that $e^{inx}$ spans, then

f(x) = \sum_{m=-\infty}^{\infty} C_m e^{imx}

\int_{-\pi}^{\pi} e^{-inx} f(x) dx = \sum_{m=-\infty}^{\infty} \int_{-\pi}^{\pi} e^{-inx} C_n e^{imx} dx

\int_{-\pi}^{\pi} e^{-inx} f(x) dx = \sum_{m=-\infty}^{\infty} \int_{-\pi}^{\pi} e^{-inx} C_n e^{imx} dx

C_n = \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{-inx} f(x) dx.

The coefficient of the Fourier series $C_n$ is an integral of the original function:

C_n = \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{-inx} f(x) dx.

Now substitute $C_n$ into the Fourier series of $f(x)$

f_{FS}(x) = \sum_{n=-\infty}^{\infty} C_n e^{inx},

we get

f_{FS}(x) = \sum_{n=-\infty}^{\infty} \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{-iny} f(y) dy e^{inx}

f_{FS}(x) = \frac{1}{2\pi} \int_{-\pi}^{\pi} \sum_{n=-\infty}^{\infty} e^{in(x-y)} f(y) dy.

Here, from appendix A, we have $\sum_{n=-\infty}^{\infty} e^{in(x-y)} \approx \int_{-\infty}^{\infty} e^{in(x-y)} dn$ . Using the property of the Dirac delta function $\int_{-\infty}^{\infty} e^{in(x-y)} dn=2\pi\delta(x-y)$ , we get

f_{FS}(x) = \frac{1}{2\pi} \int_{-\pi}^{\pi} 2\pi\delta(x-y) f(y) dy=f(x)

The last line implies that a function $f(x)$ is in fact $f_{FS}(x)$ , implying that $f(x)$ can be approximated using the Fourier serie.

The Fourier series might not always be useful, as sometimes we want to use it with non-periodic functions. To achieve this, we derive the Fourier Transform, which can be viewed as the general case of the Fourier series. To get a non-periodic function from a periodic one, we just need to stretch the period $T$ to $\infty$ .

First, change our $C_n$ into an appropriate form:

C_n = \frac{1}{2\pi} \int_{x=-\pi}^{x=\pi} e^{-inx} f(x) dx.

Again substituting $\omega t$ for $x$ , we have

C_n = \frac{1}{2\pi} \int_{\omega t=-\pi}^{\omega t=\pi} e^{-in\omega t} f(\omega t) d(\omega t)

C_n = \frac{\omega}{2\pi} \int_{t=-\pi/\omega}^{t=\pi/\omega} e^{-in\omega t} f(\omega t) d(t)

C_n = \frac{2\pi/T}{2\pi} \int_{t=-T/2}^{t=T/2} e^{-in\omega t} f(t) dt

C_n = \frac{1}{T} \int_{t=-T/2}^{t=T/2} e^{-in\omega t} f(t) dt

In the last line, I used the fact that $f(\omega t)$ is just $f(t)$ (with some extra constant). Next, substituting $C_n$ into our Fourier series equation and taking the limit of our period to infinity, we have

f(t) = \lim_{T \to \infty} \sum_{n=-\infty}^{\infty} C_n e^{in \omega t}

f(t) = \lim_{2\pi/\omega \to \infty} \sum_{n=-\infty}^{\infty} \frac{1}{T} \int_{t'=-\infty}^{t'=\infty} e^{-in \omega t'} f(t') dt' e^{in \omega t}

f(t) = \lim_{ \omega  \to 0} \sum_{n=-\infty}^{\infty} \frac{ \omega }{2\pi} \int_{t'=-\infty}^{t'=\infty} e^{in \omega (t-t')} f(t') dt'

f(t) = \sum_{n=-\infty}^{\infty} \frac{\Delta  \omega }{2\pi} \int_{t'=-\infty}^{t'=\infty} e^{in \Delta   \omega  (t-t')} f(t') dt'

Since $\sum_{n=-\infty}^{\infty} \Delta \omega$ is the Riemann sum, we can change $\sum_{n=-\infty}^{\infty} \Delta \omega$ to $\int_{-\infty}^{\infty} d \omega$ and $nd \omega$ to $\omega$ . The idea of the proof can be found in appendix A.

f(t) = \frac{1}{2\pi} \int_{ \omega =-\infty}^{ \omega =\infty} d \omega  \int_{t'=-\infty}^{t'=\infty} e^{i \omega (t-t')} f(t') dt'

f(t) = \frac{1}{\sqrt{2\pi}} \int_{ \omega =-\infty}^{ \omega =\infty} e^{i \omega  t} \left( \int_{t'=-\infty}^{t'=\infty} \frac{1}{\sqrt{2\pi}} e^{-i \omega  t'} f(t') dt' \right) d \omega

f(t) = \frac{1}{\sqrt{2\pi}} \int_{ \omega =-\infty}^{ \omega =\infty} e^{i \omega  t} f_{FT}( \omega ) d \omega,

where

f_{FT}( \omega ) = \int_{t'=-\infty}^{t'=\infty} \frac{1}{\sqrt{2\pi}} e^{-i \omega t'} f(t') dt'

is the Fourier transform.

Next, we will explain the DTFT and DFT. We will first begin with the DTFT, where DFT can be easily realized. The idea behind the two is quite simple: we can't actually compute continuous functions on a computer, so we need to quantize our data into its discrete representation. Given an incoming input which we call the function $f(t)$ , we can't actually store all the data. Because we know that the input is a continuous value, we have to periodically collect that data and store it on our computer before processing it. So $f(t)$ is, in fact, a vector of data, not a continuous function. If we want to analyze it using a Fourier transform, it won't work because the Fourier transform we defined above supports a function, not a vector. This is where the DTFT comes in. We want to find a discrete version of the Fourier transformation of our data, which can be easily achieved by quantizing $f(t)$ :

f_{\text{vec}}(t) = \sum_{n=-\infty}^{\infty} f(t) \delta(t-nt_{\text{sample}}).

Substitute this into the Fourier transform equation, we get

f_{FT}( \omega ) = \frac{1}{\sqrt{2\pi}} \int_{t=-\infty}^{t=\infty} e^{-i \omega t} f(t) dt \approx \frac{1}{\sqrt{2\pi}} \int_{t=-\infty}^{t=\infty} e^{-i \omega t} f_{\text{vec}}(t) dt

f_{DTFT}( \omega ) = \frac{1}{\sqrt{2\pi}} \int_{t=-\infty}^{t=\infty} e^{-i \omega t} \sum_{n=-\infty}^{\infty} f(t) \delta(t-nt_{\text{sample}}) dt

f_{DTFT}( \omega ) = \frac{1}{\sqrt{2\pi}} \sum_{n=-\infty}^{\infty} \int_{t=-\infty}^{t=\infty} e^{-i \omega t} f(t) \delta(t-nt_{\text{sample}}) dt

f_{DTFT}( \omega ) = \frac{1}{\sqrt{2\pi}} \sum_{n=-\infty}^{\infty} f(nt_{\text{sample}}) e^{-i \omega nt_{\text{sample}}}

f_{DTFT}(\Omega) = \frac{1}{\sqrt{2\pi}} \sum_{n=-\infty}^{\infty} f[n] e^{-in\Omega},

where $f[n]$ is a vector of our data in the time domain, and $\Omega = \omega t_{\text{sample}}$ . Note that $\omega = \frac{2\pi}{T}$ , and we define the new frequency $\Omega = \omega t_{\text{sample}} = \frac{2\pi t_{\text{sample}}}{T}$ . For this frequency $\Omega$ to be intuitive and make sense, $t_{\text{sample}}$ should live between 0 and $T$ , $0 < t_{\text{sample}} \leq T$ . This shows how often we sample the data. If $t_{\text{sample}} = T$ , it means we sample data every period. Thus, $\Omega$ is defined within any period of $2\pi$ , for example, $0 < \Omega \leq 2\pi$ or $-\pi < \Omega \leq \pi$ .

Finally, we can discuss Discrete Fourier Transforms. You might guess that after quantizing the time domain, we get DTFT, but the result is still a “continuous” function of $\omega$ , which again contains infinite values. To make it easy to analyze, we will quantize the frequency domain of the DTFT, and that is DFT! But that is not all; the fact that we derive DTFT from FT means that it is a function that spans the value from $-\infty$ to $\infty$ . DTFT is used with non-periodic functions (we can use it with a periodic one by defining a new function that contains only the value within one period and setting the value outside that range to zero).

Back to DFT. DFT is a Fourier Transform that is defined to work with a periodic function. Why? Because it contains a finite set of data. If we want something useful to analyze, we need data that contain finite elements in both the original domain and the transformed domain. Instead of letting DTFT span from $-\infty$ to $\infty$ in the time domain (a non-periodic function), we want it confined within a specific range and to have $N$ finite elements in the time domain. From DTFT,

f_{DTFT}(\Omega) = \frac{1}{\sqrt{2\pi}} \sum_{n=0}^{N-1} f[n] e^{-in\Omega}.

Since we want our data to be periodic rather than non-periodic, this means that $f[n]$ will repeat itself at some point. From our requirements that $f[n]$ contains $N$ finite elements, this means that $f[N] = f[0]$ . To analyze only one period, we demand that $f[i] = 0$ for $i \notin \{0, 1, \ldots, N-1\}$ .

Nevertheless, the above equation is still a continuous function of $\Omega$ . To quantize it, we sample $\Omega$ at $N$ equal intervals in the "frequency" domain. Why also $N$ in the frequency domain as well? $N$ because, well, IMO it is similar to a basis transformation where you need to preserve the rank of the original vector. In the time domain, you have a vector, and when you transform it to the frequency domain, you want to have the same vector but with a different set of basis. When you divide $e^{-in\Omega}$ into $N$ equally spaced intervals, it acts as basis functions, and they are orthogonal and become the root of unity.

The uniform interval sampling of the frequency domain gives us $\Omega = \frac{2\pi k}{N}$ where $k \in \{0, 1, 2, \ldots, N-1\}$ . Substituting $\Omega$ into $f_{DTFT}$ , we get DFT: