《快速傅里葉變換(FFT)第四章》課件

本章主要內(nèi)容理解按時(shí)間抽選的基2FFT算法原理、運(yùn)算流圖、所需計(jì)算量和算法特點(diǎn)；理解按頻率抽選的基2FFT算法原理、運(yùn)算流圖、所需計(jì)算量和算法特點(diǎn)；理解IFFT算法；了解混合基、分裂基和基4FFT算法；理解用DFT的快速算法對(duì)信號(hào)進(jìn)行頻譜分析第4章離散傅里葉變換的計(jì)算與應(yīng)用本章主要內(nèi)容第4章離散傅里葉變換的計(jì)算與應(yīng)用DFT是信號(hào)分析與處理中的一種重要變換。但直接計(jì)算DFT的計(jì)算量與變換區(qū)間長(zhǎng)度N的平方成正比，當(dāng)N較大時(shí)，計(jì)算量太大，直接用DFT算法進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的。1965年發(fā)現(xiàn)了DFT的一種快速算法，使DFT的運(yùn)算效率提高1－2個(gè)數(shù)量級(jí)，為數(shù)字信號(hào)處理技術(shù)應(yīng)用于各種信號(hào)的實(shí)時(shí)處理創(chuàng)造了條件，推動(dòng)了數(shù)字處理技術(shù)的發(fā)展。1984年，提出了分裂基快速算法，使運(yùn)算效率進(jìn)一步提高；4.1離散傅里葉變換的高效計(jì)算思路DFT是信號(hào)分析與處理中的一種重要變換。但直接計(jì)算DFT的計(jì)4.1離散傅里葉變換的高效計(jì)算思路

直接計(jì)算DFT的運(yùn)算量長(zhǎng)度為N的有限長(zhǎng)序列x(n)的DFT為：考慮x(n)為復(fù)數(shù)序列的一般情況，對(duì)某一個(gè)k值，直接按上式計(jì)算X(k)值需要N次復(fù)數(shù)乘法、(N-1)次復(fù)數(shù)加法。4.1離散傅里葉變換的高效計(jì)算思路直接計(jì)算DFT的運(yùn)算4.1離散傅里葉變換的高效計(jì)算思路4.1離散傅里葉變換的高效計(jì)算思路4.1離散傅里葉變換的高效計(jì)算思路例N=1024，N2=1,048,5764.1離散傅里葉變換的高效計(jì)算思路例N=1024，N2=12、減少運(yùn)算量的思路和方法思路：N點(diǎn)DFT的復(fù)乘次數(shù)等于N2。把N點(diǎn)DFT分

解為幾個(gè)較短的DFT，可使乘法次數(shù)大大減少。另外，旋轉(zhuǎn)因子WmN具有周期性和對(duì)稱性。4.1離散傅里葉變換的高效計(jì)算思路3、FFT算法思想

不斷地把長(zhǎng)序列的DFT分解成幾個(gè)短序列的DFT，并利用旋轉(zhuǎn)因子的周期性和對(duì)稱性來減少DFT的運(yùn)算次數(shù)。2、減少運(yùn)算量的思路和方法4.1離散傅里葉變換的高效計(jì)算思方法：

分解N為較小值：把序列分解為幾個(gè)較短的序列，分別計(jì)算其DFT值；利用旋轉(zhuǎn)因子WNk的周期性、對(duì)稱性、可約性進(jìn)行合并、歸類處理，以減少DFT的運(yùn)算次數(shù)。

周期性：

對(duì)稱性：可約性：4.1離散傅里葉變換的高效計(jì)算思路方法：4.1離散傅里葉變換的高效計(jì)算思路

一、時(shí)域抽取法基2FFT基本原理FFT算法基本上分為兩大類：時(shí)域抽取法FFT(簡(jiǎn)稱DIT-FFT)和頻域抽取法FFT(簡(jiǎn)稱DIF―FFT)。1、時(shí)域抽取法FFT的算法思想：

將序列x(n)按n為奇、偶數(shù)分為x1(n)、x2(n)兩組序列；用2個(gè)N/2點(diǎn)DFT來完成一個(gè)N點(diǎn)DFT的計(jì)算。

