探秘基带算法：从原理到5G时代的通信变革【七】FFT/DFT

本博客为系列博客，主要讲解各基带算法的原理与应用，包括：viterbi解码、Turbo编解码、Polar编解码、CORDIC算法、CRC校验、FFT/DFT、QAMtiaozhi/解调、QPSK调制/解调。其他博客链接如下：

1. 探秘基带算法：从原理到5G时代的通信变革【一】引言
2. 探秘基带算法：从原理到5G时代的通信变革【二】Viterbi解码
3. 探秘基带算法：从原理到5G时代的通信变革【三】Turbo 编解码
4. 探秘基带算法：从原理到5G时代的通信变革【四】Polar 编解码（一）
5. 探秘基带算法：从原理到5G时代的通信变革【四】Polar 编解码（二）
6. 探秘基带算法：从原理到5G时代的通信变革【五】CORDIC算法
7. 探秘基带算法：从原理到5G时代的通信变革【六】CRC 校验
8. 探秘基带算法：从原理到5G时代的通信变革【七】FFT/DFT
9. 探秘基带算法：从原理到5G时代的通信变革【八】QAM 调制 / 解调
10. 探秘基带算法：从原理到5G时代的通信变革【九】QPSK调制/解调
11. 探秘基带算法：从原理到5G时代的通信变革【十】基带算法应用与对比

2.6 FFT/DFT

傅里叶变换（Fourier Transform）是信号处理和数据分析领域的重要工具，而离散傅里叶变换（Discrete Fourier Transform，DFT）和快速傅里叶变换（Fast Fourier Transform，FFT）则是其在数字领域的核心实现。本文将深入探讨DFT与FFT的原理、方法论、分类体系、优缺点以及实际应用方向，并通过详细的公式推导和实例分析帮助读者全面掌握这一技术。

2.6.1 离散傅里叶变换（DFT）

• 原理

傅里叶变换的核心思想是将时域信号分解为不同频率的正弦波分量。对于连续信号，我们使用连续傅里叶变换；而对于离散信号，则需要采用离散傅里叶变换（DFT）。DFT的基本定义如下：
$$X[k]=\sum _{n=0}^{N-1}x[n]e^{-j\frac{2\pi }{N}kn},k=0,1,\dots ,N-1$$

其中：

• $x[n]$ 是输入信号的第$n$个采样值。
• $X[k]$ 是频域中第$k$个频率分量。
• $N$ 是信号的总采样点数。
• $e^{-j\frac{2\pi }{N}kn}$ 是复指数函数，用于表示正弦波分量。

• DFT公式的逐步推导

为了更好地理解DFT公式，我们可以从欧拉公式入手。欧拉公式表明，复指数函数可以分解为正弦和余弦函数的线性组合：

$$e^{-j\theta }=\cos (\theta )-j\sin (\theta )$$

因此，DFT公式可以改写为：

$$X[k]=\sum _{n=0}^{N-1}x[n]\left(\cos \left(\frac{2\pi }{N}kn\right)-j\sin \left(\frac{2\pi }{N}kn\right)\right)$$

这说明DFT实际上是将输入信号$x[n]$投影到一组正交基函数（正弦和余弦函数）上，从而得到信号的频率分量。

图：DFT的几何意义。

进一步观察公式可以发现，DFT的核心运算是一个矩阵乘法操作。如果我们用矩阵形式表示DFT，可以写成：

$$\mathbf{X}=\mathbf{W}\cdot \mathbf{x}$$

其中：

• $\mathbf{X}$ 是频域向量。
• $\mathbf{x}$ 是时域向量。
• $\mathbf{W}$ 是一个$N\times N$的矩阵，称为“旋转因子矩阵”。

图：DFT的矩阵表示。

尽管DFT的数学定义简单明了，但其计算复杂度为$O(N^2)$，当$N$较大时，计算成本会显著增加。为了解决这一问题，FFT应运而生。

2.6.2 快速傅里叶变换（FFT）

快速傅里叶变换（FFT）是一种高效的算法，用于加速DFT的计算。FFT的核心思想是利用对称性和周期性来减少不必要的重复计算。以下是FFT的基本推导过程：

假设输入信号长度$N$为2的幂次方（即$N=2^m$），我们可以将DFT公式分为两部分：偶数索引项和奇数索引项。

$$X[k]=\sum _{n=0}^{N/2-1}x[2n]e^{-j\frac{2\pi }{N}k(2n)}+\sum _{n=0}^{N/2-1}x[2n+1]e^{-j\frac{2\pi }{N}k(2n+1)}$$

通过简化指数项，可以得到：

$$X[k]=\sum _{n=0}^{N/2-1}x[2n]e^{-j\frac{2\pi }{N/2}kn}+W_N^k\sum _{n=0}^{N/2-1}x[2n+1]e^{-j\frac{2\pi }{N/2}kn}$$

其中：

• $W_N^k=e^{-j\frac{2\pi }{N}k}$ 称为旋转因子。

由此可见，FFT将原始问题分解为两个规模减半的子问题，从而大幅减少了计算量。最终，FFT的计算复杂度降低为$O(N\log N)$。

图：FFT的蝶形运算结构。

2.6.3 方法论与分类体系

根据输入信号的特性，DFT和FFT可以分为以下几种类型：

1. 实数输入DFT：当输入信号为实数时，频域结果具有共轭对称性，即$X[k]=X^{\ast }[N-k]$。这种对称性可以进一步优化计算效率。

2. 二维DFT：适用于图像处理等场景，二维DFT可以分解为两次一维DFT的级联操作。

3. 短时傅里叶变换（STFT）：用于分析非平稳信号，通过引入滑动窗口将信号分割为多个短片段，分别进行DFT计算。

表：DFT与FFT的主要分类。

图：STFT。

2.6.4 优缺点与应用

• 优点

1. 高效性：FFT算法显著降低了DFT的计算复杂度，使其能够在大规模数据处理中发挥作用。
2. 普适性：DFT和FFT适用于各种类型的信号处理任务，包括音频、图像、通信等领域。
3. 理论基础扎实：基于严格的数学理论，能够提供可靠的频域分析结果。

• 缺点

1. 对输入长度的要求：FFT要求输入信号长度为2的幂次方，否则需要进行零填充。
2. 频谱泄漏：由于DFT本质上是对信号的有限采样，可能导致频谱泄漏现象。
3. 无法直接处理非均匀采样信号：对于非均匀采样的信号，需要额外的预处理步骤。

• 应用方向

DFT和FFT在现代科技中有广泛的应用，以下列举几个典型场景：

1. 音频信号处理：通过FFT分析音频信号的频谱特征，可用于音高检测、噪声消除等任务。
2. 图像处理：二维DFT可以用于图像压缩、滤波和增强等操作。
3. 通信系统：FFT是OFDM（正交频分复用）调制解调的核心算法之一。
4. 科学计算：FFT常用于求解偏微分方程、卷积计算等问题。

图：DFT与FFT在音频信号处理中的应用。

2.6.5 实现细节

在实际编程中，可以通过多种语言实现DFT和FFT。以下是一个简单的Python代码示例，展示如何使用NumPy库计算FFT：

import numpy as np
import matplotlib.pyplot as plt

# 输入信号
x = np.array([1, 2, 3, 4])

# 计算FFT
X = np.fft.fft(x)

# 输出结果
print("FFT Result:", X)

# 绘制频谱图
plt.stem(np.abs(X), use_line_collection=True)
plt.title("FFT Spectrum")
plt.xlabel("Frequency Bin")
plt.ylabel("Amplitude")
plt.show()