文档介绍：1 设计任务描述
设计题目
快速傅里叶变换程序设计
设计要求
设计目的
1)理解FFT的算法以及利用DSP实现的方法。
2)能熟练的调试程序并能观察其结果。
3)熟悉TMS320C54x系列DSP芯片的软件设计方法。
基本要求
1)研究FFT原理以及利用DSP实现的方法。
2)编写FFT程序。
3)调试程序,观察结果。
2 设计思路
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所需复数乘法次数降至。
基2FFT的蝶形运算流图
基2FFT的蝶形运算过程可用图2-1所示,此时=8,==3。
图2-1 8点基2FFT运算过程
观察图2-1,根据DFT的基2FFT算法,可以总结出以下几条规律:
(1)点FFT运算从输入端开始,逐级进行,共需经过级运算;在第(=1,2,…,)级中存在个相似的蝶形运算组(除输入数据不同外);每个组内蝶形运算的个数为,参与每个蝶形运算的两个输入数据相距个点。
(2)中间数据的存储,可采用原位存储法。即每次蝶形运算的结果存储在与原数据相同的内存单元内。
(3)为了保证输出数据按自然数序排列,在进行FFT之前输入数据需要按照特定的顺序存放,通过位倒序寻址可以满足这种要求。
输入、输出序列的倒位序规律
由流程图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-1可知共包含3级蝶形运算,每一级蝶形单元的蝶距如下:第一级,蝶距为1,可以看作由得到:第二级,蝶距为2,可以看作由得到;第三级,蝶距为4,可以看作由得到。因此得:第级蝶形单元的蝶距为:。
旋转因子的计算
由FFT算法原理过程可知,若=,则共有级蝶形运算,各级蝶形运算中旋转因子分别如下:第
级的旋转因子为(=0,1,…,);第-1级的旋转因子为(=0,1,…,);…;第一级的旋转因子为(=0,1,…,)。由此可见, 第级蝶形运算中旋转因子为,=0,1,…,。
FFT