基于FFT快速优化算法在MSP430G2553芯片上实现128点快速傅里叶变换1
需积分: 0 5 浏览量
2022-08-03
20:53:40
上传
评论 1
收藏 1.53MB PDF 举报
基于FFT快速优化算法在MSP430G2553单片机上实
现128点快速傅里叶变换
一、项目简介及实现原理
项目简介
基于入门级单片机MSP430G2553（主时钟16MHz，512B RAM, 16KB FLASH）（对刚刚学习单片机的童鞋
来讲，这款芯片的资源已经足够，但是稍微增加一些复杂的算法或者功能就会很费劲，比如FFT算
法。如果使用最直接简单的FFT，不进行优化，则最多可以运行64点FFT，主要消耗资源为RAM，512字
节的RAM不允许开辟很大的数组）。
FFT（Fast Fourier Transform）即快速傅里叶变换，是DFT（Discrete Fourier Transform，离散傅里叶
变换）的高效算法，并不是一种新的变换。
FFT是DFT的高效算法，但FFT也有一些神奇的“变种”。参考文章 《几种特殊的FFT算法》 。本项目利
用其中的实数FFT算法用64点FFT程序框架实现128点FFT。
基本FFT原理
前言：
如果你看到了这篇文章，那么我应该默认你已经懂得了傅里叶变换是干什么的（用2553实现FFT，全
网基本上就没有，但凡想实现FFT功能的也不会选2553（老人地铁手机），所以这篇文章是学长总结
给为了学分而来的学弟们学妹们），并且也了解了DTFT，DFT，FFT等各种形式的傅里叶变换之间的联
系（即便不理解也不影响使用本程序），此处就不进行详细阐述了。一是一篇短文章不太可能把伟大
深邃的傅里叶变换讲通透；二是本文的重点是对理论转换到程序进行描述，着重于软件实现；三是笔
者水平并不高，自己也并未将傅里叶变换理解的很透彻，仅仅是了解FFT的过程以及应用范畴和各种
参数的含义，具体的数学推导以及整个理论的支撑建议大家从《信号与系统》-->《DSP数字信号处
理》中寻找答案。
FFT是啥？
简单来说，FFT就是一种快速计算DFT的方法，DFT是有限离散傅里叶变换，是将离散的数据进行离散
时间傅里叶变换（DTFT）后得到的频域连续函数再进行离散化（单独的点数据，不连续，称为离散）
得到的。所以DFT的输入数据和输出数据都是离散的。既然FFT只是DFT的快速算法，那么FFT的输入输
出也是离散的，且计算过程比DFT快，而计算机处理模拟量（连续的）比处理离散化数据难的多，所
以现在计算机普遍使用FFT进行数据处理。
FFT后的数据有什么用呢？实际上，这个问题涉及到了很多领域，因为傅里叶变换在每一个领域几乎
都可以找到它的身影。数字信号处理这门课程实际上就是在讲傅里叶变换，围绕傅里叶变换对数字信
号进行处理，那么是不是可以说只要涉及到数字信号的领域都可以用傅里叶变换作为工具去分析呢？
实际上，物联网，机械震动，通信传输，图像处理等很多你想到的，想不到的领域，都会使用到傅立
叶变换。最直接的用处就是用作信号的频谱分析。
FFT的计算过程 (本章节参考此篇知乎，基本框架代码来自该文章，优化部分为原创。想全面了解算法
请查看此篇文章，想了解优化部分，可以略过此部分，直接跳到程序优化)
整个FFT的计算过程一般都以图形方式表示，蝶形运算就是其中的精髓。下图即为一个简单的蝶形运
算：
剩余15页未读，继续阅读
评论0