基于矩阵分解的快速傅立叶变换实现

资 源 简 介

本项目通过MATLAB编程，基于线性代数中的矩阵分解理论实现了快速傅立叶变换算法。具体实现方式是将传统的离散傅立叶变换(DFT)矩阵通过稀疏矩阵分解技术，转化为多个具有分块对角结构的因子矩阵乘积，从而在数学层面模拟了Cooley-Tukey算法的蝴蝶结合过程。系统利用MATLAB强大的矩阵运算能力，构建了可递归或迭代的矩阵乘法模型，将计算复杂度从O(N²)显著降低至O(N log N)。该程序不仅能够处理标准的复数序列变换，还提供了变换过程中中间矩阵的可视化分析，帮助用户直观理解信号在不同分解层级下的频谱

详 情 说 明

基于矩阵分解的MATLAB快速傅立叶变换(FFT)逻辑实现

项目介绍

本项目通过MATLAB编程，从线性代数的视角重新审视并实现了快速傅立叶变换（FFT）。与传统的递归信号流图不同，本实现核心在于将离散傅立叶变换（DFT）矩阵分解为一系列稀疏因子矩阵的乘积。这种方法在数学上严格对应了Cooley-Tukey算法的蝴蝶结合过程，利用矩阵的稀疏性将计算复杂度从 $O(N^2)$ 降低至 $O(N log N)$。该工具不仅提供了频域分析功能，还着重于算法底层数学构造的可视化，是深入理解数字信号处理中矩阵变换理论的有力工具。

功能特性

1. 矩阵分解核心算法：通过显式构造位反转置换矩阵和各阶段的蝴蝶变换稀疏矩阵，模拟FFT的运算流程。
2. 自动参数适配：能够自动将输入信号长度补齐或截断至最近的2的幂次，以满足基-2 FFT的算法要求。
3. 多维度结果分析：计算并展示信号的单边幅度谱及相位谱，准确提取多频分量。
4. 底层结构可视化：提供蝴蝶变换因子矩阵的稀疏结构图（Spy Plot）以及标准DFT矩阵的实部热力图，直观展现算法优化的数学本质。
5. 性能计时对比：实时监测并输出矩阵分解法完成变换所需的计算时间。

系统要求

• MATLAB R2016b 或更高版本。
• 基本安装环境，无需额外的工具箱（算法基于标准内建稀疏矩阵函数实现）。

实现逻辑说明

程序的执行逻辑严格遵循以下步骤：

1. 信号准备与预处理：

* 构造包含50Hz和120Hz正弦信号及随机高斯噪声的复合测试信号。 * 计算目标FFT点数 $N$，若输入长度不符合2的幂次，则进行补零或截断处理。

1. 位反转置换 (Bit-reversal Permutation)：

* 将十进制索引转换为二进制字符串并进行翻转，计算重排后的索引。 * 构造一个 $N times N$ 的稀疏置换矩阵。 * 通过矩阵乘法将原始时域序列调整为适合蝶形运算的“倒序”排列。

1. 循环迭代构造因子矩阵：

* 算法分为 $log_2 N$ 个阶段，每一阶段通过循环构造该层的蝴蝶算子。 * 旋转因子计算：根据当前阶段的步长生成对应的复指数旋转因子（Twiddle Factors）。 * 蝴蝶矩阵构造：在每一阶段定义一个稀疏矩阵，其结构包含四个关键项（$1, W, 1, -W$），分别对应蝴蝶运算的直接叠加和加权叠加分支。 * 逐层乘法完成变换：通过连续的矩阵-向量乘法，将位反转后的信号依次通过每一个因子矩阵，最终得到频域结果。

1. 频谱特征提取：

* 对变换结果进行归一化处理。 * 计算双边频谱并转换为单边幅度谱，对非直流/奈奎斯特分量进行幅值校正。

关键算法与实现细节分析

1. 位反转矩阵逻辑 该部分消除了传统递归实现中频繁的数组交换操作，通过显式矩阵 $P$ 将数据的重新排列转化为一次线性变换（$x_{permuted} = P times x$）。这体现了线性代数中置换阵的应用。

2. 稀疏因子矩阵 A_stage 这是本项目最核心的设计。在每一个阶段，程序识别出参与蝴蝶运算的两个索引位置（$u_idx$ 和 $v_idx$），并在矩阵的四个对应位置填充值。利用MATLAB的 sparse 函数，仅存储非零元素，极大提升了处理大规模数据时的内存效率。

3. 蝴蝶算子模型 矩阵中的每一行代表一个输出节点。对于每一组蝴蝶运算：

• 上半部分：$X_{out}(u) = X_{in}(u) + W times X_{in}(v)$
• 下半部分：$X_{out}(v) = X_{in}(u) - W times X_{in}(v)$

在矩阵 $A$ 中，这体现为对角线周围特定步长处元素的精确分布，这种分布随着阶段增加从“紧密型”向“跨越型”演变。

4. 结果可视化方案

• 时域与频域图：验证算法对 50Hz 和 120Hz 频率成分提取的准确性。
• 稀疏图 (spy)：显示第一阶段和最后阶段矩阵结构的不同，反映了FFT逐级合并的过程。
• DFT 矩阵对比：通过显示标准 $N times N$ 密集矩阵的热图，用户可以直观对比出为什么分解后的稀疏乘法能大幅降低运算量。

使用方法

1. 启动MATLAB软件。
2. 将代码保存为脚本或在编辑器中打开。
3. 点击“运行 (Run)”按钮。
4. 在命令行窗口查看输出的FFT点数和耗时，同时观察弹出的图形窗口，分析信号特征及矩阵结构。