[PDF] Discrete Fourier Transform (DFT) PDF l5.pdf

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) =

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

Discrete Fourier Transform (DFT)Recall the DTFT:

X(ω) =∞?

n=-∞x(n)e-jωn.

DTFT is not suitable for DSP applications because•In DSP, we are able to compute the spectrum only at specific

discrete values ofω,•Any signal in any DSP application can be measured only in a finite number of points.

A finite signal measured atNpoints:

x(n) =? ?0, n <0,

0, n≥N,

wherey(n)are the measurements taken atNpoints.EE 524, Fall 2004, # 51

Sample the spectrumX(ω)in frequency so that

X(k) =X(kΔω),Δω=2πN=?

X(k) =N-1?

n=0x(n)e-j2πknNDFT.

Theinverse DFTis given by:

x(n) =1NN-1? k=0X(k)ej2πknN. x(n) =1NN-1? k=0? N-1? m=0x(m)e-j2πkmN? e j2πknN N-1? m=0x(m)?

1NN-1?

k=0e -j2πk(m-n)N?

δ(m-n)=x(n).EE 524, Fall 2004, # 52

The DFT pair:X(k) =N-1?

n=0x(n)e-j2πknNanalysis x(n) =1NN-1? k=0X(k)ej2πknNsynthesis.Alternative formulation:

X(k) =N-1?

n=0x(n)Wkn←-W=e-j2πN x(n) =1NN-1? k=0X(k)W-kn.EE 524, Fall 2004, # 53

EE 524, Fall 2004, # 54

Periodicity of DFT SpectrumX(k+N) =N-1?

n=0x(n)e-j2π(k+N)nN N-1? n=0x(n)e-j2πknN? e -j2πn =X(k)e-j2πn=X(k) =? the DFT spectrum is periodic with periodN(which is expected, since the DTFT spectrum is periodic as well, but with period

2π).

Example:DFT of a rectangular pulse:

0,otherwise.

X(k) =N-1?

n=0e -j2πknN=Nδ(k) =? the rectangular pulse is "interpreted" by the DFT as a spectral line at frequencyω= 0.EE 524, Fall 2004, # 55 DFT and DTFT of a rectangular pulse (N=5)EE 524, Fall 2004, # 56 Zero PaddingWhat happens with the DFT of this rectangular pulse if we increaseNbyzero padding: {y(n)}={x(0),...,x(M-1),0,0,...,0????

N-Mpositions},

wherex(0) =···=x(M-1) = 1. Hence, DFT is

Y(k) =N-1?

n=0y(n)e-j2πknN=M-1? n=0y(n)e-j2πknN sin(πkMN)sin(πkN)e-jπk(M-1)N.EE 524, Fall 2004, # 57

DFT and DTFT of a Rectangular Pulse with

Zero Padding (N= 10, M= 5)Remarks:•Zero padding of analyzed sequence results in "approximating" its DTFT better,•Zero padding cannot improve the resolution of spectral components, because the resolution is "proportional" to

1/Mrather than1/N,•Zero padding is very important for fast DFT implementation

(FFT).EE 524, Fall 2004, # 58 Matrix Formulation of DFTIntroduce theN×1vectors x=? ??x(0) x(1)... x(N-1)? ??,X=? ??X(0)

X(1)...

X(N-1)?

and theN×Nmatrix W=? ?????W

0W0W0···W0

0W1W2···WN-1

0W2W4···W2(N-1)

0WN-1W2(N-1)···W(N-1)2?

DFT in a matrix form:

X=Wx.

Result:Inverse DFT is given by

x=1NWHX,EE 524, Fall 2004, # 59 which follows easily by checkingWHW=WWH=NI, where Idenotes the identity matrix. Hermitian transpose: x

H= (xT)?= [x(1)?,x(2)?,...,x(N)?].

Also, "

?" denotes complex conjugation. Frequency Interval/Resolution:DFT"s frequency resolution F res≂1NT[Hz] and covered frequency interval

ΔF=NΔFres=1T=Fs[Hz].

