Read dft.pdf text version

Discrete Fourier Transform

Spring 2012

Outline

Periodic Sequences Discrete Fourier Series Fourier Transform of Periodic Signals Sampling the Fourier Transform Discrete Fourier Transform Linear Convolution Using the Discrete Fourier Transform Discrete Cosine Transforms

Discrete Fourier Transform

Periodic Sequences

Definition (periodic sequence, periodic signal) A sequence x [n] is said to be periodic with period N if ~ x [n + N] = x [n], ~ ~ For example, a periodic impulse train

for any integer n.

p [n] = ~

r =-

[n - rN],

n = . . . , -1, 0, 1, 2, . . .

a complex exponential signal e ~k [n] = e j (

2k N

)n ,

n = . . . , -1, 0, 1, 2, . . .

Discrete Fourier Transform

Discrete Fourier Series

Theorem (discrete Fourier series) Any periodic sequence can be represented as a sum of the complex exponentials. Such a representation is called a discrete Fourier series (DFS). Specifically, let x [n] be a periodic sequence with period ~ N. Then N-1 2 1 ~ X [k]e j ( N k )n . x [n] = ~ N k=0 Note that the frequencies of the complex exponentials are related to the period N via 2k k = . N

Discrete Fourier Transform

Orthogonality

The complex exponentials of a DFS are orthogonal. That is,

N-1

ej(

n=0

2k N

)n e -j

2k N

n

= Nkk .

If k = k ,

N-1

e

n=0

j ( 2k )n -j N

e

2k N

N-1 n

=

n=0

e

j

2(k-k ) N

n

=

1-e

j j

2(k-k ) N 2(k-k ) N

nN

= 0.

1-e

2k N

If k = k ,

N-1

e

n=0

j ( 2k )n -j N

N-1 n

e

=

n=0

1 = N.

Discrete Fourier Transform

DFS Coefficients

Theorem (DFS coefficients) ~ The coefficients X [k] of the DFS of x [n] can be obtained by ~

N-1

~ X [k] =

n=0

x [n]e -j ( ~

2k N

)n .

Proof:

N-1 N-1 N-1

2k N

x [n]e -j ( ~

n=0

)n =

1~ j X [k ]e N n=0 k =0 e

j

2k N

2k N

n -j ( 2k )n N

e

1 = N

N-1

N-1

~ X [k ]

k =0 n=0

n -j ( 2k )n N

e

1 = N

N-1

~ X [k ]Nkk

k =0

~ = X [k].

Discrete Fourier Transform

Periodicity

Theorem ~ X [k] can be treated as a spectral sequence. Clearly, it is periodic with the same period as x [n]. ~

N-1

~ X [k + N] =

n=0 N-1

x [n]e -j ( N (k+N))n ~

2

=

n=0

x [n]e -j ( N k )n ~

2

~ = X [k].

Discrete Fourier Transform

The Analysis Equation

Definition (analysis equation) Defining WN

e -j( N ) ,

2

we can rewrite the equation for DFS coefficients as

N-1

~ X [k] =

n=0

kn x [n]WN . ~

This is called the analysis equation. ~ It yields the weights of the complex exponentials X [k], which is an analysis of the spectral content of x [n]. ~

Discrete Fourier Transform

The Synthesis Equation

Definition (synthesis equation) Complementary to the analysis equation, we have x [n] = ~ 1 N

N-1 -kn ~ X [k]WN . k=0

This is called the synthesis equation. Definition (DFS pair) ~ The following notation is used to denote a DFS pair (~ [n], X [k]): x x [n] ~

DFS

~ X [k].

Discrete Fourier Transform

Example: Temporal Periodic Impulse Train

Consider a periodic impulse train in the temporal domain

p [n] = ~

r =-

[n - rN].

By the analysis equation, the DFS coefficients are

N-1

~ P[k] =

n=0

0 kn p [n]WN = WN = 1. ~

That is, the spectral sequence is flat.

Discrete Fourier Transform

Example: Spectral Periodic Impulse Train

Consider a periodic impulse train in the spectral domain

~ Y [k] =

r =-

N [k - rN].

By the synthesis equation, the signal is y [n] = ~ 1 N

N-1 -kn 0 ~ Y [k]WN = WN = 1. k=0

That is, the temporal sequence is flat.

Discrete Fourier Transform

Periodic Rectangular Sequence

Suppose x [n] is periodic with period N = 10. In one period, ~ x [n] = ~ 1, 0 n 4, 0, 5 n 9.

By the analysis equation, the DFS coefficients are

4

~ X [k] =

n=0

