Navigation

Content Actions

Download module PDF
Add to ...
Add the module to:
- My Favorites
- A lens
- An external social bookmarking service
- My FavoritesLogin required (What is 'My Favorites'?)
  'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
- A lensLogin required (What is a lens?)
  Definition of a lens
  Lenses
  A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.
  What is in a lens?
  Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.
  Who can create a lens?
  Any individual Connexions member, a community, or a respected organization.
  What are tags?
  Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.
- External bookmarks
E-mail the author
Print this Web page
Rate this module (How does the rating system work?)
Rating system
Ratings
Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).
How to rate a module
Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.
PoorFairOKGoodExcellent
(0 ratings)(Login required)

Related material

Collections using this module

Recently Viewed: This feature requires Javascript to be enabled.

The DFT: Frequency Domain with a Computer Analysis

Summary: This module will take the ideas of sampling CT signals further by examining how such operations can be performed in the frequency domain and by using a computer.

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

If the two examples below are mathematically the same, your browser is correctly displaying MathML, and you can dismiss this message.

Example 1:	$\frac{\sqrt{\frac{1}{2}}}{\sqrt{{f (x + y)}^{2}}} \frac{\sqrt{1}}{2} 〈 ℝ 〉$	Example 2:		(Hide examples)

Introduction

We just covered ideal (and non-ideal) (time) sampling of CT signals. This enabled DT signal processing solutions for CT applications (Figure 1):

**Figure 1**

Much of the theoretical analysis of such systems relied on frequency domain representations. How do we carry out these frequency domain analysis on the computer? Recall the following relationships: xn ↔ DTFT Xω x n ↔ DTFT X ω xt ↔ CTFT XΩ x t ↔ CTFT X Ω where ωω and ΩΩ are continuous frequency variables.

Sampling DTFT

Consider the DTFT of a discrete-time (DT) signal xn x n . Assume xn x n is of finite duration N N (i.e., an NN-point signal).

Xω=∑n=0N−1xnⅇ-ⅈωn

X ω n N 1 0 x n ω n

(1)

where Xω

X ω

is the continuous function that is indexed by the real-valued parameter -π≤ω≤π

. The other function, xn

x n

, is a discrete function that is indexed by integers.

We want to work with Xω X ω on a computer. Why not just sample Xω X ω ?

Xk=X2πNk=∑n=0N−1xnⅇ-ⅈ2πkNn

X k X 2 N k n N 1 0 x n 2 k N n

(2)

In Equation 2 we sampled at ω=2πNk

ω 2 N k

where k=01…N−1

k 0 1 … N 1

and Xk

X k

for k=0…N−1

k 0 … N 1

is called the Discrete Fourier Transform (DFT) of xn

x n

Example 1

**Figure 2**
Finite Duration DT Signal

The DTFT of the image in Figure 2 is written as follows:

Xω=∑n=0N−1xnⅇ-ⅈωn

X ω n N 1 0 x n ω n

(3)

where ω

is any 2π

-interval, for example -π≤ω≤π

**Figure 3**
Sample X(ω)

where again we sampled at ω=2πNk ω 2 N k where k=01…M−1 k 0 1 … M 1 . For example, we take M=10 M 10 . In the following section we will discuss in more detail how we should choose MM, the number of samples in the 2π 2 interval.

(This is precisely how we would plot Xω X ω in Matlab.)

Choosing M

Case 1

Given NN (length of xn x n ), choose M≫N ≫ M N to obtain a dense sampling of the DTFT (Figure 4):

**Figure 4**

Case 2

Choose MM as small as possible (to minimize the amount of computation).

In general, we require M≥N M N in order to represent all information in ∀n,n=0…N−1:xn n n 0 … N 1 x n Let's concentrate on M=N M N : xn ↔ DFT Xk x n ↔ DFT X k for n=0…N−1 n 0 … N 1 and k=0…N−1 k 0 … N 1 numbers ↔ N numbers numbers↔N numbers

Discrete Fourier Transform (DFT)

Define

Xk≡X2πkN

X k X 2 k N

(4)

where N=lengthxn

N length x n

and k=0…N−1

k 0 … N 1

. In this case, M=N

M N

DFT

Xk=∑n=0N−1xnⅇ-ⅈ2πkNn

X k n N 1 0 x n 2 k N n

(5)

Inverse DFT (IDFT)

xn=1N∑k=0N−1Xkⅇⅈ2πkNn

x n 1 N k N 1 0 X k 2 k N n

(6)

Interpretation

Represent xn x n in terms of a sum of NN complex sinusoids of amplitudes Xk X k and frequencies ∀k,k∈0…N−1: ω k =2πkN k k 0 … N 1 ω k 2 k N

Think:

Fourier Series with fundamental frequency 2πN

2 N

Remark 1

IDFT treats xn x n as though it were NN-periodic.

xn=1N∑k=0N−1Xkⅇⅈ2πkNn

x n 1 N k N 1 0 X k 2 k N n

(7)

where n∈0…N−1

n 0 … N 1

Exercise 1

What about other values of nn?

Solution

xn+N=??? x n N ???

Remark 2

