文档介绍：:..) 理解FFT的算法以及利用DSP实现的方法。2) 能熟练的调试程序并能观察具结果。3) 熟悉TMS320C54X系列DSP芯片的软件设计方法。) 研究FFT原理以及利用DSP实现的方法。2) 编写FFT程序。3) 调试程序,观察结果。{x(0),兀(1),…,兀(N・l)}组成的信号序列兀(n),DFT可用式2・1给岀:N-1X(k)=^x(n)w^kk二0,1,・・・,N-1n=O(2-1)式2・1中,W腭称为旋转因子或蝶形因子,w^k=e~jM/N。从中可以看叽当信号样本为复数时,计算单个X伙)需经过N次复数乘法和N・1次复数加法运算,相当于4N次实数乘法和2(2N・1)次实数加法。完成全部N点DFT共需TV?次复数乘法和N(7V-1)复数加法运算。可见,随着N不断增加,整个DFT运算量是相当庞大的,而FFT算法通过对计算过程的深入分析,利用旋转因子W护具有的周期性与对称性,实现了降低运算复朵度的目的。当序列长度N为偶数时,信号序列兀(几)可被分解为奇、偶两个子序列,相应的N点DFT被分解为两个N/2点的DFT:X伙)=G⑹+敝/7伙) k=0,1,・・・,N/2-1(2-2)X(N/2+k)=G伙)— 伙) k二0,1,…,N/2-1(2-3)式(2-2)和(2-3)中,G(k)和H伙)分别表示x(“)分解后得到的N/2点偶序列点奇序列的DFTo式(2-2)和式(2-3)表明,只要求出G(k)和H伙),兀(«)前W/2点和后N/2点的DFT就得到了,整个序列的DFT也就得到了。这样做的好处是计算N点DFT只需要约"2/2次复数乘法,总运算虽约为直接DFT运算量的一半同理,当N/2为偶数时,每个N/2点的DFT乂可被分解成两个N/4点的DFT,进一步减少了DFT运算的复杂度。依次类推,直到不能继续分解为止。分解结束时,最小DFT的点数称为称为基数,当N=2・(乙为正整数)时,经ilL-1次分解,N点DFT最终可被分解为N/2个两点的DFT,即得到基数为2的FFT运算,使得DFT所需复数乘法次数降至(N⑵logJ。・1,根据DFT的基2FFT算法,可以总结出以下儿条规律:(1) N点FFT运算从输入端开始,逐级进行,共需经过厶级运算;在第加(m=l,2,…,M)级屮存在个相似的蝶形运算组(除输入数据不同外);每个组内蝶形运算的个数为2W-',参与每个蝶形运算的两个输入数据相距2心个点。(2) 屮间数据的存储,可采用原位存储法。即每次蝶形运算的结果存储在与原数据相同的内存单元内。(3) 为了保证输出数据按自然数序排列,在进行FFTZ前输入数据需要按照特定的顺序存放,通过位倒序寻址可以满足这种要求。、输出序列的倒位序规律由流程图2・1可以看出,当进行原位运算时,发现当运算完成后,FFT的输tBX⑹按自然顺序排列在存储单元中,即按X(0),X(l),…,X(7)的顺序排列;但是这是输入兀(防却不是按自然顺序存储的,而是按兀(0),兀(4),・・・,x(7)的顺序存入存储单元,这种方式就称之为倒位序。当用二进制表示这个顺序时,它正好是“码位倒置”的顺序。例如,原来的自然顺序应是兀⑴的地方,现在存放x(4),用二进制码表示这一规律时,则是在x(001)处存放兀(100),班011)出存放兀(110),即将自然顺序的二进制码位倒置过来,第一位码变成最末位码,这样倒置以后的顺序正是输入所需要的顺序。表2-1中列出的是N詣时按码位倒置规律所得的顺序,其结果与按时间抽取算法FFT流程图中的输入顺序是一致的。同理,当W二256时,亦可以采用同样的方法进行位倒序操作。表2-1码位倒置顺序自然顺序二进码表示码位倒置倒位序000000001001100420100102301111064100001151011015611001**********.=»,则整个运算流图中包含厶级蝶形运算,每一级则有N/2个蝶形单元。蝶距即每个蝶形单元两个输入(出)节点的序号差。以N=8为例,结合图2・1可知共包含3级蝶形运算,每一级蝶形单元的蝶距如下:第一级,蝶距为1,可以看作由21-1=2°得到:第二级,蝶距为2,可以看作由22-1=2,得到;第三级,蝶距为4,可以看作由23'1=22得到。因此得:第加级蝶形单元的蝶距为:2心。,若N=2l,则共有厶级蝶形运算,各级蝶形运算中旋转因子分别如下:第厶级的