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

1、第第3章章 離散傅里葉變換離散傅里葉變換及其快速算法及其快速算法3.1 離散傅里葉變換離散傅里葉變換(DFT)3.2 利用利用DFT做連續(xù)信號(hào)的頻譜分析做連續(xù)信號(hào)的頻譜分析 3.3 快速傅里葉變換快速傅里葉變換(FFT)3.4 關(guān)于關(guān)于FFT應(yīng)用中的幾個(gè)問(wèn)題應(yīng)用中的幾個(gè)問(wèn)題3.1 3.1 離散傅里葉變換（離散傅里葉變換（DFTDFT）四種不同信號(hào)的頻譜四種不同信號(hào)的頻譜1 1 連續(xù)周期信號(hào)連續(xù)周期信號(hào) 連續(xù)周期信號(hào)的頻譜是非周期離散的連續(xù)周期信號(hào)的頻譜是非周期離散的ntjnneFtf1)(221)(1TTtjnndtetfTFnjnneFF2 2 連續(xù)非周期信號(hào)連續(xù)非周期信號(hào) 連續(xù)非周期信號(hào)的

2、頻譜是非周期連續(xù)的連續(xù)非周期信號(hào)的頻譜是非周期連續(xù)的dtetfjFtj)(jejFjF3 3 離散非周期信號(hào)離散非周期信號(hào) 離散非周期信號(hào)的頻譜是周期連續(xù)的離散非周期信號(hào)的頻譜是周期連續(xù)的njnjenxeX)( jjjeeXeX連續(xù)周期信號(hào)的頻譜是非周期離散的連續(xù)周期信號(hào)的頻譜是非周期離散的連續(xù)非周期信號(hào)的頻譜是非周期連續(xù)的連續(xù)非周期信號(hào)的頻譜是非周期連續(xù)的離散非周期信號(hào)的頻譜是周期連續(xù)的離散非周期信號(hào)的頻譜是周期連續(xù)的離散周期信號(hào)的頻譜是周期離散的離散周期信號(hào)的頻譜是周期離散的3.1.1 3.1.1 離散傅里葉級(jí)數(shù)（離散傅里葉級(jí)數(shù)（DFSDFS）一個(gè)周期為一個(gè)周期為N N的周期序列，的周期序

3、列， k k為任意整數(shù)，為任意整數(shù)，N N為周期為周期)()(kNnxnxnNjene21)(knNjkene2)(周期為周期為N N序列其基頻成分為：序列其基頻成分為：knNjnjknNjnNkNjeeee222)(2)()(nenekNkk次諧波序列為次諧波序列為：102)(1)(NkknNjekXNnx102)(NnrnNjenxrkrkNrkeerkNerkNjrkjNnnrkNj0112210)(2( 1010)(2)(1NkNnnrkNjekXN102102)(1NnrnNjNkknNjeekXN 1) 可求可求 k次諧波的系數(shù)次諧波的系數(shù) 2） 也是一個(gè)由也是一個(gè)由 N 個(gè)獨(dú)立諧

4、波分量組成的傅立葉級(jí)數(shù)個(gè)獨(dú)立諧波分量組成的傅立葉級(jí)數(shù) 3） 為周期序列，周期為為周期序列，周期為N。)()(102rXenxNnrnNj102)()(NnknNjenxkX)(kX)(kX)(kX)()()()(10/210)(/2kXenxenxmNkXNnknNjNnnmNkNj時(shí)域上周期序列的離散傅里葉級(jí)數(shù)在頻域上仍是一個(gè)時(shí)域上周期序列的離散傅里葉級(jí)數(shù)在頻域上仍是一個(gè)周期序列。周期序列。 是一個(gè)周期序列的離散傅里葉級(jí)數(shù)(DFS)變換對(duì)，這種對(duì)稱關(guān)系可表為)()(nxkX102)()()(NnknNjenxnxDFSkXNjNeW2102)(1)()(NkknNjekXNkXIDFSnx1

5、010)()(1)()()()(NkknNNnknNkXIDFSWkXNnxnxDFSWnxkX則則DFS變換對(duì)可寫為變換對(duì)可寫為DFS 離散傅里葉級(jí)數(shù)變換離散傅里葉級(jí)數(shù)變換IDFS離散傅里葉級(jí)數(shù)反變換。離散傅里葉級(jí)數(shù)反變換。nO6543211 10NnnkNWnxkX nx 3042nnkjenx102nnkje 1000njeX221jej1je10231jej1 1021nnjeX 102nnjeX 10233nnjeX 10233nnjeX ,1 , 0 ,1 , 2jjkX DFS的幾個(gè)主要特性：的幾個(gè)主要特性：)()()()(kYbkXanybnxaDFS)()(nynx、假設(shè)假設(shè)

6、 都是周期為都是周期為 N N 的周期序列的周期序列)()()()(nyDFSkYnxDFSkX各自的離散傅里葉級(jí)數(shù)為：各自的離散傅里葉級(jí)數(shù)為：1）線性）線性 2）序列移位）序列移位)()()()(nxWlkXIDFSkXWmnxDFSnlNmkN證證: 因?yàn)橐驗(yàn)?及及 都是以都是以N N為周期的函數(shù)，所以有為周期的函數(shù)，所以有)(nxknNw mNmikmNkiNNnknNWWixWmnxmnxDFS110 kXWWixWWixWkmNNikiNkmNmNmikiNkmN101由于由于 與與 對(duì)稱的特點(diǎn)，同樣可證明對(duì)稱的特點(diǎn)，同樣可證明)(nx)(kX nxWlkXIDFSnlN 3）共軛對(duì)

7、稱性）共軛對(duì)稱性 kXnx*DFS 10*)(NnnkNWnxnxDFS證證: kXnx*DFS同理同理: nx nx*對(duì)于復(fù)序列對(duì)于復(fù)序列 其共軛序列其共軛序列 滿足滿足 10*)(NnnkNWnxkX*進(jìn)一步可得進(jìn)一步可得 )()(21DFS21ReDFS*kNXkXnxnxnx )()(21ReDFS*ekNXkXkXnx共軛偶對(duì)稱分量共軛偶對(duì)稱分量 )()(21ImDFS*okNXkXkXnxj共軛奇對(duì)稱分量共軛奇對(duì)稱分量 4）周期卷積）周期卷積)()()(kYkXkF10)()()()(NmmnymxkFIDFSnf10)()(Nmmnxmy若若則則或或 *x ny n)()(kFI

8、DFSnf 101NknkNWkFN 101NkknNWkYkXN 10101NkknNNmmkNWkYWmxN 10101NmNkmnkNWkYNmx 10Nmmnymx證：證： 10() ()*Nmfnx m y nmx ny n mmnymxnynx)()(*周期卷積周期卷積線性卷積線性卷積 nxnO7 nynO766554433221188 10)()(Nmmnymxnf11 mxmmy1my2my3mmy0 60)0()(0mmymxf1 60)1 ()(1mmymxf0 60)2()(2mmymxf1 23fmy4 34fmy5 35fmy6 26fOn nf12 3 4 5 6

9、7 8)()()(nynxnf1010)()(1)()(1)()(NlNllYlkXNlkYlXNnfDFSkF 由于由于DFS與與IDFS的對(duì)稱性，對(duì)周期序列乘的對(duì)稱性，對(duì)周期序列乘積，存在著頻域的周期卷積公式積，存在著頻域的周期卷積公式若若則則3.1.2 3.1.2 離散傅里葉變換（離散傅里葉變換（DFTDFT）一個(gè)有限長(zhǎng)序列一個(gè)有限長(zhǎng)序列 x(nx(n) )，長(zhǎng)為，長(zhǎng)為N N， 假定一個(gè)周期序列假定一個(gè)周期序列 ，它由長(zhǎng)度為，它由長(zhǎng)度為 N N 的有限長(zhǎng)序列的有限長(zhǎng)序列 x(nx(n) ) 延拓而成，它們的關(guān)系：延拓而成，它們的關(guān)系： nNnnxnx其余010)()()(nxrrNnxn

10、x)()( nRnxN)( nxnO765432181 nxnO765432181 nxnO7654321813nxnO7654321813nxnO765432181nO7654321816nxnO765432181 nx2 對(duì)于周期序列對(duì)于周期序列 ,定義其第一個(gè)周期定義其第一個(gè)周期n=0N-1，為為 的的“主值區(qū)間主值區(qū)間”，主值區(qū)間上的序列為，主值區(qū)間上的序列為主值序主值序列列 x(n)。 )(nx)(nx)(nxx(n)與與 的關(guān)系可描述為：的關(guān)系可描述為：)(nxx(n)是是 的主值序列的主值序列)(nx是是x(n)的周期延拓的周期延拓周期序列的主值區(qū)間與主值序列：周期序列的主值區(qū)間

11、與主值序列：RN（n）為矩形序列。）為矩形序列。符號(hào)（符號(hào)（n）N 是余數(shù)運(yùn)算表達(dá)式，表示是余數(shù)運(yùn)算表達(dá)式，表示 n 對(duì)對(duì) N 求余數(shù)。求余數(shù)。)()()()()(nRnxnRnxnxNNNNnxnx)()(例：例： 是周期為是周期為 N=8 的序列，求的序列，求 n=11 和和 n=-2 對(duì)對(duì) N的余數(shù)。的余數(shù)。)(nx68) 1(2n)3()11(xx解：解：38111n3)11(86)2(8)6()2(xx頻域上的主值區(qū)間與主值序列：頻域上的主值區(qū)間與主值序列：周期序列周期序列 的離散傅里葉級(jí)數(shù)的離散傅里葉級(jí)數(shù) 也是一個(gè)周也是一個(gè)周期序列，也可給它定義一個(gè)主值區(qū)間期序列，也可給它定義一個(gè)

12、主值區(qū)間 ，以及主值序列以及主值序列 X(k)。 )(nx)(kX10NkNNkXkXkRkXkX)()()()()(10)()()(NnknWnxnxDFSkX10)(1)()(NkknWkXNkXIDFSnx 這兩個(gè)公式的求和都只限于主值區(qū)間這兩個(gè)公式的求和都只限于主值區(qū)間（0N-1），它們完全適用于主值序列），它們完全適用于主值序列 x(n) 與與 X(k) ，因而我們可得到一個(gè)新的定義，因而我們可得到一個(gè)新的定義有限有限長(zhǎng)序列離散傅里葉變換定義。長(zhǎng)序列離散傅里葉變換定義。 x(n) 與與 X(k) 是一個(gè)有限長(zhǎng)序列離散傅里葉變換是一個(gè)有限長(zhǎng)序列離散傅里葉變換對(duì)，已知對(duì)，已知 x(n)

13、就能唯一地確定就能唯一地確定 X(k) ，同樣已知，同樣已知 X(k) 也就唯一地確定也就唯一地確定 x(n) ，實(shí)際上，實(shí)際上 x(n) 與與 X(k) 都是長(zhǎng)度都是長(zhǎng)度為為 N 的序列（復(fù)序列）都有的序列（復(fù)序列）都有N個(gè)獨(dú)立值，因而具有等個(gè)獨(dú)立值，因而具有等量的信息。量的信息。10)()()(10NkWnxnxDFTkXNnknN10)(1)()(10NnWkXNkXIDFTnxNkknN有限長(zhǎng)序列隱含著周期性。有限長(zhǎng)序列隱含著周期性。DFT的矩陣方程表示的矩陣方程表示) 1() 1 ()0(Nxxxx) 1() 1 ()0(NXXXX1112112421211111111NNNNNNN

14、NNNNNNNNWWWWWWWWWNW 12101111111111211242121NxxxxWWWWWWWWWNNNNNNNNNNNNNNNxWNxWXN 1210NXXXX111211242121111111111NNNNNNNNNNNNNNNNWWWWWWWWWNWXWx1N94643464442434241441111111WWWWWWWWWW例例1 求復(fù)數(shù)序列求復(fù)數(shù)序列 的的DFT jjjjnx1 , 22 , 21解：解：jjjj111111111111 jjjjjjjjXXXX122211111111111113210jj22264 10,304210NkenxWnxkXnnk

15、jNnnkN 直接利用定義求直接利用定義求解：解： 3000nenxX64j 3021nnjenxX2 302nnjenxX2 30233nnjenxX2j 232223210jjjexexexx 3210jxxjxxjjjjjj10120011111111111111X 0, 0, 1, 1nx jjkX1, 0,1, 2DFT特性：特性： 以下討論以下討論DFT的一些主要特性，這些特性的一些主要特性，這些特性都與周期序列的都與周期序列的DFS有關(guān)。有關(guān)。 假定假定x(n)與與y(n)是長(zhǎng)度為是長(zhǎng)度為N的有限長(zhǎng)序列，的有限長(zhǎng)序列，其各自的離散傅里葉變換分別為：其各自的離散傅里葉變換分別為：

16、X(k)=DFTx(n) Y(k)=DFTy(n)(1) 線性線性 DFTax(n)+by(n)=aX(k)+bY(k), a,b為任意為任意常數(shù)常數(shù)(2) 循環(huán)移位循環(huán)移位 有限長(zhǎng)序列有限長(zhǎng)序列x(n)的循環(huán)移位定義為：的循環(huán)移位定義為： f(n)=x(n+m)NRN(n)含義：含義：1) x(n+m)N 表示表示 x(n) 的周期延拓序列的周期延拓序列 的移位：的移位： 2) x(n+m)NRN(n) 表示對(duì)移位的周期序列表示對(duì)移位的周期序列 x(n+m)N 取主值序列取主值序列, 所以所以f(n)仍然是一個(gè)長(zhǎng)度為仍然是一個(gè)長(zhǎng)度為N的有限長(zhǎng)序列。的有限長(zhǎng)序列。f(n)實(shí)際上可看作序列實(shí)際上

