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π 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

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

1. 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
2. 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.

Figure 7

Also, recall,

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 NN-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

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)

Problem 2

Why does Equation 14 equal Sn S n ?

Solution 2

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 .

[ Click for Solution 2 ] [ Hide Solution 2 ]

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