首页 A. Basics of Discrete Fourier Transform

A. Basics of Discrete Fourier Transform

举报
开通vip

A. Basics of Discrete Fourier Transform A. Basics of Discrete Fourier Transform A.1. Definition of Discrete Fourier Transform (8.5) A.2. Properties of Discrete Fourier Transform (8.6) A.3. Spectral Analysis of Continuous-Time Signals Using Discrete Fourier Transform (10.1, 10.2) A.4. Convolut...

A. Basics of Discrete Fourier Transform
A. Basics of Discrete Fourier Transform A.1. Definition of Discrete Fourier Transform (8.5) A.2. Properties of Discrete Fourier Transform (8.6) A.3. Spectral Analysis of Continuous-Time Signals Using Discrete Fourier Transform (10.1, 10.2) A.4. Convolution Using Discrete Fourier Transform (8.6, 8.7) A.5. Sampling of Discrete-Time Fourier Transform (8.4, 8.5) A.1. Definition of Discrete Fourier Transform Let x(n) be a finite-length sequence over 0nN1. The discrete Fourier transform of x(n) is defined as (A.2) is called the inverse discrete Fourier transform. A.1.1. Derivation of Inverse Discrete Fourier Transform Let us derive (A.2) from (A.1). (A.1) is rewritten as .1Nn0, kn N 2 jexpX(k) N 1 x(n) 1N 0k            .1Nk0, kn N 2 jexpx(n)X(k) 1N 0n           Note that X(k) is a finite-length sequence over 0kN1. x(n) can be reconstructed from X(k), i.e., (A.1) (A.2) 1.Nk0 ,km N 2 jexp)m(x)k(X 1N 0m           (A.3) .)mn(k N 2 jexp)m(xkn N 2 jexp)k(X 1N 0k 1N 0m 1N 0k                       Multiplying both the sides of (A.3) by exp(j2kn/N), 0nN1, and then summing both the sides with respect to k, we obtain (A.4) Changing the order of the two summations on the right side of (A.4), we obtain .)mn(k N 2 jexp)m(xkn N 2 jexp)k(X 1N 0m 1N 0k 1N 0k                        (A.5) Since , nm 0, nm ,N )mn(k N 2 jexp 1N 0k                 (A.6) .N)n(xkn N 2 jexp)k(X 1N 0k           (A.7) (A.2), the inverse discrete Fourier transform, is derived by dividing both the sides of (A.7) by N. A.1.2. Relation of Discrete Fourier Transform to Discrete-Time Fourier Series Let us assume that X(k) is the discrete Fourier transform of x(n), x(n) is x(n) extended with period N, and X(k) is the discrete-time Fourier series coefficient of x(n). Then, X(k) is equal to X(k) over period 0kN1 multiplied by N, i.e., X(k)=NX(k), 0kN1. (A.8) Figure A.1 illustrates this relation. we obtain …… n x(n) n x(n) k X(k) k X(k) …… Figure A.1. Relation to Discrete-Time Fourier Series. 0 0 0 0 A NA A.1.3. Relation of Discrete Fourier Transform to Discrete-Time Fourier Transform We assume that X(k) and X() are the discrete Fourier transform and the discrete-time Fourier transform of x(n), respectively. Then, X(k) equals the samples of X() over period [0, 2) at interval 2/N, i.e., .1Nk0, k N 2 XX(k)         (A.9) Figure A.2 illustrates this relation. n x(n)  X() … Figure A.2. Relation to Discrete-Time Fourier Transform. k X(k) … 0 2 0 0 If N is too small, X(k) may not reflect X() well. Example. Assume x(n)=1, 0nM1. (A.10) (1) Find X(k), the N-point discrete Fourier transform of x(n), where NM. (2) Find X(), the discrete-time Fourier transform of x(n). If N=M, does X(k) reflect X() well? Example. The sampling interval of x(n) is 2·104 second. Find the length range of the discrete Fourier transform such that the sampling interval of X(k) is 20 radians/second at the most. A.2. Properties of Discrete Fourier Transform A.2.1. Linearity If x1(n)X1(k) and x2(n)X2(k), then a1x1(n)+a2x2(n)a1X1(k)+a2X2(k), (A.11) where a1 and a2 are two arbitrary constants. (A.11) holds when x1(n) and x2(n) have the same length initially or after zero padding. A.2.2. Circular Shift Assume that x(n) is a finite-length sequence over 0nN1. The circular shift of x(n) by n0 is defined as x(nn0)=x(nn0), 0nN1, (A.12) where x(n) is x(n) extended with period N. The circular shift can be carried out in the following steps (figure A.3). (1) Extend x(n) with period N to obtain x(n). (2) Shift x(n) by n0 to obtain x(nn0). (3) Limit x(nn0) to period 0nN1 to obtain x(nn0). m0 1 2 x(n) 3 … … m0 1 2 x(n) 3 m0 1 2 3 … … m0 1 2 x(n2) 3 4 m0 1 2 3 Figure A.3. Circular Shift. x(n2) x(n2) The circular shift can also be carried out by shifting and wrapping m0 1 2 3 x(n2) 5 x(n) (figure A.3). If x(n)X(k), then ,kn N 2 jexp)k(X)nn(x 00         (A.13) where n0 is an arbitrary integer. If x(n)X(k), then ),kk(Xnk N 2 jexp)n(x 00        (A.14) where k0 is an arbitrary integer. A.2.3. Reversal If x(n)X(k), then x(n), 0nN1X(k), 0kN1, (A.15) where x(n) and X(k) are, respectively, x(n) and X(k) extended with period N. A.2.4. Conjugation If x(n)X(k), then x*(n)X(k)*, 0kN1, (A.16) where X(k) is X(k) extended with period N. From (A.16), the following conclusions can be drawn: (1) Im[x(n)]=0  X(k)=X(k)*, 0kN1. (2) Re[x(n)]=0  X(k)=X(k)*, 0kN1. If x(n)X(k), then x(n)*, 0nN1X*(k), (A.17) where x(n) is x(n) extended with period N. From (A.17), the following conclusions can be drawn: (1) Im[X(k)]=0  x(n)=x(n)*, 0nN1. (2) Re[X(k)]=0  x(n)=x(n)*, 0nN1. Example. X(k) is the 512-point discrete Fourier transform of x(n). X(11)=2000(1+j). Find X(501). (1) x(n) is real. (2) x(n) is purely imaginary or 0. A.2.5. Symmetry If x(n)X(k), then X(n)Nx(k), 0kN1, (A.18) where x(n) is x(n) extended with period N. If x(n)X(k), then X(n)/N, 0nN1x(k), (A.19) where X(k) is X(k) extended with period N. A.2.6. Circular Convolution (Section A.4) A.2.7. Parseval’s Equation If x(n)X(k), then .)k(X N 1 )n(x 1N 0k 2 1N 0n 2       (A.20) A.3. Spectral Analysis of Continuous-Time Signals Using Discrete Fourier Transform A.3.1. Frame The discrete Fourier transform can be used in the spectral analysis of a continuous-time signal (figure A.4). xc(t) C/D DFT x(n) y(n) w(n) Figure A.4. Spectral Analysis of a Continuous- Time Signal Using Discrete Fourier Transform. Y(k) Each step is discussed as follows (figure A.5). (1) Sampling. Let Xc() be the continuous-time Fourier transform of xc(t), X() be the discrete-time Fourier transform of x(n) and T be the sampling interval. Then, X() equals Xc() extended with period 2/T, divided by T and then expressed in terms of , i.e.,   . T m2 X T 1 X m c           (A.21)  Xc() 0 A  X() …… 0 2 A/T  Y() …… 0 2 k Y(k) N10 Figure A.5. Illustration of Xc(), X(), Y() and Y(k). (2) Windowing. Assume that W() and Y() are the discrete-time Fourier transforms of w(n) and y(n), respectively. Then, Y() equals the periodic convolution of X() and W() divided by 2, i.e., .d)(W)(X 2 1 )(Y 2    (A.22) (3) Discrete Fourier Transform. Assume that Y(k) is the N-point discrete Fourier transform of y(n). Then, Y(k) equals the samples of Y() over period [0, 2) at interval 2/ N, i.e., .1Nk0, k N 2 Y(k)Y          (A.23) A.3.2. Effects of Windowing Let us investigate the effects of the above windowing further. Let xi(n)=Aiexp(jin) be a frequency component of x(n). Then, the discrete-time Fourier transform of xi(n) is (A.24).)m2(A2)(X m iii     Assume that yi(n) is the component of y(n) obtained by windowing xi(n), i.e., yi(n)=xi(n)w(n). Then, yi(n) has the discrete-time Fourier transform Yi()=AiW(i). (A.25) That is, Yi() equals W() shifted by i and multiplied by Ai. From (A.24) and (A.25), we see that compared with Xi(), Yi() has the following features (figure A.6). 1. Yi() has a distribution band. (1) The width of the distribution band equals the width of the main lobe of W(). In order for Yi() to have a narrow distribution band, W() should have a narrow main lobe. (2) The width of the main lobe of W() depends on the shape and the length of w(n). A longer w(n) results in a narrower main lobe.  Xi() n xi(n) w(n)  W() n yi(n) n Figure A.6. Differences between Xi() and Yi().   Yi()  i i i+ i i+ E Ai AiE i … …… … … … 2Ai … … 2. Yi() has leakages. (1) The relative amplitudes of the leakages equal the relative amplitudes of the side lobes of W(). For Yi() to have leakages of small relative amplitudes, W() should have side lobes of small relative amplitudes. (2) The relative amplitudes of the side lobes of W() depend on the shape of w(n) only. A.3.3. Windows The rectangular window is defined as . otherwise ,0 1Nn0 ,1 )n(w      (A.26) The Bartlett window is defined as . otherwise ,0 1Nn1)/2(N ),1N/(n22 2/)1N(n0 ),1N/(n2 )n(w         (A.27) The Hann window is defined as . otherwise ,0 1Nn0 , 1N n2 cos5.05.0 )n(w                (A.28) The Hamming window is defined as . otherwise ,0 1Nn0 , 1N n2 cos46.054.0 )n(w                (A.29) . otherwise ,0 1Nn0 , 1N n4 cos08.0 1N n2 cos5.042.0 )n(w                        (A.30) The above windows are illustrated in figure A.7. The Blackman window is defined as Figure A.7. Shapes of Commonly Used Windows. Table A.1. Features of Commonly Used Windows. Shape of Window Width of Distribution Band Peak Relative Amplitude of Leakages Rectangular 4/N 13 dB Bartlett 8/(N1) 25 dB Hann 8/(N1) 31 dB Hamming 8/(N1) 41 dB Blackman 12/(N1) 57 dB Table A.1 gives the features of these windows. It can be seen that when the length of the window is fixed, a narrow distribution band corresponds to leakages of large relative amplitudes, and therefore there exists a tradeoff between the width of the distribution band and the relative amplitudes of the leakages. The Kaiser window is defined as . otherwise 0, 1Nn0 , )(I 1 1N n2 1I )n(w 0 2 0                            (A.31) Here I0(·) is the zero-order modified Bessel function of the first kind and  is a shape parameter. A.4. Convolution Using Discrete Fourier Transform A.4.1. Definition of Circular Convolution Suppose that x1(n) and x2(n) are two finite-length sequences over 0nN1, and x1(n) and x2(n) are x1(n) and x2(n) extended with period N, respectively. The circular convolution of x1(n) and x2(n) is defined as the periodic convolution of x1(n) and x2(n) over a period 0nN1, i.e., 1,Nn0 ,m)(nx(m)x(n)x(n)x Nm 2121     (A.32) which is also written as 1.Nn0 ,m)(nx(m)x(n)x(n)x 1N 0m 2121      (A.33) Several points should be noted about the circular convolution: (1) x1(n) and x2(n) should have the same length initially or after zero padding to carry out the circular convolution. (2) The circular convolution possesses the commutative property, the associative property and the distributive property. The circular convolution can be carried out in the following steps. (1) Extend x2(m) with period N to obtain x2(m). (2) Reflect x2(m) about the origin to obtain x2(m). (3) Shift x2(m) by n to obtain x2(nm). This is equivalent to the shifting and the wrapping of x2(m), 0mN1. (4) Calculate the circular convolution at n. Example. Find the circular convolution of the two sequences in the following table. n 0 1 2 otherwise x1(n) 0 1 0 0 x2(n) 3 2 1 0 A.4.2. Circular Convolution Using Discrete Fourier Transform If x1(n)X1(k) and x2(n)X2(k), then ).k(X)k(X)n(x)n(x 2121   (A.34) ).k(X)k(X N 1 )n(x)n(x 2121   (A.35) If x1(n)X1(k) and x2(n)X2(k), then Figure A.8. Circular Convolution Using Discrete Fourier Transform. DFT IDFT x1(n) DFTx2(n) )n(x)n(x 21   (A.34) shows that the circular convolution can be carried out using the discrete Fourier transform (figure A.8). A.4.3. Convolution Using Discrete Fourier Transform In this section, we will study the relation between convolution and circular convolution and consider how to carry out convolution using the discrete Fourier transform. Let x1(n) and x2(n) be two finite-length sequences over 0nN11 and 0nN21, respectively. If f(n) and g(n) are the convolution and the N-point circular convolution of x1(n) and x2(n), respectively, then we have That is, g(n) equals f(n) extended with period N and limited to period 0nN1. Since f(n) is a finite-length sequence over 0nN1+N22, we can draw the following conclusions. If N N1+N21, g(n) equals f(n). Otherwise, aliasing occurs. The relation between f(n) and g(n) is illustrated in figure A.9. 1.Nn0 ,)iNn(f)n(g i     (A.36) 0 N1+N22 m N … … 0 N1+N22 m 0 N1+N22 m Figure A.9. Relation between Convolution and Circular Convolution. NN1+N21 0 N1+N22 m N … … 0 N1+N22 m N
本文档为【A. Basics of Discrete Fourier Transform】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_941293
暂无简介~
格式:pdf
大小:227KB
软件:PDF阅读器
页数:38
分类:
上传时间:2013-10-16
浏览量:15