17、可看作序列 x(n)排列在一排列在一個(gè)個(gè)N等分圓周上，并向左旋轉(zhuǎn)等分圓周上，并向左旋轉(zhuǎn) m 位。位。 )()(mnxmnxN循環(huán)移位循環(huán)移位)(nxn30) 2(nxn1N0)(nfn1N0) 2( nxn10循環(huán)移位（圓周移位）循環(huán)移位（圓周移位）移位前移位前左移兩位后左移兩位后n=0n=1n=2n=8n=0n=1n=2n=8n=7證：利用周期序列的移位特性：證：利用周期序列的移位特性：)()(kXWmnxDFSmnxDFSmkNN)()()(nRmnxDFTnfDFTNN)()()()()(kXwkRmnxDFSnRmnxDFTmkNNN序列循環(huán)移位后的序列循環(huán)移位后的DFT為為 kXWn

18、fDFTkFmkN 同樣，對(duì)于頻域有限長(zhǎng)序列同樣，對(duì)于頻域有限長(zhǎng)序列X(k)的循環(huán)的循環(huán)移位，有如下反變換特性：移位，有如下反變換特性： nxWkRlkXIDFTnlNNN（3）循環(huán)卷積）循環(huán)卷積)()()()()(10nRmnymxkFIDFTnfNNmN)()()()()(10nRmnxmykFIDFTnfNNmN kYkXkF若若則則或或證：這個(gè)卷積可看作是周期序列證：這個(gè)卷積可看作是周期序列 卷積后再卷積后再取其主值序列。取其主值序列。)()(nynx與)()()(kYkXkF1010)()()()()(NmNNNmmnymxmnymxnf)()()()()()(10nRmnymxnR

19、nfnfNNmNN10)()()()(NmNNnRmnxmynf將將F（k）周期延拓，得：）周期延拓，得：則根據(jù)則根據(jù)DFSDFS的周期卷積公式：的周期卷積公式：這一卷積過(guò)程與周期卷積比較，過(guò)程是一樣的，只是這一卷積過(guò)程與周期卷積比較，過(guò)程是一樣的，只是這里只取結(jié)果的主值序列，由于卷積過(guò)程只在主值區(qū)這里只取結(jié)果的主值序列，由于卷積過(guò)程只在主值區(qū)間間0mN-1內(nèi)進(jìn)行，所以內(nèi)進(jìn)行，所以 實(shí)際上就是實(shí)際上就是 y（m）的圓周移位，稱為）的圓周移位，稱為“循環(huán)卷積循環(huán)卷積”，習(xí)慣上常用，習(xí)慣上常用符號(hào)符號(hào)“ ”表示循環(huán)卷積，以區(qū)別于線性卷積。表示循環(huán)卷積，以區(qū)別于線性卷積。Nmny)( )()()()

