離散傅里葉變換及其快速算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 2 h * MERGEFORMAT SEQ MTChap r 2 h * MERGEFORMAT 離散傅里葉變換及其快速算法摘要離散傅里葉變換(DFT)在數(shù)字信號處理等許多領(lǐng)域中起著重要作用。本文由離散傅里葉級數(shù)導出離散傅里葉變換定義及其計算方法。但DFT計算量太大，實際應用中有困難。為了減少運算次數(shù)，提高算法效率，常用

2、快速傅里葉變換，文中簡要介紹了幾種方法。關(guān)鍵詞：離散傅里葉變換；快速傅立葉變換；改進方法The discrete Fourier transform and fast Fourier TransformABSTRACTDiscrete Fourier Transform plays an important role in many fields of the digital signal processing. In this article, we deduced the definition and computing methods of Discrete Fourier Transf

3、orm from Discrete Fourier Series. But there are many difficulties in the practical application, owing to the large amount of computation .To improve the efficiency and reduce the computing complexity, Fast Fourier Transform are commonly used. Few methods of Fast Fourier Transform are introduced in t

4、he text.Key Words: Discrete Fourier Transform; Fast Fourier Transform; improvement approach目錄 TOC o 1-3 h z u 1引言連續(xù)時間傅里葉變換是一種積分變換，很難在實際中得到應用。離散傅里葉變換是為了適應利用計算機分析傅里葉變換而規(guī)定的一種專門運算，他是對連續(xù)時間信號頻譜分析的逼近。由于大多數(shù)文獻中很少詳細地探討連續(xù)傅里葉變換與離散傅里葉變換之間的關(guān)系，因此人們對離散傅里葉變換存在著模糊的理解。11程佩青數(shù)字信號處理教程M北京：清華大學出版社，2007:110155有限長序列在數(shù)字信號處理中非

5、常重要，當然可以用z變換和傅里葉變換來研究它，但可以導出反映它的有限長特點的一種有用工具是離散傅里葉變換。因此，DFT的計算在數(shù)字信號處理中非常有用。例如，在FIR濾波器設(shè)計中會遇到從h(n)求H(k)或由H(k)求h(n)，這就要計算DFT。再由，信號的頻譜分析對通信、圖像傳輸、雷達、聲吶等都是很重要的。此外，在系統(tǒng)的分析、設(shè)計和實現(xiàn)中都會用到DFT的計算。22孫大飛,劉浩,劉彬,陳務深離散傅里葉變換的進一步探析J電子技術(shù)2006，11：1 但在相當長的時間里,由于DFT的計算量太大，即使采用計算機也很難對問題實時處理，所以沒有得到真正的應用。直到1965年J.W.Cooley和J.W.Tu

6、key巧妙地利用因子的周期性和對稱性，構(gòu)造了 DFT 的快速算法，即快速離散傅里葉變換(FFT),在計算數(shù)學雜志上發(fā)表了著名的“機器計算傅里葉級數(shù)的一種算法”的文章，情況才發(fā)生改變。經(jīng)過改進對算法的改進，發(fā)展和完善了一套高速有效的運算方法，使DFT的計算大大簡化，運算時間可縮短一、二個數(shù)量級，從而使DFT的運算在實際當中真正得到了廣泛的應用。在以后的幾十年中，F(xiàn)FT 算法有了進一步的發(fā)展，目前較常用的是基-2算法和分裂基算法。3GUELACHVILI G傅里葉變換光譜M北京3GUELACHVILI G傅里葉變換光譜M北京:北京大學出版社，1990. 55-934呂乃光，陳家壁. 傅里葉光學M北

7、京：科學出版社， 1985. 144-1895張光昭傅里葉變換光譜學M廣州：中山大學出版社，1988. 221-2512離散傅里葉變換(DFT)的基本原理2.1引出離散傅里葉變換的必要性有限長序列的離散傅里葉變換和周期序列的離散傅里葉變換（DFS）本質(zhì)上是一樣的，為了更好地理解DFT，需要討論DFS。對離散時間信號的頻譜分析，可以用離散時間傅里葉變換，即DTFT。DTFT使我們能夠在數(shù)字域頻率分析信號的頻譜和離散系統(tǒng)的頻率響應特性，但對于DTFT仍然存在兩個實際問題。數(shù)字域頻率是一個連續(xù)變量，不利于用計算機進行計算。為了便于用數(shù)字的方法進行離散時間信號與系統(tǒng)的頻域分析和處理，僅僅在時間域進行離

