### Discrete Time Fourier Transform Definition

Let us now consider aperiodic signals. We will derive spectral representations for them just as we did for aperiodic CT signals.

Consider an aperiodic DT signal $x[n]$ with non-zero between $N_1$ & $N_2$

Let us artificially define a periodic signal by repeating $x[n]$: $\hat{x}[n] \begin{cases} x[n], & N_1 \leq n < N_1 + N - 1 \\ x[n+N], & in general \end{cases}$

We can now express the periodic signal $\hat{x}[n]$ as a DTFS: $\hat{x}[n] = \sum_{k = 0}^{N-1} a_k e^{\frac{j 2 \pi n k}{N}}$ $a_k = \frac{1}{N} \sum_{n = \text{<}N \text{>}}^{} \hat{x}[n] e^{-\frac{j 2 \pi k n}{N}}, \text{ for any "N" period}$

If we include the specific cycle that includes $(N_1,N_2)$ we can write: $a_k = \frac{1}{N} \sum_{n= \text{<}N \text{>}}^{} x[n] e^{\frac{j 2 \pi k n}{N}}$ As we noted in the CT case $a_k$ does not tell us anything about the frequency. We would like to indicate the frequency in the representation.

A sidenote on frequency

In CT signals, the notion of frequency is well defined, since the notion of time (or space, in the case of spatial frequency) is defined.

The DT signals, all we have is a series of numbers. There is no notion of "time" since there is no explicit mapping from indices to time. So we can no longer talk about radians "per second."

To state it differently, we knew that the spacing between samples is $\Delta t$ seconds, and we observed L cycles in k samples, the frequency would be $\frac{L}{k \Delta t}$ radians/sec.

But if $\Delta t$ is not known, we only have $\frac{L}{k} = \frac{L}{k \Delta T} \Delta T$

We are multiplying the time variable out. Dimensionality-wise, this variable becomes radians/sec x sec = radians

Returning to our problem. We have: $\hat{x}[n] = \sum_{k = 0}^{N-1} a_k e^{\frac{j 2 \pi n k}{N}}$ $a_k = \frac{1}{N} \sum_{n = 0}^{N-1} \hat{x}[n] e^{-\frac{j 2 \pi k n}{N}}$ Since $x[n]$ is 0 outside this range $a_k = \frac{1}{N} \sum_{-\infty}^{\infty} \hat{x}[n] e^{-\frac{j 2 \pi k n}{N}}$

Note $\frac{2 \pi k}{N}$ is a frequency term.

So lets define a generic function: $X(\Omega) = \sum_{n = -\infty}^{\infty} x[n] e^{-j \Omega n}$ then $a_k = \frac{X(\Omega_o k)}{N}, \Omega_o = \frac{2 \pi}{N}$

Writing our equations in terms of $\Omega_o$, $\frac{1}{N} = \frac{\Omega_o}{2 \pi}$

We have: $\hat{x}[n] = \frac{1}{2 \pi} \sum_{k = 0}^{N -1} x(k \Omega_o) e^{j k \Omega_o n} \Omega_o$ and $x[n] = \lim_{N \to \infty} \hat{x}[n] = \lim_{\Omega_o \to 0} \hat{x}[n]$

Consider our synthesis equation for $\hat{x}[n]$

Note that at $k = 0$, $\Omega = k\Omega_o = 0$

And at $k = N$, $\Omega = k \Omega_o = 2 \pi$

We can write: $\hat{x}[n] = \frac{1}{2 \pi} \sum_{\Omega = 0, \Omega \pm \Omega_o}^{2 \pi - \Omega_o} X(\Omega) e^{j \Omega n} \Omega_o$

$\lim_{\Omega_o \to 0} \sum_{\Omega = 0, \Omega \pm \Omega_o}^{2 \pi - \Omega_o} X(\Omega) e^{j \Omega n} \Omega_o = \int_{0}^{2 \pi} X(\Omega) e^{j \Omega n } d \Omega \\$ $x[n] = \frac{1}{2 \pi} \int_{0}^{2 \pi} X(\Omega) e^{j \Omega n} d \Omega$ This along with: $X(\Omega) = \sum_{n = -\infty}^{\infty} x[n] e^{-j \Omega n}$

