The Complex Discrete Fourier Transform

In [1]:
import numpy as np
import matplotlib.pyplot as plt

Review: Real DFT

The real DFT on a signal $x$ with $N$ samples consists of sine and cosine components for a frequency $k$, which goes through $k$ cycles over $N$ samples. Each component is obtained via a dot product

Cosine Component: $c_k = \sum_{n = 0}^{N-1} x[n]*\cos(2 \pi k n / N)$

Sine Component: $s_k = - \sum_{n = 0}^{N-1} x[n]*\sin(2 \pi k n / N)$

$k = 0, 1, 2, ..., floor(N/2)$

Euler's Formula

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

Ex) $\theta = 0$, $e^{i0} = \cos(0) + i \sin(0) = 1$

Ex) $\theta = \pi/4, e^{i \pi/4} = \cos(\pi/4) + i \sin(\pi/4) = \frac{\sqrt{2}}{2} + i\frac{\sqrt{2}}{2}$

Assume that $f(\theta) = \cos(\theta) + i \sin(\theta)$

$f'(\theta) = -\sin(\theta) + i\cos(\theta) = i f(\theta)$

Therefore, $f(\theta) = e^{i \theta}$

Complex DFT

Recall the formulat for the general sinusoid:

$A \cos(2 \pi f t + \phi)$

We're going to keep it as $+\phi$ on the inside. Recall the following angle/sum trig identity:

$\cos(x + y) = \cos(x)\cos(y) - \sin(x)\sin(y)$

This allows us to rewrite the sinusoid as

$A \cos(2 \pi f t + \phi) = A \cos(\phi)\cos(2 \pi f t) - A \sin(\phi)\sin(2 \pi f t)$

Given Euler's formula, we can then rewrite the DFT using complex numbers so the real component holds the cosine component and the imaginary component holds the sine component

$X[k] = \sum_{n = 0}^{N-1} x[n]e^{- i 2 \pi \frac{k}{N} n}$

$X[k]$ will contain $c_k$ in the real component and the sine component $s_k$ in the imaginary component

We can extract the amplitude and phase from these imaginary numbers as follows

Amplitude: $A[k] = \sqrt{ real(X[k]^2) + imag(X[k])^2}$

(Complex Modulus, Magnitude, Absolute Value)

$\phi[k] = \tan^{-1}(imag(X[k])/real(X[k]))$

In [42]:
A = 3
k = 3
phi = np.pi/3
N = 100
x = A*np.cos(2*np.pi*np.arange(N)*k/N + phi)
X = np.fft.fft(x) # Fast Fourier Transform O(N \log(N))


amp = np.abs(X[0:10])
phase = np.arctan2(np.imag(X[0:10]), np.real(X[0:10]))


plt.figure(figsize=(16, 4))
plt.subplot(141)
plt.stem(np.real(X[0:10]))
plt.title("Real")
plt.subplot(142)
plt.stem(np.imag(X[0:10]))
plt.title("Imag")
plt.subplot(143)
plt.stem(amp)
plt.title("Amplitude")
plt.subplot(144)
plt.stem(phase*(amp > 0.1))
plt.title("Phase")
Out[42]:
Text(0.5, 1.0, 'Phase')
In [ ]: