3.12 The dft: frequency domain with a computer analysis

Introduction

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

Much of the theoretical analysis of such systems relied on frequency domain representations. How do we carry out thesefrequency domain analysis on the computer? Recall the following relationships: $$x(n)\stackrel{\mathrm{DTFT}}{\leftrightarrow }X(\omega )$$ $$x(t)\stackrel{\mathrm{CTFT}}{\leftrightarrow }X(\Omega )$$ where $\omega$ and $\Omega$ 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).

We want to work with $X(\omega )$ on a computer. Why not just sample $X(\omega )$ ?

Finite duration dt signal

The DTFT of the image in is written as follows:

$X(\omega )=\sum_{n=0}^{N-1} x(n)e^{-i\omega n}$

where $\omega$ is any $2\pi$ -interval, for example $-\pi \le \omega \le \pi$ .

Sample x(Ω)

where again we sampled at $\omega =\frac{2\pi }{N}k$ where $k=\{0, 1, \dots , 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\pi$ interval.

(This is precisely how we would plot $X(\omega )$ in Matlab.)

Choosing m

Case 1

Given $N$ (length of $x(n)$ ), choose $\gg (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\ge N$ in order to represent all information in $$\forall n, n=\{0, \dots , N-1\}\colon x(n)$$ Let's concentrate on $M=N$ : $$x(n)\stackrel{\mathrm{DFT}}{\leftrightarrow }X(k)$$ for $n=\{0, \dots , N-1\}$ and $k=\{0, \dots , N-1\}$ $$\mathrm{numbers}\leftrightarrow \mathrm{N \; numbers}$$

Discrete fourier transform (dft)

Define

Interpretation

Represent $x(n)$ in terms of a sum of $N$ complex sinusoids of amplitudes $X(k)$ and frequencies $$\forall k, k\in \{0, \dots , N-1\}\colon {\omega }_k=\frac{2\pi k}{N}$$

Remark 1

IDFT treats $x(n)$ as though it were $N$ -periodic.

Remark 2

Proof that the IDFT inverts the DFT for $n\in \{0, \dots , N-1\}$

Computing dft

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

• DFT Formula
  $X(k)=\sum_{n=0}^{N-1} x(n)e^{-i\times 2\pi \frac{k}{N}n}=1+e^{-i\times 2\pi \frac{k}{4}}+e^{-i\times 2\pi \frac{k}{4}\times 2}+e^{-i\times 2\pi \frac{k}{4}\times 3}=1+e^{-i\frac{\pi }{2}k}+e^{-i\pi k}+e^{-i\frac{3}{2}\pi k}$
  Using the above equation, we can solve and get thefollowing 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(\omega )=\sum_{n=0}^3 e^{-i\omega n}=\frac{1-e^{-i\times 4\omega }}{1-e^{-i\omega }}=\mathrm{???}$
  Our sample points will be: $${\omega }_k=\frac{2\pi k}{4}=\frac{\pi }{2}k$$ where $k=\{0, 1, 2, 3\}$ ( ).

Periodicity of the dft

DFT $X(k)$ consists of samples of DTFT, so $X(\omega )$ , a $2\pi$ -periodic DTFT signal, can be converted to $X(k)$ , an $N$ -periodic DFT.

Also, recall,

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

Inverse dtft of s(Ω)

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

Connections

Combine signals in to get signals in .