20、()()()()()()(1010nxnynRmnxmynRmnymxnynxNNmNNNmN循環(huán)卷積過(guò)程循環(huán)卷積過(guò)程:1）由有限長(zhǎng)序列）由有限長(zhǎng)序列 x(n)、y(n) 構(gòu)造周期序列構(gòu)造周期序列)()(nynx與2）計(jì)算周期卷積）計(jì)算周期卷積 10)()()(Nmmnymxnf3）卷積）卷積 結(jié)果取主值結(jié)果取主值)()()(nRnfnfN nxnO nynO76655443322118 nRmnymxnfNNm10)()(11 mxmmy1my2my3mmy0 60)0()(0mmymxf1 60)1 ()(1mmymxf0 60)2()(2mmymxf1 23 fmy4 34 fmy5 3

21、5 fmy6 26 f ny例例3.2 設(shè)兩個(gè)有限長(zhǎng)序列相等，同為矩形序列設(shè)兩個(gè)有限長(zhǎng)序列相等，同為矩形序列 其他010121Nnnxnx求這兩個(gè)序列的循環(huán)卷積求這兩個(gè)序列的循環(huán)卷積解：矩形序列的解：矩形序列的DFT等于等于 10121NnknNWnxkXkX10NnknNW 其他00kN kXkXkY21 其他002kN kNX1 nxnxny21其他010NnN0 1 2 3 4nx(n)0 1 2 3 4n111 2 3 40n f(n)85 6 7y(n)y(n)55循環(huán)卷積的應(yīng)用：有限長(zhǎng)序列的線性卷積與循環(huán)循環(huán)卷積的應(yīng)用：有限長(zhǎng)序列的線性卷積與循環(huán)卷積卷積 實(shí)際問(wèn)題的大多數(shù)是求解線性

22、卷積，如信號(hào)實(shí)際問(wèn)題的大多數(shù)是求解線性卷積，如信號(hào)x(n)通過(guò)通過(guò)系統(tǒng)系統(tǒng)h(n)，其輸出就是線性卷積，其輸出就是線性卷積y(n)=x(n)*h(n)。而循環(huán)。而循環(huán)卷積比起線性卷積，在運(yùn)算速度上有很大的優(yōu)越性，它卷積比起線性卷積，在運(yùn)算速度上有很大的優(yōu)越性，它可以采用快速傅里葉變換（可以采用快速傅里葉變換（FFT）技術(shù)，若能利用循環(huán)）技術(shù)，若能利用循環(huán)卷積求線性卷積，會(huì)帶來(lái)很大的方便。卷積求線性卷積，會(huì)帶來(lái)很大的方便。 現(xiàn)在我們來(lái)討論上述現(xiàn)在我們來(lái)討論上述x(n)與與h(n)的線性卷積，如果的線性卷積，如果x(n)、h(n)為有限長(zhǎng)序列，則在什么條件下能用循環(huán)卷積代為有限長(zhǎng)序列，則在什么條件

23、下能用循環(huán)卷積代替而不產(chǎn)生失真。替而不產(chǎn)生失真。 0 1 2 3 4nx(n)0 1 2 3 4ny(n)mx(m)y(0-m)11m1 2 3 40nx(n)* y(n)y(1-m)y(4-m)85 6 7y(8-m)0 1 2 3 4nx(n)0 1 2 3 4n11y(n)y(n)1075 68 9y(0-m)10n f(n)51 2 3 4085 6 79y(1-m)10y(9-m)10在這區(qū)間以外不是在這區(qū)間以外不是x(m)=0，就是，就是y(n-m)=0，因而因而f(n)=0。因此，。因此，f(n)是一個(gè)長(zhǎng)度為是一個(gè)長(zhǎng)度為N+M-1的有限長(zhǎng)序列。的有限長(zhǎng)序列。mmnymxnynxn

24、f)()()(*)()(x(m)的非零區(qū)間：的非零區(qū)間： 0mN-1，y(n-m)的非零區(qū)間：的非零區(qū)間： 0n-mM-1，這兩個(gè)不等式相加，得：這兩個(gè)不等式相加，得： 0nN+M-2，有限長(zhǎng)序列的線性卷積：有限長(zhǎng)序列的線性卷積：假定假定x(n)為有限長(zhǎng)序列，長(zhǎng)度為為有限長(zhǎng)序列，長(zhǎng)度為N， y(n)為有限長(zhǎng)序列，長(zhǎng)度為為有限長(zhǎng)序列，長(zhǎng)度為M，它們的線性卷積它們的線性卷積f(n)也應(yīng)是有限長(zhǎng)序列。也應(yīng)是有限長(zhǎng)序列。mmnymxnynxnf)()()(*)()(循環(huán)卷積：循環(huán)卷積： 重新構(gòu)造兩個(gè)有限長(zhǎng)序列重新構(gòu)造兩個(gè)有限長(zhǎng)序列x(n)、y(n)，長(zhǎng)度均為，長(zhǎng)度均為L(zhǎng)maxN,M ，序列，序列x(n

25、)只有前只有前N個(gè)是非零值，后個(gè)是非零值，后L-N個(gè)為補(bǔ)充的零值；序列個(gè)為補(bǔ)充的零值；序列y(n)只有前只有前M個(gè)是非零值，個(gè)是非零值，后后L-M個(gè)為補(bǔ)充的零值。為了分析個(gè)為補(bǔ)充的零值。為了分析x(n)與與y(n)的循環(huán)的循環(huán)卷積，先看卷積，先看x(n)，y(n)的周期延拓：的周期延拓：rqrLnynyqLnxnx)()()()(1010)()()()()(LmLmLmnymxmnymxnf10)()(LmrmrLnymx其中其中f(n)就是線性卷積，也就是說(shuō)，就是線性卷積，也就是說(shuō)，x(n)、y(n)周期延拓后的周期卷積，是周期延拓后的周期卷積，是x(n)、y(n)線性卷積線性卷積的周期延拓

26、，周期為的周期延拓，周期為L(zhǎng)。它們的周期卷積序列為：它們的周期卷積序列為： rLmmrLnymx10)()(rrLnf)( 根據(jù)前面的分析，根據(jù)前面的分析，f(n)具有具有 N+M-1 個(gè)非零序列值，個(gè)非零序列值，因此，如果周期卷積的周期因此，如果周期卷積的周期 LN+M-1，那么，那么 f(n)周周期延拓后，必然有一部分非零序列值要重疊，出現(xiàn)期延拓后，必然有一部分非零序列值要重疊，出現(xiàn)混淆現(xiàn)象。只有混淆現(xiàn)象。只有 LN+M-1 時(shí)，才不會(huì)產(chǎn)生交疊。時(shí)，才不會(huì)產(chǎn)生交疊。這時(shí)這時(shí)f(n)的周期延拓的周期延拓 中每一個(gè)周期中每一個(gè)周期L內(nèi)，內(nèi)，前前N+M-1個(gè)序列值是個(gè)序列值是f(n)的全部非零序

27、列值，的全部非零序列值，而剩下的而剩下的L-(N+M-1)點(diǎn)的序列則是補(bǔ)充的零值。點(diǎn)的序列則是補(bǔ)充的零值。)(nfL循環(huán)卷積是周期卷積的主值序列：循環(huán)卷積是周期卷積的主值序列：周期卷積是線性卷積的周期延拓周期卷積是線性卷積的周期延拓)()()()()(nRnfnynxnfLLL)()(nRrLnfLr所以使循環(huán)卷積等于線性卷積而不產(chǎn)生混淆的必要所以使循環(huán)卷積等于線性卷積而不產(chǎn)生混淆的必要條件是：條件是：LN+M-1 利用循環(huán)卷積求線性卷積：利用循環(huán)卷積求線性卷積：第一步：補(bǔ)零；第一步：補(bǔ)零；第二步：求循環(huán)卷積第二步：求循環(huán)卷積(可利用可利用DFT)。X(k)=DFTx(n)Y(k)=DFTy(

28、n)F(k)=X(k) Y(k)f(n)=IDFT F(k)()()(1)()(10kRlkYlXNnfDFTkFNNlN)()()(110kRlkXlYNNNlN同樣，若同樣，若 nynxnf則則 kYkXN1（4）共軛對(duì)稱性）共軛對(duì)稱性 設(shè)設(shè) x*(n)為為 x(n)的共軛復(fù)數(shù)序列，則的共軛復(fù)數(shù)序列，則 DFTx*(n)=X*(-k)N RN (k) =X*(N-k)證：證： 10)(10*NkWnxnxDFTNnnkN*10)(NnnkNWnxknNknNnjknNnNNjknNnNNnkNNWWeWeWWW22)( )()(*10)(*kNXWnxnxDFTNnnkNN )()(*kR

29、kNXnxDFTNN)(kRN)(kRN說(shuō)明：說(shuō)明： 當(dāng)當(dāng)k=0時(shí)，應(yīng)為時(shí)，應(yīng)為X*(N-0)=X*(0)，因?yàn)榘炊x，因?yàn)榘炊xX(k)只有只有N個(gè)值，即個(gè)值，即0kN-1，而，而XN已超出主值已超出主值區(qū)間，但一般已習(xí)慣于把區(qū)間，但一般已習(xí)慣于把X(k)認(rèn)為是分布在認(rèn)為是分布在N等等分的圓周上，它的末點(diǎn)就是它的起始點(diǎn)，即分的圓周上，它的末點(diǎn)就是它的起始點(diǎn)，即XN= X0，因此仍采用習(xí)慣表示式，因此仍采用習(xí)慣表示式 DFTx*(n)=X*(N-k)以下在所有對(duì)稱特性討論中，以下在所有對(duì)稱特性討論中，XN均應(yīng)理解為均應(yīng)理解為XN=X0，同樣，同樣，x(N)=x(0)。 2.復(fù)序列的實(shí)部與虛部的

30、復(fù)序列的實(shí)部與虛部的DFT變換變換 以以Rex(n)和和Im x(n)表示序列表示序列x(n)的實(shí)部與虛部的實(shí)部與虛部 即即 x(n)=Rex(n)+jImx(n) 則則)()(21)(Im)()(21)(Re*nxnxnxjnxnxnx)()(21)(Re)(*nxnxDFTnxDFTkXe)()(21*kNXkX)()(21)(Im)(*nxnxDFTnxjDFTkXo)()(21*KNXkX共軛偶對(duì)稱分量共軛偶對(duì)稱分量共軛奇對(duì)稱分量共軛奇對(duì)稱分量對(duì)于純實(shí)數(shù)序列對(duì)于純實(shí)數(shù)序列 x(n)，即，即x(n)=Rex(n)，X(k)只有只有共軛偶對(duì)稱部分，即共軛偶對(duì)稱部分，即X(k)=Xe(k)，

31、表明實(shí)數(shù)序列的，表明實(shí)數(shù)序列的DFTDFT滿足共軛對(duì)稱性，利用這一特性，只要知道一半滿足共軛對(duì)稱性，利用這一特性，只要知道一半數(shù)目的數(shù)目的X( (k) )，就可得到另一半的，就可得到另一半的X( (k) )，這一特點(diǎn)在，這一特點(diǎn)在DFTDFT運(yùn)算中可以加以利用，以提高運(yùn)算效率。運(yùn)算中可以加以利用，以提高運(yùn)算效率。 根據(jù)根據(jù)x（n）與）與X（k）的對(duì)稱性，同樣可找到）的對(duì)稱性，同樣可找到X（k）的實(shí)）的實(shí)部、虛部與部、虛部與x（n）的共軛偶部與共軛奇部的關(guān)系。）的共軛偶部與共軛奇部的關(guān)系。 分別以分別以xe（n）及）及x0（n）表示序列）表示序列x（n）的圓周共軛偶部）的圓周共軛偶部與圓周共軛奇

32、部：與圓周共軛奇部：同樣應(yīng)從圓周意義上理解同樣應(yīng)從圓周意義上理解 x（N-0）=x（0）。）?？勺C明可證明: DFTxe（n）=ReX（k） DFTx0（n）=jImX（k） )()(21)()()(21)(*nNxnxnjxnNxnxnxoe（5）選頻性）選頻性 對(duì)復(fù)指數(shù)函數(shù)對(duì)復(fù)指數(shù)函數(shù) 進(jìn)行采樣得復(fù)序列進(jìn)行采樣得復(fù)序列 x(n) 0nN-1其中其中q為整數(shù)。當(dāng)為整數(shù)。當(dāng)0=2/N時(shí)，時(shí)，x(n)=ej2nq/N,其離散傅里葉變換其離散傅里葉變換為為njqoenx)(10/2/2)(NnNnkjNnqjeekXqkqkNeekXNkqjkqj011)(/ )(2)(2tjqoetx)(可見(jiàn)，

33、當(dāng)輸入頻率為可見(jiàn)，當(dāng)輸入頻率為q0時(shí)，變換時(shí)，變換X(K)的的N個(gè)值中只個(gè)值中只有有 X(q)=N，其余皆為零，如果輸入信號(hào)為若干個(gè)不，其余皆為零，如果輸入信號(hào)為若干個(gè)不同頻率的信號(hào)的組合，經(jīng)離散傅里葉變換后，不同同頻率的信號(hào)的組合，經(jīng)離散傅里葉變換后，不同的的k上，上，X(k)將有一一對(duì)應(yīng)的輸出，因此，離散傅里將有一一對(duì)應(yīng)的輸出，因此，離散傅里葉變換算法實(shí)質(zhì)上對(duì)頻率具有選擇性。葉變換算法實(shí)質(zhì)上對(duì)頻率具有選擇性。 例例 3.3 求求DFT：10,2cos)(NnNnqnx 解：解：NnqjNnqjeenx2221)(NqNnjNnqjee222110Nn nxDFTkX)(其他 0,2qNkq

34、kN（6）DFT與與Z變換變換 nnznxnxzX)()()(Z)()()()(10kXnxDFTWnxzXnNnkNWzkN10)()()(NnnkNWnxnxDFTkX10)(Nnnznx當(dāng)當(dāng) 時(shí)時(shí)kNWz10)()(NkzXkXkNWz102NkeWzkNjkNoooooooooooRezjImzo10)()(2NkeXkXkNj 10NnjnjenxeX 10102NkenxkXNnnkNj DFT與與DTFT變換變換X(k)k1N010)()(2NkeXkXkNj102NkkN2X(ej)0 是是z平面單位圓上幅角為平面單位圓上幅角為 的點(diǎn)，的點(diǎn)，即將即將z平面上的單位圓平面上的單位

35、圓N等分后的第等分后的第k點(diǎn)。點(diǎn)。NjkeXkX)(kNWkN21) X(k)也就是也就是z變換在單位圓上等間隔的采樣值。變換在單位圓上等間隔的采樣值。2) X(k)也可看作是對(duì)序列傅氏變換也可看作是對(duì)序列傅氏變換X(ej)的采樣，的采樣，采樣間隔為：采樣間隔為： N=2/N。即即結(jié)論：結(jié)論：思考：思考：1. 在一個(gè)序列的后面補(bǔ)零，序列的頻譜（在一個(gè)序列的后面補(bǔ)零，序列的頻譜（DTFT）是否發(fā)生變化？是否發(fā)生變化？2. 在一個(gè)序列的后面補(bǔ)零，序列的在一個(gè)序列的后面補(bǔ)零，序列的DFT是否發(fā)是否發(fā)生變化？生變化？（7）DFT形式下的形式下的Parseval定理定理當(dāng) x(n)=y(n)，即為有限長(zhǎng)

