離散系統(tǒng)分析和離散傅里葉變換

1、第四章 離散系統(tǒng)分析和離散傅里葉變換4-1概述在上一章中我們已經(jīng)介紹了連續(xù)時間信號（周期的或非周期的）的傅里葉變換。在第一、二章中介紹了離散信號和離散系統(tǒng)的概念，在這一章中主要討論離散信號的傅里葉變換。4-2離散信號的傅里葉變換時域抽樣定理告訴我們，連續(xù)時間信號可以由它的樣本值恢復(fù)出來，即當(dāng)抽樣頻率給定時，抽樣函數(shù)就確定了，唯一與信號相關(guān)的是信號的樣本值，換句話說傳載中信息的是樣本值。因此研究連續(xù)時間信號中的信息，就轉(zhuǎn)變?yōu)檠芯繕颖局抵械男畔ⅰ．?dāng)抽樣頻率給定時，也就一定了，樣本值就可以抽象為序列，也就是說離散信號的數(shù)學(xué)抽象是序列。以后我們就用序列表示離散信號（樣本值）。由于序列的變量是整數(shù)變量，

2、與連續(xù)信號的變量不同，因此對序列的處理方法與連續(xù)時間變量的處理方法也必定不同。先來看看序列的傅里葉變換，連續(xù)非周期時間信號的傅里葉變換為假定是非周期的，仿照連續(xù)時間信號的傅里葉變換形式可以定義序列的傅里葉變換：（4-1）（4-2）式中為數(shù)字角頻率。（4-1）式和（4-2）式構(gòu)成了序列的傅里葉變換對，前者稱為序列的傅里葉正變換，后者稱為序列的傅里葉逆變換。注意到序列傅里葉正變換公式是個和式，這是因為序列的變量是離散的整數(shù)，序列的傅里葉逆變換公式是個積分式，由此也說明序列的傅里葉變換是的連續(xù)函數(shù)，也就是說，離散信號的傅里葉變換是頻域中連續(xù)的函數(shù)。此外因117所以任何序列的傅里葉變換都是以為周期的頻

3、域連續(xù)函數(shù)。序列的傅里葉變換具有如下性質(zhì)：1. 線性特性若，則（4-3）式中a和b均為常數(shù)。2. 時間位移特性若則（4-4）式中為任意整數(shù)。3. 頻率位移特性若則（4-5）式中為任意常數(shù)。4. 對稱特性若為實數(shù)序列，且有則稱為偶序列（even sequence），通常用下標(biāo)e表示偶序列，即。若為實數(shù)序列，且則稱為奇序列（odd sequence），通常用下標(biāo)o表示奇序列，即。任何序列都可以表示為偶序列與奇序列之和，即（4-6）其中（4-7）（4-8）若為復(fù)數(shù)序列，且其實部為偶對稱，虛部為奇對稱，即則稱此序列為共軛對稱序列（conjugate symmetric sequence），通常表示為。

4、若為復(fù)數(shù)序列，且其實部為奇對稱，虛部為偶對稱，即則稱此序列為共軛反對稱序列（conjugate ant symmetric sequence），通常表示為。任意復(fù)數(shù)序列均可表示為共軛對稱序列與共軛反對稱序列之和，即（4-9）其中（4-10）（4-11）實際上，（4-9）式與（4-6）式是等價的，當(dāng)為實數(shù)序列時，（4-9）式就變成（4-6）式了。若則（4-12）（4-13）（4-12）式說明共軛序列的傅里葉變換等于原序列傅里葉變換的共軛函數(shù)的反函數(shù)。（4-13）式說明反序列的共軛序列的傅里葉變換等于原序列傅里葉變換的共軛函數(shù)。這個性質(zhì)再一次表明了時域和頻域的對稱性。4-3周期序列的傅里葉級數(shù)（D

5、FS）我們知道一個周期為T的連續(xù)時間信號可以展開成傅里葉級數(shù)，即式中，。對于一個周期為N的離散信號，也可以展開成傅里葉級數(shù)，注意到連續(xù)時間信號展開成傅里葉級數(shù)是將信號表示成一系列基波頻率整倍數(shù)頻率上復(fù)指數(shù)函數(shù)的加權(quán)和。由此我們想到一個周期序列也展開成其基波頻率整倍數(shù)頻率上復(fù)指數(shù)的加權(quán)和。比較和這兩個復(fù)值數(shù)函數(shù)表達(dá)式，可以看出有兩點不同，一是連續(xù)時間信號的周期T是個模擬量，而周期序列的周期N則為整數(shù)值；二是連續(xù)時間信號的自變量t是連續(xù)時間變量，而離散時間信號的自變量n是離散變量（整數(shù)值）正是因為存在著這種差別，決定了周期離散信號的傅里葉級數(shù)與周期連續(xù)信號的傅里葉級數(shù)有著本質(zhì)的區(qū)別。在周期連續(xù)信號

