FFT算法分析（精）

1、fft算法分析fft算法的基本原理是把长序列的dft逐次分解为较短序列 的dfto按照抽取方式的不同可分为dit-fft （按时间抽取）和 dif-fft （按频率抽取）算法。按照蝶形运算的构成不同可分为 基2、基4、基8以及任意因子（2n,n为大于1的整数），基2、 基4算法较为常用。基2、dit-fft (按时间抽取人x伙)=工心)必'n=0=x + x"偶数2奇数n/2-1n/2-1=£ x(2r)c2r + £ x(2r + l)w；(2r+,)r=0n=0n/2-1n/2-1=z x2r)c2£ 兀(2厂 + 1)臥；2r=0z?=0n

2、/2-1n/2-1令工x(2”w；2 = xi伙)，工班2厂+ l)wj；2 = x2伙)，则有:r=0r=0x 伙)= xi(k) + w；x2伙)x(k + n/2) = xi(k)-wx2(k)xiqt)dit-fft基2、dif-fft (按频率抽取)：nx二(小枕“”=0n/2-】n-1=s血)呼+ x心)呼/j=0n=n2n/2-】n/2-1=e x(72)w+ £ x(/? + n/2)w,e71=0p】=0n/2-1=工心)+叱畀2如川畸71=0n/2-1x(2门二工xs) + xa + n/2)w，；27：=0n/2-1x(2r + 1)= x mn)-x(n +

3、n/2)wxf2n=0则有：xi(n) = x(n) + x(n + n / 2)x2(n) = %(/?) 一 xn + n / 2)w$心+ "/2丫、兀2（勿dif-fft由前面的分析可知，dit （按时间抽取）算法与dif （按频率 抽取）算法没有本质上的区别，只是复数加减法与旋转因子乘法 的次序有区别，两种方法的运算量是一样的。在基2算法中，每个蝶形运算单元都包括1次复数乘法、2 次复数加法。n （n= 2"）点序列的运算流图应有m级蝶形，每 一级都由n/2个蝶形运算组成，所以n点序列的基2fft算法， 总的运算量为斗呃“次复数乘法，nlog2n次复数加法。直接d

4、ft 运算量为矿次复数乘法、n（n-1）次复数加法。可见，fft算法 大大减少了运算量，当n越大时，fft算法的优越性越明显。基4、dif-fft（按频率抽取）n-lx伙) = 0(吨n=0n/4-1n/2-13n/4-1n-=z xwn + z + z + z x()wfn=0n=n 14n=n/2”=3n/4/v/4-1n/4-1n/4-1=工 x(n)wn + 工兀s + n/4)w：e + 工 xs + n/2)w+nn=0n=0n=0n/4-1+ 工 x( + 3n/4)wjgnn=0n/4-1=工 mn) + x(n + n /4)w/4 + x(n + n / 2)a，/2 +

5、x(h + 37v /4)wkn,4w ?»=0n/4-1x (4r)=为兀)+ 尢s + n / 4) + n / 2) + x(n + 3n / 4)w；/i=0n/4-1x(4r + 1)=工x()”( + n/4)-兀s + n/2) + jx(n+ 3/4)；4=0n/4-1x(4r + 2)=工x(/i)一x(n + n/4) + x(n + n/2) 兀 + 3n/4)w$”肖爲71=0n/4-1x(4r + 3)=工%(/?) + jxs + n/4) xa + n/2)-/xs + 3n/4)uw；4w=0令：xo(n) = x(n) + x(n + n / 4)

6、+ x(n + n / 2) + x(n + 3/v / 4)x(n) = x(n) 一 jx(n + n / 4) - x(n + n / 2) + jx(n + 3n /4)w, x2(n) = x(n) 一 x(n + n / 4) + 兀o + n / 2) -兀 + 3n / 4)网" x3(n) = x(n) + jx(n + n / 4) - x(n + n / 2) - jx(n + 3n /4)w："则有：n/4-1n/4-1x(4r)=工 xo(h)w；4,x(4r + l)=工 xi(h)w；% ”=0n/4-1n/4-1x(4r + 2)= x x2