kn 1 · W10 =

5k 1 - W10 k 1 - W10

=e

-j 4 k 10

sin k 2 sin k 10

.

Discrete Fourier Transform

Properties of DFS

linearity a~[n] + b~ [n] x y shift x [n - m] ~ duality

DFS ~ x [n] X [k] ~ DFS

DFS

~ ~ aX [k] + bY [k]

km ~ WN X [k]

DFS ~ X [n] N x [-k] ~

symmetry ~ x [n] X [-k], ~

DFS

~ x [-n] X [k] ~

DFS

Discrete Fourier Transform

Proof: Shift

Let y [n] ~ x [n - m]. According to the analysis equation, we have ~

N-1

~ Y [k] =

n=0 N-1

kn y [n]WN ~

=

n=0 N-1

kn x [n - m]WN ~

=

n=0

x [n - m]WN ~

N-1

k(n-m)

km WN

km = WN

x [n - m]WN ~

k(n-m)

=

n=0 km ~ WN X [k].

Discrete Fourier Transform

Proof: Duality

Begin with the synthesis equation. 1 x [n] = ~ N

n -n N-1 -kn ~ X [k]WN k=0 N-1 kn ~ X [k]WN k=0 N-1

- - N x [-n] = -- ~ - - N x [-k] = -- ~

n=0 n k

kn ~ X [n]WN .

~ The last one is the analysis equation of X [n]! Therefore,

DFS ~ X [n] N x [-k]. ~

Discrete Fourier Transform

Periodic Convolution

Definition (periodic convolution) The periodic convolution of two periodic sequences of period N, ~ X [n] and y [n], is defined as ~

N-1

x [n] ~

y [n] = ~

m=0

x [m]~ [n - m]. ~ y

Let z [n] x [n] y [n]. ~ ~ ~ It is not difficult to see that z [n] a periodic sequence of period N. ~ What is the DFS for z [n]? ~

Discrete Fourier Transform

Periodic Convolution Theorem

Theorem (periodic convolution theorem) x [n] ~ y [n] ~

DFS

~ ~ X [k]Y [k]. x [n] ~ y [n], we have ~

k(n-m)

Applying the analysis equation to z [n] ~

N-1 N-1 kn z [n]WN = ~ n=0 N-1 n=0 N-1 km x [m]WN ~ m=0 n=0 m=0 N-1

~ Z [k] = =

km x [m]~ [n - m] WN WN ~ y

y [n - m]WN ~

k(n-m)

~ ~ = X [k]Y [k].

Discrete Fourier Transform

Spectrum of a Discrete-Time Signal

Definition (spectrum of a DT signal) The spectrum of a discrete-time signal is the discrete-time Fourier transform (DTFT) of the signal. That is,

X (e ) =

n=-

j

x[n]e -jn .

Note that X (e j ) is a function of a continuous variable is a periodic function with period 2 completely determines x[n], with 1 x[n] = 2

X (e j )e jn d ,

-

n = . . . , -1, 0, 1, . . .

Discrete Fourier Transform

Spectrum of a Complex Exponential

Theorem The spectrum of a complex exponential with frequency 0 , e [n] = e j0 n , ~ is ~ E (e j ) = 2

l=-

- < 0 < ,

( - 0 - 2l ).

Discrete Fourier Transform

Proof

~ The inverse DTFT of E (e j ) must be e [n], ~ 1 2

-

~ E (e j )e jn d = e [n] = e j0 n . ~

Therefore, within the integration interval [-, ], ~ E (e j ) = 2( - 0 ). ~ Furthermore, since E (e j ) must be periodic, we have

~ E (e j ) = 2

l=-

( - 0 - 2l ).

Discrete Fourier Transform

Periodic Signal as Sum of Complex Exponentials

By the synthesis equation, a periodic signal x [n] can be expressed as ~ 1 x [n] = ~ N

N-1

2 ~ X [k]e j N kn ,

k=0

2

which is a sum of complex exponentials e j ( N k )n .

Discrete Fourier Transform

Spectrum of a Periodic Singal

Using the DTFT of e j ( N k )n , we have the spectrum of x [n], ~

2

1 ~ X (e j ) = N = =

N-1

~ X [k] 2

k=0 N-1 l=-

-

2k + 2l N

2 N 2 N

2(k + lN) ~ X [k + lN] - N .

k=0 l=-

k =-

2k ~ X [k ] - N

Clearly, the spectrum of a periodic sequence is completely contained in the DFS coefficients ~ X [k], k = 0, 1, . . . N - 1.

Discrete Fourier Transform

Example: Periodic Impulse Train