6、的傅里葉級數(shù)表達(dá)式中，復(fù)指數(shù)（諧波分量）有無窮多個，這表現(xiàn)在傅里葉級數(shù)是n無窮和式。然而對于周期離散信號的復(fù)指數(shù)（諧波分量）只有N個獨立分量，這是因為同理可以推導(dǎo)出以上二式說明復(fù)指數(shù)既是變量k的周期序列，也是變量n的周期序列，周期均為N。因此周期信號只能分解在獨立的N個分量上，即有（4-14）為了與非周期序列加以區(qū)別，周期信號序列加注下標(biāo) “p”表示周期含義。（4-14）式是仿照周期連續(xù)時間信號的傅里葉級數(shù)形式得出的周期序列傅里葉級數(shù)展開式，現(xiàn)在的問題是這樣的展開是否可行，即能否找到滿足（4-14）式的一組系數(shù)。用乘以（4-14）式兩邊，并對n從0到N-1求和，即上式右邊交換求和次序，有上式中

7、方括弧中的和式由正交關(guān)系求出，即：式中m為整數(shù)，方括弧中的和式只有當(dāng)或時，取非零值N，由于后一個和式變量k的取值范圍為，所以m必須取零值（即），這就是說只有當(dāng)時，方括弧中的和式取非零值，于是（4-15）以上分析表明，（4-14）式中的系數(shù)可以嚴(yán)格地由（4-15）式求出，也就是說（4-14）式表述的關(guān)系是存在的。將（4-14）式和（4-15）式略作修改就是周期序列的傅里葉級數(shù)表達(dá)式，即(4-16)式中稱為旋轉(zhuǎn)因子，為傅里葉級數(shù)的系數(shù)，在這里寫成序列形式，它由下式給出：（4-17）注：因為所以注意到按照我們前面推導(dǎo)的結(jié)果因子應(yīng)該乘以（4-17）式，而在這里將這個因子放在（4-16）式中了，這是信號

8、處理理論中的習(xí)慣沒有特殊的含義；另外也看到我們除了將傅里葉級數(shù)的系數(shù)寫成序列形式外，還加注了下標(biāo)“p”，這是因為周期序列的傅里葉級數(shù)系數(shù)也是以N為周期的周期序列。任意給定一個周期序列都可以由（4-17）式求出它的傅里葉級數(shù)的系數(shù)序列，也就是說，時域中的一個周期序列必定與頻域中的一個周期序列一一對應(yīng)，在信號處理理論中通常稱（4-17）式為周期序列的離散傅里葉級數(shù)變換（簡寫為DFS），即（4-18）而（4-16）式稱為離散傅里葉級數(shù)的逆變換（簡寫為IDFS），即（4-19）我們可以把看成時域序列的頻域表示，反之也可看成一個頻域序列的時域表示，這就是說，與由（4-16）式和（4-17）式構(gòu)成了時域與

9、頻域的映射關(guān)系。現(xiàn)在討論離散傅里葉級數(shù)的性質(zhì)。設(shè)和都是周期為N的如果把周期連續(xù)時間信號的傅里葉級數(shù)的系數(shù)看成周期序列在頻域中的映射（即，則我們可以得出如下關(guān)系：1.連續(xù)、非周期時域信號映射非周期、連續(xù)頻域信號，它由傅里葉變換構(gòu)成映射關(guān)系，即（4-20）（4-21）2.離散、非周期時域信號映射周期、連續(xù)頻域信號，它由序列的傅里葉變換構(gòu)成映射關(guān)系，即（4-22）（4-23）3.連續(xù)、周期時域信號映射非周期、離散頻域信號，它由周期函數(shù)的傅里葉級數(shù)展開式構(gòu)成映射關(guān)系，即（4-24）（4-25）4.離散、周期時域信號映射周期、離散頻域信號，它由離散傅里葉級數(shù)變換構(gòu)成映射關(guān)系，即（4-26）（4-27）以

