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

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ù)字信號(hào)處理等許多領(lǐng)域中起著重要作用。本文由離散傅里葉級(jí)數(shù)導(dǎo)出離散傅里葉變換定義及其計(jì)算方法。但DFT計(jì)算量太大，實(shí)際應(yīng)用中有困難。為了減少運(yùn)算次數(shù)，提高算法效率，常用

2、快速傅里葉變換，文中簡(jiǎn)要介紹了幾種方法。關(guān)鍵詞：離散傅里葉變換；快速傅立葉變換；改進(jì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ù)時(shí)間傅里葉變換是一種積分變換，很難在實(shí)際中得到應(yīng)用。離散傅里葉變換是為了適應(yīng)利用計(jì)算機(jī)分析傅里葉變換而規(guī)定的一種專門(mén)運(yùn)算，他是對(duì)連續(xù)時(shí)間信號(hào)頻譜分析的逼近。由于大多數(shù)文獻(xiàn)中很少詳細(xì)地探討連續(xù)傅里葉變換與離散傅里葉變換之間的關(guān)系，因此人們對(duì)離散傅里葉變換存在著模糊的理解。11程佩青數(shù)字信號(hào)處理教程M北京：清華大學(xué)出版社，2007:110155有限長(zhǎng)序列在數(shù)字信號(hào)處理中非

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

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

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

8、散化還不夠，還必須在頻譜進(jìn)行離散化。數(shù)字化方法處理的序列只能為有限長(zhǎng)的，所以，要專門(mén)討論有限長(zhǎng)序列的頻譜分析問(wèn)題。2.2離散傅里葉變換的定義根據(jù)以上要求，引出了有限長(zhǎng)序列的離散傅里葉變換的概念。首先應(yīng)指出，離散傅里葉變換使針對(duì)有限長(zhǎng)序列或周期序列才存在的；其次，它相當(dāng)于把序列的連續(xù)傅里葉變換加以離散化（抽樣），頻域的離散化造成時(shí)間函數(shù)也呈周期，故級(jí)數(shù)應(yīng)限制在一個(gè)周期之內(nèi)。有限長(zhǎng)序列的離散傅里葉變換，簡(jiǎn)稱為離散傅里葉變換，即DFT(Discrete Fourier Transform)。設(shè)是周期為N的一個(gè)周期序列，在范圍內(nèi),令 它的離散傅里葉級(jí)數(shù)對(duì)如下： 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)把長(zhǎng)度為N的有限長(zhǎng)序列看成周期為N的周期序列的一個(gè)周期，利用DFS計(jì)算周期序列的一個(gè)周期，也就是計(jì)算了有限長(zhǎng)序列。設(shè)有限長(zhǎng)序列，點(diǎn)數(shù)為N，即只在有值，其他n時(shí)，。把它看成周期為N的周期序列的一個(gè)周期，而把看成的以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)同理，對(duì)頻域的周期序列可以看成是對(duì)有限長(zhǎng)序列的周期延拓，而有限長(zhǎng)序列看成周期序列的主值序列，即 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ū)間進(jìn)行的，故完全適用于主值序列與，即有限長(zhǎng)序列的離散傅里葉變換定義 正變換: 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)成離散傅里葉變換對(duì)。注意不要把離散傅里葉變換DFT和離散時(shí)間傅里葉變換DTFT混淆了。DTFT是對(duì)任意序列的傅里葉變換，它的頻譜是一個(gè)連續(xù)函數(shù)，而DFT是對(duì)有限長(zhǎng)

16、序列的離散傅里葉變換，DFT的特點(diǎn)是無(wú)論在時(shí)域還是在頻譜都是離散的，而且都是有限長(zhǎng)的。2.3離散傅里葉變換的性質(zhì) = 1 * GB2 線性 設(shè)兩個(gè)有限長(zhǎng)序列為和，則 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 對(duì)稱性 設(shè)是長(zhǎng)度為n的實(shí)序列，且，則 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)移位特性 有限長(zhǎng)序列為，若 ，則 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直接計(jì)算DFT的特點(diǎn)及減少運(yùn)算量的基本途徑長(zhǎng)度為N的有限長(zhǎng)序列的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)考慮為復(fù)數(shù)序列的一般情況，對(duì)某一個(gè)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)計(jì)算值需要N次復(fù)數(shù)乘法、(N-1)次復(fù)數(shù)加法。 N點(diǎn)DFT的復(fù)乘次數(shù)等于N2。顯然，把N點(diǎn)DFT分解為幾個(gè)較短的DFT，可使乘法次數(shù)大大減少。另外，旋轉(zhuǎn)因子WmN具有明顯的周期性和對(duì)稱性。其周期性表現(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)其對(duì)稱性表現(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運(yùn)算中有些項(xiàng)可以合并；利用的對(duì)稱性、周期性，可以將長(zhǎng)序列的FFT分解為短序列的DFT。FFT算法基本上分為兩大類：按時(shí)間抽選法 (Decimation In Time ,簡(jiǎn)稱DIT)和頻域抽取法(Decimation In Frequen

24、cy,簡(jiǎn)稱DIF)。下面只介紹DIT算法。3.2按時(shí)間抽選的（DIT）的基-2FFT算法 設(shè)序列的長(zhǎng)度為N，且滿足。如果不滿足這個(gè)條件，可以人為地加若干零值點(diǎn)，使之達(dá)到要求。這種N為2的整數(shù)冪的FFT也稱為基-2FFT。按n的奇偶把分解為兩個(gè)N/2點(diǎn)的子序列 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點(diǎn)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)式的運(yùn)算可用圖3-1的蝶形運(yùn)算符號(hào)表示。圖3-1 蝶形算法運(yùn)算符號(hào)采用這種

29、表示方法，可將上述分解過(guò)程表示于圖3-2中。此圖表示N=8的情況，其中輸出值 到由式(3.2.5)給出，而輸出值到是由式(3.2.6)給出的。圖3-2 N點(diǎn)DFT的一次時(shí)域抽取分解圖(N=8)與第一次分解相同，將x1(r)按奇偶分解成兩個(gè)N/4長(zhǎng)的子序列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)同理，由和的周期性和的對(duì)稱性，最后得到: 用

32、同樣的方法可計(jì)算出 其中 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)一為，則一個(gè)N=8的點(diǎn)DFT就可分解為四個(gè) 的點(diǎn)DFT，這樣可以得圖3-3所示的流程圖。圖3-3 N點(diǎn)DFT的第二次時(shí)域抽取分解圖(N=8)3.3DITFFT算法與直接計(jì)算DFT運(yùn)算量的比較每一級(jí)運(yùn)算都需要N/2次復(fù)數(shù)乘和N次復(fù)數(shù)加(每個(gè)蝶形需要兩次復(fù)數(shù)加法)。所以，L級(jí)運(yùn)算總共需要的復(fù)數(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)復(fù)數(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)由于計(jì)算機(jī)上乘法運(yùn)算所需時(shí)間比加法時(shí)間多得多，故以乘法為例，說(shuō)明FFT算法和DFT算法運(yùn)算量的比較。直接計(jì)算DFT與FFT算法的運(yùn)算量之比為 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是直接計(jì)算DFT與FFT算法所需運(yùn)算量