[科普中國(guó)]-同址計(jì)算

同址計(jì)算(Identical Address Operation)是FFT中的主要算法，因其在計(jì)算時(shí)總是用當(dāng)前層替代前一層,具有地址不變的關(guān)系而得名。也就是輸出數(shù)據(jù)使用原輸入數(shù)據(jù)結(jié)點(diǎn)所占用的內(nèi)存，輸出、輸入數(shù)據(jù)利用同一內(nèi)存單元的這種蝶形計(jì)算稱為同址計(jì)算，該算法在計(jì)算全部分析點(diǎn)數(shù)據(jù)時(shí)具有很高的效率。

算法描述為描述清楚起見，對(duì)右圖作一些約定：規(guī)定從左到右每一列為一層，用m(m=1,?,L)表示。節(jié)點(diǎn)所在行從上到下每一行為一個(gè)自然序號(hào)用k(k=0,?,N-1)表示，這樣節(jié)點(diǎn)就表示第m層的第k個(gè)節(jié)點(diǎn)，習(xí)慣上將第一列和最后一列的層下標(biāo)省去，分別表示為和。

“同址運(yùn)算”迭代算法是從第一層開始，以m層的各個(gè)節(jié)點(diǎn)Xm,k作為已知點(diǎn)，將(m+1)層的各個(gè)節(jié)點(diǎn)Xm+1,k迭代出來，直到算出最后一層為止，為了節(jié)省存儲(chǔ)空間，將已算得的對(duì)應(yīng)節(jié)點(diǎn)數(shù)據(jù)替換前一節(jié)點(diǎn)，對(duì)應(yīng)數(shù)據(jù)作為下一輪迭代的已知數(shù)據(jù)，“同址運(yùn)算”由此得名1。

算法優(yōu)點(diǎn)首先，該算法容易實(shí)現(xiàn)，利用旋轉(zhuǎn)因子中出現(xiàn)1處進(jìn)行基分解(split-radix)省去復(fù)數(shù)乘積而使DFT速度進(jìn)一步提高，該算法在計(jì)算全部譜線時(shí)效率很高。

其次，每一級(jí)的蝶形的輸入與輸出在運(yùn)算前后可以存儲(chǔ)在同一地址的存儲(chǔ)單元中，這種同址運(yùn)算的優(yōu)點(diǎn)是可以節(jié)省存儲(chǔ)單元，從而降低對(duì)計(jì)算機(jī)存儲(chǔ)量的要求或降低硬件實(shí)現(xiàn)的成本。

算法缺點(diǎn)雖然該算法在計(jì)算全部譜線時(shí)效率很高,但是在計(jì)算局部譜線時(shí)存在冗余。

分析FFT結(jié)果的特點(diǎn)可知X(k)與X(N-k)有如下關(guān)系：

上式表明對(duì)N點(diǎn)的FFT只要求出(0-N/2)點(diǎn),利用對(duì)偶規(guī)則可以得到另外一半,而不必算出全部點(diǎn)，因此存在冗余。

本詞條內(nèi)容貢獻(xiàn)者為:

李曉林 - 教授 - 西南大學(xué)