《FFT的C语言实现》
设计报告
姓 名：江海啸 学 号：U2010119511 班 级： 电气1006
专 业：电气工程及其自动化 指导教师：李开成
时 间：2012年八月至九月
华中科技大学 电气与电子工程学院
1
姓名：江海啸 班级：电气1006班
时间：2012年八月至九月 编程软件：microsoft visual studio2010
一、 简介：
FFT（Fast Fourier Transformation），即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。
本程序可以实现简单的FFT变换。它具有较简单的人机交互界面，可以选择FFT的变换点数（最低为4点，最高为512点），对输入不足的点自动补零，并返回输入的点数，计算结果较为精确。
二、 编程思想及原理：
本程序主要由两部分组成，一部分是FFT变换函数，另一部分是实现人机交互的主函数，其中FFT主函数由复数加法模块，复数减法模块，复数乘法模块，倒序模块，蝶形计算模块组成。主要程序框图见图 1，FFT算法的原理介绍将不再在本篇报告里面赘述，详细原理见科学出版社出版的《信号与系统基础——应用Web和MATLAB（第三版）》第128面。
开始主程序提示输入输入有错检测输入输入正确FFT计算输出数组
图 1 系统整体框图
三、 模块介绍：
1. 主程序模块
主程序程序框图见图 2，它的主要功能是人机交互，可以让用户选择FFT变换点数和输入需要变换的点数，并对未输入的点进行自动补零，并提示用户输入的点数。
2
主程序开始主程序提示选择变换点数错误（最多重复6次）检测输入正确提示输入N个点（N为前面选择的变换点数）在最后输入的数后加“，0”可退出出输入。输入完毕，不足自动补零并提示用户输入点数。FFT变换输出结果 图 2 主函数程序框图
2. FFT模块
本模块实现了FFT的运算，先对输入数组进行倒序排列，倒序排列使用了雷德算法，然后再对重排以后的数列进行蝶形算法。下面先对雷德算法进行简要介绍。
表 1倒序前后对比
倒序排列前 000（0） 001（1） 010（2） 011（3） 100（4） 101（5） 110（6） 111（7） 倒序排列后 000（0） 100（4） 010（2） 110（6） 001（1） 101（5） 011（3） 111（7） 由 可以看出，排序以前的数最低位增1，排序以后的数最高位就增1，并且排序以后的数是向低位进位的，所以根据这个原理，雷德算法可以实现倒序排列。雷德算法的程序框图
3
见图 3
定义两个整数i，j。其中j为i的倒序数，初始值都为0.检测j的最高位是否为1是最高位减1否依次检测次高位是否为1是该位减1否该位加1i加1 图 3 雷德算法程序框图
本程序的蝶形算法采用迭代变换系数的方法，蝶形图见图 4
图 4蝶形图
编程思想是：先计算蝶形级数，然后计算运算系数和一级里面蝶形结的宽度，再计算
4
相关推荐：
loading