8、散化還不夠，還必須在頻譜進行離散化。數(shù)字化方法處理的序列只能為有限長的，所以，要專門討論有限長序列的頻譜分析問題。2.2離散傅里葉變換的定義根據(jù)以上要求，引出了有限長序列的離散傅里葉變換的概念。首先應指出，離散傅里葉變換使針對有限長序列或周期序列才存在的；其次，它相當于把序列的連續(xù)傅里葉變換加以離散化（抽樣），頻域的離散化造成時間函數(shù)也呈周期，故級數(shù)應限制在一個周期之內(nèi)。有限長序列的離散傅里葉變換，簡稱為離散傅里葉變換，即DFT(Discrete Fourier Transform)。設(shè)是周期為N的一個周期序列，在范圍內(nèi),令 它的離散傅里葉級數(shù)對如下： MACROBUTTON MTPlaceR

9、ef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 1) MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2

10、. SEQ MTEqn c * Arabic * MERGEFORMAT 2)把長度為N的有限長序列看成周期為N的周期序列的一個周期，利用DFS計算周期序列的一個周期，也就是計算了有限長序列。設(shè)有限長序列，點數(shù)為N，即只在有值，其他n時，。把它看成周期為N的周期序列的一個周期，而把看成的以N為周期的周期延拓。令，則它們的關(guān)系表示為 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEF

11、ORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 3) MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 4)同理，對頻域的周期序列可以看成是對有限長序列的周期延拓，而有限長序列看成周期序列的主值序列，即 MACROBUTTON MTPlaceRef * M

12、ERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 5) MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ

13、MTEqn c * Arabic * MERGEFORMAT 6)由(2.2.5)與(2.2.6)以上兩式可以看出，求和是只限定在n=0到N-1及k=0到N-1的主值區(qū)間進行的，故完全適用于主值序列與，即有限長序列的離散傅里葉變換定義 正變換: MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT

14、7)反變換: MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 8) MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec h * MERGEFORMAT MACROBUTTON MTEditEquati

15、onSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 3 h * MERGEFORMAT SEQ MTChap h * MERGEFORMAT MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 1 h * MERGEFORMAT SEQ MTChap h * MERGEFORMAT 兩式構(gòu)成離散傅里葉變換對。注意不要把離散傅里葉變換DFT和離散時間傅里葉變換DTFT混淆了。DTFT是對任意序列的傅里葉變換，它的頻譜是一個連續(xù)函數(shù)，而DFT是對有限長

16、序列的離散傅里葉變換，DFT的特點是無論在時域還是在頻譜都是離散的，而且都是有限長的。2.3離散傅里葉變換的性質(zhì) = 1 * GB2 線性 設(shè)兩個有限長序列為和，則 MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 1 h * MERGEFORMAT SEQ MTChap h * MERGEFORMAT MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 3 h * MERGEFORMAT SEQ

17、MTChap r 2 h * MERGEFORMAT MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 3. SEQ MTEqn c * Arabic * MERGEFORMAT 1) = 2 * GB2 對稱性 設(shè)是長度為n的實序列，且，則 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT (

18、 SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 3. SEQ MTEqn c * Arabic * MERGEFORMAT 2) = 3 * GB2 循環(huán)移位特性 有限長序列為，若 ，則 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 3. SEQ MTEqn c *

19、 Arabic * MERGEFORMAT 3) = 4 * GB2 循環(huán)卷積特性 若，則 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 3. SEQ MTEqn c * Arabic * MERGEFORMAT 4) MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r

