蝶形、同址和變址計(jì)算方法及公式

1. 蝶形計(jì)算
任何一個(gè)N為2的整數(shù)冪(即N=2M)的DFT，都可以通過(guò)M次分解，最后成為2點(diǎn)的 DFT來(lái)計(jì)算。M次分解構(gòu)成了從x(n)到X(k)的M級(jí)迭代計(jì)算，每級(jí)由N/2個(gè)蝶形組成。圖3.20表示了蝶形的一般形式表示。
其輸入和輸出之間滿(mǎn)足下列關(guān)系：

大多數(shù)情況下復(fù)數(shù)乘法所花的時(shí)間最多，因此下面僅以復(fù)數(shù)乘法的計(jì)算次數(shù)為例來(lái)與直接計(jì)算進(jìn)行比較。
直接計(jì)算DFT需要的乘法次數(shù)為αD=N2，于是有例如，當(dāng)N=1024時(shí)，則： 205，即直接計(jì)算DFT所需復(fù)數(shù)乘法次數(shù)約為FFT的205倍。顯然，N越大，F(xiàn)FT的速度優(yōu)勢(shì)越大。

同址(原位)計(jì)算
圖3. 19包含log2N級(jí)迭代運(yùn)算，每級(jí)由N/2個(gè)蝶形計(jì)算構(gòu)成。蝶形計(jì)算的優(yōu)點(diǎn)是可以進(jìn)行所謂同址或原位計(jì)算。
現(xiàn)在來(lái)考察第一級(jí)的計(jì)算規(guī)律。設(shè)將輸入x(0)，x(4)，x(2)，x(6)， x(1)，x(5)，x(3)，x(7)分別存入計(jì)算機(jī)的存儲(chǔ)單元M(1), M(2), M(3),…，M(7)和M(8)中。首先，存儲(chǔ)單元M(1)和M(2)中的數(shù)據(jù)x(0)和x(4)進(jìn)入運(yùn)算器并進(jìn)行蝶形運(yùn)算，流圖中各蝶形的輸入量或輸出量是互不相重的，任何一個(gè)蝶形的二個(gè)輸入量經(jīng)蝶形運(yùn)算后，便失去了利用價(jià)值，不再需要保存。這樣，蝶形運(yùn)算后的結(jié)果便可以送到M(1)和M(2)存儲(chǔ)起來(lái)。類(lèi)似地，M(3)和M(4)中的x(2)和x(6)進(jìn)入運(yùn)算器進(jìn)行蝶形運(yùn)算后的結(jié)果也被送回 到M(3)和M(4)保存，等等。第二級(jí)運(yùn)算與第一級(jí)類(lèi)似，不過(guò)，M(1)和M(3)存儲(chǔ)單元中的數(shù) 據(jù)進(jìn)行蝶形運(yùn)算后的結(jié)果被送回M(1)和M(3)保存，M(2)和M(4)中的數(shù)據(jù)進(jìn)行蝶形運(yùn)算 后送回M(2)和M(4)保存，等等。這樣一直到最后一級(jí)的最后一個(gè)蝶形運(yùn)算完成。

蝶形運(yùn)算的特點(diǎn)是，首先每一個(gè)蝶形運(yùn)算都需要兩個(gè)輸入數(shù)據(jù)，計(jì)算結(jié)果也是兩個(gè)數(shù)據(jù)，與其它結(jié)點(diǎn)的數(shù)據(jù)無(wú)關(guān)，其它蝶形運(yùn)算也與這兩結(jié)點(diǎn)的數(shù)據(jù)無(wú)關(guān)、因此，一個(gè)蝶形 運(yùn)算一旦計(jì)算完畢，原輸入數(shù)據(jù)便失效了。這就意味著輸出數(shù)據(jù)可以立即使用原輸 人數(shù)據(jù)結(jié)點(diǎn)所占用的內(nèi)存。原來(lái)的數(shù)據(jù)也就消失了。輸出、輸人數(shù)據(jù)利用同一內(nèi)存單 元的這種蝶形計(jì)算稱(chēng)為同位(址)計(jì)算。
可以看出， 每一級(jí)的蝶形的輸入與輸出在運(yùn)算前后可以存儲(chǔ)在同一地址(原來(lái)位置上)的存儲(chǔ)單元中，這種同址運(yùn)算的優(yōu)點(diǎn)是可以節(jié)省存儲(chǔ)單元，從而降低對(duì)計(jì)算機(jī)存儲(chǔ)量的要求或降低硬件實(shí)現(xiàn)的成本。