10、上分析實際上包含了所有可能的信號形式，注意上述映射關(guān)系有這樣的對稱關(guān)系：如果信號在時域中是連續(xù)的，則它的頻域表達(dá)式一定是非周期的，反之若信號在頻域中是連續(xù)的，則它的時域表達(dá)式一定是非周期的；如果信號在時域中是離散的，則信號在頻域中的表達(dá)式一定是周期的，反之如果信號在頻域中是離散的，則信號在時域中的表達(dá)式是周期的。4-4離散傅里葉變換（DFT）如果一個信號的時域表達(dá)式是離散的，而且是有限時寬，即（4-28）上式表明序列僅在區(qū)間0,N-1上取非零值，通常稱為有限長序列或N點序列。事實上，在工程我們一次觀察信號總是在有限時寬范圍內(nèi)進(jìn)行的，這就是說一次觀察信號常常是有限時寬的，對于離散信號就是有限長序

11、列。對于信號的表述無論是在時域，還是在頻域一次只能表示有限長度的信號，即我們希望對一個有限時寬的信號，它的頻域表示也是個有限長的，在離散情況下，一個有限長的時域序列能否表示為一個有限長的頻域序列，這就是離散傅里葉變換要解決的問題。在介紹離散傅里葉變換之前，先討論周期序列與有限長序列的關(guān)系。一個N點序列，若以N為周期做周期展開就構(gòu)成一個周期為N的周期序列，表示一個N點序列周期性延拓的數(shù)學(xué)描述為：（4-29）式中稱為n對N取余數(shù)，也就是n被N除可得一個整數(shù)商m和一個介于0與N之間的整數(shù)余數(shù)l，即（4-30）式中m為整數(shù)（可正可負(fù)），l也為整數(shù)且。n對N取余數(shù)就等于l，即（4-31）例如：給定N=8

12、時，當(dāng)n=18時，因為，即，所以；當(dāng)n=-18時，因為，即，所以；當(dāng)n=4時，因為，即，所以；當(dāng)n=-4時，因為，即，所以；一個N點序列通過周期性延拓可以得到一個周期序列。反之，一個周期序列取其主值區(qū)間內(nèi)的值可以得到一個N點序列，即（4-32）式中為一個矩形序列。以上分析說明，一個周期序列與一個N點序列有唯一的對應(yīng)關(guān)系，即（4-32）式；反之，一個N點序列也與一個周期序列有唯一對應(yīng)關(guān)系，即（4-29）式。 圖4-1離散傅里葉變換綜上所述，可以看到時域與頻域之間存在著這樣的關(guān)系：一個時域N點序列與一個時域周期序列存在著對應(yīng)關(guān)系，而這個時域周期序列通過離散傅里葉級數(shù)與頻域中的一個周期序列存在著對應(yīng)

13、關(guān)系，這個頻域周期序列又與頻域中的一個N點序列對應(yīng)，反之亦然。圖4-1清楚表示地表示了上述關(guān)系，從圖中可以看到時域中的一個N點序列確實與頻域中的一個N點序列有唯一的對應(yīng)關(guān)系，這個關(guān)系由離散傅里葉變換確定。(4-32)(4-33)（4-32）式和（4-33）式定義N點序列的離散傅里葉變換，從定義式可以看出N點序列離散傅里葉變換也是一個N點序列，但要注意從前面引入離散傅里葉變換的過程來看，離散傅里葉變換是隱含周期性的，因為取主值使得周期性表現(xiàn)不出來。一個序列的傅里葉變換定義為：（4-34）對于一個N點序列它的非零值區(qū)間為0,N-1，所以傅里葉變換為（4-35）前面我們已經(jīng)說明是周期為2的連續(xù)函數(shù)。

14、若對連續(xù)變量做離散化處理（即頻域抽樣），即令，這里k為整數(shù)，則（4-35）式可以寫成：在上式中離散信號的序列符號加了下標(biāo)“p”，這是因為做這樣的離散化處理得到的是一個周期序列，將上式與（4-32）是比較可以看出在主值區(qū)間內(nèi)0,N-1，上述序列傅里葉變換的抽樣值與序列的離散傅里葉變換是相等的，即（4-36）由此可見，N點序列的離散傅里葉變換實際上就是N點序列傅里葉變換的抽樣（抽樣間隔為）序列的主值序列，這一事實也表明了序列的傅里葉變換與序列的離散傅里葉變換是兩個不同的概念，切莫混為一談?，F(xiàn)在我們將要討論離散傅里葉變換的主要性質(zhì)。設(shè)1. 線性特性（4-37）式中a和b均為常數(shù)。注意上式中的和必須是

