Fourier_Transform

There are four versions of the Fourier transform, dependent on the spaces that are mapped by the transformation:

discrete/periodic–discrete/periodic: discrete Fourier transform
continuous/periodic–discrete/aperiodic: Fourier series
discrete/aperiodic–continuous/periodic: discrete-time Fourier transform
continuous/aperiodic–continuous/aperiodic: Fourier transform

This article is particularly good for intuitive understanding of fourier transform.

Fourier Series

Fourier Transform

Basic Idea of Decomposing Signal

Defining Task: imagine a device is recording the sound of a piano from $t = 0$ to $t = 10$ . Assume each piano's keyboard produce one pure frequency of sound, our task is to know which keyboard is pressed (ie. what are the pure frequencies at time $t$ )

We can decompose any signal into multiple klzzwxh:0005 waves. Adding them together can result the original signal — We can decompose any signal into multiple $\cos$ waves. Adding them together can result the original signal

Decomposing Finite Signal with Positive Range

For finite length, positive range signals, we wind the signal up with different winding frequency $\xi$ clockwise (winding frequency $\xi > 0$ ). Given a pure signal, for the most winding frequency, the center of mass (denoted by $(x, y)$ ) is close to $0$ .

Winding a pure, finite length, positive range signal clockwise. The distance of the location of center of mass is graphed as a function of winding frequency.

You will expect the resulting frequency graph in above image to only have a dot exactly at the frequency of the original signal. This is the case for infinite signal. But since we are dealing with finite signal, we need more than one frequency. Because the negative part of the frequency is exact mirror of positive part, we don't need to consider that.

At some frequency that is equal to the pure frequency of original signal, however, the resulting graph of distance has a spike. The height of the spike is the average of absolute value of amplitude in a period.

Notice the graph has a spike at zero frequency. This spike's height is the average amplitude of the whole signal. If the signal is shifted down and centered to zero amplitude, the spike will disappear.

You can transform a signal to its corresponding frequency graph, and can transform (real part of) the frequency graph back to recover the original signal.

A fourier transform of a frequency graph is the inverse-fourier transform.

There is one-to-one correspondence between a signal and its frequency graph. One can add up two frequency graph $C_\xi = A_\xi + B_\xi$ , then we can recover $C = A + B = \text{back transform}(C_\xi)$ .

The exact formula for calculating center of mass is:

$\frac{1}{t_2 - t_1} \int_{t_1}^{t_2} g(t) e^{-2\pi i \cdot \xi \cdot t} dt$

We analyze above equation:

$e^{it}$ : the Cartesian coordinate (with one real axis and one imaginary axis) you end up after walking counter clockwise in a unit circle from $(1, 0)$ or $1 + 0i$ . $f(t) = e^{it}$ will graph the path of the walk.
$e^{-it}$ : same as $e^{ti}$ but walking clockwise
$e^{-2\pi i t}$ : same as above but walking at speed $2\pi$
$e^{-2\pi i \xi\cdot t}$ : same as above but walking at frequency $f$
$g(t)e^{-2\pi i \xi\cdot t}$ : same as above but adding the amplitude of the original signal. The resulting path looks like winding of original signal clockwise with frequency $\xi$ .
$\frac{1}{t_2 - t_1} \int_{t_1}^{t_2} g(t) e^{-2\pi i \cdot \xi \cdot t} dt$ : integrate the path and divide by domain to find out the center of mass where $\frac{1}{t_2 - t_1}$ can be seen as dividing the number of samples.

The fourier transform is the scaled version of center of mass where the center of mass (denoted by a vector) is scaled by the domain length of the frequency:

$\hat{g(\xi)} = \int_{t_1}^{t_2} g(t) e^{-2\pi i \cdot \xi \cdot t} dt$

Therefore, for a infinite length signal, the transform has a spike whose height is infinite. Also, for a infinite length pure signal, the transform is zero at other frequency.

Decomposing Phased Signal

Phased signal is harder since it requires both $\sin$ and $\cos$ .

$\hat{g(\xi)} = \int_{t_1}^{t_2} g(t) e^{-2\pi i \cdot \xi \cdot t} dt$

Notice fourier transform gives us a a sum of complex numbers $g(t) e^{-2\pi i \cdot \xi \cdot t} = c_n = a + bi$ for some $a, b, c_n$ (since they are integrated from a complex sinusoid). This complex number at specific frequency $\xi$ can be represented by two things: its magnitude and angle. The complex number can be viewed as coefficient of the transform. To draw the frequency graph: we interpret its magnitude $|c_n|$ as the amplitude of the represented sinusoid and argument (angle of of complex number as a vector) as the phase shift of the represented sinusoid.

Complex Representation of Sinusoid

To understand why we have $e^{2\pi i \xi t}$ in a non-graphical way, we see how we can represent sinusoid using complex number. Essentially $e^{2\pi i \xi x}$ represents a circle whose axis are represented by a real function of $t$ (correspond to $\cos$ ) and a imaginary function of $t$ (correspond to $\sin$ )

We know the exponential term in the fourier transform can be viewed as following:

$e^{i \theta} = \cos\theta + i \sin\theta$

$e^{2\pi i \xi t} = \cos(2\pi\xi t) + i \sin(2\pi\xi t)$

To see why above formulas hold, let me introduce the complex definition of $\sin, \cos$ .

We derive complex representation of $\cos$ :

$\begin{align*} &\begin{cases} e^{iz} = \cos(z) + i \sin(z)\\ e^{-uz} = \cos(-z) + i \sin(-z)\\ \end{cases}\\ =&\begin{cases} e^{iz} = \cos(z) + i \sin(z)\\ e^{-uz} = \cos(-z) - i \sin(z) \tag{by $\sin(-z) = -\sin(z)$}\\ \end{cases}\\ =& \cos(z) = \frac{1}{2}(e^{iz} + e^{-iz})\\ =& \cos(2\pi \xi x) = Re(e^{2\pi i \xi x}) = \frac{1}{2}(e^{2\pi i \xi x} + e^{-2\pi i \xi x})\\ \end{align*}$

We derive complex representation of $\sin$ :

$\begin{align*} &\begin{cases} e^{iz} = \cos(z) + i \sin(z)\\ e^{-uz} = \cos(-z) + i \sin(-z)\\ \end{cases}\\ =&\begin{cases} e^{iz} = \cos(z) + i \sin(z)\\ -e^{-uz} = -\cos(-z) + i \sin(z) \tag{by $\sin(-z) = -\sin(z)$ and multiply by $-1$}\\ \end{cases}\\ =& \sin(z) = \frac{1}{2i}(e^{iz} - e^{-iz})\\ =& \sin(2\pi \xi x) = Im(e^{2\pi i \xi x}) = \frac{1}{2i}(e^{2\pi i \xi x} - e^{-2\pi i \xi x})\\ \end{align*}$

Therefore, adding complex representation of $\sin, \cos$ gives us $e^{2\pi i \xi t}$ . This resembles the same idea of combining $\sin, \cos$ in two axis forms a circle of some sort. The math is just unnecessarily complicated.

The first image is the original signal. The second image is the klzzwxh:0035 and klzzwxh:0036 part of the circle winded at frequency klzzwxh:0037 and the third image is winded at klzzwxh:0038. The last image is magnitude of fourier transform. — The first image is the original signal. The second image is the $\cos$ and $\sin$ part of the circle winded at frequency $5 Hz$ and the third image is winded at $3 Hz$ . The last image is magnitude of fourier transform.

Fast Fourier Transform

FFT in Python

Table of Content