7、(n)4,x(4r + 3)=工 xs(m)w；4fi=0n=0xoqi)xl(n)x20)x3("基4、 dif-fft 蝶形运算单元由上图可知每个基4蝶形运算单元包括3次复数乘法、8次复 数加法。n （n= 2j m为偶数）点序列的fft运算若采用基4算法则有m/2级蝶形，每级由n/4个蝶形运算构成。采用基4算法计算n点序列的fft共需要nog2n次复数乘法、n 鸥2 n次 o复数加法。由于主要的运算时间集中在乘法上面，可见基4算法 的运算量较基2算法减少了 25%,但运算量的减少是以硬件的复 杂性及使用更多资源为代价的。fft算法的fpga实现以8点（复数点，包括实部与虚部）、

8、基2、dif-fft为例来 考虑fft算法的fpga实现。整个运算流图应由3级蝶形构成, 每级中有4个蝶形运算。若dif的输入序列为顺序输入，则得到 倒序输出。完整的运算流图如下所示：x(0)*(4)x*(6)x(l)x(5)xxq)考虑采用流水线结构，系统可采用3级基2蝶形运算单元构成，系统总体结构如下所示：radix-2radix-2c 11总体结构框图旋转因子产生radix-2串并转换总体结构说明输入数据为串行的数据流，故在第一级蝶形运算模块前加入串并转换模块，将串行数据流转换为并行的两列数据流以适应基2蝶形运算模块的输入信号要求。由于每级蝶形运算一次处理的两个输入数据不能直接由前一 级

9、蝶形运算一次性输出，故在两个蝶形运算单元之间插入延时对 齐模块，将前一级蝶形运算的结果（两列并行的数据流）作适当 的延时并通过转接器对齐，形成后一级蝶形运算模块所需要的2 列输入序列。在最后一级蝶形运算后加入串并转换模块，将2列并行的数 据流合成为1列。最后加入倒序模块将dif-fft得到的倒序输出 序列整理为顺序输出。旋转因子产生模块产生各级基2蝶形运算所需的旋转因子。 由运算流图可以看出最后一级的旋转因子其实是1,故可省略最 后一级蝶形运算单元中的旋转因子乘法器。因此用一个双口 rom将两组数据分别输出到第一级和第二级的蝶形运算单元即 可。基2蝶形运算模块由两个复数加法器和一个复数乘法器构

10、成。 旋转因子由rom产生后，作为复数乘法器的输入之一，与前面 复数加法器得到的结果相乘完成一次蝶形运算。为提高系统的运 行速度可在蝶形运算单元中插入流水线寄存中间结果。若输入序列的标号为0、1、2、3、4、5、6、7,则在a、b、c、d、e处的信号标号如下图所示:a0、1、2、3、4、5、6、7n0、1、2、3d4、5、6、7厂0、1、4>5u2、3、6、7n0、2、4、6u1、3、5、7e0、1、2、3、4、5、6、7串并转换模块完成a序列到b序列的转换；两个延时对齐模 块分别完成b丿予列到c序列、c序列到d丿予列的转换；并串转 换模块完成d序列到e序列的转换。各模块框图串并转换模块

11、：串并转换模块可用单输入、双输出的ram来实现，同时控制 输入信号的时钟频率为输出信号时钟频率的两倍。这里要用到乒 乓操作，即读写操作分开，故8点序列要用到16个存储单元。 写入地址在写入时钟控制下按顺序递增。两个读出地址的最高位 都为写入地址最高位的求反结果。两个读出地址的次高位固定， 一个为0, 个为1,其它位在读出时钟的控制下递增。qaqb延时对齐模块：用单输入、单输出的ram,适当控制读、写地址可实现数据的延时，转接器可用数据选择器构成。以最后一个蝶形运算单元前的延时对齐模块为例，可由如下方案实现:延时lclk转接器延时lclk 转接器两种状态分别为两个输出端与输入端直接相连和交叉 相