As an example, consider the periodic impulse train with period N

p [n] = ~

r =-

[n - rN].

To find the spectrum, we only need to know ~ P[k], k = 0, 1, . . . N - 1. ~ By the analysis equation, P[k] = 1. Therefore, the spectrum is 2 2k ~ - P(e j ) = N k =- N

.

Discrete Fourier Transform

Periodic Signal as Convolution with Impulse Train

Let x [n] be a periodic sequence with period N. Let x[n] be one ~ period of x [n], i. e., ~ x[n] = (0 n N - 1) ? x [n] : 0. ~ Then x [n] can be expressed via x[n] as ~

x [n] = ~

r =-

x[n - rN]

= x[n]

r =-

[n - rN]

= x[n] p [n] ~

Discrete Fourier Transform

Periodic Extension

Definition (periodic extension) Given a signal s[n],

~[n] s

r =-

s[n - rN],

is called the periodic extension of s[n] with period N. This is also written as ~[n] s s[(n modulo N)] s[((n))N ].

Normally, N is not smaller than the duration of s[n].

Discrete Fourier Transform

Spectrum

It follows from x [n] = x[n] p [n] that the spectrum of x [n] is ~ ~ ~ ~ ~ X (e j ) = X (e j )P(e j ) = X (e )

j

2k 2 - N k=- N .

2k 2 X e j(2/N)k - = N k=- N

Discrete Fourier Transform

DFS Coefficients are Samples of DTFT

Equating the spectrum of a periodic signal x [n] in two different ~ expressions, i.e. sum of complex exponentials and convolution with periodic impulse trains, 2k 2 ~ ~ X [k] - X (e j ) = N k=- N

. . . DFS . . . convolution,

= we have

2k 2 X e j(2/N)k - N k=- N ~ X [k] = X (e j )|= 2k .

N

~ That is, X [k] are samples of X (e j ) at equally spaced frequencies.

Discrete Fourier Transform

Example

Consider the periodic rectangular sequence with period N = 10. In one period 1, 0 n 4, x [n] = ~ 0, 5 n 9. The spectrum of x[n] is

4

X (e ) =

n=0

j

e -jn = e -j2

sin 5 2 . sin 2

It is straightforward to verify that

4 ~ X [k] = e -j 10 k

sin k 2 sin k 10

= X (e j )|= 2k .

10

Discrete Fourier Transform

Sampling the Fourier Transform

Consider an aperiodic signal a[n] and do the following. Obtain the spectrum A(e j ) of a[n]. ~ Sample A[k] at frequencies k = 2k from A(e j ). N ~ [k], apply the synthesis equation of DFS and obtain a With X periodic sequence ~[n]. a In summary, we have a[n] -- -

DTFT

A(e j )

-- --

sampling

~ A[k]

- -

DFS

a ^[n].

What is the relationship between a[n] and ^[n]? a

Discrete Fourier Transform

Theorem

Theorem a ^[n] is the periodic extension of a[n] with period N. 1 ^[n] = a N = =

m N-1

1 -kn ~ A[k]WN = N k=0 a[m]e -j

k=0 m

2k m N

N-1 -kn A(e jk )WN k=0 -kn WN

1 N

N-1

a[m]

1 N

N-1

WN

k=0

-k(n-m)

=

m

a[m]~ [n - m] = p

r

a[n - rN] = ~[n]. a

Discrete Fourier Transform

Aliasing

Consider the case that a[n] is of finite duration M. If N < M (undersamplng), the copies a[n - rN] would overlap in their span. This is called time-domain aliasing. If N = M, a[n] corresponds to one period of ~[n]. a If N > M, a[n] can still be extracted, along with N - M zeros in one period of ~[n]. a

Discrete Fourier Transform

Frequency-Domain Sampling Theorem

Theorem (frequency-domain sampling theorem) For a finite-duration sequence a[n] of length M, it suffices to represent A(e j ) by N samples in [0, 2) with N M. The following diagram shows how this is possible. A[k] - -

DFS

a ~[n]

--- --

one period

a[n]

-- -

DTFT

A(e j ).

Using a higher number of samples also works, and it leads to finer spectral resolution.

Discrete Fourier Transform

Discrete Fourier Transform

Definition (discrete Fourier transform) The discrete Fourier transform (DFT) of a finite-duration sequence x[n] of length N is defined as

N-1

X [k] =

n=0

kn x[n]WN ,

0 k N - 1.

Discrete Fourier Transform

Discrete Fourier Transform

Definition (inverse discrete Fourier transform) The inverse discrete Fourier transform (IDFT) is defined as 1 x[n] = N

