用Rust实现FFT算法（快速傅里叶变换入门教程）

什么是FFT？

FFT 是离散傅里叶变换（DFT）的一种高效实现方式。DFT 的时间复杂度是 O(N²)，而 FFT 可将其优化到 O(N log N)。这使得处理大规模数据成为可能。

在本教程中，我们将实现经典的 Cooley-Tukey 算法，它适用于输入长度为 2 的幂次（如 2, 4, 8, 16...）的情况。

准备工作

首先，请确保你已安装 Rust 开发环境。若未安装，可访问 rust-lang.org 下载并安装。

我们不需要任何外部 crate（除非你想使用更成熟的库如 rustfft），但为了学习原理，我们将从头编写代码。

Rust FFT 算法实现

在 Rust 中，复数通常用 num_complex::Complex 表示，但为了减少依赖，我们自己定义一个简单的复数结构。

// 定义复数结构体#[derive(Clone, Debug)]struct Complex {    re: f64,    im: f64,}impl Complex {    fn new(re: f64, im: f64) -> Self {        Complex { re, im }    }    // 复数加法    fn add(&self, other: &Complex) -> Complex {        Complex::new(self.re + other.re, self.im + other.im)    }    // 复数减法    fn sub(&self, other: &Complex) -> Complex {        Complex::new(self.re - other.re, self.im - other.im)    }    // 复数乘法    fn mul(&self, other: &Complex) -> Complex {        Complex::new(            self.re * other.re - self.im * other.im,            self.re * other.im + self.im * other.re,        )    }}

接下来，我们实现核心的 FFT 函数。这里采用递归方式（虽然效率不如迭代，但逻辑更清晰）：

use std::f64::consts::PI;fn fft(x: &[Complex]) -> Vec<Complex> {    let n = x.len();    if n <= 1 {        return x.to_vec();    }    // 分治：偶数索引和奇数索引    let mut even = Vec::with_capacity(n / 2);    let mut odd = Vec::with_capacity(n / 2);    for i in 0..n {        if i % 2 == 0 {            even.push(x[i].clone());        } else {            odd.push(x[i].clone());        }    }    // 递归计算    let q = fft(&even);    let r = fft(&odd);    // 合并结果    let mut y = vec![Complex::new(0.0, 0.0); n];    for k in 0..n / 2 {        let angle = -2.0 * PI * k as f64 / n as f64;        let wk = Complex::new(angle.cos(), angle.sin());        let t = wk.mul(&r[k]);        y[k] = q[k].add(&t);        y[k + n / 2] = q[k].sub(&t);    }    y}

测试我们的 FFT 实现

现在，我们用一个简单的正弦波信号来测试 FFT 是否工作正常：

fn main() {    // 构造一个长度为8的输入信号（必须是2的幂）    let signal = vec![        Complex::new(1.0, 0.0),        Complex::new(1.0, 0.0),        Complex::new(1.0, 0.0),        Complex::new(1.0, 0.0),        Complex::new(0.0, 0.0),        Complex::new(0.0, 0.0),        Complex::new(0.0, 0.0),        Complex::new(0.0, 0.0),    ];    let result = fft(&signal);    println!("FFT Result:");    for (i, c) in result.iter().enumerate() {        println!("{}: {:.3} + {:.3}i", i, c.re, c.im);    }}

运行后，你会看到输出结果。理想情况下，直流分量（第0个点）应为4.0，其余为0或接近0（由于浮点精度误差）。

注意事项与优化方向

• 本实现仅支持输入长度为 2 的幂。实际应用中可使用 混合基 FFT 或补零（zero-padding）处理任意长度。
• 递归版本在大数据量时可能栈溢出。建议改用 位逆序置换 + 迭代 的 Cooley-Tukey 实现。
• 对于生产环境，推荐使用成熟的库如 rustfft，它高度优化且支持多线程。

总结

通过本教程，你已经掌握了如何用 Rust语言 从零实现一个基础的 FFT算法。这不仅加深了你对 快速傅里叶变换 原理的理解，也展示了 Rust 在 数值计算 和 信号处理 领域的强大能力。

记住，学习 Rust FFT算法 不仅是为了写代码，更是为了理解信号背后的数学之美。继续探索吧，未来的音频工程师或科学计算开发者！