发布时间 : 星期五 文章8点基于DIT的FFT的实现更新完毕开始阅读6f5862997c1cfad6185fa725
武汉理工大学《数字信号处理》课程设计说明书
x1(2l)?x3(l)?N,l?0,1,2,...,?1 （3.1.13） ?x1(2l?1)?x4(l)?4代入x1(r)的N/2点的DFT表达式中有： X1(k)?DFT[x1(r)]N/2?1? ?r?0x1(r)WN/2x1(2l)WN/2?lk2lkN/4?1rkN/4?1???l?0?l?0kx1(2l?1)WN/2 （3.1.14） N/4?1(2l?1)kN/4?1?l?0x3(l)WN/4?WN/2k?l?0x4(l)WN/4lk?X3(k)?WN/2X4(k)且由对称性和周期性有： X1(k?其中： N/4?1Nk)?X3(k)?WN/2X4(k) （3.1.15） 4X3(k)?DFT[x3(l)]? ?l?0l?0x3(l)WN/4,k?0,1,2,...rkrkN?14N?14N/4?1 （3.1.16） X4(k)?DFT[x4(l)]??x4(l)WN/4,k?0,1,2,...所以，当N=8时，上一步分解出的一个N/2点的DFT可以分解成两个N/4点的DFT，运算流图如图3.3所示。 x(0) N/4点 X3(0) X1(0) DFT x(4) X3(1) X1(1) x(2) N/4点 X4(0) WN/2 -1 X1(2) DFT x(6) X4(1) WN/2 -1 X1(3) 11
9
武汉理工大学《数字信号处理》课程设计说明书
图3.3 由两个N/4点DFT组合成1个N/2点DFT 同理，X2(k)也做同样的分解，得： X2(k)?X5(k)?WN/2X6(k) （3.1.17） X2(k?其中： N/4?1kNk)?X5(k)?WN/2X6(k) （3.1.18） 4X5(k)?DFT[x5(l)]? ?l?0l?0x5(l)WN/4,k?0,1,2,...x6(l)WN/4,k?0,1,2,...rkrkN?14N?14N/4?1 （3.1.19） X6(k)?DFT[x6(l)]??这样就可以把两个N/2点的DFT分解成四个N/4点的DFT。当N=8时，经过两次分解后的运算流图如图3.4所示。 图3.4 DIT-FFT二次分解 由于满足N?2L，所以经过二次分解后N/4仍然是偶数，可以继续分解。根据上述讨论，经过L-1次分解后，就可以把一个N点的DFT分解成N/2个两点的DFT，而每一个两点的DFT可以根据如图3.1所示的蝶形图来进行计算。当N=8时，于是就可以把一个完整的8点的DFT分解成4个两点的DFT进行运算。计算一个完整的N=8点的DIT-FFT蝶形图
10
武汉理工大学《数字信号处理》课程设计说明书
如图3.5所示。
x(0)
X(0) x(4) x(2)x(6)W0N?1W0N2NX(1)?1?1W0NX(2)X(3)X(4)X(5)X(6)
W0N?1Wx(1)
?1?1?1?1x(5)
x(3)W0N?1W0N1WN
W0N?1?1W2Nx(7)
?12WNW
3NX(7)图3.5 N=8 DIT-DFT的蝶形图
3.2 DIT-FFT的运算量
观察图3.5，可见当N?2L时，经过L-1次分解，整个DIT-FFT运算有L级蝶形，每一级蝶形有N/2个蝶形运算，每一个蝶形运算有一次复数乘法好人两次复数加法，所以整个运算流图的运算量为： 复数乘法： mF?L?复数加法： aF?L?N?2?N1bN (3.2.2) 2NN?1?1bN (3.2.1) 22直接计算DFT需要N2次复数乘法与N(N-1)次复数加法运算，直接计算DFT与DIT-FFT的复数乘法运算量之比为：
11
武汉理工大学《数字信号处理》课程设计说明书
N2N22N (3.2.3) ??NN1bNL1bN223.3 DIT-FFT算法的特点
1. 原位运算
在DIT-FFT的蝶形图中，取第m级且两输入节点分别在第k、j行的蝶形为例，讨论DIT-FFT的原位运算规律。如图3.6所示，蝶形运算的关系式可表示为：
r??Xm(k)?Xm?1(k)?WNXm?1(j)? ?Xm(j)?Xm?1(k)?WrXm?1(j) (3.2.4)
N?从式中可以看出，第m级蝶形第k行与第j行的输出，只与第m-1级的第k行与第j行的输出有关，换言之，第m-1级的第k行与第j行的输出Xm?1(k)与Xm?1(j)在运算流图中的作用就是用来计算第m级的第k行与第j行的输出Xm(k)与Xm(j)。这样当计算完Xm(k)与Xm(j)后，Xm?1(k)与Xm?1(j)在运算流图不再起作用，因此就可以把Xm(k)与Xm(j)直接存放在原来存放Xm?1(k)与Xm?1(j)的存储单元中。同理，可以把第m级蝶形的N个输出值直接存放在第m-1级蝶形输出的N个存储单元中，这样从第一级的输入x（n）开始，到最后一级输出X(k)，只需要N个存储单元。
X1(k) X1(k)?WNX2(k)
X2(k) X1(k)?WNX2(k) WN -1
图3.6 按时间抽取蝶形运算结构
rkk 2. 倒序规律
从图3.5可以看出，按原位计算时，蝶形图的输出正好是自然顺序X(0),X(1),...,X(7)，但是输入却不是自然顺序，而是x(0),x(4),x(6)...，表面看起来好像是“混乱无序”的，实际上是有规律的，即倒序的排列方法。
倒序的形成原因是FFT不断对序列进行奇偶分组造成的，重新排列了序列的存放顺序，
12