12、连，控制转接器的状态每1个elk改变一次，即控制转接器的 状态持续时间与延时单元的延时时间相同。经过分析可知，若采 用相同的处理方式，则倒数第n个蝶型运算单元前的延时单元的 延时elk个数为2心个。延时单元可直接用ram实现，控制读写 地址z间的间隔即可实现输出与输入z间的延时。整个延时对齐 模块的连接图如下：ram_2port data15.o wraddress3.o wrenrdaddress3.o乏<工(s)pom 9lq 15.0x qaclockinst3 block type: autodata_a ”mux_2porta15.oi hn r niqa15-1.ocfjj

13、r 1 hl1 d 1 0. ujq。 i o i - ujselinst2k qbdata_b xdata15.o wraddress3.o wrenrdaddress3.01乏<工(s)pom 9lq 15.01clockinstblock type: auto旋转因子产生模块：用双口 rom产生旋转因子。按照各级蝶形运算模块中所需的 旋转因子的变化规律控制两个读出地址的变化，产生相应的旋转 因子到各级蝶形运算模块。address a4.01address b4.01clockinstrom_2portblock type: auto(spomcmx qo并串转换和倒序模块：先将用数

14、据选择器将两路数据合成为一路写入ram中，然后 从ram中读出数据，适当控制读地址可实现倒序序列的整序。 这里也要用到乒乓操作，读写操作分开。输出数据的时钟频率为 输入数据时钟频率的两倍，sei信号的变化频率与输出信号频率 相同。ram中用到的时钟信号是输出数据的时钟。控制ram 的写入地址按输出时钟递增，读出地址最高位为写入地址最高位 求反的结果。读出地址中的其它位按如下规则产生：若将余下的 地址位看成一个完整的地址，则最高位与写入地址最低位相同、 次高位与写入地址次低位相同、依此类推。基2蝶形运算模块：棊2蝶形运算单元中要完成两个复数加法和一个复数乘法。一个复数加法器可由两个实数加法器构成

15、。下图是基2蝶形运算 单元的结构图：a_re b_re+:加法器+qa_rea_imb_im+:加法器+:加法器+:加法器u-rtqb_re qb_im旋转因子复数乘法的运算为:r + = (x + )(c + js)= (x*c y *s) + ”x*s + y*c)x为输入信号的实部，y为输入信号的虚部，c为旋转因子 的实部，s为旋转因子的虚部，r为运算结果的实部，i为输出 结果的虚部。若按上述运算直接构成复数乘法器需4个实数乘法 器和3个实数加法器。考虑简化计算为：令：e = x-y, z 二 c*£ 二 c*(x-y)贝ij： r = (cs)*y + z/=(c + 5)*

16、x z与旋转因子有关的数据都可预先计算，即c、c+s、c-s可预 先计算存放在rom中。这样可将旋转因子乘法器简化为3个实 数乘法器和3个实数加法器。结构如下：+cc-sc+srxy对中间结果可用寄存器寄存以提高运算速度。fftfft,即为快速傅氏变换，是离散傅氏变换的快速算法，它是根 据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的 算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但 是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可 以说是进了一大步。设x(n)为n项的复数序列，由dft变换，任一 x (m)的计算 都需要n次复数乘法和n-1次复数加法，而一次复数乘法等于 四次实数乘法和两次实数加法，一次复数加法等于两次实数加 法，即使把一次复数乘法和一次复数加法定义成一次'运算”(四 次实数乘法和四次实数加法)，那么求出n项复数序列的x(m), 即n点dft变换大约就需要n2次运算。当n=1024点甚至更 多的时候，需要n2=1048576次运算，在fft中，利用wn的 周期性和对称性，把一个n项序列(设n=2k,k为正整数)，分 为两个n/2项的子序列，每个n/2点dft变换需要(