串行fft遞歸算法蝶式遞歸計算原理求傅里葉變換(編輯修改稿)
2025-07-23 03:16 本頁面
【文章內(nèi)容簡介】 ex *)。 /*復(fù)數(shù)加法*/void mul(plex,plex,plex *)。 /*復(fù)數(shù)乘法*/void sub(plex,plex,plex *)。 /*復(fù)數(shù)減法*/void divi(plex,plex,plex *)。 /*復(fù)數(shù)除法*/void output()。 /*輸出結(jié)果*/plex x[N],*W。 /*輸出序列的值*/intsize_x=0。 /*輸入序列的長度，只限2的N次方*/double PI。 //pi的值int main(){inti。system(cls)。PI=atan(1)*4。printf(Please input the size of x:\n)。 /*輸入序列的長度*/scanf(%d,amp。size_x)。printf(Please input the data in x[N]:(such as:5 6)\n)。for(i=0。isize_x。i++) /*輸入序列對應(yīng)的值*/scanf(%lf %lf,amp。x[i].real,amp。x[i].img)。initW()。 //計算W(0)~W(size_x1)的值fft()。 //利用fft快速算法進行DFT變化output()。 //順序輸出size_x個fft的結(jié)果return 0。} /*進行基2 FFT運算,蝶形算法。這個算法的思路就是，先把計算過程分為log(size_x)/log(2)1級（用i控制級數(shù)）；然后把每一級蝶形單元分組（用j控制組的第一個元素起始下標(biāo)）；最后算出某一級某一組每一個蝶形單元（用k控制個數(shù)，共l個）。*/voidfft(){inti=0,j=0,k=0,l=0。plexup,down,product。change()。 //實現(xiàn)對碼位的倒置for(i=0。ilog(size_x)/log(2)。i++) //循環(huán)算出fft的結(jié)果{l=1i。for(j=0。jsize_x。j+=2*l){for(k=0。kl。k++) //算出第i級內(nèi)j組蝶形單元的結(jié)果{ //算出j組中第k個蝶形單元mul(x[j+k+l],W[(size_x/2/l)*k],amp。product)。 /*size/2/l是該級W的相鄰上標(biāo)差，l是該級該組取的W總個數(shù)*/add(x[j+k],product,amp。up)。sub(x[j+k],product,amp。down)。x[j+k]=up。 //up為蝶形單元右上方的值x[j+k+l]=down。 //down為蝶形單元右下方的值}}}}void initW() //
外語相關(guān)推薦
鄂ICP備17016276號-1