[PDF] The Discrete Fourier Transform

approach: sample X(ω), then compute inverse DFT (using FFT) −2π 0 0 75π π 2π 0 0 2 0 4 0 6

5 fév 2019 · recovers the original signal x This means that the iDFT is, as its names indicates, the inverse operation to the DFT This result is of sufficient

[PDF] The Discrete Fourier Transform - Eecs Umich

approach: sample X(ω), then compute inverse DFT (using FFT) −2π 0 0 75π π 2π 0 0 2 0 4 0 6

[PDF] Lecture 7 - The Discrete Fourier Transform

integrand exists only at the sample points: Figure 7 2: Example signal for DFT i e the inverse matrix is `X times the complex conjugate of the original

[PDF] Discrete Fourier Transform (DFT)

Sample the spectrum X(ω) in frequency so that X(k) = X(k∆ω), ∆ω = 2π N =⇒ X(k) = N−1 ∑ n=0 x(n)e −j2π kn N DFT The inverse DFT is given by: x(n) =

[PDF] DFT/FFT Transforms and Applications 61 DFT and its Inverse

and the inverse DFT (IDFT) is given by (synthesis equation): 1 ,,2,1,0 )( 1 ][ 1 Example 6 1: Compute the DFT of the following two sequences: }2,1,3,1{][ −−

[PDF] Discrete Fourier Series & Discrete Fourier Transform - CityU EE

series (DFS), discrete Fourier transform (DFT) and fast Fourier DFT and their inverse transforms Then compare the results with those in Example 7 1

[PDF] 2D Discrete Fourier Transform (DFT)

samples) → circular or periodic convolution – the summation Find the inverse DFT of Y[r] Fourier transform of a 2D set of samples forming a bidimensional

[PDF] Chapter 3: Problem Solutions

Using the definition determine the DTFT of the following sequences It it does not Using the properties of the DFT (do not compute the sequences) determine the DFT's of the The inverse DCT obtained for L = 20, 30, 40 are shown below

[PDF] Real forward and inverse FFT - Jens Hee

14 mar 2014 · The Inverse Discrete Fourier transform (IDFT) is defined by: x(n) = IDFTN {X(k)} = 1 N N−1 ∑ k=0 X(k)ej 2π N nk IDFT can be calculated

Chapter5

TheDiscreteFourierTransform

5.1 5.2c

DTFTFT

Sum shifted scaled replicatesSum of shifted replicates DTFS ZDFT

Sinc interpolationRectangular window

Dirichlet interpolationRectangular windowBandlimited:Time-limited:Time-limited:Bandlimited:

SamplingSampling

Sample Unit Circle

Unit Circle

PSfragreplacements

x[n]=xa(nTs) x a(t) X a(F)x[n] X(!)x ps[n] X[k]

X(z)X[k]=X(!)j!=2

TheFTFamilyRelationships

Xa(F)=R1

1xa(t)e|2Ftdt

xa(t)=R1

1Xa(F)e|2FtdF

DTFT

X(!)=P1

n=1x[n]e|!n=X(z)jz=ej! x[n]=1 2R

X(!)e|!nd!

UniformTime-DomainSampling

x[n]=xa(nTs)

X(!)=1

TsP 1 k=1Xa!=(2)k Ts (sumofshiftedscaledreplicatesofXa())

Xa(F)=Tsrect

F Fs xa(t)=P1 n=1x[n]sinc tnTs Ts DTFS ck=1 NP N1 n=0xps[n]e|2Nkn=1NX(z)jz=e|2Nk xps[n]=PN1 k=0cke|2

Nkn,!k=2Nk

UniformFrequency-DomainSampling

X[k]=X(!)

!=2

Nk;k=0;:::;N1

X[k]=Nck

xps[n]=1 NP N1 k=0X[k]e|2Nkn xps[n]=P1 l=1x[nlN](sumofshiftedreplicatesofx[n]) k=0X[k]P(!2k=N),whereP(!)=1 NP N1 k=0e|!n. c

Overview

Mainpoints

spectrumanalyzerswork.) offrequencies.

Whichfrequencies?

!k=2Nk;k=0;1;:::;N1: canrecoverx[n]fromX2 NkN1 k=0.

X(!)=1X

n=1x[n]e|!n;x[n]=1 2Z

X(!)e|!nd!:

Discrete-timeFourierseries(DTFS)review

RecallthatforaN-periodicsignalx[n],

x[n]=N1X k=0c ke|2

Nknwhereck=1NN1X

n=0x[n]e|2 Nkn: 5.4c

Denition(s)

X[k]4=

PN1 n=0x[n]e|2

Nkn;k=0;:::;N1

??otherwise: Nout fronttomaketheDFTmatchtheDTFS.)

Thisisreasonablemathematicallysince

X[n+N]=N1X

n=0x[n]e|2

N(k+N)n=N1X

n=0x[n]e|(2Nkn+2kn)=N1X n=0x[n]e|2Nkn=X[k]:

2.TreatX[k]asundenedfork=2f0;:::;N1g.

computer.

3.TreatX[k]asbeingzerofork=2f0;:::;N1g.

Thisisavariationonthepreviousoption.

~x[n]= 1 NP N1 k=0X[k]e|2Nkn;n=0;:::;N1 ??;otherwise: x[n]= 1 NP N1 k=0X[k]e|2Nkn;n=0;:::;N1

0;otherwise:

k=0.Theproofofthisis x[n]=1 NN1X k=0X[k]e|2 Nkn:

ThisisindeedaN-periodicexpression.

x ps[n]=1 NN1X k=0X[k]e|2 Nkn; eveninthiscase. c

Examples

X[k]=N1X

n=0x[n]e|2

Nkn=7X

n=0x[n]e|28kn=7X n=0([n]+0:9[n6])ej2kn=8=1+0:9e|28k6:

0123456-0.2

0 0.2 0.4 0.6 0.8 1 n x[n]

DFT Example

012345670

0.5 1 1.5 2 k |X[k]|

01234567-1

-0.5 0 0.5 1 k

Ð X[k]

X[k]=X(z)

z=e|2

Nk=1+0:9e|2

8k:

Example.FindN-pointinverseDFToffX[k]gN1

k=0whereX[k]=1;k=k0

0;otherwise=[kk0];fork02f0;:::;N1g.

Picture.

x[n]=1 NN1X k=0X[k]e|2

Nkn=1Ne|2

Nk0n:

ThuswehavethefollowingimportantDFTpair.

Ifk02f0;:::;N1g,then1Ne|2

Nk0nDFT !N[kk0]:

Example.FindN-pointinverseDFToffX[k]gN1

k=0where

X[k]=8

:e |;k=k0 e|;k=Nk0

0;otherwise;=e|[kk0]+e|[k(Nk0])

fork02f1;:::;N=21;N=2+1;:::;N1g.

Picture.

x[n]=1 NN1X k=0X[k]e|2

Nkn=1Ne|e|2

Nk0n+1Ne|e|2

N(Nk0)n=2Ncos2Nk0n+

5.6c

Expanding:x[n]=3+3cos

2n=3+32e|282n+32e|282n=18h

24+12e|282n+12e|28(82)ni

Sobycoefcientmatching,weseethatX[k]=f24

;0;12;0;0;0;12;0g:

Supposex[n]=e|2

FindtheN-pointDFTofx[n].

X[k]=N1X

n=0x[n]e|2

Nkn=N1X

n=0e |2Nk0ne|2Nkn=N1X n=0e |2N(kk0)n=N;k=k0+lN;l2Z

0;otherwise:

Thus x[n]=e|2Nk0nDFT !NX[k]=N1X l=1[kk0lN]=NN[kk0]; whereN[n]4=P1 l=1[nlN].

Nk0foranyintegerk.

FindtheN-pointDFTofx[n].

X[k]=N1X

n=0e |!0ne|2

Nkn=N1X

n=0 e|(!02Nk)n=1 e |(!02 Nk)N

1e|(!02Nk)=1e|!0N1e|(!02Nk):

ThuswehavethefollowingcuriousDFTpair.

If!0=2Nisnon-integer,thene|!0nDFT !NX[k]=1e|!0N1e|(!02Nk):

Whatisgoingonintheseexamples?

N[n]=1;n=0;:::;N1

0;otherwise;

whichhasthefollowingDTFT:

R(!)=N1X

n=0e |!n==e|!(N1)=2Rr(!);whereRr(!)=8 :sin(!N=2) sin(!=2);!6=0

N;!=0Nsinc

N!2

Thenwehave

wheretheaboveisaDiracimpulse.Thus

X[k]=X(!)

!=2

Nk=2R2Nk!0

When!0=2

DTFTsamplingpreview

TheDTFTformulaisX(!)=P1

n=0x[n]e|2 Nkn: n=0x[n]e|!n:

X[k]=X(!)

!=2 Nk: synthesisformula:x[n]=1 2R

X(!)e|!nd!:

Doesthisapproachalwayswork?No!

X(!)=8

:3 4 !0 2; !0 1 2 1 2 32
!0 2;1 2< !0 3 2 0;3 2< !0 !0 -2p 0 0.75p p 2p0 0.2 0.4 0.6 0.8

Challenging DTFT H(w)

w H(w) -2p 0 0.75p p 2p0 0.2 0.4 0.6 0.8

Samples, N=16

H(2p/N k)

015-0.05

0 0.05 0.1 0.15 0.2 0.25 n x[n]

015-0.05

0 0.05 0.1 0.15 0.2 0.25 n x ps [n] via ifft

Inverse DFT of X[k]

-807 0 0.1 0.2 x[n]

Exact Inverse DTFT

-807 0 0.1 0.2 n x ps [n] via ifft

After "fftshift", for N=16

-807-2 0 2 4

6x 10-4

n Error 5.8c

Themodulofunction

Example

.1mod4=1;7mod4=3;1mod4=3;8mod4=0. x ps[n]4=1X l=1x[nlN]:

Notethatallthevaluesofx[n]affectxps[n].

x((n))N4=x[nmodN]:

Example.x[n]=f4;3;2;1g=4n;0n3

0;otherwise;soL=4.

n 6x[n] -2-1012342 4

N-pointperiodicsuperposition:

6xps[n];N=6

-6062 4 n

6xps[n];N=3

0362
3 5

N-pointcircularextension:

6x[nmodN];N=6

-6062 4 n

6x[nmodN];N=3

0362
3 4 x[n]!

DTFT!X(!)!sample!X2NkN1

k=0!N-pointinvDFT!xps[n] x[n]!

N-pointDFT!N-pointinvDFT!x[n]orx[nmodN]

c 5.1 X 2 Nk =X(!) !=2 Nk=1X n=1x[n]e|2

Nkn;k=0;1;:::;N1:

Questionsarise:

I.HowisX2

NkN1 k=0.

II.When(ifever)canwerecoverx[n]fromX2

NkN1 k=0orfromDFTfX[k]gN1 k=0?

III.Howcanwerecoverx[n]fromX2

NkN1 k=0orfromDFTfX[k]gN1 k=0? Nk. X 2 Nk =X(!) !=2 Nk=1X n=1x[n]e|2 Nknquotesdbs_dbs20.pdfusesText_26

[PDF] [PDF] The Discrete Fourier Transform - Eecs Umich

Chapter5

TheDiscreteFourierTransform

Contents

DTFTFT

Sinc interpolationRectangular window

SamplingSampling

Sample Unit Circle

Unit Circle

PSfragreplacements

X(z)X[k]=X(!)j!=2

TheFTFamilyRelationships

Xa(F)=R1

1xa(t)e|2Ftdt

1Xa(F)e|2FtdF

X(!)=P1

X(!)e|!nd!

UniformTime-DomainSampling

X(!)=1

Xa(F)=Tsrect

Nkn,!k=2Nk

UniformFrequency-DomainSampling

X[k]=X(!)

Nk;k=0;:::;N1

X[k]=Nck

Overview

Mainpoints

Whichfrequencies?

X(!)=1X

X(!)e|!nd!:

Discrete-timeFourierseries(DTFS)review

RecallthatforaN-periodicsignalx[n],

Nknwhereck=1NN1X

Denition(s)

X[k]4=

Nkn;k=0;:::;N1

Thisisreasonablemathematicallysince

X[n+N]=N1X

N(k+N)n=N1X

2.TreatX[k]asundenedfork=2f0;:::;N1g.

3.TreatX[k]asbeingzerofork=2f0;:::;N1g.

Thisisavariationonthepreviousoption.

0;otherwise:

ThisisindeedaN-periodicexpression.

Examples

X[k]=N1X

Nkn=7X

0123456-0.2

DFT Example

012345670

01234567-1

Ð X[k]

X[k]=X(z)

Nk=1+0:9e|2

Example.FindN-pointinverseDFToffX[k]gN1

0;otherwise=[kk0];fork02f0;:::;N1g.

Picture.

Nkn=1Ne|2

ThuswehavethefollowingimportantDFTpair.

Ifk02f0;:::;N1g,then1Ne|2

Nk0nDFT !N[kk0]:

Example.FindN-pointinverseDFToffX[k]gN1

X[k]=8

0;otherwise;=e|[kk0]+e|[k(Nk0])

Picture.

Nkn=1Ne|e|2

Nk0n+1Ne|e|2

N(Nk0)n=2Ncos2Nk0n+

Expanding:x[n]=3+3cos

2n=3+32e|282n+32e|282n=18h

24+12e|282n+12e|28(82)ni

Sobycoefcientmatching,weseethatX[k]=f24

Supposex[n]=e|2

FindtheN-pointDFTofx[n].

X[k]=N1X

Nkn=N1X

0;otherwise:

Nk0foranyintegerk.

FindtheN-pointDFTofx[n].

X[k]=N1X