15、等長度的N點序列。2. 逆變換的另一種形式（4-38）式中“*”表示取共軛，這個公式意義在于告訴我們求序列的離散傅里葉變換及其逆變換可以用同一個程序來實現(xiàn)。3. 圓周位移特性序列的圓周移位（有時又稱為循環(huán)移位）的定義為：（4-39）圖4-2序列圓周位移式中m為常數(shù)，為N點序列。上式告訴我們，所謂圓周位移是將一個N點序列作周期延拓，然后移位并取主值序列，由此可見一個N點序列作圓周移位后仍為N點序列。序列的圓周移位可以用圖4-2來說明，當(dāng)時，相當(dāng)于坐標(biāo)右移（或圖形左移）m位；當(dāng)時，相當(dāng)于坐標(biāo)左移（或圖形右移）m位；注意序列的位移，相當(dāng)于將原坐標(biāo)原點移至處。4. 圓周卷積特性設(shè)和均為N點序列，則與的

16、圓周卷積定義為（4-40）上式說明，兩個N點序列的圓周卷積仍是一個N點序列。通常序列的圓周卷積用符號表示，即圖4-3序列的圓周卷積現(xiàn)在舉例說明圓周卷積的計算方法。設(shè)和均為6點序列，如圖4-3所示。5利用圓周卷積求線性卷積由離散卷積定理可知，兩個序列的圓周卷積可以通過它們的離散傅里葉乘積的反離散傅里葉變換得到，離散傅里葉變換和反離散傅里葉變換又可用其快速算法FFT來計算，所以如果線性卷積能夠用圓周卷積來實現(xiàn)，則可利用高效的FFT算法計算線性卷積，從而可以大大提高計算效率。下面就來討論如何用圓周卷積計算線性卷積的問題。已知離散線性非移變系統(tǒng)的單位抽樣響應(yīng)為，當(dāng)給定輸入時，系統(tǒng)的輸出可以由一下卷積求

17、出，假定是個N點序列，為M點序列，則可以肯定與的線性卷積也一定是個有限長序列。這是因為：而的非零值區(qū)間為的非零值區(qū)間為將這兩個不等式相加，有，這就是可能取非零值的區(qū)間，其長度為，在這個區(qū)間以外，不是等于零，就是等于零，因而卷積。根據(jù)以上分析可知，N點序列與M點序列的線性卷積得到一個點序列。為了尋找圓周卷積與循環(huán)卷積的關(guān)系，令即補(bǔ)M-1個零點構(gòu)成點有限長序列，令即補(bǔ)N-1個零點構(gòu)成點有限長序列。這樣和均為點的有限長序列，它們的圓周卷積也是個點序列與一樣長。我們現(xiàn)在逐點比較與的關(guān)系。 圖4-4給定序列的周期延拓圖4-5線性卷積與圓周卷積假定和的圖形如圖4-4所示。因為線性卷積圓周卷積根據(jù)線性卷積和

18、圓周卷積公式分別計算和，如圖4-5所示。當(dāng)時，圓周卷積與在區(qū)間上有非零值交點，并且相交的情況如同線性卷積與在區(qū)間上非零值相交的情況。所以在這個區(qū)間內(nèi)圓周卷積與線性卷積相等。當(dāng)時，圓周卷積與在上有非零值交點，并且相交的情況如同線性卷積與在同一區(qū)間上非零值相交的情況。所以在這個區(qū)間內(nèi)圓周卷積與線性卷積相等。當(dāng)時，圓周卷積與在上有非零值交點，并且相交的情況如同線性卷積與在同一區(qū)間上非零值相交的情況。所以在這個區(qū)間內(nèi)圓周卷積與線性卷積相等?？偵戏治隹梢?，即在這種情況下線性卷積與圓周卷積完全相等。一般來說，若是個N點序列，是個M點序列，則通過補(bǔ)零的方法將和延長為L（）點的序列，則與的L點圓周卷積就等于與

