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

1、第五章離散傅里葉變換及其快速算法1離散傅里葉變換(DFT)的推導(dǎo)(1)時(shí)域抽樣：目的：解決信號(hào)的離散化問題。效果：連續(xù)信號(hào)離散化使得信號(hào)的頻譜被周期延拓。(2)時(shí)域截?cái)啵涸颍汗こ躺蠠o法處理時(shí)間無限信號(hào)。方法：通過窗函數(shù)(一般用矩形窗)對(duì)信號(hào)進(jìn)行逐段截取。 結(jié)果：時(shí)域乘以矩形脈沖信號(hào), 頻域相當(dāng)于和抽樣函數(shù)卷積。(3)時(shí)域周期延拓：目的：要使頻率離散，就要使時(shí)域變成周期信號(hào)。方法：周期延拓中的搬移通過與 6(_遲)的卷積來實(shí)現(xiàn)。結(jié)果：周期延拓后的周期函表示：延拓后的波形在數(shù)學(xué)上可表示為原始波形與沖激串序列的卷積。數(shù)具有離散譜。經(jīng)抽樣.截?cái)嗪陀⑼睾?，信?hào)時(shí)域和頻域都是離散、周期的©過程

2、電圖圖1 DFT推導(dǎo)過程示意圖A1-I磔處理后信號(hào)的連續(xù)時(shí)間傅里葉變換：«(/)- x心NTs包)題步調(diào)旅淤凝神髓瞰，僅在離切頻跑相斕散序鼻處鬼幽帔尸醺N粉DFT璃散譜，簡(jiǎn)稱離 DFT =1余物感為0。W0E2 DFT及IDFT的與麋/2 郵三覬伙=0.1, 7-N-1)(3) IDFT定義：設(shè)川士是連續(xù)頻率函數(shù)lAT"的寬度為用的IDFT為：吟啊制T爭(zhēng)島嚴(yán)桃如心，心H(/)的N個(gè)抽樣值一0，？ JI|-1，這川個(gè)點(diǎn)/?-0? N7伙=0.1，3離散 譜的性Ns,散譜。(2)性質(zhì):(i)周期性：序列的 W點(diǎn)的DFT離散譜是周期為少中的序列。(ii) Im共扼對(duì)稱性：如果x(

3、nTs)(O<n<N)為實(shí)序列，則其川點(diǎn)的 DFT關(guān)于原點(diǎn)和臚2都具有 共覘對(duì)稱性。即Hn =H;一± k 22(iv)幅度對(duì)稱性：如果A<W75X0<K<TV)為實(shí)序列，則其 N點(diǎn)的DFT關(guān)于原點(diǎn)和N/2都具有幅度對(duì)稱性。即網(wǎng)卜億I;日勺卜|日勺| ;律士廠松寸(3)改寫：(1) 簡(jiǎn)記力0迅？)為h(n)(ii)簡(jiǎn)記 |命|為川幻DPT(iii) DFT 對(duì)簡(jiǎn)記為：Zj(n) o H(k)或 hgoH(k)A(iv) H(k)=DFrli(n)= AhWN ?伙=(M,?,N-1)n-01 N-l(v) /心)=DFT?"伙)=三另"

4、;("怕叭 5 = 0L, N l)4 DFT總結(jié)(1) DFT的定義是針對(duì)任意的離散序列血G)中的有限個(gè)離散抽樣(0<n<N)的，它并不要 求該序列具有周期性。(2)由DFT求出的離散譜H(k) = H ktHA r(keZ)是離散的周期函數(shù)，周期為% = Nrr° =NM=人、 離散間隔為-J- = 4=Ar =從離散譜關(guān)于變?cè)?amp;的周期為NTs i s NTsNlo(3) r如果稱離散譜經(jīng)過IDFT所得到的序列為重建信號(hào)，xSGMwZ),則重建信號(hào)是離散 的周期函數(shù)，周期為NTf =，(對(duì)應(yīng)離散譜的離散間隔的倒數(shù))、離散間隔為JoT嚴(yán)NTJN = n

5、 = $-(對(duì)應(yīng)離散譜周期的倒數(shù))。(5)經(jīng)IDFT重建信號(hào)的基頻就是頻域的離散間隔，或時(shí)域周期的倒數(shù)，為 /o=-a = -!-o幾NTS(6)實(shí)序列的離散譜關(guān)于原點(diǎn)和上(如果2是偶數(shù))是共輪對(duì)稱和幅度對(duì)稱的。因此，真正2有用的頻譜信息可以從 0辛-1范圍獲得，從低頻到高頻。(7)在時(shí)域和頻域0"范圍內(nèi)的小中點(diǎn)分別是各自的主值區(qū)間或主值周期。-Af(l</n<M )，有(1)線性U-im-l性：對(duì)5 DFT性質(zhì)(2) 奇偶虛實(shí)性：(i) DFT的反褶、平移：先把有限長(zhǎng)序列周期延拓，再作相應(yīng)反褶或平移，最后取主 值 區(qū)間的序列作為最終結(jié)果。(ii) DFT有如下的奇偶虛實(shí)

6、特性：奇O奇；偶O偶；實(shí)偶O實(shí)偶；實(shí)奇O虛奇；實(shí)0(實(shí)偶)+ j(實(shí)奇)；實(shí)O(實(shí)偶)？ EXP(實(shí)奇)反褶和共覘性：時(shí)域頻域反褶反褶共扼共覘+反褶共扼+反褶共犯(5)對(duì)偶性：XS)u>AM-R)(i)把耦散譜序列當(dāng)成時(shí)域序列進(jìn)行DFT,結(jié)果是原時(shí)域序列反褶的川倍；(ii):(uo如果原序列具有偶對(duì)稱性，則DFT結(jié)果是原肘域序列的倍。(6)時(shí)移性：叱護(hù)。序列的時(shí)移不影響DFT離散譜的幅度。(7)頻移性：心)林N oX( -/)(8)時(shí)域離散圓卷積定理：x(n)?y(n)AX(k)Y(k)(i)圓卷積：周期均為用的序列 x()“與yS)之間的圓卷積為AM.？ y(/T )=- i)J-0心

