基于FFT快速优化算法在MSP430G2553芯片上实现128点快速傅里叶变换_小字体1
需积分: 0 201 浏览量
2022-08-03
21:47:52
上传
评论 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的计算过程一般都以图形方式表示，蝶形运算就是其中的精髓。下图即为一个简单的蝶形运算：
表示的结果为：
其中 是旋转因子，旋转因子定义为：
由该定义可以推出以下性质：
1）周期性
剩余11页未读，继续阅读
资源评论
