---

title: "Discrete-Time Fourier Transform (DTFT)" description: "Transform signals between time and frequency domains using FFT to analyze frequency components." order: 3

Discrete-Time Fourier Transform (DTFT)

Vibe Prompt

"A sensor samples at 8 kHz, signals at 1000, 2000, 3000 Hz. Use FFT to identify frequencies."

import numpy as np

fs = 8000
freqs = [1000, 2000, 3000]
t = np.arange(0, 1, 1/fs)
signal = sum(np.sin(2*np.pi*f*t) for f in freqs)

n = len(signal)
fft = np.fft.fft(signal)
freq = np.fft.fftfreq(n, 1/fs)
mag = abs(fft) / n

half = n // 2
peaks = [(freq[i], mag[i]) for i in range(half) if mag[i] > 0.3]

print("Detected frequencies:")
for f, m in peaks:
    print(f"  {f:.0f} Hz (intensity: {m:.4f})")

---

How FFT Works

FFT converts time-domain signals to frequency components via divide and conquer:

Given N samples (power of 2):
1. Split into even and odd indices
2. Recursively compute FFT of each group
3. Combine using butterfly operations

Naive DFT: O(N^2) - 64M operations for N=8000
FFT: O(N log N) - ~104K operations for N=8000
Speedup: ~615x!

FFT Formula

$$X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j2\pi kn/N}$$

FFT exploits symmetry and periodicity of DFT to reduce complexity from O(N^2) to O(N log N).

Spectral Resolution

| Concept | Formula | Description | |:-------:|:-------:|-------------| | Frequency resolution | Delta f = fs / N | Width per frequency bin | | Nyquist frequency | f_nyquist = fs / 2 | Maximum detectable frequency | | Sampling theorem | fs >= 2 x f_max | Must sample at 2x max frequency |

Complex Signal Analysis

import numpy as np

fs = 8000
duration = 2.0
N = int(fs * duration)
t = np.linspace(0, duration, N, endpoint=False)

# Composite signal: different frequencies, amplitudes, phases
freqs = [440, 880, 1320]  # A4, A5, E6 notes
amps = [1.0, 0.5, 0.25]
phases = [0, np.pi/4, np.pi/2]

signal = sum(a * np.sin(2*np.pi*f*t + p) for a, f, p in zip(amps, freqs, phases))
noise = np.random.normal(0, 0.15, N)
signal_noisy = signal + noise

fft = np.fft.fft(signal_noisy)
freq = np.fft.fftfreq(N, 1/fs)
magnitude = abs(fft) / N

half = N // 2
print(f"Sample count: {N}")
print(f"Frequency resolution: {fs/N:.3f} Hz/bin")
print(f"Nyquist frequency: {fs/2} Hz")

threshold = 0.08
for i in range(half):
    if magnitude[i] > threshold:
        expected = ""
        for j, (ef, ea) in enumerate(zip(freqs, amps)):
            if abs(freq[i] - ef) < 5:
                expected = f" <- original {ef} Hz (amp {ea})"
                break
        print(f"  {freq[i]:7.1f} Hz | intensity: {magnitude[i]:.4f}{expected}")

Window Functions

Real signals rarely perfect periods. Direct FFT causes spectral leakage.

| Window | Main lobe | Side lobe | Use Case | |:------:|:---------:|:---------:|----------| | Rectangular | Narrow | Poor (-13 dB) | Transient signals | | Hann | Medium | Good (-32 dB) | General default | | Hamming | Medium | Good (-43 dB) | Speech processing | | Blackman | Wide | Excellent (-58 dB) | High dynamic range | | Gaussian | Adjustable | Good | Time-frequency analysis |

def apply_hann_window(signal):
    n = len(signal)
    window = 0.5 * (1 - np.cos(2 * np.pi * np.arange(n) / (n - 1)))
    return signal * window

signal_windowed = apply_hann_window(signal_noisy)
fft_raw = abs(np.fft.fft(signal_noisy)) / N
fft_win = abs(np.fft.fft(signal_windowed)) / N

print(f"Without window: 440 Hz intensity = {fft_raw[440]:.4f}")
print(f"With Hann window: 440 Hz intensity = {fft_win[440]:.4f}")

FFT Applications