7、)仍是/?的序列，周期為M(ii)非周期序列之間只可能存在線卷積，不存在圓卷積；周期序列之間存在圓卷積，但不存在線卷積。(9)頻域離散圓卷積定理：.g)yS)o，X伙)？ 丫(燈(10)時(shí)域耦散圓相關(guān)定理：/<學(xué)(0X(幻廠伙)JV-1周期為少中的序列.附)和y(n)的圓相關(guān)：/W(.g), y(/O ) =R ； f)(")=rU)是"的序列，周期為M(11) /Kh) = 1d?7； /*(Z ； 其中DFT表示按斤進(jìn)行 DFT運(yùn)算。(12)帕斯瓦爾定理：另|心)二1習(xí)|x伙)n-0"Jt-06快速傅里葉變換FFT(1) FFT不是一種新的變換，而是 D

8、FT的快速算法。(2)直接DFT計(jì)算的復(fù)雜度：O(N2)計(jì)算DFT需要：NAN = N2次復(fù)數(shù)乘法；N*N = N?次復(fù)數(shù)加法。(3) FFT算法推導(dǎo)：(i)第L次迭代中對(duì)偶結(jié)點(diǎn)值的計(jì)算公式為：(心尸xi (心)+ Xu (/Q )W#(心尸 A£(Ki) - xq (心)WA1，心是循環(huán)控制變量。KL-KL=2r-L=A-RabR(Kl?(r-L)(ii) 對(duì)偶結(jié)點(diǎn)的關(guān)系如圖2所示:圖2 FFT中對(duì)偶結(jié)點(diǎn)關(guān)系圖(iii) 族轉(zhuǎn)因子：被稱為旋轉(zhuǎn)因子，可預(yù)先算好弁保存。(iv) 整序：經(jīng)過r次迭代后，得到結(jié)果Xr(Mr-Vi)J?實(shí)際結(jié)果應(yīng)是X(?T "o)J,所以 流程的最

9、后一步是按下標(biāo)的正常二進(jìn)制順序?qū)Y(jié)果進(jìn)行整序。(4) FFT 算法特點(diǎn):(N = 2)(i)共需廠次迭代；(ii)第U<L<r)次迭代對(duì)偶結(jié)點(diǎn)的偶距為因此一組結(jié)點(diǎn)覆蓋的序號(hào)個(gè)數(shù)是2(Kl-Kl)=-八,(iii) 第U<L<r)次迭代結(jié)點(diǎn)的組數(shù)為 NA1(K l -K l)= 2 Ll。(iv) 可以預(yù)先計(jì)算好，而且巳的變化范圍是0號(hào)-1。(5) FFT 算法流程：(N = 2 r)(i) 初始化：a*o(?)< A</0-0<n<N- ;(ii) -w第L(<L<r)次迭代:(a)下標(biāo)控制變量初始化忑=0;(b)“結(jié)點(diǎn)對(duì)”的個(gè)數(shù)初始化陽代0;N(C) WHILEAunADO按對(duì)偶結(jié)點(diǎn)對(duì)的計(jì)算公式進(jìn)行置位運(yùn)算，得到耳(KJ和丑(應(yīng))的值；KL K) +1 ; num<- nunH- ;跳過已經(jīng)計(jì)算過的結(jié)點(diǎn)(即上面應(yīng)所對(duì)應(yīng)的那些結(jié)點(diǎn)):K/+ = N/2s如果 K(<N,轉(zhuǎn)到b)繼續(xù)計(jì)算下一組結(jié)點(diǎn)；否則結(jié)束本次迭代。(iv)當(dāng)r次迭代全部完成后，對(duì)結(jié)果*1伙XOdSN-l)按下標(biāo)二進(jìn)制位進(jìn)行整序，從而得到結(jié)果X伙XOSSN-l)。(6) FFT算法復(fù)雜度分析：(N = 2，叭預(yù)先算好)(i) 一個(gè)對(duì)偶結(jié)點(diǎn)對(duì)的計(jì)算需要 2次復(fù)數(shù)加法和1次復(fù)數(shù)