《數(shù)字信號處理》課件12

1、第 4 2）,數(shù)字信號處理,第4章 快速傅里葉變換,引言 直接計(jì)算DFT的問題及改進(jìn)途徑 按時(shí)間抽選的基-2FFT算法（Cooley-Tukey算法） 按頻率抽選的基-2FFT算法（Sande-Tukey算法） 離散傅里葉反變換的快速計(jì)算方法,4.3 按時(shí)間抽選（DIT）的基 -2 FFT算法,4.3.1 算法原理,步驟：將 x(n)按 n 先偶后奇分解為兩個N/2點(diǎn)的子序列,基-2 FFT算法,且滿足N=2L，L為正整數(shù),時(shí)間抽選法蝶形運(yùn)算流圖符號,按時(shí)間抽選，將一個N點(diǎn)DFT分解為兩個N/2點(diǎn)DFT（N=8）,復(fù)數(shù)乘法：,2個 點(diǎn)DFT,蝶形圖部分,次復(fù)數(shù)乘法,復(fù)數(shù)加法：,2個 點(diǎn)DFT,

2、蝶形圖部分,次復(fù)數(shù)乘法,次復(fù)數(shù)加法,將N點(diǎn)DFT，進(jìn)行一次分解后，運(yùn)算工作量節(jié)省了近一半,由于N=2L， 仍是偶數(shù),可以進(jìn)一步把每個 點(diǎn)子序列分解為兩個 點(diǎn)的子序列,，,一 點(diǎn)DFT進(jìn)一步分解為兩個 點(diǎn)DFT,式中,按時(shí)間抽選，將一個N點(diǎn)DFT分解為兩個N/2點(diǎn)DFT（N=8）,由兩個N/4點(diǎn)DFT組合成一個N/2點(diǎn)DFT,按時(shí)間抽選，將一個N點(diǎn)DFT分解為四個N/4點(diǎn)DFT （N=8）,按時(shí)間抽選，將一個N點(diǎn)DFT分解為兩個N/2點(diǎn)DFT（N=8）,X2(k)也可進(jìn)行同樣的分解：,式中,按時(shí)間抽選，將一個N點(diǎn)DFT分解為四個N/4點(diǎn)DFT （N=8）,N=8按時(shí)間抽選法FFT運(yùn)算流圖,按時(shí)間

3、抽選：N=2L時(shí)，共有L級蝶形，每級由N/2個蝶形組成,L 級蝶形運(yùn)算需要： 復(fù)數(shù)乘法 復(fù)數(shù)加法,式中，數(shù)學(xué)符號lb=log2,4.3.2 運(yùn)算量,每一級蝶形運(yùn)算需要：復(fù)數(shù)乘法 N/2 次 復(fù)數(shù)加法 N 次,當(dāng)N=2048時(shí)，直接計(jì)算DFT的運(yùn)算量是FFT運(yùn)算量的372.4倍。當(dāng)點(diǎn)數(shù)N越大時(shí)，F(xiàn)FT的優(yōu)點(diǎn)更為明顯。,直接計(jì)算DFT與FFT算法的計(jì)算量之比為,計(jì)算機(jī)乘法運(yùn)算所需的時(shí)間比加法運(yùn)算所需的時(shí)間多得多，故以乘法為例，比較 DFT和FFT的運(yùn)算量。 直接DFT復(fù)數(shù)乘法次數(shù)N 2， FFT復(fù)數(shù)乘法次數(shù),解: 直接計(jì)算DFT復(fù)乘次數(shù)（N )2=（10241024)2= 240 1012 ， 用

4、每秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，需要近3000小時(shí)。,例：對10241024點(diǎn)的二維圖像做DFT變換，計(jì)算機(jī)每秒可做 10萬次復(fù)數(shù)乘法，需要多少時(shí)間？ （忽略加法運(yùn)算時(shí)間）,直接計(jì)算DFT與FFT計(jì)算量之比為,同樣的計(jì)算機(jī)，應(yīng)用FFT算法進(jìn)行DFT變換需要0.2ms。,4.3.3 按時(shí)間抽選的FFT算法的特點(diǎn),1分組的方法，每一步分解都是按輸入序列在時(shí)域上是 屬于偶數(shù)還是奇數(shù)分為兩組，故稱為“按時(shí)間抽選”法。,3. 原位運(yùn)算（同址運(yùn)算） 當(dāng)數(shù)據(jù)輸入到存儲器后，每一級運(yùn)算的結(jié)果仍然存儲在這 同一組存儲器中，直到最后輸出，中間無需其他的存儲器。,每一級運(yùn)算均可在原位進(jìn)行，這種原位運(yùn)算的結(jié)構(gòu)可以節(jié)

5、省存儲單元，降低設(shè)備成本。,4. 倒位序規(guī)律,按時(shí)間抽選FFT 輸出X(k) 按自然順序排列在存儲單元,輸入 x(n) 不是按自然順序排列,是由于x(n)按標(biāo)號n先偶后奇不斷分組造成的,倒位序的規(guī)律：,例如,自然順序二進(jìn)制數(shù)和相應(yīng)的倒位序二進(jìn)制數(shù) （N=8）,第4章 快速傅里葉變換,引言 直接計(jì)算DFT的問題及改進(jìn)途徑 按時(shí)間抽選的基-2FFT算法（Cooley-Tukey算法） 按頻率抽選的基-2FFT算法（Sande-Tukey算法） 離散傅里葉反變換的快速計(jì)算方法,4.4 按頻率抽選（DIF）的基 -2 FFT算法,4.3.1 算法原理,步驟：將 x(n)按 n 前后對半分開為兩個N/2

6、點(diǎn)的子序列,基-2 FFT算法,且滿足N=2L，L為正整數(shù),k=0, 1, , N-1,將DFT化為,k=0, 1, , N-1,按k的奇偶可將 X(k) 分為兩部分:,下式：前一半輸入與后一半輸入之差再與WNn之積的N/2點(diǎn)DFT。,上式：前一半輸入與后一半輸入之和的N/2點(diǎn)DFT，,頻率抽取法蝶形運(yùn)算單元,按頻率抽取的第一次分解,按頻率抽取的第二次分解,按頻率抽取的FFT（N=8）信號流圖,4.4.2 按頻率抽選的FFT算法的特點(diǎn),1不斷將序列分為前后兩半，直到2點(diǎn)DFT,2分組的方法，從頻率上看，每一次都是按輸出在頻域上是 屬于偶數(shù)還是奇數(shù)分為兩組，故稱為“按頻率抽選”法。,1按時(shí)間抽選

7、：輸入是倒位序， 輸出是自然順序； 按頻率抽選：輸入是自然順序， 輸出是倒位序。,DIT法與DIF法比較：,二、相同點(diǎn) 運(yùn)算量相同,一、不同點(diǎn),2按時(shí)間抽選：復(fù)數(shù)乘法出現(xiàn)在加、減運(yùn)算之前； 按頻率抽選：復(fù)數(shù)乘法出現(xiàn)在減法運(yùn)算之后。,第4章 快速傅里葉變換,引言 直接計(jì)算DFT的問題及改進(jìn)途徑 按時(shí)間抽選的基-2FFT算法（Cooley-Tukey算法） 按頻率抽選的基-2FFT算法（Sande-Tukey算法） 離散傅里葉反變換的快速計(jì)算方法,4.5 離散傅里葉反變換的快速計(jì)算方法,1）DFT中的 IDFT中的,2）IDFT 中有常數(shù),區(qū)別：,按頻率抽取的FFT（N=8）信號流圖,按時(shí)間抽選的