快速傅里葉變換（Fast Fourier Transform，FFT）是一種算法，用于快速計算離散傅里葉變換（DFT）及其逆變換。傅里葉變換將時間或空間域的信號轉換為頻率域的信號，便于分析信號的頻率特性。FFT顯著提高了計算效率，將計算復雜度從$O(n^2)$降低到$O(n\log n)$。

FFT的基本原理

傅里葉變換的基本公式為：
$$X(k)=\sum _{n=0}^{N?1}x(n)?e^{?j\frac{2\pi }{N}kn}$$
其中，$x(n)$是時間域信號，$X(k)$是頻率域信號，$N$是信號的長度，$j$是虛數單位。

FFT利用分治法，將DFT分解成若干個更小的DFT計算。常用的算法包括Cooley-Tukey算法、分裂基算法等。

Cooley-Tukey算法

Cooley-Tukey算法是最常用的FFT算法，它將DFT分解成兩個長度為$N/2$的DFT，遞歸計算，直到達到最小子問題。

1. 將原始序列分為奇數和偶數兩部分：
   $$X(k)=\sum _{n=0}^{N/2?1}x(2n)?e^{?j\frac{2\pi }{N}2nk}+\sum _{n=0}^{N/2?1}x(2n+1)?e^{?j\frac{2\pi }{N}(2n+1)k}$$

2. 通過變換得到：
   $$X(k)=\sum _{n=0}^{N/2?1}x(2n)?e^{?j\frac{2\pi }{N/2}nk}+e^{?j\frac{2\pi }{N}k}\sum _{n=0}^{N/2?1}x(2n+1)?e^{?j\frac{2\pi }{N/2}nk}$$

3. 遞歸計算兩個$N/2$長度的DFT，最終合并結果。

FFT的應用

FFT廣泛應用于信號處理、圖像處理、音頻處理、譜分析等領域。例如：

• 音頻處理：FFT用于分析音頻信號的頻譜成分，以進行音頻壓縮、噪聲消除等操作。
• 圖像處理：通過FFT進行圖像的頻域處理，如濾波、邊緣檢測等。
• 通信：FFT在數字信號處理（DSP）中用于調制解調、信號分析等。

代碼示例

以下是一個使用Python中的numpy庫計算FFT的示例：

import numpy as np
import matplotlib.pyplot as plt# 生成一個信號：包含兩個不同頻率的正弦波
fs = 1000  # 采樣頻率
t = np.arange(0, 1, 1/fs)  # 時間序列
f1, f2 = 50, 120  # 信號頻率
x = 0.6 * np.sin(2 * np.pi * f1 * t) + 0.4 * np.sin(2 * np.pi * f2 * t)# 計算FFT
X = np.fft.fft(x)
freqs = np.fft.fftfreq(len(X), 1/fs)# 繪制頻譜
plt.figure()
plt.plot(freqs[:len(freqs)//2], np.abs(X)[:len(X)//2])
plt.xlabel('Frequency (Hz)')
plt.ylabel('Amplitude')
plt.title('Frequency Spectrum')
plt.show()

這個示例生成了一個包含50Hz和120Hz兩個頻率成分的信號，通過FFT計算頻譜并繪制結果。