16767dft的快速算法——fft-資料下載頁
2024-10-17 21:39本頁面
【導(dǎo)讀】介紹DFT的運(yùn)算特點(diǎn)，再具體討論高效算法。FIRDF的實(shí)現(xiàn)、線性卷積等。一個(gè)重要的原因是DFT有。nx有限長序列的DFT為。次復(fù)乘，有總的計(jì)算量有次復(fù)加。當(dāng)N較大時(shí)，所需的運(yùn)算量是很大的。如果要求實(shí)時(shí)處理，對運(yùn)算速度的要求將是十分苛刻的。N例如，當(dāng)，則。這么大量的復(fù)乘對運(yùn)算時(shí)間的要求就很高。特點(diǎn)及減少運(yùn)算量，提高運(yùn)算效率的方法。所以，每一次復(fù)乘實(shí)際是作了四次實(shí)乘，兩次實(shí)加。在定義時(shí)我們強(qiáng)調(diào)其隱含周期性，實(shí)質(zhì)是系。nkNW此外，除了具有周期性外，還具有對稱性。由以上推倒看到，利用周期性使原有7個(gè)系數(shù)，兩個(gè)系數(shù)，不難想象4點(diǎn)的DFT可以利用兩點(diǎn)DFT實(shí)現(xiàn)。事實(shí)正是如此，1965年，庫利-圖基首次提。逐次分解為較短序列的DFT運(yùn)算。次分解時(shí)間序列得到的，所以叫時(shí)間抽取法。因?yàn)镹是2的M次方，所以稱“基2”。
【正文】 本蝶形流圖中 Bpq ?? 。應(yīng)用同址計(jì)算，則第 級蝶形運(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以及上面的分析，可以歸納出時(shí)選 FFT的運(yùn)算 規(guī)律：第 L級每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)相距 同一旋轉(zhuǎn)因子對應(yīng)著間隔為 點(diǎn)； 點(diǎn)的 個(gè)蝶形。根據(jù)上 述規(guī)律，從輸入端（第一級）開始，逐級進(jìn)行，共作 M 級運(yùn)算。在作第 L級運(yùn)算時(shí)，依次求出個(gè)不同的旋轉(zhuǎn)因 子，每求出一個(gè)旋轉(zhuǎn)因子，就計(jì)算完它對應(yīng)的所有 個(gè)蝶形。這樣可以用三重循環(huán)實(shí)現(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圖說明。 起的，實(shí)際上的輸入是“倒序位”存儲(chǔ)。仍以 8點(diǎn)的 DFT流 列的，而是 。這是由時(shí)選法不斷 不是按這種自然順序排 序輸出。但我們注意到輸入的 正好順序放著 。因此可以直接按順 由時(shí)間抽取 FFT可見，當(dāng)全部 FFT完成后，存儲(chǔ)單元中 變址 在時(shí)序中將長點(diǎn)的 DFT（按奇、偶）分解為短點(diǎn) 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可以寫成一般表示 儲(chǔ)，然后再運(yùn)算。 實(shí)際運(yùn)算時(shí)，直接將輸入數(shù)據(jù)按碼位倒置的順序排好后 再輸入是很不方便的，所以總是先按自然順序輸入，經(jīng) 過變址運(yùn)算，將自然順序存儲(chǔ)轉(zhuǎn)換成碼位倒置次序存 變址 碼位倒置 應(yīng)存單元 — 碼位倒序 ??6A ??8A??5A??1A ??3A ? ?2A ? ?4A? ?7A? ?JA存儲(chǔ)單元 自然順序 — 自然順序 ? ?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時(shí) I 1,2,1 ?? NI ?J JIJI ? ? ??IA ? ?JAJI ?實(shí)現(xiàn)變址的程序流圖如圖 631所示，圖中虛框部分是實(shí) 現(xiàn)倒序的流程圖。 由圖可見，進(jìn)行變址的步驟： （ 3） （ 2）計(jì)算 （ 1）計(jì)算 則 則不變 比較 與 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