離散傅立葉變換及其快速算法1ppt課件

1、)(),()(為整數(shù)rrNnxnxnkjNe2)(nxN20njnjNeene20)(1nkjnkjkNeene20)()()(22)(neeeneknkjrNknjrNkNNnkjNe2nkjNe2)(nxNNjNNnnkjeWekXNnx2210)(1)(記即NjNeW2)(rNnNnNWW*)(nNnNWWnNrnrNWW011)(110)(10*NnnkmNNnmnNknNWNWWNkmkm10)()()(NnnkNWnxkXnxDFS正變換正變換)( k10)(1)()(NknkNWkXNnxkXIDFS反變換反變換)( k顯然具有周期性)(nx分解成分解成N N個離散的諧波分量的加

2、權和，各諧波的頻率為個離散的諧波分量的加權和，各諧波的頻率為 ，Nk2幅度為幅度為 ，其中，其中)(1kXN1, 1 ,0Nk留意：留意： 和和 都可取任何整數(shù)值，這闡明都可取任何整數(shù)值，這闡明 和和 都是無都是無限長的，但由于它們的周期性，只需求知道一個周期，其限長的，但由于它們的周期性，只需求知道一個周期，其它周期可經(jīng)過周期延拓得到。它周期可經(jīng)過周期延拓得到。kn)(kX)(nx1 1、線性性、線性性)()()()(2211nxDFSkXnxDFSkX若)()()()(22112211kXakXanxanxaDFS則2 2、移位性、移位性)()(nxDFSkX若)()(kXWmnxDFSm

3、kN則3 3、頻域移位調(diào)制性、頻域移位調(diào)制性)()(nxDFSkX若)()(lkXnxWDFSnlN則4 4、周期卷積定理、周期卷積定理)(1nx)(2nx)()()()()(211021nxnxmnxmxnyNm周期卷積與第二章所討論的線性卷積不同，其特點是： 和 都是周期為N的序列。、)(1nx)(2nx)(ny留留意意)()(11nxDFSkX若)()()()(21kXkXnyDFSkY則)()(22nxDFSkX5 5、頻域周期卷積定理、頻域周期卷積定理)()()(21nxnxny若)()(1)()(1)()(211021kXkXNlkXlXNnyDFSkYNl則)(1nx)(2nx)

