先說(shuō)基2FFT和混合基FFT的概念。
設 N 是一個(gè)復合數，可分解為
N=r1r2…rL，若r1 = r2 = … = rL=2，就是基2FFT。若各個(gè)ri不相同，就稱(chēng)為混合基FFT。也就是說(shuō)，基2FFT可以看成混合基FFT的特例。下面以程佩青《數字信號處理（第四版）》為例進(jìn)行解釋。
教材234頁(yè)，圖4.23
這是N=30點(diǎn)的混合基FFT流圖。怎么看懂這幅如蜘蛛網(wǎng)一樣復雜的圖呢？
這里把30分成了5×2×3，所以是三列。三個(gè)基分別是5、2、3，所以每列分別是3點(diǎn)DFT、2點(diǎn)DFT和5點(diǎn)DFT。
最左邊一列，是10（即5×2）個(gè)3點(diǎn)DFT（注意圖中只畫(huà)出了兩個(gè)3點(diǎn)DFT，第一個(gè)是x(0)、x(10)、x(20)；第二個(gè)是x(4)、x(14)、x(24)）；
中間一列，是15（即5×3）個(gè)2點(diǎn)DFT；
最右邊一列，是6（即2×3）個(gè)5點(diǎn)DFT。
帶著(zhù)這種理解再來(lái)看基2算法，以DIT-FFT為例，如218頁(yè)圖4.5所示。如下圖。
這是N=8點(diǎn)的按時(shí)間抽?。―IT）FFT。N=8=2×2×2，所以是3列，每列都是2點(diǎn)DFT，并且每列都是4個(gè)2點(diǎn)DFT，但這個(gè)4，是由不同的2組合而來(lái)的（為了方便說(shuō)明，用不同的顏色表示）。第一列，是2×2個(gè)2點(diǎn)DFT；第二列，是2×2個(gè)2點(diǎn)DFT；第三列，是2×2個(gè)2點(diǎn)DFT。
所以說(shuō)，基2FFT是混合基FFT的特例，混合基FFT，無(wú)非是更為復雜的下標變換?；?FFT是實(shí)際中應用最為廣泛的FFT算法。
聯(lián)系客服