N-1 -kn X [k]WN , k=0

0 n N - 1.

We henceforth denote a DFT pair by x[n] X [k].

DFT

Discrete Fourier Transform

Circular Shift

Definition (circular shift) The circular shift by m of an N-point signal x[n] is defined as xm [n] = x[((n - m))N ], 0 n N - 1, 0, otherwise

A circular shift can be visualized in two ways: construct periodic extension x [n], shift x [n] to the right by m, ~ ~ and truncate x [n] to the segment 0 n N - 1; ~ place the points of x[n] clockwise on a circle, and rotate the points clockwise.

Discrete Fourier Transform

Properties of DFT

linearity ax[n] + by [n] circular shift xm [n] duality x[n] X [k] symmetry x [n] X [((-k))N ],

DFT DFT DFT

DFT

aX [k] + bY [k] e -j N km X [k]

2

X [n] Nx[((-k))N ]

DFT

x [((-n))N ] X [k]

DFT

Discrete Fourier Transform

Proof: Circular Shift

xm [n]

DFT

e -j N km X [k]

2

This can be argued as follows: x[n] X [k]

DFS ~ x [n] X [k] ~ DFT

~ x [n - m] e -j N km X [k] ~ xm [n] e -j N km X [k]

DFT

2

DFS

2

Discrete Fourier Transform

Circular Convolution

Definition (N-point circular convolution) The N-point circular convolution of two finite-duration sequences x[n] and y [n] is defined as follows:

N-1

x[n]

N

y [n] =

m=0 N-1

x[((m))N ]y [((n - m))N ] x[m]y [((n - m))N ],

m=0

=

0 n N - 1.

Let z[n] x[n] N y [n]. z[n] is of finite duration by definition. z[n] is one period of the periodic convolution z [n] ~

x [n] ~

y [n]. ~

Discrete Fourier Transform

Circular Convolution Theorem

Theorem Let x[n] and y [n] be of finite duration N. Then x[n]

N

y [n]

-- - - - - -

N-point DFT

X [k]Y [k].

~ ~ Let x [n], y [n] be the periodic extensions and X [k], Y [k] be the DFS ~ ~ coefficients. By the periodic convolution theorem, x [n] ~ y [n] ~

DFS

~ ~ X [k]Y [k].

Taking one period, we get x[n]

N

y [n]

DFT

X [k]Y [k].

Discrete Fourier Transform

Convolution of Finite-Duration Sequences

Theorem (finite-duration convolution) Let x[n] and y [n] be causal and finite-duration sequences with durations L and M respectively, and

L-1

z[n]

x[n] y [n] =

m=0

x[m]y [n - m].

Then z[n] is sure to be causal and finite-duration of length no more than L + M - 1.

Discrete Fourier Transform

Proof

We show that z[n] = 0 for n < 0 and n > L + M - 2. If n < 0, we have n - m < n < 0, 0 m L - 1.

Therefore, the convolution sum is 0 as y [n - m] = 0. If n > L + M - 2, we have n - m > L + M - 2 - (L - 1) = M - 1, 0 m L - 1.

Therefore, the convolution sum is 0 as y [n - m] = 0. Since z[n] can be nonzero only for 0 n L + M - 2, we conclude that the duration of z[n] is at most L + M - 1.

Discrete Fourier Transform

Linear Convolution

Theorem Let x[n] and y [n] be causal and finite-duration sequences with durations L and M respectively. For any N L + M - 1, we have x[n] y [n] = x[n]

L-1 N

y [n],

0 n N - 1.

N-1

x[n] y [n] =

m=0 N-1

x[m]y [n - m] =

m=0

x[m]y [n - m]

=

m=0

x[m]y [((n - m))N ]

N

= x[n]

y [n].

Discrete Fourier Transform

Implementation of Convolution via DFT

By circular convolution theorem, the DFT of z[n] = x[n] Z [k] = X [k]Y [k]. Therefore, the convolution z[n] of two causal and finite-duration sequences x[n] and y [n] can be obtained as follows. pad x[n] and y [n] with zeros to length N L + M - 1; compute DFT of X [k] and Y [k]; compute IDFT of Z [k] = X [k]Y [k]; extract from z[n] a finite-duration sequence of length L + M - 1. y [n] is

N

Discrete Fourier Transform

Information

43 pages

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

850363


You might also be interested in

BETA
Microsoft Word - R-2008-ECE-SYLLABUS.doc
SE EXTC Syllabus
TD_apscom2006_fullpaper.dvi
Microsoft Word - EE-III-IV-11-12.doc