36、序列的能量1010*)()(1)()(NnNkkYkXNnynx101022| )(|1| )(|NnNkkXNnx利用循環(huán)卷積和共軛對(duì)稱特性，利用循環(huán)卷積和共軛對(duì)稱特性，可證明可證明DFT形式下的形式下的Parseval定律：定律： 當(dāng)當(dāng)y(n)= x(n)時(shí)，即為有限長(zhǎng)序列的能量時(shí)，即為有限長(zhǎng)序列的能量1010*)()(1)()(NnNkkYkXNnynx101022| )(|1| )(|NnNkkXNnx例例3.4 用序列用序列 ，驗(yàn)證，驗(yàn)證DFT形式下的形式下的Parseval定理。定理。 0 , 0 , 1 , 1nx解：解： jjkX1 , 0 ,1 , 2 302nnx21122

37、 30241nkX211011241222223.2 利用利用DFT做連續(xù)信號(hào)的頻譜分析做連續(xù)信號(hào)的頻譜分析 采樣采樣截短截短DFT)(ajX)(atx( )x n)(jeX( )( )( )NNxnx n Rn)(jNeX)(kXNkNjNeX2)( (1)混疊混疊 對(duì)連續(xù)信號(hào)對(duì)連續(xù)信號(hào)x(t)進(jìn)行數(shù)字處理前，要進(jìn)行采進(jìn)行數(shù)字處理前，要進(jìn)行采樣樣 采樣序列的頻譜是連續(xù)信號(hào)頻譜的周期延拓采樣序列的頻譜是連續(xù)信號(hào)頻譜的周期延拓，周期為，周期為fs，如采樣率過(guò)低，不滿足采樣定理，如采樣率過(guò)低，不滿足采樣定理，fs2fh，則導(dǎo)致頻譜混疊，使一個(gè)周期內(nèi)的，則導(dǎo)致頻譜混疊，使一個(gè)周期內(nèi)的譜對(duì)原信號(hào)譜產(chǎn)生

38、失真，無(wú)法恢復(fù)原信號(hào)，進(jìn)譜對(duì)原信號(hào)譜產(chǎn)生失真，無(wú)法恢復(fù)原信號(hào)，進(jìn)一步的數(shù)字處理失去依據(jù)。一步的數(shù)字處理失去依據(jù)。nanTttxnTx)()()(例例3.5 對(duì)連續(xù)時(shí)間信號(hào)對(duì)連續(xù)時(shí)間信號(hào) 分別按分別按 和和 采樣，比較原信號(hào)的頻譜采樣，比較原信號(hào)的頻譜和采樣信號(hào)的頻譜，觀察不同采樣頻率下的混和采樣信號(hào)的頻譜，觀察不同采樣頻率下的混疊。疊。 tuetxtaHzfs2Hzfs20 dtetxjXtjaa解：解：0dteetjtj11211jXa2211fjfXa nnjjenxeX采樣：采樣：0njnnTeejTee1122sincos11TTjeeeX nTxnxa nuenTTTee2cos21

39、0.81頻 率 f幅度 模 擬 信 號(hào) 頻 譜00.81頻 率 f幅度 fs=2Hzfs=20Hz （2） 泄漏泄漏 處理實(shí)際信號(hào)序列處理實(shí)際信號(hào)序列 x(n)時(shí)，一般總要將時(shí)，一般總要將它截?cái)酁橐挥邢揲L(zhǎng)序列，長(zhǎng)為它截?cái)酁橐挥邢揲L(zhǎng)序列，長(zhǎng)為N點(diǎn)，相當(dāng)于乘點(diǎn)，相當(dāng)于乘以一個(gè)矩形窗以一個(gè)矩形窗 w(n)=RN(n)。 矩形窗函數(shù)，其頻譜有主瓣，也有許多矩形窗函數(shù)，其頻譜有主瓣，也有許多副瓣，窗口越大，主瓣越窄，當(dāng)窗口趨于無(wú)窮副瓣，窗口越大，主瓣

40、越窄，當(dāng)窗口趨于無(wú)窮大時(shí)，就是一個(gè)沖擊函數(shù)。大時(shí)，就是一個(gè)沖擊函數(shù)。 時(shí)域的乘積對(duì)應(yīng)頻域的卷積，所以，加時(shí)域的乘積對(duì)應(yīng)頻域的卷積，所以，加窗后的頻譜實(shí)際是原信號(hào)頻譜與矩形窗函數(shù)頻窗后的頻譜實(shí)際是原信號(hào)頻譜與矩形窗函數(shù)頻譜的卷積，卷積的結(jié)果使頻譜延伸到了主瓣以譜的卷積，卷積的結(jié)果使頻譜延伸到了主瓣以外，且一直延伸到無(wú)窮。當(dāng)窗口無(wú)窮大時(shí)，與外，且一直延伸到無(wú)窮。當(dāng)窗口無(wú)窮大時(shí)，與沖擊函數(shù)的卷積才是其本身，這時(shí)無(wú)畸變，否沖擊函數(shù)的卷積才是其本身，這時(shí)無(wú)畸變，否則就有畸變。則就有畸變。 例如，信號(hào)為例如，信號(hào)為 ，是一單線譜，但當(dāng)加，是一單線譜，但當(dāng)加窗后，線譜與抽樣函數(shù)進(jìn)行卷積，原來(lái)在窗后，線譜與抽