4、()(21mxmx和)(ny序列傅立葉變換存在的條件是滿足絕對可和或平方可和，但對周期序列這兩個條件都不滿足，由于當 時，序列的值或平方值都不趨于0。假設引入頻域的沖擊函數(shù) ，也可求得其傅立葉變換。n)()(nx)2()(2)(NkkXNeXkj1021)(1)()(NnNnkjjekXNeXFnx參見P87頁例題問題的引入：問題的引入：由第二章曾討論過的“序列的傅立葉變換我們知道：序列的傅立葉變換就是序列的頻譜，它是數(shù)字頻率 的延續(xù)變量函數(shù)，且序列的長度不受限制。但在實踐利用計算機或數(shù)字設備進展頻譜分析時，只能處置有限長數(shù)據(jù)且必需將 離散化。有限長序列的傅立葉變換及頻率離散化問題離散傅立葉變

5、換DFT有限長序列的離散傅立葉變換有限長序列的離散傅立葉變換離散傅立葉變換的性質(zhì)離散傅立葉變換的性質(zhì)離散頻率、數(shù)字頻率和模擬頻離散頻率、數(shù)字頻率和模擬頻率間的關系率間的關系)(nx10)()()(NnnjjenxnxFeX上式中僅管 是離散序列，但 卻是延續(xù)變量，且 是 的周期為 的周期函數(shù)，故實踐上只需計算 在區(qū)間 上的值。同時，由于 為延續(xù)變量，在 中有無限多個點，而實踐只能計算有限個點，故必需將 離散化。)(nx)(jeX2)20)20)20Nkk21, 1 ,0)()(102NkenxeXNnknNjjk定義式，令)()(kjeXkXNjNeW2并記1, 1 , 0)()()(10Nk

6、WnxnxDFTkXNnnkN則其中 為序列 在離散頻率點 上的頻譜值。 )(kX)(nxNkk21, 1 , 0)()()(10NkWnxnxDFTkXNnnkN有限長序列 的離散傅立葉變換簡稱DFT的意義：)(nx1、 為序列 在離散頻率點 上的頻譜值。 )(kX)(nxNkk22、 相當于頻譜 在 范圍內(nèi)實施了等間隔采樣，采樣間隔為)(kX)(jeX)2 , 0N21, 1 , 0)(1)()(10NnWkXNkXIDFTnxNknkN據(jù)DFT和IDFT的定義知：)()(nxmNnx)()(kXmNkX有限長序列的有限長序列的DFTDFT是是 的周期序列，周期為的周期序列，周期為N N；

7、 而由而由IDFTIDFT所求得的所求得的 也變成了一個周期為也變成了一個周期為N N的周期的周期序列，即經(jīng)過序列，即經(jīng)過IDFTIDFT將原將原 進展了周期延拓。進展了周期延拓。k)(nx)(nx將由有限長序列 以N為周期進展延拓后所得的序列記為 ，并稱原 為 的主值區(qū)。其中 表示 對N除法求余，即假設 那么)(nxNnx)()(nxNnx)(Nn)(n為整數(shù)MNnnMNn, 10 ,111)(nnN)5()5()1()9(888xxxxN，則，例如：)11()5()9()9(161616xxxxN，則)(nx)(nx)(kX)(kX( )( )()X kXkX krNNrX kXkRkNN

8、()()()(nx10)()(NnnznxzX10)()()(22NkzXeXkXkNjezkNj)(nx)(nx)(nx)(nx( )( )()x nxnx nrNNrx nxnRnNN()()()知 ，分別求 和 時的 。 )()(4nRnx8N16N)(kX解：解：30708241082)()()(nknjnknjnkNNneenRWnxkX時8N)8/sin()2/sin(118382824kkeeekjkjkj)7, 1 ,0(k時16N30150162410162)()()(nknjnknjnkNNneenRWnxkX)16/sin()4/sin(111631621624kkeee

9、kjkjkj)15,1 ,0(k由該例可知：頻率采樣點數(shù)不同，由該例可知：頻率采樣點數(shù)不同，DFT的的長度不同，長度不同，DFT 的結果也不同。的結果也不同。1 1、線性性、線性性21aa、假設x(n)與y(n)是同樣長的序列，那么對任何實數(shù)或復數(shù)有： )()()()(2121nyDFTanxDFTanyanxaDFT2 2、循環(huán)移位性、循環(huán)移位性)()()(nRmnxnyNN假設x(n) 是長為n的有限長序列，定義： 為 的循環(huán)移位序列。)(nx循環(huán)移位的本質(zhì)：將原循環(huán)移位的本質(zhì)：將原序列序列 左移左移 位，而位，而移出主值區(qū)的各序列值移出主值區(qū)的各序列值又依次從右側(cè)進入主值又依次從右側(cè)進入

10、主值區(qū)。區(qū)。)(nxm)()(nxDFTkX若)()()(kXWnyDFTkYmkN則)()()(nRmnxnyNN設)()(nxDFTkX若)()()(nxWkYIDFTnynlN則)()()(kRlkXkYNN3、頻域移位定理、頻域移位定理的共軛復序列為設)()(nxnx4、共軛復序列的、共軛復序列的DFT)()()(kRkNXnxDFTNN則5、共軛對稱性、共軛對稱性)()()(njxnxnxir設)()(21)(*nxnxnxr)()(21)(*nxnxnjxi實部虛部虛部)()(21)()(*nxnxDFTnxDFTkXre)()(21*kNXkX)()(21)()(*nxnxDFT

11、njxDFTkXio)()(21*kNXkX)()(kNXkXee共軛對稱性則)()(kNXkXoo共軛反對稱性闡明：闡明： 和和 均是有限長序列，定義區(qū)間為均是有限長序列，定義區(qū)間為0N-1，與第二章中的對稱性不同，這里所謂的對稱是，與第二章中的對稱性不同，這里所謂的對稱是指關于指關于N/2點的對稱，而不是關于原點的對稱。點的對稱，而不是關于原點的對稱。)(kX)(nx特別地：特別地：)()(*kNXkX)()(*kNXkX)(nx)(nx設 ， 和 為實序列，知求: 和)()()(njynxnf)(nx)(nyjNkFnf1)()()(nx)(ny解：解：)()()()(21)()()()

12、()(21)(*kjNRkRkNFkFnjyDFTkRkRkNFkFnxDFTNNNNNN)()()()(1)(1)()(1010nNkYIDFTnynWNWkXNkXIDFTnxNkknNNkkNN6、循環(huán)卷積定理、循環(huán)卷積定理)(1nx)(2nx1, 1 , 0, )()()()(1021NnnRmnxmxnyNmNN)()()()(1221nxnxnxnx)()(11nxDFTkX若)()(22nxDFTkX)()()()(21kXkXnyDFTkY則7、頻域循環(huán)卷積定理、頻域循環(huán)卷積定理)()()(21nxnxny若)()(1)()(21kXkXNnyDFTkY則)2()(),()(4

13、241nRnxnRnx)(ny解：解：)(),(21nxnx)(),(21mxmxNmx)(2)(2mxNmx)(2)()(2mRmnxNN)(1mx)()(2mRmnxNNNmx)(28、循環(huán)相關定理、循環(huán)相關定理)(nx)(ny1, 1 , 0)()()()(10NnnRmnymxnrNmNNxy)(nx)(ny)()(nxDFTkX若)()(nyDFTkY)()()()(kYkXnrDFTkRxyxy則9、Parseval定理定理102| )(|Nnnx210| )(|1kXNNkf)(2ffsffT2 的取值范圍：20或2/sf 就是離散信號數(shù)字頻率能取的最高頻率 此時，雖然信號在時域

14、時離散的，但此時，雖然信號在時域時離散的，但 依然是延續(xù)的依然是延續(xù)的留意留意10NkkNffkNks2kkf以上所討論的三種頻率變量之間的關系，在對模擬信號進展數(shù)字處置以及利用模擬濾波器設計數(shù)字濾波器乃至整個數(shù)字信號處置中非常重要，望同窗們高度注重。頻域采樣不失真恢復的條件頻域采樣不失真恢復的條件內(nèi)插公式內(nèi)插公式問題的提出：問題的提出：時域：時域：)(tx)(nx經(jīng)過滿足經(jīng)過滿足“時域采樣定理的采時域采樣定理的采樣樣頻域：頻域：)(jeX)(kX？)(nxLnnjjenxeX)()(10NknnkNWnxkX)()(頻域采樣頻域采樣) 10)()(NnkXIDFTnxN令欲恢復原信號，即)(

15、)(nxnxN)()()(nxDFTkXkXN)()()(kRkXkXN)()()(kXIDFTnxnxNN)()()(nRnxnxNNnkNNknkNNkWkXNWkXNnx1010)(1)(1)(取主值區(qū) 10)(1NknkNmmkNWWmxNmNkknmNWmxN10)()(1x nrNr()(nxNrNnRrNnx)()()(nxN)(nx10)()(NnnkNWnxkX10)(1)(NknkNWkXNnx10)()(NnnznxzX1010)(1NnnNknkNzWkXNnNkNnnkNzWkXN1010)(110111)(1NkkNNNkNzWzWkXN1011)(1NkkNNzWkXNz10)()(NkkzkX1111)(zWzNzkNNk其中10)()()()(NkjkezjekXzXeXj)2(111)(NkjNjjkeeNe222/ )2sin()2sin(1NkNjeNkNN)2(Nk2)1(2/)sin()2sin(1)(NjeNN其中22sin)sin()(ttTtTttgss時域采樣定理中的內(nèi)插函數(shù)類似類似以上所討論的兩種情形的內(nèi)插公式是用頻域采樣法設計F