串行fft遞歸算法(蝶式遞歸計算原理)求傅里葉變換

1、串行FFT遞歸算法（蝶式遞歸計算原理）求傅里葉變換摘要FFT，即為快速傅氏變換，是離散傅氏變換的快速算法，它是根據(jù)離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進獲得的。它對傅氏變換的理論并沒有新的發(fā)現(xiàn)，但是對于在計算機系統(tǒng)或者說數(shù)字系統(tǒng)中應(yīng)用離散傅立葉變換，可以說是進了一大步。設(shè)x(n)為N項的復(fù)數(shù)序列，由DFT變換，任一X（m）的計算都需要N次復(fù)數(shù)乘法和N1次復(fù)數(shù)加法，而一次復(fù)數(shù)乘法等于四次實數(shù)乘法和兩次實數(shù)加法，

2、一次復(fù)數(shù)加法等于兩次實數(shù)加法，即使把一次復(fù)數(shù)乘法和一次復(fù)數(shù)加法定義成一次“運算”（四次實數(shù)乘法和四次實數(shù)加法），那么求出N項復(fù)數(shù)序列的X（m）即N點DFT變換大約就需要N^2次運算。當N=1024點甚至更多的時候，需要N2=1048576次運算，在FFT中，利用WN的周期性和對稱性，把一個N項序列（設(shè)N=2kk為正整數(shù)），分為兩個N2項的子序列，每個N2點DFT變換需要（N2）^2次運算，再用N次運算把兩個N2點的DFT變換組合成一個N

3、點的DFT變換。這樣變換以后，總的運算次數(shù)就變成N2（N2）^2=NN^22。繼續(xù)上面的例子，N=1024時，總的運算次數(shù)就變成了525312次，節(jié)省了大約50%的運算量。而如果我們將這種“一分為二”的思想不斷進行下去，直到分成兩兩一組的DFT運算單元，那么N點的DFT變換就只需要Nlog(2)(N)次的運算，N在1024點時，運算量僅有10240次，是先前的直接算法的1%，點數(shù)越多，運算量的節(jié)約就越大，這就是FFT的優(yōu)越性。關(guān)鍵字：F

4、FT蝶式計算傅里葉變換1一題目及要求1.1題目對給定的，利用串行FFT遞歸算法（蝶式遞歸計算)232716830742221(????原理）計算其傅里葉變換的結(jié)果。1.2要求利用串行遞歸與蝶式遞歸原理，對給定的向量求解傅里葉變換的結(jié)果。二設(shè)計算法、算法原理2.1算法原理與設(shè)計蝶式遞歸計算原理：令為n2次單位元根，則有，將b向量的偶數(shù)項和奇數(shù)項分別記為和。注意推導(dǎo)中反復(fù)使用：。圖2.1公式圖形)2(2~nie??＝2~??＝Tnbbb).