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

2、由于序列的變量是整數(shù)變量，與連續(xù)信號(hào)的變量不同，因此對(duì)序列的處理方法與連續(xù)時(shí)間變量的處理方法也必定不同。先來看看序列的傅里葉變換，連續(xù)非周期時(shí)間信號(hào)的傅里葉變換為假定是非周期的，仿照連續(xù)時(shí)間信號(hào)的傅里葉變換形式可以定義序列的傅里葉變換：（4-1）（4-2）式中為數(shù)字角頻率。（4-1）式和（4-2）式構(gòu)成了序列的傅里葉變換對(duì)，前者稱為序列的傅里葉正變換，后者稱為序列的傅里葉逆變換。注意到序列傅里葉正變換公式是個(gè)和式，這是因?yàn)樾蛄械淖兞渴请x散的整數(shù)，序列的傅里葉逆變換公式是個(gè)積分式，由此也說明序列的傅里葉變換是的連續(xù)函數(shù)，也就是說，離散信號(hào)的傅里葉變換是頻域中連續(xù)的函數(shù)。此外因?qū)Ｐ?專注-專業(yè)所以

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

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

5、稱性。4-3周期序列的傅里葉級(jí)數(shù)（DFS）我們知道一個(gè)周期為T的連續(xù)時(shí)間信號(hào)可以展開成傅里葉級(jí)數(shù)，即式中，。對(duì)于一個(gè)周期為N的離散信號(hào)，也可以展開成傅里葉級(jí)數(shù)，注意到連續(xù)時(shí)間信號(hào)展開成傅里葉級(jí)數(shù)是將信號(hào)表示成一系列基波頻率整倍數(shù)頻率上復(fù)指數(shù)函數(shù)的加權(quán)和。由此我們想到一個(gè)周期序列也展開成其基波頻率整倍數(shù)頻率上復(fù)指數(shù)的加權(quán)和。比較和這兩個(gè)復(fù)值數(shù)函數(shù)表達(dá)式，可以看出有兩點(diǎn)不同，一是連續(xù)時(shí)間信號(hào)的周期T是個(gè)模擬量，而周期序列的周期N則為整數(shù)值；二是連續(xù)時(shí)間信號(hào)的自變量t是連續(xù)時(shí)間變量，而離散時(shí)間信號(hào)的自變量n是離散變量（整數(shù)值）正是因?yàn)榇嬖谥@種差別，決定了周期離散信號(hào)的傅里葉級(jí)數(shù)與周期連續(xù)信號(hào)的傅里

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

7、和，即上式右邊交換求和次序，有上式中方括弧中的和式由正交關(guān)系求出，即：式中m為整數(shù)，方括弧中的和式只有當(dāng)或時(shí)，取非零值N，由于后一個(gè)和式變量k的取值范圍為，所以m必須取零值（即），這就是說只有當(dāng)時(shí)，方括弧中的和式取非零值，于是（4-15）以上分析表明，（4-14）式中的系數(shù)可以嚴(yán)格地由（4-15）式求出，也就是說（4-14）式表述的關(guān)系是存在的。將（4-14）式和（4-15）式略作修改就是周期序列的傅里葉級(jí)數(shù)表達(dá)式，即(4-16)式中稱為旋轉(zhuǎn)因子，為傅里葉級(jí)數(shù)的系數(shù)，在這里寫成序列形式，它由下式給出：（4-17）注：因?yàn)樗宰⒁獾桨凑瘴覀兦懊嫱茖?dǎo)的結(jié)果因子應(yīng)該乘以（4-17）式，而在這里將這個(gè)

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

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

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

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

12、于l，即（4-31）例如：給定N=8時(shí)，當(dāng)n=18時(shí)，因?yàn)椋矗裕划?dāng)n=-18時(shí)，因?yàn)椋矗裕划?dāng)n=4時(shí)，因?yàn)椋矗裕划?dāng)n=-4時(shí)，因?yàn)椋矗裕灰粋€(gè)N點(diǎn)序列通過周期性延拓可以得到一個(gè)周期序列。反之，一個(gè)周期序列取其主值區(qū)間內(nèi)的值可以得到一個(gè)N點(diǎn)序列，即（4-32）式中為一個(gè)矩形序列。以上分析說明，一個(gè)周期序列與一個(gè)N點(diǎn)序列有唯一的對(duì)應(yīng)關(guān)系，即（4-32）式；反之，一個(gè)N點(diǎn)序列也與一個(gè)周期序列有唯一對(duì)應(yīng)關(guān)系，即（4-29）式。 圖4-1離散傅里葉變換綜上所述，可以看到時(shí)域與頻域之間存在著這樣的關(guān)系：一個(gè)時(shí)域N點(diǎn)序列與一個(gè)時(shí)域周期序列存在著對(duì)應(yīng)關(guān)系，而這個(gè)時(shí)域周期序列通過離散傅里葉