4.2基2時(shí)間抽選的FFT算法一、時(shí)域抽取法基2FFT基本原理4.2基2時(shí)間抽選的

設(shè)序列x(n)的長(zhǎng)度為N，且滿足：(1)按n的奇偶把x(n)分解為兩個(gè)N/2點(diǎn)的子序列4.2基2時(shí)間抽選的FFT算法為自然數(shù)

設(shè)序列x(n)的長(zhǎng)度為N，且滿足：4.2基2(2)用N/2點(diǎn)X1(k)和X2(k)表示N點(diǎn)X(k)4.2基2時(shí)間抽選的FFT算法偶數(shù)奇數(shù)注意：這里k的取值范圍為0，1，…，N-1？(2)用N/2點(diǎn)X1(k)和X2(k)表示N點(diǎn)X(k)4.由于X1(k)和X2(k)均隱含周期為N/2，且

,X(k)又可表示為:

對(duì)上式的運(yùn)算用下圖所示的流圖符號(hào)來表示4.2基2時(shí)間抽選的FFT算法這樣將N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)的DFT由于X1(k)和X2(k)均隱含周期為N/2，且對(duì)上式的運(yùn)算用下圖所示的流圖符號(hào)來表示4.2基2時(shí)間抽選的FFT算法X1(k)X2(k)X1(k)+WNkX2(k)X1(k)WNkX2(k)WNk蝶形運(yùn)算圖-1例:X(0)=X1(0)+WN0X2(0)，X(1)=X1(1)+WN1X2(1)對(duì)上式的運(yùn)算用下圖所示的流圖符號(hào)來表示4.2基2時(shí)間抽選x(0)x(2)x(4)x(6)WN0X(0)WN1X(1)WN2X(2)WN3X(3)X1(0)X1(1)X1(2)X1(3)N/2點(diǎn)DFTX2(0)X2(1)X2(2)X2(3)N/2點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)x(1)x(3)x(5)x(7)x2(0)x2(1)x2(2)x2(3)X(4)-1X(5)-1X(6)-1X(7)-1N=8點(diǎn)的DIT-2FFT(時(shí)域抽取圖)一次分解圖x1x2x(0)x(2)x(4)x(6)WN0X(0)WN1X((3)第二次分解：

將x1(r)按r取奇、偶可分解成2個(gè)長(zhǎng)度為N/4的子序列x3(l)=x1(2l)、x4(l)=x1(2l+1)，根據(jù)上面推導(dǎo)可得：X1(k)=X3(k)+WN/2kX4(k)，k=0,1,…,N/2-1將x2(r)按r取奇、偶可分解成2個(gè)長(zhǎng)N/4的子序列x5(l)=x2(2l)，l=0,1,…，N/4x6(l)=x2(2l+1)；同理得4.2基2時(shí)間抽選的FFT算法l=0,1,…，N/4-1；X1(k+N/4)=X3(k)WN/2kX4(k)，k=0,1,…,N/4-1；X1(k)=X3(k)+WN/2kX4(k)，k=0,1,…,N/4-1；X2(k)=X5(k)+WN/2kX6(k)，k=0,1,…,N/4-1；X2(k+N/4)=X5(k)WN/2kX6(k),k=0,1,…,N/4-1；(3)第二次分解：4.2基2時(shí)間抽選的FFT算法l=0,X1(0)W40x3(0)x3(1)x4(0)x4(1)W80X(0)W81X(1)W82X(2)W83X(3)X(4)-1X(5)-1X(6)-1X3(0)X3(1)N/2點(diǎn)DFTX1(1)W41X(7)-1X1(2)-1X1(3)-1X4(0)X4(1)N/2點(diǎn)DFTx1(0)x1(2)x1(1)x1(3)N/2點(diǎn)DFTX2(0)X2(1)X2(2)X2(3)x5(0)x5(1)x6(0)x6(1)W40W41X5(0)X5(1)X6(0)X6(1)-1-1N/2點(diǎn)DFTx2(0)x2(2)x2(1)x2(3)x(0)=x(4)=x(2)=x(6)=x(1)=x(5)=x(3)=x(7)=N=8點(diǎn)DFT的二次時(shí)域抽取分解圖X1(0)W40x3(0)x3(1)x4(0)x4(1)W8x3(l)=x1(2l)x4(l)=x1(2l+1)4.2基2時(shí)間抽選的FFT算法l=0,1,…，N/4-1；以N=8為例，將k=0,1代入得x3(l)=x1(2l)4.2基2時(shí)間抽4.2基2時(shí)間抽選的FFT算法N=8點(diǎn)DIT-FFT運(yùn)算流圖X(5)x(0)x(4)x(2)x(6)x(1)x(5)x(3)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(6)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)WN/20WN/21WN/20WN/40x(7)WN/21L=1級(jí)L=2L=3X(7)X3(0)X1(0)WN/40WN/40WN/40-1-1-1-1-1-1-1-1-1-1-1-14.2基2時(shí)間抽選的FFT算法N=8點(diǎn)DIT-FFT運(yùn)算二、DIT―FFT算法與直接計(jì)算DFT運(yùn)算量的比較1、直接DFT運(yùn)算N點(diǎn)運(yùn)算：復(fù)數(shù)乘次數(shù)：N×N復(fù)數(shù)加次數(shù)：N×(N-1)2、用DIT-FFT作N點(diǎn)運(yùn)算：復(fù)數(shù)乘次數(shù)：M×N/2=N/2×log2N；復(fù)加次數(shù)：2×N/2×M=N×log2N?？梢奆FT大大減少了運(yùn)算次數(shù)，提高了運(yùn)算速度。4.2基2時(shí)間抽選的FFT算法整個(gè)運(yùn)算流圖中有M級(jí)蝶形，每一級(jí)中有N/2個(gè)蝶形，每個(gè)蝶形需一次復(fù)乘和兩次復(fù)數(shù)加運(yùn)算。二、DIT―FFT算法與直接計(jì)算DFT運(yùn)算量的比較4.24.2基2時(shí)間抽選的FFT算法1.蝶形運(yùn)算

