MATLAB从零开始实现快速傅里叶变换FFT

一、基础目标

在 MATLAB 中从零开始实现快速傅里叶变换（FFT）是一项非常有益的工作，有助于深入理解这个核心算法的精妙之处。

二、FFT的核心思想

FFT 并非一种新的变换，而是离散傅里叶变换（DFT）的一种高效算法。它的核心目标是通过巧妙的分解策略，将 DFT 巨大的计算量O ( N 2 ) O(N^2)O(N2)显著降低到O ( N l o g N ) O(NlogN)O(NlogN)，从而使得实时处理大规模信号数据成为可能。

实现这一目标主要依赖两个关键思想：
1）分治法（Divide and Conquer）：FFT算法（特别是最常用的基-2 算法）的核心在于，将一个长度为N的DFT持续分解为两个长度为N/2的DFT（分别计算偶数索引点和奇数索引点），然后递归地进行下去，直到序列长度为1。长度为1序列，其DFT就是它自身。
**2）利用旋转因子的特性：**旋转因子W N k = e − j 2 π k / N W_N^k=e^{-j2\pi k/N}WNk​=e−j2πk/N具有周期性和对称性。FFT算法正是充分利用了这些数学性质，避免了大量重复计算。

三、实现步骤与 MATLAB 代码

这里我们以实现一个经典的递归式基-2 FFT​ 为例，这是理解算法最直观的方式。

第一步：编写递归 FFT 函数

下面的 my_fft函数完成了 FFT 的核心计算流程。它首先处理输入序列，然后按奇偶索引分解，递归调用自身，最后通过蝶形运算组合结果。

functionX=my_fft(x)% 自定义递归实现FFT（基-2算法）% 输入：x - 输入时域信号序列% 输出：X - 频域信号（复数序列）N=length(x)