19、的線性卷積。4-5 快速傅里葉變換如前所述，快速傅里葉變換（FFT）是DFT的快速算法，其運(yùn)算次數(shù)比按DFT的定義直接計算要大為減少。下面分析FFT的算法原理。以N=4的DFT為例，按其定義用矩陣表示，有 (4-35)式中矩陣W的各元素均為復(fù)數(shù)，故欲求X(k)的每一個值，均需做4次復(fù)數(shù)乘法和3次復(fù)數(shù)加法。要計算X(k)的4個值，需做16次復(fù)數(shù)乘法和12次復(fù)數(shù)加法。推而廣之，計算N點的DFT，需要N2次復(fù)數(shù)乘與N(N-1)次復(fù)數(shù)加(如考慮W0 =1，需作的復(fù)數(shù)乘法的次數(shù)將略 有減少）。N越大，計算量增加得越多，當(dāng)N=2048時，復(fù)數(shù)乘運(yùn)算達(dá)到419萬次，這樣大的計算量，不可能對信號實時處理。然而

20、仔細(xì)觀察矩陣W發(fā)現(xiàn)，它的矩陣元素Wnk具有周期和對稱的特性，因此W的許多元素都是相同的，從而為簡化DFT計算提供了條件。（1） Wnk的周期性 （4-36）當(dāng)N=4時，則W6=W2，W9=W1（2） Wnk的對稱性因為故有 (4-37)若N=4，則W3= -W-1，W2= -W0利用Wnk 的周期性與對稱性，式(4-35)中的矩陣W可簡化為可見矩陣中有許多元素是相同的。如果把序列x(n)分解為若干短序列，并與W矩陣元素巧妙地結(jié)合起來計算DFT，就可能簡化運(yùn)算，這就是FFT的基本思路。下面推導(dǎo)FFT的算法。設(shè)N=2(為整數(shù))，則將x(n)分解成n為偶數(shù)(even)與奇數(shù)(odd)的兩序列之和，上

21、式可寫成當(dāng)n為偶數(shù)時，令n=2r；n為奇數(shù)時，令n=2r+1(r為整數(shù))，則由于 ，將此結(jié)果代入上式就有 (4-38)若記 (4-39)則式(4-38)可改寫作 (4-40)上式表明：求N點的DFT被分解為求兩個N/2點的DFT，即H(k)和G(k)。以N=8的DFTx(n)為例，利用(4-40)則有 (4-41)根據(jù)式(4-39)，G(k)，H(k)都為4點DFT，它們均是以4為周期的，故有G(k+4)=G(k)，H(k+4)=H(k)。再考慮W8k 的對稱性W8k+4 = -W8k (0k3)，則式(4-41)可寫為 (4-42)式(4-42)可用流圖來表示，流圖的形式如圖4.8右半部所示

22、。根據(jù)輸入輸出數(shù)據(jù)的運(yùn)算結(jié)構(gòu)可把流圖分為四個基本運(yùn)算單元，稱為蝶形運(yùn)算單元，如圖中由G(1)，H(1)，X(1)，X(5)所構(gòu)成的結(jié)構(gòu)就是一個蝶形運(yùn)算單元示如圖4.9(a)。由圖看出，蝶形運(yùn)算單元有如下規(guī)律：左方兩節(jié)點為輸入節(jié)點，代表輸入數(shù)值；右方兩節(jié)點為輸出節(jié)點，表示輸出數(shù)值得疊加。運(yùn)算是自左向右運(yùn)行的。線旁標(biāo)注的加權(quán)系數(shù)W81 ， -W81 與相應(yīng)的輸入數(shù)值作乘法運(yùn)算，即圖4.8 把8點DFT分解為兩個4點DFT的流圖X(1)與X(5)取值都僅與G(1)，H(1)有關(guān)，因此把X(1)與X(5)，和H(1)與G(1)稱為對偶節(jié)點，計算對偶節(jié)點的數(shù)值如X(1)和X(5)，僅需做一次復(fù)數(shù)乘法W8

23、1 H(1)、兩次復(fù)數(shù)加法G(1)+ W81 H(1)、G(1)- W81 H(1)。蝶形運(yùn)算單元也可畫成圖4.9(b)的形式。圖4.9 蝶形運(yùn)算單元G(k)是4點DFT，G(k)各點數(shù)值的計算可由式(4-39)將x(2r)按r的奇偶繼續(xù)分組，把4點DFT進(jìn)一步分解成兩個2點的DFT，即r為偶數(shù)時，記r=2l；r為奇數(shù)時，記r=2l+1(l均為正整數(shù))，則G(k)可寫成 式中， ， 。因設(shè)N=8，故A(k)，B(k)都是2點DFT，它們與G(k) 的關(guān)系為有A（k），B(k)計算G(k)的蝶形流圖見圖4.10(a)。(a) (b)圖4.10 4點DFT分解為2點DFT蝶形流圖與G(k)的分解類

24、似，也可將H(k)分解為2點DFT組合，即式中， ， 也都是2點DFT，由C(k)，D(k)求H(k)的蝶形流圖見圖4.10(b)。至此，A(k)，B(k)，C(k)，D(k)都已是2點DFT，它們均是由原始數(shù)據(jù)x(n)的兩點通過一個蝶形運(yùn)算單元計算而成，如對于A(k)，因當(dāng)N=8時，A(0)和A(1)可寫成這已是不可再分解的最簡DFT運(yùn)算。綜上所述，可得出8點DFT的蝶形流圖如圖4.11所示，它的逐級分解的框圖見圖4.12。 由圖4.11所示結(jié)構(gòu)得出的算法即快速傅里葉變換（FFT）。圖4.11 8點DFT蝶形流圖圖4.12 8點DFT逐級分解運(yùn)算框圖由圖4.11可見，蝶形流圖的輸出序列X(k

25、)是按k由小到大順序排列的，而輸入序列x(n)則是按所謂的碼位倒序排列的。如果把十進(jìn)制數(shù)換成二進(jìn)制數(shù)，然后把這些二進(jìn)制的首位至末位的順序顛倒過來再重新?lián)Q算成十進(jìn)制數(shù)，這個十進(jìn)制數(shù)的排列即碼位倒序排列。N=8的自然順序與碼位倒序的比較適于表4.2。表4.2 自然順序與碼位倒序 （N=8）二進(jìn)制數(shù)二進(jìn)制數(shù)的碼位倒序碼位倒序后的十進(jìn)制數(shù)0000000010011004201001023011110641000011510110156110011371111117碼位倒序的排列規(guī)律是由FFT算法所決定的。如果要輸入按自然順序排列，則輸出就會變成碼位倒序排列；如果輸出、輸入均要按自然序排列，則蝶形流圖的