41、樣函數(shù)進(jìn)行卷積，原來(lái)在0處的處的一根譜線變成了以一根譜線變成了以0為中心的，形狀為抽樣函數(shù)為中心的，形狀為抽樣函數(shù)的譜線序列，原來(lái)在一個(gè)周期（的譜線序列，原來(lái)在一個(gè)周期（s）內(nèi)只有一個(gè)）內(nèi)只有一個(gè)頻率上有非零值，而現(xiàn)在頻率上有非零值，而現(xiàn)在一個(gè)周期內(nèi)幾乎所有頻率上都有非零值，即一個(gè)周期內(nèi)幾乎所有頻率上都有非零值，即 的頻率成份從的頻率成份從0處處“泄漏泄漏”到其它頻率處去了。到其它頻率處去了。 考慮各采樣頻率周期間頻譜考慮各采樣頻率周期間頻譜“泄漏泄漏”后的互后的互相串漏，卷積后還有頻譜混迭現(xiàn)象產(chǎn)生。相串漏，卷積后還有頻譜混迭現(xiàn)象產(chǎn)生。nTje0Tjex例例3.6 一線性一線性IIR系統(tǒng)系統(tǒng)，

42、求系統(tǒng)的頻率響應(yīng)以及對(duì)，求系統(tǒng)的頻率響應(yīng)以及對(duì)h(n)截短后的頻率響截短后的頻率響應(yīng)，截短長(zhǎng)度分別為應(yīng)，截短長(zhǎng)度分別為16和和64，觀察截短后的頻譜，觀察截短后的頻譜變化。變化。 2198. 0z35. 111zzH0100200300-202系 統(tǒng) 的 沖 激 響 應(yīng)01234050100系 統(tǒng) 的 頻 響 函 數(shù)051015-202截 短 的 沖 激 響 應(yīng) N=160123401020截 短 后 N=16的 頻 響 函 數(shù)020406080-202截 短 的 沖 激 響 應(yīng) N=640123402040截 短 后 N=64的 頻 響 函 數(shù) （3）柵欄效應(yīng)）柵欄效應(yīng) N點(diǎn)點(diǎn)DFT是在頻率

43、區(qū)間是在頻率區(qū)間 0，2 上對(duì)信號(hào)上對(duì)信號(hào)頻譜進(jìn)行頻譜進(jìn)行N點(diǎn)等間隔采樣，得到的是若干個(gè)離點(diǎn)等間隔采樣，得到的是若干個(gè)離散的頻譜點(diǎn)散的頻譜點(diǎn) X(k)，且它們限制在基頻的整數(shù)，且它們限制在基頻的整數(shù)倍上，這就好像在柵欄的一邊通過(guò)縫隙看另倍上，這就好像在柵欄的一邊通過(guò)縫隙看另一邊的景象一樣，只能在離散點(diǎn)處看到真實(shí)一邊的景象一樣，只能在離散點(diǎn)處看到真實(shí)的景象，其余部分頻譜成分被遮擋，的景象，其余部分頻譜成分被遮擋， 所以稱所以稱之為柵欄效應(yīng)。之為柵欄效應(yīng)。 減小柵欄效應(yīng)方法：尾部補(bǔ)零，使譜線減小柵欄效應(yīng)方法：尾部補(bǔ)零，使譜線變密，增加頻域采樣點(diǎn)數(shù)，原來(lái)漏掉的某些變密，增加頻域采樣點(diǎn)數(shù)，原來(lái)漏掉的某

44、些頻譜分量就可能被檢測(cè)出來(lái)。頻譜分量就可能被檢測(cè)出來(lái)。l(4) DFT的分辨率的分辨率l填補(bǔ)零值可以改變對(duì)填補(bǔ)零值可以改變對(duì)DTFT的采樣密度，人的采樣密度，人們常常有一種誤解，認(rèn)為補(bǔ)零可以提高們常常有一種誤解，認(rèn)為補(bǔ)零可以提高DFT的頻率分辨率。事實(shí)上我們通常規(guī)定的頻率分辨率。事實(shí)上我們通常規(guī)定DFT的頻率分辨率為的頻率分辨率為 ，這里的，這里的N是指信是指信號(hào)號(hào)x(n)的有效長(zhǎng)度，而不是補(bǔ)零的長(zhǎng)度。不的有效長(zhǎng)度，而不是補(bǔ)零的長(zhǎng)度。不同長(zhǎng)度的同長(zhǎng)度的x(n)其其DTFT的結(jié)果是不同的；而的結(jié)果是不同的；而相同長(zhǎng)度的相同長(zhǎng)度的x(n)盡管補(bǔ)零的長(zhǎng)度不同其盡管補(bǔ)零的長(zhǎng)度不同其DTFT的結(jié)果應(yīng)是相

45、同的，他們的的結(jié)果應(yīng)是相同的，他們的DFT只是只是反映了對(duì)相同的反映了對(duì)相同的DTFT采用了不同的采樣密采用了不同的采樣密度。度。 Nfs/例例 3.7 設(shè)模擬信號(hào)設(shè)模擬信號(hào) 的最高頻率的最高頻率 ，試決定最低采樣頻率試決定最低采樣頻率 ，在這一采樣頻率下，在這一采樣頻率下采得采得256點(diǎn)數(shù)據(jù)，并對(duì)其作點(diǎn)數(shù)據(jù)，并對(duì)其作DFT，給了所能，給了所能得到的最大頻率分辨率得到的最大頻率分辨率 。 txaHzf5maxsff解：解：Hzffs102maxHzNffs039. 025610參數(shù)選擇的一般原則：參數(shù)選擇的一般原則： (1)若已知信號(hào)的最高頻率若已知信號(hào)的最高頻率 ，為防止混疊，選，為防止混疊

46、，選定采樣頻率定采樣頻率 ；(2)根據(jù)頻率分辯率根據(jù)頻率分辯率 ，確定所需，確定所需DFT的長(zhǎng)度的長(zhǎng)度(3) 和和N確定以后，即可確定相應(yīng)模擬信號(hào)的時(shí)間確定以后，即可確定相應(yīng)模擬信號(hào)的時(shí)間長(zhǎng)度長(zhǎng)度這里這里T是采樣周期。是采樣周期。maxfmax2ffsfffNs/NTfNs/sf3.2.2 連續(xù)周期信號(hào)的頻譜分析連續(xù)周期信號(hào)的頻譜分析 對(duì)于連續(xù)的單一頻率周期信號(hào)對(duì)于連續(xù)的單一頻率周期信號(hào) ， 為信號(hào)的頻率。為信號(hào)的頻率。 可以得到單一譜線的可以得到單一譜線的DFT結(jié)果，但這是和作結(jié)果，但這是和作DFT時(shí)數(shù)據(jù)的截取長(zhǎng)度選得是否恰當(dāng)有關(guān)，截取長(zhǎng)度時(shí)數(shù)據(jù)的截取長(zhǎng)度選得是否恰當(dāng)有關(guān)，截取長(zhǎng)度N選得合理