Proof that the IDFT inverts the DFT for n∈0…N−1 n 0 … N 1

1N∑k=0N−1Xkⅇⅈ2πkNn=1N∑k=0N−1∑m=0N−1xmⅇ-ⅈ2πkNmⅇⅈ2πkNn=???

1 N k N 1 0 X k 2 k N n 1 N k N 1 0 m N 1 0 x m 2 k N m 2 k N n ???

(8)

Example 2: Computing DFT

Given the following discrete-time signal (Figure 5) with N=4 N 4 , we will compute the DFT using two different methods (the DFT Formula and Sample DTFT):

**Figure 5**

DFT Formula
Xk=∑n=0N−1xnⅇ-ⅈ2πkNn=1+ⅇ-ⅈ2πk4+ⅇ-ⅈ2πk42+ⅇ-ⅈ2πk43=1+ⅇ-ⅈπ2k+ⅇ-ⅈπk+ⅇ-ⅈ32πk X k n N 1 0 x n 2 k N n 1 2 k 4 2 k 4 2 2 k 4 3 1 2 k k 3 2 k (9)
Using the above equation, we can solve and get the following results: x0=4 x 0 4 x1=0 x 1 0 x2=0 x 2 0 x3=0 x 3 0
Sample DTFT. Using the same figure, Figure 5, we will take the DTFT of the signal and get the following equations:
Xω=∑n=03ⅇ-ⅈωn=1−ⅇ-ⅈ4ω1−ⅇ-ⅈω=??? X ω n 0 3 ω n 1 4 ω 1 ω ??? (10)
Our sample points will be: ω k =2πk4=π2k ω k 2 k 4 2 k where k=0123 k 0 1 2 3 (Figure 6).

**Figure 6**

Periodicity of the DFT

DFT Xk X k consists of samples of DTFT, so Xω X ω , a 2π 2 -periodic DTFT signal, can be converted to Xk X k , an NN-periodic DFT.

Xk=∑n=0N−1xnⅇ-ⅈ2πkNn

X k n N 1 0 x n 2 k N n

(11)

where ⅇ-ⅈ2πkNn

2 k N n

is an N

-periodic basis function (See Figure 7).

**Figure 7**

Also, recall,

xn=1N∑n=0N−1Xkⅇⅈ2πkNn=1N∑n=0N−1Xkⅇⅈ2πkNn+mN=???

x n 1 N n N 1 0 X k 2 k N n 1 N n N 1 0 X k 2 k N n m N ???

(12)

Example 3: Illustration

**Figure 8**

note:

When we deal with the DFT, we need to remember that, in effect, this treats the signal as an N

-periodic sequence.

A Sampling Perspective

Think of sampling the continuous function Xω X ω , as depicted in Figure 9. Sω S ω will represent the sampling function applied to Xω X ω and is illustrated in Figure 9 as well. This will result in our discrete-time sequence, Xk X k .

**Figure 9**

Recall:

Remember the multiplication in the frequency domain is equal to convolution in the time domain!

Inverse DTFT of S(ω)

∑k=-∞∞δω−2πkN

k δ ω 2 k N

(13)

Given the above equation, we can take the DTFT and get the following equation:

N∑m=-∞∞δn−mN≡Sn

N m δ n m N S n

(14)

Exercise 2

Why does Equation 14 equal Sn S n ?

Solution

Sn S n is NN-periodic, so it has the following Fourier Series:

c k =1N∫-N2N2δnⅇ-ⅈ2πkNndn=1N

c k 1 N n N 2 N 2 δ n 2 k N n 1 N

(15)

Sn=∑k=-∞∞ⅇ-ⅈ2πkNn

S n k 2 k N n

(16)

where the DTFT of the exponential in the above equation is equal to δω−2πkN

δ ω 2 k N

So, in the time-domain we have (Figure 10):

**Figure 10**

Connections

**Figure 11**

Combine signals in Figure 11 to get signals in Figure 12.

**Figure 12**

Comments, questions, feedback, criticisms?

Send feedback

E-mail the author of the module, The DFT: Frequency Domain with a Computer Analysis

Footer

More about this content: Metadata | Version History

This work is licensed by Robert Nowak under a Creative Commons Attribution License (CC-BY 1.0), and is an Open Educational Resource.

Last edited by Charlet Reedstrom on Jul 22, 2005 3:08 pm GMT-5.

Connexions

Navigation

Content Actions

Definition of a lens

Lenses

What is in a lens?

Who can create a lens?

What are tags?

Rating system

Ratings

How to rate a module

Related material

Similar content

Collections using this module

Recently Viewed

The DFT: Frequency Domain with a Computer Analysis

Introduction

Sampling DTFT

Example 1

Choosing M

Case 1

Case 2

Discrete Fourier Transform (DFT)

DFT

Inverse DFT (IDFT)

Interpretation

Think:

Remark 1

Exercise 1

Solution

Remark 2

Example 2: Computing DFT

Periodicity of the DFT

Example 3: Illustration

note:

A Sampling Perspective

Recall:

Inverse DTFT of S(ω)

Exercise 2

Solution

Connections

Comments, questions, feedback, criticisms?

Send feedback

Footer