26、形狀會發(fā)生扭曲，造成不能即位運(yùn)算，計算機(jī)內(nèi)存增加等新問題。由圖4.11可計算出FFT的運(yùn)算工作量。每按奇偶分解一次即可得出一級蝶形流圖，當(dāng)N=8時，共有28=3級蝶形流圖。每級蝶形流圖都有N/2=4個蝶形單元，故三級共有蝶形運(yùn)算單元N/22N=4×3=12（個）由前分析已知，每一蝶形運(yùn)算單元需作一次復(fù)數(shù)乘和兩次復(fù)數(shù)加運(yùn)算，故8點FFT總運(yùn)算次數(shù)中，復(fù)數(shù)乘為N/22N=12（次）復(fù)數(shù)加為N2N=24（次）直接按DFT的定義計算，8點DFT所需總運(yùn)算次數(shù)為復(fù)數(shù)乘 N2 =64 復(fù)數(shù)加 N（N-1）=56 可見當(dāng)N增加時，直接DFT使計算量急劇增加，但FFT則增加較少，圖4.13示出了兩種運(yùn)算情況下復(fù)數(shù)乘法次數(shù)的比較。上述FFT算法是把時間序列x(n)按n的奇偶分組分解后再來計算的，又稱為按時間分組的FFT的算法。與此對應(yīng)，也可把X(k)按k的奇偶分組分解后再來計算DFT，稱為按頻率分組的FFT的算法。上述兩種方法推導(dǎo)過程相仿，它們的計算工作量一樣，僅僅是算法的結(jié)構(gòu)有所不同。按頻率分組的算法可參考有關(guān)書籍。在推導(dǎo)上面的FFT算法時，規(guī)定序列N=2(為整數(shù))，這種算法被稱為以2為基底的FFT算法，還有4，8，16等為基底的FFT算法，這些算法計算速度更快，但算法也隨之變得更為復(fù)雜。FFT算法不僅用于計算DFT的正變換，也可用于離散傅立葉逆變換的計算，根據(jù)其正反變換相互