课程设计（论文）-快速傅里叶变换程序设计

《课程设计（论文）-快速傅里叶变换程序设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、快速傅里叶变换程序设计1设计任务描述1.1设计题目快速傅里叶变换程序设计1.2设计要求1.2.1设计目的1）理解FFT的算法以及利用DSP实现的方法。2）能熟练的调试程序并能观察其结果。3）熟悉TMS320C54x系列DSP芯片的软件设计方法。1.3基本要求1）研究FFT原理以及利用DSP实现的方法。2）编写FFT程序。3）调试程序，观察结果。16快速傅里叶变换程序设计2设计思路2.1FFT算法原理若给定由个信号样本{（0），（1），…，（-1）}组成的信号序列（），DFT可用式2-1给出：=0,1，…，-1（

2、2-1）式2-1中，称为旋转因子或蝶形因子，=。从中可以看出：当信号样本为复数时，计算单个需经过次复数乘法和-1次复数加法运算，相当于4次实数乘法和2（2-1）次实数加法。完成全部点DFT共需次复数乘法和（-1）复数加法运算。可见，随着不断增加，整个DFT运算量是相当庞大的，而FFT算法通过对计算过程的深入分析，利用旋转因子具有的周期性与对称性，实现了降低运算复杂度的目的。当序列长度为偶数时，信号序列（）可被分解为奇、偶两个子序列，相应的点DFT被分解为两个/2点的DFT：=0,1,…，/2-1（2-2）=0,

3、1,…，/2-1（2-3）式（2-2）和（2-3）中，和分别表示（）分解后得到的/2点偶序列点奇序列的DFT。式（2-2）和式（2-3）表明，只要求出和，（）前/2点和后/2点的DFT就得到了，整个序列的DFT也就得到了。这样做的好处是计算点DFT只需要约/2次复数乘法，总运算量约为直接DFT运算量的一半同理，当/2为偶数时，每个/2点的DFT又可被分解成两个/4点的DFT，进一步减少了DFT16快速傅里叶变换程序设计运算的复杂度。依次类推，直到不能继续分解为止。分解结束时，最小DFT的点数称为称为基数，当=（

4、为正整数）时，经过-1次分解，点DFT最终可被分解为/2个两点的DFT，即得到基数为2的FFT运算，使得DFT所需复数乘法次数降至。2.2基2FFT的蝶形运算流图基2FFT的蝶形运算过程可用图2-1所示，此时=8，==3。图2-18点基2FFT运算过程观察图2-1，根据DFT的基2FFT算法，可以总结出以下几条规律：（1）点FFT运算从输入端开始，逐级进行，共需经过级运算；在第（=1，2，…，）级中存在个相似的蝶形运算组（除输入数据不同外）；每个组内蝶形运算的个数为，参与每个蝶形运算的两个输入数据相距个点。（2

5、）中间数据的存储，可采用原位存储法。即每次蝶形运算的结果存储在与原数据相同的内存单元内。（3）为了保证输出数据按自然数序排列，在进行FFT之前输入数据需要按照特定的顺序存放，通过位倒序寻址可以满足这种要求。16快速傅里叶变换程序设计2.2.1输入、输出序列的倒位序规律由流程图2-1可以看出，当进行原位运算时，发现当运算完成后，FFT的输出按自然顺序排列在存储单元中，即按，，…，的顺序排列；但是这是输入却不是按自然顺序存储的，而是按，，…，的顺序存入存储单元，这种方式就称之为倒位序。当用二进制表示这个顺序时，它正

6、好是“码位倒置”的顺序。例如，原来的自然顺序应是的地方，现在存放，用二进制码表示这一规律时，则是在处存放，出存放，即将自然顺序的二进制码位倒置过来，第一位码变成最末位码，这样倒置以后的顺序正是输入所需要的顺序。表2-1中列出的是=8时按码位倒置规律所得的顺序，其结果与按时间抽取算法FFT流程图中的输入顺序是一致的。同理，当=256时，亦可以采用同样的方法进行位倒序操作。表2-1码位倒置顺序自然顺序二进码表示码位倒置倒位序0000000010011004201001023011110641000011510110

7、1561100113711111172.2.2蝶距的计算设=，则整个运算流图中包含级蝶形运算，每一级则有个蝶形单元。蝶距即每个蝶形单元两个输入（出）节点的序号差。以为例，结合图2-1可知共包含3级蝶形运算，每一级蝶形单元的蝶距如下：第一级，蝶距为1，可以看作由得到：第二级，蝶距为2，可以看作由16快速傅里叶变换程序设计得到；第三级，蝶距为4，可以看作由得到。因此得：第级蝶形单元的蝶距为：。2.2.3旋转因子的计算由FFT算法原理过程可知，若=，则共有级蝶形运算，各级蝶形运算中旋转因子分别如下：第级的旋转因子为（

8、=0,1，…，）；第-1级的旋转因子为（=0,1，…，）；…；第一级的旋转因子为（=0,1，…，）。由此可见，第级蝶形运算中旋转因子为，=0，1，…，。2.3FFT算法的DSP的实现方法设FFT运算的输入数据为实数，则2点实数FFT算法的实现步骤为：第一步，把2实数输入序列组合成点的复数序列。然后把该复数序列进行位倒序操作后存储在输入区。第二步，进行的FFT运算。第三步，把点FFT输出