These specify the Fourier Tranform pair of equations to compute the frequency composition of aperiodic DT signals.

$X(\Omega)$ is called the discrete time Fourier transform of $x[n]$

The DTFT exists & is guaranteed to converge if: $\sum_{n} |x[n]| < \infty \text{ (absolutely summable) }$ $or$ $\sum_{n} |x[n]|^2 < \infty \text{ (finite energy)}$

An important property of DTFT: $X(\Omega) = X(\Omega + 2 \pi) (because a_k = a_{k +n})$

Easily shown: $e^{j \Omega n} = e^{j(\Omega + 2 \pi)n} = e^{j \Omega n} e^{j 2 \pi n}$ \begin{align*} X(\Omega + 2 \pi) &= \sum_{n = -\infty}^{\infty} x[n] e^{j (\Omega + 2 \pi)n} \\ &= \sum_{n = -\infty}^{\infty} x[n] e^{j \Omega n} \\ &= X(\Omega) \end{align*} $X(\Omega)$ is periodic with $2 \pi$ which is why the integral $x[n] = \frac{1}{2 \pi} \int_{0}^{2 \pi} X(\Omega) e^{j \Omega n} d \Omega$ is only over a $2 \pi$ range. In fact it can be over any $2 \pi$ range.

EXAMPLES

1. $x[n] = a^n u[n]$ \begin{align*} X(\Omega) &= \sum_{n = 0}^{\infty} a^n\ e^{-j \Omega n} \\ &= \frac{1}{1 - a e^{-j \Omega}} \end{align*}
2. $x[n] = a^{|n|}, |a| < 1$ (two-sided) \begin{align*} X(\Omega) &= \sum_{n = -\infty}^{\infty} a^{|n|} e^{-j \Omega n} \\ &= \sum_{n=0}^{\infty} \alpha^n e^{-j \Omega n} + \sum_{n = -\infty}^{-1}a^{-n}e^{-j \Omega n} \end{align*} We have \begin{align*} \sum_{n = -\infty}^{-1}a^{-n}e^{-j \Omega n} &= \sum_{m = 1}^{\infty} a^m e^{j \Omega m} \\ &= \frac{a e^{j \Omega}}{1 - a e^{j }\Omega} \end{align*} So \begin{align*} X(\Omega) &= \frac{1}{1 + a e^{-j \Omega}} + \frac{a e^{j \Omega}}{1 - a e^{j \Omega}} \\ &= \frac{1 - a^2}{1 - 2acos \Omega + a^2}, for |a| < 1, a >0 \end{align*}
3. $x[n] = \begin{cases} 1, & |n| \leq N_1 \\ 0, & |n| > N_1 \end{cases}$ \begin{align*} X(\Omega) &= \sum_{n = -N_1}^{N_1} e^{-j \Omega n} \\ &= \frac{sin \Omega (N_1 + \frac{1}{2})}{sin(\frac{\Omega}{2})} \end{align*}

This is the DT counterpart of the sinc function. Its periodic with $2 \pi$.

4. $x[n] = \delta[n]$ $X(\Omega) = \sum_{n = 0}^{\infty} \delta[n] e^{-j \Omega n} = 1$
5. The following example computes $x[n]$ given $X(\Omega)$

$X(\Omega) = \begin{cases} 1, & |\Omega| < \omega \\ 0, & \omega \leq |\Omega| < \pi \\ X(\Omega + 2 \pi) \end{cases}$ \begin{align*} x[n] &= \frac{1}{2 \pi} \int_{-\pi}^{\pi} X(\Omega) e^{-j \Omega n}d \Omega \\ &= \frac{1}{2 \pi} \int_{-\omega}^{\omega} e^{j \Omega n} d \Omega \\ &= \frac{sin \omega_n}{\pi n} \end{align*} $As \omega \rightarrow \pi, x[n] \rightarrow \delta[n]$
Back

### Relation Between Discrete time Fourier Series & the Discrete Time Fourier Transfrom

