1.7 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}}{}X()$$ $$x(t)\stackrel{\mathrm{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).

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

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

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, , N-1\}\colon {}_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, , N-1\}$

Periodicity of the dft

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

Also, recall,

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)$ .

Inverse dtft of s()

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

Connections

Combine signals in to get signals in .