47、，選得合理， 可完全等于可完全等于 的采樣。的采樣。 )2sin()(tftxaaaf)(kXN)(ajX051015-1-0.500.51t/Tx(n)0510150246810kX(k)051015-1-0.500.51t/Tx(n)0510150246810kX(k)(a)(b)(c)(d)不同截取長(zhǎng)度的正弦信號(hào)及其DFT結(jié)果3.3 快速傅里葉變換快速傅里葉變換 （FFT） 快速傅里葉變換（快速傅里葉變換（FFT）是計(jì)算）是計(jì)算DFT的一種的一種快速有效方法?？焖儆行Х椒?。 從前面的討論中看到，有限長(zhǎng)序列在數(shù)字技從前面的討論中看到，有限長(zhǎng)序列在數(shù)字技術(shù)中占有很重要的地位。有限長(zhǎng)序列的一個(gè)

48、重術(shù)中占有很重要的地位。有限長(zhǎng)序列的一個(gè)重要特點(diǎn)是其頻域也可以離散化，即離散傅里葉要特點(diǎn)是其頻域也可以離散化，即離散傅里葉變換（變換（DFT）。）。 雖然頻譜分析和雖然頻譜分析和DFT運(yùn)算很重要，但在很長(zhǎng)運(yùn)算很重要，但在很長(zhǎng)一段時(shí)間里，由于一段時(shí)間里，由于DFT運(yùn)算復(fù)雜，并沒(méi)有得到運(yùn)算復(fù)雜，并沒(méi)有得到真正的運(yùn)用，而頻譜分析仍大多采用模擬信號(hào)真正的運(yùn)用，而頻譜分析仍大多采用模擬信號(hào)濾波的方法解決，直到濾波的方法解決，直到1965年首次提出年首次提出DFT運(yùn)運(yùn)算的一種快速算法以后，情況才發(fā)生了根本變算的一種快速算法以后，情況才發(fā)生了根本變化，人們開(kāi)始認(rèn)識(shí)到化，人們開(kāi)始認(rèn)識(shí)到DFT運(yùn)算的一些內(nèi)在規(guī)律

49、，運(yùn)算的一些內(nèi)在規(guī)律，從而很快地發(fā)展和完善了一套高速有效的運(yùn)算從而很快地發(fā)展和完善了一套高速有效的運(yùn)算方法方法快速傅里葉付里變換（快速傅里葉付里變換（FFT）算法。）算法。FFT的出現(xiàn)，使的出現(xiàn)，使DFT的運(yùn)算大大簡(jiǎn)化，運(yùn)算時(shí)的運(yùn)算大大簡(jiǎn)化，運(yùn)算時(shí)間縮短一二個(gè)數(shù)量級(jí)，使間縮短一二個(gè)數(shù)量級(jí)，使DFT的運(yùn)算在實(shí)際的運(yùn)算在實(shí)際中得到廣泛應(yīng)用。中得到廣泛應(yīng)用。DFT運(yùn)算的特點(diǎn)：運(yùn)算的特點(diǎn)： 每計(jì)算一個(gè)每計(jì)算一個(gè)X（k）值的計(jì)算量：）值的計(jì)算量：N次復(fù)數(shù)相乘，次復(fù)數(shù)相乘，N-1次復(fù)數(shù)相加次復(fù)數(shù)相加X(jué)（k）一共有）一共有N個(gè)點(diǎn)的計(jì)算量個(gè)點(diǎn)的計(jì)算量需要需要N2次復(fù)數(shù)相乘和次復(fù)數(shù)相乘和N（N-1）次復(fù)數(shù)相加）

50、次復(fù)數(shù)相加 又每個(gè)復(fù)數(shù)相加包括又每個(gè)復(fù)數(shù)相加包括2個(gè)實(shí)數(shù)相加，所以，每計(jì)算一個(gè)個(gè)實(shí)數(shù)相加，所以，每計(jì)算一個(gè) X（k）要進(jìn)行）要進(jìn)行4N次實(shí)數(shù)相乘和次實(shí)數(shù)相乘和2N+2（N-1）=2（2N-1）次實(shí)）次實(shí)數(shù)相加，因此，整個(gè)數(shù)相加，因此，整個(gè)DFT運(yùn)算需要運(yùn)算需要4N2實(shí)數(shù)相乘和實(shí)數(shù)相乘和2N（2N-1）次實(shí)數(shù)相加。次實(shí)數(shù)相加。 101, 1 , 0)()()(NnnkNNkWnxnxDFTkX)()()()()(10nkNemnkNmeNnnkNmmnkNeeWRnxIWInxRjWInxIWRnxRkX在在DFT計(jì)算中，不論是乘法和加法，運(yùn)算量均與計(jì)算中，不論是乘法和加法，運(yùn)算量均與N2成正比

51、。因此，成正比。因此，N較大時(shí)，運(yùn)算量十分可觀。例較大時(shí)，運(yùn)算量十分可觀。例，計(jì)算，計(jì)算N=10點(diǎn)的點(diǎn)的DFT，需要，需要100次復(fù)數(shù)相乘，而次復(fù)數(shù)相乘，而N=1024點(diǎn)時(shí)，需要點(diǎn)時(shí)，需要1048576（一百多萬(wàn)）次復(fù)數(shù)乘（一百多萬(wàn)）次復(fù)數(shù)乘法，如果要求實(shí)時(shí)處理，則要求有很高的計(jì)算速法，如果要求實(shí)時(shí)處理，則要求有很高的計(jì)算速度才能完成上述計(jì)算量。度才能完成上述計(jì)算量。 反變換反變換IDFT與與DFT的運(yùn)算結(jié)構(gòu)相同，只是多的運(yùn)算結(jié)構(gòu)相同，只是多乘一個(gè)常數(shù)乘一個(gè)常數(shù)1/N，所以二者的計(jì)算量相同。，所以二者的計(jì)算量相同。FFT算法的基本思想：算法的基本思想：系數(shù)系數(shù) 是一個(gè)周期函數(shù)是一個(gè)周期函數(shù) 系

52、數(shù)系數(shù) 具有對(duì)稱性具有對(duì)稱性nkNjnkNeW2)()(NknNNnkNknNWWW, 12/NNWnkNjnkNeW2nkNnNkNkNnNWWW)()(NkNkNWW*nkNW*kNkNkNNWWW利用這些周期性和對(duì)稱性，使利用這些周期性和對(duì)稱性，使DFT運(yùn)算中有些項(xiàng)可運(yùn)算中有些項(xiàng)可合并；合并；利用利用 的周期性和對(duì)稱性，把長(zhǎng)度為的周期性和對(duì)稱性，把長(zhǎng)度為N點(diǎn)的大點(diǎn)點(diǎn)的大點(diǎn)數(shù)的數(shù)的DFT運(yùn)算依次分解為若干個(gè)小點(diǎn)數(shù)的運(yùn)算依次分解為若干個(gè)小點(diǎn)數(shù)的DFT。因。因?yàn)闉镈FT的計(jì)算量正比于的計(jì)算量正比于N2，N小，計(jì)算量也就小。小，計(jì)算量也就小。FFT算法正是基于這樣的基本思想發(fā)展起來(lái)的。它算法正是