序列經(jīng)過時(shí)域抽選后，存入數(shù)組中，如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，蝶形運(yùn)算可表示成如下形式：XL-1(k)XL-1(k+B)WNpp=J×2M-L，J=0,1,2,…,2L-1－1B=2L-1-1三、DIT―FFT的運(yùn)算特點(diǎn)及編程思想4.2基2時(shí)間抽選的FFT算法1.蝶形運(yùn)算XL-1(k)2.原位計(jì)算序列長(zhǎng)為N=2M點(diǎn)的FFT，有M級(jí)蝶形，每級(jí)有N/2個(gè)蝶形運(yùn)算。同一級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)本蝶形有用，每個(gè)蝶形的輸入、輸出數(shù)據(jù)節(jié)點(diǎn)在用一條水平線上。這樣，當(dāng)計(jì)算完一個(gè)蝶形后，所得的輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元。經(jīng)過M級(jí)運(yùn)算后，原來存放輸入序列數(shù)據(jù)的N個(gè)存儲(chǔ)單元中可依次存放X(k)的N個(gè)值。原位計(jì)算：利用同一存儲(chǔ)單元存儲(chǔ)蝶形計(jì)算輸入、輸出數(shù)據(jù)的方法。優(yōu)點(diǎn)：節(jié)約存儲(chǔ)空間、降低設(shè)備成本。4.2基2時(shí)間抽選的FFT算法2.原位計(jì)算4.2基2時(shí)間抽選的FFT算法3.旋轉(zhuǎn)因子和運(yùn)算級(jí)數(shù)的關(guān)系N點(diǎn)DIT―FFT運(yùn)算流圖中，每個(gè)蝶形都要乘以旋轉(zhuǎn)因子WpN，p稱為旋轉(zhuǎn)因子的指數(shù)。N＝8＝23時(shí)各級(jí)的旋轉(zhuǎn)因子第一級(jí)：L=1，有1個(gè)旋轉(zhuǎn)因子：WNp=WN/4J=W2LJJ=0第二級(jí)：L=2，有2個(gè)旋轉(zhuǎn)因子：WNp=WN/2J=W2LJJ=0,1第三級(jí)：L=3，有4個(gè)旋轉(zhuǎn)因子：WNp=WNJ=W2LJJ=0,1,2,3對(duì)于N＝2M的一般情況，第L級(jí)共有2L-1個(gè)不同的旋轉(zhuǎn)因子：