Earlier when we derived the DTFT of a signal $x[n]$. We did so by composing periodic signal $\tilde{x}[n]$ from $x[n]$ by repeating $x[n]$ every N samples & letting N go to infinity.

Now lets go the other way. Let $\tilde{x}[n]$ be a signal that's periodic with N

$\tilde{x}[n]$ can be expresses as a Fourier series as: $\tilde{x}[n] = \sum_{k = 0}^{K - 1} a_k e^{\frac{j 2 \pi n k}{N}}$

Now compose an aperiodic signal by slicing out one period of $\tilde{x}[n]$ starting at any sample N

$x[n] = \begin{cases} \tilde{x}[n], & M \leq n < M +N \\ 0, & else \end{cases}$

Let's compute the DTFT of $x[n]$ \begin{align*} X(\Omega) &= \sum_{-\infty}^{\infty} x[n] e^{-j \Omega n} \\ &= \sum_{M}^{M+N-1}x[n]e^{-j \Omega n} \end{align*}

Clearly as M changes $X(\Omega)$ changes. But at specific values $\Omega = \frac{2 \pi k}{N}$ $X(\Omega) = \sum_{n = M}^{M +N-1} \tilde{x}[n] e^{-\frac{j 2 \pi k}{N}} = N a_k$ $X(k \frac{2 \pi}{N}) = N a_k$

Thus $N a_k$ corresponds to snapshots of $X(\Omega)$ at $\Omega = \frac{2 \pi k}{N}$

In other words, although $X(\Omega)$ can change quite dramatically as M changes. Its values specifically at $\Omega = \frac{2 \pi k}{N}$ will not change!

This is because the DTFS is invariant if you compute it from ANY period of $\tilde{x}[n]$. The DTFS values are samples from the DTFT $X(\Omega)$ which varies with the cycle.

Back

### Discrete Time FT of a Periodic Signal

Let us begin by considering a complex exponential $e^{j \Omega_o n}$.

We would expect the DTFT of the signal to have an impulse at $\Omega = \Omega_o$. Also, since $e^{j \Omega_o n} = e^{j \Omega_o n}e^{j 2 \pi m n}$ or $e^{j \Omega_o n} = e^{j(\Omega_o + 2 \pi m)n}$

Another way to arrive at this conclusion is that the DTFT is periodic with $2 \pi$ so if there is an impulse at $\Omega_o$ there will also be impulese at $\Omega_o + 2 \pi n$.

At other frequencies we expect zero spectral value since the signal has no other frequency components.

So we expect: $e^{j \Omega_o n} \leftrightarrow C \sum_{m = -\infty}^{\infty} \delta(\Omega - \Omega_o - 2 \pi m)$

\begin{align*} DTFT(e^{j \Omega_o n}) &= \sum_{n = -\infty}^{\infty} e^{j \Omega_o n} e^{-j \Omega n} \\ &= C \sum_{m =-\infty}^{\infty} \delta(\Omega - \Omega_o - 2 \pi m) \end{align*}

As a matter of fact it is actually quite difficult to derive the above equation directly but we can do it backwards instead. Let: $X(\Omega) = 2 \pi \sum_{m = -\infty}^{\infty} \delta(\Omega - \Omega_o - 2 \pi m)$ We will show that the inverse DTFT of $X(\Omega)$ is $e^{j \Omega_o n}$. By the uniqueness property of DTFTs, the forward transform also holds: $X(\Omega) = 2 \pi \sum_{m = -\infty}^{\infty} \delta(\Omega - \Omega_o - 2 \pi m))$ $x[n] = \frac{2 \pi}{2 \pi} \int_{0}^{2 \pi} \sum_{m = -\infty}^{\infty} \delta(\Omega - \Omega_o - 2 \pi m) e^{j \Omega n} d \Omega$