53、基于這樣的基本思想發(fā)展起來(lái)的。它有多種形式，但基本上可分為兩類：時(shí)間抽取法和有多種形式，但基本上可分為兩類：時(shí)間抽取法和頻率抽取法。頻率抽取法。nkNW3.3.1 3.3.1 按時(shí)間抽取的按時(shí)間抽取的FFTFFT（N N點(diǎn)點(diǎn)DFTDFT運(yùn)算的分運(yùn)算的分解）解） N=2M，M：正整數(shù)：正整數(shù) )()12()()2(21rxrxrxrx12, 2 , 1 , 0Nr2011)()(NnNnnkNnkNWnxWnx偶數(shù)奇數(shù)1, 1 , 0)()()(10NkWnxnxDFTkXNnnkN將將DFT運(yùn)算也相應(yīng)分為兩組：運(yùn)算也相應(yīng)分為兩組：120)12(1202) 12()2(NrkrNNrrkNWrx

54、Wrx12021202) 12()2(NrrkNNrkNrkNWrxWWrxnNnNjnNjnNWeeW222222 rkNNrkNNrrkNWrxWWrxkX21201202) 12()2(因?yàn)橐驗(yàn)樗运詒kNNrkNNrrkNWrxWWrx2120212021)()(10Nk 1202)2(NrrkNWrxkG rkNNrWrxkH2120) 12(設(shè)設(shè)12021)(NrrkNWrx12022)(NrrkNWrx12, 1 , 0Nk 12, 1 , 0NkkHWkGkXkN 12, 1 , 0,)2(NkkHWkGNkXkNrkNNkrNWW2)2(2 rkNNrkNNrrkNWrxW

55、WrxkX2120212021)()(kNNkNWW22212022120221)()(2NkrNNrNkNNrNkrNWrxWWrxNkX NkkHWkGkXkN, 12, 1 , 0,)2(NkkHWkGNkXkN依此類推，依此類推，G(k)和和H(k)可以繼續(xù)分下去，這種按時(shí)間抽可以繼續(xù)分下去，這種按時(shí)間抽取算法是在輸入序列分成越來(lái)越小的子序列上執(zhí)行取算法是在輸入序列分成越來(lái)越小的子序列上執(zhí)行DFT運(yùn)算，最后再合成為運(yùn)算，最后再合成為點(diǎn)的點(diǎn)的DFT。 蝶形信號(hào)流圖蝶形信號(hào)流圖將將G(k)和和H(k) 合成合成X(k)運(yùn)算可歸結(jié)為：運(yùn)算可歸結(jié)為： bWabWaWa+bWa-bW-W1a+b

56、Wa-bWWabab蝶形運(yùn)算的簡(jiǎn)化蝶形運(yùn)算的簡(jiǎn)化(a)(b)N=23=8 的例子的例子。 直接計(jì)算直接計(jì)算N點(diǎn)點(diǎn)DFT的計(jì)算工作量：的計(jì)算工作量：N2次復(fù)數(shù)乘法，次復(fù)數(shù)乘法，N(N-1)次復(fù)數(shù)加法次復(fù)數(shù)加法分成兩個(gè)分成兩個(gè)N/2點(diǎn)的點(diǎn)的N點(diǎn)點(diǎn)DFT的計(jì)算工作量：的計(jì)算工作量： 次復(fù)數(shù)乘法，次復(fù)數(shù)乘法， 次復(fù)數(shù)加法次復(fù)數(shù)加法22NN 22N按照這個(gè)辦法，繼續(xù)把按照這個(gè)辦法，繼續(xù)把N/2用除，由于用除，由于N=2M，仍然是偶數(shù)，可以被整除，因此可以對(duì)兩個(gè)仍然是偶數(shù)，可以被整除，因此可以對(duì)兩個(gè)N/2點(diǎn)的點(diǎn)的DFT再分別作進(jìn)一步的分解。即對(duì)再分別作進(jìn)一步的分解。即對(duì)G(k)和和H(k)的計(jì)算，又可以分

57、別通過(guò)計(jì)算的計(jì)算，又可以分別通過(guò)計(jì)算兩個(gè)長(zhǎng)度為兩個(gè)長(zhǎng)度為N/4=2點(diǎn)的點(diǎn)的DFT，進(jìn)一步節(jié)省計(jì)算，進(jìn)一步節(jié)省計(jì)算量，見(jiàn)圖。這樣，一個(gè)點(diǎn)的量，見(jiàn)圖。這樣，一個(gè)點(diǎn)的DFT就可以分解就可以分解為四個(gè)點(diǎn)的為四個(gè)點(diǎn)的DFT。 最后剩下的是最后剩下的是2點(diǎn)點(diǎn)DFT，它可以用一個(gè)蝶形結(jié)表示：，它可以用一個(gè)蝶形結(jié)表示：這樣，一個(gè)這樣，一個(gè)8點(diǎn)的完整的按時(shí)間抽取運(yùn)算的流圖點(diǎn)的完整的按時(shí)間抽取運(yùn)算的流圖由于這種方法每一步分解都是按輸入時(shí)間序列是屬由于這種方法每一步分解都是按輸入時(shí)間序列是屬于偶數(shù)還是奇數(shù)來(lái)抽取的，所以稱為于偶數(shù)還是奇數(shù)來(lái)抽取的，所以稱為“按時(shí)間抽取法按時(shí)間抽取法”或或“時(shí)間抽取法時(shí)間抽取法”。)

58、1 ()0() 1 ()0() 1 () 1 ()0() 1 ()0()0(1202xxxWxXxxxWxX按時(shí)間抽取的按時(shí)間抽取的8點(diǎn)點(diǎn)FFT時(shí)間抽取法時(shí)間抽取法FFTFFT的運(yùn)算特點(diǎn)：的運(yùn)算特點(diǎn)：（1）蝶形運(yùn)算）蝶形運(yùn)算（2）原位計(jì)算）原位計(jì)算 （3）序數(shù)重排）序數(shù)重排（4）蝶形類型隨迭代次數(shù)成倍增加）蝶形類型隨迭代次數(shù)成倍增加 （1）蝶形運(yùn)算）蝶形運(yùn)算對(duì)于對(duì)于N=2M，總是可以通過(guò)，總是可以通過(guò)M次分解最后成為次分解最后成為2點(diǎn)的點(diǎn)的DFT運(yùn)算。這樣構(gòu)成從運(yùn)算。這樣構(gòu)成從x(n)到到X(k)的的M級(jí)運(yùn)算過(guò)程。級(jí)運(yùn)算過(guò)程。從上面的流圖可看到，每一級(jí)運(yùn)算都由從上面的流圖可看到，每一級(jí)運(yùn)算都由

59、N/2個(gè)蝶形運(yùn)個(gè)蝶形運(yùn)算構(gòu)成。因此每一級(jí)運(yùn)算都需要算構(gòu)成。因此每一級(jí)運(yùn)算都需要N/2次復(fù)乘和次復(fù)乘和N次復(fù)次復(fù)加，這樣，經(jīng)過(guò)時(shí)間抽取后加，這樣，經(jīng)過(guò)時(shí)間抽取后M級(jí)運(yùn)算總共需要的運(yùn)算級(jí)運(yùn)算總共需要的運(yùn)算： 復(fù)乘復(fù)乘: 復(fù)加復(fù)加: NNNM2log22NNNM2log22 與直接計(jì)算相比較：與直接計(jì)算相比較：復(fù)乘：復(fù)乘：復(fù)加：復(fù)加： NNNNN222log2log2NNNNNN22log1log1N直接計(jì)算復(fù)乘次數(shù)直接計(jì)算復(fù)乘次數(shù)FFT計(jì)算復(fù)乘次數(shù)計(jì)算復(fù)乘次數(shù)比值比值864125.3325665,53610246410241,048,5765120204.820484,194,30411,2643

60、72.4（2）原位計(jì)算）原位計(jì)算 當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器中以后，每一級(jí)運(yùn)算當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器中以后，每一級(jí)運(yùn)算的結(jié)果仍然儲(chǔ)存在同一組存儲(chǔ)器中，直到最的結(jié)果仍然儲(chǔ)存在同一組存儲(chǔ)器中，直到最后輸出，中間無(wú)需其它存儲(chǔ)器，這叫原位計(jì)后輸出，中間無(wú)需其它存儲(chǔ)器，這叫原位計(jì)算。算。每一級(jí)運(yùn)算均可在原位進(jìn)行，這種原位運(yùn)算每一級(jí)運(yùn)算均可在原位進(jìn)行，這種原位運(yùn)算結(jié)構(gòu)可節(jié)省存儲(chǔ)單元，降低設(shè)備成本，還可結(jié)構(gòu)可節(jié)省存儲(chǔ)單元，降低設(shè)備成本，還可節(jié)省尋址的時(shí)間。節(jié)省尋址的時(shí)間。（3）蝶形類型隨迭代次數(shù)成倍增加）蝶形類型隨迭代次數(shù)成倍增加觀察觀察8點(diǎn)點(diǎn)FFT的三次迭代運(yùn)算的三次迭代運(yùn)算:第一級(jí)迭代，有一種類型的蝶形運(yùn)算系數(shù)第一