蝶式運算(butterfly computation) ，是一種在快速傅立葉變換中得到廣泛運用的運算方法。
基本介紹
- 中文名：蝶式運算
- 外文名：butterfly computation
- 套用學科：通信
定義,
定義
在快速傅立葉變換中，基2算法用得最普遍。通常按序列在時域或在頻域分解過程的不同，又可分為兩種：一種是時間抽取FFT算法（DIT），將N點DFT輸入序列x(n)、在時域分解成2個N/2點序列而x1(n)和x2(n)。前者是從原序列中按偶數序號抽取而成，而後者則按奇數序號抽取而成。DIT就是這樣有規律地按奇、偶次序逐次進行分解所構成的一種快速算法。其過程可表示為如圖1.
圖1
圖1則N點DFT可寫成為如圖2.
圖2
圖2式中，X1(k)和X2(k)分別是N/2點序列x1（n）和x2(n)的DFT，它們的周期都是N/2，即X1(k+N/2)=Xl(k);X2(k+N/2)=X2(k)。由於在高速專用器件出現以前，在實際運算中複數乘法花時較多，所以常以復乘次數的多少來估算速度的快慢。按直接計算N/2點DFT的復乘次數為(N/2)，故式①所需總的復乘次數為2×(N/2）+N/2=N(N/2+1)≈N/2。顯然，比不通過分解而直接計算N點DFT的復乘次數減少約一半。不難推出，若N是2的整數冪（N=2），則上述被分解後的N/2點序列還可以進一步分解成2個更短的N/4點序列，使復乘次數更進一步減少。依此類推，由於每分解一次降低一階冪次，所以總可以通過r次分解，最後變換成一系列2點DFT的組合，使復乘次數大大減少，運算速度隨之提高。
以N=2為例，第一次按序號(0，2，4，6)與（1，5，3，7)分解為2個4點DFT，然後又把4點DFT分別按序號（0，4)，(2，6)和（1，5)，(3，7)分解為4個2點DFT。為了直觀和便於進一步導出FFT電腦程式流程框圖，通常採用信號流圖表示特定的算法，見圖1。從圖中可見，8點DFT的計算共分三級：第一級是4個2點DFT；第二級是2個4點DFT(由2個2點DFT組成）；第三級是一個8點DFT(由2個4點DFT組成）。每一級的基本運算都是由四個形似蝴蝶的蝶形運算所組成。如圖2所示，每一蝶形運算的輸入是兩個複數數據a和b，運算結果的輸出是A和B，所以完成每一個蝶形運算只含有一個復乘和兩個復加。因而對於N=2點的DFT計算共分r級，每級有N/2個蝶形運算，故總共的復乘次數為如圖3.
圖3
圖3與直接算法相比，則得如圖4.
圖4
圖4當N=1024，α≈0．5%，這說明若直接計算DFT需要200秒，而採用FFT只需1秒。從圖1可見，FFT的基本運算單元是蝶形運算，當輸入存儲單元的每一對數據一旦進入計算單元，它們就不需保留。因而可以把通過蝶形運算輸出的一對數據，分別就地存儲在原來的存儲單元里，實現同址運算，大大減少計算機記憶體容量。FFT除了具有快速和節省設備外，該算法由於要求輸入數據按位序顛倒，即所謂反序排列。所以還存在將原按自然順序（正序）輸入的序列通過變址，即所謂整序過程進行重新排列。一般的規律是，輸入正序、輸出反序；輸入反序、輸出正序。
還有一種是頻率抽取FFT算法（DIF），將N點DFT輸出序列X（k），在頻域分解2個N/2點序列X（2k）和X(2k+1)。前者是從X(k)按偶數序號抽取而成，而後者則按奇次序號抽取而成。DIF就是這樣有規律地按奇、偶次序進行分解所構成的一種快速算法。圖3表示N=8按頻率抽取FFT算法的信號流圖。與按時間抽取FFT算法類似，它們之間存在對偶關係。該算法的基本運算也是蝶形運算，見圖2(b)，所以計算量一樣，也具有同址運算的優點和對輸入或輸出序列進行整序的特點。用單片高速信號處理器實現FFT常採用DIF算法。
換句話說，可以採用高基算法來實現。理論和實踐證明，基數越高總運算量越會減少，但算法與控制設備更加複雜。一般說來，基4和基8算法最有效，基2算法最便於實現。因此在實際中，基2算法仍獲得廣泛套用。倘若序列變換長度是任意的，但總可以通過適當補零使N=2。
分裂基算法(RSFFT) 1984年由P．杜哈美爾和H．赫爾曼等導出的一種比庫利圖基算法更加有效的改進算法，其基本思想是在變換式的偶部採用基2算法，在變換式的奇部採用基4算法。優點是具有相對簡單的結構，非常適用於實對稱數據，對長度N=2能獲得最少的運算量(乘法和加法），所以是選用固定基算法中的一種最佳折衷算法。
