離散時間傅立葉轉換 (DTFT)

🔥 Vibe Prompt

"一個音頻感測器以 8 kHz 取樣 1000 Hz、2000 Hz、3000 Hz 的訊號。使用 FFT 識別頻率。"

import numpy as np
import matplotlib.pyplot as plt

fs = 8000  # 取樣率 (Hz)
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 = np.abs(fft) / n

# 只取正頻率
half = n // 2
peaks = []
for i in range(half):
    if mag[i] > 0.3:
        peaks.append((freq[i], mag[i]))

print("檢測到的頻率：")
for f, m in peaks:
    print(f"  {f:.0f} Hz (強度: {m:.4f})")

FFT 的工作原理

快速傅立葉轉換 (FFT) 將時域訊號轉換為其頻率成分。核心思想是分而治之：

給定 N 個樣本（2 的冪次）：
1. 將樣本分為偶數索引和奇數索引兩組
2. 遞迴計算每組的 FFT
3. 使用「蝶形運算」合併結果

時間複雜度：
  樸素 DFT: O(N²)
  FFT: O(N log N)

以 N=8000 為例：
  樸素 DFT: 6400 萬次運算
  FFT: ~104,000 次運算
  加速比: ~615 倍！

FFT 的核心公式

離散傅立葉轉換 (DFT) 的數學定義：

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

其中：

$x[n]$ 是時域訊號的第 $n$ 個樣本
$X[k]$ 是頻域的第 $k$ 個頻率分量
$N$ 是總樣本數
$j$ 是虛數單位

FFT 利用 DFT 的對稱性與週期性，將計算複雜度從 $O(N^2)$ 降到 $O(N \log N)$。

頻譜解析度與取樣定理

| 概念 | 公式 | 說明 | |:----:|:----:|------| | 頻率解析度 | $\Delta f = f_s / N$ | 每個頻率 bin 的寬度，$N$ 越大解析度越高 | | 奈奎斯特頻率 | $f_{nyquist} = f_s / 2$ | 可偵測的最大頻率 | | 取樣定理 | $f_s \geq 2f_{max}$ | 需至少兩倍最高頻率的取樣率才能還原訊號 |

範例計算

fs = 8000   # 取樣率 8 kHz
N = 8000    # 1 秒的資料

freq_resolution = fs / N  # 1 Hz/bin
nyquist = fs / 2           # 4000 Hz（可偵測範圍）

# 如果我們想分辨 1000 Hz 和 1001 Hz 的差異
# 需要 freq_resolution < 1 Hz
# 因此需要 N > fs / 1 = 8000 個樣本（> 1 秒資料）

實戰：複雜訊號分析

import numpy as np
import matplotlib.pyplot as plt

fs = 8000  # 取樣率 (Hz)
duration = 2.0  # 秒
N = int(fs * duration)
t = np.linspace(0, duration, N, endpoint=False)

# 產生複合訊號：不同的頻率、振幅、相位
freqs = [440, 880, 1320]  # A4, A5, E6 音符
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 分析
fft = np.fft.fft(signal_noisy)
freq = np.fft.fftfreq(N, 1/fs)
magnitude = np.abs(fft) / N

# 尋找頻率峰值
half = N // 2
threshold = 0.08
print(f"\n{'='*50}")
print(f"FFT 頻譜分析 (取樣率={fs} Hz)")
print(f"{'='*50}")
print(f"樣本數: {N}")
print(f"頻率解析度: {fs/N:.3f} Hz/bin")
print(f"奈奎斯特頻率: {fs/2} Hz")
print(f"\n檢測到的頻率峰值：")

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" ← 原始訊號 {ef} Hz (振幅 {ea})"
                break
        print(f"  {freq[i]:7.1f} Hz | 強度: {magnitude[i]:.4f}{expected}")

# 視覺化
plt.figure(figsize=(14, 5))

plt.subplot(1, 2, 1)
plt.plot(t[:200], signal_noisy[:200])
plt.xlabel('時間 (秒)')
plt.ylabel('振幅')
plt.title('時域波形 (前 200 個樣本)')
plt.grid(True)