20、 1 h * MERGEFORMAT SEQ MTChap h * MERGEFORMAT 3快速傅里葉變換3.1直接計算DFT的特點及減少運算量的基本途徑長度為N的有限長序列的DFT為 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 1. SEQ MTEqn c * Arabic * MERGEFORMAT 1)考慮為復數(shù)序列的一般情況，對某一個k值，直接按式 MA

21、CROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 1. SEQ MTEqn c * Arabic * MERGEFORMAT 2)計算值需要N次復數(shù)乘法、(N-1)次復數(shù)加法。 N點DFT的復乘次數(shù)等于N2。顯然，把N點DFT分解為幾個較短的DFT，可使乘法次數(shù)大大減少。另外，旋轉(zhuǎn)因子WmN具有明顯的周期性和對稱性。其周期性表現(xiàn)為 MACROBUTTON MTPlaceRe

22、f * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 1. SEQ MTEqn c * Arabic * MERGEFORMAT 3)其對稱性表現(xiàn)為 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFO

23、RMAT 1. SEQ MTEqn c * Arabic * MERGEFORMAT 4) MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 2 h * MERGEFORMAT SEQ MTChap r 3 h * MERGEFORMAT 利用這些特性，是FFT運算中有些項可以合并；利用的對稱性、周期性，可以將長序列的FFT分解為短序列的DFT。FFT算法基本上分為兩大類：按時間抽選法 (Decimation In Time ,簡稱DIT)和頻域抽取法(Decimation In Frequen

24、cy,簡稱DIF)。下面只介紹DIT算法。3.2按時間抽選的（DIT）的基-2FFT算法 設(shè)序列的長度為N，且滿足。如果不滿足這個條件，可以人為地加若干零值點，使之達到要求。這種N為2的整數(shù)冪的FFT也稱為基-2FFT。按n的奇偶把分解為兩個N/2點的子序列 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGE

25、FORMAT 1)則的DFT為 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 2)由于,上式可表示成 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEF

26、ORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 3)其中和分別為和的N/2點DFT，即 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 4) MACROBUTTON MTPlac

27、eRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 5) 由于和均以N/2為周期，且，所以X(k)又可表示為 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSe

28、c c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 6) MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 7)(3.2.5)式和(3.2.6)式的運算可用圖3-1的蝶形運算符號表示。圖3-1 蝶形算法運算符號采用這種

29、表示方法，可將上述分解過程表示于圖3-2中。此圖表示N=8的情況，其中輸出值 到由式(3.2.5)給出，而輸出值到是由式(3.2.6)給出的。圖3-2 N點DFT的一次時域抽取分解圖(N=8)與第一次分解相同，將x1(r)按奇偶分解成兩個N/4長的子序列x03(l)和x4(l)，即 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Ar

30、abic * MERGEFORMAT 8)那么，X1(k)又可表示為 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 9)式中 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Ara

31、bic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 10) MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 11)同理，由和的周期性和的對稱性，最后得到: 用

32、同樣的方法可計算出 其中 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 12) MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 3 h * MERGEFORMAT SEQ MTChap r

33、3 h * MERGEFORMAT 將系數(shù)統(tǒng)一為，則一個N=8的點DFT就可分解為四個 的點DFT，這樣可以得圖3-3所示的流程圖。圖3-3 N點DFT的第二次時域抽取分解圖(N=8)3.3DITFFT算法與直接計算DFT運算量的比較每一級運算都需要N/2次復數(shù)乘和N次復數(shù)加(每個蝶形需要兩次復數(shù)加法)。所以，L級運算總共需要的復數(shù)乘次數(shù)為 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * M

34、ERGEFORMAT 3. SEQ MTEqn c * Arabic * MERGEFORMAT 1)復數(shù)加次數(shù)為 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 3. SEQ MTEqn c * Arabic * MERGEFORMAT 2)由于計算機上乘法運算所需時間比加法時間多得多，故以乘法為例，說明FFT算法和DFT算法運算量的比較。直接計算DFT與FFT算法的運算量之比為 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 3. SEQ MTEqn c * Arabic * MERGEFORMAT 3)圖3-4是直接計算DFT與FFT算法所需運算量