Frequency resolution is determined only by the length of the observation interval, whereas the frequency interval is

determined by the length of sampling interval. Thus•Increase sampling rate=?expand frequency interval,•Increase observation time=?improve frequency resolution.

Question:Does zero padding alter the frequency resolution?EE 524, Fall 2004, # 510 Answer:No, because resolution is determined by the length of observation interval, and zero padding does not increase this length. Example (DFT Resolution):Two complex exponentials with two close frequenciesF1= 10Hz andF2= 12Hz sampled with the sampling intervalT= 0.02seconds. Consider various data lengthsN= 10,15,30,100with zero padding to 512 points.DFT withN= 10and zero padding to 512 points. Not resolved:F2-F1= 2Hz<1/(NT) = 5Hz.EE 524, Fall 2004, # 511

DFT withN= 15and zero padding to 512 points.

Not resolved:F2-F1= 2Hz<1/(NT)≈

3.3Hz.DFT withN= 30and zero padding to 512 points.

Resolved:F2-F1= 2Hz>1/(NT)≈1.7Hz.EE 524, Fall 2004, # 512

DFT withN= 100and zero padding to 512

points. Resolved:F2-F1= 2Hz>1/(NT) =

0.5Hz.EE 524, Fall 2004, # 513

DFT Interpretation Using

Discrete Fourier SeriesConstruct a periodic sequenceby periodic repetition ofx(n) everyNsamples: {?x(n)}={...,x(0),...,x(N-1)???? {x(n)},x(0),...,x(N-1)???? {x(n)},...} The discrete version of the Fourier Series can be written as ?x(n) =? kX kej2πknN=1N? k?

X(k)ej2πknN=1N?

X(k)W-kn,

where ?X(k) =NXk. Note that, for integer values ofm, we have W As a result, the summation in the Discrete Fourier Series (DFS) should contain onlyNterms: ?x(n) =1NN-1? k=0?

X(k)ej2πknNDFS.EE 524, Fall 2004, # 514

Inverse DFS

The DFS coefficients are given by

X(k) =N-1?

n=0?x(n)e-j2πknNinverse DFS.Proof. N-1? n=0?x(n)e-j2πknN=N-1? n=0? ?1NN-1? p=0?

X(p)ej2πpnN?

e-j2πknN N-1? p=0? X(p)?

1NN-1?

n=0e j2π(p-k)nN?

δ(p-k)=

?X(k).

The DFS coefficients are given by

X(k) =N-1?

n=0?x(n)e-j2πknNanalysis, ?x(n) =1NN-1? k=0?

X(k)ej2πknNsynthesis.EE 524, Fall 2004, # 515

•DFS and DFT pairs are identical, except that-DFT is applied to finite sequencex(n),-DFS is applied to periodic sequence?x(n).•Conventional (continuous-time) FS vs. DFS-CFS represents a continuous periodic signal using an

infinite number of complex exponentials, whereas-DFS represents a discrete periodic signal using a finite number of complex exponentials.EE 524, Fall 2004, # 516

DFT: PropertiesLinearity

Circular shift of a sequence: ifX(k) =DFT {x(n)}then

X(k)e-j2πkmN=DFT {x((n-m)modN)}

Also ifx(n) =DFT-1{X(k)}then

x((n-m)modN) =DFT-1{X(k)e-j2πkmN} where the operationmodNdenotes the periodic extension ?x(n)of the signalx(n): ?x(n) =x(nmodN).EE 524, Fall 2004, # 517

DFT: Circular ShiftN-1?

n=0x((n-m)modN)Wkn =WkmN-1? n=0x((n-m)modN)Wk(n-m)EE 524, Fall 2004, # 518 =WkmN-1? n=0x((n-m)modN)Wk(n-m)modN =WkmX(k), where we use the facts thatWk(lmodN)=Wkland that the order of summation in DFT does not change its result.

Similarly, ifX(k) =DFT {x(n)}, then

X((k-m)modN) =DFT {x(n)ej2πmnN}.

DFT: Parseval"s Theorem

