【正文】 kXNjkkNj N??????2)()()( 2????即 : X(K)也是 在 w=2πk/N處的采樣值 。 MN， 將原序列裁為 N點(diǎn)計(jì)算 N點(diǎn)的 DFT； MN， 將原序列補(bǔ)零至 N點(diǎn) ， 然后計(jì)算 N點(diǎn) DFT。 若 xop(n)=x*op(Nn), 0≤n≤N 1 則稱(chēng) xop(n)為 共軛反對(duì)稱(chēng)序列 如圖所示。確定 DFT在奇數(shù)點(diǎn)的值。 根據(jù)實(shí)序列 DFT的對(duì)稱(chēng)特性 X[k]=X *[Nk] 可得 可見(jiàn)，當(dāng)輸入信號(hào)的頻率為 qω0時(shí)， X(K)的 N個(gè)值中只有X（ q） =N，其余皆為零，如果輸入信號(hào)為若干個(gè)不同頻率的信號(hào)的組合，經(jīng)離散付里葉變換后，不同的 k上， X（ k）將有一一對(duì)應(yīng)的輸出，因此，離散付里葉變換實(shí)質(zhì)上對(duì)頻率具有選擇性。 說(shuō)明： xN(n)為原序列 x (n)以 N為周期 周期延拓后的主值序列。 同樣，頻域取樣時(shí)， 頻域離散，時(shí)域周期 。記 X(ej?)在 {?=2? k/3。所以 X（ Z）的 N個(gè)取樣值 X(K），包含了 X（ Z）的全部信息。 因而 ， 插值函數(shù) Φk(z)只在本身采樣點(diǎn) r=k處不為零 ， 在其他（ N1） 個(gè)采樣點(diǎn) r上 （ r=0, 1, …, N1， 但 r≠k） 都是零點(diǎn) （ 有 （ N1）個(gè)零點(diǎn) ） 。 ?????? ?????? ?? kNkX ?? 2)( 實(shí)際應(yīng)用中，大多數(shù)是求解線(xiàn)性卷積，如信號(hào) x（ n）通過(guò)系統(tǒng) h（ n），其輸出就是線(xiàn)性卷積 y（ n） =x（ n） *h（ n）。 ( ) [ ( ) ]( ) [ ( ) ]X k D F T x nH k D F T h n??若 則由時(shí)域循環(huán)卷積定理有 Yc(k)=DFT［ yc(n) ］ =X (k)H(k) 1010( ) ( ) ( ) ( )( ) ( ) ( )LcLmqLLqmy n h m x n m q L R nh m x n m q L R n??? ? ? ???? ? ? ?? ? ?? ? ?????循環(huán)卷積與線(xiàn)性卷積的關(guān)系 10( ) ( ) ( ) ( ) ( ( ) ) ( )01LLLmcy n x n h n h m x n m R nnL??? ? ? ?? ? ??( ( ) ) ( ) ,Lqx n x n q L?? ? ????()ly n qL?10( ) ( ) ( )( ) ( ) ( )Nlmc l Lqh m x n q L m y n q Ly n y n q L R n???? ? ?? ? ? ?????所以 ,循環(huán)卷積 yc(n)等于線(xiàn)性卷積 yl(n)以 L為周期的周期延拓序列的主值序列 , 因?yàn)?yl(n)的長(zhǎng)度為 N1+N21, 因此只有L≥ N1+N21時(shí)， yl(n)以 L為周期進(jìn)行周期延拓才不會(huì)產(chǎn)生混疊， yc(n)= yl(n) 將 x(n)、 h(n)的長(zhǎng)度都變?yōu)?N1+N21, 則： 11 1 2( ) 0 139。 長(zhǎng)序列線(xiàn)性卷積的計(jì)算 直接用 DFT計(jì)算的缺點(diǎn)： 1）信號(hào)要全部輸入后才能進(jìn)行計(jì)算，延遲太多 2）內(nèi)存要求大 3）算法效率不高 需要將 x(n)分成若干段短序列 設(shè) h(n)的長(zhǎng)度為 N， x(n)為長(zhǎng)度為 L的長(zhǎng)序列。 F愈小，頻率分辨率愈高。 上述兩種現(xiàn)象又稱(chēng)為截?cái)嘈?yīng)。如對(duì)抽樣信號(hào)做 N=1600點(diǎn)的 DFT，試確定 X[k]中 k=600和k=1200點(diǎn)所分別對(duì)應(yīng)原連續(xù)信號(hào)的連續(xù)頻譜點(diǎn) f1 和 f2 (kHz)。 0 , 1 , , 1n n r N r m n N? ? ? ? ? ?211 ( 39。20 39。 0( ) ( 39。)kN jnNmnkX x n em?? ??? ?11 2200( ) ( ) ( )kkmm j r j rmmMrrkkX k X e X emm???? ????????而 1 20/0/km jrmrm k mekm?? ???? ???為 整 數(shù)不 為 整 數(shù)( ) /()0/Mkm X k mXk mkm??? ???為 整 數(shù)不 為 整 數(shù)如： x(n)=cos(nπ/6) 0 1 2 11x ( n )n 0 1X ( k )11 nN=12時(shí)的 DFT N=24時(shí)的 DFT 6N=16時(shí)的 DFT 快速傅里葉變換 (FFT) 頻譜分析在數(shù)字信號(hào)處理中用途廣泛：如通過(guò)語(yǔ)言信號(hào)的頻譜分析實(shí)現(xiàn)語(yǔ)音通訊的頻帶壓縮、聲納信號(hào)的頻譜分析用以區(qū)分水面與水下目標(biāo)、在各種測(cè)量?jī)x器中，頻譜分析用得更多，這些都需要 DFT運(yùn)算。所以直接計(jì)算 DFT的計(jì)算量與 N的平方成正比，當(dāng) N較大時(shí)，計(jì)算量太大。 基 2時(shí) 域 抽取 (Decimation in time)FFT算法 基 2頻率抽取 (Decimation in frequency)FFT算法 12,1,0]12[ ]2[][ ???????Nrrxrxkx ?nr r k 1 基 2時(shí)域抽取 FFT算法（ DITFFT） 設(shè)： x(n)為一長(zhǎng)度為 N的序列。兩個(gè) N/2點(diǎn)的 DFT需要 2 (N/2)2＝ N2/2次復(fù)數(shù)乘 ,可見(jiàn)，分解后運(yùn)算量大約節(jié)省了一倍。如圖所示： 可看出第 m1級(jí)的兩節(jié)點(diǎn) xm1(p), xm1(q) ，經(jīng)蝶算后，在 m級(jí)中的節(jié)點(diǎn)序號(hào)是不變的，即 xm(p), xm(q) 。而不需要開(kāi)辟新的地址存放計(jì)算結(jié)果。 對(duì)偶節(jié)點(diǎn)的間距可用下式確定： m為該級(jí)的序號(hào) r可由下式確定： 若 ,則數(shù)據(jù)不必交換。如圖所示： nnn?nn? nn nn n n3)、 碼位整序 通常將 x(n)按順序輸入，通過(guò)變址運(yùn)算，得到它的倒序排列。 兩邊再同時(shí)取共軛，得 ? ?1011( ) [ ( ) ]。 設(shè)序列 x(n)的長(zhǎng)度為 N=2M，將 x(n)前后對(duì)半分開(kāi)，得到兩個(gè)子序列，其 DFT可表示為如下形式： 10/ 2 1 10 / 2/ 2 1 / 2 1( / 2 )00/ 2 1/20( ) [ ( ) ] ( )( ) ( )( ) ( )2[ ( ) ( ) ]2NknNnNNk n k nNNn n NNNk n k n NNNnnNk N k nNNnX k D FT x n x n Wx n W x n WNx n W x n WNx n W x n W?????????????????? ? ?? ? ??????? 將 X(k)分解成偶數(shù)組與奇數(shù)組，當(dāng) k取偶數(shù) (k=2r, r=0,1,… ,N/21)時(shí) /2 1,( 1 )1k N kNkWk???? ? ?? ????偶奇/ 2 120/ 2 1/20( 2 ) [ ( ) ( ) ]2[ ( ) ( ) ] 0 , 1 , , 122NrnNnNrnNnNX r x n x n WNNx n x n W r????? ? ?? ? ? ? ???當(dāng) k取奇數(shù) (k=2r+1,r=0,1,… ,N/21)時(shí) / 2 1 ( 2 1)0/ 2 1/20( 2 1 ) [ ( ) ( ) ]2[ ( ) ( ) ]2NnrNnNn nrNNnNX r x n x n WNx n x n W W?????? ? ? ?? ? ???12( ) ( ) ( / 2 )( ) [ ( ) ( / 2 ) ] 0 , 1 , , / 2 1nNx n x n x n Nx n x n x n N W n N? ? ?? ? ? ? ?/ 2 11 / 20/ 2 12 / 20( 2 ) ( )( 2 1 ) ( )NrnNnNrnNnX r x n WX r x n W?????????? ??????令： 則： 所以在頻域按 K將一個(gè) N點(diǎn)的 DFT，分成偶、奇兩部分的N/2點(diǎn)的 DFT 圖 DIF―FFT 一次分解運(yùn)算流圖 (N=8) N / 2 點(diǎn)D F TW N0N / 2 點(diǎn)D F TW N1W N2WN3X ( 0 )x1( 0 )X ( 2 )X ( 4 )X ( 6 )X ( 1 )X ( 3 )X ( 5 )X ( 7 )x1( 1 )x1( 2 )x1( 3 )x2( 0 )x2( 1 )x2( 2 )x2( 3 )x ( 0 )x ( 1 )x ( 2 )x ( 3 )x ( 4 )x ( 5 )x ( 6 )x ( 7 )同樣還可繼續(xù)分解，將 N/2點(diǎn)的 DFT分解成兩個(gè) N/4點(diǎn)的DFT 圖 DIF―FFT 二次分解運(yùn)算流圖 (N=8) N /4 點(diǎn)D F TW N0W N1W N2W N3x ( 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 )W N0W N2W N0W N2N /4 點(diǎn)D F TN /4 點(diǎn)D F TN /4 點(diǎn)D F T 圖 DIF―FFT 運(yùn)算流圖 (N=8) W N0W N1W N2W N3W N0W N2W N0W N2W N0W N0W N0W N0X ( 0 )X ( 4 )X ( 2 )X ( 6 )X ( 1 )X ( 5 )X ( 3 )X ( 7 )x ( 0 )x ( 1 )x ( 2 )x ( 3 )x ( 4 )x ( 5 )x ( 6 )x ( 7 ) 圖 DIT―FFT 的一種變形運(yùn)算流圖 W N0W N0W N2W N0X ( 0 )X ( 4 )X ( 2 )X ( 6 )X ( 1 )X ( 5 )X ( 3 )X ( 7 )x ( 0 )x ( 1 )x ( 2 )x ( 3 )x ( 4 )x ( 5 )x ( 6 )x ( 7 )W N0W N2W N1W N3W N2W N0W N0W N0 圖 DIT―FFT 的一種變形運(yùn)算流圖 W N0W N0W N2W N0X ( 0 )X ( 1 )X ( 2 )X ( 3 )X ( 4 )X ( 5 )X ( 6 )X ( 7 )x ( 0 )x ( 1 )x ( 2 )x ( 3 )x ( 4 )x ( 5 )x ( 6 )x ( 7 )W N0W N2W N1W N3W N2W N0W N0W N03. IDFT的高效算法 上述 FFT算法流圖也可以用于離散傅里葉逆變換(In