16767dft的快速算法——fft-資料下載頁
2025-10-08 21:39本頁面
【導(dǎo)讀】介紹DFT的運(yùn)算特點，再具體討論高效算法。FIRDF的實現(xiàn)、線性卷積等。一個重要的原因是DFT有。nx有限長序列的DFT為。次復(fù)乘，有總的計算量有次復(fù)加。當(dāng)N較大時，所需的運(yùn)算量是很大的。如果要求實時處理，對運(yùn)算速度的要求將是十分苛刻的。N例如，當(dāng)，則。這么大量的復(fù)乘對運(yùn)算時間的要求就很高。特點及減少運(yùn)算量，提高運(yùn)算效率的方法。所以，每一次復(fù)乘實際是作了四次實乘，兩次實加。在定義時我們強(qiáng)調(diào)其隱含周期性，實質(zhì)是系。nkNW此外，除了具有周期性外，還具有對稱性。由以上推倒看到，利用周期性使原有7個系數(shù)，兩個系數(shù)，不難想象4點的DFT可以利用兩點DFT實現(xiàn)。事實正是如此，1965年，庫利-圖基首次提。逐次分解為較短序列的DFT運(yùn)算。次分解時間序列得到的，所以叫時間抽取法。因為N是2的M次方，所以稱“基2”。
【正文】 本蝶形流圖中 Bpq ?? 。應(yīng)用同址計算，則第 級蝶形運(yùn)算輸出 表示 的一般情況，第 L級的旋轉(zhuǎn)因子為 ? ? ? ? ? ? rNLLL WBpXpXpX ??? ?? 11? ? ? ? ? ? ? ? rNLLLL WBpXpXBpXqX ????? ?? 11 LMpr ??? 212,2,1,0 1 ?? ?Lp ?ML ,2,1 ??12 ?? LB式中， 12 ?? LBL2 LM?2LM?2從圖 626以及上面的分析，可以歸納出時選 FFT的運(yùn)算 規(guī)律：第 L級每個蝶形的兩個輸入數(shù)據(jù)相距 同一旋轉(zhuǎn)因子對應(yīng)著間隔為 點； 點的 個蝶形。根據(jù)上 述規(guī)律，從輸入端（第一級）開始，逐級進(jìn)行，共作 M 級運(yùn)算。在作第 L級運(yùn)算時，依次求出個不同的旋轉(zhuǎn)因 子，每求出一個旋轉(zhuǎn)因子，就計算完它對應(yīng)的所有 個蝶形。這樣可以用三重循環(huán)實現(xiàn) FFT運(yùn)算。程序流圖 如圖 628所示。 ? ? Mnx ,輸入倒 序 輸 出 結(jié)束 MN 2?ML ,1?12 ?? LB1,0 ?? BpLMr ?? 2LNpk 2,1, ??? ? ? ? ? ?? ? ? ? ? ? rNrNWBkXkXBkXWBkXkXkX???????開始 （ 1） （ 1） ? ? ? ? ? ?1,1,0 ?NXXX ?? ?nx? ? ? ? ? ? ? ?1,2,4,0 ?Nxxxx ?32?N圖說明。 起的，實際上的輸入是“倒序位”存儲。仍以 8點的 DFT流 列的，而是 。這是由時選法不斷 不是按這種自然順序排 序輸出。但我們注意到輸入的 正好順序放著 。因此可以直接按順 由時間抽取 FFT可見，當(dāng)全部 FFT完成后，存儲單元中 變址 在時序中將長點的 DFT（按奇、偶）分解為短點 DFT引 要用三位二進(jìn)制碼標(biāo)明數(shù)列的次序。 ? ? ? ? 210 0000 xx ? ? ? ? ? 210 0 0 11 xx ?? ? ? ? 210 0102 xx ?? ? ? ? 210 0 1 13 xx ?? ? ? ? 210 1 0 04 xx ? ? ? ? ? 210 1 0 15 xx ?? ? ? ? 210 1 1 06 xx ? ? ? ? ? 210 1 1 17 xx ?? ?012 nnnx1 1 0 0 1n1 1 1 1 0 0 0 0 2n1 0n0 ? ? ? ?01210 nnnxnx ?? ?2020x? ?2020x? ?2020x? ?2020x? ?2100x? ?2101x? ?2110x? ?2111x? ?2020x? ?2020x? ?2020x? ?2020x? ?2100x? ?2101x? ?2110x? ?2111x可以寫成一般表示 儲，然后再運(yùn)算。 實際運(yùn)算時，直接將輸入數(shù)據(jù)按碼位倒置的順序排好后 再輸入是很不方便的，所以總是先按自然順序輸入，經(jīng) 過變址運(yùn)算，將自然順序存儲轉(zhuǎn)換成碼位倒置次序存 變址 碼位倒置 應(yīng)存單元 — 碼位倒序 ??6A ??8A??5A??1A ??3A ? ?2A ? ?4A? ?7A? ?JA存儲單元 自然順序 — 自然順序 ? ?IA??0x ? ?4x ??6x??1x ??3x? ?2x ??5x ??7x??0x ? ?4x ??6x ??1x ??3x? ?2x ??5x ??7x??6A ??8A??5A??1A ??3A? ?2A ? ?4A ? ?7A例 N=8時 I 1,2,1 ?? NI ?J JIJI ? ? ??IA ? ?JAJI ?實現(xiàn)變址的程序流圖如圖 631所示，圖中虛框部分是實 現(xiàn)倒序的流程圖。 由圖可見，進(jìn)行變址的步驟： （ 3） （ 2）計算 （ 1）計算 則 則不變 比較 與 Yes Yes NO NO (1) 2NVk ?Jk? 2kk kJJ ? ??kJJ ??1NMI ?(1) Yes NO 輸入 01??IJ1??JIJI ?? ?? ? ? ?? ? TIAIAJAJAT???11 22 ??? NNM NNV變址流圖：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1