N-1? n=0x(n)y?(n) =1NN-1? k=0X(k)Y?(k) Using the matrix formulation of the DFT, we obtain y

Hx=?1NWHY?

H?1NWHY?

1N2YHWWH????

NIX=1NYHX.EE 524, Fall 2004, # 519

DFT: Circular Convolution

IfX(k) =DFT {x(n)}andY(k) =DFT {y(n)}, then

X(k)Y(k) =DFT {{x(n)}?{y(n)}}

Here,?stands for circular convolution defined by

{x(n)}?{y(n)}=N-1? m=0x(m)y((n-m)modN).

DFT {{x(n)}?{y(n)}}

N-1? n=0? ?N-1 m=0x(m)y((n-m)modN)? {x(n)}?{y(n)}W kn N-1? m=0? ?N-1 n=0y((n-m)modN)Wkn?

Y(k)Wkmx(m)

=Y(k)N-1? m=0x(m)Wkm

X(k)=X(k)Y(k).EE 524, Fall 2004, # 520

quotesdbs_dbs20.pdfusesText_26

[PDF] [PDF] Discrete Fourier Transform (DFT)

Discrete Fourier Transform (DFT)Recall the DTFT:

X(ω) =∞?

A finite signal measured atNpoints:

0, n≥N,

Sample the spectrumX(ω)in frequency so that

X(k) =X(kΔω),Δω=2πN=?

X(k) =N-1?

Theinverse DFTis given by:

1NN-1?

δ(m-n)=x(n).EE 524, Fall 2004, # 52

The DFT pair:X(k) =N-1?

X(k) =N-1?

EE 524, Fall 2004, # 54

Periodicity of DFT SpectrumX(k+N) =N-1?

2π).

Example:DFT of a rectangular pulse:

0,otherwise.

X(k) =N-1?

N-Mpositions},

Y(k) =N-1?

DFT and DTFT of a Rectangular Pulse with

1/Mrather than1/N,•Zero padding is very important for fast DFT implementation

X(1)...

X(N-1)?

0W0W0···W0

0W1W2···WN-1

0W2W4···W2(N-1)

0WN-1W2(N-1)···W(N-1)2?

DFT in a matrix form:

Result:Inverse DFT is given by

H= (xT)?= [x(1)?,x(2)?,...,x(N)?].

Also, "

ΔF=NΔFres=1T=Fs[Hz].

DFT withN= 15and zero padding to 512 points.

Not resolved:F2-F1= 2Hz<1/(NT)≈

3.3Hz.DFT withN= 30and zero padding to 512 points.

DFT withN= 100and zero padding to 512

0.5Hz.EE 524, Fall 2004, # 513

DFT Interpretation Using

X(k)ej2πknN=1N?

X(k)W-kn,

X(k)ej2πknNDFS.EE 524, Fall 2004, # 514

Inverse DFS

The DFS coefficients are given by

X(k) =N-1?

X(p)ej2πpnN?

1NN-1?

δ(p-k)=

The DFS coefficients are given by

X(k) =N-1?

X(k)ej2πknNsynthesis.EE 524, Fall 2004, # 515

DFT: PropertiesLinearity

X(k)e-j2πkmN=DFT {x((n-m)modN)}

Also ifx(n) =DFT-1{X(k)}then

DFT: Circular ShiftN-1?

Similarly, ifX(k) =DFT {x(n)}, then

X((k-m)modN) =DFT {x(n)ej2πmnN}.

DFT: Parseval"s Theorem

Hx=?1NWHY?

H?1NWHY?

1N2YHWWH????

NIX=1NYHX.EE 524, Fall 2004, # 519

DFT: Circular Convolution

IfX(k) =DFT {x(n)}andY(k) =DFT {y(n)}, then

X(k)Y(k) =DFT {{x(n)}?{y(n)}}

Here,?stands for circular convolution defined by

DFT {{x(n)}?{y(n)}}

Y(k)Wkmx(m)

X(k)=X(k)Y(k).EE 524, Fall 2004, # 520