根據(jù)DFT的基二分解方法，可以發(fā)現(xiàn)在第L（L表示從左到右的運(yùn)算級(jí)數(shù)，L＝1，2，3…M）級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)相距B=2^(L-1)個(gè)點(diǎn)，同一旋轉(zhuǎn)因子對(duì)應(yīng)著間隔為2^L點(diǎn)的2^(M-L)個(gè)蝶形。從輸入端開始，逐級(jí)進(jìn)行，共進(jìn)行M級(jí)運(yùn)算。在進(jìn)行L級(jí)運(yùn)算時(shí)，依次求出個(gè)2^(L-1)不同的旋轉(zhuǎn)因子，每求出一個(gè)旋轉(zhuǎn)因子，就計(jì)算完它對(duì)應(yīng)的所有的2^(M-L)個(gè)蝶形。因此我們可以用三重循環(huán)程序?qū)崿F(xiàn)FFT變換。同一級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)本蝶形有用，而且每個(gè)蝶形的輸入、輸出數(shù)據(jù)節(jié)點(diǎn)又同在一條水平線上，所以輸出數(shù)據(jù)可以立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元。這種方法可稱為原址計(jì)算，可節(jié)省大量的存儲(chǔ)單元。附件包含算法流程圖和源程序。
標(biāo)簽：
DFT
分解方法
上傳時(shí)間：
2013-12-25
上傳用戶：qiao8960