We note that within any $2 \pi$ interval of $\Omega$, we get only ONE impulse $X(\Omega)$, since the impulses are spaces $2 \pi$ apart. So: \begin{align*} x[n] &= \int_{0}^{2 \pi} \sum_{m = -\infty}^{\infty} \delta(\Omega - \Omega_o - 2 \pi m) e^{j \Omega n} d\Omega \\ &= \int_{0}^{2 \pi} \delta(\Omega - \Omega_o) e^{j \Omega n} d \Omega \\ &= e^{j \Omega_o n} \end{align*}

Thus we confirm that $e^{j \Omega_o n}$ has a spectrum that is a periodic repetition of impulses at $\Omega_o \neq 2 m \pi$

This is true even if $e^{j \Omega_o n}$ is not periodic, i.e. if $\Omega_o$ is not a rational product of $\pi$.

So if we have any signal $x[n] = a_o e^{j \Omega_o n} + a_1 e^{j \Omega_1 n} + a_2 e^{j \Omega_2 n} + ... + a_k e^{j \Omega_k n}$ so by the linearity property of DTFT (which we are actually yet to define) $X(\Omega) = 2 \pi a_o \sum_{m = -\infty}^{\infty} \delta[\Omega - \Omega_o - 2 \pi m] + \\ + 2 \pi a_1 \sum_{m} \delta[\Omega - \Omega_1 - 2 \pi m] + \\ + 2 \pi a_2 \sum_{m} \delta[\Omega - \Omega_2 - 2 \pi m] + ...$

