快速傅里叶变换程序设计精选.doc

1 设计任务描述 1.1 设计题目 快速傅里叶变换程序设计 1.2 设计要求 1.2.1 设计目的 1）理解FFT的算法以及利用DSP实现的方法。 2）能熟练的调试程序并能观察其结果。 3）熟悉TMS320C54x系列DSP芯片的软件设计方法。 1.3 基本要求 1）研究FFT原理以及利用DSP实现的方法。 2）编写FFT程序。 3）调试程序，观察结果。 2 设计思路 2.1 FFT算法原理 若给定由个信号样本{（0），（1），…，（-1）}组成的信号序列（），DFT可用式2-1给出： =0,1，…，-1 （2-1） 式2-1中，称为旋转因子或蝶形因子，=。从中可以看出：当信号样本为复数时，计算单个需经过次复数乘法和-1次复数加法运算，相当于4次实数乘法和2（2-1）次实数加法。完成全部点DFT共需次复数乘法和（-1）复数加法运算。可见，随着不断增加，整个DFT运算量是相当庞大的，而FFT算法通过对计算过程的深入分析，利用旋转因子具有的周期性与对称性，实现了降低运算复杂度的目的。 当序列长度为偶数时，信号序列（）可被分解为奇、偶两个子序列，相应的点DFT被分解为两个/2点的DFT： =0,1, …，/2-1 （2-2） =0,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，进一步减少了DFT运算的复杂度。依次类推，直到不能继续分解为止。分解结束时，最小DFT的点数称为称为基数，当=（为正整数）时，经过-1次分解，点DFT最终可被分解为/2个两点的DFT，即得到基数为2的FFT运算，使得DFT所需复数乘法次数降至。 2.2 基2FFT的蝶形运算流图 基2FFT的蝶形运算过程可用图2-1所示，此时=8，==3。 图2-1 8点基2FFT运算过程 观察图2-1，根据DFT的基2FFT算法，可以总结出以下几条规律： （1）点FFT运算从输入端开始，逐级进行，共需经过级运算；在第（=1，2，…，）级中存在个相似的蝶形运算组（除输入数据不同外）；每个组内蝶形运算的个数为，参与每个蝶形运算的两个输入数据相距个点。 （2）中间数据的存储，可采用原位存储法。即每次蝶形运算的结果存储在与原数据相同的内存单元内。 （3）为了保证输出数据按自然数序排列，在进行FFT之前输入数据需要按照特定的顺序存放，通过位倒序寻址可以满足这种要求。 2.2.1 输入、输出序列的倒位序规律 由流程图2-1可以看出，当进行原位运算时，发现当运算完成后，FFT的输出按自然顺序排列在存储单元中，即按，，…，的顺序排列；但是这是输入却不是按自然顺序存储的，而是按，，…，的顺序存入存储单元，这种方式就称之为倒位序。 当用二进制表示这个顺序时，它正好是“码位倒置”的顺序。例如，原来的自然顺序应是的地方，现在存放，用二进制码表示这一规律时，则是在处存放，出存放，即将自然顺序的二进制码位倒置过来，第一位码变成最末位码，这样倒置以后的顺序正是输入所需要的顺序。表2-1中列出的是=8时按码位倒置规律所得的顺序，其结果与按时间抽取算法FFT流程图中的输入顺序是一致的。同理，当=256时，亦可以采用同样的方法进行位倒序操作。 表2-1 码位倒置顺序 自然顺序 二进码表示 码位倒置 倒位序 0 000 000 0 1 001 100 4 2 010 010 2 3 011 110 6 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7 2.2.2 蝶距的计算 设=，则整个运算流图中包含级蝶形运算，每一级则有个蝶形单元。蝶距即每个蝶形单元两个输入（出）节点的序号差。以为例，结合图2-1可知共包含3级蝶形运算，每一级蝶形单元的蝶距如下：第一级，蝶距为1，可以看作由得到：第二级，蝶距为2，可以看作由得到；第三级，蝶距为4，可以看作由得到。因此得：第级蝶形单元的蝶距为：。 2.2.3 旋转因子的计算 由FFT算法原理过程可知，若=，则共有级蝶形运算，各级蝶形运算中旋转因子分别如下：第级的旋转因子为（=0,1，…，）；第-1级的旋转因子为（=0,1，…，）；…；第一级的旋转因子为（=0,1，…，）。由此可见， 第级蝶形运算中旋转因子为，=0，1，…，。 2.3 FFT算