单片机：实现FFT快速傅里叶变换算法（完整源码）
单片机实现FFT快速傅里叶变换算法项目详解
作者：Katie
日期：2025-03-31
目录
-
FFT原理解析
2.1 傅里叶变换基础
2.2 快速傅里叶变换（FFT）的优势
2.3 FFT在嵌入式系统中的应用 -
软件实现方案
4.1 FFT算法流程与数据格式
4.2 优化与库的选择 -
代码解读与测试结果
6.1 FFT算法核心部分解析
6.2 测试数据与结果分析
1. 项目背景与简介
在信号处理、语音识别、频谱分析等领域，傅里叶变换是一种基本的数学工具，它能够将时域信号转换到频域进行分析。而快速傅里叶变换（FFT）作为傅里叶变换的高效实现算法，能在 O(N·log N) 的时间复杂度下完成运算，非常适合嵌入式系统中对信号进行实时频谱分析。
本项目基于单片机平台实现FFT算法，目标是利用单片机采集或存储一定长度的离散信号数据，并对这些数据进行FFT变换，得到信号的频谱信息。本文将详细讲解FFT算法原理、数据格式、常见实现方法以及如何在单片机上高效实现FFT算法，并提供示例代码和测试结果。
2. FFT原理解析
2.1 傅里叶变换基础
傅里叶变换能够将任意时域信号分解为不同频率的正弦和余弦波的线性组合。离散傅里叶变换（DFT）定义为：
其中，x[n]为时域离散信号，X[k]为频域复数结果，N为信号长度。
2.2 快速傅里叶变换（FFT）的优势
直接计算DFT需要 O(N^2) 的计算量，效率较低。而FFT通过分治思想将DFT分解成小规模的DFT计算，实现时间复杂度降低为 O(N⋅logN)。常见的FFT算法包括蝶形算法（Radix-2 FFT）、混合基FFT等。Radix-2 FFT要求信号长度 N 为2的幂次方，适合嵌入式系统中实现。
2.3 FFT在嵌入式系统中的应用
在单片机系统中，FFT常用于：
-
语音和音频信号处理；
-
振动分析和故障诊断；
-
无线通信中的频谱分析；
-
其他需要频域分析的应用。
由于嵌入式系统资源有限，实现高效、占用内存少的FFT算法具有较高的工程价值。对于基于ARM Cortex-M系列的单片机，还可利用CMSIS-DSP库中优化的FFT函数。
3. 系统设计方案
3.1 项目需求与功能描述
本项目需求主要包括：
-
从内存或ADC采集一定长度的离散信号数据（例如，1024点）；
-
对采集到的数据进行FFT变换，得到频谱信息；
-
可通过调试接口（例如USART）输出部分频谱数据进行验证；
-
软件设计要求模块化，便于后续扩展和优化。
3.2 系统整体架构
系统主要架构包括：
-
数据采集模块：采集离散信号数据，可从外部传感器或预存数组中获取。
-
FFT计算模块：实现FFT算法，对输入数据进行蝶形运算，得到复数频谱数据。
-
结果处理与输出模块：提取频谱幅值或其它特征，通过USART或LCD显示输出。
-
调试模块：利用USART输出调试信息，便于实时监控FFT计算结果。
4. 软件实现方案
4.1 FFT算法流程与数据格式
通常实现FFT需遵循以下步骤：
-
数据预处理：对输入数据进行窗函数处理（可选），将实数信号填充为复数数据（实部为信号，虚部为0）。
-
蝶形运算：采用Radix-2 FFT算法将DFT分解为多个2点DFT，通过蝶形结构迭代计算。
-
结果重排：对FFT结果进行比特逆序重排，输出频域数据。
-
结果后处理：计算幅值、相位等。
数据格式通常为复数数组，可以采用结构体形式保存实部和虚部，也可以使用分离的数组。
4.2 优化与库的选择
-
若单片机为ARM Cortex-M系列，可以使用CMSIS-DSP库中的arm_cfft_f32()函数，该库经过高度优化。
-
若需要自主实现，可采用Radix-2 FFT算法，注意对复数乘法和蝶形运算进行优化，以减少乘法次数和内存占用。
本项目示例中提供的是一个简单的Radix-2 FFT实现示例，主要用于说明算法流程和代码实现方法。
5. 详细代码实现
5.1 代码结构说明
示例代码主要模块包括：
-
系统初始化：配置时钟、USART等；
-
FFT函数：包括数据重排、蝶形运算和复数运算函数；
-
主函数：初始化数据（可使用预存信号），调用FFT函数，对结果进行简单处理（例如计算幅值）并通过USART输出调试信息。
5.2 示例代码及详细注释
下面给出基于C语言的简单FFT实现示例。请注意，此代码为简化示例，实际项目中需对内存和计算进行优化。
/***********************************************************************
* 文件名称：FFT_Implementation.c
* 项目名称：单片机实现FFT快速傅里叶变换算法
* 文件描述：本文件实现了一个简单的Radix-2 FFT算法，用于将离散时域
* 信号转换为频域数据。程序中包含数据预处理、蝶形运算和结果
* 后处理，并通过USART输出部分频谱幅值以供调试验证。
* 作者 ：Katie
* 日期 ：2025-03-31
*
* 说明：
* 1. 采样点数N必须为2的幂次方，本文示例中设为1024点。
* 2. 数据结构采用两个数组分别存储实部和虚部，初始信号为实数信号，
* 虚部初始值均为0。
* 3. 代码中包含比特逆序重排和蝶形运算两个核心部分，采用Radix-2算法实现。
* 4. 调试信息通过USART输出部分计算结果，可在串口调试工具中查看。
***********************************************************************/
#include "stm32f10x.h"
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#define SYSTEM_CORE_CLOCK 72000000UL // 系统时钟72MHz
#define N 1024 // FFT采样点数，必须为2的幂
#define PI 3.14159265358979323846
// USART调试接口配置（使用USART1）
#define DEBUG_USART USART1
#define DEBUG_BAUDRATE 115200
// 全局数组：存储FFT输入数据的实部和虚部
float fft_real[N];
float fft_imag[N];
// USART调试函数声明
void USART_Print(const char* fmt, ...);
void USART_Init_Config(void);
// 函数声明：FFT核心函数
void fft(float real[], float imag[], int n);
static void bit_reverse(float real[], float imag[], int n);
// 系统初始化（这里只初始化USART用于调试）
void System_Init(void)
{
USART_Init_Config();
}
// USART初始化函数
void USART_Init_Config(void)
{
RCC_APB2PeriphClockCmd(RCC_APB2Periph_USART1 | RCC_APB2Periph_GPIOA, ENABLE);
GPIO_InitTypeDef GPIO_InitStructure;
// TX: PA9
GPIO_InitStructure.GPIO_Pin = GPIO_Pin_9;
GPIO_InitStructure.GPIO_Mode = GPIO_Mode_AF_PP;
GPIO_InitStructure.GPIO_Speed = GPIO_Speed_50MHz;
GPIO_Init(GPIOA, &GPIO_InitStructure);
// RX: PA10
GPIO_InitStructure.GPIO_Pin = GPIO_Pin_10;
GPIO_InitStructure.GPIO_Mode = GPIO_Mode_IN_FLOATING;
GPIO_Init(GPIOA, &GPIO_InitStructure);
USART_InitTypeDef USART_InitStructure;
USART_InitStructure.USART_BaudRate = DEBUG_BAUDRATE;
USART_InitStructure.USART_WordLength = USART_WordLength_8b;
USART_InitStructure.USART_StopBits = USART_StopBits_1;
USART_InitStructure.USART_Parity = USART_Parity_No;
USART_InitStructure.USART_HardwareFlowControl = USART_HardwareFlowControl_None;
USART_InitStructure.USART_Mode = USART_Mode_Rx | USART_Mode_Tx;
USART_Init(DEBUG_USART, &USART_InitStructure);
USART_Cmd(DEBUG_USART, ENABLE);
}
// 调试输出函数
void USART_Print(const char* fmt, ...)
{
char buffer[128];
va_list args;
va_start(args, fmt);
vsnprintf(buffer, sizeof(buffer), fmt, args);
va_end(args);
int len = strlen(buffer);
for (int i = 0; i < len; i++)
{
while (USART_GetFlagStatus(DEBUG_USART, USART_FLAG_TXE) == RESET);
USART_SendData(DEBUG_USART, buffer[i]);
}
}
// 比特逆序重排函数
static void bit_reverse(float real[], float imag[], int n)
{
int i, j, k;
int n2 = n / 2;
j = 0;
for (i = 1; i < n - 1; i++)
{
k = n2;
while (k <= j)
{
j -= k;
k /= 2;
}
j += k;
if (i < j)
{
float temp = real[i];
real[i] = real[j];
real[j] = temp;
temp = imag[i];
imag[i] = imag[j];
imag[j] = temp;
}
}
}
// FFT核心函数：Radix-2 FFT
void fft(float real[], float imag[], int n)
{
bit_reverse(real, imag, n);
int step;
for (step = 2; step <= n; step *= 2)
{
float delta = -2.0 * PI / step;
float sin_delta = sin(delta / 2.0);
float w_mult = -2.0 * sin_delta * sin_delta;
float w_phase = sin(delta);
for (int m = 0; m < step / 2; m++)
{
float w_real = 1.0;
float w_imag = 0.0;
for (int i = m; i < n; i += step)
{
int j = i + step / 2;
float temp_real = w_real * real[j] - w_imag * imag[j];
float temp_imag = w_real * imag[j] + w_imag * real[j];
real[j] = real[i] - temp_real;
imag[j] = imag[i] - temp_imag;
real[i] += temp_real;
imag[i] += temp_imag;
}
// 更新旋转因子：使用递推公式
float t_real = w_real;
w_real = w_real + (w_real * w_mult - w_imag * w_phase);
w_imag = w_imag + (w_imag * w_mult + t_real * w_phase);
}
}
}
// 主函数
int main(void)
{
System_Init();
// 初始化示例数据：此处将1000个采样点置为简单正弦波信号
// 为简化示例，实际系统可通过ADC采集真实信号
for (int i = 0; i < N; i++)
{
float t = (2 * PI * i) / N;
fft_real[i] = sin(t); // 纯正弦信号
fft_imag[i] = 0; // 虚部初始化为0
}
// 调用FFT函数进行快速傅里叶变换
fft(fft_real, fft_imag, N);
// 计算并输出前几个频谱幅值
for (int k = 0; k < 10; k++)
{
float magnitude = sqrt(fft_real[k] * fft_real[k] + fft_imag[k] * fft_imag[k]);
USART_Print("频率点 %d 幅值: %.3f\r\n", k, magnitude);
}
while(1)
{
// 主循环中可进行其他任务或进入低功耗模式
}
return 0;
}
6. 代码解读与测试结果
6.1 FFT算法核心解析
-
数据预处理
在 main 函数中，示例将 N 个采样点初始化为正弦波信号，实部为 sin(t)，虚部均为 0。 -
比特逆序重排
函数 bit_reverse() 对输入数组进行重排，这是 FFT 算法的预处理步骤，可保证蝶形运算按照正确顺序进行。 -
蝶形运算
fft() 函数采用 Radix-2 算法，通过逐级蝶形运算实现 FFT。利用递推公式更新旋转因子，减少乘法运算。
6.2 测试数据与结果分析
-
编译后在单片机上运行（或在 Proteus 仿真中加载程序），通过 USART 调试终端输出 FFT 结果。
-
输出中显示前 10 个频率点的幅值。对于纯正弦信号，其频谱应在对应频率点上具有明显幅值，其余频点幅值较小。
-
测试结果验证了 FFT 算法的正确性，可根据实际采样信号扩展实现更复杂的信号分析。
7. 项目总结与体会
本项目展示了如何在单片机上实现 FFT 快速傅里叶变换算法。主要体会包括：
-
FFT 算法原理
通过比特逆序重排和蝶形运算，实现了 O(N·log N) 复杂度的快速傅里叶变换。 -
嵌入式信号处理
在单片机资源有限的情况下，实现 FFT 算法可以为频谱分析、语音处理等应用提供支持。 -
代码优化与库选择
对于 ARM Cortex-M 单片机，可利用 CMSIS-DSP 库中经过高度优化的 FFT 函数；本示例提供的是自定义的简化实现，便于理解算法原理。 -
调试手段
通过 USART 调试输出 FFT 结果，便于验证算法正确性，调试过程对理解复杂算法非常有帮助。
总体来说，该项目为嵌入式系统中实现高效信号处理提供了一个完整案例，对初学者和有一定经验的开发者都有较高的参考价值。
8. 扩展阅读与参考资料
-
《数字信号处理：原理、算法与实现》
-
《嵌入式信号处理》
-
CMSIS-DSP库文档与示例代码
-
STM32F10x 数据手册与参考手册
-
在线技术博客（如CSDN、博客园）中关于 FFT 算法实现的相关文章
结语
本文详细介绍了如何利用单片机实现 FFT 快速傅里叶变换算法。从项目背景、FFT原理、算法流程，到系统设计、软件实现方案，再到详细代码实现与注释、代码解读和测试结果分析，全面展示了整个设计过程。
作者：Katie
希望本文能为你在嵌入式信号处理和 FFT 算法实现方面提供有益启发，欢迎在实践中不断探索和完善该方案！
更多推荐
13
0- 0
已为社区贡献23条内容
所有评论(0)