3．變址計(jì)算
從圖3. 19所示的流程圖看出，同址計(jì)算要求輸入x(n)是“混序”排列的。所謂輸入為“混 序”，并不是說(shuō)輸入是雜亂無(wú)章的，實(shí)際上它是有規(guī)律的。如果輸入x(n)的序號(hào)用二進(jìn)制碼來(lái) 表示，就可以發(fā)現(xiàn)輸入的順序恰好是正序輸入的“碼位倒置”，表3. 3列出了這種規(guī)律。

在實(shí)際運(yùn)算中，按碼位倒置順序輸入數(shù)據(jù)x(n)，特別當(dāng)N較大時(shí)，是很不方便的。因此，數(shù)據(jù)總是按自然順序輸入存儲(chǔ)，然后通過(guò)“變址”運(yùn)算將自然順序轉(zhuǎn)換成碼位倒置順序存儲(chǔ)。實(shí)現(xiàn)這種轉(zhuǎn)換的程序可用圖3. 21來(lái)說(shuō)明。

圖中用n表示自然順序的標(biāo)號(hào)，用l表示碼位倒置的標(biāo)號(hào)。當(dāng)l=n時(shí)，x(n)和x(l)不必互相調(diào)換。當(dāng)l≠n時(shí)， 必須將x(l)和x(n)互相調(diào)換，但只能調(diào)換一次，為此必須規(guī)定每當(dāng)l>n時(shí)，要將x(l)和x(n)相互調(diào)換，即把原來(lái)存放x(n)的存儲(chǔ)單元中的數(shù)據(jù)調(diào)入存儲(chǔ)x(l)的存儲(chǔ)單元中，而把原來(lái)存儲(chǔ)x(l)的存儲(chǔ)單元中的數(shù)據(jù)調(diào)入到存儲(chǔ)x(n)的存儲(chǔ)單元中。
這樣，按自然序輸入的數(shù)據(jù)x(n)經(jīng)過(guò)變址計(jì)算后變成了碼位倒置的排列順序，便可進(jìn)入第一級(jí)的蝶形運(yùn)算。
最后介紹一下時(shí)間抽選FFT算法的另外一些形式的流程圖。對(duì)于任何流程圖，只要保持 各節(jié)點(diǎn)所連支路及其傳輸系數(shù)不變，則不論節(jié)點(diǎn)位置怎樣排列，所得到的流程圖總是等效的，因而都能得到DFT的正確結(jié)果，只是數(shù)據(jù)的提取和存儲(chǔ)次序不同而已。
把圖3. 19中與x(4)水平相鄰的所有節(jié)點(diǎn)和與x(1)水平相鄰的所有節(jié)點(diǎn)交換，把與x(6)水平相鄰的所有節(jié)點(diǎn)和與 x(3)水平相鄰的所有節(jié)點(diǎn)交換，而與x(2)、x(5)和x(7)水平相鄰各節(jié)點(diǎn)位置不變，就可以從圖3. 19得到圖3.22。圖3.22與圖3.19的區(qū)別只是節(jié)點(diǎn)的排列不同，而支路傳輸比，即WN的 各次冪保持不變。顯然圖3.22所示流程圖的輸入是正序(自然順序)排列的，輸出是碼位倒置 排列的，所以輸出要進(jìn)行變址計(jì)算。圖3. 22所示的流程圖相當(dāng)于最初由庫(kù)利和圖基給出的時(shí) 間抽選算法。

另一種形式的流程圖是將節(jié)點(diǎn)排列成輸入 和輸出兩者都是正序排列，但這類(lèi)流程圖不能進(jìn)行同址計(jì)算，因而需要兩列 長(zhǎng)度為N的復(fù)數(shù)存儲(chǔ)器。