Discrete Fourier Transform Chapter 5 Part A ◆Definition ●●● ●●● ●●● 色● ◆Matrix Relations ●●0●6 Finite Length The Discrete Fourier DFT Computation Using MATLAB Discrete Transforms Transform(DFT) Relation between DTFT and DFT and their inverses 1.Definition 1.Definition 1.Definition Definition .From the definition of the DTFT we thus have Using the notation W=pr,the DFT is The simplest relation between a length-N X)=X(e。-2aN sequence x(n),defined for OsnN-I and its usually expressed as: DTFT X(e)is obtained by uniformly =∑x(n)e2saN, 0≤k≤N-1 X(k)=∑x(n)W,0≤k≤N-1 sampling X(ei)on the @-axis between Osos m=0 2πato4=2πkW,0s≤N-1 .X(k)is also a length-N sequence in the The inverse discrete Fourier transform (IDFT) frequency domain is given by .DFT is obtained by sampling the DTFT over The sequence X(k)is called the discrete 1 one principal value interval in the frequency x(n)= ∑Xk)w,0≤n≤N-1 Fourier transform(DFT)of the sequence x(n) domain 4 6
Chapter 5 Chapter 5 Finite Length Discrete Transforms Part A The Discrete Fourier Transform (DFT) Discrete Fourier Transform Definition Matrix Relations DFT Computation Using MATLAB R l ti b t DTFT d DFT d Relation between DTFT and DFT and their inverses 3 1. Definition Definition Th i l li b l h he simplest relation between a length-N sequence x(n), defined for 0nNˉ1 and its DTFT X j (e ) is obtained by uniformly sampling X(ej) on the -axis between 0 2 at k= 2 k/N, 0k Nˉ1 DFT is obtained by sampling the DTFT over DFT is obtained obtained by sampling sampling the DTFT over one principal value interval in the frequency domain 4 1. Definition From the definition of the DTFT we thus have 2 / 1 2 / () ( ) () 0 1 j k N N j kn N X k Xe k N X(k) is also a length N sequence in the 2 / 0 ( ) , 0 1 j kn N n x n e k N X(k) is also a length-N sequence in the frequency domain The sequence X(k) is called the discrete Fourier transform (DFT) of the sequence x(n) 5 1. Definition Using the notation WN=e-j2 /N g , the DFT is N , usually expressed as: 1 () () 0 1 N kn Xk W k N The inverse discrete Fourier transform (IDFT) 0 () () , 0 1 kn N n X k x n W kN The inverse inverse discrete discrete Fourier Fourier transform transform (IDFT) is given by 1 1 N 0 () () , 0 1 N kn N k xn X kW n N N 6
1.Definition 1.Definition 1.Definition To verify the validity of IFDT,we multiply .W=e which is usually called twiddle both sides of the expression by Ww and sum Making use of the identity factor has many useful features the result from n=0 to n=N-1,resulting in [N,for k-1=rN,r isan integer It is the first root of the NN-th roots of unity 分mw-】 1 -0 0,otherwise The modulus is I (on the unit circle) 岁w=0 N -0 ·Hence ·联=WgP=Wg 1 ∑∑X)-h omg=XO =0k-0 =0 W8-1 W2=-1 X∑- N- =0 1.Definition 1.Definition 1.Definition Mapping Relations between time-domain and Type 1:Continuous-Time Fourier Transform Type 2:Continuous-Time Fourier Series frequency-domain transforms (CTFT) (CTFS) (Time-domain) (Frequency-domain) Continuous Aperiodical 普x(0 X.(2) P x() >X,U0)6s LDiscrete Periodical x.().d 1, X.())e-ao d Periodical Discrete -Aperiodical◆ Continuous 0-上x.U x)=∑X.Uk2,)ea 12
1. Definition WN=e-j2 /N which is usually called twiddle N factor has many useful features It i th fi t t f th It is the first root of the N N-th t f it th roots of unity The modulus is 1 (on the unit circle) 1 k kN W W N N kN k / 2 W W N N 1 1 0 N k N k W k 1 0 1 WN / 2 1 N WN 7 1. Definition To verify the validity of IFDT, we multiply both sides of the expression by and both sides of the expression by W ln and sum the result from n = 0 to n=Nˉ1, resulting in WN N NN 1 11 0 00 1 () () N NN ln kn ln N NN n nk xnW X kW W N 0 00 1 1 1 ( ) n nk N N k ln N N X kW N 0 0 1 1 1 ( ) n k N N k ln N N Xk W 0 0 8 ( ) N k n Xk W N 1. Definition Making y use of the identity 1 , for , isan integer N k ln N N k l rN r W Hence 0 0, otherwise N n W Hence 1 0 ( ) () N ln N x nW X l n0 9 1. Definition Mapping Relations between time-domain and frequency-di f oma n transforms (Time-domain) (q y Fre uency-domain) Continuous Aperiodical Discrete Periodical Periodical Discrete Periodical Discrete Aperiodical Continuous 10 1. Definition Type 1: Continuous-Time Fourier Transform (CTFT) Continuous Aperiodical ( ) a x t ( ) X j a Continuous Aperiodical Aperiodical Continuous ( ) () j t X j x t e dt a a 1 () ( ) 2 j t a a xt X j e d 11 2 1. Definition Type 2: Continuous-Time Fourier Series (CTFS) Continuous Aperiodical ( ) a x t 0 ( ) X jk a Continuous Periodical Aperiodical Discrete 1 T / 2 0 0 / 2 1 ( ) () p p T jk t a a T p X jk x t e dt T p 0 0 () ( ) jk t a a k x t X jk e 12 k
1.Definition 1.Definition 1.Definition Type 3:Discrete-Time Fourier Transform .Type 4:Discrete Fourier Transform(DFT) Examples (DTFT) Rectangular Pulse RM(n),width N x(n)◆X(k) Periodical Its N-point DFT is given by Am x(n) >X(em)d Discrete X=发mw哈，0≤k≤N-1 X)-足mw吃=时- N-I Ke-豆o 1-W9 0 WAwn WwnWwn (m(-de x(n)= ∑X(k)W,0≤n≤N-1 W WR-WAE Progression N1 sin(kπ/W) 1.Definition 1.Definition 2.Matrix Relations .Its 2N-point DFT is given by This part is introduced for the purpose of X(k)= w computation using MATLAB Since MATLAB stands for MAtrix sin(kπ/2】 2w1 LABoratory,we represent DFT definition in =e 1-m sin(kπ/2W) terms of matrix form So the length of DFT plays a very important x6-发mw吃，0≤k≤N-1 role in DFT -0 X=Dx 话 1
1. Definition Type 3: Discrete-Time Fourier Transform (DTFT) ( ) Discrete j Periodical x n( ) ( ) j X e Discrete Aperiodical Periodical Continuous ( ) () j j n n X e xne 1 () ( ) 2 j jn xn X e e d 13 2 - 1. Definition Type 4: Discrete Fourier Transform (DFT) x n( ) X k( ) Discrete Periodical x n( ) X k( ) Periodical Discrete 1 () () 0 1 N kn Xk W k N 0 () () , 0 1 kn N n X k x n W kN 1 1 N 0 () () , 0 1 N kn N k xn X kW n N N 14 1. Definition Examples Rectang lar ectangular Pulse RN(n), width N Its N-point DFT is given by 1 1 1 () () 1 N N kN kn kn N N N k W X k xnW W W 0 0 /2 /2 /2 /2 /2 /2 n n 1 N kN kN kN NN N k kk W WW W /2 /2 /2 Geometric 1 sin( ) k kk NN N Nj k N WW W k Geometric Progression 15 ( ) sin( / ) N e k N 1. Definition Its 2N-p gy oint DFT is given by 21 1 2 2 () () N N kn kn X k xnW W N N 0 0 1 2 2 1 sin( / 2) n n kN Nj k W N N k e So the length of DFT plays a very important 2 1 sin( / 2 ) kN e W kN So the length of DFT plays a very important role in DFT 16 1. Definition 4 DTFT of R4(n) 4 Relation between DFT and DTFT 2.5 3 3.5 4 4 d e 3 4 e 1 1.5 2 Amplitu d 1 2 Amplitud 4-Point DFT of R (n) 8-point of R (n) 0 0.5 1 1.5 2 0 0.5 / 0 1 2 3 4 5 6 0 3 4 4-Point DFT of R4(n) 3 4 8 point of R4(n) 1 2 |X(k)| 1 2 |X(k)| 17 0 1 2 3 0 1 n 0 1 2 3 4 5 6 7 8 0 1 n 2. Matrix Relations This part is introduced for the purpose of computation using MATLAB Since MATLAB stands for Since MATLAB stands for MAtrix LABoratory, we represent DFT definition in terms of matri form terms of matrix form 1 () () 0 1 N kn X k xnW k N 0 () () , 0 1 N n X k xnW k N X Dx 18 N
2.Matrix Relations 2.Matrix Relations 2.Matrix Relations ·where X=[X(O)X() .X(W- .Likewise.the IDFT relations can be Obviously,the relation between the two x=[xOx)…xW-I expressed in x=D'X coefficient matrices can be expressed as follows 「11 1 1 1 1 1 W W … E 1 W w Wtw-n D时=D N 1 Dx= 1 W w时 Waw-b Dy=- W N 在 x-b Therefore,the algorithms designed for DFT are applicable to IDFT 1 Ww-WaN-D -w- 1 Ww-）W2- N-IXN-3) 3.DFT Computation 3.DFT Computation 4.Relations between DTFT and Using MATLAB Using MATLAB DFT and their inverses The functions to compute the DFT and the IDFT are fft and ifft DTFT from DFT by interpolation These functions make use of FFT algorithms 。Sampling the DTFT which are computationally highly efficient Numerical computation of the DTFT using compared with the direct computation DFT Figure in the next slide shows the DFT and DTFT of the sequence X(k) interpolation) cos(6xm/160≤n≤15 sampling
2. Matrix Relations where (0) (1) ( 1)T X X X XN (0) (1) ( 1)T x x x xN 12 1 11 1 1 1 N WW W 2 4 2( 1) 1 1 NN N N N NN N WW W WW W D 1 2( 1) ( 1)( 1) 1 N N NN WW W 19 ( ) ( )( ) 1 WW W NN N N N 2. Matrix Relations Likewise, the IDFT relations can be d i 1 expressed in 11 1 1 1 N x DX 1 2 ( 1) 11 1 1 1 N WW W NN N 1 2 4 2( 1) 1 1 NN N N N NN N WW W N D ( 1) 2( 1) ( 1)( 1) 1 N N NN NN N N WW W 20 1 WW W NN N N N 2. Matrix Relations Obviously, the relation between the two coefficient matrices can be expressed as follows 1 * 1 N N N D D Therefore, the algorithms designed for DFT N are applicable to IDFT 21 3. DFT Computation Using MATLAB The functions to compute the DFT and the IDFT are fft and ifft These functions make use of FFT algorithms These functions make use of FFT algorithms which are computationally highly efficient compared with the direct computation compared with the direct computation Figure in the next slide shows the DFT and DTFT of the sequence DTFT of the sequence cos(6 /16) 0 15 n n 22 3. DFT Computation Using MATLAB 9 DFT 6 7 8 DTFT 4 5 6 Magnitude 1 2 3 0 0.2 0.4 0.6 0.8 1 0 1 / 23 4. Relations between DTFT and DFT and their inverses DTFT from DFT by interpolation Samp g lin the DTFT Numerical computation of the DTFT using DFT ( ) j X k( ) X interpolation ( ) j X k( ) X e sampling 24
4.1 DTFT from DFT by interpolation 4.1 DTFT from DFT by interpolation 4.1 DTFT from DFT by interpolation The N-point DFT X(k)of a length-N sequence We use the IFDT relation and the definition x(n)is simply the frequency samples of its of DTFT to study the relation between DFT Lets- e and r=eo)] DTFT X(ei)evaluated at N uniformly spaced and DTFT ·Thus frequency points X(e)-∑x(n)em 1-e-i(ax-2al) X(W o=2πkN,03≤N-1 1-r1-e-2aw可 V-I 。-a2wm sin oN-2πk Given the N-point DFT X(k)of a length-N sequence x(n),its DTFT X(ej)can be uniquely N 2 -0 = ea-2a1ww-/g网 determined from X(k) ùN-2πk sin Exchange of the order of summutions 2N 20 4.1 DTFT from DFT by interpolation 4.2 Sampling the DTFT 4.2 Sampling the DTFT There,DTFT can be determined by the .Consider a sequence x(n)with a DTFT X(ef) ●Now following interpolation formula X(e)=x(nem We sample X(ef)at Nequally spaced points ●Thus X(ei) @=2 k/N,0sks N-1 developing the N Y(k)=X(eim)=X(es) aN-2πk frequency samples (X(ei) sin N e-2Nw-网 These N frequency samples can be considered as an N-point DFT Y(k)whose N-point IDFT sin @N-2nk is a length-N sequence y(n) An IDFT of Y()yields y(m)=Y( 2N 2
4.1 DTFT from DFT by interpolation The N-point DFT X(k) of a length-N sequence x(n) is simply the frequency samples of its DTFT X(ej) evaluated at N uniformly spaced frequency points k= 2 k/N, 0k Nˉ1 Given the N-point DFT X(k) of a length-N ( ) it DTFT X( j sequence x(n), its DTFT X(e ) b il j) can be uniquely determined from X(k) 25 4.1 DTFT from DFT by interpolation We use the IFDT relation and the definition of DTFT to study the relation between DFT of DTFT to study the relation between DFT and DTFT 1 11 1 N NN 0 00 1 ( ) () () N NN j j n kn j n N n nk X e xne X kW e N 1 1 1 [ 2/] ( ) N N j kN n Xk e N x(n) IDFT N k n 0 0 x(n) 26 Exchange of the order of summations 4.1 DTFT from DFT by interpolation Let and 1 2 / N j kN n S e j 2 / k N r e Thus n0 1 ( 2) 1 1 N N jN k r e 2 / 0 1 1 1 1 2 n j kN n r e S r r e N k 2 / ( 1) / 2 2 sin 2 j kN N N k e 2 sin 2 e N k N 27 2N 4.1 DTFT from DFT by interpolation There, y DTFT can be determined by the following interpolation formula ( ) j X 2 i j X e N k 1 2 / ( 1) / 2 sin 1 2 ( ) 2 N j kN N Xk e N N k 0 2 sin 2 N k N k N 28 4.2 Sampling the DTFT Consider a sequence x(n) with a DTFT X(ej q ( ) ( ) We sample X(ej) at N equally spaced points k=2 k/N, 0k Nˉ1 developing the developing the N frequency samples {X(ejk)} These N frequency samples can be considered as an N-point DFT Y(k) whose N-point IDFT is a length-N sequence y(n) 29 4.2 Sampling the DTFT Now ( ) () j jn Now X e xne Thus - ( ) () n X e xne (2 / ) () ( ) ( ) k j j kN Yk X X (2 / ) () ( ) ( ) ( ) k j j kN kl Yk X e X e xlW An IDFT of Y(k) yields ( ) N l xlW 1 1 () () N kn yn Y kW An IDFT of Y(k) yields 0 () () N k yn Y kW N 30