If even one of the $\Omega_{i's}$ is not a rational function of $\pi$, $x[n]$ is not periodic, but the relation still holds.

Let us now consider the DTFT of a periodic signal $x[n]$ with period N

$x[n]$ can be expresses as a DTFS: $x[n] = \sum_{k = 0}^{N-1}a_k e^{j \Omega_o k n} \text{ where } \Omega_o = \frac{2 \pi}{N}$

$\Rightarrow DTFT(x[n]) = 2 \pi \sum_{k = 0}^{N-1} a_k \sum_{l = -\infty}^{\infty} \delta(\Omega - \frac{2 \pi k}{N} - 2 \pi l)$ Or using $a_k = a_{k +N}$ \begin{align*} X(\Omega) &= 2 \pi \sum_{k = 0}^{N-1} \sum_{l = -\infty}^{\infty} a_k \delta(\Omega - 2 \pi (l + \frac{k}{N})) \\ &= 2 \pi \sum_{k = -\infty}^{\infty} a_k \delta(\Omega - \frac{2 \pi k}{N}) \end{align*}

The DTFT of a periodic signal consits of impulses space $\frac{2 \pi}{N}$ apart where the heights of the impulses fllow its Fourier series coefficients

Back

### A Lookahead: The Discrete Fourier Transform

The relationship between the DTFT of a periodic signal and the DTFS of a periodic signal composed from it leads us to the idea of a Discrete Fourier Transform (not to be confused with Discrete-Time Fourier Transform)

Consider any finite length signal $x[n]$. We can create a periodic signal $\tilde{x}[n]$ by repeating $x[n]$ after every N samples (N > length $x[n]$) $x[n] = \begin{cases} x[n], & 0 \leq n < N\\ \tilde{x}[n + N] \end{cases}$

We can express $\tilde{x}[n]$ as a DTFS: $\tilde{x}[n] = \frac{1}{N} \sum_{k} a_k e^{\frac{j 2 \pi k n}{N}}$

The DTFT coefficients $a_k$ filly describe $\tilde{x}[n]$ and can compose it.

But $x[n]$ can also be extracted from $\tilde{x}[n]$. Specifically $a_k$ are sample of $X(\Omega)$ drawn at $\Omega = \frac{2 \pi k}{N}$

This means that if you have any finit length sequenc of length $L \leq N$ then you don't need all of $X(\Omega)$ to characterize $x[n]$

It is sufficient to obtain N iniformly spaced sample of $X(\Omega)$

The uniformly spaces samples of the discrete time Fourier transform are called Discerte Fourier Transform

The DFT can be computed as the Fourier series coefficients of the periodic signal $\tilde{x}[n]$ composed from $x[n]$ \begin{align*} x_k &= \frac{1}{N} \sum_{n = 0}^{N - 1} \tilde{x}[n] e^{-\frac{j 2 \pi k n}{N}} \\ &= \frac{1}{N} \sum_{n=0}^{N-1} x[n] e^{-\frac{j 2 \pi k n}{N}} \end{align*} (i.e. you don't actually have to compose the periodic signal $\tilde{x}[n]$)

Back

### Properties of DTFT

The properties of the DTFT are similar to those of other Fourier representations we have studied

1. $X(\Omega)$ is periodic with $2 \pi$
2. Linearity $x[n] \leftrightarrow X(\Omega)$ $yn] \leftrightarrow Y(\Omega)$ $a x[n] + b y[n] \leftrightarrow a X(\Omega) + b Y(\Omega)$
3. Symmetry

If $x[n]$ is real-valued $X(\Omega) = X^*(-\Omega)$ i.e. Real($X(\Omega)$) is even Imag($X(\omega)$) is odd

alternately $|X(\Omega)|$ is even $\angle X(\Omega)$ is odd

4. If $x[n] = x^*[-n]$, $X(\Omega)$ is real \begin{align*} X(\Omega) &= \sum_{n = -\infty}^{\infty} x[n] e^{-j \Omega n} \\ &= x[0] + \sum_{n=1}^{\infty}(x[n]e^{-j \Omega n} + x[-n] e^{j \Omega n}) \\ &= x[0] + \sum_{n=1}^{\infty}(x[n]e^{-j \Omega n}) + (x[n] e^{-j \Omega n})^* \end{align*}

By $x[n] = x^*[-n]$, x[0] is real. The summation sum values & their complex conjugates * are real. The overall sum is real!

5. If $x[n] = -x^*[-n]$
$X(\Omega)$ is imaginary

Corollary:

If $x[n]$ is real & even

$X(\Omega)$ is real $even If$x[n]$is real & odd$X(\Omega)$is imaginary & odd 6. Time shifting $x[n] \leftrightarrow X(\Omega)$ $x[n- n_o] \leftrightarrow X(\Omega) e^{- j \Omega n_o}$ A time-shift is a phase shift in frequency 7. Frequency shifting $x[n] \leftrightarrow X(\Omega)$ $x[n] e^{j \Omega_o n} \leftrightarrow X(\Omega - \Omega_o)$ 8. Differencing $x[n] - x[n-1] \leftrightarrow (1 - e^{-j \Omega})X(\Omega)$ 9. Summation $y[n] = \sum_{m = -\infty}^{\infty} x[m]$ Note using property (8) we may assume that $y[n] - y[n-1] = x[n]$ $Y(\Omega) = \frac{X(\Omega)}{1 - e^{-j \Omega}}$ This would only be partially right. The correct answer is: $\sum_{m = -\infty}^{n}x[n] \leftrightarrow \frac{X(\Omega)}{1 - e^{-j \Omega}} + X(0) \sum_{k = -\infty}^{\infty} \delta(\Omega - 2 \pi k)$ Note$X(0) = \sum_{n=-\infty}^{\infty}x[n]as in the CT case. Example $\delta[n] \leftrightarrow 1$ $u[n] = \sum_{m = -infty}^{n} \delta(m) \leftrightarrow \frac{1}{1 - e^{-j \Omega}} + \pi \sum_{k = -\infty}^{\infty} \delta(\Omega - 2 \pi k)$ 10. Time Reversal $x[n] \leftrightarrow X(\Omega)$ $x[-n] \leftrightarrow X(-\Omega)$ Proof $y[n] = x[-n]$ \begin{align*} \sum_{n = -\infty}^{\infty} y[n]e^{-j \Omega n} &= \sum_{n = -\infty}^{\infty} x[-n]e^{-j \Omega n}\\ &= \sum_{n = -\infty}^{\infty}x[n]e^{-j(-\Omega)n} \\ &= X(-\Omega) \end{align*} 11. Unlike in CT, time-scaling must be carefully defined in DT becasue indices are integers. Let k be a positive integer. Define: $x_k[n] = \begin{cases} x[n/k], & n = \text{multiple } \text{of } \text{k} \\ 0, & else \end{cases}$ \begin{align*} X_k(\Omega) &= \sum_{n = -\infty}^{\infty} x_k[n]e^{-j \Omega n} \\ &= \sum_{r = -\infty}^{\infty}x_k[rk]e^{-j \Omega r k} \end{align*} (because the otherx_k[n]$terms are 0) $X_k(\Omega) = \sum_{r = -\infty}^{\infty}x[r]e^{-j(k \Omega)r}$ $x_k[n] \leftrightarrow X(k \Omega)$ As the signal stretches the spectrum shrinks. But note something off We get k repeating cycles withing$2 \pi! Unlike the CT case the spectrum is fundamentally changed On the other hand we do note that slowing down the signal lowers frequencies. Its only that it also ADDs weird higher frequencies. This happens because of the abrupt transitions from 0 to sample values. 12. What about time shrinking - shrinking the signal. We've seen earlier that this is not rivial. We'll revist this later. We will also consider non-integer cases of k later. 13. Differentiation of Frequency $x[n] \leftrightarrow X(\Omega)$ $j \frac{d X(\Omega)}{d \Omega} \leftrightarrow n x[n]$ Proof \begin{align*} X(\Omega) &= \sum_{n = -\infty}^{\infty} x[n]e^{0j \Omega n} \\ \frac{d X(\Omega)}{d \Omega } &= - \sum_{n = -\infty}^{\infty}j n x[n]e^{-j \Omega n} \\ &= \sum_{n = -\infty}^{\infty} (\frac{n x[n]}{j}) e^{-j \Omega n} \\ &= DTFT(\frac{n x[n]}{j}) \end{align*} $j \frac{dX(\Omega)}{d \Omega} \leftrightarrow n x[n]$ 14. Parseval's Relations $\sum_{n = -\infty}^{\infty} |x[n]|^2 = \frac{1}{2 \pi} \int_{<2 \pi>} |X(\Omega)|^2 d \Omega$ The energy in the signal is\frac{1}{2 \pi}$the energy in$X(\Omega)||X(\Omega)||^2is also called the energy density spectrum. 15. Convolution Property $x[n] \leftrightarrow X(\Omega)$ $y[n] \leftrightarrow Y(\Omega)$ $x[n] * y[n] \leftrightarrow X(\Omega) Y(\Omega)$ Proof $x[n] * y[n] = \sum_{k = -\infty}^{\infty}x[k]y[n-k]$ \begin{align*} DTFT(x[n]*y[n]) &= \sum_{n = -\infty}^{\infty} \sum_{k = -\infty}^{\infty}x[k]y[n-k]e^{-j \Omega n} \\ &= \sum_{k = -\infty}^{\infty}x[k] \sum_{n = -\infty}^{\infty} y[n-k]e^{-j \Omega n} \\ Let n-k =m, n = m+k \\ &=\sum_{k = -\infty}^{\infty} x[k] \sum_{m = -\infty}^{\infty}y[m]e^{-j \Omega (m + k)} \\ &= \sum_{k = -\infty}^{\infty}x[k]e^{-j \Omega k} \sum_{m = -\infty}^{\infty} y[m] e^{- j \Omega m} \\ &= X(\Omega) Y(\Omega) \end{align*} The convolution property is extremely important in the study of LTI systems. We will return to it shortly. 16. Modulation Property $x[n] \leftrightarrow X(\Omega)$ $y[n] \leftrightarrow Y(\Omega)$ $x[n] \cdot y[n] \leftrightarrow \frac{1}{2 \pi} \int_{<2 \pi>} X(\Theta) Y(\Omega - \Theta) d \Theta$ Proof Letz[n] = x[n] y[n]\begin{align*} Z(\Omega) &= \sum_{n = -\infty}^{\infty} x[n] y[n]e^{-j \Omega n} \\ &= \sum_{n = -\infty}^{\infty} x[n] \frac{1}{2 \pi} \int_{<2 \pi>} Y(\Theta) e^{j \Theta n}d \Theta \cdot e^{-j \Omega n} \\ &= \frac{1}{2 \pi} \int_{<2 \pi>} Y(\Theta) \sum_{n = -\infty}^{\infty} x[n] e^{-j (\Omega - \Theta)n}d \Theta \\ &=\frac{1}{2 \pi} \int_{<2 \pi>} Y(\Theta) X(\Omega - \Theta) d \Theta \\ &= \frac{1}{2 \pi} \int_{<2 \pi>} X(\Theta) Y(\Omega - \Theta) d \Theta \end{align*} The DTFT of the product of two signals is their convultion of their DTFTs. However the convolution is a circular convolution becasueX(\Omega)$&$Y(\Omega)$are preiodic Back ### The Relationship of Properties to Systems We now see the particular importance of the convolution property and the time shift property in analyzing the behavior of LSI systems. Recall the properties are: $x[n] * y[n] \leftrightarrow X(\Omega Y(\Omega))$ $x[n - n_o] \leftrightarrow X(\Omega)e^{-j \Omega n_o}$ Consider an LSI system with impulse response$h[n]$. For such a system for any input$x[n]$the ouput$y[n]$is given by: $y[n] = x[n]* h[n] = \sum_{k = -\infty}^{\infty}x[k]h[n-k]$ How can we find out how this system will affect the input? The convolution equation helps us here: $Y(\Omega) = X(\Omega) H(\Omega)$ We know that passing$x$through system$h[]$will eliminate low frequnecies. Now consider another situation. We are given the following difference equation that specifies a system: $y[n] = \sum_{k =0}^{K}a_k x[n -k] + \sum_{k = 1}^{M} b_k y[n-k]$ How do we: • compute its impulse response • find out how it affects a signal We use the time shift property to solve this. Taking DTFT on both sides we get: $Y(\Omega) = \sum_{k = 0}^{K} a_k X(\Omega) e^{-j \Omega k} + \sum_{k = 1}^{M} b_k Y(\Omega) e^{-j \Omega k}$ $Y(\Omega)(1 - \sum_{k = 1}^{M} b_k e^{-j \Omega k}) = X(\Omega) \sum_{k = 0}^{K}a_k e^{-j \Omega k}$ $Y(\Omega) = X(\Omega) = \frac{\sum_{k=0}^{K}a_k e^{ij \Omega k}}{1 - \sum_{k=1}^{M}b_k e^{-j \Omega k}}$ But we know that since the system is LSI, if its impulse response is$h[n]$$Y(\Omega) = X(\Omega) H(\Omega)$ So comparing the two equations above we get: $H(\Omega) = \frac{\sum_{k=0}^{K}a_k e^{-j \Omega k}}{1 - \sum_{k=1}^{M}b_k e^{-j \Omega k}}$ To compute the actualy impulse response we only have to take the inverse DTFT of$H(\Omega)$To see how it affects the signal we can analyze$H(\Omega)$. As we will see later, there are easy ways to do this. Back ### Inverse DTFT Examples To round off our discussion of DTFTs lets see some examples of how to compute a signal given only its DTFT. 1.$H(\Omega) = cos^2(\Omega)$. What is$h[n]$? We can write $cos(\Omega) = \frac{e^{j \Omega} + e^{-j \Omega}}{2}$ $cos^2(\Omega) = \frac{1}{4}e^{j 2 \Omega} + \frac{1}{4} e^{-j 2 \Omega} + \frac{1}{2}$ We know that:$\delta[n] \leftrightarrow 1C \delta[n] \leftrightarrow C$We also known from the time-shift property:$\delta[n-n_o] \leftrightarrow e^{-j \Omega n_o}\$
\begin{align*} IDTFT(\frac{1}{4}e^{j 2 \Omega} + \frac{1}{4} e^{-j \Omega n} + \frac{1}{2}) &= \\ &= IDTFT(\frac{1}{4}e^{j2 \Omega}) + IDTFT(\frac{1}{4}e^{-j2 \omega}) + IDTFT(\frac{1}{2}) \\ &= \frac{1}{4} \delta[n+2] + \frac{1}{4} \delta[n - 2] + \delta[n] \end{align*}
Back