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.
So we talk about radians/sec or cycles/sec (Hz)
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
Thus DT frequencies are measures in radians, and not radians/sec
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
This is the DT counterpart of the sinc function. Its periodic with $2 \pi$.
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]\]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.
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
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]$)
The properties of the DTFT are similar to those of other Fourier representations we have studied
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
By $x[n] = x^*[-n]$, x[0] is real. The summation sum values & their complex conjugates * are real. The overall sum is real!
$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
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)\]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 other $x_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 changedOn 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.
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.
The energy in the signal is $\frac{1}{2 \pi}$ the energy in $X(\Omega)$
$||X(\Omega)||^2$ is also called the energy density spectrum.
The convolution property is extremely important in the study of LTI systems. We will return to it shortly.
The DTFT of the product of two signals is their convultion of their DTFTs. However the convolution is a circular convolution becasue $X(\Omega)$ & $Y(\Omega)$ are preiodic
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: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.
To round off our discussion of DTFTs lets see some examples of how to compute a signal given only its DTFT.
$\delta[n] \leftrightarrow 1$
$C \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*} \]