探秘基带算法：从原理到5G期间的通讯厘革【七】FFT/DFT

登录 · 发表于 2025-10-21 16:59:13

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

探秘基带算法：从原理到5G期间的通讯厘革【一】弁言
探秘基带算法：从原理到5G期间的通讯厘革【二】Viterbi解码
探秘基带算法：从原理到5G期间的通讯厘革【三】Turbo 编解码
探秘基带算法：从原理到5G期间的通讯厘革【四】Polar 编解码（一）
探秘基带算法：从原理到5G期间的通讯厘革【四】Polar 编解码（二）
探秘基带算法：从原理到5G期间的通讯厘革【五】CORDIC算法
探秘基带算法：从原理到5G期间的通讯厘革【六】CRC 校验
探秘基带算法：从原理到5G期间的通讯厘革【七】FFT/DFT
探秘基带算法：从原理到5G期间的通讯厘革【八】QAM 调制 / 解调
探秘基带算法：从原理到5G期间的通讯厘革【九】QPSK调制/解调
探秘基带算法：从原理到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 ] = ∑ n = 0 N − 1 x [ n ] e − j 2 π N k n , k = 0 , 1 , … , N − 1 X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn}, \quad k = 0, 1, \ldots, N-1 X[k]=n=0∑N−1x[n]e−jN2πkn,k=0,1,…,N−1
此中：

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

DFT公式的徐徐推导

为了更好地明确DFT公式，我们可以从欧拉公式入手。欧拉公式表明，复指数函数可以分解为正弦和余弦函数的线性组合：
                                          e                                     −                            j                            θ                                           =                      cos                      ⁡                      (                      θ                      )                      −                      j                      sin                      ⁡                      (                      θ                      )                            e^{-j \theta} = \cos(\theta) - j \sin(\theta)                e−jθ=cos(θ)−jsin(θ)
因此，DFT公式可以改写为：
                                 X                      [                      k                      ]                      =                                  ∑                                     n                            =                            0                                              N                            −                            1                                           x                      [                      n                      ]                                  (                         cos                         ⁡                                     (                                                       2                                  π                                           N                                        k                            n                            )                                     −                         j                         sin                         ⁡                                     (                                                       2                                  π                                           N                                        k                            n                            )                                     )                                     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)                X[k]=n=0∑N−1x[n](cos(N2πkn)−jsin(N2πkn))
这分析DFT现实上是将输入信号                            x                   [                   n                   ]                         x[n]             x[n]投影到一组正交基函数（正弦和余弦函数）上，从而得到信号的频率分量。

图：DFT的多少意义。
进一步观察公式可以发现，DFT的焦点运算是一个矩阵乘法利用。假如我们用矩阵情势体现DFT，可以写成：
X = W ⋅ x \mathbf{X} = \mathbf{W} \cdot \mathbf{x} X=W⋅x
此中：

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

图：DFT的矩阵体现。
只管DFT的数学界说简朴明确，但其盘算复杂度为 O ( N 2 ) O(N^2) O(N2)，当 N N N较大时，盘算本钱会显着增长。为相识决这一标题，FFT应运而生。

2.6.2 快速傅里叶变更（FFT）

快速傅里叶变更（FFT）是一种高效的算法，用于加快DFT的盘算。FFT的焦颔首脑是使用对称性和周期性来镌汰不须要的重复盘算。以下是FFT的根本推导过程：
假设输入信号长度                            N                         N             N为2的幂次方（即                            N                   =                            2                      m                               N = 2^m             N=2m），我们可以将DFT公式分为两部分：偶数索引项和奇数索引项。
                                 X                      [                      k                      ]                      =                                  ∑                                     n                            =                            0                                              N                            /                            2                            −                            1                                           x                      [                      2                      n                      ]                                  e                                     −                            j                                                       2                                  π                                           N                                        k                            (                            2                            n                            )                                           +                                  ∑                                     n                            =                            0                                              N                            /                            2                            −                            1                                           x                      [                      2                      n                      +                      1                      ]                                  e                                     −                            j                                                       2                                  π                                           N                                        k                            (                            2                            n                            +                            1                            )                                                 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]=n=0∑N/2−1x[2n]e−jN2πk(2n)+n=0∑N/2−1x[2n+1]e−jN2πk(2n+1)
通过简化指数项，可以得到：
                                 X                      [                      k                      ]                      =                                  ∑                                     n                            =                            0                                              N                            /                            2                            −                            1                                           x                      [                      2                      n                      ]                                  e                                     −                            j                                                       2                                  π                                                          N                                  /                                  2                                                    k                            n                                           +                                  W                         N                         k                                           ∑                                     n                            =                            0                                              N                            /                            2                            −                            1                                           x                      [                      2                      n                      +                      1                      ]                                  e                                     −                            j                                                       2                                  π                                                          N                                  /                                  2                                                    k                            n                                                 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}                X[k]=n=0∑N/2−1x[2n]e−jN/22πkn+WNkn=0∑N/2−1x[2n+1]e−jN/22πkn
此中：

W N k = e − j 2 π N k W_N^k = e^{-j \frac{2\pi}{N} k} WNk=e−jN2πk 称为旋转因子。

由此可见，FFT将原始标题分解为两个规模减半的子标题，从而大幅镌汰了盘算量。终极，FFT的盘算复杂度低落为 O ( N log ⁡ N ) O(N \log N) O(NlogN)。

图：FFT的蝶形运算结构。

2.6.3 方法论与分类体系

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

实数输入DFT：当输入信号为实数时，频域结果具有共轭对称性，即 X [ k ] = X ∗ [ N − k ] X[k] = X^*[N-k] X[k]=X∗[N−k]。这种对称性可以进一步优化盘算服从。
二维DFT：实用于图像处理处罚等场景，二维DFT可以分解为两次一维DFT的级联利用。
短时傅里叶变更（STFT）：用于分析非安稳信号，通过引入滑动窗口将信号分割为多个短片断，分别举行DFT盘算。

表：DFT与FFT的重要分类。
分类特点实数输入DFT频域结果具有共轭对称性，适当处理处罚实数信号。二维DFT将二维信号分解为行和列的一维DFT，广泛应用于图像处理处罚范畴。STFT引入时间窗，适当分析随时间厘革的信号特性。

图：STFT。

2.6.4 优缺点与应用

优点

高效性：FFT算法显着低落了DFT的盘算复杂度，使其可以或许在大规模数据处理处罚中发挥作用。
普适性：DFT和FFT实用于各种范例的信号处理处罚使命，包罗音频、图像、通讯等范畴。
理论根本踏实：基于严格的数学理论，可以或许提供可靠的频域分析结果。

缺点

对输入长度的要求：FFT要求输入信号长度为2的幂次方，否则必要举行零添补。
频谱走漏：由于DFT本质上是对信号的有限采样，大概导致频谱走漏征象。
无法直接处理处罚非匀称采样信号：对于非匀称采样的信号，必要额外的预处理处罚步调。

应用方向

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

音频信号处理处罚：通过FFT分析音频信号的频谱特性，可用于音高检测、噪声消除等使命。
图像处理处罚：二维DFT可以用于图像压缩、滤波和加强等利用。
通讯体系：FFT是OFDM（正交频分复用）调制解调的核默算法之一。
科学盘算：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()

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源