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

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: x n ↔ DTFT X ω x t ↔ CTFT X Ω where ω and Ω are continuous frequency variables.

Sampling DTFT Consider the DTFT of a discrete-time (DT) signal x n . Assume x n is of finite duration N (i.e., an N-point signal). X ω n N 1 0 x n ω n where X ω is the continuous function that is indexed by the real-valued parameter ω . The other function, x n , is a discrete function that is indexed by integers. We want to work with X ω on a computer. Why not just sample X ω ? X k X 2 N k n N 1 0 x n 2 k N n In we sampled at ω 2 N k where k 0 1 … N 1 and X k for k 0 … N 1 is called the Discrete Fourier Transform (DFT) of x n .

Finite Duration DT Signal The DTFT of the image in is written as follows: X ω n N 1 0 x n ω n where ω is any 2 -interval, for example ω .

Sample X(ω) where again we sampled at ω 2 N k where k 0 1 … M 1 . For example, we take M 10 . In the following section we will discuss in more detail how we should choose M, the number of samples in the 2 interval. (This is precisely how we would plot X ω in Matlab.)

Choosing M

Case 1 Given N (length of x n ), choose ≫ M N to obtain a dense sampling of the DTFT ():

Case 2 Choose M as small as possible (to minimize the amount of computation). In general, we require M N in order to represent all information in n n 0 … N 1 x n Let's concentrate on M N : x n ↔ DFT X k for n 0 … N 1 and k 0 … N 1 numbers ↔ N numbers

Discrete Fourier Transform (DFT) Define X k X 2 k N where N length x n and k 0 … N 1 . In this case, M N . DFT X k n N 1 0 x n 2 k N n Inverse DFT (IDFT) x n 1 N k N 1 0 X k 2 k N n

Interpretation Represent x n in terms of a sum of N complex sinusoids of amplitudes X k and frequencies k k 0 … N 1 ω k 2 k N Fourier Series with fundamental frequency 2 N

Remark 1 IDFT treats x n as though it were N-periodic. x n 1 N k N 1 0 X k 2 k N n where n 0 … N 1 What about other values of n? x n N ???

Remark 2 Proof that the IDFT inverts the DFT for n 0 … N 1 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 ???

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

DFT Formula 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 Using the above equation, we can solve and get the following results: x 0 4 x 1 0 x 2 0 x 3 0 Sample DTFT. Using the same figure, , we will take the DTFT of the signal and get the following equations: X ω n 0 3 ω n 1 4 ω 1 ω ??? Our sample points will be: ω k 2 k 4 2 k where k 0 1 2 3 ().

Periodicity of the DFT DFT X k consists of samples of DTFT, so X ω , a 2 -periodic DTFT signal, can be converted to X k , an N-periodic DFT. X k n N 1 0 x n 2 k N n where 2 k N n is an N-periodic basis function (See ).

Also, recall, 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 ??? Illustration

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 ω , as depicted in . S ω will represent the sampling function applied to X ω and is illustrated in as well. This will result in our discrete-time sequence, X k .

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

Inverse DTFT of S(ω) k δ ω 2 k N Given the above equation, we can take the DTFT and get the following equation: N m δ n m N S n Why does equal S n ? S n is N-periodic, so it has the following Fourier Series: c k 1 N n N 2 N 2 δ n 2 k N n 1 N S n k 2 k N n where the DTFT of the exponential in the above equation is equal to δ ω 2 k N . So, in the time-domain we have ():

Connections

Combine signals in to get signals in .