WNp=W2LJJ=0,1,2,…,2L-1－12L=2LM2M=N2LM故：

按照上面兩式可以確定第L級(jí)運(yùn)算的旋轉(zhuǎn)因子。4.2基2時(shí)間抽選的FFT算法JJ2M-LWNp=W2LJ=WN2L-M=WNp=J×2M-L，J=0,1,2,…,2L-1－13.旋轉(zhuǎn)因子和運(yùn)算級(jí)數(shù)的關(guān)系4.2基2時(shí)間抽選的FFT算同一級(jí)中，同一旋轉(zhuǎn)因子對(duì)應(yīng)蝶形數(shù)目第L級(jí)FFT運(yùn)算中，同一旋轉(zhuǎn)因子用在2M-L個(gè)蝶形中；同一級(jí)中，蝶形運(yùn)算使用相同旋轉(zhuǎn)因子之間相隔的“距離”第L級(jí)中，蝶距：D=2L。4.2基2時(shí)間抽選的FFT算法同一級(jí)中，同一旋轉(zhuǎn)因子對(duì)應(yīng)蝶形數(shù)目4.2基2時(shí)間抽選的F4.序列的倒序

N=2M，用M位二進(jìn)制數(shù)(nM-1nM-2…n1n0)2表示序列的序號(hào)n.

M次偶奇時(shí)域抽選過程為：對(duì)最低位按0、1分為偶、奇兩組，次低位也按0、1分組，依此類推，M次分解后形成倒序圖為：4.2基2時(shí)間抽選的FFT算法二進(jìn)制數(shù)(N=8)分解倒序圖10041015110611170000001101020113倒序前00111015011311170000100401021106倒序后可見，只要將順序數(shù)的二進(jìn)制位倒置可得到對(duì)應(yīng)的二進(jìn)制倒序值。10n20101n100010n0111(n2n1n0)24.序列的倒序4.2基2時(shí)間抽選的FFT算法二進(jìn)制數(shù)(思考題：已知N=16點(diǎn)，在DIT-FFT運(yùn)算中，序數(shù)為2的二進(jìn)制數(shù)經(jīng)倒序后為多少?4.2基2時(shí)間抽選的FFT算法順序數(shù)增加1，是在順序數(shù)的二進(jìn)制數(shù)的最低位加1，向左進(jìn)位到序數(shù)是在M位二進(jìn)制數(shù)的最高位加1，向右進(jìn)位(0010->0100)順序和倒序二進(jìn)制數(shù)對(duì)照表思考題：已知N=16點(diǎn)，在DIT-FFT運(yùn)算中，序數(shù)為2的二

N=2M，用M位二進(jìn)制數(shù)表示，則從左至右的十進(jìn)制權(quán)值為：N/2、N/4、N/8,…、2,1

對(duì)倒序數(shù)J，其下一個(gè)序數(shù)是在該序數(shù)J的二進(jìn)制首位碼加1，相當(dāng)于十進(jìn)制運(yùn)算J+N/2。計(jì)算機(jī)上倒序數(shù)的實(shí)現(xiàn)過程為：4.2基2時(shí)間抽選的FFT算法J>N/2？J>N/4輸入當(dāng)前倒序數(shù)十進(jìn)制數(shù)值JNYNYJ>N/2MNY結(jié)束J=J-N/2倒序數(shù)的十進(jìn)制運(yùn)算規(guī)律N=2M，用M位二進(jìn)制數(shù)表示，則從左至右的十進(jìn)制權(quán)值為：倒序程序框圖為了實(shí)現(xiàn)原位運(yùn)算，以節(jié)約存貯空間，提高運(yùn)算速率。在倒序數(shù)J形成后，需將原存儲(chǔ)器中存放的輸入序列重新排列。下面先分析N=8點(diǎn)的倒序規(guī)律。

4.2基2時(shí)間抽選的FFT算法x(0)A(0)x(1)A(1)x(2)A(2)x(3)A(3)x(4)A(4)x(5)A(5)x(6)A(6)x(7)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)輸入序列數(shù)組分析上圖N=8點(diǎn)倒序規(guī)律，順序數(shù)I與倒序數(shù)J存在關(guān)系：