13、級(jí)數(shù)與頻域中的一個(gè)周期序列存在著對(duì)應(yīng)關(guān)系，這個(gè)頻域周期序列又與頻域中的一個(gè)N點(diǎn)序列對(duì)應(yīng)，反之亦然。圖4-1清楚表示地表示了上述關(guān)系，從圖中可以看到時(shí)域中的一個(gè)N點(diǎn)序列確實(shí)與頻域中的一個(gè)N點(diǎn)序列有唯一的對(duì)應(yīng)關(guān)系，這個(gè)關(guān)系由離散傅里葉變換確定。(4-32)(4-33)（4-32）式和（4-33）式定義N點(diǎn)序列的離散傅里葉變換，從定義式可以看出N點(diǎn)序列離散傅里葉變換也是一個(gè)N點(diǎn)序列，但要注意從前面引入離散傅里葉變換的過程來看，離散傅里葉變換是隱含周期性的，因?yàn)槿≈髦凳沟弥芷谛员憩F(xiàn)不出來。一個(gè)序列的傅里葉變換定義為：（4-34）對(duì)于一個(gè)N點(diǎn)序列它的非零值區(qū)間為0,N-1，所以傅里葉變換為（4-35）前

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

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

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

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

18、。因?yàn)榫€性卷積圓周卷積根據(jù)線性卷積和圓周卷積公式分別計(jì)算和，如圖4-5所示。當(dāng)時(shí)，圓周卷積與在區(qū)間上有非零值交點(diǎn)，并且相交的情況如同線性卷積與在區(qū)間上非零值相交的情況。所以在這個(gè)區(qū)間內(nèi)圓周卷積與線性卷積相等。當(dāng)時(shí)，圓周卷積與在上有非零值交點(diǎn)，并且相交的情況如同線性卷積與在同一區(qū)間上非零值相交的情況。所以在這個(gè)區(qū)間內(nèi)圓周卷積與線性卷積相等。當(dāng)時(shí)，圓周卷積與在上有非零值交點(diǎn)，并且相交的情況如同線性卷積與在同一區(qū)間上非零值相交的情況。所以在這個(gè)區(qū)間內(nèi)圓周卷積與線性卷積相等。總上分析可見，即在這種情況下線性卷積與圓周卷積完全相等。一般來說，若是個(gè)N點(diǎn)序列，是個(gè)M點(diǎn)序列，則通過補(bǔ)零的方法將和延長為L（）

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

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

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

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

23、)和X(5)，僅需做一次復(fù)數(shù)乘法W81 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點(diǎn)DFT，G(k)各點(diǎn)數(shù)值的計(jì)算可由式(4-39)將x(2r)按r的奇偶繼續(xù)分組，把4點(diǎn)DFT進(jìn)一步分解成兩個(gè)2點(diǎn)的DFT，即r為偶數(shù)時(shí)，記r=2l；r為奇數(shù)時(shí)，記r=2l+1(l均為正整數(shù))，則G(k)可寫成 式中， ， 。因設(shè)N=8，故A(k)，B(k)都是2點(diǎn)DFT，它們與G(k) 的關(guān)系為有A（k），B(k)計(jì)算G(k)的蝶形流圖見圖4.10(a)。(a) (b)圖4.10 4點(diǎn)DFT分解為

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

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

26、、輸入均要按自然序排列，則蝶形流圖的形狀會(huì)發(fā)生扭曲，造成不能即位運(yùn)算，計(jì)算機(jī)內(nèi)存增加等新問題。由圖4.11可計(jì)算出FFT的運(yùn)算工作量。每按奇偶分解一次即可得出一級(jí)蝶形流圖，當(dāng)N=8時(shí)，共有28=3級(jí)蝶形流圖。每級(jí)蝶形流圖都有N/2=4個(gè)蝶形單元，故三級(jí)共有蝶形運(yùn)算單元N/22N=4×3=12（個(gè)）由前分析已知，每一蝶形運(yùn)算單元需作一次復(fù)數(shù)乘和兩次復(fù)數(shù)加運(yùn)算，故8點(diǎn)FFT總運(yùn)算次數(shù)中，復(fù)數(shù)乘為N/22N=12（次）復(fù)數(shù)加為N2N=24（次）直接按DFT的定義計(jì)算，8點(diǎn)DFT所需總運(yùn)算次數(shù)為復(fù)數(shù)乘 N2 =64 復(fù)數(shù)加 N（N-1）=56 可見當(dāng)N增加時(shí)，直接DFT使計(jì)算量急劇增加，但F

27、FT則增加較少，圖4.13示出了兩種運(yùn)算情況下復(fù)數(shù)乘法次數(shù)的比較。上述FFT算法是把時(shí)間序列x(n)按n的奇偶分組分解后再來計(jì)算的，又稱為按時(shí)間分組的FFT的算法。與此對(duì)應(yīng)，也可把X(k)按k的奇偶分組分解后再來計(jì)算DFT，稱為按頻率分組的FFT的算法。上述兩種方法推導(dǎo)過程相仿，它們的計(jì)算工作量一樣，僅僅是算法的結(jié)構(gòu)有所不同。按頻率分組的算法可參考有關(guān)書籍。在推導(dǎo)上面的FFT算法時(shí)，規(guī)定序列N=2(為整數(shù))，這種算法被稱為以2為基底的FFT算法，還有4，8，16等為基底的FFT算法，這些算法計(jì)算速度更快，但算法也隨之變得更為復(fù)雜。FFT算法不僅用于計(jì)算DFT的正變換，也可用于離散傅立葉逆變換的計(jì)算，根據(jù)其正反變換