1、第2章 DFT及其快速算法,2-1 周期序列 2-2 離散傅立葉級數(shù) 2-3 離散傅立葉變換 2-4 頻率采樣理論 2-5 快速傅立葉變換 2-6 離散傅立葉反變換（IDFT) 的運(yùn)算,一個完整N=8的按時間抽取FFT的運(yùn)算流圖,x(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),m=0,m=1,m=2,2.5.3 頻率抽取基2 FFT 算法（DIF),將x(n)按前后分為兩組：,前,后,將N=8點(diǎn)分解成2個4點(diǎn)的DFT的信號流圖,4點(diǎn) DFT,x(0) x(1) x(2) x(3),4

2、點(diǎn) DFT,x(4) x(5) x(6) x(7),X(0) X(2) X(4) X(6),X(1) X(3) X(5) X(7),X1(k),前半部分序列,后半部分序列,x1(n),x2(n),X2(k),完整N=8的按頻率抽取FFT的運(yùn)算流圖,x(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),m=0,m=1,m=2,DIF與DIT比較,不同之處： （1）DIF與DIT兩種算法結(jié)構(gòu)倒過來。 DIF為輸入順序，輸出亂序。運(yùn)算完畢再運(yùn)行“二進(jìn)制倒讀”程序。 DIT為輸入亂序，輸出順序。先

3、運(yùn)行“二進(jìn)制倒讀”程序，再進(jìn)行求DFT。 （2）DIF與DIT根本區(qū)別：在于蝶形結(jié)不同。 DIT的復(fù)數(shù)相乘出現(xiàn)在減法之前。 DIF的復(fù)數(shù)相乘出現(xiàn)在減法之后。,DIT,DIF,2-6 計(jì)算IFFT,將下列兩式進(jìn)行比較,一、改變FFT流圖系數(shù)的方法1.思路,在IFFT的運(yùn)算中，常常把1/N分解為(1/2)m，并且在M級運(yùn)算中每一級運(yùn)算都分別乘以1/2因子，就可得到IFFT的兩種基本蝶形運(yùn)算結(jié)構(gòu)。（并不常用此方法）,2.IFFT的基本蝶形運(yùn)算,A,B,A,B,(a)頻率抽取IFFT的蝶形運(yùn)算,(b)時間抽取IFFT的蝶形運(yùn)算,時間抽取和頻率抽取的概念要倒一下,四.直接利用FFT流圖的方法1.思路,前

4、面的兩種IFFT算法，排程序很方便，但要改變FFT的程序和參數(shù)才能實(shí)現(xiàn)。 現(xiàn)介紹第三種IFFT算法，則可以完全不必改動FFT程序。,2.直接利用FFT流圖方法的推導(dǎo),實(shí)序列的FFT 運(yùn)算, FFT算法為同址運(yùn)算，且 X(k)一般為復(fù)數(shù)，,存放的數(shù)組應(yīng)該是復(fù)數(shù)數(shù)組，但輸入序列 x(n),通常為實(shí)序列，存放到復(fù)數(shù)數(shù)組中時，造成存儲空,間及運(yùn)算時間的浪費(fèi)，為提高存儲空間利用率及提,高運(yùn)算速度：,1. 通過一個N 點(diǎn)FFT運(yùn)算 ，同時求出兩個,獨(dú)立的N 點(diǎn)實(shí)序列的DFT,設(shè),x(n)與y(n)為實(shí),序列。,令,N點(diǎn)FFT,由傅立葉變換的奇偶虛實(shí)性,2. 用一個N點(diǎn)FFT運(yùn)算，求一個2N點(diǎn)實(shí)序列,的DFT,設(shè)x(n)為2N點(diǎn)實(shí)序列,令g(m)=x(2m) , h(m)=x(2m+1),且,N點(diǎn)FFT,再由時間抽取基2 FFT算法,補(bǔ)0,IDFT,線性 卷積,用FFT實(shí)現(xiàn)線性