I=J時(shí)，不交換；I<J時(shí)，交換存儲(chǔ)器內(nèi)容。I>J時(shí)，不交換，直接更新序數(shù)值；IJx(0)x(2)x(4)x(1)x(5)x(6)x(3)x(7)倒序程序框圖4.2基2時(shí)間抽選的FFT算法x(0)x(1計(jì)算倒序值交換數(shù)組中的數(shù)據(jù)不交換數(shù)據(jù)，避免再次調(diào)換前面調(diào)換過的一對(duì)數(shù)據(jù)，計(jì)算下一個(gè)倒數(shù)值。計(jì)算倒序值交換數(shù)組中的數(shù)據(jù)不交換數(shù)據(jù)，避免再次調(diào)換前面調(diào)換過6.DIT-FFT程序框圖根據(jù)DIT-FFT原理和過程，DIT-FFT的完整程序框圖包括以下幾部分：(1)倒序:輸入自然順序序列x(n)，根據(jù)倒序規(guī)律，進(jìn)行倒序處理；(2)循環(huán)層1:確定運(yùn)算的級(jí)數(shù)，L=1M(N=2M)；確定一蝶形兩輸入數(shù)據(jù)距離B=2L-1(3)循環(huán)層2:確定L級(jí)的(B=)2L-1個(gè)旋轉(zhuǎn)因子；旋轉(zhuǎn)因子指數(shù)p=2M-LJ，J=0B-1；(4)循環(huán)層3:對(duì)于同一旋轉(zhuǎn)因子，用于同一級(jí)2M-L個(gè)蝶形運(yùn)算中：k的取值從J到N-1，步長(zhǎng)為2L(使用同一旋轉(zhuǎn)因子的蝶形相距的距離)

(5)完成一個(gè)蝶形運(yùn)算。6.DIT-FFT程序框圖4.2.4DIT-FFT的其他形式流圖W40W40W40W40W40W40W40W40W40W40W40W40X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)按時(shí)間抽選，輸入自然序，輸出倒位序的FFT流圖4.2.4DIT-FFT的其他形式流圖W40W40W4DIT-FFT的其他形式流圖按時(shí)間抽選，輸入和輸出都是自然序的FFT流圖W80W81W82W83X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1WN0WN0WN2WN2-1-1-1-1WN0WN0WN0WN0x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)-1-1-1-1DIT-FFT的其他形式流圖按時(shí)間抽選，輸入和輸出都是自然序DIT-FFT的其他形式流圖按時(shí)間抽選,各級(jí)具有相同幾何形狀的FFT流圖WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1WN0WN0WN2WN2-1-1-1-1WN0WN0WN0WN0x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)-1-1-1-1DIT-FFT的其他形式流圖按時(shí)間抽選,各級(jí)具有相同幾何形狀在基2快速算法中，頻域抽取法FFT也是一種常用的快速算法。1、算法思想和運(yùn)算過程設(shè)序列x(n)長(zhǎng)度為N=2M，將序列x(n)前后對(duì)半分為x1(n)、x2(n)兩組序列，用2個(gè)N/2點(diǎn)DFT來完成一個(gè)N點(diǎn)DFT的計(jì)算。4.3按頻率抽取的基-2FFT算法nk=偶數(shù)

,k=奇數(shù)