plt.subplot(1, 2, 2)
plt.stem(freq[:half], magnitude[:half], linefmt='b-', markerfmt='bo', basefmt='r-')
plt.xlabel('頻率 (Hz)')
plt.ylabel('強度')
plt.title('頻譜 (頻率域)')
plt.xlim(0, 2000)
plt.grid(True)

plt.tight_layout()
plt.show()

窗函數 (Windowing)

實際訊號通常不是完整的週期，直接進行 FFT 會產生頻譜洩漏 (Spectral Leakage)——能量從真實頻率擴散到相鄰頻率。窗函數可以減輕這個問題。

| 窗函數 | 主瓣寬度 | 旁瓣衰減 | 適用場景 | |:------:|:--------:|:--------:|---------| | 矩形窗 | 窄 | 差 (-13 dB) | 暫態訊號分析 | | 漢寧窗 | 中 | 好 (-32 dB) | 通用預設 | | 海明窗 | 中 | 好 (-43 dB) | 語音訊號處理 | | 黑曼窗 | 寬 | 極佳 (-58 dB) | 需要高動態範圍 | | 高斯窗 | 可調 | 好 | 時頻分析 |

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_unwindowed = signal_noisy
signal_windowed = apply_hann_window(signal_noisy)

fft_raw = np.abs(np.fft.fft(signal_unwindowed)) / N
fft_windowed = np.abs(np.fft.fft(signal_windowed)) / N

print(f"無窗函數: 峰值頻率 440 Hz 強度 = {fft_raw[440]:.4f}")
print(f"加漢寧窗: 峰值頻率 440 Hz 強度 = {fft_windowed[440]:.4f}")
print(f"窗函數優點：旁瓣能量減少 {(fft_raw[445]-fft_windowed[445])/fft_raw[445]*100:.1f}%")

FFT 的應用場景

| 領域 | 應用 | |:----:|------| | 🎵 音樂 | 頻譜分析、音高偵測、等化器 | | 🗣️ 語音 | 共振峰分析、語者辨識 | | 📷 影像 | JPEG 壓縮（DCT 變體） | | 📡 雷達 | 都卜勒頻移偵測、目標識別 | | 🫀 醫療 | ECG/EKG 心率分析、EEG 腦波分析 | | 🔧 振動 | 機械故障檢測、軸承狀態監控 | | 💹 金融 | 週期性分析、市場頻率偵測 |

關鍵要點

✅ FFT 是 $O(N \log N)$ 的演算法，實現離散傅立葉轉換
✅ 頻率解析度 = $f_s / N$，取更多樣本可提升解析度
✅ 奈奎斯特頻率 = $f_s / 2$，是可偵測的最高頻率
✅ 取樣率必須至少為最高頻率的 2 倍才能避免混淆
✅ 窗函數（漢寧窗是通用預設）可減少頻譜洩漏
✅ 實際訊號的頻譜分析需結合窗函數 + FFT + 峰值檢測

為什麼要學離散時間傅立葉轉換 DTFT？

離散時間傅立葉轉換 DTFT 是 algorithm-gradient-descent 課程的核心章節之一。

在真實世界中

離散時間傅立葉轉換 DTFT 並不是課本上的理論——它在真實的軟體開發中頻繁出現。無論你是正在接案、準備面試，還是想要提升自己的技術深度，理解這個主題都能讓你直接受益。

你將從本章獲得

🎯 完整的知識體系：從核心原理到實作細節，條理分明
💻 可運行的程式碼：每段程式碼都是完整的，可直接執行
🔍 除錯技巧：常見錯誤的分析與解決方案
🚀 下一步指引：學完後該往哪個方向繼續深入

銜接下一章

本章為你建立了離散時間傅立葉轉換 DTFT 的完整知識基礎。下一章將在此基礎上，帶你探索更進階的真實世界應用場景——你將學會如何將本章所學應用到更複雜的問題中。