離散的傅里葉變換

1、 一、四種信號傅里葉表示一、四種信號傅里葉表示 1. 周期為周期為T0的連續(xù)時間周期信號的連續(xù)時間周期信號 n tn enXtx 0 j 0) ()( dtetx T nX tn T 0 0 j 0 0 )( 1 )( 頻譜特點： 離散非周期譜 deXtx t j )j ( 2 1 )( dtetxX t j )()j ( 頻譜特點： 連續(xù)非周期譜 deeXeXkx k jjj )( 2 1 )(IDTFT k k ekxkxeX j -j DTFT)( 頻譜特點： 周期為2的連續(xù)譜 mk N N m mk N N m WmX N emX N mXkx 1 0 2 j 1 0 1 1 IDFS

2、 km N N k mk N N k WkxekxkxmX 1 0 2 j - 1 0 DFS 頻譜特點：周期為N的離散譜 為了便于更好地理解DFT的概念，先討論周期序列及其 離散傅里葉級數(shù)（DFS）表示。 一個周期為N的周期序列，即 ， k為任意整數(shù)，N為周期 周期序列不能進行Z變換，因為其在 n=-到+ 都周而 復始永不衰減，即 z 平面上沒有收斂域。但是，正象連 續(xù)時間周期信號可用傅氏級數(shù)表達，周期序列也可用離散 的傅氏級數(shù)來表示，也即用周期為N的正弦序列來表示。 )( )( kNnxnx nNj ene /2 1 )( knNj k ene /2 )( 周期為N的正弦序列其基頻成分為：

3、 K次諧波序列為： knNjnNkNj ee /2)(/2 但離散級數(shù)所有諧波成分中只有N個是獨立的， 這是與連續(xù)傅氏級數(shù)的不同之處， 即 因此 )()(nene kNk 將周期序列展成離散傅里葉級數(shù)時，只需取 k=0 到 (N-1) 這N個獨立的諧波分量，所以一個周期序列的離 散傅里葉級數(shù)只需包含這N個復指數(shù)， 利用正弦序列的周期性可求解系數(shù) 。 將上式兩邊乘以 ，并對一個周期 求和 1 0 /2 )( 1 )( N K knNj ekX N nx )( kX rnNj e )/2( 1 0 1 0 )( 2 1 0 1 0 1 0 )( 22 )( 1 )( 1 )( N k N n nr

4、k N j N n N n N k nrk N jrn N j ekX N ekX N enx 1 11 )( 1 0 /)(2 )(2 N k Nrkj rkj e e N kX rk sNrk e N N n nrk N j 0 1 1 1 0 )( 2 ( 上式中 部分顯然只有當k=r時才有值為1,其他任意k值時均為 零,所以有 或寫為 1) 可求 N 次諧波的系數(shù) 2） 也是一個由 N 個獨立諧波分量組成的傅立葉級數(shù) 3） 為周期序列，周期為N。 )( )( 1 0 2 rXenx N n rn N j 10)( )( 1 0 2 NkenxkX N n kn N j )( kX )(

5、 kX )( kX )( )( )( )( 1 0 /2 1 0 )(/2 kXenx enxmNkX N n knNj N n nmNkNj 時域上周期序列的離散傅里葉級數(shù)在頻域上仍是一個 周期序列。 是一個周期序列的離散傅里葉級數(shù)(DFS) 變換對，這種對稱關系可表為： 習慣上：記 ， )( )( nxkX 1 0 /2 )( )( )( N n knNj enxnxDFSkX 1 0 /2 )( 1 )( )( N n nkNj ekX N kXIDFSnx Nj N eW /2 DFS變換對公式表明，一個周期序列雖然是無窮 長序列，但是只要知道它一個周期的內容（一個周期 內信號的變化情

6、況），其它的內容也就都知道了，所 以這種無窮長序列實際上只有N個序列值的信息是有 用的，因此周期序列與有限長序列有著本質的聯(lián)系。 1 0 1 0 )( )( 1 )( )( )( )( N k kn N N n kn N kXIDFSWkX N nx nxDFSWnxkX DFS 離散傅里葉級數(shù)變換 IDFS離散傅里葉級數(shù)反變換。 DDFS的幾個主要特性：的幾個主要特性： 假設 都是周期為 N 的兩個周期序列，各自的 離散傅里葉級數(shù)為： 1）線性）線性 a,b為任意常數(shù) )( )( nynx、 )( )( )( )( nyDFSkY nxDFSkX )( )( )( )( kYbkXanybn

7、xaDFS 2）序列移位）序列移位 證因為 及 都是以N為周期的函數(shù)， 所以有 )( )( )( )( nxwlkXIDFS kXwmnxDFS nl N mk N )( nx kn N w 1 0 1 )( )( )( N n mN mi km N ki N kn N wwixwmnxmnxDFS )( )( )( 1 0 1 kXwwixw wixw mk N N i ki N mk N mN mi ki N mk N 由于 與 對稱的特點，同樣可證明)( nx)( kX )( )( nxwlkXIDFS nl N 3）共軛對稱性共軛對稱性 對于復序列 其共軛序列 滿足 nx nx * k

8、Xnx * DFS kXWnx Wnxnx N n nk N N n nk N * 1 0 * 1 0 * )( ( )( DFS 證證: kXnx * DFS 同理同理: 進一步可得 )( )( 2 1 DFS 2 1 ReDFS * * kNXkX nxnxnx )( )( 2 1 ReDFS * e kNXkXkXnx 共軛偶對稱分量 )( )( 2 1 ImDFS * o kNXkXkXnxj 共軛奇對稱分量 4）周期卷積）周期卷積 若 則 或 )( )( )( kYkXkF 1 0 )( )( )( )( N m mnymxkFIDFSnf 1 0 )( )( N m mnxmy 周

9、 期 卷 積 證： 這是一個卷積公式，但與前面討論的線性卷積的差 別在于，這里的卷積過程只限于一個周期內（即 m=0N-1），稱為周期卷積。 例： 、 ，周期為 N=7, 寬度分別為 4 和 3 ，求周期卷積。 結果仍為周期序列，周期為 N 。 1 0 )( )( 1 )( )( )( N k kn N wkYkX N kYkXIDFSnf 1 0 1 0 )( )( 1 N k N m nk N mk N wkYwmx N 1 0 1 0 1 0 )( )( )( )( 1 )( N m N m N k kmn N mnymxwkY N mx )( nx )( ny )( )( )( nyn

10、xnf 1 0 1 0 )( )( 1 )( )( 1 )( )( N l N l lYlkX N lkYlX N nfDFSkF 由于DFS與IDFS的對稱性，對周期序列乘 積，存在著頻域的周期卷積公式， 若 則 我們知道周期序列實際上只有有限個序列值有意義，因此 它的許多特性可推廣到有限長序列上。 一個有限長序列 x(n)，長為N， 為了引用周期序列的概念，假定一個周期序列 ，它 由長度為 N 的有限長序列 x(n) 延拓而成，它們的關系： n Nnnx nx 其余0 10)( )( )( nx n Nnnx nx rNnxnx r 其它0 10)( )( )()( 周期序列的主值區(qū)間與主

11、值序列： 對于周期序列 ，定義其第一個周期 n=0N-1，為 的“主值區(qū)間”，主值區(qū)間上的序列為主值序列 x(n)。 x(n)與 的關系可描述為： 數(shù)學表示： RN（n）為矩形序列。 符號（n）N 是余數(shù)運算表達式，表示 n 對 N 求余數(shù)。 )( nx )( nx )( nx )( )( )()( 主值序列的是 的周期延拓是 nxnx nxnx )()()()( )( )()( nRnxnRnxnx nxnx NNN N )( nx )(nx 例： 是周期為 N=8 的序列，求 n=11 和 n=-2 對 N的余數(shù)。 因此 )( nx 6)2(68) 1(2 3)11(38111 8 8 n

12、 n )6()2( ),3()11( xxxx 周期序列 的離散付氏級數(shù) 也是一個 周期序列，也可給它定義一個主值區(qū)間 ，以及主值序列 X(k)。 數(shù)學表示： )( nx)( kX 10Nk N N kXkX kRkXkX )()( )()( )( 10)( )( )( 1 0 NkWnxnxDFSkX N n kn 10)( 1 )( )( 1 0 NnWkX N kXIDFSnx N n kn 再看周期序列的離散傅里葉級數(shù)變換（DFS）公式： 這兩個公式的求和都只限于主值區(qū)間（0N-1），它 們完全適用于主值序列 x(n) 與 X(k) ，因而我們可得到 一個新的定義有限長序列離散傅里葉變

13、換定義。 長度為N的有限長序列 x(n) ，其離散傅里葉變換 X(k) 仍是 一個長度為N 的有限長序列，它們的關系為： x(n) 與 X(k) 是一個有限長序列離散傅里葉變換對，已知 x(n) 就能唯一地確定 X(k) ，同樣已知 X(k) 也就唯一地確定 x(n) ，實際上 x(n) 與 X(k) 都是長度為 N 的序列（復序列）都 有N個獨立值，因而具有等量的信息。 有限長序列隱含著周期性。 10)( 1 )()( 10)()()( 1 0 1 0 NnWkX N kXIDFTnx NkWnxnxDFTkX N k kn N N n kn N 1. 線性線性 DFTDFTDFT 2121

14、 kxbkxakbxkax 需將較短序列補零后，再按長序列的點數(shù)做需將較短序列補零后，再按長序列的點數(shù)做DFT 2. 循環(huán)位移循環(huán)位移(Circular shift of a sequence) )(kRnkxky NN 循環(huán)位移定義為 xk, N=5 0 1 2 3 4 )( N kx -5 -4 -3 -2 -10123456789 )2( 5 kx -5 -4 -3 -2 -10123456789 55 )2(Rkx 01234 1 5 4 3 2 k=0 k=2 k=1 k=4 k=3 DFSmXWnkx mn N )(DFTmXWkRnkx mn NNN lmXkxWDFS lk N

15、 )(DFTmRlmXkxW NN lk N DFT頻域循環(huán)位移特性 周期共軛對稱(Periodic conjugate symmetry)定義為 周期共軛反對稱(Periodic conjugate antisymmetry)定義為 *)(*kNxkRkxkx NN *)(*kNxkRkxkx NN 當序列xk為實序列時，周期偶對稱序列滿足 kNxkx 當序列xk為實序列時，周期奇對稱序列滿足 kNxkx 對稱特性對稱特性 DFSmXkx DFSmXkx )(mXkRkxDFT NN )(DFTmRmXkx NN 當xk是實序列時 )(kRmXmX NN 4.循環(huán)卷積循環(huán)卷積 定 義 1 k

16、x N 2 kx)()( 21 1 0 kRnkxnx NNN N n xk,N=4 0123 1 2 3 4 hk 0123 1 0123 1 0123 1 0123 1 0123 1 xk 4 hk 0123 4 1 2 3 h(n)N h(1n)N h(2n)N h(3n)N 卷積定理卷積定理 DFT 2121 mXmXkxNkx 1 DFT 2121 mXNmX N kxkx m N j ez m N j k N kez zkxzXmX 2 2 |)( 1 0 km N N k ekx 2 j - 1 0 xk的 Xm等于其z變換X(z)在單位圓上等間隔取樣 設序列設序列xk的長度為的

17、長度為N k N k zkxzX )( 1 0 km N N k WkxmX 1 0 11 , 0;)( 2 NmzXmX m N j ez mXIDFTkx 變換Z )(zX m N N m N Wz mX N z zX 1 1 01 )1 ( )( (內插公式) 問題提出:DFT 2121 mXmXkxkx 實際需要： LTI系統(tǒng)響應 yk=x khk 可否利用DFT計算線性卷積？ 例：x1k=1,1,1, x 2k=1,1,0,1 , N=4 一、兩個有限長序列的線性卷積一、兩個有限長序列的線性卷積 , 2121 kxkxkxkx 5 4 3 2 1 0 y y y y y y 01 2

18、000 01 200 01 20 01 2 01 0 111 111 111 111 11 1 xxx xxx xxx xxx xx x 0 0 3 2 1 0 2 2 2 2 x x x x 111000 11100 1110 111 11 1 0 0 1 0 1 1 1 2 2 2 2 1 0 1 1 n 2 1 nx 3 0 1 1 n 2 2 nx 3 0 1 1 n 2 )2( 1 kRkx NN 3 0 1 1 n 2 )3( 1 kRkx NN 3 3 2 1 0 y y y y 0 1 2 3 30 1 2 2 30 1 1 2 30 1111 1111 1111 1111 x

19、xxx xxxx xxxx xxxx 3 2 1 0 2 2 2 2 x x x x 1110 0111 1011 1101 1 0 1 1 2 2 3 2 0 1 1 n 2 )( 1 nRnx NN 3 0 1 1 n 2 )1( 1 nRnx NN 3 0 1 1 n 2 )2( 1 kRkx NN 3 0 1 1 n 2 )3( 1 kRkx NN 30 1 1 n 2 )4( 1 kRkx NN 354 0 1 1 n 2 )5( 1 kRkx NN 3540 1 2 k 2 1 3 21 kxkx 54 5 4 3 2 1 0 y y y y y y 01 2000 001 200

20、 0001 20 00001 2 500001 540000 111 111 111 111 111 111 xxx xxx xxx xxx xxx xxx 0 0 3 2 1 0 2 2 2 2 x x x x 111000 011100 001110 000111 100011 110001 0 0 1 0 1 1 1 2 2 2 2 1 補LN零 補LM零 L點DFT L點DFT L點IDFT kx kh ky x1k h1k 11 khkxkhkx 直接計算與由DFT間接計算結果比較 若若x1k為為 M 點序列點序列, x2k為為L 點序列點序列 ， L M x1k L x2k中哪些點

21、不是線性卷積的點中哪些點不是線性卷積的點? k 1 kx M1 問題討論 n 1 nx M1 n 2 nx L1 )1( 1 nRnMx LL 0 k M 2不是線性卷積不是線性卷積 的結果，即前的結果，即前(M 1)個點個點 與線性卷積不一樣。與線性卷積不一樣。 )( 1 nRnx LL )1( 1 nRnx LL 0 1 2 1 0 3 2 1 0 1 2 0 0 1 0 2 1 0 1 0 1111 1111 111 111 111 11 1 xxMxMx xMxMxMx xxx xxMx xMxMx xx x 0 0 0 0 1 1 0 2 2 2 Lx x x T MLyMLyMyM

22、yMyyy 1 2 1 1 1 0 0 3 2 1 0 4 3 2 1 0 0 1 2 0 0 0 1 0000 0 2 1 2 1000 0 1 1 1 2000 0 1111 1111 111 111 111 1111 1111 xMxMxMx MxMxMxMx xxx xxMx xMxMx xMxxx xMxMxx 1 0 0 0 0 1 0 2 2 2 Lx x x T LyLyMyMyMyyy 12 1 1 1 0 x1k L x2k k=0 M 2, 前前M 1個點不是線性卷積的點個點不是線性卷積的點 k= M 1 L 1 , L M+1個點與線性卷積的點對應個點與線性卷積的點對應

23、 線性卷積線性卷積 L L+M 2 后后M 1點沒有計算點沒有計算 則則L點循環(huán)卷積點循環(huán)卷積 結論 若若x1k為為 M 點序列點序列, x2k為為L 點序列點序列 ， L M 長序列和短序列的線性卷積 直接利用直接利用DFT計算的缺點：計算的缺點： (1) 信號要全部輸入后才能進行計算，延遲太多信號要全部輸入后才能進行計算，延遲太多 (2) 內存要求大內存要求大 (3) 算法效率不高算法效率不高 解決問題方法：采用分段卷積解決問題方法：采用分段卷積 分段卷積可采用分段卷積可采用重疊相加法重疊相加法 和和 重疊保留法重疊保留法 1. 重疊相加（重疊相加（overlap add） 將長序列xk 分為若干段長度為L的序列 0 nLkxkx n n 0 10 其它 LknLkx kxn其中 0 khnLkxkhkx n n 0 nLkyn n y0k的非零范圍20MLk y1kL的非零范圍 22MLkL 序列 y0k, y1k的重疊部分2MLkL 重疊的點數(shù)L+M2L+1=M1 :khkxky nn 記 依次將相鄰兩段的依次將相鄰兩段的M-1個重疊點相加，即得到最終的個重疊點相加，即得到最終的 線性卷積結果。線性卷積結果。 重疊相加法分段卷積舉例重疊相加法分段卷積舉例 方法： (1) 將xk