在基2快速算法中，頻域抽取法FFT也是一種常用的4.3按頻率抽取的基-2FFT算法將X(k)分解成偶數(shù)組與奇數(shù)組，當(dāng)k取偶數(shù)(k=2r,r=0,1,…,N/2-1)時(shí)當(dāng)k取奇數(shù)(k=2r+1,r=0,1,…,N/2-1)時(shí)：將x1(n)和x2(n)分別代入上式，可得x1(n)x2(n)表明：X(k)按奇偶k值分為兩組:偶數(shù)組是x1(n)的N/2點(diǎn)DFT奇數(shù)組是x2(n)的N/2點(diǎn)DFTr=0,1,…,N/2-14.3按頻率抽取的基-2FFT算法將X(k)分解成偶數(shù)組那么對(duì)序列x1(n)、x2(n)和x(n)可用蝶形運(yùn)算符號(hào)表示4.3按頻率抽取的基-2FFT算法x(n)x1(n)=x(n)+x(n+N/2)x2(n)=[x(n)x(n+N/2)]WNnx(n+N/2)DIF-FFT蝶形運(yùn)算流圖符號(hào)WNk-1那么對(duì)序列x1(n)、x2(n)和x(n)可用蝶形運(yùn)算符號(hào)4.3按頻率抽取的基-2FFT算法N=8時(shí)第1次分解的運(yùn)算流圖x(0)x(1)x(2)x(3)WN0X(0)WN1X(2)WN2X(4)WN3X(6)N/2點(diǎn)DFTN/2點(diǎn)DFTx(4)x(5)x(6)x(7)X(1)-1X(3)-1X(5)-1X(7)-14.3按頻率抽取的基-2FFT算法N=8時(shí)第1次分解的運(yùn)N=2M，N/2仍是偶數(shù)，繼續(xù)將N/2點(diǎn)進(jìn)行分解。將輸入序列x1(n)、x2(n)分別按前、后對(duì)半分解成4個(gè)長(zhǎng)N/4的子序列,其n=0,1,…，N/4-14.3按頻率抽取的基-2FFT算法｛x3(n)=x1(n)+x1(n+N/4)

x4(n)=[x1(n)-x1(n+N/4)]WN/2n

x5(n)=x2(n)+x2(n+N/4)

x6(n)=[x2(n)-x2(n+N/4)]WN/2n｛DIF―FFT二次分解運(yùn)算流圖(N=8)

X(0)X(4)X(2)X(6)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0N/4點(diǎn)DFTN/4點(diǎn)DFTWN0WN1WN2WN3X(1)X(5)X(3)X(7)WN2WN0WN2N/4點(diǎn)DFTN/4點(diǎn)DFT-1-1-1-1-1-1-1-1N=2M，N/2仍是偶數(shù)，繼續(xù)將N/2點(diǎn)進(jìn)行分解。將輸入序列DIF―FFT運(yùn)算流圖(N=8)4.3按頻率抽取的基-2FFT算法X(0)X(4)X(2)X(6)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0WN0WN1WN2WN3X(1)X(5)X(3)X(7)WN2WN0WN2-1-1-1-1-1-1-1-1-1-1-1-1WN0WN0WN0WN0DIF―FFT運(yùn)算流圖(N=8)4.3按頻率抽取的基-22、DIF-FFT運(yùn)算規(guī)律

DIF-FFT算法也可采用原位計(jì)算；N=2M時(shí)，共有M級(jí)運(yùn)算，每級(jí)共有N/2個(gè)蝶形，DIT與DIF算法的運(yùn)算次數(shù)相同。DIT與DIF不同的是：

DIF-FFT算法輸入序列為自然序列，輸出為倒序序列。因此，在M級(jí)運(yùn)算完成后，需對(duì)輸出數(shù)據(jù)進(jìn)行倒序才能得到自然順序的X(k)。

蝶形運(yùn)算符號(hào)不同：DIT-FFT蝶形是先相乘，后加/減；而DIF-FFT蝶形是先加/減，后相乘。4.3

按頻率抽取的基-2FFT算法x(n)x1(n)=x(n)+x(n+N/2)x2(n)=[x(n)x(n+N/2)]WNnx(n+N/2)DIF-FFT蝶形運(yùn)算流圖符號(hào)WNk-12、DIF-FFT運(yùn)算規(guī)律4.3按頻率抽取的基-2FFT3、其它形式的DIT-FFT運(yùn)算流圖

