【正文】 處理很不經(jīng)濟(jì) ， 因此 ， 如果要求求準(zhǔn)確的 N點(diǎn) DFT值 ,可采用任意基數(shù)的 FFT算法 ,但其運(yùn)算效率低于以 2為基數(shù)的 FFT算法 。 任意基數(shù)的 FFT算法的基本思想仍是把一個(gè)大 N點(diǎn)的 FFT盡量分解為小點(diǎn)數(shù)的 FFT。 Chirpz變換 （簡稱 CZT) 采用 FFT可以算出全部 N點(diǎn) DFT值 ， 而 DFT值是 Z變換X(z)在 Z平面單位圓上的等間隔取樣值 ， 但有些情況下不需要求出全部的 DFT值 。 ② 語音信號處理中 ， 需要知道 Z變換的極點(diǎn)所在的復(fù)頻率位置 ， 即共振峰的位置 。 ③ 當(dāng) N是素?cái)?shù)時(shí) ， 不能采用任意基數(shù)的 FFT算法 。 螺線采樣是FFT的另外一種快速算法 ， 它是沿著一條螺旋線的采樣 。令采樣點(diǎn) zk=AWk ， k=0,… ,M1， M為采樣點(diǎn)數(shù) ， ???????? 00??jojoeWWeAAA0 表示起始取樣點(diǎn)的 半徑長度，通常 A0≤1 θ 0表示起始取樣點(diǎn)的相角 φ 0表示兩相鄰點(diǎn)之間的等分角 A、 W為任意復(fù)數(shù)，其中： W0 表示螺旋線的伸展率 ， 則隨 K的增大螺線外伸 ， 則螺線內(nèi)縮 (反時(shí)針 )， W0=1表示半徑為 A0的一段圓弧 ,若 A0=1表示這段圓弧是單位圓的一部分 。 Z變換在采樣點(diǎn) zk上的值為： 10( ) ( )Nn nknkX z x n A W???? ?])([21 222 nknknk ????2222)(1022 )()(nkNnnnkk WWAnxWzX???????zk=AWk 22( ) ( ) , ( )nnng n x n A W h n W??? －令： 22120210 , 1 , ,( ) ( ) ( )( ) ( )k NknkMkX z W g n h k nW g k h k?????????則 上式說明，如對信號 x(n)先進(jìn)行一次加權(quán)處理，加權(quán)系數(shù)為 ，然后通過一個(gè)單位脈沖響應(yīng)為h(n)的線性系統(tǒng)，最后對該系統(tǒng)的前 M點(diǎn)輸出再作一次 加權(quán)，就可得到全部 M點(diǎn)的螺旋線采樣值 。 22)(nWnh ??二 .CZT的算法實(shí)現(xiàn) 輸入信號 是有限長序列，長度為 N， 22( ) ( ) nng n x n A W??但 是無限長序列 ,而計(jì)算 0～ M1點(diǎn)卷積中h(n)取值只需要 n=(N1)～ M1那一部分的值 。所以 ， 把 Chirpz變換可以看成兩個(gè)有限長序列的線性卷積 。 h(n)的主值序列 可由 h(n)作周期延拓后取 0≤n≤L 1部分值獲得 ， 將 與 g(n)作圓周卷積后 ， 其輸出的 前 M個(gè)值 就是 Chirpz變換的 M個(gè)值 。 22)(nWnh ??)(nh)(nh( ) ( )g k h k?Chirpz變換的計(jì)算步驟： (1)求 h(n)的主值序列 (2)求 的 L點(diǎn)的 FFT: H(k)=FFT[ ] (3) 對 x(n)加權(quán)并補(bǔ)零 22/2( ) / 21110() nLnML N LWnnh ????? ? ??? ????????)(nh )(nh(4) G(k)= FFT[g(n)] , L點(diǎn) (5) Y(k)= G(k)H(k), L點(diǎn) (6) y(n)= IFFT[Y(k)] , L點(diǎn) (7) , 0≤k≤M 1 1010)()( 2/2?????????? ?LnNNnWAnxng nn22( ) ( )kkX z W y k? 利用 FFT計(jì)算 Chirpz變換 Chirpz變換的特點(diǎn)： 1）輸入序列長度 N與輸出序列長度 M不需要相等； 2） N及 M不必是高度復(fù)合數(shù)，二者均可為素?cái)?shù)； 3）相鄰采樣點(diǎn) zk之間的角間隔 φ 0是任意的，即頻 率分辨率是任意的； 4）圍線是任意的，不必是 Z平面上的圓； 5）起始點(diǎn) z0可任意選定，即可從任意頻率上開始 對輸入數(shù)據(jù)進(jìn)行窄帶高分辨率分析； 6）若 A=1, M=N , ,可用 Chirpz變換 計(jì)算 DFT（即使 N為素?cái)?shù)）。 線性卷積的 FFT算法 線性卷積是求離散系統(tǒng)響應(yīng)的主要方法之一 ,許多重要應(yīng)用都建立在這一理論基礎(chǔ)上 。計(jì)算表明 , L32時(shí) , 上述計(jì)算線 性卷積的方法比直接計(jì)算線卷積有明顯的優(yōu)越性。 上述方法適用于 x(n)、 h(n)兩序列長度比較接近或相等的情況。 為了保持快速卷積法的優(yōu)越性 ,可將 x(n)分為許多段 ,每段的長度與 h(n)接近 , 處理方法有兩種： (1)重疊相加法 (2)重疊保留法 (1)重疊相加法 —— 由分段卷積的各段相加構(gòu) 成總的卷積輸出 h(n) x(n) 序列長度為 1N序列長度為 2N 假定 表示 x(n)序列的第 i段 ： 則輸入序列可表為： 于是輸出可分解為： 其中 ??? ?????01)1()()( 22 NiniNnxnxi??????ii nxnx )()(? ????????????i iii nynhnxnhnxny )()(*)()(*)()()(*)()( nhnxny ii ?()ixn 。 b. 用 N點(diǎn) FFT計(jì)算 c. 用 N點(diǎn) FFT計(jì)算 ()ixn( ) [ ( ) ]iiDFTX k nx?( ) ( ) ( )iiy n x n h n?? 由于 的長度為 N， 而 的長度為 N2， 因此相鄰兩段序列 必然有 NN2=N11 點(diǎn)發(fā)生重疊 ，最后的輸出應(yīng)該是這些重疊部分相加起來 ， 再和不重疊部分共同組成輸出序列 。 ()iyn()ixn()iyn()yn有 N11個(gè)點(diǎn)發(fā)生重疊 (2)重疊保留法 這種方法和第一種方法稍有不同 ， 即將上面分段序列中補(bǔ)零的部分不是補(bǔ)零 ， 而是保留原來的輸入序列值 ， 如果利用 FFT實(shí)現(xiàn) h(n)和 xi(n)的圓周卷積 ， 則每段卷積結(jié)果中有 N11個(gè)點(diǎn)不等于線性卷積值需舍去 。 h(n) x(n) 序列長度為 1N序列長度為 2N(1)重疊相加法 (2)重疊保留法 保留 點(diǎn)的輸入序列值 211N N N? ? ??FFT應(yīng)用中的幾個(gè)問題 實(shí)數(shù)序列的 FFT 以上討論的 FFT算法都是復(fù)數(shù)運(yùn)算 ,包括序列 x(n)也認(rèn)為是復(fù)數(shù) ,但大多數(shù)場合 ,信號是實(shí)數(shù)序列 ,任何實(shí)數(shù)都可看成虛部為零的復(fù)數(shù) 。 這種作法很不經(jīng)濟(jì) ,因?yàn)榘褜?shí)序列變成復(fù)序列 ,存儲器要增加一倍 ,且計(jì)算機(jī)運(yùn)行時(shí) ,即使虛部為零 ,也要進(jìn)行涉及虛部的運(yùn)算 ,造成運(yùn)算速度下降 。 （ 1） 用一個(gè) N點(diǎn) FFT同時(shí)計(jì)算兩個(gè) N點(diǎn)實(shí)序列的 DFT 設(shè) x(n)、 y(n)是彼此獨(dú)立的兩個(gè) N點(diǎn)實(shí)序列 ,且 X(k)=DFT[x(n)]， Y(k)=DFT[y(n)] 則 X(k)、 Y(k)可通過一次 FFT運(yùn)算同時(shí)獲得 。 Y(k)的值也可以通過 g(n)的 FFT運(yùn)算結(jié)果 G(k)得到 。顯然，這將使運(yùn)算效率提高一倍。 2）利用共軛對稱性求出 X1(k)、 X2(k)。 X(k)=X1(k)+W2Nk X2(k) ??????????????? ?????????1011022101011)12()()()2()()(NnnkNNnnkNNnNnnkNnkNWnxWnxkXWnxWnxkX