The Complex Discrete Fourier Transform¶
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)$
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
$\phi[k] = \tan^{-1}(imag(X[k])/real(X[k]))$¶
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")