| Domain | Application | |:------:|-------------| | Music | Spectrum analysis, pitch detection, equalizer | | Speech | Formant analysis, speaker recognition | | Image | JPEG compression (DCT variant) | | Radar | Doppler shift detection, target identification | | Medical | ECG analysis, EEG brain wave analysis | | Mechanical | Vibration analysis, bearing fault detection | | Finance | Periodicity analysis, market frequency detection |

---

Key Takeaways

• FFT: O(N log N) algorithm implementing discrete Fourier transform
• Frequency resolution = fs / N, more samples = better resolution
• Nyquist frequency = fs / 2, maximum detectable frequency
• Sample rate must be >= 2x max frequency to avoid aliasing
• Window functions (Hann recommended) reduce spectral leakage
• Real-world spectrum analysis = windowing + FFT + peak detection

---

Visualization: Signal Analysis

import matplotlib.pyplot as plt

plt.figure(figsize=(14, 5))

plt.subplot(1, 2, 1)
plt.plot(t[:200], signal_noisy[:200])
plt.xlabel("Time (s)")
plt.ylabel("Amplitude")
plt.title("Time Domain (first 200 samples)")
plt.grid(True)

plt.subplot(1, 2, 2)
plt.stem(freq[:half], magnitude[:half], linefmt="b-", markerfmt="bo", basefmt="r-")
plt.xlabel("Frequency (Hz)")
plt.ylabel("Intensity")
plt.title("Frequency Spectrum")
plt.xlim(0, 2000)
plt.grid(True)

plt.tight_layout()
plt.show()

Window Function Comparison

def apply_hann_window(signal):
    n = len(signal)
    window = 0.5 * (1 - np.cos(2 * np.pi * np.arange(n) / (n - 1)))
    return signal * window

def apply_hamming_window(signal):
    n = len(signal)
    window = 0.54 - 0.46 * np.cos(2 * np.pi * np.arange(n) / (n - 1))
    return signal * window

def apply_blackman_window(signal):
    n = len(signal)
    window = 0.42 - 0.5 * np.cos(2*np.pi*np.arange(n)/(n-1)) + 0.08*np.cos(4*np.pi*np.arange(n)/(n-1))
    return signal * window

# Compare window effects
signal_hann = apply_hann_window(signal_noisy)
signal_hamming = apply_hamming_window(signal_noisy)
signal_blackman = apply_blackman_window(signal_noisy)

for name, sig in [("None", signal_noisy), ("Hann", signal_hann), ("Hamming", signal_hamming), ("Blackman", signal_blackman)]:
    spec = abs(np.fft.fft(sig)) / N
    print(f"{name}: 440 Hz = {spec[440]:.4f}, 445 Hz = {spec[445]:.4f} (leakage delta)")

Spectral Resolution Example

To distinguish 1000 Hz from 1001 Hz:

• Need resolution < 1 Hz
• Resolution = fs / N < 1
• With fs = 8000: N > 8000 samples (> 1 second)

# Resolution calculation
fs = 8000
for n in [1000, 4000, 8000, 16000]:
    res = fs / n
    print(f"N={n:5d}: resolution={res:.3f} Hz, nyquist={fs/2} Hz")

Real-World Applications

| Domain | Application | Description | |:------:|-------------|-------------| | Audio | Music equalizers | Visualize frequency bands for real-time adjustment | | Speech | Speaker identification | MFCC features extracted via FFT | | Image | JPEG compression | 2D DCT (FFT variant) for image compression | | Radar | Doppler detection | Frequency shift indicates moving object speed | | Medical | ECG analysis | Detect arrhythmias via frequency analysis | | Mechanical | Bearing monitoring | Vibration spectrum reveals wear patterns |

Key Takeaways

• FFT converts O(N^2) DFT to O(N log N) via divide and conquer
• Frequency resolution = fs / N: more data = better resolution
• Nyquist theorem: fs must be >= 2x maximum frequency
• Window functions reduce spectral leakage at cost of wider main lobe
• Hann window is the universal default for general-purpose analysis
• Real signal analysis = windowing + FFT + peak detection

DTFT Connection to Gradient Descent

| Application | Connection | |-------------|------------| | Adaptive filtering | LMS filter training uses gradient descent | | Frequency domain learning | Some models train more efficiently in frequency domain | | Audio processing | Spectral subtraction, FFT-accelerated convolution |

Next Chapter: PID Control

From frequency analysis to control systems - PID controllers for real-world applications.