通過改變輸入/輸出節(jié)點(diǎn),中間節(jié)點(diǎn)的排列順序,可以得到不同變形的FFT運(yùn)算流圖。因此，前面介紹的DIT-FFT和DIF-FFT運(yùn)算流圖都不是唯一的。

4.3按頻率抽取的基-2FFT算法輸出序列輸入序列DIT-FFT的一種變形運(yùn)算流圖（輸入順序，輸出倒序）X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)X3(0)X5(0)X4(0)X6(0)X3(1)X5(1)X4(1)X6(1)WN0x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0WN0WN0WN2WN1WN3X1(0)X2(0)X1(2)X2(2)X1(1)X2(1)X1(3)X2(3)WN0WN0WN0WN2WN23、其它形式的DIT-FFT運(yùn)算流圖4.3按頻率抽取的基用同樣的方法可得DIT-FFT的另外一種變形運(yùn)算流圖，輸入和輸出均為順序排列，但不能采用原位計(jì)算。4.3按頻率抽取的基-2FFT算法DIT―FFT的一種變形運(yùn)算流圖用同樣的方法可得DIT-FFT的另外一種變形運(yùn)算流圖一、IDFT的高效算法1．DFT和IDFT的公式比較上述FFT算法流圖也可以用于離散傅里葉逆變換IDFT根據(jù)運(yùn)算公式可以看出，只需將DFT的系數(shù)WNkn變?yōu)閃N-kn，最后結(jié)果乘以1/N，就是IDFT的運(yùn)算公式。4.4傅里反葉變換（IDFT）的快速計(jì)算方法[X(k)]n一、IDFT的高效算法4.4傅里反葉變換（IDFT）2．用FFT流圖實(shí)現(xiàn)IDFT快速算法將DIT-FFT或DIF-FFT蝶形運(yùn)算流圖中旋轉(zhuǎn)因子WNp改為WN-p在IDFT快速算法的最后結(jié)果輸出前，乘以1/N常數(shù)；如要防止溢出，可在每一級(jí)運(yùn)算中，輸出支路分別乘以1/2，實(shí)現(xiàn)系數(shù)分級(jí)分擔(dān)。在IDFT快速算法中，輸入序列為X(k)，而輸出序列為x(n)。節(jié)點(diǎn)對(duì)應(yīng)關(guān)系：DIT-FFT對(duì)應(yīng)DIF-IFFTDIF-FFT對(duì)應(yīng)DIT-IFFT4.4傅里反葉變換（IDFT）的快速計(jì)算方法2．用FFT流圖實(shí)現(xiàn)IDFT快速算法4.4傅里反葉變換4.4傅里反葉變換（IDFT）的快速計(jì)算方法DIT―IFFT運(yùn)算流圖4.4傅里反葉變換（IDFT）的快速計(jì)算方法DIT―IF4.4傅里反葉變換（IDFT）的快速計(jì)算方法DIT―IFFT運(yùn)算流圖(防止溢出)4.4傅里反葉變換（IDFT）的快速計(jì)算方法DIT―IF3、直接調(diào)用FFT程序?qū)崿F(xiàn)IFFT的計(jì)算

對(duì)FFT流程作一些修改后，調(diào)用FFT程序?qū)崿F(xiàn)IFFT的快速計(jì)算。具體實(shí)現(xiàn)方法：先將X(k)取共軛，得到X*(k)；直接調(diào)用FFT子程序計(jì)算出DFT[X*(k)]的值；對(duì)輸出序列取共軛，并乘以1/N常數(shù)。雖然2次用了取共軛運(yùn)算，但可以和FFT共用一個(gè)子程序，實(shí)現(xiàn)方便。4.4傅里反葉變換（IDFT）的快速計(jì)算方法｛｝*3、直接調(diào)用FFT程序?qū)崿F(xiàn)IFFT的計(jì)算4.4傅里反葉變4.8.1兩個(gè)長(zhǎng)度相同的實(shí)序列

可以將兩個(gè)長(zhǎng)度相同的實(shí)序列組合成一個(gè)復(fù)序列來