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
4.2 Sampling the DTFT 4.2 Sampling the DTFT 4.2 Sampling the DTFT .i.e. o-22 We arrive at the desired relation 。To apply = ,x(n+mW),0≤n≤N-1 y(n)= 2m+mN,0≤m≤N-l to finite-length sequences,we assume that the Thus wn)is obtained fromx(n)by adding an samples outside the specified range are zeros Making use of the identity infinite number of shifted replicas of x(n), with each replica shifted by an integer Thus if x(n)is a length-Msequence with MN, 2-6 for I=n+mN multiple of N sampling instants,and observing then y(n)=x(n)for 0N,there is a time-domain aliasing of ·By sampling its DTFT X(e)ato,=2πk/4, A practical approach to the numerical samples ofx(n)in generating v(n),and x(n) 05k3,and then applying a 4-point IDFT to computation of the DTFT of a finite-length cannot be recovered from wn) these samples,we arrive at the sequence yn) sequence This is called Sampling Theorem in given by Let X(j)be the DTFT of a length-N Frequency-Domain (N2M) y(n)=x(n)+x(n+4)+x(n-4),05ks3 sequence x(n) Recall that the condition of Sampling Theorem i.e.nF{4623} .We wish to evaluate X(e)at a dense grid of in Time--Domain is≥2 frequencies,where M>>N: Example Let x(n)=(0 1 2 3 4 5) fx(n)cannot be recovered from (y(n)) ,0≤k≤M-1 15
4.2 Sampling the DTFT i.e. 1 1 ( ) () N kl kn N N yn xlW W i.e. 0 1 ( ) () 1 N N k l N yn xlW W N ( ) 0 1 ( ) knl N l k xl W N Making use of the identity 1 1 1 for N l n mN ( ) 0 1 1, for 0, otherwise knl N k l n mN W N 31 4.2 Sampling the DTFT We arrive at the desired relation y n x n mN n N ( ) ( ), 0 1 Thus y(n) is obtained from x(n) by adding an infinite number of shifted replicas of x(n) m infinite number of shifted replicas of x(n) , with each replica shifted by an integer multiple of multiple of N sampling instants and observing sampling instants, and observing the sum only for the interval 0nNˉ1 32 4.2 Sampling the DTFT To app yl fi i l h hh ( ) ( ), 0 1 m y n x n mN n N to finite-length sequences, we assume that the samples outside the specified range are zeros Thus if x(n) is a length-M sequence with MN, then y(n)=x(n) for 0nNˉ1 33 4.2 Sampling the DTFT If M > N, there is a time-domain aliasing of sampl f es o x(n) i i n generating y(n) , and x(n) cannot be recovered from y(n) This is called Sampling Theorem in Freq y uenc -Domain (NM) Recall that the condition of Sampling Theorem in Time in Time-Domain is Domain is f 2f s c Example Let x(n)={0 1 2 3 4 5} 34 4.2 Sampling the DTFT By sampling its DTFT X(ej y pg ( ) at k=2 k/4, k 0k3, and then applying a 4-point IDFT to these samp, q les we arrive at the sequence y(n) given by y(n)= x(n) + x(n+4) + x(nˉ4) 0 ,k3 i.e. y(n)= {4 6 2 3} {x(n) } cannot be recovered from {y(n)} 35 4.3 Numerical Computation of the DTFT using DFT A practical approach to the numerical computation of the DTFT of a finite computation of the DTFT of a finite-length sequence Let X(ej) be the DTFT of a length-N sequence x(n) We wish to evaluate X(ej) at a dense grid of frequencies where frequencies , where M >> N : 2 ,0 1 k k k M 36 ,0 1 k k M M
4.3 Numerical Computation of the 4.3 Numerical Computation of the DTFT using DFT DTFT using DFT -艺m-艺nc学 Thus X(ei)is essentially an M-point DFT X(k)of the length-M sequence x(n) ●Define a new sequence The DFT X(k)can be computed very efficiently using the FFT algorithm if Mis an [x(n)0≤n≤N-1 x(n)= integer power of 2 0 N≤n≤M-1 The function freqz employs this approach 。Then -空a学 to evaluate the frequency response at a prescribed set of frequencies of a DTFT expressed as a rational function in e
4.3 Numerical Computation of the DTFT using DFT 1 1 2 k k N N j kn j jn M X e xne xne Define a new sequence 0 0 n n X e xne xne Define a new sequence 0 1 xn n N x n Then 0 1 e x n NnM Then 1 2 k M j kn j M X e x ne e 37 0 e n 4.3 Numerical Computation of the DTFT using DFT Thus is essentially an M-point DFT X (k) of the length M sequence x (n) ( ) k j X e Xe(k) of the length-M sequence xe(n) The DFT Xe(k) can be computed very efficiently using the FFT algorithm if M is an integer power of 2 The function freqz employs this approach to evaluate the frequency response at a to evaluate the frequency response at a prescribed set of frequencies of a DTFT expressed as a rational function in j e 38 expressed as a rational function in e